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

北 京 化 工 大 学 试 卷 2004.6离 散 数 学（参考答案）一、填空题（共10分，每小题2分）1.$xF(x)yG(y,z)的前束范式是 xy(F(x)yG(y,z) ) 。2.(pq)p是（永真/永假/可满足） 永真 式。3.设全集E=1,2,3,4,5,6，其子集A=1,4,B=1,2,5，则AB= 4 。 4.设集合M=a,b,c,d,e，则M上一共有 52 个不同的等价关系。 5.设f：NNN，f () = x+y+1，令A= | x,yN且f ()=3，则A的列举法表示为A= , 。二、判断题（共10分，每小题2分，正确的在题号前打，错误的在题号前打）( ) 1. 设X=a,b,c,d，Y= 1,2,3，f=,，则f 是从X 到Y 的二元关系，但不是从X 到Y 的函数。( ) 2.已知A和B为两个集合，且AB，则A B一定为假。( ) 3.设p,q,r,s为命题公式，如果p q且r s，则pr qs。( ) 4.一个谓词公式，如果量词均出现在全式的开头，则称该谓词公式为前束范式。( ) 5. 设R是A上的自反关系，且当R和R时，必有R，则R是A上的等价关系。三、选择题（共10分，每小题2分）1.设个体域为整数集，P(x,y)：x+y = 1，Q(x,y)：xy 0，下列命题为真的是（ A ）。 A、x$ y P(x,y) B、$ xyP(x,y)C、x$ y Q(x,y) D、$ xyQ(x,y)2.设R是集合A上的自反关系，则下列叙述中不成立的是（ C ）。A、RR-1一定是A上的自反关系B、RR-1一定是A上的对称关系 C、RR-1一定是A上的传递关系D、仅有A和B是正确的3.下列命题真值为真的是（ A ）。 A、23当且仅当57B、23当且仅当57C、2+24与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 | xN且x是偶素数 D、A=1,2,，B=1,2,5. 在谓词演算中，若谓词公式中含有自由变元，则不能被使用的规则是（ C ）。A、US规则 B、UG规则 C、ES规则 D、EG规则四、简答及计算题（共30分，每题10分）1采用真值表求命题公式(pq)(pr)的主析取范式和主合取范式。解：求解过程（4分）pqrpqpr(pq)(pr)000000001011010000011011100000101000110101111101主析取范式（3分）：(pq)(pr) m1m3m6m7(pqr)(pqr)(pqr)(pqr)主合取范式（3分）：(pq)(pr)M0M2M4M5=(pqr)(pqr)(pqr)(pqr)2设A=a,b,c,d,e,f ，R是A上的二元关系，其关系定义如下：R=,求最小自然数s和t，使得s t 且 Rs=Rt。解：求解过程（6分）R=,R2=,R3=,R4=,R5=,R6=,（4分）因此有：R6=IA= R0 即：s =0，t=6fdcaefb3如图为偏序集的哈斯图。（1）给出X和的集合表示（6分）；（2）求该偏序集的极大元、极小元、最大元和最小元（4分）。解：X =a,b,c,d,e,f X =,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）（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为集合，已知(AC)(BC), (AC)(BC),证明：AB。解： A= A(CC) = (AC)(AC) (BC)(BC) = B(CC) =B故：AB3采用形式证明法证明下面的推理：如果周强是上海人，则他是复旦大学或中山大学的学生；如果他不想离开上海，他就不是中山大学的学生；周强是上海人并且不想离开上海，所以他是复旦大学的学生。解：令：p：周强是上海人，q：周强是复旦大学的学生，r：周强是中山大学的学生，s：周强想离开上海。（3分）前提：p(qr)，sr，ps结论：q（3分）（4分）（1）psP（2）sT（1）（3）srP（4）rT（2）（3）（5）p(qr)P（6）pT（1）（7）qrT（5）（6）（8）qT（4）（7）4设集合A=a,b,c ，R是A上的二元关系，且：R=, (1) 判断R是否是等价关系？请给出证明。若是，请继续完成下面3个问题。 (2) 求A中每一个元素的等价类； (3) 求A对R的商集A/R； (4) 求由R诱导的A的划分AR。解：（1）（4分）=(aij)33因为aii=1（i=1,2,3,4），故R是自反的；因为aij=aji（i,j=1,2,