《离散数学（上）》考试试卷（B卷）
（时间120分钟）
院/系 专业 姓名 学号
| 题 号 | 一 | 二 | 三 | 四 | 五 | 总分 |
| 得 分 |
| 得分 |
1.设天下雨，小王乘汽车上班，则命题“仅当天下雨，小王才乘汽车上班”可符号化为（ ）
A.； B.； C.； D.。
2.设个体域为, , ,则下列公式为真的是( ）
A.； B.； C.； D.。
3.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于( )
A.( x)A(x)→B B.( x)A(x)→B
C.A(x)→B D.( x)A(x)→(x)B
4.对任意集合，下列各式中一定成立的是（ ）
A.； B.；
C.； D.。
5.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )
A.R∪IA B.R C.R∪{〈c,a〉} D.R∩IA
6.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )
A. ｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉}
C. {〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉}
7.下列式子正确的是( )
A.∈ B. C.{ } D.{ }∈
8.以下命题公式中，为永假式的是( )
A.p→(p∨q∨r) B.(p→┐p)→┐p
C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p)
9.设和是非空集合的划分，则下列集合一定是的划分的是（ ）
A. B. C. D.
10.设和分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（ ）
A. B. C. D.（）
| 得分 |
1.（ ）联结词集合为全功能的。
2.（ ）（（PQ）（QR））（PR）为重言式。
3.（ ）R是A上的二元关系，R是自反的，当且仅当r(R)=R。
4.（ ）集合A上的等价关系确定了A的一个划分。
5.（ ）R是集合A上的关系，R有传递性的充要条件是RoRR。
| 得分 |
1. 设：是偶数，：是质数，：是整数，：是负数，则在全总个体域下
“有某个质数其平方是偶数”符号化为： ；
“对任何两个整数和，或是非负的”符号化 。
2. 命题{{a}} {{a},3,4,1} 的真值 = __ __ 。
3. 公式的自由变元是 , 约束变元是 。
4.个命题变元的真值有＿＿ ＿种不同的组合；个命题变元可构造＿ ＿＿个不同的主析取范式。
5. 集合上有＿＿ ＿个不同的二元关系，＿＿ ＿个不同的等价关系。
6. 集合上的关系的传递闭包为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。
| 得分 |
1. 求的主析取范式和主合取范式。
2. 设R是集合上的关系
（1）画出R的关系图;
（2）证明R是等价关系；
（3）写出R的所有等价类。
3. 设为偏序集，其中，是上整除关系。
(1) 画出的哈斯图；
(2) 求的极大元和极小元；
(3) 令，求的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。
| 得分 |
1. 设为实数集合，为自然数集合，证明：。
2. 用推理规则证明：{ P∨Q, P→R, Q→S, R→(P∧Q)}蕴涵S 。
安徽大学20 10 —20 11 学年第 1 学期
《离散数学（上）》考试试题（B卷）参及评分标准
一、单选题（每小题2分，共20分）
1.B；2.A；3.A；4.C；5.C；6.D；7.B；8.C；9.D；10.D。
二、判断题（每小题1分，共10分。对的打√，错的打×）
1.×；2.√；3.√；4.√；5.√。
三、填空题（每小空2分，共20分）
1.，；
2. T或真或1； 3. y,x； x,z；
4.；； 5.或65536；； 6.。
四、计算题（每小题10分，共30分）
1.
4分
（主析取范式） 8分
（主合取范式） 10分
2. .
(1) R的关系图
4分
(2) 因为 R满足自反、对称和传递性，所以R是等价关系； 3分
(3) 等价类：{1, 3}, {2, 5}, {4}。 3分
3. (1) 的哈斯图为
4分
(2) 的极大元为：12，14，16，18，20，极小元为2； 2分
(3) 的极大元为：8，12，极小元为6，8；的最大元和最小元都不存在； 2分
的上界不存在，下界为2；的上确界不存在，下确界为2。 2分
五、证明题（每小题10分，共20分）
1. 设，，则是从到的单射函数，所以。 3分
构造从到的函数如下：
7分
其中为负整数集合，则是从到的单射函数（双射函数），所以。
综合以上，。 10分
2.证:
(1) P∨Q P
(2) R→(P∧Q) P
(3) R∨ (P∨Q) T(2)
(4) (P∨Q)→R T(3) 1分
(5) R T(1)(4) 2分
(6) P→R P
(7) R→P T (6) 1分
(8) P T(5)(7) 2分
(9) Q T(1)(8) 2分
(10) Q→S P
(11) S T(9)(10) 2分
所以 { P∨Q, P→R, Q→S, R→(P∧Q)}蕴涵S .
