2007级离散数学I

北京化工大学2007——2008学年第一学期
《离散数学(I)》期末考试试卷
班级：姓名：学号：分数：
一、填空题（共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）A/R及由等价关系R诱导的A的划分A R。

2.（共10分）
（1）令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，其中个体域为自然数集，用以上符号表示命题：对任意的x，x+y=x当且仅当y=0。

（2）证明如下推理：
前提：p→﹁q,r→q,r
结论：﹁p
3.（共10分）设X={1,2,3,4}是集合
（1）证明：<ρ(X),⊆>是偏序集；
（2）对集合ρ(X)，求其最大元和最小元。

其中ρ(X)是X的幂集，⊆是集合的包含关系。

4.（共10分）证明：((A∪B)∩(A∪B∪C))-((A-B)∩C)∪(A-B))=B。