离散数学试题答案及评分参考第1页（共4页）绝密★启用前2020年8月高等教育自学考试全国统一命题考试离散数学试题答案及评分参考（课程代码02324）一、单项选择题：本大题共15小题，每小题1分，共15分。1.D2.B3.D4.A5.B6.C7.B8.D9.A10.C11.B12.A13.D14.C15.D二、填空题：本大题共10小题，每小题2分，共20分。16.317.{1,5,9}18.T19.1120.{〈1,2〉}21.∀𝑥∀𝑦∃𝑧𝐹�(𝑥)∨¬𝐺(𝑦)∨𝐻(𝑧)�22.1123.24.825.{〈3,1〉,〈9,2〉,〈6,3〉}三、简答题：本大题共7小题，第26~30小题，每小题6分；第31~32小题，每小题7分，共44分。26.解：命题公式(𝑃∧𝑄)∨(¬𝑄→𝑅)的真值表如下𝑃𝑄𝑅𝑃∧𝑄¬𝑄→𝑅(𝑃∧𝑄)∨(¬𝑄→𝑅)(1分)FFFFFFFFTFTT(1分)FTFFTTFTTFTT(1分)TFFFFFTFTFTT(1分)TTFTTTTTTTTT(1分)由上表可知，命题公式为非重言式的可满足式。(1分)10离散数学试题答案及评分参考第2页（共4页）101011010010𝑣4𝑣79433𝑣𝑣530127.解：(𝑃∨¬𝑄)∧(¬𝑅→𝑄)-(𝑃∨¬𝑄)∧(𝑅∨𝑄)(2分)-(𝑃∨¬𝑄∨𝑅)∧(𝑃∨¬𝑄∨¬𝑅)∧(𝑃∨𝑄∨𝑅)∧(¬𝑃∨𝑄∨𝑅)(1分)主合取范式为(𝑃∨𝑄∨𝑅)∧(𝑃∨¬𝑄∨𝑅)∧(𝑃∨¬𝑄∨¬𝑅)∧(¬𝑃∨𝑄∨𝑅)，(1分)成假赋值为000，010，011和100。(2分)28.解：集合𝐴={𝑎,𝑏,𝑐,𝑑}的二元关系𝑅={〈𝑎,𝑏〉,〈𝑏,𝑑〉,〈𝑐,𝑎〉,〈𝑐,𝑐〉,〈𝑑,𝑐〉}，(2分)01𝑅的关系矩阵𝑴𝑅=�00000001�，(2分)1001对称闭包的关系矩阵𝑴𝑠(𝑅)=𝑴𝑅∨𝑴𝑅−1=�10011001�。(2分)1029.解：利用Kruskal算法，避圈法过程如下，添加权值为2的边(𝑣1,𝑣2);添加权值为2的边(𝑣1,𝑣4);(1分)添加权值为3的边(𝑣3,𝑣4);添加权值为3的边(𝑣5,𝑣6)；(1分)添加权值为4的边(𝑣5,𝑣7)；添加权值为9的边(𝑣4,𝑣5);(1分)得到的最小生成树如答29图所示。(2分)𝑣122𝑣2该最小生成树的权为23。30.解：答29图𝑣6(1分)00(1)图𝐺的邻接矩阵为𝑴=�10001011�。(2分)11(2)由于01𝑴2=�010110𝑴3=�1211离散数学试题答案及评分参考第3页（共4页）11210021�，111122�，22/**−c+fabde离散数学试题答案及评分参考第4页（共4页）可知，图G中长度为3的通路数为20条。(1分)(3)由𝑴，𝑴2及𝑴3可知，图G中长度小于或等于3的回路数为11。(1分)31.解：算术表达式(𝑎−𝑏)∗𝑐⁄�(𝑑+𝑒)∗𝑓�的二叉树如答31图所示，(1分)先序遍历序列为/(∗(−𝑎𝑏)𝑐)(∗(+𝑑𝑒)𝑓)，即/∗−𝑎𝑏𝑐∗+𝑑𝑒𝑓;(2分)中序遍历序列为�(𝑎−𝑏)∗𝑐�/�(𝑑+𝑒)∗𝑓�，即a−𝑏∗𝑐/𝑑+𝑒∗𝑓;(2分)后序遍历序列为�(𝑎𝑏−)𝑐∗��(𝑑𝑒+)𝑓∗/�，即𝑎𝑏−𝑐∗𝑑𝑒+𝑓∗/。(2分)答31图32.解：集合𝐴={1,2,3,6,9,18}，(1)〈𝐴,≼〉的哈斯图如答32图所示。(2分)1862931答32图(2)子集𝐵={3,6,9}的极大元为6和9，(1分)极小元为3，(1分)最大元不存在，(1分)最小元为3。(1分)(3)该偏序集𝐴是格，因为每对元素都有最小上界和最大下界。(1分)四、证明题：本大题共3小题，每小题7分，共21分。33.证明：(1)满足封闭性：∀𝑎,𝑏∈𝐙，有𝑎∘𝑏=𝑎+𝑏−1∈𝐙；(1分)(2)满足结合律：∀𝑎,𝑏,𝑐∈𝐙，有(𝑎∘𝑏)∘𝑐=𝑎+𝑏+𝑐−2=𝑎∘(𝑏∘𝑐)；(1分)(3)存在幺元1：∀𝑎∈𝐙，有𝑎∘1=𝑎+1−1=𝑎=1+𝑎−1=1∘𝑎;(1分)(4)每个元素存在逆元：∀𝑎∈𝐙，𝑎∘(2−𝑎)=(2−𝑎)∘𝑎=1，离散数学试题答案及评分参考第5页（共4页）故𝑎的逆元为2−𝑎;(5)满足交换律：𝑎∘𝑏=𝑎+𝑏−1=𝑏∘𝑎；综上，〈𝐙,∘〉构成交换群。(2分)(1分)(1分)34.证明：(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<6且8度顶点个数𝑛8<5。(1分)已知无向简单图𝐺=〈𝑉,𝐸〉，|𝑉|=9，∆(𝐺)=8，𝛿(𝐺)=7。所以图𝐺中顶点的度数或者为7或者为8，故𝑛7+𝑛8=|𝑉|=9。(1分)再由假设，有𝑛7≤5且𝑛8≤4，故必得𝑛7=5，𝑛8=4，(2分)从而，度数总和等于𝑛7×7+𝑛8×8=5×7+4×8=67，(2分)显然，度数总和67为奇数与握手定理矛盾，故结论得证。(1分)
