2026年山大离散数学期末试题及答案

2026年山大离散数学期末试题及答案一、单项选择题（每题2分，共20分）1.设P：今天下雨，Q：我去图书馆。则命题“若今天不下雨，则我去图书馆”可符号化为（）A.PB.¬C.PD.¬答案：B解析：“今天不下雨”为¬P，整个命题为条件句，故符号化为¬2.谓词公式∀xA.∀B.∃C.∀D.∃答案：B解析：¬∀xA3.设集合A={1,2A.{B.{C.{D.∅答案：A解析：对称差A⊕4.集合A={1,2A.自反性B.对称性C.传递性D.反对称性答案：D解析：R缺少⟨2,2⟩、⟨3,3⟩，无自反性；有⟨1,2⟩但无⟨2,15.设函数f:R→R，A.单射B.满射C.双射D.既非单射也非满射答案：D解析：$f(-1)=f(1)=1$，故非单射；负数无原像，故非满射。6.在群⟨G,*A.不存在B.eC.G中任意元素D.只有e以外的元素答案：B解析：由e*e=7.在布尔代数中，若a∧A.aB.aC.aD.a答案：A解析：a∧b=a即8.无向图G有6个顶点，每个顶点的度数均为3，则G的边数为（）A.6B.9C.12D.18答案：B解析：由握手定理，2m=v9.一棵树有8个顶点，则其边数为（）A.7B.8C.9D.6答案：A解析：树的边数=n10.下列命题公式中，为重言式的是（）A.pB.pC.pD.p答案：B解析：p∨二、填空题（每题2分，共10分）1.命题公式(p答案：重言式2.设集合A={a,b答案：8解析：|A|=3.设R是集合A上的等价关系，则R必满足自反性、对称性和______。答案：传递性4.无向完全图K5答案：10解析：K5的边数为55.设n个顶点的无向连通图G为一棵树，则G恰有______条边。答案：n三、计算题（每题10分，共40分）1.求命题公式(p答案：先将公式展开为极小项之和：$$(p\wedgeq)\vee(\negp\wedger)

\equiv(p\wedgeq\wedger)\vee(p\wedgeq\wedge\negr)\vee(\negp\wedgeq\wedger)\vee(\negp\wedge\negq\wedger)$$所以主析取范式为：(对应极小项为m1,m使公式为假的小项为m0,m(该公式既不是重言式，也不是矛盾式，是可满足式。解析：先对含缺失变量的项进行扩展，使每个合取项都包含p,2.设集合A={1,2,3答案：关系R满足自反性、对称性和传递性，故R是A上的等价关系。等价类为：[商集为：A解析：由R中成对出现的⟨1,2⟩与⟨23.给定带权无向图G，顶点为v1,v2,v3,v4,v5，边权如下：(答案：按边权从小到大排序：(依次选边：-选择(v-选择(v-选择(v-选择(v-选择(v最小生成树的边集为：{总权值为：1解析：Kruskal算法的核心是每次选择权值最小且不与已选边构成回路的边，直到选满n−4.设集合G={1,2答案：⟨G•封闭性：任意a,b∈G，•结合律：由模5乘法结合律保证；•单位元为1；•每个元素均有逆元：1−1=1，2−解析：群要求封闭性、结合律、存在单位元、每个元素有逆元。本题中2×3≡四、证明题（每题10分，共30分）1.设函数f:A→B，g:B→答案：证明：任取x1,xg因为g是单射，所以f(又因为f是单射，所以x1因此g∘解析：证明单射的基本方法是假设函数值相等，逐步推出自变量相等。本题由外函数g的单射性先推出中间值相等，再由内函数f的单射性推出自变量相等。2.证明：任何无向图G中，奇度顶点的个数为偶数。答案：证明：设图G的顶点集为V，边数为m。由握手定理：v将顶点分为奇度顶点集合V1和偶度顶点集合Vv因V2中每个顶点的度数均为偶数，所以v∈V2​V1中每个顶点度数为奇数，奇数之和为偶数当且仅当项数为偶数，因此|解析：本题证明的关键是握手定理以及“奇数个奇数之和为奇数，偶数个奇数之和为偶数”这一数论性质。3.在命题逻辑中，证明：(即证明该蕴含式是重言式。答案：证明：令H结论为C=要证H⇒C，只需证¬于是H由p与¬