发布时间 : 星期四 文章《离散数学》试题及答案更新完毕开始阅读
得到树.
(A)6 (B)5 (C)10 (D)4. 15. 设图G的相邻矩阵为
，则G的顶点数与边数分别
为( D ).
(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8. 三、计算证明题
1.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。 (1) (2)
画出半序集()的哈斯图；
写出A的子集B = {3,6,9,12}的上界，下界，最小上
界，最大下界； (3)
写出A的最大元，最小元，极大元，极小元。
解：（1）
（2） B无上界，也无最小上界。下界1, 3; 最大下界是3 （3） A无最大元，最小元是1，极大元8, 12, 9; 极小元是1
2. 设集合A＝{1, 2, 3, 4}，A上的关系R＝{() | x, y
y}, 求
A 且 x
(1) (2)
画出R的关系图； 写出R的关系矩阵.
解：（1） （2）
3. 设R是实数集合，,,是R上的三个映射，(x) = 3, (x) = 2x, ?，解： (1)?＝(2)?＝(3)?＝(4)?＝(5)?
(
(x))＝
(x)+3＝23＝23. (x)+3＝(3)+3＝6, (x)+3＝4+3, (x)/4＝24 = 2,)＝
?
(x) ＝ 4,试求复合映射?
?.
?，?, ?,
((x))＝((x))＝((x))＝?(
?
?＝+3＝24+3＝2+3.
▲4. 设I是如下一个解释：D = {2, 3},
a b f (2) f (3) P(2, P(2, P(3, P(3,
2)
3) 0
2) 1
3) 1
3 2 3 2 0
试求 (1) P(a, f (a))∧P(b, f (b));
(2)
xy P (y, x).
解：
(1) P(a, f (a))∧P(b, f (b)) = P(3, f (3))∧P(2, f (2)) = P(3, 2)∧P(2, 3) = 1∧0 = 0. (2)
xy P (y, x) = x (P (2, x)∨P (3, x))
= (P (2, 2)∨P (3, 2))∧(P (2, 3)∨P (3, 3)) = (0∨1)∧(0∨1) = 1∧1 = 1.
5. 设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。 (1) (2) (3)
画出半序集()的哈斯图；
写出A的最大元，最小元，极大元，极小元； 写出A的子集B = {4, 6, 8, 12}的上界，下界，最小
上界，最大下界.
解：(1) (2)无最大元，最小元1，极大元8, 12; 极小元是1.
(3) B无上界，无最小上界。下界1, 2; 最大下界2.
6. 设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。 解： G = =
(P→Q)∨(Q∧(P→R)) (P∨Q)∨(Q∧(P∨R))
Q)∨(Q∧(P∨R)) Q)∨(Q∧P)∨(Q∧R) Q∧R)∨(P∧
Q∧
R)∨(P∧Q∧R)∨(P∧Q∧
R)
= (P∧ = (P∧ = (P∧
∨(P∧Q∧R)∨(P∧Q∧R) = (P∧
Q∧R)∨(P∧
Q∧
R)∨(P∧Q∧R)∨(P∧Q∧
R)
∨(P∧Q∧R)
= m3∨m4∨m5∨m6∨m7 =
7. (9分)设一阶逻辑公式：G = ((x)∨化成前束范式. 解： G = (
(x)∨
(y))→
(x)
(y))→
(x)，把G(3, 4, 5, 6, 7).