离散数学

离散数学（Discrete Mathematics）研究的是离散（而非连续）的数学结构，是计算机科学的数学基础。与微积分和线性代数关注连续对象不同，离散数学处理的是有限或可数的对象：集合、图、组合结构、逻辑命题等。

离散数学在 AI 中有广泛的应用：图论是图神经网络（GNN） 的理论基础，组合数学支撑着搜索与优化算法，布尔代数是SAT 求解和逻辑推理的核心工具。本笔记涵盖集合论、关系与函数、图论、组合数学、布尔代数和递推关系等核心主题。

1. 集合论基础

1.1 集合运算

设 $A, B$ 为全集 $U$ 的子集：

运算	记号	定义
并集	$A \cup B$	$\{x \mid x \in A \text{ 或 } x \in B\}$
交集	$A \cap B$	$\{x \mid x \in A \text{ 且 } x \in B\}$
差集	$A - B$	$\{x \mid x \in A \text{ 且 } x \notin B\}$
补集	$\overline{A}$	$\{x \mid x \in U \text{ 且 } x \notin A\}$
对称差	$A \oplus B$	$(A - B) \cup (B - A)$

De Morgan 律：

\[ \overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B} \]

1.2 幂集与笛卡尔积

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

集合的基数

有限集的基数就是元素个数。
$\mathbb{N}$（自然数）是可数无穷，$\mathbb{R}$（实数）是不可数无穷。
Cantor 对角线论证证明了 $|\mathbb{R}| > |\mathbb{N}|$。

2. 关系与函数

2.1 关系的性质

设 $R$ 是集合 $A$ 上的二元关系：

性质	定义	示例
自反性	$\forall a \in A,\; (a, a) \in R$	$\leq$ 是自反的
对称性	$(a, b) \in R \Rightarrow (b, a) \in R$	"是朋友"是对称的
反对称性	$(a, b) \in R \land (b, a) \in R \Rightarrow a = b$	$\leq$ 是反对称的
传递性	$(a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R$	$<$ 是传递的

2.2 等价关系与偏序

等价关系：满足自反性、对称性和传递性的关系。等价关系将集合划分为若干等价类。 - 例：模 $n$ 同余 $a \equiv b \pmod{n}$ 是 $\mathbb{Z}$ 上的等价关系。
偏序关系：满足自反性、反对称性和传递性的关系，记为 $(A, \preceq)$。 - 例：$(\mathcal{P}(S), \subseteq)$ 是偏序集。
全序关系：偏序关系中，任意两个元素都可比较。 - 例：$(\mathbb{R}, \leq)$ 是全序集。

2.3 函数

函数 $f: A \to B$ 是一种特殊的关系，满足 $\forall a \in A$，存在唯一的 $b \in B$ 使得 $(a, b) \in f$。

类型	定义
单射（Injection）	$f(a_1) = f(a_2) \Rightarrow a_1 = a_2$
满射（Surjection）	$\forall b \in B,\; \exists a \in A,\; f(a) = b$
双射（Bijection）	既是单射又是满射

3. 图论基础

3.1 图的基本概念

图 $G = (V, E)$ 由顶点集 $V$ 和边集 $E$ 构成。

概念	定义
无向图	边 $\{u, v\}$ 无方向
有向图	边 $(u, v)$ 有方向
度（degree）	无向图中与顶点关联的边数，$\sum_{v \in V} \deg(v) = 2
邻接矩阵	$A_{ij} = 1$ 当且仅当 $(i, j) \in E$
邻接表	每个顶点存储其邻居列表

3.2 连通性

连通图：任意两个顶点之间存在路径。
强连通（有向图）：任意两个顶点之间存在双向路径。
连通分量：最大连通子图。可用 BFS/DFS 在 $O(V + E)$ 时间内求解。

3.3 特殊路径与回路

类型	条件	判定
欧拉路径	经过每条边恰好一次	恰好有 0 或 2 个奇数度顶点
欧拉回路	欧拉路径 + 起终点相同	所有顶点度数为偶数
哈密顿路径	经过每个顶点恰好一次	NP-完全问题，无多项式判定
哈密顿回路	哈密顿路径 + 起终点相同	NP-完全问题

3.4 图着色与平面图

图着色：用最少的颜色给顶点着色，使相邻顶点颜色不同。所需最少颜色数称为色数 $\chi(G)$。
四色定理：任何平面图的色数不超过 4。
平面图：可以在平面上画出使得边不交叉的图。欧拉公式：$V - E + F = 2$（$F$ 为面的个数）。

4. 组合数学

4.1 排列与组合

排列：从 $n$ 个元素中选 $r$ 个，考虑顺序：$P(n, r) = \frac{n!}{(n-r)!}$
组合：从 $n$ 个元素中选 $r$ 个，不考虑顺序：$\binom{n}{r} = \frac{n!}{r!(n-r)!}$

4.2 二项式定理

\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k \]

Pascal 恒等式：$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

4.3 容斥原理

\[ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap \cdots \cap A_n| \]

应用示例：计算 $[1, 1000]$ 中不被 2、3、5 整除的整数个数。

4.4 鸽巢原理

若将 $n+1$ 个物体放入 $n$ 个盒子，则至少有一个盒子包含两个或以上物体。

推广形式：若将 $n$ 个物体放入 $k$ 个盒子，则至少有一个盒子包含 $\lceil n/k \rceil$ 个物体。

4.5 生成函数入门

普通生成函数（OGF）：序列 $\{a_n\}$ 的 OGF 为 $G(x) = \sum_{n=0}^{\infty} a_n x^n$。

序列	生成函数
$1, 1, 1, \dots$	$\frac{1}{1-x}$
$1, 2, 3, \dots$	$\frac{1}{(1-x)^2}$
$\binom{n}{k}$ 对应的行	$(1+x)^n$
Fibonacci 数列	$\frac{x}{1-x-x^2}$

5. 布尔代数

5.1 布尔运算

布尔代数定义在集合 $\{0, 1\}$ 上，基本运算如下：

运算	符号	真值表（部分）
与（AND）	$a \land b$	$1 \land 1 = 1$，其余为 $0$
或（OR）	$a \lor b$	$0 \lor 0 = 0$，其余为 $1$
非（NOT）	$\neg a$	$\neg 0 = 1$，$\neg 1 = 0$
异或（XOR）	$a \oplus b$	相同为 $0$，不同为 $1$

5.2 范式

析取范式（DNF）：由合取子句的析取构成，如 $(A \land B) \lor (\neg A \land C)$
合取范式（CNF）：由析取子句的合取构成，如 $(A \lor B) \land (\neg A \lor C)$

任何布尔函数都可以转化为 DNF 或 CNF。CNF 是 SAT 求解器的标准输入格式。

5.3 逻辑电路

布尔代数直接对应数字逻辑电路：

AND 门、OR 门、NOT 门：基本逻辑门
NAND 门：功能完备，任何布尔函数都可以仅用 NAND 门实现
半加器：$S = A \oplus B$，$C = A \land B$
全加器：$S = A \oplus B \oplus C_{in}$，$C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B))$

6. 递推关系

6.1 线性递推

线性齐次递推的一般形式：

\[ a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} \]

求解方法：特征方程 $x^k - c_1 x^{k-1} - \cdots - c_k = 0$，根据特征根构造通解。

示例：Fibonacci 数列 $F_n = F_{n-1} + F_{n-2}$

特征方程 $x^2 - x - 1 = 0$，特征根 $\phi = \frac{1+\sqrt{5}}{2}$，$\hat{\phi} = \frac{1-\sqrt{5}}{2}$

\[ F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}} \]

6.2 主定理（Master Theorem）

对于递推 $T(n) = aT(n/b) + f(n)$，其中 $a \geq 1$，$b > 1$：

情形	条件	结果
Case 1	$f(n) = O(n^{\log_b a - \epsilon})$	$T(n) = \Theta(n^{\log_b a})$
Case 2	$f(n) = \Theta(n^{\log_b a} \log^k n)$	$T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$
Case 3	$f(n) = \Omega(n^{\log_b a + \epsilon})$	$T(n) = \Theta(f(n))$

示例：归并排序 $T(n) = 2T(n/2) + \Theta(n)$，$a=2, b=2, \log_b a = 1$，属于 Case 2（$k=0$），故 $T(n) = \Theta(n \log n)$。

7. 离散数学与 AI 的联系

离散数学领域	AI 应用
图论	图神经网络（GCN, GAT, GraphSAGE）、知识图谱、社交网络分析
组合优化	搜索算法（A*、蒙特卡洛树搜索）、调度问题、NP-hard 近似
布尔代数	SAT 求解器、约束满足问题（CSP）、形式化验证
集合论 / 关系	数据库关系模型、类型系统
递推 / 生成函数	算法复杂度分析、动态规划状态转移
概率组合	随机算法、哈希函数分析、布隆过滤器

图论 → GNN

图神经网络中的消息传递机制可以用图论语言描述：每个节点聚合其邻居的特征（邻接关系），更新自身表示。GNN 的表达能力与 Weisfeiler-Leman 图同构检验密切相关。

参考资料

Rosen, Discrete Mathematics and Its Applications
Diestel, Graph Theory
Graham, Knuth & Patashnik, Concrete Mathematics
MIT 6.042J: Mathematics for Computer Science

运算	记号	定义
并集	\(A \cup B\)	\(\{x \mid x \in A \text{ 或 } x \in B\}\)
交集	\(A \cap B\)	\(\{x \mid x \in A \text{ 且 } x \in B\}\)
差集	\(A - B\)	\(\{x \mid x \in A \text{ 且 } x \notin B\}\)
补集	\(\overline{A}\)	\(\{x \mid x \in U \text{ 且 } x \notin A\}\)
对称差	\(A \oplus B\)	\((A - B) \cup (B - A)\)

序列	生成函数
\(1, 1, 1, \dots\)	\(\frac{1}{1-x}\)
\(1, 2, 3, \dots\)	\(\frac{1}{(1-x)^2}\)
\(\binom{n}{k}\) 对应的行	\((1+x)^n\)
Fibonacci 数列	\(\frac{x}{1-x-x^2}\)

运算	符号	真值表（部分）
与（AND）	\(a \land b\)	\(1 \land 1 = 1\)，其余为 \(0\)
或（OR）	\(a \lor b\)	\(0 \lor 0 = 0\)，其余为 \(1\)
非（NOT）	\(\neg a\)	\(\neg 0 = 1\)，\(\neg 1 = 0\)
异或（XOR）	\(a \oplus b\)	相同为 \(0\)，不同为 \(1\)

性质	定义	示例
自反性	\(\forall a \in A,\; (a, a) \in R\)	\(\leq\) 是自反的
对称性	\((a, b) \in R \Rightarrow (b, a) \in R\)	"是朋友"是对称的
反对称性	\((a, b) \in R \land (b, a) \in R \Rightarrow a = b\)	\(\leq\) 是反对称的
传递性	\((a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R\)	\(<\) 是传递的

类型	定义
单射（Injection）	\(f(a_1) = f(a_2) \Rightarrow a_1 = a_2\)
满射（Surjection）	\(\forall b \in B,\; \exists a \in A,\; f(a) = b\)
双射（Bijection）	既是单射又是满射

概念	定义
无向图	边 \(\{u, v\}\) 无方向
有向图	边 \((u, v)\) 有方向
度（degree）	无向图中与顶点关联的边数，$\sum_{v \in V} \deg(v) = 2
邻接矩阵	\(A_{ij} = 1\) 当且仅当 \((i, j) \in E\)
邻接表	每个顶点存储其邻居列表

情形	条件	结果
Case 1	\(f(n) = O(n^{\log_b a - \epsilon})\)	\(T(n) = \Theta(n^{\log_b a})\)
Case 2	\(f(n) = \Theta(n^{\log_b a} \log^k n)\)	\(T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\)
Case 3	\(f(n) = \Omega(n^{\log_b a + \epsilon})\)	\(T(n) = \Theta(f(n))\)