离散数学

$n^{2} + n + 41$ 对 $n = 0, 1, 2, \dots, 39$ 全都是质数。试了 40 个都对，能说它对所有 $n$ 成立吗？不能， $n = 40$ 时它等于 $4 1^{2}$ 。程序也一样：测试通过 1000 个用例，不等于它对第 1001 个输入也正确。离散数学教的是另一种确定性：证明。它是计算机科学的母语，算法的正确性、复杂度、密码学的安全性，都用这门语言写成。

前置：会写简单的 Python 函数和递归，见高阶函数与递归。

命题与逻辑：先把话说清楚

证明之前，先要把”要证明什么”说得没有歧义。命题是一个非真即假的陈述。复合命题由连接词构成：与 $\land$ 、或 $\lor$ 、非 $\neg$ 、蕴含 $\to$ 、等价 $\leftrightarrow$ 。

最容易出错的是蕴含 $P \to Q$ 。它只在” $P$ 真而 $Q$ 假”时为假，其余情况都为真。“如果下雨，我就带伞”在没下雨时无论带不带伞都不算说谎。这叫”空真”（vacuous truth），程序员每天都在用：all([]) 返回 True，因为空列表里没有任何元素违反条件。

判断两个复合命题是否等价，最直接的办法是枚举真值表。变量少时让计算机来做：

from itertools import product
implies = lambda p, q: (not p) or q
rows = list(product([False, True], repeat=2))
# 逆否命题与原命题等价；逆命题不等价
print("P→Q ≡ ¬Q→¬P :", all(implies(p, q) == implies(not q, not p) for p, q in rows))
print("P→Q ≡ Q→P   :", all(implies(p, q) == implies(q, p) for p, q in rows))
# De Morgan：¬(P∧Q) ≡ ¬P∨¬Q
print("De Morgan   :", all((not (p and q)) == ((not p) or (not q)) for p, q in rows))
print("all([]) =", all([]))

输出：

P→Q ≡ ¬Q→¬P : True
P→Q ≡ Q→P   : False
De Morgan   : True
all([]) = True

逆否等价给了我们一种证明方法：要证” $n^{2}$ 是偶数 $\to$ $n$ 是偶数”，改证” $n$ 是奇数 $\to$ $n^{2}$ 是奇数”，后者一行就完： $(2 k + 1)^{2} = 2 (2 k^{2} + 2 k) + 1$ 。另一种是反证法：假设结论不成立，推出矛盾。经典例子是 $2$ 是无理数，以及”质数有无穷多个”：假设只有有限个 $p_{1}, \dots, p_{k}$ ，那么 $p_{1} p_{2} \dots p_{k} + 1$ 不能被其中任何一个整除，矛盾。

真值表的行数是 $2^{n}$ 。判断一个有 $n$ 个变量的布尔公式能否被满足（SAT），目前没有已知的多项式算法，这就是第一个被证明为 NP 完全的问题（见算法设计）。

量词把命题推广到集合上： $\forall x P (x)$ （对所有 $x$ ）， $\exists x P (x)$ （存在 $x$ ）。否定时量词互换： $\neg\forall x P (x) \equiv \exists x \neg P (x)$ 。要推翻”所有 $n$ 都让 $n^{2} + n + 41$ 为质数”，只需一个反例 $n = 40$ ；要证明它，举多少例子都不够。量词的顺序也要紧： $\forall x \exists y (y > x)$ （没有最大的数）为真， $\exists y \forall x (y > x)$ （存在比一切都大的数）为假。

停一下，检查理解单选

命题"如果函数的输入列表已排序，那么它返回正确结果"。下面哪个与它逻辑等价？

如果函数返回正确结果，那么输入列表已排序如果输入列表未排序，那么函数返回错误结果如果函数返回错误结果，那么输入列表未排序输入列表已排序，并且函数返回正确结果

归纳法：从有限步走到无穷

回到开头的问题：怎么证明一件事对所有自然数成立？

数学归纳法：证明 $P (0)$ 成立（基础），再证明对任意 $n$ ， $P (n) \to P (n + 1)$ （归纳步）。这两件事合起来像一排多米诺骨牌，第一块倒下，每一块倒下都推倒下一块，于是全部倒下。

例： $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ 。基础 $n = 1$ 时两边都是 1。归纳步：假设对 $n$ 成立，那么 $1 + \dots + n + (n + 1) = \frac{n ( n + 1 )}{2} + (n + 1) = \frac{( n + 1 ) ( n + 2 )}{2}$ ，正好是 $n + 1$ 时的公式。

有时 $P (n + 1)$ 需要的不只是 $P (n)$ ，而是前面所有的情况。强归纳法允许假设 $P (0), \dots, P (n)$ 全部成立。例：每个大于 1 的整数都能写成质数之积。如果 $n + 1$ 是质数，直接成立；否则 $n + 1 = ab$ ， $a, b$ 都比 $n + 1$ 小，由归纳假设都能分解，乘起来就是。普通归纳法在这里不够用，因为 $a, b$ 不一定是 $n$ 。

归纳法和递归是同一个想法的两面。写一个递归函数时，你相信”子问题的递归调用会返回正确结果”，只关心如何用它拼出当前问题的答案，并保证有一个不再递归的基础情况。这正是归纳证明的结构，证明一个递归函数正确，就是对输入规模做归纳。

def hanoi(n, src="A", dst="C", via="B", moves=None):
    # 归纳假设：hanoi(n-1) 能正确搬走上面 n-1 个盘子
    if moves is None: moves = []
    if n == 0: return moves
    hanoi(n - 1, src, via, dst, moves)
    moves.append((src, dst))
    hanoi(n - 1, via, dst, src, moves)
    return moves
 
for n in range(1, 8):
    print(n, len(hanoi(n)), 2**n - 1)

输出：

步数的递推 $T (n) = 2 T (n - 1) + 1$ ， $T (0) = 0$ 。猜测 $T (n) = 2^{n} - 1$ ，再用归纳法证明： $2 (2^{n - 1} - 1) + 1 = 2^{n} - 1$ 。“先猜，再用归纳证”是处理递推式最通用的办法。

归纳法还有一个变形在程序里更常见：不变式。证明循环正确，就是找到一个性质，循环开始前成立，每次迭代保持它成立，循环结束时它加上终止条件就推出想要的结论。二分查找的不变式是”如果目标存在，它一定在 [lo, hi) 里”。插入排序的不变式是”前 i 个元素已经有序”。写不出不变式的循环，通常也很难写对。

另一个经典的不变式例子是 15 数码问题：在 4×4 网格里滑动 15 个方块。可以证明，交换 14 和 15 的位置（其余不动）的局面永远无法到达。证明的思路是找一个每次滑动都保持不变的量（逆序数的奇偶性与空格所在行的组合），而目标局面的这个量与初始局面不同。不变式不仅能证明什么会发生，还能证明什么不可能发生。

停一下，检查理解单选

用归纳法证明"所有马都是同一种颜色"：基础是 1 匹马显然同色；归纳步取 n+1 匹马，去掉第一匹剩下 n 匹同色，去掉最后一匹剩下 n 匹也同色，两组有重叠所以全部同色。错在哪里？

基础情况应该从 0 匹马开始从 1 匹推到 2 匹时，两组没有重叠，归纳步不成立归纳法不能用于马这种非数学对象应该用强归纳法而不是普通归纳法

集合、函数与”一样多”

集合是数学的基本积木：一组互不相同的元素，不计顺序。并、交、差、补，以及幂集 $P (S)$ （所有子集组成的集合）。 $∣ S ∣ = n$ 时 $∣ P (S) ∣ = 2^{n}$ ，因为每个元素都有”选”或”不选”两种可能。Python 的 set 和 frozenset 就是对这套概念的直接实现。

函数 $f : A \to B$ 给 $A$ 中每个元素指定 $B$ 中唯一一个元素。三个性质决定了它能用来比较集合大小：

单射（injective）：不同的输入映到不同的输出。存在单射 $A \to B$ 说明 $∣ A ∣ \leq ∣ B ∣$ 。
满射（surjective）： $B$ 中每个元素都被映到。存在满射说明 $∣ A ∣ \geq ∣ B ∣$ 。
双射（bijection）：两者兼备，说明两个集合一样大。

双射是计数里最有力的工具：数不清一个集合时，找一个和它一一对应、但更好数的集合。 $n$ 元集合的子集与长度为 $n$ 的 0/1 串一一对应，所以有 $2^{n}$ 个。

单射的反面就是鸽巢原理：把 $n + 1$ 个东西放进 $n$ 个盒子，至少一个盒子里有两个。它看上去平凡，用起来却很深：

任何无损压缩算法都不可能把所有文件变短。长度为 $n$ 比特的文件有 $2^{n}$ 个，长度小于 $n$ 的只有 $2^{n} - 1$ 个，不可能一一对应。
哈希函数把无穷多个键映射到有限个桶，冲突必然存在，只能设法让它少（见数据结构）。

双射的思想推到无限集合，得到一个惊人的结论。自然数和偶数一样多（ $n \mapsto 2 n$ 是双射），自然数和有理数也一样多。但 Cantor 证明了实数比自然数多：假设能把 $[0, 1)$ 里的实数排成一列，构造一个数，让它的第 $i$ 位小数与第 $i$ 个数的第 $i$ 位不同，它就不在列表里，矛盾。这个对角线论证在计算机科学里有一个直接的后代：停机问题不可判定。所有程序可以排成一列（它们都是有限字符串），而”程序集合上的判定问题”和实数一样多，所以必然存在没有程序能解决的问题；Turing 用同样的对角线构造，具体指出了一个：判断任意程序在任意输入上是否停机。

函数之外还有更一般的关系： $A \times B$ 的任意子集。两类关系反复出现。等价关系满足自反、对称、传递，它把集合切成互不相交的等价类：模 $n$ 同余把整数切成 $n$ 类，“在同一个连通分量里”把图的顶点切成若干块，并查集维护的正是这样的划分。偏序满足自反、反对称、传递，但允许两个元素”不可比”：子集包含关系、任务之间的依赖关系都是偏序。把一个偏序扩展成全序（排出一个先后顺序且不违反任何依赖），就是图上的拓扑排序。

停一下，检查理解多选

下面哪些结论可以由鸽巢原理直接得到？

任意 13 个人中，至少两人生日在同一个月把 2^64 + 1 个不同的字符串哈希成 64 位整数，一定有冲突23 个人中有两人同一天生日的概率超过一半不存在能把每个文件都压缩得更短的无损压缩算法

图：关系的通用语言

社交网络、道路地图、函数调用关系、模块依赖、神经网络的计算图，都可以抽象成同一种东西：图 $G = (V, E)$ ，一组顶点和连接它们的边。

最早的图论问题是 Euler 的哥尼斯堡七桥问题：能否走过每座桥恰好一次？Euler 的回答不靠枚举，靠一个计数论证：每次经过一个顶点，用掉一条进入的边和一条离开的边，所以除了起点和终点，每个顶点的度（连接的边数）必须是偶数。哥尼斯堡四块陆地的度都是奇数，不可能。

这个论证里藏着最基本的一条定理，握手引理： $\sum_{v} de g (v) = 2∣ E ∣$ ，因为每条边贡献两个度。一个推论是度为奇数的顶点一定有偶数个。

几个基本概念：

路径与连通：任意两点间都有路径的图是连通的。
环：起点和终点相同的路径。
树：连通且无环的图。 $n$ 个顶点的树恰好有 $n - 1$ 条边；任意两点之间恰好一条路径；去掉任何一条边就不连通，加上任何一条边就出现环。
有向无环图（DAG）：有向边且没有有向环。依赖关系天然是 DAG，构建系统、包管理器、反向传播的计算图都在 DAG 上按拓扑序处理。
二分图：顶点能分成两组，边只在组间。一个图是二分图当且仅当它没有奇数长度的环。

图着色是另一个能大量建模的问题：给顶点涂色，相邻顶点颜色不同，最少要几种颜色？考试排期（冲突的课不能同时考）、寄存器分配（同时活跃的变量不能用同一个寄存器）都是着色问题。二分图恰好是能 2 着色的图。

from itertools import combinations
# 树的性质：用 Prüfer 序列可以证明 n 个带标号顶点的树有 n^(n-2) 棵（Cayley 公式）
def count_trees(n):
    # 暴力枚举 n-1 条边的子集，检查是否连通（n-1 条边 + 连通 ⇒ 无环 ⇒ 树）
    edges = list(combinations(range(n), 2)); total = 0
    for subset in combinations(edges, n - 1):
        parent = list(range(n))
        def find(x):
            while parent[x] != x: x = parent[x]
            return x
        for u, v in subset: parent[find(u)] = find(v)
        total += len({find(x) for x in range(n)}) == 1
    return total
 
for n in range(2, 7):
    print(n, count_trees(n), n ** (n - 2))

输出：

2 1 1
3 3 3
4 16 16
5 125 125
6 1296 1296

暴力枚举和 Cayley 公式 $n^{n - 2}$ 完全吻合。这里用到的 find 就是并查集的雏形。图在内存里怎么存（邻接表还是邻接矩阵）见数据结构，在图上搜索、求最短路和最小生成树的算法见算法设计。

停一下，检查理解单选

一个连通无向图有 10 个顶点、12 条边。关于它，哪个说法一定正确？

它是一棵树它至少包含一个环所有顶点的度数之和是 12它是二分图

计数：不用一个个数

很多问题最后都归结为”有多少种”：算法要检查多少种情况？密码有多少种可能？一个事件的概率是多少（见概率论）？

两条基本法则：乘法法则，分步完成的事，方法数相乘；加法法则，分类完成的事，互不重叠时方法数相加。由此得到：

$n$ 个不同元素的排列： $n!$
从 $n$ 个里选 $k$ 个、计顺序： $\frac{n !}{( n - k )!}$
从 $n$ 个里选 $k$ 个、不计顺序： $(k n) = \frac{n !}{k ! ( n - k )!}$ 。每个无序选择对应 $k!$ 个有序选择，所以要除掉，这叫除法法则。

一个漂亮的技巧是隔板法：把 10 个相同的球放进 4 个不同的盒子，有几种方法？把球排成一行，插 3 块隔板，一种排法对应一种分配（双射！）。13 个位置里选 3 个放隔板， $(3 13) = 286$ 。

分类有重叠时用容斥原理： $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$ ，三个集合时再加回三者的交。例：1 到 1000 里能被 2、3、5 之一整除的数有多少？

from math import comb
print("隔板法:", comb(13, 3),
      "暴力:", sum(1 for a in range(11) for b in range(11 - a) for c in range(11 - a - b)))
# 容斥：|A∪B∪C| = 单个之和 − 两两之交 + 三者之交
N = 1000
f = lambda d: N // d
incl_excl = f(2) + f(3) + f(5) - f(6) - f(10) - f(15) + f(30)
brute = sum(1 for x in range(1, N + 1) if x % 2 == 0 or x % 3 == 0 or x % 5 == 0)
print("容斥:", incl_excl, "暴力:", brute)
# 二项式定理的组合解释：所有子集个数 = 各大小子集个数之和
print(sum(comb(10, k) for k in range(11)), 2**10)

输出：

隔板法: 286 暴力: 286
容斥: 734 暴力: 734
1024 1024

隔板法的暴力版本里，第四个盒子的球数由前三个决定，所以三重循环就够了。最后一行是 $\sum_{k} (k n) = 2^{n}$ 的验证，它有两种证明：代数上是二项式定理 $(1 + 1)^{n}$ 展开；组合上是”按大小分类数子集”。用两种方法数同一个集合，得到一个恒等式，这叫组合证明，往往比代数推导更容易让人信服。

公式数不出来的时候，还有第三条路：递推计数。长度为 $n$ 、没有两个 1 相邻的二进制串有多少个？按最后一位分类：最后一位是 0，前面是任意合法的长度 $n - 1$ 的串；最后一位是 1，倒数第二位必须是 0，前面是任意合法的长度 $n - 2$ 的串。于是 $a_{n} = a_{n - 1} + a_{n - 2}$ ， $a_{1} = 2$ ， $a_{2} = 3$ ，这是斐波那契数列。分类、写出递推、再用归纳法证明闭式，这条路线和动态规划的思路完全一样。

from itertools import product
def brute(n):
    return sum(1 for bits in product("01", repeat=n) if "11" not in "".join(bits))
a = [1, 2]  # a_0 = 1（空串），a_1 = 2
for n in range(2, 11):
    a.append(a[-1] + a[-2])
print([brute(n) for n in range(1, 11)])
print(a[1:])

输出：

[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
[2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

停一下，检查理解单选

一个长度为 8 的二进制串，恰好有 3 个 1，并且没有两个 1 相邻。有多少个这样的串？

5620106

渐近：只关心增长的速度

最后一块是分析算法时用的数学语言。精确地数一个算法执行多少条指令既困难又没有意义，机器不同常数就不同。我们关心的是：输入翻倍时，时间怎么变？

$f (n) = O (g (n))$ 的精确定义是：存在常数 $c > 0$ 和 $n_{0}$ ，使得对所有 $n \geq n_{0}$ 有 $f (n) \leq c \cdot g (n)$ 。它是一个上界，忽略常数因子，也忽略小 $n$ 时的行为。对称地， $Ω$ 是下界， $Θ$ 是上下界同时成立（增长速度相同）。

几个由定义直接推出的事实：

$3 n^{2} + 100 n + 7 = Θ (n^{2})$ ：取 $n_{0} = 100$ ， $c = 5$ 即可。低阶项和常数都会被吞掉。
$lo g_{2} n$ 与 $ln n$ 只差常数倍 $ln 2$ ，所以对数的底在渐近记号里无所谓，写 $O (lo g n)$ 即可。
$O$ 只是上界： $n = O (n^{2})$ 是对的，只是不够紧。说”这个算法是 $O (n^{2})$ “不等于说它在最坏情况下真的要 $n^{2}$ 步。
常见的增长等级： $1 ≪ lo g n ≪ n ≪ n ≪ n lo g n ≪ n^{2} ≪ 2^{n} ≪ n!$ 。

import math
print(f"{'n':>8} {'log2 n':>8} {'n log n':>12} {'n^2':>14} {'2^n':>12}")
for n in [10, 100, 1000, 10**6]:
    two_n = f"{2**n:.2e}" if n <= 1000 else "太大"
    print(f"{n:>8} {math.log2(n):>8.1f} {n*math.log2(n):>12.0f} {n*n:>14} {two_n:>12}")
# Stirling：log2(n!) ≈ n log2 n，所以比较排序的下界是 Θ(n log n)
for n in [10, 100, 1000]:
    print(n, round(math.lgamma(n + 1) / math.log(2)), round(n * math.log2(n)))

输出：

       n   log2 n      n log n            n^2          2^n
      10      3.3           33            100     1.02e+03
     100      6.6          664          10000     1.27e+30
    1000     10.0         9966        1000000    1.07e+301
 1000000     19.9     19931569  1000000000000           太大
10 22 33
100 525 664
1000 8529 9966

$n = 1 0^{6}$ 时， $n lo g n$ 约 $2 \times 1 0^{7}$ ，一台机器零点几秒； $n^{2}$ 是 $1 0^{12}$ ，要几十分钟； $2^{n}$ 在宇宙寿命里也跑不完。最后三行展示了 $lo g_{2} (n!)$ 与 $n lo g_{2} n$ 同阶：两者之比从 0.67 升到 0.86，缓慢趋向 1，差距来自 Stirling 公式里 $- n lo g_{2} e$ 这个低阶项，这个事实是”比较排序至少需要 $Θ (n lo g n)$ 次比较”的核心： $n!$ 种排列需要至少 $lo g_{2} n!$ 次二元判断才能区分。

渐近分析还需要两样数学工具。一是求和： $\sum_{i = 1}^{n} i = Θ (n^{2})$ ，几何级数 $\sum_{i = 0}^{k} 2^{i} = 2^{k + 1} - 1$ （这就是动态数组均摊 $O (1)$ 的原因），调和级数 $\sum_{i = 1}^{n} \frac{1}{i} \approx ln n$ 。二是递推式：分治算法的时间满足 $T (n) = a T (n / b) + f (n)$ 这种形式，可以用前面”先猜再归纳证”的办法，也可以用主定理直接读出答案。这些怎么用在具体算法上，见算法设计。

停一下，检查理解多选

关于渐近记号，哪些说法正确？

n log n 是 O(n^2)2^(n+1) 和 2^(2n) 是同阶的，因为指数里的常数可以忽略log2(n) 和 log10(n) 是 Θ 同阶的只要算法是 O(n)，对所有输入它都一定比 O(n^2) 的算法快

记住这三件事

例子再多也不是证明；蕴含只与逆否等价，反证、归纳、不变式是三把基本工具。
递归与归纳是同一种思想：相信子问题的答案，管好基础情况和”一步”。
计数的核心是双射与分类；渐近记号只描述增长速度，丢掉常数，也丢掉小规模的真相。

CS 与 LLM 学习知识库

探索

离散数学

命题与逻辑：先把话说清楚

归纳法：从有限步走到无穷

集合、函数与”一样多”

图：关系的通用语言

计数：不用一个个数

渐近：只关心增长的速度

记住这三件事

延伸阅读

目录

反向链接