《离散数学》试题及答案
一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。
1. 命题公式(P?Q)?Q为 ( )
(A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式 2．设P表示“天下大雨”， Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。 (A)． P?Q； (B)．P?Q； (C)．?P??Q； (D)．?P?Q． 3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( )
(A) 1?A (B) {1,2, 3}?A (C) {{4,5}}?A (D) ??A
4. 设A＝{1,2},B={a,b,c},C={c,d}, 则A×(B?C)= ( )
(A) {<1,c>,<2,c>} (B) {
(C)欧拉图； (D) 平面图.
二、填空题：本大题共5小题，每小题4分，共20分。把答案填在对应题号后的横线上。
6. 设集合A={?,{a}}，则A的幂集P(A)= 7. 设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{?x,y?y?2x,x?A,y?B}, 那么R1＝
－
8. 在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系. 9. 写出一个不含“?”的逻辑联结词的完备集 . 10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为
?101??，那么R的关系图为 MR＝?100????100??
三、证明题（共30分）
11. （10分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) 12. （10分）构造证明：(P?(Q?S))∧(?R∨P)∧Q?R?S
（0,1）13.（10分）证明与[0,1)，[0,1)与[0,1]等势。 四、解答题(共35分)
14.（7分）构造三阶幻方（以1为首项的9个连续自然数正好布满一个3?3方阵，且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.）
15.（8分） 求命题公式(P?Q)?(?P??Q)的真值表.
16.（10分）设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{?,?}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={
毕节学院《离散数学 》课程试卷 第 1 页 共 4 页
求R1?R2的集合表达式.
17.（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？
三个条件：(1)若A去，则C和D中要去1个人；(2)B和C不能都去； (3)若C去，则D留下。
一、单项选择题(每小题3分，共15分) 1.B 2.C 3. C 4.A 5.B 二、填空题(每小题4分，共20分) 6. {?,{?},{{a}},{?,{a}}} 7.{<6,3>,<8,4> } 8. 老乡 9.{?,?}或{?,?} 或 {?}或 {?}
10. 见第10题答案图.
11.证明：∵x? A∩（B∪C）? x? A∧x?（B∪C） ··························································· 2分
? x? A∧（x?B∨x?C） ······························································································· 3分 ?（ x? A∧x?B）∨（x? A∧x?C） ··········································································· 5分 ? x?（A∩B）∨x? A∩C ······························································································ 7分 ? x?（A∩B）∪（A∩C） ····························································································· 9分 ∴A∩（B∪C）=（A∩B）∪（A∩C） ·················································································· 10分 12.证明：（1）R 附加前提
（2）?R∨P P ········································································································ 2分 （3）P T(1)(2)，I ······················································································ 3分 （4）P?(Q?S) P ······································································································· 4分 （5）Q?S T(3)(4)，I ······················································································ 5分 （6）Q P ······································································································· 6分 （7）S T(5)(6)，I ······················································································ 8分 （8）R?S CP ··································································································· 10分 13. 证明：a) 设A?{,,?, a? ?c b? 第10题答案图
11231,?}，作f:(0,1)?[0,1)如下： ································· 2分 n1?f()?0?2?1?1,x?A?n?2 ························································································ 5分 ?f()?nn?1??f(x)?x,x?(0,1)?A??b) 设A?{,,?,11231,?}，作f:[0,1)?[0,1]如下： ····················································· 7分 n毕节学院《离散数学 》课程试卷 第 2 页 共 4 页
f(0)?0??111?························································································ 10分 ,n?1,?A ·?f()?n?1n?n??f(x)?x,x?[0,1)?A14.
4
3 8
9 5 1
2 7 6
填对每个格得1分。 15.
P Q P?Q 0 0 0 0 1 1 0 1 1 0 0 1 ?P 1 1 0 0 ?Q 1 0 1 0 ?P??Q 1 1 1 0 (P?Q)?(?P??Q) 0 0 0 0 表中最后一列的数中，每对1个数得2分.
?110?16. MR1???, (2分)
001??MR2?01?? (4分)
??01????00???01??01???01? (6分) ???00?????00???110? MR1?R2????001?R1?R2?{?1,??} (10分)
17. 解 设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：A?C?D，?(B∧C)，C??D必须同时成立。 ······························································································ 2分 因此(A?C?D)∧?(B∧C)∧(C??D)
?(?A∨(C∧? D)∨(?C∧D))∧(?B∨?C)∧(?C∨?D)
?(?A∨(C∧? D)∨(?C∧D))∧((?B∧?C)∨(?B∧?D)∨?C∨(?C∧?D)) ?(?A∧?B∧?C)∨(?A∧?B∧?D)∨(?A∧?C)∨(?A∧?C∧?D)
∨(C∧? D∧?B∧?C)∨(C∧? D∧?B∧?D)∨(C∧? D∧?C)∨(C∧? D∧?C∧?D) ∨(?C∧D∧?B∧?C)∨(?C∧D∧?B∧?D)∨(?C∧D∧?C)∨(?C∧D∧?C∧?D) ?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D) ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)
?T ··································································································································· 8分
毕节学院《离散数学 》课程试卷 第 3 页 共 4 页
故有三种派法：B∧D，A∧C，A∧D。 ······································································· 10分 毕节学院《离散数学 》课程试卷 第 4 页 共 4 页