2010级离散数学(I)A卷参考答案

北京化工大学试卷2004.6离散数学（参考答案）一、填空题（共10分，每小题2分）1.xF(x)→yG(y,z)的前束范式是xy(F(x)→yG(y,z))。2.(p→q)∨p是（永真/永假/可满足）永真式。3.设全集E={1,2,3,4,5,6}，其子集A={1,4},B={1,2,5}，则A∩~B={4}。4.设集合M={a,b,c,d,e}，则M上一共有52个不同的等价关系。5.设f：N×N→N，f(x,y)=x+y+1，令A={x,y|x,y∈N且f(x,y)=3}，则A的列举法表示为A={1,1,2,0,0,2}。二、判断题（共10分，每小题2分，正确的在题号前打，错误的在题号前打×）(√)1.设X={a,b,c,d}，Y={1,2,3}，f={a,1,b,2,c,3}，则f是从X到Y的二元关系，但不是从X到Y的函数。(×)2.已知A和B为两个集合，且AB，则AB一定为假。(√)3.设p,q,r,s为命题公式，如果pq且rs，则p∧rq∧s。(×)4.一个谓词公式，如果量词均出现在全式的开头，则称该谓词公式为前束范式。(√)5.设R是A上的自反关系，且当a,b∈R和a,c∈R时，必有b,c∈R，则R是A上的等价关系。三、选择题（共10分，每小题2分）1.设个体域为整数集，P(x,y)：x+y=1，Q(x,y)：x×y0，下列命题为真的是（A）。A、xyP(x,y)B、xyP(x,y)C、xyQ(x,y)D、xyQ(x,y)2.设R是集合A上的自反关系，则下列叙述中不成立的是（C）。A、RR-1一定是A上的自反关系B、RR-1一定是A上的对称关系C、RR-1一定是A上的传递关系D、仅有A和B是正确的3.下列命题真值为真的是（A）。A、23当且仅当57B、23当且仅当57C、2+2≠4与4+4=8互为充分必要条件D、如果π无理数，则3也是无理数，反之亦然4.下列每组两个集合中相等的一组集合是（A）。A、A={3,1,1,5,5}，B={1,3,5}B、A=，B={}C、A=，B={x|x∈N且x是偶素数}D、A={1,2,}，B={1,2,{}}5.在谓词演算中，若谓词公式中含有自由变元，则不能被使用的规则是（C）。A、US规则B、UG规则C、ES规则D、EG规则四、简答及计算题（共30分，每题10分）1．采用真值表求命题公式(p∧q)∨(~p∧r)的主析取范式和主合取范式。解：求解过程（4分）pqrp∧q~p∧r(p∧q)∨(~p∧r)000000001011010000011011100000101000110101111101主析取范式（3分）：(p∧q)∨(~p∧r)m1∨m3∨m6∨m7(~p∧~q∧r)∨(~p∧q∧r)∨(p∧q∧~r)∨(p∧q∧r)主合取范式（3分）：(p∧q)∨(~p∧r)M0∨M2∨M4∨M5=(p∨q∨r)∧(p∨~q∨r)∧(~p∨q∨r)∧(~p∨q∨~r)2．设A={a,b,c,d,e,f}，R是A上的二元关系，其关系定义如下：R={a,b,b,c,c,a,e,f,f,e}求最小自然数s和t，使得st且Rs=Rt。解：求解过程（6分）R={a,b,b,c,c,a,e,f,f,e}R2={a,c,b,a,c,b,e,e,f,f}R3={a,a,b,b,c,c,e,f,f,e}R4={a,b,b,c,c,a,e,e,f,f}R5={a,c,b,a,c,b,e,f,f,e}R6={a,a,b,b,c,c,e,e,f,f}（4分）因此有：R6=IA=R0即：s=0，t=63．如图为偏序集X,≤的哈斯图。（1）给出X和≤的集合表示（6分）；（2）求该偏序集的极大元、极小元、最大元和最小元（4分）。解：X={a,b,c,d,e,f}X={a,b,a,c,a,d,a,e,a,f,b,e,c,e,c,f,d,f}∪IX极大元e,f，极小元a，最大元不存在，最小元a五、证明题（共40分，每题10分）1．采用形式证明推理证明下式：已知：x(~P(x)Q(x))，x(Q(x)~R(x))，xR(x)结论：xP(x)解：（1）xR(x)P（2）R(c)ES（1）（3）x(Q(x)~R(x))P（4）Q(c)~R(c)US（3）（5）~Q(c)T（2）（4）fdcaefb（6）x(~P(x)Q(x))P（7）~P(c)Q(c)US（6）（8）P(c)T（5）（7）（9）xP(x)EG（8）2．设A,B,C为集合，已知(A∩C)(B∩C),(A∩~C)(B∩~C),证明：AB。解：A=A∩(C∪~C)=(A∩C)∪(A∩~C)(B∩C)∪(B∩~C)=B∩(C∪~C)=B故：AB3．采用形式证明法证明下面的推理：如果周强是上海人，则他是复旦大学或中山大学的学生；如果他不想离开上海，他就不是中山大学的学生；周强是上海人并且不想离开上海，所以他是复旦大学的学生。解：令：p：周强是上海人，q：周强是复旦大学的学生，r：周强是中山大学的学生，s：周强想离开上海。（3分）前提：p(q∨r)，~s~r，p∧~s结论：q（3分）（4分）（1）p∧~sP（2）~sT（1）（3）~s~rP（4）~rT（2）（3）（5）p(q∨r)P（6）pT（1）（7）q∨rT（5）（6）（8）qT（4）（7）4．设集合A={a,b,c}，R是A上的二元关系，且：R={a,a,b,b,b,c,c,c,c,b}(1)判断R是否是等价关系？请给出证明。若是，请继续完成下面3个问题。(2)求A中每一个元素的等价类；(3)求A对R的商集A/R；(4)求由R诱导的A的划分AR。解：（1）（4分）110110001M=(aij)3×3332)(110110001110110001110110001ijbM因为aii=1（i=1,2,3,4），故R是自反的；因为aij=aji（i,j=1,2,3,4），故R是对称的；因为bij=1，则有aij=1（i,j=1,2,3,4），故R是传递的。故R是等价关系。（2）（2分）[1]R={1}[2]R=[3]R={2,3}（3）（2分）商集A/R={{1},{2,3}}（4）（2分）划分A={{1},{2,3}}