级离散数学I.docVIP

北京化工大学2007——2008学年第一学期 《离散数学(I)》期末考试试卷 课程代码 M A T 2 1 3 2 T 班级： 姓名： 学号： 分数： 题号 一 二 三 四 总分 得分 一、填空题（共20分，每小题2分） 1.已知命题公式A(P,Q,R)的主析取范式为m1∨m2∨m5∨m6，它的主合取范式为 。 2.任意两个不同极小项的合取为 式。 3.命题公式P∨(Q∧~R)的真值为真的解释为 。 4.设个体域D={1,2}，命题(x(y(x+y=3)的真值为 。 5.设I为整数集合，A={x| x2＜30,x(I }，B={x| x是素数,x＜20}，C={1,3,5}则(C-A)∩(B-A)= 。 6.设{0,1}上的关系R={0,0,0,1}，则R的自反闭包r(R)= 。 7.设R是集合{1,2,…,10}上的模7等价关系，则[2]R= 。 8.设A={a,b,c,d,e,f,g}，A上的一个划分(={{a,b},{c,d,e},{f,g}}，则(所诱导的等价关系R应有 个元素（序偶）。 9.设个体域D={0,1}，消去公式(xP(x)∧(yQ(y)中的量词，可得 。 10.谓词公式(x(yP(x,y)的否定式为 。 二、判断题（共20分，每小题2分，正确的在题号前打(，错误的在题号前打×） 1.对于任意集合S，都有{S}(P(S)。2.若R是集合X上的等价关系，则商集X/R是X的一个划分。3.若P∪Q=Q，P∩Q=Φ，则P=Φ。4.给定命题公式A,B,C，若A(B，B(C，则A(C。5.设A,B是集合，则A(B和A(B可能同时成立。6.一个不是自反的二元关系一定是反自反的。7.集合{1,2,3}上的一个关系R={1,2,1,3}，R显然不是传递关系。8.一个命题的析取范式是唯一的。9.对于任意的集合A,B,C，都有A((B∪C)=(A(B)∪(A(C)。10.在谓词公式中，一个变元要么是自由的，要么是约束的。 三、选择题（共20分，每小题2分） 1.设A,B,C都是集合，若A∪B=A∪C，则 。 A B(C B C(B C C=B D C和B不一定相等 2.若A是素数集合，B是奇数集合，则A-B= 。 A {2} B {3} C {5} D {0} 3.设S是一任意集合，且|S|=3，则S上不同的等价关系有 个。 A {8} B {9} C {5} D {6} 4.下面的命题中， 是假命题。 A 若2是奇数，则一个公式的合取范式是唯一的。 B 若2是奇数，则一个公式的合取范式不唯一。 C 若2是偶数，则一个公式的合取范式是唯一的。 D 若2是偶数，则一个公式的合取范式不唯一。 5.设有命题“x是偶数或y是负数”，则该命题的否定是 。 A x是偶数或y不是负数 B x是奇数或y不是负数 C x是奇数且y不是负数 D x不是偶数且y不是负数 6.在谓词演算中，P(a)是(xP(x)的有效结论，其理论根据是 。 A US规则 B UG规则 C ES规则 D EG规则 7.重言式的否定式是 。 A 重言式 B 矛盾式 C 可满足式 D 蕴涵式 8.给定命题公式P,Q，若 为永真式，则称Q为P的有效结论。 A P→Q B Q→P C P↓Q D P↑Q 9.如果P(Q成立，则 也成立。 A Q(P B ~P(~Q C ~Q(~P D ~P(Q 10.若个体域为整数域，则下列公式中 为真。 A (x(y(x+y=0) B (x(y(x+y=0) C (x(y(x+y=0) D (y(x(x+y=0) 四、计算与证明题 1.（共10分）设A={a,b,c,d}，R是A上的等价关系，且 R={a,a,a,b,b,a,b,b,c,c,c,d,d,c,d,d} 求： （1）证明R是等价关系；（2）每一个元素的等价类；（3