(离散数学)自测题
- 格式：doc
- 大小：160.50 KB
- 文档页数：3
离散数学自测题2011.5
一、单项选择题（每题2分） 16 %
1. 设P ： 21≥，Q ： 32>，则命题“只有 21<，才有 32>”符号化为 ( )
(A ) (B) () (D ) P Q
P Q
C P Q
Q P →⌝⌝→↔⌝→⌝
2 设F (x )：x 是运动员，G (y )：y 是世界，H (x ,y )：x 游玩过y ，那么命题“某些运动员游玩过整个世界”符号化为 ( ) (A) (()(()(,)))x F x y G y H x y ∀→∃∧ (B) (()(()(,)))x F x y G y H x y ∃∧∀→
(C) (()(()(,)))x F x y G y H x y ∃→∀∧ (D) ((()())(,))x y F x G y H x y ∃∀→∧
3. 命题公式()p q q ⌝→∧是 ( )
(A) 矛盾式 (B) 重言式 (C) 可满足式 (D) 蕴涵式 4. 若A-B=Ф，则下列结论不可能正确的是 ( )
(A) A =∅ (B) B =∅ (C) A B ⊂ (D) B A ⊂ 5. 设A ={a,b,c}，A 上的关系R ={<a,a>,<c,a>,<b,b>,<b,c>}，则R 是 ( ) （A ）自反的 （B ）传递的 （C ）对称的 （D ）反对称的 6. 设函数 :f
R Z
→且
()f x x =⎢⎥⎣⎦
，则f 是 ( )
(A) 单射，非满射 (B) 满射，非单射 (C) 双射 (D) 非单射，非满射
7. 设G 是由5个顶点组成的完全图，则从图G 中删去（ ）条边可以得到树。
(A) 4 (B) 5 (C) 6 (D) 8
8. 无向图,G V E =<>是连通图且没有奇度顶点是欧拉图的（ ）条件。
（A ）充分必要条件 （B ）充分条件（C ）必要条件（D ）都不是
二、填空题（每空2分） 18 %
9. 设():F x x 是汽车，():G y y 是火车，H (x,y )：x 比y 快，则命题“说凡是火车就比汽车快是不对的”符号化是 ， 其另一种等值形式为 。
10. 设个体域D ={a,b,c },公式 (()())x y G x F y ⌝∃∀∨⌝的消去量词后等值式为。
11. 一棵树有3个2度顶点，2个3度顶点，1个4度顶点，其余都是树叶，则其树叶数为 。
12. 命题“整数列（2,2,3,3,5,5）可图化”的真值为 。
13. 设D ＝<V ,E >为4阶有向图，1234{,,,}V v v v v =，
邻接矩阵为A (D )=1
201011110100
2
1
0⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦
，
那么D 中顶点2v 的入度为 。
14. 在1到400的整数中（包含1和400）满足各条件整除个数：可以被3整除,但不能被5整除的是 ；可以被5整除,但不能被3整除的是 。
15. 设集合A ={a ,b ,c }，R 为A 上的关系，R ={<a ,b >,<b ,a >,<c ,a >}，则R 的传递闭包()t R 是 。
三、计算题 54 %
16. （6 分）设,,A B C 是Z 子集，其中{|206}
A x x k k Z k ==∧∈∧≤≤，2
{|80}B x x x Z =<∧∈，用列元素法表示集合B A -。
17.（6分）设集合{,}A b c =，试求幂集()P A A ⨯。
18. （10分）用等值演算法求公式()r p q →∧的主析取范式，并求成真赋值。
19. （8分）画出偏序集,A R ≤<>的哈斯图，并指出A 的极大元、极小元、最大元和最小元。
其中：{,,,,,}A a b c d e f =和
{,,,,,,,,,,,,,,,,,}A R a b a c a d a e a f b e c e c f d f I ≤=<><><><><><><><><>
20. （14分）右图所示无向图G 中，实线边所示子图为G 的一棵生成树T ，求G 对应T 的基本回路系统和基本割集系统。
21. （10分）已知有向图D 如右图所示，求（1）邻接矩阵A (D )；（2）D 中长度是2的回路数；（3）D 中从v 2到v 3长度是3的通路数；（4）D 是哪类连通图, 为什么?
1
v 4
v
四、证明题 12 %
22. （5分）证明对任意集合A,B,C ，有()()()A B C A C B C --=---。
23. （7分）在自然推理系统P 中构造推理证明：
前提：(), (), , ()p q r r s u u t s t ∨→→∨→⌝∨，结论：q ⌝
补充题：
1. （8分）右上图是偏序集,A R ≤<>的哈斯图，分别写出集合A 和偏序关系R ≤的集合表达式，并指出A 的极大元、极小元、最大元和最小元。
2. 右下图无向图是（ ）图。
(A) 欧拉图 (B) 哈密顿图
(C) 既是欧拉图，又是哈密顿图 (D) 都不是
3. 设B 不含有x ，(())x A x B ∀→等值于（ ）
(A) ()xA x B ∀→ (B) (())x A x B ∃∨ (C) ()xA x B ∃→ (D) (())x A x B ∃∧ 4. 设集合A ={a ,b ,c ,d }，R 1和R 2为A 上的关系，其中R 1={<b ,c >,<d ,b >}，R 2={<a ,d >,<b ,d >,<c ,b >}，则21R R 为 。
5.（12分）设7个字母在通信中出现的频率如下：
A: 30%, B: 20%, C: 13%, D: 12%, E: 10%, F: 9%, G: 6%
用Huffman 算法求传输它们的最佳前缀码。
要求画出最优树，指出每个字母对应的编码。
并指出传输100个按上述频率出现字母所需二进制数字个数。
6.（10分）将下列命题推理符号化并给出形式证明：
若张超与李志都是计算机系学生，则王红是中文系学生，若王红是中文系学生，则她爱看小说，可是王红不爱看小说，张超是计算机系学生，所以李志不是计算机系的学生。
7.（8分）证明对任意集合A,B,C ，有()()()A B A C B C A ⊕=⊕- 。
8.（15分）在1到800的整数中（包括1和800在内）分别求满足以下条件的整数个数。
要求写出解题过程，每小题必须做出文氏图，集合表达式和个数。
（1）可以被4或5整除，但不能被6整除； （2）只被4，5和6之中的一个数整除。
a
d
b
c
h
f。
