计算机学院2010—2011年离散数学（上）B卷和参考答案及评分标准

安徽大学20 10 — 20 11 学年第 1 学期 《离散数学（上）》考试试卷（B卷）

（时间120分钟）

院/系 专业 姓名 学号

题 号 得 分

一 二 三 四 五 总分 一、单选题（每小题2分，共20分）

得分 Q:小王乘汽车上班，1. 设P:天下雨，则命题“仅当天下雨，小王才乘汽车上班”可符号化为（ ）

A.P?Q； B.Q?P； C.P?Q； D.P?Q。

2. 设个体域为D?{a,b},F(a,a)?F(a,b)?0,F(b,a)?F(b,b)?1,则下列公式为真的是( ）

A. ?x?yF(x,y)； B. ?x?yF(x,y)； C.?x?yF(x,y)； D.??x?yF(x,y)。 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，下列各式中一定成立的是（ ）

A.A?(B?C)?(A?B)?(A?C)； B. A?(B?C)?(A?B)?(A?C)； C. A?(B?C)?(A?B)?(A?C)； D. (A?B)?C?A?(B?C)。

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. 设?1和?2是非空集合A的划分，则下列集合一定是A的划分的是（ ）

A.?1??2 B.?1??2 C.?1??2 D.?1?(?2??1)??1

10. 设N和R分别为自然数和实数集合，则下列集合中与其他集合的基数不同的集合是（ ）

A.R B.N C.?(N) D.N（n?N）

《离散数学（上）》试卷 第 1 页 共 4 页

Nn

二、判断题（每小题2分，共10分。对的打√，错的打×）

1. （ ）联结词集合{?,?}为全功能的。

2. （ ）（（?P?Q）?（Q?R））?（P?R）为重言式。

3. （ ）R是A上的二元关系，R是自反的，当且仅当r(R)=R。 4. （ ）集合A上的等价关系确定了A的一个划分。

5. （ ）R是集合A上的关系，R有传递性的充要条件是RoR?R。

得分 三、填空题（每小空2分，共20分）

得分 1. 设E(x)：x是偶数，P(x)：x是质数，I(x)：x是整数，N(x)：x是负数，则在全总个体域下 “有某个质数其平方是偶数”符号化为： ； “对任何两个整数x和y，x?y或y?x是非负的”符号化 。 2. 命题{{a}} ? {{a},3,4,1} 的真值 = __ __ 。

3. 公式?x(P(x)?Q(x,y))??z(R(y,z)?S(x))的自由变元是 , 约束变元

是 。

4. n个命题变元的真值有＿＿ ＿种不同的组合；n个命题变元可构造＿ ＿＿个不同的

主析取范式。

5. 集合A?{1,2,3,4}上有＿＿ ＿个不同的二元关系，＿＿ ＿个不同的等价关系。 6. 集合A上的关系{?1,2?,?2,1?,?2,3?}的传递闭包为＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

四、计算题（每小题10分，共30分）

1. 求P?Q?P的主析取范式和主合取范式。

《离散数学（上）》试卷 第 2 页 共 4 页

得分

2. 设R是集合A?{1,2,3,4,5}上的关系

R?{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}

（1）画出R的关系图; （2）证明R是等价关系； （3）写出R的所有等价类。

3. 设?A,R?为偏序集，其中A?{2,4,6,?,20}，R是A上整除关系。 (1) 画出?A,R?的哈斯图； (2) 求A的极大元和极小元；

(3) 令B?{6,8,12}，求B的极大元、极小元、最大元、最小元、上界、下界、上确界和下确界。

《离散数学（上）》试卷 第 3 页 共 4 页

五、证明题（每小题10分，共20分）

1. 设R为实数集合，N为自然数集合，证明：|R?N|?|R|。

2. 用推理规则证明：{ P∨Q, P→R, Q→S, R→(?P∧?Q)}蕴涵S 。

得分 《离散数学（上）》试卷 第 4 页 共 4 页

安徽大学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. ?x(P(x)?E(x2))，?x?y(I(x)?I(y)??N(x?y)??N(y?x))；

2. T或真或1； 3. y,x； x,z；

n162n4.2；2； 5.2或65536；15； 6.{?1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?2,3?}。

四、计算题（每小题10分，共30分）

1. P?Q?P?((?P?Q)?P)?(P?(?P?Q))

?(?(?P?Q)?P)?(?P?(?P?Q))

?((P??Q)?P)?(?P?Q)

4分 8分

?P?(?P?Q)?(P??P)?(P?Q)?(P?Q)??(3)（主析取范式）

??(0,1,2)?(P?Q)?(P??Q)?(?P?Q)（主合取范式） 10分

2. R?{(1,1),(1,3),(2,2),(2,5),(3,1),(3,3),(4,4),(5,2),(5,5)}.

(1) R的关系图

1 3 2 5 4

4分 3分 3分

(2) 因为 R满足自反、对称和传递性，所以R是等价关系；

(3) 等价类：{1, 3}, {2, 5}, {4}。

3. (1) ?A,R?的哈斯图为

《离散数学（上）》参考答案 第 1 页 共 2 页

4分

(2) A的极大元为：12，14，16，18，20，极小元为2； 2分 (3) B的极大元为：8，12，极小元为6，8；B的最大元和最小元都不存在； 2分

B的上界不存在，下界为2；B的上确界不存在，下确界为2。 2分

五、证明题（每小题10分，共20分）

1. 设f:R?N?R，f(x)?x，则f是从R?N到N的单射函数，所以|R?N|?|R|。 3分

构造从R到R?N的函数g:R?R?N如下：

x?I??2x?g(x)???2x?1x?N 7分

?x其它x?其中I?为负整数集合，则g是从N到R?N的单射函数（双射函数），所以|R|?|R?N|。 综合以上，|R?N|?|R|。 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 .

《离散数学（上）》参考答案 第 2 页 共 2 页

本文来源：https://www.bwwdw.com/article/yllh.html