下载文档原格式
绝密★启用前
2020年8月高等教育自学考试全国统一命题考试
离散数学试题答案及评分参考
（课程代码 02324）
一、单项选择题：本大题共15小题，每小题1分，共15分。
1. D
2. B
3. D
4. A
5. B
6. C
7. B
8. D
9. A 10. C
11.B 12.A 13.D 14.C 15.D
二、填空题：本大题共10小题，每小题2分，共20分。
16. 3
17.{1,5,9}
18.T
19.11
20.{〈1,2〉}
21.∀x∀y∃z�F(x)∨¬G(y)∨H(z)�
22.11
23.∅
24.8
25.{〈3,1〉,〈9,2〉,〈6,3〉}
三、简答题：本大题共7小题，第26~30小题，每小题6分；第31~32小题，每小题
7分，共44分。
26.解：命题公式(P∧Q)∨(¬Q→R)的真值表如下
P Q R P∧Q¬Q→R(P∧Q)∨(¬Q→R)(1分)
F F F F F F
F F T F T T (1分)
F T F F T T
F T T F T T (1分)
T F F F F F
T F T F T T (1分)
T T F T T T
T T T T T T (1分) 由上表可知，命题公式为非重言式的可满足式。 (1分)
离散数学试题答案及评分参考第1页（共4页）
离散数学试题答案及评分参考第2页（共4页） 27. 解：(P ∨¬Q )∧(¬R →Q )
⇔(P ∨¬Q )∧(R ∨Q ) (2分) ⇔(P ∨¬Q ∨R )∧(P ∨¬Q ∨¬R )∧(P ∨Q ∨R )∧(¬P ∨Q ∨R )
(1分) 主合取范式为 (P ∨Q ∨R )∧(P ∨¬Q ∨R )∧(P ∨¬Q ∨¬R )∧(¬P ∨Q ∨R )， (1分)
成假赋值为000，010，011和100。 (2分) 28. 解：集合A ={a ,b ,c ,d }的二元关系
R ={〈a ,b 〉,〈b ,d 〉,〈c ,a 〉,〈c ,c 〉,〈d ,c 〉}，
(2分) R 的关系矩阵M R =�0100000110001010�，
(2分) 对称闭包的关系矩阵M s (R )=M R ∨M R −1=�011010
0110011110�。
(2分) 29. 解：利用Kruskal 算法，避圈法过程如下， 添加权值为2的边(v 1
,v 2); 添加权值为2的边(v 1,v 4); (1分) 添加权值为3的边(v 3,v 4); 添加权值为3的边(v 5,v 6)； (1分) 添加权值为4的边(v 5,v 7)；添加权值为9的边(v 4,v 5); (1分) 得到的最小生成树如答29图所示。
(2分)
该最小生成树的权为23。
(1分) 30. 解：
(1) 图G 的邻接矩阵为M =�0010
101101
00011�。
(2分) (2) 由于 M 2=�01010
2110
011
111�，
(1分) M 3=�1012112201112
122�，
(1分) 答29
图
v 1v 2v 4
6
3
9 3 4
v 7
2
离散数学试题答案及评分参考第3页（共4页） 可知，图G 中长度为3的通路数为20条。 (1分)
(3) 由M ，M 2及M 3可知，图G 中长度小于或等于3的回路数为11。 (1分) 31. 解：算术表达式(a −b )∗c �(d +e )∗f�⁄的二叉树如答31图所示， (1分)
先序遍历序列为/(∗(−ab )c )(∗(+de )f )，即/∗−abc ∗+def ; (2分) 中序遍历序列为�(a −b )∗c�/�(d +e )∗f�，即a −b ∗c /d +e ∗f ; (2分) 后序遍历序列为�(ab −)c ∗��(de +)f ∗�/，即ab −c ∗de +f ∗/。 (2分)
32. 解：集合A ={1,2,3,6,9,18}，
(1) 〈A ,≼〉的哈斯图如答32图所示。
(2分)
(2) 子集B ={3,6,9}的极大元为6和9，
(1分) 极小元为3，
(1分) 最大元不存在，
(1分) 最小元为3。
(1分) (3) 该偏序集A 是格，因为每对元素都有最小上界和最大下界。
(1分) 四、证明题：本大题共3小题，每小题7分，共21分。
33. 证明：
(1) 满足封闭性：∀a ,b ∈Z ，有a ∘b =a +b −1∈Z ；
(1分) (2) 满足结合律：∀a ,b ,c ∈Z ，有
(a ∘b )∘c =a +b +c −2=a ∘(b ∘c )； (1分) (3) 存在幺元1：∀a ∈Z ，有a ∘1=a +1−1=a =1+a −1=1∘a ;
(1分) (4) 每个元素存在逆元：∀a ∈Z ，a ∘(2−a )=(2−a )∘a =1，
答31图 b +
a
*
− / * c f
e
d 6 3
2
答32图
