离散数学速查表

本文档汇总离散数学的核心概念、公式和定理，方便快速查阅。

数理逻辑

命题联结词

联结词	符号	读法	真值条件
否定	$\neg p$	非 p	$\neg T = F$, $\neg F = T$
合取	$p \land q$	p 且 q	仅当 $p = T$ 且 $q = T$ 时为真
析取	$p \lor q$	p 或 q	仅当 $p = F$ 且 $q = F$ 时为假
蕴含	$p \to q$	如果 p 则 q	仅当 $p = T$ 且 $q = F$ 时为假
等价	$p \leftrightarrow q$	p 当且仅当 q	$p$ 和 $q$ 同真或同假
异或	$p \oplus q$	p 异或 q	$p$ 和 $q$ 恰一为真

逻辑等价式

德摩根律：

$\neg(p \land q) \equiv \neg p \lor \neg q$

$\neg(p \lor q) \equiv \neg p \land \neg q$

蕴含等价式：

$p \to q \equiv \neg p \lor q$

逆否命题：

$p \to q \equiv \neg q \to \neg p$

量词否定：

$\neg \forall x P(x) \equiv \exists x \neg P(x)$

$\neg \exists x P(x) \equiv \forall x \neg P(x)$

范式

文字：命题变量或其否定（$p$ 或 $\neg p$）

子句：文字的析取（$p \lor \neg q \lor r$）

CNF（合取范式）：子句的合取 $(p \lor \neg q) \land (\neg p \lor r)$

DNF（析取范式）：合取项的析取 $(p \land \neg q) \lor (\neg p \land r)$

CNF 转换步骤：

1. 消除蕴含：$p \to q \equiv \neg p \lor q$
2. 德摩根律将否定内移
3. 消除双重否定
4. 分配律：$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

前束范式（PNF）

定义：所有量词都在公式开头的形式

$Q_1 x_1 Q_2 x_2 \cdots Q_n x_n \, B$

其中 $Q_i \in \lbrace\forall, \exists\rbrace$，$B$ 不含量词

转换步骤：

1. 消除蕴含和等价
2. 将否定内移（使用量词否定规则）
3. 标准化变量（重命名避免冲突）
4. 将量词移到前面

量词移动规则（$x$ 不在 $A$ 中自由出现）：

$A \land \exists x \, B(x) \equiv \exists x \, (A \land B(x))$

$A \lor \forall x \, B(x) \equiv \forall x \, (A \lor B(x))$

$\forall x \forall y \, P(x,y) \equiv \forall y \forall x \, P(x,y)$

$\exists x \exists y \, P(x,y) \equiv \exists y \exists x \, P(x,y)$

注意：$\forall x \exists y \, P(x,y) \not\equiv \exists y \forall x \, P(x,y)$

谓词逻辑等价式

分配性：

$\forall x \, (P(x) \land Q(x)) \equiv \forall x \, P(x) \land \forall x \, Q(x)$

$\exists x \, (P(x) \lor Q(x)) \equiv \exists x \, P(x) \lor \exists x \, Q(x)$

不可分配：

$\forall x \, (P(x) \lor Q(x)) \not\equiv \forall x \, P(x) \lor \forall x \, Q(x)$

$\exists x \, (P(x) \land Q(x)) \not\equiv \exists x \, P(x) \land \exists x \, Q(x)$

谓词逻辑推理规则

规则	形式	说明
全称实例化	$\forall x P(x) \vdash P(c)$	从全称推出具体实例
全称推广	$P(c) \vdash \forall x P(x)$	$c$ 必须是任意元素
存在实例化	$\exists x P(x) \vdash P(c^*)$	$c^*$ 必须是新符号
存在推广	$P(c) \vdash \exists x P(x)$	从具体推出存在

注意：先存在实例化，后全称实例化

Skolem化

目的：消除存在量词，得到只含全称量词的公式

Skolem常量：存在量词前无全称量词时使用

原公式	Skolem化结果
$\exists x \, P(x)$	$P(c)$
$\forall y \exists x \, P(x, y)$	$\forall y \, P(f(y), y)$
$\exists x \forall y \exists z \, P(x, y, z)$	$\forall y \, P(c, y, f(y))$

重要性质：Skolem化保持可满足性，但不保持逻辑等价

消解原理

消解规则：

$\frac{C_1 \lor L \quad C_2 \lor \neg L}{C_1 \lor C_2}$

消解反驳步骤：

1. 否定结论
2. 转换为CNF（命题逻辑）或Skolem CNF（一阶逻辑）
3. 应用消解规则推导
4. 若推出空子句 $\square$，则原命题成立

一阶逻辑消解：需要合一（Unification）算法

合一示例：$P(x, f(y))$ 和 $P(a, f(b))$ 合一为 $P(a, f(b))$，替换 $\{x \mapsto a, y \mapsto b\}$

证明方法

方法	适用场景
直接证明	证明 $p \to q$：假设 $p$，推导 $q$
反证法	假设结论为假，导出矛盾
逆否证明	证明 $\neg q \to \neg p$ 等价于 $p \to q$
数学归纳法	与自然数相关的命题
构造性证明	存在性命题，直接构造对象
分情况证明	命题涉及多种互斥情况

集合论

集合运算

运算	定义
并集	$A \cup B = \{x \mid x \in A \lor x \in B\}$
交集	$A \cap B = \{x \mid x \in A \land x \in B\}$
差集	$A - B = \{x \mid x \in A \land x \notin B\}$
补集	$\overline{A} = U - A$
对称差	$A \triangle B = (A - B) \cup (B - A)$

集合恒等式

德摩根律：

$\overline{A \cup B} = \overline{A} \cap \overline{B}$

$\overline{A \cap B} = \overline{A} \cup \overline{B}$

分配律：

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

容斥原理：

$|A \cup B| = |A| + |B| - |A \cap B|$

笛卡尔积与幂集

• 笛卡尔积：$A \times B = \{(a, b) \mid a \in A, b \in B\}$
• 幂集：$\mathcal{P}(A) = \{S \mid S \subseteq A\}$，$|\mathcal{P}(A)| = 2^{|A|}$

函数与关系

函数类型

类型	定义	条件
单射	不同输入映射不同输出	$f(x_1) = f(x_2) \Rightarrow x_1 = x_2$
满射	值域等于陪域	$\forall y \in Y, \exists x: f(x) = y$
双射	既是单射又是满射	一一对应

关系的性质

性质	定义
自反性	$\forall x: xRx$
对称性	$xRy \Rightarrow yRx$
反对称性	$xRy \land yRx \Rightarrow x = y$
传递性	$xRy \land yRz \Rightarrow xRz$

特殊关系

• 等价关系：自反 + 对称 + 传递
• 偏序关系：自反 + 反对称 + 传递

组合数学

排列与组合

概念	公式	说明
排列	$P(n, r) = \frac{n!}{(n-r)!}$	有序选取
组合	$C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$	无序选取
圆排列	$(n-1)!$	环状排列
可重组合	$C(n+r-1, r)$	允许重复选取

二项式定理

$(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$

常用等式：

$\sum_{k=0}^{n} \binom{n}{k} = 2^n$

$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$

鸽巢原理

• 基本形式：$n+1$ 个物品放入 $n$ 个盒子，至少一个盒子有 $\geq 2$ 个物品
• 一般形式：$n$ 个物品放入 $m$ 个盒子，至少一个盒子有 $\geq \lceil n/m \rceil$ 个物品

递推关系

斐波那契数列：$F_n = F_{n-1} + F_{n-2}$，$F_0 = 0$，$F_1 = 1$

通项公式：

$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

图论

基本概念

概念	定义
阶（Order）	顶点数 $
规模（Size）	边数 $
度数（Degree）	与顶点关联的边数
握手定理	$\sum_{v} \deg(v) = 2\vert E\vert$

特殊图

图类型	描述	边数
完全图 $K_n$	任意两点都有边	$\frac{n(n-1)}{2}$
二分图	顶点分成两部分，边只连接两部分之间	—
完全二分图 $K_{m,n}$	两部分间所有点对都有边	$mn$
树	连通无环图	$n-1$

图的遍历

算法	数据结构	应用
DFS	栈	路径搜索、拓扑排序、检测环
BFS	队列	最短路径（无权）、层次遍历

最短路径算法

算法	适用图	时间复杂度
BFS	无权图	$O(V + E)$
Dijkstra	非负权重	$O((V + E) \log V)$
Floyd-Warshall	任意权重	$O(V^3)$

最小生成树

算法	策略	时间复杂度
Prim	从顶点扩展	$O(E \log V)$
Kruskal	按边权排序	$O(E \log E)$

欧拉路径与哈密顿路径

欧拉路径判定条件：

情况	条件
欧拉回路	连通且所有顶点度数为偶数
欧拉路径（非回路）	连通且恰有 2 个奇数度顶点

Hierholzer 算法：$O(E)$ 时间复杂度

哈密顿路径：判定是 NP 完全问题

定理	条件
Dirac 定理	每个顶点度数 $\geq n/2$ 则存在哈密顿回路
Ore 定理	任意不相邻顶点 $u, v$ 满足 $\deg(u) + \deg(v) \geq n$

平面图

欧拉公式：$V - E + F = 2$

边的上界：简单连通平面图 $E \leq 3V - 6$

四色定理：平面图最多需要 4 种颜色着色

Kuratowski 定理：平面图 $\Leftrightarrow$ 不含 $K_5$ 或 $K_{3,3}$ 的细分

树

树的等价定义

以下命题等价：

1. 连通且无环
2. 连通且 $|E| = |V| - 1$
3. 无环且 $|E| = |V| - 1$
4. 任意两点间有唯一路径

二叉树性质

• 第 $i$ 层最多 $2^i$ 个节点
• 深度 $k$ 的二叉树最多 $2^{k+1} - 1$ 个节点
• 叶子数 $n_0$ = 度为 2 的节点数 $n_2$ + 1

遍历序列

遍历	顺序	用途
前序	根→左→右	复制树、前缀表达式
中序	左→根→右	BST 排序输出、中缀表达式
后序	左→右→根	删除树、后缀表达式
层次	逐层从左到右	层次遍历

Cayley 公式

$n$ 个标号顶点的树有 $n^{n-2}$ 种。

数论

整除与同余

概念	记号	定义
整除	$a \mid b$	$\exists k: b = ak$
同余	$a \equiv b \pmod{m}$	$m \mid (a - b)$

GCD 与 LCM

$\gcd(a, b) \times \text{lcm}(a, b) = |ab|$

Bezout 定理：存在整数 $x, y$ 使得 $ax + by = \gcd(a, b)$

欧拉函数

$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

特殊值：$\phi(p) = p - 1$（$p$ 为素数）

重要定理

欧拉定理：若 $\gcd(a, n) = 1$，则 $a^{\phi(n)} \equiv 1 \pmod{n}$

费马小定理：若 $p$ 为素数且 $p \nmid a$，则 $a^{p-1} \equiv 1 \pmod{p}$

威尔逊定理：$n > 1$ 是素数当且仅当 $(n-1)! \equiv -1 \pmod{n}$

中国剩余定理：若 $m_1, \ldots, m_k$ 两两互质，则同余方程组有唯一解。

模逆元

$a$ 模 $m$ 的逆元存在当且仅当 $\gcd(a, m) = 1$。

当 $p$ 为素数时：$a^{-1} \equiv a^{p-2} \pmod{p}$

算法基础

渐近记号

记号	定义	含义
$O(g)$	$\exists C, k: \|f(n)\| \leq C\|g(n)\|, \forall n > k$	上界
$\Omega(g)$	$\exists C, k: \|f(n)\| \geq C\|g(n)\|, \forall n > k$	下界
$\Theta(g)$	$f$ 是 $O(g)$ 且 $f$ 是 $\Omega(g)$	精确阶

常见复杂度级别

$1 < \log n < \sqrt{n} < n < n \log n < n^2 < n^3 < 2^n < n! < n^n$

复杂度层次

复杂度	名称	典型算法
$O(1)$	常数时间	数组访问
$O(\log n)$	对数时间	二分搜索
$O(n)$	线性时间	线性搜索
$O(n \log n)$	线性对数	快速排序
$O(n^2)$	平方时间	冒泡排序
$O(2^n)$	指数时间	子集枚举

循环不变式

证明正确性的三步骤：

1. 初始化：循环开始前不变式成立
2. 保持性：迭代过程中不变式保持成立
3. 终止性：循环终止时不变式提供正确性证明

布尔代数

布尔运算真值表

与运算（AND）：

$x$	$y$	$x \land y$
0	0	0
0	1	0
1	0	0
1	1	1

或运算（OR）：

$x$	$y$	$x \lor y$
0	0	0
0	1	1
1	0	1
1	1	1

非运算（NOT）：

$x$	$\neg x$
0	1
1	0

布尔代数定律

交换律：$x \land y = y \land x$，$x \lor y = y \lor x$

分配律：$x \land (y \lor z) = (x \land y) \lor (x \land z)$

德摩根律：

$\neg(x \land y) = \neg x \lor \neg y$

$\neg(x \lor y) = \neg x \land \neg y$

吸收律：$x \land (x \lor y) = x$，$x \lor (x \land y) = x$

双重否定：$\neg \neg x = x$

标准形式

析取范式（DNF）：最小项的析取（积之和）

合取范式（CNF）：最大项的合取（和之积）

逻辑门

门	符号	函数
AND	$\land$	$x \land y$
OR	$\lor$	$x \lor y$
NOT	$\neg$	$\neg x$
NAND	$\uparrow$	$\neg(x \land y)$
NOR	$\downarrow$	$\neg(x \lor y)$
XOR	$\oplus$	$x \oplus y$

完备性：{NAND} 和 {NOR} 都是功能完备的门集合

离散概率

概率基本公式

条件概率：

$P(A | B) = \frac{P(A \cap B)}{P(B)}$

乘法公式：

$P(A \cap B) = P(A) \cdot P(B | A)$

全概率公式（$B_1, \ldots, B_n$ 为划分）：

$P(A) = \sum_{i=1}^{n} P(B_i) \cdot P(A | B_i)$

贝叶斯定理：

$P(B_i | A) = \frac{P(B_i) \cdot P(A | B_i)}{\sum_{j} P(B_j) \cdot P(A | B_j)}$

独立性

两事件独立：$P(A \cap B) = P(A) \cdot P(B)$

等价于 $P(A | B) = P(A)$

期望与方差

期望：$E[X] = \sum_x x \cdot P(X = x)$

方差：$\text{Var}(X) = E[X^2] - (E[X])^2$

性质：

• $E[aX + b] = aE[X] + b$
• $\text{Var}(aX + b) = a^2 \text{Var}(X)$
• $E[X + Y] = E[X] + E[Y]$
• 若 $X, Y$ 独立：$E[XY] = E[X] \cdot E[Y]$，$\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y)$

常见离散分布

分布	PMF	期望	方差
伯努利 $Bern(p)$	$P(X=1)=p, P(X=0)=1-p$	$p$	$p(1-p)$
二项 $Bin(n,p)$	$\binom{n}{k}p^k(1-p)^{n-k}$	$np$	$np(1-p)$
几何 $Geo(p)$	$(1-p)^{k-1}p$	$\frac{1}{p}$	$\frac{1-p}{p^2}$
泊松 $Poi(\lambda)$	$\frac{\lambda^k e^{-\lambda}}{k!}$	$\lambda$	$\lambda$

极限定理

大数定律：$\bar{X}_n \xrightarrow{P} E[X]$

中心极限定理：$\frac{\bar{X}_n - \mu}{\sigma/\sqrt{n}} \xrightarrow{d} N(0, 1)$

常用算法复杂度

算法	时间复杂度
欧几里得算法（GCD）	$O(\log(\min(a, b)))$
快速幂	$O(\log n)$
埃拉托斯特尼筛法	$O(n \log \log n)$
DFS/BFS	$O(V + E)$
Dijkstra	$O((V + E) \log V)$
Prim/Kruskal	$O(E \log V)$
线性搜索	$O(n)$
二分搜索	$O(\log n)$
归并排序	$O(n \log n)$

常用数学公式速查

求和公式

等差数列求和：

$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$

等差数列一般形式：

$\sum_{k=0}^{n-1} (a + kd) = na + \frac{n(n-1)d}{2}$

等比数列求和：

$\sum_{k=0}^{n} r^k = \frac{r^{n+1} - 1}{r - 1} \quad (r \neq 1)$

平方和：

$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$

立方和：

$\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$

对数恒等式

$\log_a(xy) = \log_a x + \log_a y$

$\log_a(x/y) = \log_a x - \log_a y$

$\log_a(x^n) = n \log_a x$

$\log_a x = \frac{\log_b x}{\log_b a}$（换底公式）

阶乘与斯特林公式

$n! = n \times (n-1) \times \cdots \times 2 \times 1$

斯特林近似：

$n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$

常见错误与陷阱

逻辑推理中的常见错误

1. 肯定后件：$p \to q, q \vdash p$（错误）
2. 否定前件：$p \to q, \neg p \vdash \neg q$（错误）
3. 混淆充分与必要：$p \to q$ 中 $p$ 是 $q$ 的充分条件，$q$ 是 $p$ 的必要条件

集合论中的常见错误

1. 混淆 $\in$ 和 $\subseteq$：$x \in A$ 与 $x \subseteq A$ 不同
2. 忽略空集：空集是任何集合的子集
3. 幂集大小：$|\mathcal{P}(A)| = 2^{|A|}$，不是 $2|A|$

组合数学中的常见错误

1. 排列与组合混淆：排列考虑顺序，组合不考虑顺序
2. 重复计数：使用乘法原理时忘记检查步骤是否独立
3. 遗漏情况：分类讨论时遗漏某些情况

图论中的常见错误

1. 混淆度数与边数：握手定理 $\sum \deg(v) = 2|E|$
2. 欧拉路径条件：度数为奇数的顶点个数必须是 0 或 2
3. 平面图边数上界：$E \leq 3V - 6$ 仅适用于简单连通平面图

概率论中的常见错误

1. 条件概率方向：$P(A|B) \neq P(B|A)$
2. 独立性误判：$P(A \cap B) = 0$ 不意味着独立
3. 贝叶斯定理应用：分母必须是所有情况的总和