《离散数学》试题及答案一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。
1. 命题公式Q Q P →∨)(为 ( )(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) 1A (B) {1,2, 3}A (C) {{4,5}}A (D) A4. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >} (C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>}5. 设G 如右图：那么G 不是( ).(A)哈密顿图； (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 ＝},,2,{B y A x x y y x ∈∈=><, 那么R －1＝8. 在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9. 写出一个不含“→”的逻辑联结词的完备集 .10.设X ＝{a ,b ,c }，R 是X 上的二元关系，其关系矩阵为M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001001101，那么R 的关系图为三、证明题（共30分）11. （10分）已知A 、B 、C 是三个集合，证明A ∩(B ∪C)=(A ∩B)∪(A ∩C)12. （10分）构造证明：(P (Q S))∧(R ∨P)∧Q R S13.（10分）证明（0,1）与[0,1)，[0,1)与[0,1]等势。
四、解答题(共35分)14.（7分）构造三阶幻方（以1为首项的9个连续自然数正好布满一个33⨯方阵，且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.）15.（8分） 求命题公式)()(Q P Q P ⌝∨⌝∧∧的真值表.16.（10分）设R 1是A 1＝{1,2}到A 2＝(a ,b ,c )的二元关系，R 2是A 2到A 3＝{βα,}的二元关系，R 1= {<1,a >,<1,b >,<2,c >}, R 2={<a ,>,<b ,>}求R 1R 2的集合表达式.17.（10分）某项工作需要派A 、B 、C 和D 4个人中的2个人去完成，按下面3个条件，有几种派法如何派三个条件：(1)若A 去，则C 和D 中要去1个人；(2)B 和C 不能都去；(3)若C 去，则D 留下。
一、单项选择题(每小题3分，共15分)3. C二、填空题(每小题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 ∧xC ） ·················· 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 附加前提a c b（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) 设111{,,,,}23A n=L L ，作:(0,1)[0,1)f →如下： ········ 2分 1()0211(),21(),(0,1)f f x A n nn f x x x A ⎧=⎪⎪⎪=∈∧>⎨-⎪=∈-⎪⎪⎩······················ 5分 b) 设111{,,,,}23A n=L L ，作:[0,1)[0,1]f →如下： ············· 7分 (0)0111(),1,1(),[0,1)f f n A nn n f x x x A=⎧⎪⎪=>∈⎨-⎪=∈-⎪⎩ ······················ 10分 14.49 235 7 81 6 填对每个格得1分。
15. P Q P Q P QP Q (P Q )(P Q )0 0 0 1 1 1 00 1 0 1 0 11 00 0 1 1 0 1 1 1 0 0 0 0 表中最后一列的数中，每对1个数得2分.16. ,1000111⎥⎦⎤⎢⎣⎡=R M (2分) ⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=0010102R M (4分) ⎥⎦⎤⎢⎣⎡=•10001121R R M ⎥⎦⎤⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0010001010 (6分) },1{21><=•βR R (10分) 17. 解 设A ：A 去工作；B ：B 去工作；C ：C 去工作；D ：D 去工作。