离散试题及解答

考试时间：2008年6月12日北京化工大学20072008学年第二学期 离散数学（I） 期末考试试卷课程代码MAT2132T班级： 姓名： 学号： 分数： 题号一 二三四总分得分 一、填空题（共20分，每小题2分）1.已知命题公式A(P,Q,R)的主析取范式为m1m2m5m6，它的主合取范式为M0M3M4M7。2.任意两个不同极小项的合取为 永假 式。3.命题公式P(QR)的真值为真的解释为 100，101，110，111，010 。4.设个体域D=1,2，命题x$y(x+y=3)的真值为 1 。5.设I为整数集合，A=x| x230,xI ，B=x| x是素数，x20，C=1,3,5则(C-A)(B-A)= 。6.设0,1上的关系R=,，则R的自反闭包r(R)= R 。7.设R是集合1,2,10上的模7等价关系，则2R= 2,9 。8.设A=a,b,c,d,e,f,g，A上的一个划分p=a,b,c,d,e,f,g，则p所诱导的等价关系R应有 17 个元素（序偶）。9.设个体域D=0,1，消去公式xP(x)$yQ(y)中的量词，可得 P(0)P(1)(Q(0)Q(1) 。10.谓词公式$xyP(x,y)的否定式为 x$yP(x,y) 。二、判断题（共20分，每小题2分，正确的在题号前打，错误的在题号前打）1.对于任意集合S，都有SP(S)。（Y）2.若R是集合X上的等价关系，则商集X/R是X的一个划分。（Y）3.若PQ=Q，PQ=，则P= （Y） 4.给定命题公式A,B,C，若AB，BC，则AC。（Y）5.设A,B是集合，则AB和AB可能同时成立。（Y）6.一个不是自反的二元关系一定是反自反的。（N）7.集合1,2,3上的一个关系R=,，R显然不是传递关系。（N）8.一个命题的析取范式是唯一的。(N)9.对于任意的集合A,B,C，都有A(BC)=(AB)(AC)。（Y）10.在谓词公式中，一个变元要么是自由的，要么是约束的。（N）三、选择题（共20分，每小题2分）1.设A,B,C都是集合，若AB=AC，则 D 。 A BC B CB C C=B D C和B不一定相等2.若A是素数集合，B是奇数集合，则A-B= A 。 A 2 B 3 C 5 D 0 3.设S是一任意集合，且|S|=3，则S上不同的等价关系有 C 个。 A 8 B 9 C 5 D 6 4.下面的命题中， C 是假命题。 A 若2是奇数，则一个公式的合取范式是唯一的。 B 若2是奇数，则一个公式的合取范式不唯一。 C 若2是偶数，则一个公式的合取范式是唯一的。 D 若2是偶数，则一个公式的合取范式不唯一。5.设有命题“x是偶数或y是负数”，则该命题的否定是 D 。A x是偶数或y不是负数 B x是奇数或y不是负数 C x是奇数且y不是负数 D x不是偶数且y不是负数6.在谓词演算中，P(a)是xP(x)的有效结论，其理论根据是 A 。 A US规则 B UG规则 C ES规则 D EG规则7.重言式的否定式是 B 。 A 重言式 B 矛盾式 C 可满足式 D 蕴涵式8.给定命题公式P,Q，若 A 为永真式，则称Q为P的有效结论。 A PQ B QP C PQ D PQ9.如果PQ成立，则 C 也成立。 A QP B PQ C QP D PQ10.若个体域为整数域，则下列公式中 A 为真。 A x$y(x+y=0) B $xy(x+y=0) C xy(x+y=0) D $yx(x+y=0)四、计算与证明题1.（共5分）证明：(AB)(ABC)-( ( (A-B)C)(A-B)=B。解 (AB)(ABC)-( ( (A-B)C)(A-B) =(AB)-(A-B)C)(A-B) =(AB)-(A-B) =B2.（共5分）令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，其中个体域为自然数集，用以上符号表示命题：对任意的x，x+y=x当且仅当y=0。解：x(S(x,y,x)G(y,0)3.（共10分）证明如下推理：前提：pq,rq,r结论：p证明：证明序列如下：(1) rP规则(2) rqP规则(3) qT规则,(1)(2)(4) pqP规则(5) qpT规则,(4)(6) pT规则,(3)(5)4.（共10分）设A=a,b,c,d，R是A上的等价关系，且R=,求：（1）证明R是等价关系；(4分)（2）求每一个元素的等价类；(3分)（3）求A/R及由等价关系R诱导的A的划分AR。(3分)解 （1）可见该矩阵的对角元均为1，故R是自反的。又该矩阵是对称的，故R是对称的。可见R是传递的。故R是等价关系。（2）aR=bR=a,b,cR=dR=c,d（3）A/R=a,b,c,d，AR=a,b,c,d5.（共10分）设X=1,2,3,4是集合（1）证明：是偏序集；(4分)（2）对集合r(X)，求其最大元和最小元，极大元和极小元，上确界和下确界。其中r(X)是X的幂集，是集合的包含关系。(6分)证明： Ar(X)，则有AA，故，即是自反的。 A,Br(X)，若且，则必有AB且BA，因此A=B，故是反对称的。 A,B,Cr(X)，若且，则有AB且BC，必有AC，故是传递的。 综上证明，知是偏序关系，即是偏序集。P(X)= 1 2 3