第 4 章 · 证明方法

证明 = 用逻辑规则把结论从公理/已知事实推出來的完整推理序列。它的价值不是「数学仪式」,而是确定性本身:程序的正确性论证、算法的复杂度下界、密码学的安全归约,全是证明。本章讲四种基本方法(直接、反证、归纳、构造)各自的适用场景和典型病,目标是让你面对「请证明……」时有一套启动流程,而不是空对空地发呆。

4.1 直接证明:从定义出发的推土机

最朴素也最常用的方法:从定义和已知定理出发,一步步推到结论。示范一个数据结构课用过的命题:两个偶数之和是偶数。

设 m = 2a,n = 2b(a、b 为整数)。则 m + n = 2a + 2b = 2(a + b),由偶数定义,m + n 是偶数。∎

三步走完:设(引入符号精确化)→ 变形(代数操作)→ 对定义(回扣定义)。直接证明的适用信号:结论是「某物具有某性质」这种肯定句,且定义链条足够短。它的核心技巧是**「按定义展开」**:大多数卡壳,是因为没把「偶数」「整除」「连续」这些词展开成形式定义。证明的第一动作永远是:把所有词换成定义。

4.2 反证法:把「不可能」推成矛盾

要证 p,先假设 ¬p,推出矛盾(¬q 与 q 同时成立,或与已知事实冲突),则 ¬p 不成立,p 成立。合法性由第 2 章背书:¬p → (q ∧ ¬q) 恒假,等价于 p 永真。

经典示范:√2 是无理数。假设 √2 = p/q(最简分数),则 2q² = p²,故 p 偶(p² 偶则 p 偶,用奇偶性引理),设 p = 2k,得 2k² = q²,故 q 偶;p、q 都偶,与「最简分数」矛盾。∎

反证法的适用信号:结论是否定式或**「不存在/唯一」类**(√2 不是分数、素数无穷多、没有最小正实数)。生活里它的影子:排除法。一个重要的变体:证逆否(第 2 章 p→q ≡ ¬q→¬p),当直接证 p→q 卡壳时,「假设 q 不成立,推出 p 不成立」常常一马平川——「若 n² 是偶数则 n 是偶数」直接证要分类讨论,逆否「n 奇则 n² 奇」一行就完。

4.3 数学归纳法:对付「无穷多」的武器

要证对所有自然数成立(∀n P(n)),逐一验证不可能(无穷),归纳法两步:

基础步:P(0)(或 P(1))成立;
归纳步:假设 P(k) 成立(归纳假设),推出 P(k + 1) 成立。

由第 2 章「∀k (P(k) → P(k+1)) ∧ P(0) → ∀n P(n)」的永真性,两步完成对无穷的覆盖。示范:1 + 3 + 5 + … + (2n−1) = n²。

基础:n = 1 时左边 1 = 右边 1。归纳:设前 k 个奇数和为 k²,加第 k+1 个奇数:(k²) + (2k+1) = k² + 2k + 1 = (k+1)²。∎

(这个等式还有一行「无字证明」:奇数点阵摆 L 形,每个 L 恰补成下一个平方,数形结合的直观。数学的两个方向:严格性归归纳,直觉归图。)

归纳的常见姿势:二阶归纳(依赖前两个,如斐波那契公式)、强归纳(假设所有 ≤k 都成立,用于整除/算法终止性证明)、结构归纳(对树/表达式递归结构归纳,编译器课第 5 章 AST 的性质、数据结构课第 9 章递归的正确性,全靠它)。归纳假设当自由使用但别偷偷加强:证 1/(1×2) + 1/(2×3) + … + 1/(n(n+1)) = n/(n+1) 时,常见错误是「设和为 k²」(抄了上一题的假设)——归纳假设必须来自你要证的那个命题本身。

4.4 构造性与存在性证明

存在性命题(∃x P(x))两种证法:构造(真的找出一个 x)与非构造(证「不存在会矛盾」,但没告诉你是谁)。构造性强很多(算法课的「证明 = 算法」:说「存在解」不如给出找到解的程序),非构造在组合数学里也大量存在(如「两人朋友数相同的生日悖论式论证」,第 5 章)。

** iff(当且仅当)证明**:p ↔ q 要两个方向都证(p→q 与 q→p),漏一半是最常见的考场事故。分情况证明(case analysis):按对象的类别(奇偶、正负、模 3 余数)穷举每类,穷举要完备且互斥——「完备且互斥」四个字,既是证明的纪律,也是写 switch 语句(Java 课第 3 章)的纪律。

4.5 证明的写作:给读者台阶

证明是写给「怀疑的读者」的,写作规范:每一步有依据(定义/已知定理/归纳假设),引入的符号有声明(「设 m = 2a,其中 a ∈ ℤ」),关键跳步给出理由。「显然」这个词要慎用(你显然,读者懵);一个练习方法:给自己的证明隔一周再读,哪里卡住哪里补。

常见错误

归纳步直接用结论。P(k+1) 的证明里写了「由 P(k+1) 可知……」;循环论证,最隐蔽的错误。
基础步忘了或从 0/1 数错。归纳法两根柱子,基础步不成立全盘崩(「所有马同色」的著名谬误:归纳步在 k=1 处断了)。
反证法只推到「不合理」。「不合理」不是矛盾;要推到逻辑矛盾(q ∧ ¬q)或与已知定理冲突。
iff 只证一个方向。写「必要性」「充分性」两个小标题,强迫自己配平。

练习

证明:对任意整数 n,n² 与 n 奇偶性相同(分情况:n 偶/n 奇,两种都推)。
用归纳法证明:2ⁿ > n² 对一切 n ≥ 5 成立(基础步从 5 起,归纳步要处理「k=5 边界后」的不等式放大)。
反证:证明素数有无穷多个(Euclid:设有限个 p₁…pₖ,构造 p₁×…×pₖ+1,讨论它的素因子)。
动手:用归纳法证明「含 n 个结点的满二叉树有 n−1 条边」(数据结构课第 5 章的结论),再用「结构归纳」对「任意表达式的括号数匹配」证明一次,对比两种归纳的「归纳对象」差异。