资源描述：
《离散试题及解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、考试时间：2008年6月12日北京化工大学2007——2008学年第二学期《离散数学（I）》期末考试试卷课程代码MAT2132T班级：姓名：学号：分数：题号一二三四总分得分一、填空题（共20分，每小题2分）1.已知命题公式A(P,Q,R)的主析取范式为m1∨m2∨m5∨m6，它的主合取范式为M0∧M3∧M4∧M7。2.任意两个不同极小项的合取为永假式。3.命题公式P∨(Q∧~R)的真值为真的解释为100，101，110，111，010。4.设个体域D={1,2}，命题"x$y(x+y=3)的真值为1。5.设I为整数集合，A={x
2、x2＜30,xÎI}，B={x
3、x是素数，x＜2
4、0}，C={1,3,5}则(C-A)∩(B-A)=Φ。6.设{0,1}上的关系R={<0,0>,<0,1>}，则R的自反闭包r(R)=R∪{<1,1>}。7.设R是集合{1,2,…,10}上的模7等价关系，则[2]R={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.谓词公式$x"yP(x,y)的否定式为"x$y~P(x,y)。二、判断题（共2
5、0分，每小题2分，正确的在题号前打Ö，错误的在题号前打×）1.对于任意集合S，都有{S}ÍP(S)。（Y）2.若R是集合X上的等价关系，则商集X/R是X的一个划分。（Y）3.若P∪Q=Q，P∩Q=Φ，则P=Φ（Y）4.给定命题公式A,B,C，若AÞB，BÞC，则AÞC。（Y）5.设A,B是集合，则AÍB和AÎB可能同时成立。（Y）6.一个不是自反的二元关系一定是反自反的。（N）7.集合{1,2,3}上的一个关系R={<1,2>,<1,3>}，R显然不是传递关系。（N）8.一个命题的析取范式是唯一的。(N)9.对于任意的集合A,B,C，都有A´(B∪C)=(A´B)∪(A´C)。
6、（Y）10.在谓词公式中，一个变元要么是自由的，要么是约束的。（N）三、选择题（共20分，每小题2分）1.设A,B,C都是集合，若A∪B=A∪C，则D。ABÉCBC¹BCC=BDC和B不一定相等2.若A是素数集合，B是奇数集合，则A-B=A。A{2}B{3}C{5}D{0}3.设S是一任意集合，且
7、S
8、=3，则S上不同的等价关系有C个。A8B9C5D64.下面的命题中，C是假命题。A若2是奇数，则一个公式的合取范式是唯一的。B若2是奇数，则一个公式的合取范式不唯一。C若2是偶数，则一个公式的合取范式是唯一的。D若2是偶数，则一个公式的合取范式不唯一。5.设有命题“x是偶数或y是
9、负数”，则该命题的否定是D。Ax是偶数或y不是负数Bx是奇数或y不是负数Cx是奇数且y不是负数Dx不是偶数且y不是负数6.在谓词演算中，P(a)是"xP(x)的有效结论，其理论根据是A。AUS规则BUG规则CES规则DEG规则7.重言式的否定式是B。A重言式B矛盾式C可满足式D蕴涵式8.给定命题公式P,Q，若A为永真式，则称Q为P的有效结论。AP→QBQ→PCP↓QDP↑Q9.如果PÞQ成立，则C也成立。AQÞPB~PÞ~QC~QÞ~PD~PÞQ10.若个体域为整数域，则下列公式中A为真。A"x$y(x+y=0)B$x"y(x+y=0)C"x"y(x+y=0)D$y"x(x+y
10、=0)四、计算与证明题1.（共5分）证明：((A∪B)∩(A∪B∪C))-(((A-B)∩C)∪(A-B))=B。解((A∪B)∩(A∪B∪C))-(((A-B)∩C)∪(A-B))=(A∪B)-((A-B)∩C)∪(A-B))=(A∪B)-(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分）证明如下推理：前提：p→﹁q,r→q,r结论：﹁p证明：证明序列如下：(1)rP规则(2)r→qP规则(3)q
11、T规则,(1)(2)(4)p→﹁qP规则(5)q→﹁pT规则,(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是等
