离散数学期末试卷拆解：120分钟13题判分动作与复习节奏-平芜编程栈

简介：中国地质大学（武汉）离散数学2022秋季学期课程试卷，面向准备期末复习、自测或教师命题参考的计算机与数学相关专业学习者，重点检验谓词逻辑、集合论、二元关系、群论与图论等核心知识的掌握程度。压缩包内共1个PDF文件，约287KB，为三页版结课考试试卷，含A/B卷标识、闭卷/开卷说明及13道解答题，所有题目均要求给出详细求解或证明过程。已有603人学习或下载，具备一定参考热度。试卷内容覆盖量词消去与谓词公式类型判断、形式化推理、主析取范式应用、集合等势关系、偏序集哈斯图、关系性质与商代数构造、子群证明、循环群同构、置换群、欧拉公式以及哈密尔顿图等典型考点，并设置考试安排建模题。适合按题型逐项训练，对照课堂重点梳理证明思路与解题步骤，也可用于模拟限时测试和查漏补缺。

1. 先确认这是一份什么样的卷子

一套 2022 秋季学期的离散数学结课试卷，13 道题，100 分，120 分钟，13 道全是解答题且明确要求写出求解或证明过程。很多人拿到它只是打印出来做一遍、对对答案就归档，我第一遍拆的时候也是这个心态，结果在第 5 题上卡了半小时——自反、对称都写对了，传递性却漏掉一个三段组。这套卷子的价值不在题量，而在它把谓词逻辑、集合与关系、代数结构、图论四条线压进一张卷面，每道题都卡在一个具体判断动作上。适合正在准备期末、想拿完整卷面做知识体检的人，也适合需要一份带分值分布的样例来设计自测节奏的人。

2. 13 道题反推考点地图：120 分钟该切给谁

拿到卷子先别急着动笔。先把 13 道题按主线归类、把分值和自己最容易卡壳的判分动作标出来，再倒推时间预算，这一步做扎实，后面做题才不会在第 3 题上耗掉 20 分钟、最后两道图论大题空着交卷。

2.1 六条主线与 13 个判分动作

原卷的知识点分布相当规整：谓词逻辑两题 16 分，命题逻辑一题 10 分，集合与关系三题 20 分，代数结构四题 28 分，图论三题 26 分。代数结构占比最高，而且第 10 题把群和置换群叠在一起考，是最容易失分的地方。

题号	主线	分值	判分关键动作	建议用时
1	谓词逻辑	6	存在量词按论域展开、四个公式定类型	6 min
2	谓词逻辑	10	形式化 + EI/UI 顺序不出错	10 min
3	命题逻辑	10	主析取范式筛可行指派	12 min
4	集合	6	三条性质各给一个双射	5 min
5	关系	8	性质判定 + 关系图 + 连通分支	8 min
6	偏序	6	只画覆盖关系的哈斯图 + 极值元	7 min
7	代数	8	5 个等价关系逐个验相容性	10 min
8	群	6	子群三条件	8 min
9	群	6	同构保阶	6 min
10	群	8	轮换分解 + 封闭性 + 同构映射	10 min
11	图论	6	e ≥ n−ω、广义欧拉公式	6 min
12	图论	10	最长通路法的反证骨架	12 min
13	图论	10	冲突图建模 + 色数上下界	12 min

加起来 112 分钟，留 8 分钟回填和检查。这套分配的逻辑是：证明题按「骨架 + 关键一步」给时间，计算题按「验证一遍」给时间。第 8、9 题虽然各只有 6 分，但子群三条件和同构保阶都是标准套路，8 分钟和 6 分钟足够写完；第 13 题看似是应用题，实际是图着色，建模那三分钟最值钱，建模错了后面全废。

2.2 谓词逻辑：论域 D={a,b} 的存在量词怎么展开

第 1 题给四个谓词公式，第一问要求在论域 D={a,b} 下消去 (C) 中的存在量词，第二问判断四个公式的类型。展开规则很死：存在量词按论域元素逐个析取，全称量词逐个合取，蕴含先化掉。手写时最容易出的错是把两层量词的括号层级搞乱，导致后面判类型时看不出哪一项恒真。

正确的展开是先把外层 ∃x 拆成两项的析取，每一项内部再把 ∃y 拆开：

((P(a)→P(a)) ∨ (P(a)→P(b))) ∨ ((P(b)→P(a)) ∨ (P(b)→P(b)))

注意 (P(a)→P(a)) 这一项不能省，它恒真，正是它让 (C) 成为重言式。判断四个公式的类型时，含自由变元的 (A) P(x)→P(y) 和 (B) P(x)∧¬P(y) 严格说不是命题，只能说「存在赋值使其为真、存在赋值使其为假」，结论落在可满足式上；(C) 是重言式；(D) ∀x∀y(P(x)∧¬P(y)) 取 x=y 就得到 P(x)∧¬P(x)，是矛盾式。

想验证结论，两分钟写个枚举脚本比反复推演可靠：

from itertools import product D = ('a', 'b') # 论域元素，个数决定真值表行数 # (C) ∃x∃y(P(x)→P(y))：存在量词展开成 any，蕴含展开成 ¬P(x)∨P(y) def C(env): return any((not env[x]) or env[y] for x in D for y in D) # (D) ∀x∀y(P(x)∧¬P(y))：全称量词展开成 all def Df(env): return all(env[x] and not env[y] for x in D for y in D) def kind(f, name): vals = [f(dict(zip(D, v))) for v in product([True, False], repeat=len(D))] res = '重言式' if all(vals) else ('矛盾式' if not any(vals) else '可满足式') print(name, res, vals) kind(C, '(C)') kind(Df, '(D)')

product([True, False], repeat=2)枚举 P(a)、P(b) 的全部四种赋值，any对应存在量词、all对应全称量词，这是在有限论域上最直接的翻译。把D改成三个元素，真值表自动变成八行，不需要改逻辑；如果论域换成无限集，这个脚本就失效了，得回到语义论证。跑出来 (C) 四种赋值全真、(D) 四种赋值全假，和手推一致，这一步花的时间比检查三遍草稿少。

2.3 演绎法推理：EI 和 UI 的先后顺序决定能不能推出来

第 2 题要求把「所有某类奖项获得者都是计算机科学家，一些该奖项获得者本科主修数学，所以一些计算机科学家本科主修数学」形式化并演绎证明。设 F(x) 为获奖者、S(x) 为计算机科学家、M(x) 为本科主修数学，论域为全总域，形式化结果是：

前提1: ∀x(F(x) → S(x)) 前提2: ∃x(F(x) ∧ M(x)) 结论: ∃x(S(x) ∧ M(x))

演绎的关键在步骤顺序。存在前提必须先做存在示例，拿到一个新常元 c，再用全称示例把前提 1 落到同一个 c 上，才能做假言推理。顺序反了——先对前提 1 做全称示例拿到 F(y)→S(y)，再对前提 2 引入常元 c——就会出现 F(c)∧M(c) 和 F(y)→S(y) 对不上的局面，推不下去。

步骤	动作	结果	约束
1	前提 1	∀x(F(x)→S(x))	原样引用
2	前提 2	∃x(F(x)∧M(x))	原样引用
3	对 2 做存在示例	F(c)∧M(c)	c 必须是本证明中首次出现的新常元
4	对 1 做全称示例	F(c)→S(c)	全称示例可代任意个体，代 c 合法
5	对 3 化简	F(c)、M(c)	合取消解
6	对 4、5 假言推理	S(c)	—
7	对 6、5 合取引入	S(c)∧M(c)	—
8	存在推广	∃x(S(x)∧M(x))	结论中出现的是约束变元，与原常元无关

第 3 步的「新常元」是硬约束：同一个常元不能既在存在示例里引入、又在别处当已知个体用，否则会推出「所有获奖者都是同一个人的同班同学」这类荒谬结论。这是形式化推理里最经典的一处硬性要求，写证明时在步骤后面标一句「c 为新引入常元」，阅卷时能直接看出你清楚这条约束。

3. 关系、偏序与商代数：把第 5、6、7 题写成可跑的检查脚本

第 5、6、7 三道题共 22 分，全部围绕二元关系展开，而且都有一个共同特征：手算容易漏项，脚本一跑就现形。我一般会先手算一遍，再用脚本对一遍答案，两次结果不一致就以脚本为准回头找漏在哪。

3.1 关系性质：自反闭包不补，后面全错

第 5 题给了 9 个模块和六组「必须同一开发小组」的约束：1 与 4、6 与 5、2 与 3、7 与 8、5 与 4、2 与 9。题目定义 aRb 表示模块 a 与 b 需由同一小组实现。这里有个容易被忽略的点：模块和自己当然同组，所以 R 必须包含全部 (i,i)，即自反闭包要补上。

from collections import defaultdict N = 9 pairs = [(1, 4), (6, 5), (2, 3), (7, 8), (5, 4), (2, 9)] # 原卷六组约束 R = set(pairs) | {(b, a) for a, b in pairs} # 对称闭包 R |= {(i, i) for i in range(1, N + 1)} # 自反闭包 reflexive = all((i, i) in R for i in range(1, N + 1)) symmetric = all((b, a) in R for a, b in R) transitive = all((a, c) in R for (a, b) in R for (x, c) in R if b == x) print(reflexive, symmetric, transitive)

自反、对称、传递三个判定都是对 R 全量扫描，transitive那一行的含义是：任取两个有序对，只要前者的第二分量等于后者的第一分量，就要求首尾组成的对也在 R 里。跑出来是True True False——1R4、4R5 但 1R5 不在 R 中，传递性不成立。所以 R 是自反的、对称的、非传递的，不是等价关系。这一步如果用眼睛扫，很容易只验证题目给出的六组、忘掉 1 和 5 这条隐藏路径。

3.2 传递闭包与开发小组划分

第 5 题第三问要求分析最多需要多少个开发小组，本质是求 R 的传递闭包后数等价类，或者直接用并查集数连通分支。

parent = list(range(N + 1)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # 路径压缩 x = parent[x] return x def union(a, b): ra, rb = find(a), find(b) if ra != rb: parent[ra] = rb for a, b in pairs: # 只用原始约束连边即可 union(a, b) groups = defaultdict(list) for i in range(1, N + 1): groups[find(i)].append(i) print(dict(groups))

并查集只关心连通性，不需要显式构造传递闭包，时间复杂度接近线性。跑出来的三个分支是 {1,4,5,6}、{2,3,9}、{7,8}，对应三组开发任务：第一组做模块 1、4、5、6，第二组做 2、3、9，第三组做 7、8。想写成「传递闭包 + 等价类」的完整过程也可以，用三重循环的 Warshall 求出 t(R) 再按行分组，答案完全一样，只是代码长一些。答辩式的写法建议在卷面上画出关系图，再用连通分支说明，比纯文字清楚。

3.3 哈斯图只画覆盖关系

第 6 题给 A={1,…,10} 和整除关系，要求画哈斯图并写出最小元、极大元、上界。画图时的核心是覆盖关系：a 被 b 覆盖，当且仅当 a|b 且不存在中间元素 c 使 a|c|b。把所有整除对都连上，画出来的是一张稠密的有向图，不是哈斯图。

A = list(range(1, 11)) cover = [(a, b) for a in A for b in A if b % a == 0 and a != b and not any(a != c != b and c % a == 0 and b % c == 0 for c in A)] minimal = [a for a in A if all(c % a == 0 for c in A)] # 最小元：整除所有元素 maximal = [b for b in A if not any(b % a == 0 and a != b for a in A)] upper = [u for u in A if all(x == u or u % x == 0 for x in A)] print(cover, minimal, maximal, upper)

cover里的not any(...)就是在排除中间元素，跑出来是 1-2、1-3、1-5、1-7、2-4、2-6、2-10、3-6、3-9、4-8、5-10，共 11 条边，哈斯图从上往下排就按这个关系。最小元是 1（1 整除 A 中所有元素）；极大元是 6、7、8、9、10（没有别的元素是它们的倍数，注意 5 不在其中，因为 5|10）；上界要求一个元素被 A 中所有元素整除，也就是最小公倍数 2520，不在 A 内，所以上界为空集。把「极大元」写成「最大元」是这一问最常见的失分点，两者的区别在于最大元要求与所有元素可比。