离散数学 · 题型模板与自测（自考 02324 口径）

配合本目录 考点速查.md 使用。先看模板 → 遮住答案做例题 → 最后做 20 题自测。本文件是 02324 离散数学的自编复习资料，不是官方题型、权重或评分说明；尚未核验适用省份的现行大纲、2026 年特殊通知及历年题型统计，不据此承诺考频或得分，考试范围与安排以适用的官方文件为准。

一、按练习类型整理方法

时间安排建议：按实际考试时长和试卷结构安排作答，预留检查时间。遇到证明题，应写与结论有关且有依据的推导；只写“由定义，设……”并不能保证得分，具体评分以实际评分要求为准。

二、分章模板 + 例题

模板 1：等值演算证明

步骤：从左（或右）出发，每步只用一个等值式，右边标注依据。

例：证明 (p→q)∧(p→r) ⇔ p→(q∧r)

(p→q)∧(p→r)
⇔ (¬p∨q)∧(¬p∨r)      蕴含等值式
⇔ ¬p∨(q∧r)            分配律
⇔ p→(q∧r)             蕴含等值式

（反向同理，故等值。）

模板 2：求主析取范式 / 主合取范式

真值表法（最稳）：

1. 列 2^n 行真值表；
2. 结果为 1 的行 → 写极小项，取析取 → 主析取范式；
3. 结果为 0 的行 → 写极大项，取合取 → 主合取范式。

例：求 (p→q)∧(q→r) 的主析取范式与主合取范式。

• 主析取范式：m₀∨m₁∨m₃∨m₇
• 主合取范式（其余行取 0 的极大项，变元取反写）：M₂∧M₄∧M₅∧M₆ = (p∨¬q∨r)∧(¬p∨q∨r)∧(¬p∨q∨¬r)∧(¬p∨¬q∨r)

检查技巧：主析取项数 + 主合取项数 = 2^n。

模板 3：推理证明（命题逻辑）

步骤：编号 → 每行写"公式 + 依据（前提/某规则 + 行号）"。

例：前提 p→q, r→s, p∨r, ¬q，证明 s。

(1) p→q        前提引入
(2) ¬q         前提引入
(3) ¬p         由(1)(2) 拒取式
(4) p∨r        前提引入
(5) r          由(3)(4) 析取三段论
(6) r→s        前提引入
(7) s          由(5)(6) 假言推理

变式：

• 结论是 p→q → 用附加前提法，把 p 当前提；
• 结论是否定或"不是…" → 反证法，把结论否定加入前提，推出 r∧¬r。

模板 4：谓词符号化 + 推理

符号化套路：

• "所有 A 都是 B" → ∀x(A(x)→B(x))
• "有的 A 是 B" → ∃x(A(x)∧B(x))
• "没有 A 是 B" → ∀x(A(x)→¬B(x)) 或 ¬∃x(A(x)∧B(x))
• "只有 A 才 B" → B→A

例：所有有理数都是实数，有的有理数是整数，所以有的实数是整数。

设 F(x)：x 是有理数；G(x)：x 是实数；H(x)：x 是整数。

前提：∀x(F(x)→G(x))，∃x(F(x)∧H(x))；结论：∃x(G(x)∧H(x))。

(1) ∃x(F(x)∧H(x))      前提引入
(2) F(c)∧H(c)          由(1) EI（c 为新常项）
(3) F(c)               由(2) 化简
(4) H(c)               由(2) 化简
(5) ∀x(F(x)→G(x))      前提引入
(6) F(c)→G(c)          由(5) UI
(7) G(c)               由(3)(6) 假言推理
(8) G(c)∧H(c)          由(4)(7) 合取
(9) ∃x(G(x)∧H(x))      由(8) EG

本例的两条前提并列，可先 EI 引入新常项 c，再用 UI 把全称前提实例化到 c；这不是顺序铁律。每次 EI 使用新的见证常项。例如 ∀x∃yP(x,y) 应先 UI 再 EI，见证 y 可依赖于 x，不能把它改成 ∃y∀xP(x,y)（自然数上取 P(x,y) 为 y>x，前者真、后者假）。

模板 5：容斥计数

例：1~1000 中不能被 2、3、5 任一整除的数有多少个？

A₂=500, A₃=333, A₅=200
A₂∩A₃=166, A₂∩A₅=100, A₃∩A₅=66
A₂∩A₃∩A₅=33
|A₂∪A₃∪A₅| = 500+333+200-166-100-66+33 = 734
所求 = 1000 - 734 = 266

模板 6：关系的闭包

例：A={1,2,3,4}，R={⟨1,2⟩,⟨2,3⟩,⟨3,4⟩}，求 t(R)。

R² = {⟨1,3⟩,⟨2,4⟩}
R³ = {⟨1,4⟩}
t(R) = R∪R²∪R³
     = {⟨1,2⟩,⟨2,3⟩,⟨3,4⟩,⟨1,3⟩,⟨2,4⟩,⟨1,4⟩}

图论视角：i 能沿箭头走到 j，就把 ⟨i,j⟩ 加进去。

Warshall（写代码/大题给矩阵时用）：对 k=1..n，若 r[i][k]=1 且 r[k][j]=1，则置 r[i][j]=1。

模板 7：等价关系 ↔ 划分

例：A={1,2,3,4}，划分 {{1,2},{3},{4}} 诱导的等价关系 R？

R = I_A ∪ {⟨1,2⟩,⟨2,1⟩}
  = {⟨1,1⟩,⟨2,2⟩,⟨3,3⟩,⟨4,4⟩,⟨1,2⟩,⟨2,1⟩}

证明"R 是等价关系 ⇒ 商集是划分"：

1. 自反 ⇒ 每个 x 属于 [x]，各类非空且并集为 A；
2. 若 [x]∩[y]≠∅，取 z 在交中，则 x R z 且 y R z，由对称、传递得 x R y，进而 [x]=[y]（互相包含）；
3. 故不同类不交，构成划分。

模板 8：偏序、哈斯图与极值

例：A={1,2,3,4,6,12}，R 为整除关系。

覆盖关系（哈斯图的边）：2 覆盖 1，3 覆盖 1，4 覆盖 2，6 覆盖 2，6 覆盖 3，12 覆盖 4，12 覆盖 6。

        12
       /  \
      4    6
      |  / |
      | /  |
      2    3
       \  /
        1

（ASCII 图仅作示意，连线以上述覆盖关系为准：边表为 {1–2, 1–3, 2–4, 2–6, 3–6, 4–12, 6–12}。）

• 最大元 12，最小元 1；极大元 12，极小元 1。
• {2,3} 的上界：6,12；上确界 6；下界：1；下确界 1。
• {4,6} 的上界：12；上确界 12；下界：1,2；下确界 2。

注意：求上界时检查"是否所有元素都 ≼ 它"，别只看大小。

模板 9：握手定理与度序列

例 1：证明不存在 5 个顶点度数都为 3 的简单图。

Σdeg = 5×3 = 15 为奇数，违背握手定理 Σdeg = 2|E|，故不存在。

例 2：8 阶简单图有 12 条边，是否可能有 3 个度为 5 的顶点？

Σdeg = 24。若 3 个度为 5，则它们共连出 15 度，
剩余 5 个顶点度之和为 9，且每个度 ≤ 5，可行；需再检查简单图构造，
一般用"最大度 ≤ n-1"和"度序列可图化"判断。

（若题目给定完整度序列，可用 Havel-Hakimi 判定可图化。）

Havel-Hakimi 示例：判断 (4,3,3,2,2) 是否可图化。

排序 4,3,3,2,2 → 去掉 4，后面 4 项各减 1 → (2,2,1,1)
排序 2,2,1,1 → 去掉 2，后两项减 1 → (1,0,1)
排序 1,1,0 → 去掉 1，后一项减 1 → (0,0)
全 0，可图化。

模板 10：欧拉图 / 哈密顿图判断

例：判断图 G（顶点 1~5，边 12,13,24,34,35,45）是否有欧拉回路。

度：deg1=2, deg2=2, deg3=3, deg4=3, deg5=2
奇度顶点 2 个（3、4）→ 无欧拉回路，但有欧拉通路（从 3 到 4）。

哈密顿判断话术：

• 要否定：找非空顶点子集 S 使 p(G-S) > |S|；
• 要肯定：给出哈密顿回路，或对 n≥3 的简单无向图验证 Dirac（δ ≥ n/2）或 Ore（不相邻点度和 ≥ n）；充分条件不满足不能直接否定。

模板 11：平面图

例：连通平面图 n=10，m=15，求面数 r。

r = 2 - n + m = 2 - 10 + 15 = 7

判断非平面：对 n≥3 的简单图，若 m > 3n-6 则必非平面。例如 K₅ 有 n=5、m=10 > 9。K₃,₃ 有 n=6、m=9 ≤ 3×6-6=12，不能用第一条界排除；但它是简单二部图，无三角形，若为平面图则应满足 m ≤ 2n-4=8，而 9>8，故非平面。

两条必要条件：n≥3 的简单平面图满足 m ≤ 3n-6；其中无三角形的图还满足 m ≤ 2n-4。满足边数界本身不能证明平面性。

模板 12：最小生成树

例：K₄，AB=1, AC=4, AD=3, BC=2, BD=5, CD=6。

Kruskal：

选 AB(1) → 选 BC(2) → AD(3)（三条边 4 点不构成圈）→ 停
总权 = 1+2+3 = 6

Prim 从 A 出发：AB(1) → BC(2) → AD(3)，结果相同。

模板 13：哈夫曼编码

例：权 {1,4,5,6,8}。

1+4=5   → {5,5,6,8}
5+5=10  → {6,8,10}
6+8=14  → {10,14}
10+14=24
WPL = 5+10+14+24 = 53

编码（左 0 右 1，答案不唯一）：

1 → 000    4 → 001    5 → 01    6 → 10    8 → 11

验证：1×3 + 4×3 + 5×2 + 6×2 + 8×2 = 3+12+10+12+16 = 53 ✓

快算：WPL = 所有"合并出的新结点权"之和，不用逐个乘深度。

模板 14：群与子群

例：G = ⟨Z₆, +⟩，求全部子群、各元素阶、生成元。

子群（阶必须整除 6）：{0}(1阶)、{0,3}(2阶)、{0,2,4}(3阶)、Z₆(6阶)
元素阶：0→1, 1→6, 2→3, 3→2, 4→3, 5→6
生成元：与 6 互质的 1,5（φ(6)=2 个）

子群判定证明模板（已知 G 是群，H⊆G）：

1. 根据 H 的具体定义，找出一个元素 h₀∈H，证明 H 非空；
2. 任取 a,b∈H，利用 H 的定义及 G 中的运算，证明 ab⁻¹ 仍满足 H 的定义；不能预先假设 H 已对逆元或乘法封闭；
3. 由非空子集的子群判定定理，得 H≤G。加法记法中应验证 a−b∈H。

示范：在 G=⟨Z₆,+⟩ 中，H={0,2,4} 是偶数剩余类组成的子集。

0∈H，故 H 非空。
任取 a,b∈H，可写 a=[2r]₆、b=[2s]₆（r,s∈Z）。
a−b=[2(r−s)]₆∈{[0]₆,[2]₆,[4]₆}=H。
故由子群判定定理，H≤G。

三、自编诊断练习，20题104分非仿真卷

本节保留自编题分：A 部分 16 分，B 部分 24 分，C、D 部分各 32 分，总分 104 分；不代表正式试卷的题型权重或评分细则。如需百分制记录，可按“原始得分 / 104 × 100”换算，仅用于复习诊断，不据此设置或推断考试及格线。

A. 选择 / 填空（每题 2 分）

1. 下列等值式不成立的是（ ） A. p→q ⇔ ¬p∨q　B. p→q ⇔ ¬q→¬p　C. p∧(p∨q) ⇔ p　D. p→q ⇔ q→p
2. 公式 (p∧q)→p 是（ ） A. 矛盾式　B. 可满足式但非重言式　C. 重言式　D. 无法判断
3. ¬∀x(P(x)∧Q(x)) 等值于（ ） A. ∀x(¬P(x)∧¬Q(x))　B. ∃x(¬P(x)∨¬Q(x)) C. ∃x(¬P(x)∧¬Q(x))　D. ∀x(¬P(x)∨¬Q(x))
4. |P(P(∅))| = ______。
5. A={1,2,3} 上关系 R={⟨1,2⟩,⟨2,1⟩,⟨1,1⟩,⟨2,2⟩,⟨3,3⟩} 是（ ） A. 只是自反的　B. 自反、对称但非传递　C. 等价关系　D. 偏序关系
6. 一棵树有 7 个顶点，则它的边数是 ______。
7. 下列必为非平面图的是（ ） A. K₄　B. K₃,₃　C. 六边形加一条对角线　D. 8 个顶点 10 条边的图
8. 群 G 的阶为 12，则 G 中元素 a 的阶不可能是（ ） A. 2　B. 3　C. 4　D. 5

B. 计算题（每题 6 分）

1. 求 (p∨q)→(p∧q) 的主析取范式与主合取范式。
2. A={1,2,3,4,6,12}，≼ 为整除关系，求 {2,3,4} 的上界集合与上确界。
3. K₄ 顶点 A,B,C,D，边权 AB=1, AC=4, AD=3, BC=2, BD=5, CD=6，求最小生成树及总权。
4. 对权 {1,4,5,6,8} 构造哈夫曼树，求 WPL。

C. 证明题（每题 8 分）

1. 用等值演算证明 (p→q)∧(p→r) ⇔ p→(q∧r)。
2. 设 R 是 A 上的等价关系，证明 R∘R = R。
3. 证明：n≥2 的树至少有两片树叶。
4. 证明：奇数阶群不存在指数为 2 的子群。

D. 综合（每题 8 分）

1. 将“每个大学生或者学英语或者学日语，有的大学生不学英语，所以有的大学生学日语”符号化并证明。
2. 设 A={1,2,3,4}，R 为模 2 同余关系，写出 R、等价类、商集，并说明对应的划分。
3. 无向图 G 有 6 个顶点、9 条边，判断是否可能为平面图？说明理由。
4. 群 G=⟨Z₈,+⟩，求全部子群、生成元个数，并指出 3 的阶。

四、自测答案

1. D。蕴含不可交换，反例 p=0,q=1。
2. C。p∧q 为真时 p 必真，故恒真。
3. B。否定内移，∀ 变 ∃，∧ 变 ∨。
4. 2。P(∅)={∅}，P({∅})={∅,{∅}}。
5. C。自反 ✓、对称 ✓、传递 ✓（⟨1,2⟩与⟨2,1⟩要求⟨1,1⟩、⟨2,2⟩，都有）。
6. 6。树 m=n-1。
7. B。K₃,₃ 是二部图，m=9 > 2n-4=8，非平面。
8. D。元素阶必整除群阶 12，5 不整除。
9. 真值表：00→1 (m₀)，01→0，10→0，11→1 (m₃)。
   • 主析取范式：m₀∨m₃ = (¬p∧¬q)∨(p∧q)（即 p↔q）
   • 主合取范式：M₁∧M₂ = (p∨¬q)∧(¬p∨q)
10. 上界需同时是 2、3、4 的倍数且属于 A：只有 12；上确界 12。
11. 选 AB(1)、BC(2)、AD(3)，总权 6。（BD、CD 会成圈或更大）
12. 合并过程 1+4=5，5+5=10，6+8=14，10+14=24 → WPL = 5+10+14+24 = 53。
13. 见"模板 1"。
14. 见"模板 7"后的论证思路：
    • R 传递 ⇒ R∘R ⊆ R；
    • R 自反 ⇒ 对任意 ⟨x,y⟩∈R，有 ⟨x,x⟩∈R 且 ⟨x,y⟩∈R，故 ⟨x,y⟩∈R∘R，即 R ⊆ R∘R；
    • 故 R∘R = R。
15. 取树中最长路径 v₁v₂…v_k。若 v₁ 还有除 v₂ 外的邻点 u，则 u 不在该路径上（否则出现回路或更长路径），可把路径延长，矛盾；故 deg(v₁)=1。同理 deg(v_k)=1，两片树叶。
16. 若 [G:H]=2，则 |G| = 2|H| 为偶数，与 |G| 为奇数矛盾（拉格朗日定理）。
17. 设 S(x)：x 是大学生；E(x)：x 学英语；J(x)：x 学日语。 前提：∀x(S(x)→(E(x)∨J(x)))，∃x(S(x)∧¬E(x))；结论：∃x(S(x)∧J(x))。 `` (1) ∃x(S(x)∧¬E(x)) 前提 (2) S(c)∧¬E(c) (1) EI (3) S(c) (2) 化简 (4) ¬E(c) (2) 化简 (5) ∀x(S(x)→(E(x)∨J(x))) 前提 (6) S(c)→(E(c)∨J(c)) (5) UI (7) E(c)∨J(c) (3)(6) 假言推理 (8) J(c) (4)(7) 析取三段论 (9) S(c)∧J(c) (3)(8) 合取 (10) ∃x(S(x)∧J(x)) (9) EG ``
18. R = {⟨x,y⟩ | x≡y (mod 2)} = {⟨1,1⟩,⟨3,3⟩,⟨1,3⟩,⟨3,1⟩,⟨2,2⟩,⟨4,4⟩,⟨2,4⟩,⟨4,2⟩}； 等价类 [1]=[3]={1,3}，[2]=[4]={2,4}； 商集 A/R = {{1,3},{2,4}}；对应划分 {{1,3},{2,4}}。
19. 简单平面图需 m ≤ 3n-6 = 3×6-6 = 12，9 ≤ 12，不能仅凭此否定，故可能是平面图（例如八面体图去掉若干边）。若要否定需找出 K₅ 或 K₃,₃ 的细分。
20. 子群（阶整除 8）：{0}、{0,4}、{0,2,4,6}、Z₈； 生成元为与 8 互质者：1,3,5,7，共 φ(8)=4 个； 3 的阶：在加法群 Z₈ 中，[3] 的阶是使 3k≡0 (mod 8) 的最小正整数 k。因 gcd(3,8)=1，8|3k 当且仅当 8|k，故最小 k=8，阶为 8。

五、考前时间路线

只剩 3 小时

只剩 1 天

• 上午：第 1–5 章（逻辑 + 集合 + 关系 + 函数），配合模板 1–8。
• 下午：第 6–7 章（图论 + 树），把 Prim/Kruskal/哈夫曼/平面图各做 2 题。
• 晚上：第 8 章（代数系统）+ 自编诊断练习 + 错题重做。
• 睡前：只看“易错点”和“数字记忆卡”。

考场技巧

1. 证明题先明确已知与待证，再选直接证明、附加前提法或反证法；每一步都应有依据，不能用无关文字代替推导。
2. 主范式题先列真值表，别硬推等值演算。
3. 图论计算题画图，别在脑子里绕。
4. 哈斯图别忘了去掉传递边。
5. 结果代回验证：主范式项数、WPL、MST 边数 n-1。