离散数学期末复习

发表于 2026/05/31 更新于 2026/06/04

作者 youzi

73 分钟阅读

离散数学期末复习

本资料按期末复习需要整理，重点放在定义、判定方法、常用公式、易错点、典型例题和自测题。建议先掌握“能判定、会计算、能翻译、会证明”的基本能力，再集中练综合题。

复习总览

复习模块与重点

模块	核心内容	期末常见题型
集合	集合运算、幂集、笛卡儿积、集合恒等式	计算、证明集合相等
二元关系	关系性质、复合、闭包、等价关系、偏序关系	判定、矩阵/图表示、等价类、哈斯图
函数	单射、满射、双射、复合、逆函数	判定、计数、证明
图论基础	度数、连通性、简单图、完全图、路径与回路	计算边数、判断连通、构造图
欧拉图与哈密顿图	欧拉通路/回路、哈密顿通路/回路	判定、构造、对比说明
图论专题	最短路、树、平面图、支配集、覆盖集、匹配、着色	算法计算、判定、证明、构造
命题逻辑	真值表、等值演算、范式、推理规则	判断公式类型、化范式、证明推理有效
一阶逻辑	谓词、量词、解释、等值演算、推理	自然语言翻译、量词变换、形式证明

建议复习顺序

先复习集合、关系、函数，因为这些是后续图论和逻辑表达的基础。
再复习图论，重点区分“欧拉看边，哈密顿看点”，并补上最短路、树、平面图、匹配与着色。
最后复习命题逻辑和一阶逻辑，重点训练等值演算和推理证明。
考前优先刷判定题和证明题：关系性质、等价/偏序、欧拉图、逻辑公式类型、量词公式转换。

核心能力清单

能用定义判断对象是否满足某性质。
能用公式快速计算集合、关系、函数和图的基本量。
能把自然语言准确翻译为命题公式或谓词公式。
能用等值演算逐步化简逻辑公式。
能写出结构清楚的证明，尤其是“双包含法”和“由前提推出结论”的推理链。

一、集合

1. 基本概念

集合是由确定对象组成的整体。集合中的对象称为元素。

a ∈ A：a 是集合 A 的元素。
a ∉ A：a 不是集合 A 的元素。
A ⊆ B：A 是 B 的子集，即任意 x ∈ A 都有 x ∈ B。
A ⊂ B：A 是 B 的真子集，即 A ⊆ B 且 A ≠ B。
∅：空集，不含任何元素。
U：全集，讨论范围内所有对象组成的集合。

常见表示法：

列举法：A = {1, 2, 3}。
描述法：A = {x | x 是小于 10 的正偶数}。
区间或条件表示：例如 {x ∈ Z | x > 0} 表示正整数集合。

重要结论：

∅ ⊆ A 对任何集合 A 成立。
A ⊆ A 对任何集合 A 成立。
如果有限集合 A 有 n 个元素，则幂集 P(A) 有 2^n 个元素。

2. 集合运算

设 A、B 是全集 U 的子集。

并集：A ∪ B = {x | x ∈ A 或 x ∈ B}。
交集：A ∩ B = {x | x ∈ A 且 x ∈ B}。
差集：A - B = {x | x ∈ A 且 x ∉ B}。
补集：Ā = U - A。
对称差：A △ B = (A - B) ∪ (B - A)。
笛卡儿积：A × B = {(a, b) | a ∈ A 且 b ∈ B}。

常用公式：

交换律：A ∪ B = B ∪ A，A ∩ B = B ∩ A。
结合律：(A ∪ B) ∪ C = A ∪ (B ∪ C)，(A ∩ B) ∩ C = A ∩ (B ∩ C)。
分配律：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̄。
吸收律：A ∪ (A ∩ B) = A，A ∩ (A ∪ B) = A。
包含判定：A ⊆ B ⇔ A ∩ B = A ⇔ A ∪ B = B ⇔ A - B = ∅。

3. 证明集合相等

常用方法有三种：

双包含法：证明 A ⊆ B 且 B ⊆ A。
元素法：任取 x，证明 x ∈ A ⇔ x ∈ B。
运算律法：用集合恒等式一步步化简。

证明时推荐写法：

任取 x ∈ 左边。
根据定义推出 x 满足右边条件，所以 x ∈ 右边。
因此左边 ⊆ 右边。
同理证明右边 ⊆ 左边。
所以两集合相等。

4. 典型例题

例 1：证明 A - (B ∪ C) = (A - B) ∩ (A - C)。

解析：

A - (B ∪ C)
= A ∩ (B ∪ C)̄
= A ∩ (B̄ ∩ C̄)
= (A ∩ B̄) ∩ (A ∩ C̄)
= (A - B) ∩ (A - C)

例 2：设 A = {1, 2}，B = {a, b, c}，求 A × B 的元素个数。

解析：|A × B| = |A| · |B| = 2 · 3 = 6。具体为 {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}。

5. 自测题

若 A = {1,2,3}，写出 P(A) 的元素个数。
判断：∅ ∈ {∅, {1}} 是否成立？
证明：A ∩ (B - C) = (A ∩ B) - C。
若 A ⊆ B，判断 A ∩ C ⊆ B ∩ C 是否一定成立。

二、二元关系

1. 关系的定义与表示

设 A、B 是集合，A × B 的任意子集都称为从 A 到 B 的二元关系。若 R ⊆ A × A，则称 R 是集合 A 上的二元关系。

如果 (a, b) ∈ R，也可写作 aRb。

常见表示方式：

集合表示：R = {(1,2), (2,3)}。
关系矩阵：用 0/1 矩阵表示是否存在关系。
关系图：顶点表示元素，有向边 a -> b 表示 (a,b) ∈ R。

2. 关系的运算

逆关系：

R^-1 = {(b, a) | (a, b) ∈ R}

复合关系：

S ∘ R = {(a, c) | 存在 b，使得 (a,b) ∈ R 且 (b,c) ∈ S}

注意顺序：S ∘ R 表示先经过 R，再经过 S。

关系的幂：

R^1 = R。
R^2 = R ∘ R。
R^n = R^(n-1) ∘ R。

3. 关系性质判定

设 R 是集合 A 上的关系。

性质	定义	矩阵/图判定
自反	对任意 `a ∈ A`，都有 `aRa`	主对角线全为 `1`；每个顶点有自环
反自反	对任意 `a ∈ A`，都没有 `aRa`	主对角线全为 `0`；无自环
对称	若 `aRb`，则 `bRa`	矩阵关于主对角线对称；边成对反向出现
反对称	若 `aRb` 且 `bRa`，则 `a = b`	非对角位置不能同时成对为 `1`
传递	若 `aRb` 且 `bRc`，则 `aRc`	有路径 `a -> b -> c` 时必须有边 `a -> c`

易错点：

反对称不是“没有对称边”，而是“不允许不同元素之间双向相关”。
一个关系可以既对称又反对称，例如恒等关系 {(a,a) | a ∈ A}。
传递性要检查所有两步路径，不能只看相邻几个元素。

4. 等价关系

若集合 A 上的关系 R 同时满足自反、对称、传递，则称 R 是等价关系。

等价类：

[a] = {x ∈ A | xRa}

等价关系的重要结论：

任意元素 a 必属于自己的等价类 [a]。
两个等价类要么完全相等，要么互不相交。
所有等价类构成 A 的一个划分。
反过来，A 的任意划分都能确定一个等价关系：同一块中的元素互相关。

典型例子：

整数集合 Z 上定义 aRb ⇔ a ≡ b (mod n)，这是等价关系。
等价类是按除以 n 的余数分类。

5. 偏序关系

若集合 A 上的关系 R 同时满足自反、反对称、传递，则称 R 是偏序关系，记为 (A, R)。

常见偏序：

数集上的小于等于关系 ≤。
集合族上的包含关系 ⊆。
正整数上的整除关系 |，其中 a | b 表示 a 整除 b。

偏序中的元素：

极大元：没有比它更大的可比较元素。
最大元：它大于等于集合中所有元素。
极小元：没有比它更小的可比较元素。
最小元：它小于等于集合中所有元素。
上界：大于等于子集中所有元素的元素。
下界：小于等于子集中所有元素的元素。
最小上界：所有上界中的最小者，也叫上确界。
最大下界：所有下界中的最大者，也叫下确界。

易错点：

最大元若存在一定唯一，极大元可以有多个。
最小元若存在一定唯一，极小元可以有多个。
极大元不一定能和所有元素比较，最大元必须能和所有元素比较。

哈斯图画法：

先画出偏序关系中的覆盖关系。
去掉自环。
去掉由传递性可以推出的边。
小元素画在下方，大元素画在上方，箭头通常省略。

6. 典型例题

例 1：设 A = {1,2,3}，R = {(1,1),(2,2),(3,3),(1,2),(2,1)}。判断 R 是否为等价关系。

解析：

自反：(1,1),(2,2),(3,3) 都在 R 中，满足。
对称：(1,2) 与 (2,1) 成对出现，满足。
传递：因为 1R2 且 2R1，需要 1R1，有；2R1 且 1R2，需要 2R2，有；其他情况也满足。
所以 R 是等价关系。等价类为 {1,2} 和 {3}。

例 2：在 {1,2,3,6} 上定义整除关系 |。求极小元、最小元、极大元、最大元。

解析：

1 整除所有元素，所以 1 是最小元，也是极小元。
所有元素都整除 6，所以 6 是最大元，也是极大元。

7. 自测题

设 A = {1,2,3}，R = {(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)}，判断 R 是否传递。
判断恒等关系 I_A = {(a,a) | a ∈ A} 是否对称、反对称。
在整数集合上，关系 aRb ⇔ a - b 是偶数，是否为等价关系？
在 P({1,2}) 上按 ⊆ 构成偏序，求最大元和最小元。

三、函数

1. 函数的定义

设 A、B 是非空集合，如果对每个 a ∈ A，都存在唯一的 b ∈ B 与之对应，则称 f 是从 A 到 B 的函数，记为：

f: A -> B

其中：

A 是定义域。
B 是陪域。
{f(a) | a ∈ A} 是值域，也叫像集。

注意：值域一定是陪域的子集，但不一定等于陪域。

2. 单射、满射、双射

单射：

若 f(a1) = f(a2)，则 a1 = a2。

等价说法：不同的输入不会得到相同的输出。

满射：

对任意 b ∈ B，存在 a ∈ A，使得 f(a) = b。

等价说法：陪域中每个元素都被映到。

双射：

f 既是单射又是满射。

双射的重要意义：函数存在反函数。

3. 复合函数与逆函数

若 f: A -> B，g: B -> C，则复合函数 g ∘ f: A -> C 定义为：

(g ∘ f)(a) = g(f(a))

注意顺序：g ∘ f 表示先做 f，再做 g。

逆函数：

只有双射才存在反函数。
若 f(a) = b，则 f^-1(b) = a。
f^-1 ∘ f = I_A，f ∘ f^-1 = I_B。

4. 有限集合上的判定技巧

设 A、B 是有限集合。

若 |A| > |B|，则不存在从 A 到 B 的单射。
若 |A| < |B|，则不存在从 A 到 B 的满射。
若 |A| = |B|，则单射、满射、双射三者可以互相推出。

5. 典型例题

例 1：判断 f: Z -> Z，f(x) = 2x + 1 是否单射、满射。

解析：

单射：若 f(a)=f(b)，则 2a+1=2b+1，所以 a=b，是单射。
满射：值域只包含奇数，不包含偶数，所以不是满射。

例 2：设 f: R -> R，f(x)=x^3。判断是否存在反函数。

解析：x^3 在实数上严格单调，既单射又满射，因此是双射，存在反函数 f^-1(x)=三次方根 x。

6. 自测题

判断 f: R -> R，f(x)=x^2 是否单射、满射。
若 A={1,2,3}，B={a,b}，是否可能存在从 A 到 B 的单射？
若 f: A -> B 和 g: B -> C 都是双射，判断 g ∘ f 是否双射。
若 f: A -> B 有反函数，说明 f 必须满足什么性质。

四、图的基本概念

1. 图的组成

图通常记为 G = (V, E)，其中：

V 是顶点集合。
E 是边集合。

常见类型：

无向图：边没有方向。
有向图：边有方向。
简单图：无自环、无重边的无向图。
多重图：允许重边。
完全图 K_n：任意两个不同顶点之间都有边。
子图：顶点和边都来自原图的图。
补图：在同一顶点集上，原图没有的边构成补图。

完全图边数：

K_n 的边数 = n(n-1)/2

2. 度数与握手定理

无向图中，顶点 v 的度数 deg(v) 是与 v 关联的边数。自环通常贡献 2 度。

握手定理：

Σ deg(v) = 2|E|

重要推论：

无向图中奇度顶点个数一定为偶数。

有向图中：

入度：指向该顶点的边数。
出度：从该顶点出发的边数。

公式：

Σ 入度 = Σ 出度 = |E|

3. 通路、回路与连通性

通路：顶点和边交替出现的序列，相邻顶点之间有边。
回路：起点和终点相同的通路。
简单路径：通常指顶点不重复的路径。
简单回路：除起点和终点相同外，其余顶点不重复。
连通图：无向图中任意两个顶点之间都有路径。
连通分量：极大的连通子图。

易错点：

“路径是否允许重复顶点”要看教材定义，考试中按题目说明。
判断欧拉图时通常要求忽略孤立点后相关部分连通。
简单图中，n 个顶点的最大度数是 n-1。

4. 典型例题

例 1：一个无向图有 6 个顶点，度数分别为 1,2,2,3,4,4，问这样的图是否可能存在？

解析：度数和为 1+2+2+3+4+4=16，是偶数，不违反握手定理。但这只是必要条件，还要进一步构造或用图序列判定。期末基础题中若只问“是否违反握手定理”，答案是不违反。

例 2：完全图 K_5 有多少条边？

解析：5·4/2 = 10 条。

5. 自测题

无向图的度数和为 15 是否可能？
K_6 有多少条边？
有向图有 8 条边，则所有顶点入度之和是多少？
一个无向图有 4 个奇度顶点，是否违反握手定理？

五、欧拉图与哈密顿图

1. 欧拉通路与欧拉回路

欧拉通路：经过图中每条边恰好一次的通路。
欧拉回路：经过图中每条边恰好一次且起点等于终点的回路。
欧拉图：含有欧拉回路的图。

无向图判定：

连通无向图存在欧拉回路 ⇔ 每个顶点度数都是偶数。
连通无向图存在欧拉通路但不存在欧拉回路 ⇔ 恰有两个奇度顶点。
若奇度顶点超过两个，则不存在欧拉通路。

有向图判定：

有向图存在欧拉回路：每个顶点入度等于出度，并且所有非零度顶点在连通意义上属于同一部分。
有向图存在欧拉通路：一个顶点满足 出度 = 入度 + 1，一个顶点满足 入度 = 出度 + 1，其余顶点入度等于出度，并且相关顶点连通。

2. 哈密顿通路与哈密顿回路

哈密顿通路：经过图中每个顶点恰好一次的通路。
哈密顿回路：经过图中每个顶点恰好一次并回到起点的回路。
哈密顿图：含有哈密顿回路的图。

与欧拉图不同，哈密顿图没有简单通用的充要判定。考试中常见方法：

直接构造一个经过所有顶点的回路。
证明不存在，例如删去某些顶点后连通分量过多。
使用充分条件。

常用充分条件：

Dirac 定理：设 G 是有 n ≥ 3 个顶点的简单图，若每个顶点度数都至少为 n/2，则 G 有哈密顿回路。
Ore 定理：设 G 是有 n ≥ 3 个顶点的简单图，若任意两个不相邻顶点 u,v 都满足 deg(u)+deg(v) ≥ n，则 G 有哈密顿回路。

注意：这些是充分条件，不满足条件不代表一定没有哈密顿回路。

3. 欧拉与哈密顿对比

对比项	欧拉	哈密顿
关注对象	边	顶点
要求	每条边恰好一次	每个顶点恰好一次
判定难度	有明确度数判定	一般较难，无简单充要条件
常用方法	看奇度顶点个数	构造、反证、充分条件

4. 典型例题

例 1：某连通无向图顶点度数为 2,2,2,4,4，判断是否有欧拉回路。

解析：所有顶点度数都是偶数，且图连通，所以存在欧拉回路。

例 2：某连通无向图顶点度数为 1,2,2,3,4，判断是否有欧拉通路。

解析：奇度顶点为度数 1 和 3 的两个顶点，恰有两个奇度顶点，所以存在欧拉通路，但不存在欧拉回路。

例 3：简单图有 n=6 个顶点，最小度数为 3。能否推出有哈密顿回路？

解析：因为 n/2 = 3，最小度数 δ(G)=3 ≥ n/2，由 Dirac 定理可推出有哈密顿回路。

5. 自测题

连通无向图有 0 个奇度顶点，是否存在欧拉回路？
连通无向图有 4 个奇度顶点，是否存在欧拉通路？
有向图中每个顶点入度都等于出度，是否一定有欧拉回路？
不满足 Dirac 条件的图是否一定不是哈密顿图？

五、最短路、树、平面图、匹配与着色

本节对应图片中第 15.3、16、17、18 章内容，接在欧拉图与哈密顿图之后复习。核心思路是：先掌握加权图上的路径优化，再掌握树和平面图的结构公式，最后掌握图中“选点、选边、配对、染色”的几类典型优化问题。

1. 最短路问题

加权图是在边上赋予权值的图。路径长度通常定义为路径上各边权值之和。最短路问题是在两个顶点之间寻找权值和最小的路径。

常见类型：

单源最短路：从一个起点到其他所有顶点的最短路。
两点最短路：从指定起点到指定终点的最短路。
多源或全源最短路：任意两个顶点之间的最短路。

Dijkstra 算法：

适用条件：边权非负。
基本思想：每次选择当前距离起点最近且尚未确定的顶点，把它的最短距离固定下来，再用它更新相邻顶点。
易错点：若存在负权边，普通 Dijkstra 算法不再保证正确。

Dijkstra 简要步骤：

起点距离设为 0，其余顶点距离设为 ∞。
从未确定顶点中选距离最小者 u。
将 u 标记为已确定。
对 u 的每个邻点 v，若 dist(u)+w(u,v) < dist(v)，则更新 dist(v)。
重复直到所有顶点确定或目标顶点确定。

Floyd 算法：

适用于求所有顶点对之间的最短路。
允许负权边，但不能有负权回路。
思想：逐步允许顶点 1,2,...,k 作为中间点，更新任意两点间距离。

核心递推：

d[i][j] = min(d[i][j], d[i][k] + d[k][j])

2. 中国邮递员问题与货郎担问题

中国邮递员问题：

目标：从某点出发，走遍图中每条边至少一次，最后回到出发点，并使总路程最短。
本质：边遍历问题，与欧拉回路密切相关。
若加权连通无向图本身是欧拉图，则最优路线就是一条欧拉回路，总长度为所有边权之和。
若不是欧拉图，则需要重复走某些边，使所有顶点度数变为偶数，同时重复边的总权值尽量小。

无向图常用解法思路：

找出所有奇度顶点。
计算这些奇度顶点两两之间的最短路长度。
将奇度顶点两两配对，使配对最短路总长度最小。
把这些最短路对应的边重复加入原图。
新图所有顶点度数为偶数，求欧拉回路。

货郎担问题，也叫旅行商问题 TSP：

目标：从某城市出发，每个城市恰好访问一次，最后回到起点，并使总路程最短。
本质：顶点遍历问题，与哈密顿回路密切相关。
若只问是否存在经过所有顶点一次的回路，是哈密顿回路问题。
若还要求总权值最小，就是 TSP 优化问题。

中国邮递员问题与 TSP 对比：

问题	关注对象	允许重复	目标
中国邮递员问题	边	顶点和边都可能重复	每条边至少走一次，总路程最短
货郎担问题 TSP	顶点	通常顶点不能重复访问	每个顶点恰好访问一次，总路程最短

3. 无向树及其性质

树是连通且无回路的无向图。森林是无回路的无向图，森林的每个连通分量都是一棵树。

设树 T 有 n 个顶点、m 条边，则：

m = n - 1
Σdeg(v) = 2(n - 1)

树的常用等价刻画：

T 连通且无回路。
T 连通，且边数为 n-1。
T 无回路，且边数为 n-1。
T 中任意两个顶点之间有唯一简单路径。
T 中任意一条边都是桥，删去后图不连通。
在 T 中任意添加一条新边，都会产生唯一回路。

叶子与度数：

度数为 1 的顶点称为叶子。
非平凡树至少有两个叶子。
树中不会出现所有顶点度数都大于等于 2 的情况，否则会形成回路。

4. 生成树与最小生成树

设 G 是连通无向图。若 T 是 G 的子图，且 T 包含 G 的所有顶点并且是一棵树，则称 T 是 G 的生成树。

重要结论：

连通图一定存在生成树。
非连通图不存在覆盖所有顶点的生成树，但每个连通分量有自己的生成树。
若连通图有 n 个顶点，则任意生成树都有 n-1 条边。
从连通图中不断删除回路上的边，且不破坏连通性，最终可得到生成树。

最小生成树：

在加权连通无向图中，权值和最小的生成树称为最小生成树。
Kruskal 算法：按边权从小到大选边，若加入后不形成回路就保留，直到选出 n-1 条边。
Prim 算法：从一个顶点开始，每次选择连接“已选顶点集”和“未选顶点集”的最小权边，直到覆盖全部顶点。

易错点：

生成树要求包含原图所有顶点，但不要求包含所有边。
最小生成树不一定唯一；若边权有相同值，可能存在多棵最小生成树。
Kruskal 防回路，Prim 保连通扩张。

5. 根树及其应用

指定一个顶点作为根的树称为根树。

常用术语：

根：最顶层顶点。
父亲与儿子：若从根到某顶点的路径上，u 紧接在 v 前面，则 u 是 v 的父亲，v 是 u 的儿子。
兄弟：有同一父亲的顶点。
祖先与后代：沿根到顶点路径形成的上下级关系。
叶子：没有儿子的顶点。
内部顶点：至少有一个儿子的顶点。
层数：从根到该顶点的路径长度。
高度：根到最远叶子的路径长度。

m 叉树：

每个内部顶点最多有 m 个儿子的根树称为 m 叉树。
每个内部顶点恰有 m 个儿子的称为满 m 叉树。

满 m 叉树公式：

若内部顶点数为 i，叶子数为 l，总顶点数为 n，则：

n = mi + 1
l = (m - 1)i + 1

常见应用：

表达式树：用树表示算术表达式或逻辑表达式。
决策树：用树表示分类或判断过程。
搜索树：DFS/BFS 过程中形成的树结构。
编码树：如前缀编码、哈夫曼编码。

6. 平面图的基本概念

如果一个图可以画在平面上，并且任意两条边只在公共端点处相交，不发生边与边的交叉，则称它为平面图。某个已经无交叉画出的图称为平面嵌入或平面图的一种画法。

平面图把平面分成若干区域，称为面，其中无界的区域称为外部面。

欧拉公式：

对连通平面图，若顶点数为 v，边数为 e，面数为 f，则：

v - e + f = 2

若平面图有 c 个连通分量，则：

v - e + f = 1 + c

常用推论：

简单连通平面图若 v ≥ 3，则 e ≤ 3v - 6。
若简单连通平面图没有三角形，且 v ≥ 3，则 e ≤ 2v - 4。
K_5 不是平面图，因为 e=10，但 3v-6=9。
K_{3,3} 不是平面图，因为它无三角形，e=9，但 2v-4=8。

易错点：

图是否平面与画法有关，但只要存在一种无交叉画法，它就是平面图。
看起来有交叉的图不一定非平面，可能换一种画法就无交叉。
欧拉公式中的 f 包括外部面。

7. 平面图的判断与对偶图

判断平面图常用方法：

尝试重新画图，寻找无交叉画法。
使用欧拉公式及其推论排除非平面图。
识别是否含有与 K_5 或 K_{3,3} 相关的非平面结构。

对偶图：

对给定连通平面图 G 的某个平面嵌入，在每个面内放一个新顶点。
若原图中一条边分隔两个面，则在对偶图中连接对应两个面顶点。
原图的每条边对应对偶图的一条边。

重要提醒：

对偶图依赖于平面嵌入；同一个平面图的不同画法可能产生不同形式的对偶图。
原图中的桥在对偶图中常对应自环。
原图中的面着色问题可转化为对偶图的点着色问题。

8. 支配集、覆盖集与独立集

支配集：

设 G=(V,E)。若 D ⊆ V，并且每个不在 D 中的顶点都至少与 D 中某个顶点相邻，则称 D 是支配集。

最小支配数：

γ(G) = 最小支配集的顶点个数

点覆盖集：

若 C ⊆ V，并且图中每条边至少有一个端点属于 C，则称 C 是点覆盖集。

点独立集：

若 S ⊆ V，并且 S 中任意两个不同顶点之间都没有边相连，则称 S 是点独立集。

点覆盖与点独立的重要关系：

S 是点独立集 ⇔ V - S 是点覆盖集

因此在有限图中：

最大独立集大小 + 最小点覆盖集大小 = |V|

边覆盖集：

若 F ⊆ E，并且每个顶点都至少与 F 中某条边关联，则称 F 是边覆盖集。

注意：如果图中有孤立顶点，则不存在覆盖所有顶点的边覆盖集。

9. 匹配与二部图中的匹配

匹配是边集 M ⊆ E，其中任意两条边都没有公共端点。

10. 点着色、地图着色与边着色

点着色：

给图的顶点染色，使任意相邻顶点颜色不同。所需最少颜色数称为色数，记为 χ(G)。

常见结论：

χ(K_n)=n。
若图是二部图且至少有一条边，则 χ(G)=2。
无奇回路的图是二部图，因此可用 2 种颜色点着色。
若图含有 K_n 子图，则 χ(G) ≥ n。

地图着色：

将地图区域看作平面图的面，相邻区域要求颜色不同。
可通过构造对偶图，把面着色转化为对偶图的点着色。
四色定理：任意平面地图可以用不超过 4 种颜色着色。

边着色：

给图的边染色，使相邻边颜色不同。相邻边指有公共端点的边。

边色数记为 χ'(G)。

常见结论：

任意图的边色数至少为最大度数 Δ(G)。
简单图满足 Vizing 定理：Δ(G) ≤ χ'(G) ≤ Δ(G)+1。
二部图的边色数等于最大度数：χ'(G)=Δ(G)。

11. 典型例题

例 1：某连通无向加权图所有顶点度数都是偶数，所有边权和为 50。求中国邮递员问题的最优总长度。

解析：所有顶点度数都是偶数，图存在欧拉回路。邮递员可沿欧拉回路走遍所有边并回到起点，所以最优总长度为 50。

例 2：一棵树有 10 个顶点，求边数和度数和。

解析：树的边数为 n-1=9，度数和为 2m=18。

例 3：判断 K_5 是否为平面图。

解析：若 K_5 是简单平面图，则应满足 e ≤ 3v-6。但 K_5 中 v=5、e=10，而 3v-6=9，矛盾。所以 K_5 不是平面图。

例 4：设 P_4 是 4 个顶点的路径图。求其最小点覆盖数和最大独立数。

解析：路径为 v1-v2-v3-v4。取 {v2,v3} 可覆盖所有边，所以最小点覆盖数为 2。取 {v1,v3} 或 {v1,v4} 是大小为 2 的独立集，最大独立数为 2。二者之和为 4=|V|。

12. 自测题

Dijkstra 算法为什么要求边权非负？
中国邮递员问题和货郎担问题分别关注边还是顶点？
一棵树有 n 个顶点，边数是多少？
连通图是否一定存在生成树？
满二叉树有 i 个内部顶点，叶子数是多少？
连通平面图有 v=8、e=12，求面数 f。
用平面图边数不等式判断 K_5 是否平面。
什么是点覆盖集？它和点独立集有什么关系？
极大匹配和最大匹配是否一定相同？
二部图存在饱和左部 X 的匹配需要满足什么条件？
若一个图含有奇回路，它能否是二部图？
简单图最大度数为 4，它的边色数可能是多少？

六、命题逻辑基本概念与等值演算

1. 命题与联结词

命题是能够判断真假的陈述句。疑问句、祈使句、含糊不确定的句子通常不是命题。

常用联结词：

符号	名称	含义
`¬p`	否定	非 `p`
`p ∧ q`	合取	`p` 且 `q`
`p ∨ q`	析取	`p` 或 `q`，通常为相容或
`p -> q`	蕴含	若 `p` 则 `q`
`p <-> q`	等价	`p` 与 `q` 同真同假

蕴含 p -> q 只有在 p 真、q 假时为假，其余情况均为真。

2. 公式类型

重言式：所有赋值下都为真。
矛盾式：所有赋值下都为假。
可满足式：至少存在一个赋值使其为真。

关系：

重言式一定可满足。
矛盾式不可满足。
非重言式不一定是矛盾式。

3. 常用等值式

基本等值：

p -> q ≡ ¬p ∨ q。
p <-> q ≡ (p -> q) ∧ (q -> p)。
p <-> q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)。

德摩根律：

¬(p ∧ q) ≡ ¬p ∨ ¬q。
¬(p ∨ q) ≡ ¬p ∧ ¬q。

双重否定：

¬¬p ≡ p。

分配律：

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)。
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)。

吸收律：

p ∨ (p ∧ q) ≡ p。
p ∧ (p ∨ q) ≡ p。

常量律：

p ∨ 1 ≡ 1，p ∧ 1 ≡ p。
p ∨ 0 ≡ p，p ∧ 0 ≡ 0。

4. 范式

析取范式：若干合取项的析取，例如：

(p ∧ ¬q) ∨ (¬p ∧ r)

合取范式：若干析取项的合取，例如：

(p ∨ q) ∧ (¬p ∨ r)

主析取范式：

每个合取项都包含全部命题变元。
每个变元只出现一次。
通常由真值表中公式取真值 1 的行得到。

主合取范式：

每个析取项都包含全部命题变元。
每个变元只出现一次。
通常由真值表中公式取真值 0 的行得到。

5. 典型例题

例 1：化简 (p -> q) ∧ p。

解析：

(p -> q) ∧ p
≡ (¬p ∨ q) ∧ p
≡ (p ∧ ¬p) ∨ (p ∧ q)
≡ 0 ∨ (p ∧ q)
≡ p ∧ q

例 2：判断公式 p -> (q -> p) 是否为重言式。

解析：

p -> (q -> p)
≡ ¬p ∨ (¬q ∨ p)
≡ (¬p ∨ p) ∨ ¬q
≡ 1 ∨ ¬q
≡ 1

所以是重言式。

6. 自测题

将 ¬(p ∨ q) 化为只含 ¬、∧ 的形式。
判断 p ∨ ¬p 是什么类型的公式。
化简 p ∧ (p ∨ q)。
将 p -> q 改写为不含蕴含符号的公式。

七、命题逻辑推理理论

1. 推理有效性

推理形式：

前提1, 前提2, ..., 前提n ⊢ 结论

推理有效的含义：当前提全真时，结论必真。

判定方法：

真值表法：检查所有前提都为真的行，结论是否都为真。
等值演算法：证明 (前提1 ∧ ... ∧ 前提n) -> 结论 是重言式。
推理规则法：从前提出发，逐步推出结论。

2. 常用推理规则

规则	形式
假言推理	`p -> q, p ⊢ q`
拒取式	`p -> q, ¬q ⊢ ¬p`
析取三段论	`p ∨ q, ¬p ⊢ q`
假言三段论	`p -> q, q -> r ⊢ p -> r`
合取引入	`p, q ⊢ p ∧ q`
合取消去	`p ∧ q ⊢ p`，`p ∧ q ⊢ q`
析取引入	`p ⊢ p ∨ q`
化简	`p ∧ q ⊢ p`

常见错误：

肯定后件谬误：由 p -> q 和 q 推出 p，无效。
否定前件谬误：由 p -> q 和 ¬p 推出 ¬q，无效。

3. 典型例题

例：证明 p -> q, q -> r, p ⊢ r。

证明：

p -> q        前提
q -> r        前提
p             前提
q             由 1,3 假言推理
r             由 2,4 假言推理

4. 自测题

判断 p -> q, q ⊢ p 是否有效。
证明 p ∧ q ⊢ q ∧ p。
判断 p -> q, ¬q ⊢ ¬p 是否有效。
证明 p -> q, q -> r ⊢ p -> r。

八、一阶逻辑基本概念

1. 谓词、个体与量词

一阶逻辑比命题逻辑更细致，能表达对象及对象性质。

个体常元：表示具体对象，如 a、b。
个体变元：表示任意对象，如 x、y。
谓词：表示性质或关系，如 P(x)、R(x,y)。
函数符号：表示对象到对象的对应，如 f(x)。
论域：变量取值的范围。

量词：

全称量词：∀x P(x)，表示所有 x 都满足 P。
存在量词：∃x P(x)，表示至少存在一个 x 满足 P。

2. 自由变元与约束变元

在 ∀x P(x) 或 ∃x P(x) 中，x 被量词约束，称为约束变元。

没有被相应量词约束的变量称为自由变元。

例：

∀x R(x, y)

其中 x 是约束变元，y 是自由变元。

含自由变元的公式通常不是命题，只有给自由变元赋值或加上量词后才有确定真假。

3. 自然语言翻译

常见表达：

“所有 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”：¬∀x(A(x) -> B(x))，等价于 ∃x(A(x) ∧ ¬B(x))。

易错点：

全称句通常用蕴含 ->。
存在句通常用合取 ∧。
∀x(A(x) ∧ B(x)) 表示所有对象都是 A 且都是 B，通常太强。
∃x(A(x) -> B(x)) 很弱，因为不是 A 的对象会使命题自动为真。

4. 典型例题

例：论域为全体学生，P(x) 表示“x 认真复习”，Q(x) 表示“x 通过考试”。翻译“所有认真复习的学生都能通过考试”。

解析：

∀x(P(x) -> Q(x))

例：翻译“有些学生没有认真复习但通过了考试”。

∃x(¬P(x) ∧ Q(x))

5. 自测题

翻译“所有偶数都能被 2 整除”。
翻译“存在一个学生喜欢离散数学”。
判断 ∀x(P(x) ∧ Q(x)) 与 ∀xP(x) ∧ ∀xQ(x) 是否等价。
判断 ∃x(P(x) -> Q(x)) 是否适合表达“有些 P 是 Q”。

九、一阶逻辑等值演算和推理

1. 量词否定

最重要的量词等值式：

¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)

含义：

“并非所有人都及格”等价于“至少有一个人不及格”。
“不存在反例”等价于“所有对象都不是反例”。

2. 量词分配

一定成立：

∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x)
∃x(P(x) ∨ Q(x)) ≡ ∃xP(x) ∨ ∃xQ(x)

一般不成立：

∀x(P(x) ∨ Q(x)) ≠ ∀xP(x) ∨ ∀xQ(x)
∃x(P(x) ∧ Q(x)) ≠ ∃xP(x) ∧ ∃xQ(x)

变量不自由出现时的常用等值：

若 x 不在 Q 中自由出现，则 ∀x(P(x) ∧ Q) ≡ ∀xP(x) ∧ Q。
若 x 不在 Q 中自由出现，则 ∃x(P(x) ∨ Q) ≡ ∃xP(x) ∨ Q。

3. 量词辖域与换名

量词辖域是量词作用的公式范围。变换公式时要避免变量混淆。

约束变元可以换名：

∀x P(x) ≡ ∀y P(y)

但换名不能捕获原本自由的变量。例如在含自由变量 y 的公式中，不能随意把 x 换成 y，否则会改变含义。

4. 一阶逻辑推理规则

全称实例化：

∀x P(x) ⊢ P(a)

全称推广：

若能对任意对象 x 证明 P(x)，则可推出 ∀x P(x)

存在实例化：

∃x P(x) 可引入新的常元 c，使 P(c) 成立

限制：c 必须是新的，不能是已有特定对象。

存在推广：

P(a) ⊢ ∃x P(x)

5. 典型例题

例 1：证明 ∀x(P(x) -> Q(x)), ∀xP(x) ⊢ ∀xQ(x)。

证明：

∀x(P(x) -> Q(x))       前提
∀xP(x)                 前提
任取个体 a
P(a) -> Q(a)            由 1 全称实例化
P(a)                    由 2 全称实例化
Q(a)                    由 4,5 假言推理
∀xQ(x)                  由 3-6 全称推广

例 2：化简 ¬∀x(P(x) -> Q(x))。

解析：

¬∀x(P(x) -> Q(x))
≡ ∃x ¬(P(x) -> Q(x))
≡ ∃x ¬(¬P(x) ∨ Q(x))
≡ ∃x(P(x) ∧ ¬Q(x))

含义：存在某个对象满足 P 但不满足 Q。

6. 自测题

化简 ¬∃x(P(x) ∧ Q(x))。
判断 ∀x(P(x) ∨ Q(x)) 是否等价于 ∀xP(x) ∨ ∀xQ(x)。
由 ∀xP(x) 能否推出 ∃xP(x)？需要什么前提？
证明 ∀x(P(x) -> Q(x)), ∃xP(x) ⊢ ∃xQ(x)。

十、综合易错点

∈ 表示元素属于集合，⊆ 表示集合包含关系。例：若 A={1,{2}}，则 {2} ∈ A，但 {2} ⊆ A 不成立。
P(A) 是集合的集合。若 A={1,2}，则 P(A)={∅,{1},{2},{1,2}}。
A × B 与 B × A 一般不同，除非元素结构刚好相同且顺序不影响讨论。
反对称不是“不对称”。恒等关系既对称又反对称。
传递性要检查所有 aRb 和 bRc 组合，不是只看是否有三角形。
等价关系对应划分；偏序关系对应“可比较的顺序结构”。
极大元可以有多个，最大元若存在只能有一个。
欧拉图看边是否能一次走完，关键是顶点度数。
哈密顿图看点是否能一次走完，通常需要构造或用充分条件。
p -> q 不表示因果，只表示真值关系；当前件假时蕴含式为真。
不能由 p -> q 和 q 推出 p。
不能由 p -> q 和 ¬p 推出 ¬q。
全称命题翻译常用 ->，存在命题翻译常用 ∧。
¬∀ 变 ∃¬，¬∃ 变 ∀¬。
存在实例化引入的常元必须是新的，不能偷换成已有对象。

十一、期末题型与答题模板

1. 集合证明题

模板：

证明 A = B。
任取 x ∈ A，推出 x ∈ B，所以 A ⊆ B。
任取 x ∈ B，推出 x ∈ A，所以 B ⊆ A。
因此 A = B。

如果题目适合公式法，优先使用集合运算律，步骤更简洁。

2. 关系性质判定题

模板：

自反：检查所有 (a,a) 是否都属于 R。
对称：检查每个 (a,b) 是否都有 (b,a)。
反对称：检查不同元素 a,b 是否存在双向关系。
传递：检查若 (a,b),(b,c) ∈ R，是否必有 (a,c) ∈ R。
结论：列出满足和不满足的性质。

3. 等价关系与偏序题

等价关系模板：

分别证明自反、对称、传递。
若三者都成立，则为等价关系。
再按 [a] = {x | xRa} 求等价类。

偏序关系模板：

分别证明自反、反对称、传递。
若三者都成立，则为偏序关系。
画哈斯图时去自环、去传递边、保留覆盖关系。

4. 欧拉图判定题

模板：

先说明图是否连通。
统计奇度顶点个数。
0 个奇度顶点：有欧拉回路。
2 个奇度顶点：有欧拉通路但无欧拉回路。
超过 2 个奇度顶点：无欧拉通路。

5. 哈密顿图判定题

模板：

若能构造经过所有顶点一次的回路，则说明是哈密顿图。
若用充分条件，先说明图是 n ≥ 3 的简单图，再验证最小度数或 Ore 条件。
若证明不存在，常用反证或割点/连通分量思想。

6. 命题逻辑等值演算题

模板：

先消去 -> 和 <->。
再用德摩根律把否定推进到命题变元前。
再用分配律化为析取范式或合取范式。
最后用吸收律、幂等律、矛盾律化简。

7. 一阶逻辑翻译题

模板：

确定论域。
定义谓词。
判断是全称句还是存在句。
全称句通常写成 ∀x(条件 -> 结论)。
存在句通常写成 ∃x(条件 ∧ 结论)。
检查量词辖域和变量是否一致。

十二、综合自测题

设 A={1,2,3}，B={2,3,4}，求 A ∪ B、A ∩ B、A - B。
设 A={a,b}，写出 P(A)。
设 R={(1,1),(2,2),(3,3),(1,2),(2,1)} 是 {1,2,3} 上的关系，判断它是否为等价关系，并求等价类。
在 {1,2,3,6} 上按整除关系 | 排序，求最大元和最小元。
判断 f: R -> R，f(x)=2x-3 是否为双射。
一个连通无向图有 6 个顶点，度数为 2,2,2,2,4,4，判断是否有欧拉回路。
一个连通无向图有 6 个顶点，度数为 1,1,2,2,2,4，判断是否有欧拉通路和欧拉回路。
化简命题公式 ¬(p -> q)。
判断推理 p -> q, q -> r, p ⊢ r 是否有效。
将“所有喜欢数学的学生都喜欢离散数学”翻译为一阶逻辑公式。
化简 ¬∃x(P(x) ∨ Q(x))。
判断 ∃x(P(x) ∧ Q(x)) 与 ∃xP(x) ∧ ∃xQ(x) 是否等价。
一棵树有 12 个顶点，求边数和度数和。
连通平面图有 10 个顶点、15 条边，求面数。
判断 K_{3,3} 是否为平面图，并说明理由。
某加权连通无向图所有顶点度数均为偶数，所有边权和为 80，求中国邮递员问题最优总长度。
说明中国邮递员问题和 TSP 的核心区别。
设 S 是图 G=(V,E) 的点独立集，判断 V-S 是否一定是点覆盖集。
判断“极大匹配一定是最大匹配”是否正确。
一个二部图若含有奇回路，是否可能成立？
简单图最大度数为 5，根据 Vizing 定理，边色数可能取哪些值？

十三、答案与解析

1. 各章自测题答案

集合：

|P(A)| = 2^3 = 8。
成立，因为 {∅,{1}} 的一个元素就是 ∅。
A ∩ (B - C) = A ∩ (B ∩ C̄) = (A ∩ B) ∩ C̄ = (A ∩ B) - C。
一定成立。若 x ∈ A ∩ C，则 x ∈ A 且 x ∈ C；由 A ⊆ B 得 x ∈ B，所以 x ∈ B ∩ C。

二元关系：

传递。因为有 (1,2) 和 (2,3)，且 (1,3) 已在 R 中；其他组合也不破坏传递性。
恒等关系既对称又反对称。
是等价关系。自反：a-a=0 是偶数；对称：若 a-b 是偶数，则 b-a 是偶数；传递：若 a-b、b-c 是偶数，则 a-c 是偶数。
最大元是 {1,2}，最小元是 ∅。

函数：

f(x)=x^2 在 R -> R 上不是单射，因为 f(1)=f(-1)；也不是满射，因为负数没有原像。
不可能，因为 |A|>|B|。
是双射。双射的复合仍为双射。
必须是双射。

图的基本概念：

不可能。无向图度数和必须为偶数。
K_6 有 6·5/2=15 条边。
入度之和为 8。
不违反。奇度顶点个数为 4，是偶数。

欧拉图与哈密顿图：

存在欧拉回路。
不存在欧拉通路，因为奇度顶点超过两个。
不一定，还需要相关连通性条件。
不一定。Dirac 条件是充分条件，不是必要条件。

命题逻辑：

¬p ∧ ¬q。
重言式。
p。
¬p ∨ q。

命题逻辑推理：

无效，这是肯定后件谬误。
由 p ∧ q 合取消去得 p 和 q，再合取引入得 q ∧ p。
有效，这是拒取式。
假设 p，由 p -> q 得 q，由 q -> r 得 r，所以 p -> r。

一阶逻辑基本概念：

可写为 ∀x(Even(x) -> DivisibleBy2(x))。
可写为 ∃x(Student(x) ∧ LikesDiscreteMath(x))，若论域已限定为学生，则可写为 ∃x LikesDiscreteMath(x)。
等价。
不适合。应写为 ∃x(P(x) ∧ Q(x))。

一阶逻辑等值演算和推理：

¬∃x(P(x) ∧ Q(x)) ≡ ∀x¬(P(x) ∧ Q(x)) ≡ ∀x(¬P(x) ∨ ¬Q(x))。
一般不等价。
若论域非空，则可以推出；若允许空论域，则不能推出。
由 ∃xP(x) 取新常元 c 使 P(c)；由 ∀x(P(x)->Q(x)) 得 P(c)->Q(c)；推出 Q(c)；由存在推广得 ∃xQ(x)。

2. 综合自测题答案

A ∪ B={1,2,3,4}，A ∩ B={2,3}，A-B={1}。
P(A)={∅,{a},{b},{a,b}}。
是等价关系，等价类为 {1,2} 和 {3}。
最小元为 1，最大元为 6。
是双射。单射：2a-3=2b-3 推出 a=b；满射：任意 y ∈ R，取 x=(y+3)/2，则 f(x)=y。
有欧拉回路，因为连通且所有顶点度数为偶数。
有欧拉通路但无欧拉回路，因为恰有两个奇度顶点。
¬(p -> q) ≡ ¬(¬p ∨ q) ≡ p ∧ ¬q。
有效。由 p 和 p -> q 得 q，再由 q 和 q -> r 得 r。
设 M(x) 表示 x 喜欢数学，D(x) 表示 x 喜欢离散数学，论域为学生，则公式为 ∀x(M(x) -> D(x))。若论域不是学生，还应写为 ∀x((Student(x) ∧ M(x)) -> D(x))。
¬∃x(P(x) ∨ Q(x)) ≡ ∀x¬(P(x) ∨ Q(x)) ≡ ∀x(¬P(x) ∧ ¬Q(x))。
一般不等价。左边要求同一个对象同时满足 P 和 Q；右边只要求存在某个对象满足 P，存在某个对象满足 Q，可以不是同一个对象。
边数为 12-1=11，度数和为 2×11=22。
由欧拉公式 v-e+f=2，得 10-15+f=2，所以 f=7。
K_{3,3} 不是平面图。它是无三角形简单图，若平面则应满足 e≤2v-4；但 v=6、e=9，而 2v-4=8，矛盾。
最优总长度为 80。因为所有顶点度数均为偶数，图存在欧拉回路，邮递员不需要重复额外边。
中国邮递员问题关注“边”，要求每条边至少走一次并回到起点；TSP 关注“顶点”，要求每个顶点恰好访问一次并回到起点。
一定是。若存在一条边两个端点都不在 V-S 中，则两个端点都在 S 中，这与 S 是独立集矛盾。
不正确。极大匹配只表示不能再加入边，最大匹配要求边数最多；极大匹配可能不是最大匹配。
不可能。二部图的充要判定之一是不存在奇回路。
根据 Vizing 定理，简单图满足 Δ≤χ'(G)≤Δ+1，所以边色数可能为 5 或 6。

十四、考前快速检查表

集合：会用双包含法；熟悉德摩根律、分配律、差集公式。
关系：会判定自反、对称、反对称、传递；会求等价类；会读哈斯图。
函数：能区分定义域、陪域、值域；会判定单射、满射、双射。
图论：记住握手定理；会数奇度顶点；能区分欧拉和哈密顿。
图论专题：会用树的 m=n-1、平面图欧拉公式、最短路算法适用条件、匹配/覆盖/独立/着色的基本定义。
命题逻辑：会消去 ->、<->；会用真值表和等值演算；掌握常用推理规则。
一阶逻辑：会翻译全称句和存在句；熟练使用 ¬∀ ≡ ∃¬ 和 ¬∃ ≡ ∀¬。

本文由作者按照 CC BY 4.0 进行授权