2020年8月自考《02324离散数学》试题答案

PAGE1（4）绝密★启用前20208离散数学试题答案及评分参考（课程代码02324）151151.D2.B3.D4.A5.B6.C7.B8.D9.A10.C11.B12.A13.D14.C15.D1022016.317.{1,5,9}18.T19.1120.{〈1,2〉}21.∀𝑥∀𝑦∃𝑧�𝐹(𝑥)∨¬𝐺(𝑦)∨𝐻(𝑧)�1123.24.825.{〈3,1〉,〈9,2〉,〈6,3〉}726~30631~3274426.解：命题公式(𝑃𝑄¬𝑄→𝑅)的真值表如下𝑃𝑄𝑅𝑃∧𝑄¬𝑄→𝑅(𝑃∧𝑄)∨(¬𝑄→𝑅)(1FFFFFFFFTFTT(1FTFFTTFTTFTT(1TFFFFFTFTFTT(1TTFTTTTTTTTT(1由上表可知，命题公式为非重言式的可满足式。 (1分)27.解：(𝑃¬𝑄¬𝑅→𝑄)(𝑃∨¬𝑄)∧(𝑅∨𝑄) (2(𝑃∨¬𝑄∨𝑅)∧(𝑃∨¬𝑄∨¬𝑅)∧(𝑃∨𝑄∨𝑅)∧(¬𝑃∨𝑄∨𝑅) 主合取范式为(𝑃∨𝑄∨𝑅)∧(𝑃∨¬𝑄∨𝑅)∧(𝑃∨¬𝑄∨¬𝑅)∧(¬𝑃∨𝑄∨𝑅)， 和100。 28.解：集合𝐴={𝑎𝑏𝑐𝑑}的二元关系𝑅={〈𝑎𝑏〉〈𝑏𝑑〉〈𝑐𝑎〉〈𝑐𝑐〉〈𝑑𝑐〉}， (20 1 𝑅的关系矩阵𝑴𝑅=�0 1 0

0 01 0 1�， (21 1 01 0 1 对称闭包的关系矩阵𝑴𝑠(𝑅)=𝑴𝑅∨𝑴𝑅−1=�1 0

1 01 0 1�。 (21 1 0ual添加为2的(1,2;权为2的(1,4); 1分)添加为3的(3,4;权为3的(5,6； 1分)添加为4的(5,7；权为9的(4,5); 1分)得到的最小生成树如答29图所示。 (2分)𝑣4𝑣79 4𝑣4𝑣79 433𝑣𝑣532𝑣223。解：

29

𝑣6

(10 0 (1)图𝐺的邻接矩阵为𝑴=�1 0 0

1 00 1 1�。 (20 1 1

0 1 𝑴2=�0 1 0 1 0 𝑴3=�1 0 1

0 01 2 1�， (11 1 11 12 2 2�， (12 2 2可知，图G中长度为3的通路数为20条。 (1分)及𝑴3可知，图G中长度小于或等于3的回路数为11。 (1分)∗𝑓�的二叉树如答31图所示，(1分)先序历列(∗(−𝑏)𝑐)(∗(𝑑𝑒)𝑓)，∗−𝑐∗+𝑑𝑓; 2分)中序历列�𝑎−𝑏)∗𝑐�(𝑑+𝑒)∗𝑓�a−𝑏∗𝑐𝑑+𝑒∗𝑓;2)后序遍历序列为�(𝑎𝑏−)𝑐∗��(𝑑𝑒+)𝑓∗�/，即𝑎𝑏−𝑐∗𝑑𝑒+𝑓∗/。(2分)//**−c+fabde3132.解：集合𝐴={1,2,3,6,9,18}，(1)〈𝐴,≼〉的哈斯图如答32图所示。 (2分)186293132(2)子集𝐵={3,6,9}的极大元为6和9， 极小元为3， 最大元不存在， (1分)最小元为3。 (1分)(3)该偏序集𝐴是格，因为每对元素都有最小上界和最大下界。 (1分)372133.证明：(1)满足封闭性：∀𝑎,𝑏∈𝐙，有𝑎∘𝑏=𝑎+𝑏−1∈𝐙； (1分)(2)满足结合律：∀𝑎𝑏𝑐∈𝐙，有(𝑎∘𝑏𝑐=𝑎+𝑏+𝑐−2=𝑎∘(𝑏∘𝑐)； (13)1𝑎∈𝑎∘1=𝑎+1−1=𝑎=1+𝑎−1=1∘𝑎;1分)(4)每个元素存在逆元：∀𝑎∈𝐙，𝑎2𝑎)=(2𝑎𝑎=1，故𝑎2−𝑎;(5)满足交换律：𝑎𝑏=𝑎𝑏1=𝑏𝑎；综上，〈𝐙,∘〉构成交换群。(2(1(134.证明：(1)𝑅 CP（附加前提）(1(2)𝑅→𝑄 P(1(3)𝑄 T(1)(2)(1(4)𝑄→𝑃 P(1(5)𝑃 T(3)(4)(1(6)¬𝑃𝑆 P(1(7)𝑆 T(5)(6)(1由此得到推理是正确的。35.证明：反证法。假设𝐺7𝑛7<68𝑛8<5。(1已知无向简单图𝐺=〈𝑉𝐸〉，|𝑉|=9，∆(𝐺)=8，𝛿(𝐺)=7。所以图𝐺中顶点的8，故𝑛7+𝑛8=|𝑉|=9。 (1分)再由假设，有𝑛7≤5且𝑛8≤4，故必得