本节对应原书 PDF 第 26–31 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
在数学中，为了说明一个命题是真命题需要进行证明. 要证明的命题有 3 种形式：
形式 1 若 A，则 B. 可表示成 A \rightarrow B，其中 A 是前提或已知条件，B 是结论.
形式 2 A 的充分必要条件是 B，或 A 当且仅当 B. 可表示成 A \leftrightarrow B.
形式 3 B（即 B 恒真）.
由于“A 的充分必要条件是 B”等价于“若 A，则 B，并且若 B，则 A.” 即 A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \wedge (B \rightarrow A)，故形式 2 可以化成形式 1. 而形式 3 可以看成形式 1 的特殊情况——没有前提 A，也可以把它表示成 1 \rightarrow B，即前提恒真. 要证形式 1 的命题为真，是要证明当 A 为真时，B 一定为真. 而对于形式 3 的命题，是要证 B 一定为真，这里没有前提 A. 可见，后两种形式都可以归结为形式 1.
“若 A，则 B.” 的证明是在假设前提 A 为真的情况下，利用已知的定义、定理、引理和推论，按照推理规则推导出结论 B 为真的过程. 所谓定理是已经被证明的真命题. 当然，只有那些重要的真命题才能成为定理. 引理和推论也是已被证明的真命题，区别在于引理是为了证明某个定理而预先证明的真命题，而推论是由定理能够立即得到的真命题. 在证明中有时还要使用公理. 数学中的公理方法是古希腊欧几里得首创的. 他在《几何原本》中从少数几个定义、公理出发，通过逻辑推理获得一系列的几何定理，建立起几何学的公理系统. 公理系统不仅使知识系统化，而且也是为了消除数学中的逻辑隐患. 公理是公理系统中的原始假设，即不加证明地承认它们. 它们中的绝大多数是被人们普遍接受的事实. 但是，也有例外，如在欧几里得几何中有一条平行公理：“如果两条直线和第三条直线相交且在同一侧所构成的两个内角之和小于二直角，那么这两条直线向这一侧适当延长后一定相交”，它等价于另一种大家所熟悉的叙述：“在平面上，过一直线外的一点可引一条而且只有一条和这直线不相交的直线”. 平行公理并不明显，人们一直想用其他公理推出它，但都失败了. 直到 19 世纪中叶，高斯、罗巴切夫斯基等数学家认识到这种努力是不可能实现的，也就是说平行公理独立于其他公理，并且可以用不同的“平行公理”代替它而建立不同的几何学. 罗巴切夫斯基和波尔约用一条新的公理“在平面上，过一直线外的一点可引无数条和这直线不相交的直线”代替欧几里得平行公理，创建了一种新的非欧几何，现在称为罗巴切夫斯基几何，又称双曲几何. 接着，黎曼又创建了另一个不同的非欧几何，他用来代替平行公理的公理是“在平面上，过一直线外的一点所引的任何直线都与这直线相交”. 这就是黎曼几何，又称椭圆几何.
证明方法不仅是数学研究中不可或缺的，而且在计算机科学中有广泛的应用，例如计算机推理所用的规则、程序正确性证明的技术、人工智能中的推理等. 本节非形式地介绍常用证明方法，在 2.4 节将做进一步的说明.
解读：三种命题形式其实只有一种需要真正去证。形式 2 拆成两个方向就变成形式 1；形式 3 是没有前提的形式 1。所以"怎么证 A \rightarrow B"是本节所有方法的共同落点。
1.3.1 直接证明法和归谬法
直接证明法 设命题 P：若 A，则 B，即 A \rightarrow B. 直接证明法是假设 A 为真，利用已知的定义、定理、引理和推论，可能还有公理，推出 B 为真的结论，从而证明 P 为真. 直接证明法是最常用的证明方法. 例 1.5 ～ 1.8 都是用直接证明法进行证明的.
归谬法（反证法） 归谬法是从假设 A 为真、B 为假，推出矛盾. 这就说明当 A 为真时，B 必为真，从而证明 P 为真. 归谬法也是常用的证明方法. 例 1.4（3）就是用归谬法证明的. 下面再举一个用归谬法证明的例子.
例 1.10 证明：不存在最大的素数.
证明 使用归谬法. 假设不然，即假设存在最大的素数，设为 p，则所有素数均大于等于 2，并且小于等于 p. 令 S 为所有素数之积，即
又设
易知，用 2 到 p 的所有素数去除 S'，所得余数全是 1. 这说明 S' 的正因子只有 1 与自己，故 S' 是素数. 可是 S' > p，这与 p 是最大的素数矛盾. 得证不存在最大的素数.
间接证明法 把 P 的逆否命题记作 P'：若非 B，则非 A，即 \neg B \rightarrow \neg A. P 与 P' 同时为真，或同时为假，即 P \Leftrightarrow P'. 因此可以通过证明 P' 来证明 P. 这就是间接证明法.
例 1.11 证明：完全数不是素数.
等于除本身外所有正因子之和的正整数称作完全数. 例如，6 = 1 + 2 + 3，28 = 1 + 2 + 4 + 7 + 14，均为完全数.
证明 用间接证明法证明. 它的逆否命题是：素数不是完全数. 设 n 是素数，显然 n \geqslant 2. 除本身外，n 只有一个正因子 1. 而 n \neq 1，故 n 不是完全数. 得证原命题成立，即完全数不是素数.
间接证明法可以看作是归谬法的特殊形式. 假设 \neg B 为真，推出 \neg A 为真，即 A 为假. 这与假设 A 为真矛盾.
解读：归谬法与间接证明法容易混。归谬法是"假设 A 真且 B 假，推出矛盾"；间接证明法是"改证逆否命题 \neg B \rightarrow \neg A"。原书点明后者是前者的特殊形式——因为从 \neg B 推出 \neg A，正是让"A 真且 B 假"这个假设自相矛盾。
1.3.2 分情况证明法和构造性证明法
分情况证明法（穷举法） 若前提 A 可以分成若干种情况 A_1, A_2, \cdots, A_k，那么只要证明对每一个 i(1 \leqslant i \leqslant k)，当 A_i 为真时，B 为真，就可得到当 A 为真时，B 为真. 这是因为 A 为真，必有一个 A_i 为真. 这样就把证明“若 A，则 B”转化为证明 k 个命题“若 A_i，则 B”，i = 1, 2, \cdots, k.
例 1.12 证明：\max(a, \max(b, c)) = \max(\max(a, b), c).
证明 a, b, c 的大小关系有并且只有下面 6 种情况：
情况 1 \quad a \leqslant b \leqslant c；
情况 2 \quad a \leqslant c \leqslant b；
情况 3 \quad b \leqslant a \leqslant c；
情况 4 \quad b \leqslant c \leqslant a；
情况 5 \quad c \leqslant a \leqslant b；
情况 6 \quad c \leqslant b \leqslant a.
对于情况 1，\max(a, \max(b, c)) = \max(a, c) = c，\max(\max(a, b), c) = \max(b, c) = c，两者相等.
对于情况 2，\max(a, \max(b, c)) = \max(a, b) = b，\max(\max(a, b), c) = \max(b, c) = b，两者相等.
类似可证情况 3 至情况 6，结合律都成立. 得证原命题成立.
例 1.13 证明：若 3 \nmid n，则 n^2 \equiv 1 \pmod 3.
证明 若 3 \nmid n，则存在 k，使得 n = 3k + 1 或 n = 3k + 2. 当 n = 3k + 1 时，
由此式可知，n^2 \equiv 1 \pmod 3.
当 n = 3k + 2 时，
同样有 n^2 \equiv 1 \pmod 3. 得证原命题成立.
构造性证明法 有时要证明存在一种具有某种性质的客体. 对此有两种证明方法. 一种是构造出具有所需性质的客体，从而证明了它的存在性，这种证明方法称作构造性. 另一种是仅仅证明了它的存在，而没有具体的给出它，称这种证明方法为非构造性的.
例 1.14 对于任意的自然数 n，存在大于 n 的素数.
证明 这是例 1.10 的推论，这里给出它的独立的证明. 类似前面的证明，令 S' 等于所以小于等于 n 的素数之积加 1. 于是，要么 S' 是素数，要么 S' 被大于 n 的素数整除. 总之，存在大于 n 的素数.
这是非构造性证明. 这个证明确实证明了存在大于 n 的素数，但是它并没有提供找到这样的素数的方法.
下面是构造性证明的例子.
例 1.15 证明：对于每个正整数 n，都存在 n 个连续的正合数.
证明 设 x = (n + 1)! + 1，考虑如下的 n 个连续的正整数
对于 i(i = 1, 2, \cdots, n)，x + i = (n + 1)! + (1 + i)，注意到 (n + 1)! 中含有因子 (1 + i)，所以 x + i 中含因子 (1 + i). 而 1 + i 不等于 1，也不等于 x + i，故 x + i 是合数. 所以，x + 1, x + 2, \cdots, x + n 是 n 个连续的正合数.
这个证明是构造性的. 它不仅证明了存在这样的正合数，而且根据证明可以对任给的正整数 n，构造出 n 个连续的正合数. 例如，当 n = 3 时，x = (3 + 1)! + 1 = 25. 26，27，28 是 3 个连续的正合数.
下面介绍两种比较特殊的证明方法，它们可能会在将要介绍的数学归纳法的归纳基础中使用.
前提假证明法（空证明法） 如果前提 A 为假，则命题“若 A，则 B”为真. 如某人发誓：如果太阳从西边出来，我就把脑袋给你. 其实，由于太阳永远不会从西边出来，所以不管他把不把脑袋给你都没错. 也就是说，如果前提不成立，你说什么都可以. 因此，如果能证明前提为假，也就证明了命题为真，而不必管结论是否为真. 这种通过证明前提为假来证明命题为真的证明方法称作前提假证明法或空证明法.
例 1.16 设 n \in \mathbf{N}，记 P(n)：若 n > 1，则 n^2 > 1. 试证明 P(0) 为真.
证明 P(0)：若 0 > 1，则 0^2 > 1. 因为此蕴涵式前件 0 > 1 为假，所以蕴涵式为真，即 P(0) 为真.
结论真证明法（平凡证明法） 如果能证明结论为真，而不管前提真假，那么命题一定为真. 这种通过在不假设前提为真的情况下证明结论为真来证明命题为真的方法称作结论真证明法或平凡证明法.
例 1.17 设 n \in \mathbf{N}，a > 0，b > 0，记 P(n)：若 a \geqslant b，则 a^n \geqslant b^n. 试证明 P(0) 为真.
证明 P(0)：若 a \geqslant b，则 a^0 \geqslant b^0. 因为 a^0 = b^0 = 1，所以 P(0) 为真.
在这个证明中，并没有用到条件 a \geqslant b.
解读：空证明法与平凡证明法是数学归纳法归纳基础的常用手段——归纳基础往往取 n_0 = 0，此时前提可能根本不成立（例 1.16）或者结论自动为真（例 1.17），于是无需真正推导。
1.3.3 数学归纳法
通过观察、发现规律、给出猜想，进而进行严格的数学证明，使猜想成为定理，是数学研究的一种方法. 例如，观察到
\vdots
猜想：前 n 个奇数之和等于 n^2，即
此时还不能认为这个式子一定成立，需要证明. 对于这类与正整数有关的性质，数学归纳法是常用的证明方法.
数学归纳法原理 设命题 P(n)，n \in \mathbf{N} 且 n \geqslant n_0. 若
（1）P(n_0) 为真，
（2）\forall n(n \in \mathbf{N} 且 n \geqslant n_0)，假设 P(n) 为真，则 P(n + 1) 为真，
那么，\forall n(n \in \mathbf{N} 且 n \geqslant n_0)，P(n) 为真.
最常遇到的是 n_0 = 0 和 n_0 = 1，即要证的命题是 \forall n \in \mathbf{N}，P(n) 和 \forall n \in \mathbf{Z}^+，P(n).
直观上，已知 P(n_0) 为真，由 P(n_0) 真推出 P(n_0 + 1) 真，由 P(n_0 + 1) 真推出 P(n_0 + 2) 真，\cdots，所以对所有的自然数 n \geqslant n_0，P(n) 真.
严格地说，数学归纳法原理的基础是自然数集 \mathbf{N} 的良序性，即 \mathbf{N} 的任何非空子集都有最小的数. 如 \mathbf{N} 的最小数是 0，\mathbf{Z}^+ 的最小数是 1，偶数集的最小数是 2，\{10, 15, 16, 21\} 的最小数是 10.
假设数学归纳法原理不正确，那么存在 n(n \in \mathbf{N} 且 n \geqslant n_0)，使得 P(n) 为假. 令
则 F \neq \varnothing. 由 \mathbf{N} 的良序性，F 有最小数，设为 a. 若 a = n_0，由原理的（1），P(n_0) 为真，这与 n_0 \in F 矛盾. 若 a > n_0，那么 a - 1 \notin F 且 a - 1 \geqslant n_0，从而 P(a - 1) 为真. 于是，由原理的（2），可推出 P(a) 为真. 这与 a \in F 矛盾.
数学归纳法的证明步骤
（1）归纳基础：证明 P(n_0) 为真；
（2）归纳步骤：对任意的自然数 n \geqslant n_0，假设 P(n) 为真，证明 P(n + 1) 为真，
其中“假设 P(n) 为真”称作归纳假设，注意在这里 n 是一个任意固定的自然数.
现在证明前面提出的猜想.
例 1.18 证明：1 + 3 + 5 + \cdots + (2n - 1) = n^2.
证明 用数学归纳法证明.
归纳基础：n = 1 时，1 = 1^2.
归纳步骤：假设当 n \geqslant 1 时等式成立，考虑 n + 1 的情况，
即当 n + 1 时等式也成立. 得证对任意的正整数 n，等式成立.
例 1.19 证明：n(n \geqslant 0) 元集 A 的幂集 P(A) 有 2^n 个元素.
证明 这是定理 1.2，在 1.2 节已证明过，现在用数学归纳法证明.
归纳基础：当 n = 0 时，A = \varnothing，P(A) = \{\varnothing\}，|P(A)| = 1 = 2^0. 结论成立.
归纳步骤：假设对任意的 n \geqslant 0，当 |A| = n 时，|P(A)| = 2^n. 现考虑 |A| = n + 1 的情况. 因为 n + 1 > 0，A \neq \varnothing，任取 a \in A，令 A' = A - \{a\}，则 |A'| = n. 根据归纳假设，|P(A')| = 2^n. A 的子集或者不含 a（即是 A' 的子集），或者含 a. 不难看出，含 a 的子集和不含 a 的子集一一对应，从而这两个子集的个数相等. 根据归纳假设，不含 a 的子集，即 A' 的子集共有 2^n 个. 因此
得证对结论 n + 1 也成立. 由数学归纳法原理，原命题成立.
例 1.20 证明：可以仅用 4 分和 5 分邮票组成等于或超过 12 分的所有邮资.
证明 用数学归纳法证明. 设 n 分邮资，其中 n \geqslant 12.
归纳基础：当 n = 12 时，可用 3 张 4 分邮票组成 12 分邮资，故结论成立.
归纳步骤：假设当 n \geqslant 12 时结论成立，要证明对 n + 1 结论也成立. 根据归纳假设，可用 4 分邮票和 5 分邮票组成 n 分邮资. 分情况讨论如下：
（1）n 分邮资中含有 4 分邮票. 此时用 1 张 5 分邮票代替 1 张 4 分邮票，得到 n + 1 分邮资.
（2）n 邮资中不含 4 分邮票. 因为 n \geqslant 12，因而至少含 3 张 5 分邮票. 用 4 张 4 分邮票取代 3 张 5 分邮票，得到 n + 1 分邮资.
得证对 n + 1 结论也成立. 由数学归纳法原理，命题成立.
数学归纳法还有另一种形式——第二数学归纳法. 相对应地，也称前面介绍的数学归纳法为第一数学归纳法.
第二数学归纳法原理 设命题 P(n)，n \in \mathbf{N} 且 n \geqslant n_0. 若
（1）P(n_0) 为真；
（2）\forall n(n \in \mathbf{N} 且 n \geqslant n_0)，假设 P(n_0)，P(n_0 + 1)，\cdots，P(n) 为真，则 P(n + 1) 为真，
那么，\forall n(n \in \mathbf{N} 且 n \geqslant n_0)，P(n) 为真.
可以类似地利用自然数集的良序性证明第二数学归纳法原理.
第二数学归纳法的证明步骤
（1）归纳基础：证明 P(n_0) 为真，
（2）对任意的 n \geqslant n_0，假设 P(n_0)，P(n_0 + 1)，\cdots，P(n) 为真，证明 P(n + 1) 为真.
例 1.21 证明：所有大于等于 2 的整数都可以写成素数之积.
证明 用第二数学归纳法证明.
归纳基础：2 是素数，2 = 2，这表明 2 可以写成素数之积.
归纳步骤：对任意的自然数 n \geqslant 2，假设 2, 3, \cdots, n 都可以写成素数之积，要证明 n + 1 也可以写成素数之积. 分情况讨论如下：
（1）n + 1 为素数. 此时 n + 1 本身就是素数之积的形式.
（2）n + 1 为合数. 此时存在整数 a, b，且 2 \leqslant a, b \leqslant n，使得 n + 1 = a \cdot b. 因为 2 \leqslant a, b \leqslant n，由归纳假设，a 与 b 都可以写成素数之积. 于是，n + 1 也可以写成素数之积.
由第二数学归纳法原理可知，原命题成立.
解读：第一与第二数学归纳法的差别只在归纳假设的强弱。第一归纳法只假设 P(n)，第二归纳法假设 P(n_0), \cdots, P(n) 全部成立。当证明 P(n+1) 需要用到更早的项（例如例 1.21 要把 n+1 拆成 a \cdot b，而 a, b 可能远小于 n）时，就必须用第二归纳法。