离散数学 · 考点速查（自考 02324 口径）

用途：考前复习定义、公式与适用条件。本文件是 02324 离散数学的知识复习提要，不是官方考试大纲；尚未核验适用省份的现行大纲、2026 年特殊通知及历年题型统计，不据此认定整章考或不考，也不承诺考频、分值或得分。报考范围与考试安排应以适用的官方文件为准。

0. 先复习这 8 个基础结论

1. n 个命题变元 → 真值表 2^n 行，极小项/极大项各 2^n 个。
2. |P(A)| = 2^|A|；|A×B| = |A|·|B|。
3. n 元集合上二元关系共 2^(n²) 个。
4. 等价关系 ⟺ 集合的划分；偏序关系 ⟺ 哈斯图。
5. 握手定理：Σdeg(v) = 2|E|，奇度顶点个数必为偶数。
6. 树：在 n 阶无向图（n≥1）的背景下，“连通”“无回路”“m=n−1”三项中任意两项成立，即为树。
7. 欧拉图：连通 + 所有顶点度为偶数（回路）。
8. 拉格朗日定理：子群阶整除群阶，[G:H] = |G|/|H|。

1. 命题逻辑

1.1 联结词

• p→q 的三种等价说法：¬p∨q、¬q→¬p（逆否）、q 是 p 的必要条件。
• 易错：p→q 为真不代表 q→p 为真；p→q 中 p 为假时命题恒真。

1.2 常用等值演算

双重否定  ¬¬p ⇔ p
幂等      p∧p ⇔ p,  p∨p ⇔ p
交换      p∧q ⇔ q∧p,  p∨q ⇔ q∨p
结合      (p∧q)∧r ⇔ p∧(q∧r)，∨ 同理
分配      p∧(q∨r) ⇔ (p∧q)∨(p∧r)
          p∨(q∧r) ⇔ (p∨q)∧(p∨r)
德摩根    ¬(p∧q) ⇔ ¬p∨¬q,  ¬(p∨q) ⇔ ¬p∧¬q
吸收      p∨(p∧q) ⇔ p,  p∧(p∨q) ⇔ p
零律      p∨1 ⇔ 1,  p∧0 ⇔ 0
同一律    p∨0 ⇔ p,  p∧1 ⇔ p
排中律    p∨¬p ⇔ 1
矛盾律    p∧¬p ⇔ 0
蕴含      p→q ⇔ ¬p∨q
假言易位  p→q ⇔ ¬q→¬p
等价      p↔q ⇔ (p→q)∧(q→p)
输出律    p→(q→r) ⇔ (p∧q)→r
归谬论    (p→q)∧(p→¬q) ⇔ ¬p

1.3 范式

• 析取范式：若干个合取式的析取。
• 主析取范式：每个极小项都包含全部 n 个变元（每个变元或其否定出现一次）。
  • 极小项 m_i 的编号：按变元顺序 p,q,r…，取值为 1 写正文字，0 写否定。例如 p=1,q=0,r=1 → m₅ = p∧¬q∧r。
  • 真值表中该行结果为 1 的极小项之析取。
  • 重言式含全部 2^n 个极小项；矛盾式没有主析取范式。
• 主合取范式：极大项 M_i 编号与极小项相反（取 0 写正文字），取结果为 0 的行。
  • 关系：m_i 与 M_i 互为否定；同一公式的两种范式编号互补。
• 求法二选一：真值表法（稳）、等值演算法（快，最后用分配律补齐缺变元：A ⇔ A∧(p∨¬p)）。

1.4 推理理论

基本规则：

前提引入、结论引入、置换规则
假言推理    p→q, p ⊢ q
附加        p ⊢ p∨q
化简        p∧q ⊢ p
拒取        p→q, ¬q ⊢ ¬p
假言三段    p→q, q→r ⊢ p→r
析取三段    p∨q, ¬p ⊢ q
构造性二难 p→q, r→s, p∨r ⊢ q∨s

• 直接证明：从前提一步步推出结论。
• 附加前提法：要证 p→q，把 p 加入前提推出 q。
• 反证法：把结论的否定 ¬B 加入前提，推出矛盾（如 r∧¬r）。
• 证明时写清每一步的结论及所用规则，便于检查推理是否成立；具体评分以实际评分要求为准。

1.5 联结词完备集

{¬,∧}、{¬,∨}、{¬,→} 都是完备集；{↑}（与非）、{↓}（或非）单独完备。p↑q ⇔ ¬(p∧q)，p↓q ⇔ ¬(p∨q)。

2. 谓词逻辑

2.1 基本概念

• 个体词（常项/变项）、谓词、量词 ∀（全称）、∃（存在）。
• 约束变元：在量词辖域内且与量词同名的变元；其余为自由变元。
• 换名规则：约束变元可改名（新名不与辖域内其他变元冲突）；自由变元可代入，但不能与约束变元同名。

2.2 量词否定

¬∀xA(x) ⇔ ∃x¬A(x)
¬∃xA(x) ⇔ ∀x¬A(x)

2.3 量词分配（只在有条件下成立）

∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x)
∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨∃xB(x)
∀x(A→B(x))    ⇔ A→∀xB(x)      （A 中不含 x 的自由出现）
∃x(A∧B(x))    ⇔ A∧∃xB(x)       （A 中不含 x 的自由出现）

只能单向推出、不能反推：

∀xA(x)∨∀xB(x) ⇒ ∀x(A(x)∨B(x))
∃x(A(x)∧B(x)) ⇒ ∃xA(x)∧∃xB(x)

2.4 前束范式

所有量词移到公式最前面，辖域延伸到公式末尾，如 ∀x∃y(P(x)→Q(x,y))。步骤：消去 →、↔ → 否定内移（用 2.2）→ 变元换名避免冲突 → 量词左移。

2.5 谓词推理

UI 全称实例化  ∀xA(x) ⊢ A(c)      （c 任意）
UG 全称推广    A(x) ⊢ ∀xA(x)      （x 必须任意，未被额外假设约束）
EI 存在实例化  ∃xA(x) ⊢ A(c)      （c 为新引入的见证常项，不能视为任意个体）
EG 存在推广    A(c) ⊢ ∃xA(x)

当前提中并列出现存在命题与全称命题时，可先 EI 引入新见证常项 c，再对全称命题 UI 到 c；每次 EI 应使用新的见证常项。这是常用策略，不是固定顺序：例如 ∀x∃yP(x,y) 必须先对外层 ∀x 做 UI，再对内层 ∃y 做 EI，不能据此推出 ∃y∀xP(x,y)（自然数上取 P(x,y) 为 y>x，前者真、后者假）。

3. 集合论

3.1 运算与恒等式

A-B = A∩~B = A-(A∩B)
A-(B∪C) = (A-B)∩(A-C)
A-(B∩C) = (A-B)∪(A-C)
~(A∪B) = ~A∩~B,  ~(A∩B) = ~A∪~B
A⊕B = (A-B)∪(B-A) = (A∪B)-(A∩B)
A⊕A = ∅,  A⊕∅ = A
(A⊕B)⊕C = A⊕(B⊕C)
A⊆B ⟺ A∪B=B ⟺ A∩B=A ⟺ A-B=∅

3.2 幂集与笛卡尔积

• P(A) = A 的全部子集；|P(A)| = 2^|A|。
• P(∅) = {∅}（元素个数 1，不是 0）；P({∅}) = {∅, {∅}}。
• A×B = {⟨a,b⟩ | a∈A, b∈B}，|A×B| = |A|·|B|；一般不交换。
• 易错：∅∈{∅} 为真；∅⊆{∅} 为真；{∅}⊆∅ 为假。

3.3 容斥原理

|A∪B| = |A|+|B|-|A∩B|
|A∪B∪C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|

求"1..n 中能被 a 或 b 整除的个数"= 容斥直接套；求"至少满足一个性质"同理；求"都不满足"用全集减去并集。

4. 二元关系

4.1 基本

• A 到 B 的关系是 A×B 的子集；A 上有 2^(n²) 个关系。
• 定义域 dom R、值域 ran R、域 fld R。
• 逆关系 R⁻¹ = {⟨y,x⟩ | ⟨x,y⟩∈R}。
• 复合 R∘S（按教材约定方向，通常 ⟨x,z⟩ 表示先经 R 再经 S）：注意矩阵表示时是"行×列"顺序。
• 关系矩阵 M_R：r_ij = 1 当 ⟨a_i,a_j⟩∈R；关系图：有向边。

4.2 五大性质

注意：对每项性质，一个关系要么满足、要么不满足；不满足时应给出反例。“不自反”是存在 x 使 ⟨x,x⟩∉R，“反自反”是所有 x 都有 ⟨x,x⟩∉R，二者不同。主对角线上既有 0 又有 1 时，关系既不自反也不反自反，但这不是对同一性质“既不满足也不违反”。空关系：反自反、对称、反对称、传递都成立；自反不成立（非空集上）。

4.3 闭包

r(R) = R ∪ I_A          （自反闭包）
s(R) = R ∪ R⁻¹          （对称闭包）
t(R) = R ∪ R² ∪ … ∪ R^n （传递闭包，n=|A|）

• 求 t(R)：关系图上看"可达即连边"；或 Warshall 算法（依次以各点为中转点更新）。
• 性质：R 自反 ⇒ s(R)、t(R) 自反；R 对称 ⇒ r(R)、t(R) 对称；R 传递 ⇒ r(R) 传递。

4.4 等价关系与划分

• 等价关系 = 自反 + 对称 + 传递。
• 等价类 [x] = {y | ⟨x,y⟩∈R}；性质：非空、同类相等、不同类不交、并为全集。
• 商集 A/R = 全体等价类的集合。
• 等价关系 ↔ 划分 一一对应，证明时检查等价类非空、不同类不交、并集为全集。
• 典型：模 n 同余、同姓、同余数。

4.5 偏序关系

• 偏序 = 自反 + 反对称 + 传递；偏序集记 ⟨A, ≼⟩。
• 哈斯图画法：删自环、删由传递可得的边、箭头省略（约定向上为"大"）、同层不连线。
• 覆盖：y 覆盖 x ⟺ x≺y 且不存在 z 使 x≺z≺y。哈斯图的边就是覆盖关系。
• 最大元：比所有元素都大（唯一或不存在）；最小元同理。
• 极大元：没有比它更大的元素（可多个）；极小元同理。
• 上界/下界、上确界（最小上界）/下确界（最大下界），注意可能不存在。
• 全序（链）：任意两元可比。良序：每个非空子集有最小元。
• 典型偏序：⊆、整除 |、≤。

5. 函数

• 函数是特殊关系：每个 x 只有唯一像。
• 单射（入射）：f(x₁)=f(x₂) ⇒ x₁=x₂。
• 满射：ran f = B（每个 y 都有原像）。
• 双射 = 单射 + 满射。
• 有限集：|A|=|B| 时，单射 ⟺ 满射 ⟺ 双射。
• 复合 g∘f：(g∘f)(x)=g(f(x))，先 f 后 g；单射/满射/双射都保持。
• 逆函数 f⁻¹ 存在 ⟺ f 是双射。
• 常用计数：|A|=m, |B|=n 时，A→B 共 n^m 个函数；m≤n 时单射个数为 P(n,m)=n!/(n-m)!，m>n 时为 0。
• 特征函数、集合的基数：可数集（自然数、整数、有理数）、不可数（实数 (0,1)）。
• 康托定理：|P(A)| > |A|。

6. 图论基础

6.1 度与握手定理

Σdeg(v) = 2|E|
奇度顶点个数为偶数
n 阶简单无向图：m ≤ n(n-1)/2；有向完全图边数 n(n-1)

• 度序列可图化：最大度 < n；Σ 为偶数；(Havel-Hakimi 依次删最大度并递减后面各项，出现负数则不可图化)。
• 正则图：所有顶点度相同。

6.2 通路与连通

• 通路、简单通路（边不重复）、初级通路/路径（点不重复）、回路、圈。
• 无向图连通：任意两点有通路；连通分支数 p(G)。
• 有向图：强连通（互相可达）、单向连通、弱连通。
• 割点、割边（桥）：删去后连通分支增加。
• 点连通度 κ(G)、边连通度 λ(G)，有 κ ≤ λ ≤ δ。

6.3 欧拉图与哈密顿图

欧拉回路存在 ⟺ 连通 + 所有顶点度为偶数
欧拉通路存在 ⟺ 连通 + 恰有 0 或 2 个奇度顶点（有 2 个时从奇度点出发）
有向欧拉回路 ⟺ 弱连通 + 每个顶点入度=出度

• 哈密顿图：含经过所有顶点一次的回路（判定困难）。
  • 必要条件：对任意非空顶点子集 S，p(G-S) ≤ |S|。
  • 充分条件（简单无向图，n≥3）：δ(G) ≥ n/2（Dirac）；或任意不相邻 u,v 有 deg u + deg v ≥ n（Ore）。
• 易错：欧拉图不一定是哈密顿图；哈密顿图不一定欧拉。

6.4 二部图

• 二部图 ⟺ 无奇圈；完全二部图 K_{m,n} 边数 mn。
• 匹配、最大匹配、完美匹配；霍尔定理（了解）。

6.5 平面图

连通平面图：n - m + r = 2   （r 为面数，含外部面）
简单平面图（n≥3）：m ≤ 3n - 6
无三角形的简单平面图（n≥3，如简单二部平面图）：m ≤ 2n - 4

• K₅、K₃,₃ 非平面（库拉托夫斯基定理：含 K₅ 或 K₃,₃ 的细分）。
• 连通平面图可用欧拉公式反推面数：r = 2 - n + m。
• 对偶图：面变点、公共边变边。

6.6 图的着色

• 点着色数 χ(G)；χ(G) ≤ Δ(G)+1。
• 完全图 χ(K_n)=n；偶圈 χ=2；奇圈 χ=3；二部图（有边）χ=2；平面图 χ≤4。
• 下界：χ(G) ≥ n/α(G)（α 为最大独立集）。

7. 树

7.1 等价刻画（以下每条独立地等价于“G 是树”）

设 G 为 n 阶无向图（n≥1），则 G 是树当且仅当以下任意一条成立：

• 连通且无回路；
• 连通且 m = n-1；
• 无回路且 m = n-1；
• 任意两点之间有唯一路径；
• 连通且每条边都是桥。

7.2 性质

• n≥2 的树至少有 2 片树叶。
• 树中任意删一条边即不连通，加一条边即产生唯一回路。
• 森林：m = n - p（p 为连通分支数）。

7.3 生成树与最小生成树

• 连通图必有生成树，边数 n-1；生成树个数可用矩阵树定理（一般只需会数简单图）。
• Prim：从任一点开始，每次选连接"已选点集"与"未选点集"的最小边（适合稠密图）。
• Kruskal：所有边按权升序，依次加入不成圈的边，选够 n-1 条（适合稀疏图）。
• 最小生成树权值唯一，树形可能不唯一。

7.4 根树

• 根树、父/子、兄弟、层数、树高。
• m 叉树：每个分支点至多 m 个儿子；正则 m 叉树：恰好 m 个儿子。
• 正则二叉树：n₀ = n₂ + 1（叶 = 双分支点 + 1）。
• 哈夫曼算法：每次取两个最小权合并，重复至一个根；WPL = 各叶权 × 叶深度之和 = 所有合并权之和（后者更快）。
• 前缀码：哈夫曼编码是使总码长最短的前缀码。

8. 代数系统

8.1 运算性质

封闭、交换、结合、幂等（a*a=a）、分配、吸收。

• 单位元 e：e*a = a*e = a（唯一）。
• 零元 θ：θ*a = a*θ = θ（唯一）。
• 逆元：a*b = b*a = e 时，b 为 a 的双侧逆元，记 a⁻¹；在含幺半群（因而在群）中，双侧逆元若存在则唯一。
• 消去律：a*b = a*c ⇒ b = c。

8.2 半群 / 群

半群：封闭 + 结合
含幺半群（独异点）：半群 + 单位元
群：封闭 + 结合 + 单位元 + 每元有逆元

• 群的性质：(a⁻¹)⁻¹ = a；(ab)⁻¹ = b⁻¹a⁻¹；单位元与逆元唯一；消去律成立；方程 ax=b、ya=b 有唯一解。
• 有限群中元素 a 的阶 = 使 a^k=e 的最小正整数，且元素的阶整除群的阶。
• 阿贝尔群（交换群）：运算可交换。

8.3 子群与陪集

• 子群判定：对群 G 的子集 H，H 非空且 ∀a,b∈H，ab⁻¹∈H ⇔ H 是子群（乘法记法）；若 H 有限且非空，只需验证对群运算封闭。
• 陪集 aH = {ah | h∈H}；左右陪集大小都等于 |H|，全体陪集构成 G 的划分。
• 拉格朗日定理：|G| = [G:H]·|H|；推论：子群阶整除群阶，元素阶整除群阶。
• 正规子群：∀a∈G，aH = Ha；指数为 2 的子群必正规；阿贝尔群的所有子群正规。
• 商群 G/H（H 正规）。

8.4 循环群

• G = ⟨a⟩ = {a^k | k∈Z}；生成元 a。
• n 阶循环群同构于 ⟨Z_n, +⟩；无限循环群同构于 ⟨Z, +⟩。
• a^k 是生成元 ⟺ gcd(k,n)=1；n 阶循环群有 φ(n) 个生成元。
• 循环群的子群仍是循环群，且 n 阶循环群对每个 d|n 恰有一个 d 阶子群。

8.5 同态与同构

• 同态 f(ab) = f(a)f(b)；单同态、满同态、同构（双射同态）。
• ker f = {a | f(a)=e'} 是 G 的正规子群。
• 同态基本定理：G/ker f ≅ Im f。
• 同构的必要条件：群阶、元素阶分布、交换性、循环性等一致；任一不一致都可排除同构，但这些条件全部一致一般仍不足以证明同构。证明同构应构造并验证双射同态，或引用适用的结构定理。

8.6 环与域

环：⟨R,+,·⟩，加法构成阿贝尔群，乘法半群，乘法对加法分配
整环：交换 + 含幺 + 无零因子的环
域：交换 + 含幺 + 每个非零元有逆元（⇒ 无零因子）

• Z_n 是域 ⟺ n 为素数。
• 零因子：a≠0, b≠0 但 ab=0。

8.7 格与布尔代数

• 格：任意两元都有最小上界（并 a∨b）和最大下界（交 a∧b）。
• 分配格：a∧(b∨c) = (a∧b)∨(a∧c)。
• 有补格：每元有补元（a∨b=1, a∧b=0）。
• 布尔代数 = 有补分配格；补元唯一；满足德摩根律、双重否定、0/1 律。
• 典型布尔代数：⟨P(S), ∪, ∩, ~, ∅, S⟩。
• 有限布尔代数元素个数必为 2^n。

9. 易错点清单

1. p→q 与 q→p 不等值；p→q 为假只有一种情况（p 真 q 假）。
2. 主析取范式取结果为 1 的行，主合取取结果为 0 的行，编号规则相反。
3. ¬∀xP(x) 是 ∃x¬P(x)，不是 ∀x¬P(x)。
4. ∀ 对 ∨、∃ 对 ∧ 不分配（只单向）。
5. P(∅)={∅} 有 1 个元素；∅ 与 {∅} 的 ∈/⊆ 关系别搞混。
6. 对称与反对称可以同时成立（如空关系、对角线关系）。
7. 传递闭包不是 R∪R²，要并到 R^n。
8. 最大元必须与所有元素可比；极大元只要求没有更大的。
9. 树的 m=n-1 必须配合"连通"或"无回路"，单说边数不够。
10. 欧拉图看度数，哈密顿图看回路，两者不等价。
11. 平面图欧拉公式中的 r 包含外部面。
12. 奇度顶点个数必为偶数，这是判断"是否存在"的常用反证点。
13. 子群阶整除群阶，但"整除群阶的子集"不一定是子群。
14. 循环群元素 a^k 的阶 = n/gcd(n,k)。
15. 同态核一定是正规子群，像是子群但不一定正规。

10. 数字记忆卡