离散数学

离散数学是可数、分离结构的数学，是计算构建其上的基础。本文涵盖命题逻辑与谓词逻辑、证明技巧、集合、关系、函数、图论基础以及递推关系。

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

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

命题逻辑

• 命题逻辑是真/假陈述的代数。一个命题是一个要么为真（T）要么为假（F）的陈述，不能两者都是。“天在下雨”是一个命题。“现在几点？”不是（它是一个问题，而不是一个有真值的陈述）。

• 命题可以使用逻辑连接词进行组合：

  • 与（合取，\(p \wedge q\)）：仅在 \(p\) 和 \(q\) 都为真时为真。
  • 或（析取，\(p \vee q\)）：在 \(p\) 或 \(q\) 至少一个为真时为真。
  • 非（否定，\(\neg p\)）：翻转真值。
  • 蕴含（蕴涵，\(p \to q\)）：仅在 \(p\) 为真且 \(q\) 为假时为假。“如果下雨，那么地面是湿的”这个陈述只在下雨且地面不湿时才被违反。
  • 当且仅当（双条件，\(p \leftrightarrow q\)）：当两者真值相同时为真。

• 真值表穷举所有可能的输入组合以及对应的输出。对于 \(n\) 个命题，表格有 \(2^n\) 行。这就是我们验证逻辑等价性的方法：

\(p\)	\(q\)	\(p \wedge q\)	\(p \vee q\)	\(p \to q\)
T	T	T	T	T
T	F	F	T	F
F	T	F	T	T
F	F	F	F	T

• \(p\) 为假时的蕴含行值得注意：无论 \(q\) 是什么，\(F \to q\) 总是为真。这就是空真。“如果猪会飞，那么我就是英国国王”在逻辑上为真，因为前提是假的。这看起来违反直觉，但对数学推理至关重要。

• 逻辑等价是对所有真值都成立的恒等式：

  • 德摩根定律：\(\neg(p \wedge q) \equiv \neg p \vee \neg q\) 和 \(\neg(p \vee q) \equiv \neg p \wedge \neg q\)。否定一个与运算，需要否定每个部分并将与变为或（反之亦然）。它们直接出现在编程中：!(a && b) 等价于 (!a || !b)。

  • 逆否命题：\(p \to q \equiv \neg q \to \neg p\)。“如果下雨，地面是湿的”等价于“如果地面不是湿的，那么没有下雨”。这是一种强大的证明技巧。

  • 双重否定：\(\neg(\neg p) \equiv p\)。

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

• 一个总是为真（对所有真值指派）的公式称为重言式。总是为假的称为矛盾式。有时真有时假的称为偶然式。例如，\(p \vee \neg p\) 是重言式，\(p \wedge \neg p\) 是矛盾式。

谓词逻辑与量词

• 命题逻辑无法表达关于一个集合中所有或某些元素的陈述。“每个大于2的素数都是奇数”需要谓词逻辑，它通过变量、谓词和量词扩展了命题逻辑。

• 谓词是一个依赖于变量的陈述：\(P(x)\) = “\(x\) 是偶数”。当 \(x\) 被赋予一个具体值时，它成为一个命题：\(P(4)\) 为真，\(P(7)\) 为假。

• 量词表达范围：

  • 全称量词（\(\forall\)）：“对所有”。\(\forall x \, P(x)\) 表示 “对于论域中的每个 \(x\)，\(P(x)\) 为真。”
  • 存在量词（\(\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{inputs} \, x, \, \text{output}(x) = \text{desired}(x)\)。当我们说它“终止”，我们的意思是 \(\forall x \, \exists t \, \text{halts}(x, t)\)。

证明技巧

• 证明是一个逻辑论证，它确定地建立一个陈述的真理性。与经验证据（表明某事物对测试过的案例有效）不同，证明保证它对所有案例都有效。这是计算机科学中正确性的标准。

• 直接证明：假设前提，通过逻辑步骤推导出结论。要证明“如果 \(n\) 是偶数，那么 \(n^2\) 是偶数”：假设 \(n = 2k\)（\(k\) 为某个整数），则 \(n^2 = 4k^2 = 2(2k^2)\)，是偶数。

• 反证法：假设该陈述为假，并推导出矛盾。要证明 \(\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\) 是约简的——矛盾。

• 数学归纳法：通过证明以下两点来证明对一切自然数成立的命题：(1) 基础情况成立（通常是 \(n = 0\) 或 \(n = 1\)），(2) 归纳步骤：如果命题对 \(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\) 时的公式。得证。

• 归纳法是证明递归算法和数据结构性质的主要工具。每个递归算法都有一个隐含的归纳正确性证明：基础情况是终止条件，归纳步骤是递归调用。

• 强归纳法假设命题对直到 \(k\) 的所有值都成立（不仅仅是 \(k\)），然后证明它对 \(k+1\) 成立。当递归依赖于不只前一个值时，这很有用。

• 鸽巢原理：如果将 \(n+1\) 个物体放入 \(n\) 个盒子，则至少有一个盒子包含两个物体。简单但出奇地强大。它证明了在任意13个人中，至少有两人出生月份相同。在网络中，它证明了当项目数多于桶数时，哈希冲突是不可避免的。

集合

• 集合是由不同元素组成的无序集合。集合是数学中最原始的数据结构，它们支撑着从类型系统到数据库查询的一切。

• 集合运算（联系第5章，我们在概率中使用了这些运算）：

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

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

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

关系

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

• 关系的重要性质：

  • 自反性：每个元素都与自身相关。对所有 \(a\)，\(a R a\)。例如：\(\leq\)（每个数都 \(\leq\) 自身）。
  • 对称性：如果 \(a R b\)，则 \(b R a\)。例如：“是兄弟/姐妹”。
  • 反对称性：如果 \(a R b\) 且 \(b R a\)，则 \(a = b\)。例如：\(\leq\)。
  • 传递性：如果 \(a R b\) 且 \(b R c\)，则 \(a R c\)。例如：\(<\)、\(\leq\)、“是…的祖先”。

• 等价关系是自反、对称且传递的关系。它将集合划分为等价类，其中同一类中的所有元素相互关联，但不同类中的元素不关联。模运算是等价关系：\(a \equiv b \pmod{n}\) 将整数划分为 \(n\) 个类。编程语言中的类型等价是一种等价关系。

• 偏序是自反、反对称且传递的关系。它定义了一种“小于等于”结构，其中某些元素可能不可比较。文件系统目录形成偏序（父-子），但兄弟目录不可比较。全序是每对元素都可比较的偏序（如整数上的 \(\leq\)）。

• 偏序在并发中至关重要：事件上的“先发生”关系是偏序。没有被“先发生”排序的事件是并发的，可以以任何相对顺序执行。

函数

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

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

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

• 双射：既是单射又是满射。\(A\) 和 \(B\) 之间完美的一一对应。双射具有逆函数。加密必须是双射的：每个明文映射到唯一的密文，解密函数就是其逆。

• 复合 \((g \circ f)(x) = g(f(x))\)：先应用 \(f\)，再应用 \(g\)。函数复合是结合的（第2章：与矩阵乘法的结合性相同）。软件中的管道就是函数复合：数据流经一系列变换。

图论基础

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

• 树是没有环的连通图。等价地，它有 \(n\) 个节点和 \(n-1\) 条边。树是文件系统、XML/HTML文档、决策过程和递归分解的结构。有根树有一个指定的根节点；其他每个节点有且只有一个父节点。

• 图 \(G\) 的生成树是一棵树，它使用 \(G\) 的边的一个子集包含 \(G\) 的所有节点。最小生成树（MST） 最小化总边权。Kruskal 算法（对边排序，贪心地添加不会形成环的最轻边）和 Prim 算法（从一个起始节点开始生长树，总是添加连接到新节点的最轻边）都能够在 \(O(|E| \log |V|)\) 时间内找到 MST。

• 平面性：如果一个图可以在平面上画出且没有边交叉，则它是平面的。根据欧拉公式，对于一个连通的平面图：\(|V| - |E| + |F| = 2\)，其中 \(|F|\) 是面的数量（区域，包括外部面）。这预示着对于平面图有 \(|E| \leq 3|V| - 6\)，因此平面图是稀疏的。电路板布线和地图着色利用了平面性。

• 图着色为节点分配颜色，使得相邻节点颜色不同。所需的最小颜色数称为色数 \(\chi(G)\)。四色定理指出，对于任何平面图，\(\chi(G) \leq 4\)。在计算机科学中，图着色用于寄存器分配（将变量分配到CPU寄存器，使得同时活跃的变量获得不同的寄存器）和调度（将任务分配到时间槽，使得冲突的任务不重叠）。

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

递推关系

• 递推关系定义一个序列，其中每一项都依赖于前面的项。它们自然地从递归算法中产生。

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

• 归并排序给出 \(T(n) = 2T(n/2) + O(n)\)：将数组分成两半（两个大小为 \(n/2\) 的子问题），递归排序每一半，然后合并（\(O(n)\) 工作）。解为 \(T(n) = O(n \log n)\)。

• 主定理解形如 \(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章（概率）中介绍。这些计数技巧对算法分析（有多少可能的输入？需要多少次比较？）至关重要，但这里不再重复。

可计算性

• 并非所有东西都能被计算。这是整个数学中最深刻的结果之一，它设定了计算机能做什么的根本极限。

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

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

• 停机问题问：给定一个程序和一个输入，该程序最终会停止，还是会永远运行？图灵在1936年证明，不存在通用算法能解决这个问题。证明采用反证法：假设存在一个停机判定器 \(H(P, x)\)。构造一个程序 \(D\)，它运行 \(H(D, D)\) 并做与 \(H\) 所述相反的操作。如果 \(H\) 说 \(D\) 停机，则 \(D\) 永远循环。如果 \(H\) 说 \(D\) 循环，则 \(D\) 停机。矛盾。

• 这不是当前技术的局限；这是数学上的不可能。无论多少计算量、多高的智慧或人工智能，都永远无法一般性地解决停机问题。这是计算机科学中哥德尔不完全性定理的类比。

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

• 如果一个算法存在，总是能以正确的“是/否”答案终止，则该问题是可判定的。如果不存在这样的算法，则是不可判定的。停机问题是不可判定的。素数测试是可判定的。大多数编程语言中的类型检查是可判定的（按设计）。

复杂性理论

• 即使在可计算的问题中，有些也远比其他的难。复杂性理论根据解决问题所需资源（时间、空间）随输入增长的情况对问题进行分类。

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

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

• P 中的每个问题也都在 NP 中（如果你能快速解决它，你当然也能快速验证一个解）。核心问题是 \(P = NP\) 是否成立：每个解能快速验证的问题是否也能快速求解？这是计算机科学中最重要的开放问题，悬赏一百万美元的克雷数学研究所千禧年大奖。

• 大多数专家认为 \(P \neq NP\)，这意味着有些问题本质上比验证更难求解。如果 \(P = NP\)，密码学将崩溃（破解加密属于 NP），优化、调度和药物设计将变得极其简单。

• NP-完全问题是 NP 中最难的问题。一个问题如果 (1) 它在 NP 中，并且 (2) 所有其他 NP 问题都可以在多项式时间内归约到它，则它是 NP-完全的。如果你能高效地求解任何一个 NP-完全问题，你就能求解所有 NP 问题（从而 \(P = NP\)）。

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

• 著名的 NP-完全问题：

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

• 当你在实践中遇到 NP-完全问题时，对于大规模输入你不会精确求解。相反，你会使用：近似算法（找到在最优解的一定保证因子内的解）、启发式方法（贪心、局部搜索、模拟退火）或特例求解器（许多 NP-完全问题在受限输入下是容易的）。例如，现代的 SAT 求解器尽管在最坏情况下是指数复杂度，但通过利用实际实例中的结构，通常能求解包含数百万个变量的实例。

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

编码任务（使用 CoLab 或 notebook）

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

   import itertools
   
   def truth_table(n_vars, expr_fn):
       """生成 n_vars 个变量的布尔函数的真值表。"""
       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("德摩根定律验证：")
   truth_table(2, lambda p, q: (not (p and q)) == ((not p) or (not q)))
   

2. 用归纳法证明求和公式——对多个数值进行数值验证，然后实现封闭形式解。

   import jax.numpy as jnp
   
   # 验证求和公式：1+2+...+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):
       """统计归并排序中的比较次数（递推式：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}")