离散数学

离散数学

离散数学（discrete maths）研究的是可数、分离的结构，是整个计算机科学的基石。本文件涵盖命题逻辑与谓词逻辑、证明技术、集合、关系、函数、图论基础以及递推关系。

• 在前面的章节里，我们打交道的主要是连续数学：微积分（第 3 章）、概率分布（第 5 章）、对实值参数的优化（第 6 章）。但计算机本质上是离散的机器。它存储比特（0 或 1），处理整数，遵循分支逻辑，操作有限的数据结构。离散数学为推理这些结构提供了形式化语言。

• 本章随后所有内容都建立在离散数学之上：处理器的逻辑门就是布尔代数，调度算法需要正确性证明，内存管理用到集合运算，而算法分析离不开递推关系。

命题逻辑

• **命题逻辑（propositional logic）是关于真/假陈述的代数。一个命题（proposition）**是或为真（T）或为假（F）、二者必居其一的陈述句。"今天在下雨"是一个命题。"现在几点了？"则不是（它是个疑问句，没有真假值可言）。

• 命题可以通过**逻辑联结词（logical connectives）**组合起来：

  • AND（合取，p \wedge q）：仅当 p 和 q 同时为真时才为真。
  • OR（析取，p \vee q）：只要 p 或 q 至少有一个为真就为真。
  • NOT（否定，\neg p）：翻转真值。
  • IMPLIES（蕴含，p \to q）：仅当 p 为真且 q 为假时才为假。"如果下雨，地面就会湿"这句话只有在下雨且地面没湿时才被违反。
  • IFF（双条件，p \leftrightarrow q）：当两者真值相同时为真。

• **真值表（truth table）**穷举所有可能的输入组合及其对应的输出。对于 n 个命题，真值表有 2^n 行。这就是我们验证逻辑等价的方式：

• p 为假的那一行蕴含值得注意：无论 q 取何值，F \to q 永远为真。这就是空真（vacuous truth）。"如果猪会飞，那我就是英格兰国王"在逻辑上为真，因为前提为假。这看似反直觉，却是数学推理中不可或缺的。

• **逻辑等价（logical equivalences）**是对所有真值取值都成立的恒等式：

  • 德摩根律（De Morgan's laws）：\neg(p \wedge q) \equiv \neg p \vee \neg q 和 \neg(p \vee q) \equiv \neg p \wedge \neg q。要否定一个 AND，就把每一部分都取反，再换成 OR（反之亦然）。它直接体现在编程中：!(a && b) 等价于 (!a || !b)。

  • 逆否命题（contrapositive）：p \to q \equiv \neg q \to \neg p。"如果下雨，地面就会湿"等价于"如果地面不湿，那就没下雨"。这是一种强有力的证明技巧。

  • 双重否定（double negation）：\neg(\neg p) \equiv p。

  • 分配律（distributive）：p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)。

• 对所有真值赋值都为真的公式叫重言式（tautology）；永远为假的叫矛盾式（contradiction）；有时真有时假的叫偶真式（contingent）。例如，p \vee \neg p 是重言式，p \wedge \neg p 是矛盾式。

谓词逻辑与量词

• 命题逻辑无法表达关于某个集合中所有元素或某些元素的陈述。"所有大于 2 的素数都是奇数"需要谓词逻辑（predicate logic），它在命题逻辑基础上引入了变量、谓词和量词。

• **谓词（predicate）**是依赖于某个变量的陈述：P(x) = "x 是偶数。"当 x 取定某个具体值时，它就变成了一个命题：P(4) 为真，P(7) 为假。

• **量词（quantifiers）**表达作用范围：

  • 全称量词（universal quantifier）（\forall）："对所有的"。\forall x \, P(x) 表示"对定义域内的每一个 x，P(x) 都为真。"
  • 存在量词（existential quantifier）（\exists）："存在"。\exists x \, P(x) 表示"至少存在一个 x 使 P(x) 为真。"

• 否定量词会把它翻转：\neg(\forall x \, P(x)) \equiv \exists x \, \neg P(x)。"不是所有人都通过了"意味着"有人没通过"。而 \neg(\exists x \, P(x)) \equiv \forall x \, \neg P(x)。"不存在完美的算法"意味着"每个算法都有缺陷"。

• 嵌套量词表达复杂关系。\forall x \, \exists y \, (y > x) 表示"对每个数，都存在一个更大的数"（对整数成立）。顺序很重要：\exists y \, \forall x \, (y > x) 表示"存在一个比所有其他数都大的数"（对整数不成立）。

• 谓词逻辑是形式化规约的语言。当我们说一个算法"正确"，是指 \forall \text{输入} \, x, \, \text{输出}(x) = \text{期望}(x)。当我们说它"会终止"，是指 \forall x \, \exists t \, \text{停止}(x, t)。

证明技术

• **证明（proof）**是确立某个陈述为真的逻辑论证，不容置疑。不同于经验证据（只说明在被测案例上成立），证明保证它在所有情形下都成立。这是计算机科学中正确性的标准。

• 直接证明（direct proof）：假设前提成立，通过逻辑步骤推导出结论。要证明"若 n 是偶数，则 n^2 是偶数"：假设 n = 2k（k 为某整数），那么 n^2 = 4k^2 = 2(2k^2)，是偶数。

• 反证法（proof by contradiction）：假设命题不成立，再推出矛盾。要证明 \sqrt{2} 是无理数：假设 \sqrt{2} = a/b（已约分到最简）。则 2 = a^2/b^2，所以 a^2 = 2b^2，意味着 a^2 是偶数，故 a 是偶数，设 a = 2c。则 4c^2 = 2b^2，所以 b^2 = 2c^2，意味着 b 也是偶数。但我们之前说过 a/b 已约到最简——矛盾。

• 数学归纳法（proof by induction）：通过以下两步证明某个陈述对所有自然数成立：（1）**基础情形（base case）**成立（通常是 n = 0 或 n = 1）；（2）归纳步骤（inductive step）：如果陈述对 n = k 成立（归纳假设），则它对 n = k + 1 也成立。

• 例如，证明 \sum_{i=1}^{n} i = \frac{n(n+1)}{2}：

  • 基础情形：n = 1：1 = \frac{1 \cdot 2}{2} = 1。成立。
  • 归纳步骤：假设 \sum_{i=1}^{k} i = \frac{k(k+1)}{2}。则 \sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}。这正是 n = k+1 时的公式。证毕。

• 归纳法是证明递归算法和数据结构性质的主力工具。每个递归算法都隐含着一个归纳证明：基础情形就是终止条件，归纳步骤就是递归调用本身。

• **强归纳法（strong induction）**假设陈述对直到 k 的所有取值都成立（不只是 k），再去证明它对 k + 1 成立。当递归依赖于不止前一个值时，这种方式很有用。

• 鸽巢原理（pigeonhole principle）：如果把 n+1 个物体放进 n 个盒子里，至少有一个盒子装了两个物体。简单却出奇地强大。它可以证明：任意 13 人的群体中，至少有两人生日月份相同。在网络中，它证明当物品数多于桶数时哈希冲突不可避免。

集合

• **集合（set）**是互异元素的无序汇集。集合是数学中最原始的数据结构，从类型系统到数据库查询，一切都建立在它之上。

• 集合运算（呼应第 5 章在概率中用到的这些运算）：

  • 并集（union） A \cup B：属于 A 或 B 或同时属于两者的元素。
  • 交集（intersection） A \cap B：同时属于 A 和 B 的元素。
  • 补集（complement） \bar{A}：不属于 A 的元素（相对于某个全集）。
  • 差集（difference） A \setminus B：属于 A 但不属于 B 的元素。
  • 笛卡尔积（Cartesian product） A \times B：所有形如 (a, b) 的有序对，其中 a \in A, b \in B。

• 幂集（power set） \mathcal{P}(A) 是 A 的所有子集构成的集合。若 |A| = n，则 |\mathcal{P}(A)| = 2^n。对 A = \{1, 2\}：\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}。

• **基数（cardinality）衡量集合大小。有限集的基数是整数。无限集则有不同的"大小"：自然数 \mathbb{N} 和有理数 \mathbb{Q} 是可数无穷（countably infinite）的（可以列出来），而实数 \mathbb{R} 是不可数无穷（uncountably infinite）**的（无法列出，由康托尔的对角线论证证明）。这个区别在可计算性理论中很重要：函数有不可数无穷多个，但程序只有可数无穷多个，因此大多数函数是不可计算的。

关系

• 集合 A 上的关系（relation） R 是 A \times A 的一个子集：一组有序对，指明哪些元素之间有关系。例如，整数上的 \leq 就是集合 \{(a, b) : a \leq b\}。

• 关系的几个重要性质：

  • 自反（reflexive）：每个元素与自身有关系。对所有 a，a R a。例如 \leq（每个数都 \leq 自身）。
  • 对称（symmetric）：若 a R b 则 b R a。例如"是……的兄弟姐妹"。
  • 反对称（antisymmetric）：若 a R b 且 b R a 则 a = b。例如 \leq。
  • 传递（transitive）：若 a R b 且 b R c 则 a R c。例如 <、\leq、"是……的祖先"。

• 等价关系（equivalence relation）同时满足自反、对称、传递。它把集合划分成若干等价类（equivalence classes）：同一类内的所有元素彼此相关，但与其它类中的元素无关。模运算就是等价关系：a \equiv b \pmod{n} 把整数划分成 n 个类。编程语言中的类型等价也是等价关系。

• **偏序（partial order）**满足自反、反对称、传递。它定义了一种"小于等于"结构，但某些元素之间可能无法比较。文件系统的目录构成偏序（父子关系），但兄弟目录之间无法比较。**全序（total order）**则是任意两个元素都可比较的偏序（如整数上的 \leq）。

• 偏序在并发中不可或缺：事件之间的"先于（happens-before）"关系就是偏序。不被先于关系排序的事件是并发的，可能以任意相对顺序执行。

函数

• 函数（function） f: A \to B 把 A（定义域）中的每个元素映射到 B（陪域）中恰好一个元素。函数是确定性计算的数学模型：给定一个输入，恰好有一个输出。

• 单射（injective，一一对应）：不同的输入总是映射到不同的输出。f(a) = f(b) \implies a = b。无损压缩必须是单射：不同的输入必须压缩成不同的输出（否则无法唯一解压）。

• 满射（surjective，映上）：B 中的每个元素都被 A 中某个元素映射到。值域等于陪域。如果字符串数少于可能的哈希数，把字符串映射到 256 位哈希的哈希函数就不是满射。

• 双射（bijective）：既是单射又是满射。A 与 B 之间完美的一一对应。双射存在逆函数。加密必须是双射：每个明文映射到唯一的密文，解密函数就是它的逆。

• 复合（composition） (g \circ f)(x) = g(f(x))：先应用 f，再应用 g。函数复合满足结合律（第 2 章提到：矩阵乘法也满足结合律）。软件中的管道（pipeline）就是函数复合：数据流经一连串变换。

图论基础

• 我们在第 12 章（图神经网络）中详细讲过图，包括邻接矩阵、图的类型、拉普拉斯矩阵和谱理论。这里我们聚焦与计算机科学相关的算法性和结构性性质。

• **树（tree）**是没有环的连通图。等价地，它有 n 个节点和 n-1 条边。树是文件系统、XML/HTML 文档、决策过程和递归分解的结构。**有根树（rooted tree）**有一个指定的根节点；其余每个节点都恰好有一个父节点。

• 图 G 的**生成树（spanning tree）**是用其边的一个子集把 G 的所有节点都连通起来的树。**最小生成树（minimum spanning tree，MST）**使边权总和最小。Kruskal 算法（把边排序，贪心地加入不构成环的最轻边）和 Prim 算法（从一个起点开始向外长树，每次加入连接到新节点的最轻边）都能在 O(|E| \log |V|) 时间内找到 MST。

• 平面性（planarity）：如果一个图可以在平面上画出来且边不交叉，它就是可平面图。由欧拉公式（Euler's formula），对连通的平面图有：|V| - |E| + |F| = 2，其中 |F| 是面（区域，包括外部面）的个数。由此可推出平面图满足 |E| \leq 3|V| - 6，所以平面图是稀疏的。电路板布线和地图着色正是利用了平面性。

• 图着色（graph colouring）给节点分配颜色，使任意两个相邻节点颜色不同。所需的最少颜色数叫色数（chromatic number） \chi(G)。**四色定理（four-colour theorem）**指出对任何平面图都有 \chi(G) \leq 4。在计算机科学中，图着色被用来建模寄存器分配（把变量分配到 CPU 寄存器，使同时活跃的变量得到不同的寄存器）和调度（把任务分配到时间槽，使冲突的任务不重叠）。

• **欧拉路径（Euler path）**经过每条边恰好一次。当且仅当图中恰好有 0 个或 2 个奇数度节点时它才存在。**哈密顿路径（Hamiltonian path）**经过每个节点恰好一次。判断哈密顿路径是否存在是 NP 完全问题——计算机科学中经典的难题之一。这种对比（欧拉：多项式时间，哈密顿：NP 完全）正好说明：听起来相似的问题，计算复杂度可以天差地别。

递推关系

• **递推关系（recurrence relation）**定义这样一个序列：其中每一项都依赖于前面的项。它们自然地从递归算法中产生。

• 最简单的例子：T(n) = T(n-1) + 1，T(0) = 0。展开：T(n) = T(n-1) + 1 = T(n-2) + 2 = \cdots = n。这是 O(n)，正是一个简单循环的时间复杂度。

• **归并排序（merge sort）**给出 T(n) = 2T(n/2) + O(n)：把数组对半分（两个规模为 n/2 的子问题），递归地排序每一半，然后合并（O(n) 工作量）。解为 T(n) = O(n \log n)。

• **主定理（Master Theorem）**求解形如 T(n) = aT(n/b) + O(n^d) 的递推：

  • 若 d > \log_b a：T(n) = O(n^d)（每一层的工作量占主导）
  • 若 d = \log_b a：T(n) = O(n^d \log n)（各层工作量平衡）
  • 若 d < \log_b a：T(n) = O(n^{\log_b a})（子问题数量占主导）

• 对归并排序：a = 2, b = 2, d = 1。由于 d = \log_2 2 = 1，我们处于平衡情形：T(n) = O(n \log n)。

• 斐波那契递推 F(n) = F(n-1) + F(n-2)，F(0) = 0, F(1) = 1，有闭式解 F(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}，其中 \phi = \frac{1+\sqrt{5}}{2}（黄金比例），\psi = \frac{1-\sqrt{5}}{2}。这说明斐波那契序列按 O(\phi^n) 指数增长，也正是朴素递归求斐波那契数会慢到指数级的原因。

• 组合数学（排列、组合、二项式定理、容斥原理）放在第 5 章（概率）里讲。这些计数技巧对算法分析至关重要（有多少种可能的输入？需要多少次比较？），但这里不再重复。

可计算性

• 并非所有问题都能被计算。这是整个数学中最深刻的结论之一，它划定了计算机能力的根本边界。

• 图灵机（Turing machine）是计算的抽象模型：一条无限长的带子（每个格子放一个符号）、一个读写头，以及一组带转移规则的有限状态。尽管如此简单，图灵机能计算任何真实计算机能算的东西。这就是丘奇-图灵论题（Church-Turing thesis）：任何可有效计算的函数都能被图灵机计算。

• 每种编程语言（Python、C、Haskell）都是**图灵完备（Turing complete）**的：它能模拟图灵机，因此能计算任何可计算的东西。语言之间的差异在于便捷性、速度和安全性，而不在于它们本质上能计算什么。

• **停机问题（halting problem）**问的是：给定一个程序和一个输入，这个程序最终会停下来，还是会永远运行下去？图灵在 1936 年证明：没有任何算法能在一般情形下解决这个问题。证明用的是反证法：假设存在一个停机检测器 H(P, x)。构造一个程序 D，它运行 H(D, D) 并做与 H 所说相反的事。如果 H 说 D 会停，D 就永远循环。如果 H 说 D 会循环，D 就停下。矛盾。

• 这不是当前技术的局限，而是数学上的不可能。无论多少算力、多少聪明才智、多强的 AI，都永远无法在一般情形下解决停机问题。它是计算机科学中哥德尔不完备性定理的对应物。

• 现实后果：你无法写出完美的死锁检测器、完美的杀毒软件或完美的优化编译器。每一个都需要在一般情形下解决停机问题（或某个等价的不可判定问题）。真实工具用的是启发式方法和近似，它们在常见情况下能工作，但无法对所有输入保证正确。

• 如果存在一个算法，它总是能终止并给出正确的"是/否"答案，那么这个问题就是可判定的（decidable）。如果不存在这样的算法，它就是不可判定的（undecidable）。停机问题不可判定。素性测试可判定。大多数编程语言的类型检查都是可判定的（这是刻意设计的）。

复杂度理论

• 即便都是可计算的问题，有些也比另外一些难得多。**复杂度理论（complexity theory）**按照输入增长时求解所需的资源（时间、空间）对问题进行分类。

• P（多项式时间）：能在 O(n^k) 时间内求解（k 为某常数）的问题。排序（O(n \log n)）、最短路径（O(|V|^2)）、矩阵乘法（O(n^3)）。这些被认为是"高效的"或"易处理的"。

• NP（非确定性多项式时间）：问题的一个候选解可以在多项式时间内被验证，即便找到这个解可能要花指数时间。例如，给定一条声称的哈密顿路径，你可以在 O(n) 时间内验证它（检查每条边）。但要找出一条，可能需要尝试指数级多的可能性。

• P 中的每个问题也都在 NP 中（如果你能很快求解，自然也能很快验证）。核心问题是 P = NP 是否成立：每一个解能被快速验证的问题，是否也能被快速求解？这是计算机科学中最重要的开放问题，悬赏 100 万美元的克雷千禧奖。

• 大多数专家相信 P \neq NP，即有些问题从根本上比求解更难于验证。如果 P = NP，密码学会崩塌（破解加密属于 NP），优化、调度、药物设计都会变得轻而易举。

• NP 完全（NP-complete）问题是 NP 中最难的问题。一个问题如果是 NP 完全的，需要满足：（1）它属于 NP；（2）NP 中的每一个其它问题都能在多项式时间内归约到它。如果你能高效地解任何一个 NP 完全问题，你就能高效地解所有这些问题（于是 P = NP）。

• **归约（reduction）**把一个问题变换成另一个问题。如果问题 A 可归约到问题 B，那么 B 至少和 A 一样难。Cook（1971）证明了 SAT（布尔可满足性问题：给定一个逻辑公式，是否存在一种变量赋值使它为真？）是 NP 完全的。Karp（1972）通过把 SAT 归约到另外 21 个经典问题，证明了它们也都是 NP 完全的。

• 著名的 NP 完全问题：

  • 旅行商问题（Travelling Salesman Problem，TSP）：找到访问所有城市恰好一次的最短路线。
  • 图着色：用 k 种颜色给节点着色，使相邻节点不同色（k \geq 3）。
  • 子集和（subset sum）：给定一组整数，是否存在一个子集使其和等于某个目标值？
  • 布尔可满足性（SAT）：是否存在一种真值赋值使某个逻辑公式成立？
  • 哈密顿路径（前文图论中已提到）。

• 在实践中遇到 NP 完全问题时，你不会对大规模输入去精确求解。相反，你会用：近似算法（approximation algorithms）（在最优解的一个保证倍数范围内找到解）、启发式方法（heuristics）（贪心、局部搜索、模拟退火），或专用求解器（special-case solvers）（许多 NP 完全问题在受限输入下是容易的）。例如，现代 SAT 求解器经常能求解有数百万变量的实例，尽管最坏情况下复杂度是指数级，靠的就是利用实际实例中的结构。

• **NP 困难（NP-hard）**问题至少和 NP 完全问题一样难，但不一定属于 NP（它们的解甚至可能无法在多项式时间内验证）。NP 完全问题的优化版本通常是 NP 困难的："找到最短的 TSP 路线"是 NP 困难的，而"是否存在长度小于 k 的 TSP 路线？"是 NP 完全的。

编程练习（使用 CoLab 或 notebook）

1. 写一个真值表生成器。给定一个逻辑表达式，枚举所有输入组合并计算输出。

import itertools

def truth_table(n_vars, expr_fn):
    """Generate truth table for a boolean function of n_vars variables."""
    headers = [f"p{i}" for i in range(n_vars)]
    print(" | ".join(headers + ["result"]))
    print("-" * (len(headers) * 4 + 10))
    for vals in itertools.product([False, True], repeat=n_vars):
        result = expr_fn(*vals)
        row = [str(v)[0] for v in vals] + [str(result)[0]]
        print(" | ".join(f"{r:>2}" for r in row))

# 验证德摩根律：NOT(p AND q) == (NOT p) OR (NOT q)
print("De Morgan's Law verification:")
truth_table(2, lambda p, q: (not (p and q)) == ((not p) or (not q)))
​

2. 用归纳法证明求和公式——先对许多值做数值验证，再实现闭式解。

import jax.numpy as jnp

# 验证求和公式：sum(1..n) = n(n+1)/2
for n in [1, 5, 10, 100, 1000, 10000]:
    brute = sum(range(1, n + 1))
    formula = n * (n + 1) // 2
    print(f"n={n:5d}  sum={brute:>10d}  formula={formula:>10d}  match={brute == formula}")
​

3. 用主定理求解归并排序的递推，并通过统计操作次数做经验验证。

import jax.numpy as jnp

def merge_sort_ops(n):
    """Count comparisons in merge sort (recurrence: T(n) = 2T(n/2) + n)."""
    if n <= 1:
        return 0
    half = n // 2
    return merge_sort_ops(half) + merge_sort_ops(n - half) + n

for n in [8, 64, 512, 4096, 32768]:
    ops = merge_sort_ops(n)
    predicted = n * jnp.log2(n)
    ratio = ops / predicted
    print(f"n={n:5d}  ops={ops:>10d}  n log n={int(predicted):>10d}  ratio={ratio:.3f}")
​