离散数学考试 必备大全 看完不低于90分
离散数学 练习题
一、填空题
1. 仅用∨和┐写出下列表达式的等价形式
a) b)
⌝(P ∨Q ) ∧⌝R ⇔ ⌝A →(D ∨⌝E ) ⇔2. 仅用∧和┐写出下列表达式的等价形式
a) b)
⌝(P ∨Q ) ∧⌝R ⇔ ⌝Q →(P ∧Q ) ⇔；
3. 构造公式P ∧(P ∨Q ) Q 的真值表
。
4. 公式A 有三个命题变元P 、Q 、R 组成，其主合取范式为A ⇔M 0∧M 1∧M 7，则
其主析取范式为：
5. 公式A 有三个命题变元P 、Q 、R 组成，其主析取范式为A ⇔m 0∨m 2∨m 5∨m 6，则其主合取范式为： 6. 设A ={a , b , c , d }, A 上的二元关系：
R ={, , , , }，S ={, , , , }
则S -1 R =R S =r (R ) =s (R ) =t (S ) =
7. 给定如图所示的二元树：
按先根次序遍历访问结点的顺序为： 按中根次序遍历访问结点的顺序为： 按后根次序遍历访问结点的顺序为： 8.
B
F
A ={1, 2},B ={a , b },A ⨯B 2=
9. 设解释I 如下：
确定下列各式的真值：
∃xP (x , 2) ∀yP (1, y ) ∀x ∀yP (x , y ) 。∀x ∃yP (x , y ) 10. 集合A ={{Φ, 2},{2}}的幂集ρ(A ) = 11. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,4,5,6}, B={2,4,6,8,10},
则：(A∪B)-B = , B -A = , B⊕A= , B⊗A= 12. A ={{1, 2}},B ={a , b },A ⨯B 。
13. 给定集合S={a,b,c,d}，S 上的等价关系R 能产生划分{{a},{b},{c,d}}，则R ＝ 14. 指出下列映射是单射、满射、双射还是既非单射也非满射：
a) b) c) d) e)
f :Z +→R ,
f (x ) =ln x ； (Z+: 表示正整数集) 。
f :R →R +，f (x ) =x 2+1 （R +表示不小于0的实数） f :R →R +，f (x ) =x 2 （R +表示不小于0的实数） 。
f :A →B , g :B →C , g f 是双射，则 f 是f :R →R ，f (x ) =
21
x +
32
(a)：(b)：(c)：(d)：16. 某单位装配了30辆汽车，其中15辆有录音机，8辆有空调，6辆有座位调节，三种
设备都有的有2辆，问这三种设备都不具备的汽车至少有 辆？
17. 设无向图中有6条边，有一个3度结点和一个5度结点，其余结点的度数为2，则该
图的结点数为： 。
二、命题符号化：
18. 19. 20. 21. 22.
李明和王平是大学同学。
不是所有的哺乳动物都是胎生的。
任何一个公式总存在一个与之等价的主析取范式。 有些人对某些药品过敏。
参加考试的人不一定取得好成绩。
23. 发光的不都是金子。
24. 有的兔子比所有的乌龟跑的快。
25. 所有猫都是动物，但有些动物不是猫。
三、作图：
26. 27. 28. 29.
用二元有序树表示命题公式：（见课后习题P320 2） 将普通的树转换为等价的二叉树。
将二叉树T 转换为等价的普通树或树林。 用克鲁斯克尔算法求出左图的最小生成树。（见课后习题P309 11）
四、证明题：
30. A ∨B →C ∧D , D ∨E →G ⇒A →G 31. 证明下列论证：
如果甲参加球赛，则乙或丙也将参加球赛； 如果乙参加球赛，则甲不参加球赛； 如果丁参加球赛，则丙不参加球赛；
所以，如果甲参加球赛，则丁不参加球赛。
32. 设R 为二元关系，S ={|∃c , ∈R ∧∈R }，
证明，若R 是等价关系，则S 也是等价关系。 33. 试证明：在任何一棵树T(n,m)中均有m=n-1。
五、计算题：
34. 设集合A ＝{2,3,4,5,6,8,12,18,36}，R 是A 上的整除关系，
(1) 画出偏序集(A, R)的哈斯图；
(2) 写出集合A 的最大元，最小元，极大元，极小元。
(3) 写出A 的子集{2, 3, 6}的上界，下界，最小上界，最大下界； (4) 写出A 的子集{2, 4, 6}的上界，下界，最小上界，最大下界；
35. 用迪克斯特拉算法求从a 到z 最经济道路的长度以及该道路所经过的结点，并给出求
解过程。（见课后习题P277 18）