元数据卡
- 前置知识：第1章 逻辑，第2章 集合论
- 预计时间：50 分钟
- 核心难度：进阶
- 完成标志：能够区分四种证明方法，在简单场景下构造反例或归纳证明
你的进度
现在你有了逻辑和集合两件工具。馆长在第三层指着墙上的几道定理："这些都是真的——但你怎么知道它们总是真的？"
你的任务
你写了一个排序算法，测试了一千次都正确。你能说它"永远正确"吗？不能——测试只能证明有 bug，不能证明没有 bug。证明是你走向程序正确性的唯一可靠路径。这一章的目的是掌握几种通用的证明策略，让你能从"我觉得是对的"走向"我知道它一定成立"。
本章分层
- 必读：直接证明，反证法，数学归纳法
- 选读：构造性证明与非构造性证明
破局 · 溯源
你在代码评审中发现同事写了一个优化："这个块永远不可能被空指针异常影响，因为前面已经检查过了。"如何确定他说的"永远不可能"是真的？你下意识做的是心理逻辑推导。这里需要的正是形式化的证明思路——不是直觉，是链条。
证明的核心结构是：已知为真的前提 → 逻辑推理 → 结论。这一章不涉及高深定理的证明，而是四种基本范式。
1. 直接证明
从前提出发，经过一系列逻辑推理到达结论。
定理：如果 n 是偶数，则 n² 也是偶数。
证明：n 是偶数，所以 n = 2k (k 为整数)。n² = (2k)² = 4k² = 2(2k²)。所以 n² 是偶数。
这是最简洁也最直接的证明形式。你从前提 n 是偶数出发，用偶数的定义（存在整数 k 使 n=2k），做代数和算术，得出结论。
2. 反证法
假设结论为假，推导出与已知前提的矛盾。证明必须放弃"结论为假"的假设。
定理：√2 是无理数。
证明是一个经典反证。假设 √2 是有理数，即 √2 = p/q（p, q 互质整数）。两边平方得 2 = p²/q²，即 p² = 2q²。所以 p² 是偶数，p 是偶数，设 p = 2k。代入得 (2k)² = 2q²，即 4k² = 2q²，所以 q² = 2k²，q 是偶数。p 和 q 都是偶数，与 p/q 最简分数（互质）矛盾。假设不成立，√2 是无理数。
反证法在算法分析中非常有用——比如证明"没有基于比较的排序算法能优于 O(n log n)"，就是先假设存在一个更优的，然后导出矛盾。
3. 构造反例
证明一个命题是假的——只需一个反例。
命题："所有质数都是奇数。" 反例：2 是质数，但 2 是偶数。命题为假。
构造反例是程序员最熟悉的"证明"方式——你在找 bug 时做的实际就是这个。
4. 数学归纳法
证明一个关于自然数的命题对所有 n 都成立。两步：
- 基础情况：证明 P(0) 或 P(1) 成立。
- 归纳步骤：假设 P(k) 成立，证明 P(k+1) 成立。
这是递归结构的形式化证明。如果你的代码用递归实现，数学归纳法就是证明它正确的自然工具。
示例：证明 1 + 2 + ... + n = n(n+1)/2。
基础：n=1，左边=1，右边=1(2)/2=1。成立。 归纳：假设 1+...+k = k(k+1)/2。则 1+...+k+(k+1) = k(k+1)/2 + (k+1) = (k(k+1) + 2(k+1))/2 = (k+1)(k+2)/2。成立。
归纳法和你调试递归函数的方式几乎一模一样：先确认基本情况正确（base case），然后假设递归调用正确（归纳假设），再验证当前层是否组合正确。
常见陷阱
- 归纳法中忘记证明基础情况。即使归纳步骤完全正确，基础情况不成立则整个证明失效。
- 反证法中的矛盾不是真正的矛盾。"这不合理"不是数学矛盾——必须是与已知前提或公理直接冲突。
- 循环论证：用结论来证明结论。比如"这个数能被 3 整除，因为它是 3 的倍数"——你要证明的正是"它是 3 的倍数"。
通关挑战
- 用直接证明证明：如果 m 和 n 都是偶数，则 m + n 是偶数。
- 用反证法证明：不存在最大的整数。
- 用归纳法证明：前 n 个奇数的和为 n²。
旅人笔记
证明是从"我觉得它是对的"到"我知道它一定对"的桥梁。四种方法——直接、反证、反例、归纳——覆盖了计算机科学中 90% 的证明场景。
→ 下一站预告：证明给了你推理的框架。但许多程序的结构本质上是递归的——函数调自己，数据引用自己。下一章我们把这种"自指"的结构搞明白。