证明¶

CS70 Note 2 | UC Berkeley

在科学领域，人们通过实验积累数据来断言某个命题的正确性，而数学则追求更高层次的确定性——数学证明能确保命题必然为真，且在某种程度上类似于计算机程序。

学习证明的目标是学会针对不同的定理给出清晰简洁的证明，本节内容将通过观察不同的证明实例来学习不同的证明方法并达成这一目标。

直接证明法¶

对于任意整数 \(a\), \(b\), \(c\)，如果 \(a\ |\ b\)¹ 且 \(a\ |\ c\)，则 \(a\ |\ (b+c)\)

Review

设 \(P(x, y) =\) "\(x\ |\ y\)"，则上述命题等价于

\[ (\forall a, b, c \in \mathbb{Z})(P(a, b) \land P(a, c) \Rightarrow P(a, b+c)) \]

从高层次来看，直接证明的步骤如下：

对于每个 \(x\)，我们要证明的命题均具有 \(P(x) \Rightarrow Q(x)\) 的形式。直接证明的方式首先假设 \(P(x)\) 对某个通用 \(x\) 值成立，最终通过一系列蕴含关系得出 \(Q(x)\) 的结论：

直接证明法（Direct Proof）

目标：证明 \(P \Rightarrow Q\)

方法：假设 \(P\) 成立

\[ ..... \]

因此 \(Q\) 得证
- 关于该定理的证明如下：
  
  设 \(a\ |\ b\) 且 \(a\ |\ c\)，即存在整数 \(q_1\) 和 \(q_2\) 使得 \(b = aq_1\) 且 \(c = aq_2\)。
  
  于是有 \(b + c = aq_1 + aq_2 = a(q_1 + q_2)\)。
  
  由于整数集 \(\mathbb{Z}\) 对加法封闭²，可得 \((q_1 + q_2) \in \mathbb{Z}\)，故 \(a\ |\ (b+c)\) 得证。
Tip

在上述的证明中，我们并没有限定 \(a\), \(b\), \(c\) 的具体取值，故该证明适用于任意整数，也就对应了 review 中的 \((\forall a, b, c \in \mathbb{Z})\)
设 \(0 < n < 1000\) 为整数。若 \(n\) 的各位数字之和能被 \(9\) 整除，则 \(n\) 也能被 \(9\) 整除。

Review

该命题等价于

\[ (\forall n \in \mathbb{Z}^{+})(n <1000) \Rightarrow (n \text{的各位数字之和能被 9 整除} \Rightarrow n \text{能被 9 整除}) \]

我们的证明思路是：首先假设对于任意 \(n\) 值，其各位数字之和能被 \(9\) 整除，然后通过一系列推导得出 \(n\) 本身也能被 \(9\) 整除的结论。

证明如下：

令 \(n = 100a + 10b + c\)。假设 \(n\) 的各位数字之和能被 \(9\) 整除，即

\[ \exists k \in \mathbb{Z}\ \text{使得}\ a+b+c = 9k\ \ \ \ \ (1) \]

在等式 \((1)\) 两侧同时加上 \(99a + 9b\)，可得

\[ 100a + 10b + c = n = 9k + 99a + 9b = 9(k + 11a + b) \]

故定理\(2\) 得证。

3.（定理\(2\) 的逆定理）设 \(0 < n < 1000\) 为整数。若 \(n\) 能被 \(9\) 整除，则 \(n\) 的各位数字之和也能被 \(9\) 整除。

证明如下：

\[ \begin{aligned} n \text{能被} 9 \text{整除} & \Rightarrow \exists l \in \mathbb{Z}\ \text{使得}\ n = 9l \newline & \Rightarrow 100a + 10b + c = 9l \newline & \Rightarrow 99a + 9b + (a + b + c) = 9l \newline & \Rightarrow a + b + c = 9l - 99a - 9b \newline & \Rightarrow a + b + c = 9(l - 11a - b) \newline & \Rightarrow \exists k = l - 11a - b \in \mathbb{Z}\ \text{使得}\ a + b + c = 9k \newline \end{aligned} \]

故定理\(3\) 得证。

Important

从定理\(2\) 与定理\(3\) 的证明可以得出：当且仅当整数 \(n\) 本身能被 \(9\) 整除时，\(n\) 的各位数字之和也能被 \(9\) 整除，即定理2 与定理3 在逻辑上等价。

当需要证明等价关系 \(P \Leftrightarrow Q\) 时，务必分别证明 \(P \Rightarrow Q\)（充分性）和 \(Q \Rightarrow P\)（必要性）

逆否命题证明法¶

逆否命题证明法（Proof by Contraposition）

目标：\(P \Rightarrow Q\)

方法：假设 \(\neg Q\) 成立

\[ ..... \]

故 \(\neg P\) 成立

结论：\(\neg Q \Rightarrow \neg P\)，等价于 \(P \Rightarrow Q\)

在学习命题逻辑时我们得知，任何蕴涵式 \(P \Rightarrow Q\) 都等价于其逆否命题 \(\neg Q \Rightarrow \neg P\)。在一些情况下，证明 \(\neg Q \Rightarrow \neg P\) 会比直接证明 \(P \Rightarrow Q\) 容易得多，因此在这些情况下我们就可通过证明这个命题的逆否命题来等价地证明它的原命题。

设 \(n\) 是正整数，且 \(d\) 整除 \(n\)。若 \(n\) 为奇数，则 \(d\) 也为奇数。

若使用直接证明法，在假设 \(n \in \mathbb{N}^{+}\) 且 \(n\) 为奇数后，我们似乎就无法继续推动证明了——但采用逆否命题证明法就显得简单得多。

Review

设 \(P(x, y) =\) "\(x\ |\ y\)"，则对于该定理，其逻辑形式等价于：

\[ (\forall n, d \in \mathbb{N}^{+})(P(d, n)) \Rightarrow (n \in \{x \in \mathbb{N}^{+}\ |\ \exists k \in \mathbb{N}^{+}, x = 2k - 1\} \Rightarrow d \in \{x \in \mathbb{N}^{+}\ |\ \exists k \in \mathbb{N}^{+}, x = 2k - 1\}) \]

由于对于一个正整数而言，其不是奇数就是偶数，故其对应的逆否命题如下：

\[ (\forall n, d \in \mathbb{N}^{+})(P(d, n)) \Rightarrow (d \in \{x \in \mathbb{N}^{+}\ |\ \exists k \in \mathbb{N}^{+}, x = 2k\} \Rightarrow n \in \{x \in \mathbb{N}^{+}\ |\ \exists k \in \mathbb{N}^{+}, x = 2k\}) \]

即“若 \(d\) 是偶数，则 \(n\) 也是偶数”

Tip

在证明时在行首标注此次证明采用的证明方法是一个良好实践，这样起到与代码注释类似的作用

证明如下：

使用逆否命题证明法

假设 \(d\) 是偶数，由定义可知 \(\exists k \in \mathbb{Z}\) 使得 \(d = 2k \hspace{6.8cm} (1)\)

又由于 \(d\ |\ n\)，故有 \(\exists l \in \mathbb{Z}\) 使得 \(n = dl \hspace{6.9cm} (2)\)

联立 \((1)\ (2)\) 可得 \(n = dl = (2k)l = 2(kl)\)

由此可证 \(n\) 为偶数

下面来看一个典型定理的逆否证法示例：

(鸽巢定理) 设 \(n\) 和 \(k\) 为正整数。将 \(n\) 个物体放入 \(k\) 个盒子中，若 \(n > k\)，则至少有一个盒子必须包含多个物体。

该定理的名称来源于想象这 \(n\) 个物体是🕊，而我们试图将它们放入鸽巢中
- 证明如下：
  
  使用逆否命题证明法
  
  若一个盒子最多包含一个物体，则物体数量最多等于盒子数量，即 \(n \leqslant k\)。
Tip

尽管该定理的表述与证明看上去十分简单，但在某些方面的应用或许超乎人们的想象：无论盒子中物体的配置方式如何，结论都成立——当物体以某种复杂的方式放入盒子时，该定理的结论可能具有非凡意义。

生活中一个简单的基于该定理的实例就是“同年同月同日生”问题：假设一个群体的人数大于等于 \(366\) 人，且他们出生于同一年份（这里以平年为例），那么我们就可以断定至少有两个人是“同年同月同日生”的。

反证法¶

反证法（Proof by Contradiction）

目标：证明命题 \(P\) 成立

方法：假设 \(\neg P\) 成立

\[ ...... \]

\[ \Rightarrow R \]

\[ ...... \]

\[ \Rightarrow \neg R \]

结论：\(\neg P \Rightarrow \neg R \land R\)，矛盾，故 \(P\) 成立

反证法的核心思路是，假设待证明的命题不成立，随后以此为基础推导出一个与命题的前提条件相悖或是其他荒谬的结论，即“归谬”——这是一个极具魅力的技巧。

Review

反证法最为关键的依据就是排中律，即对于任意命题，其真值非真即假。这我们在上一章的学习中有所提及。

以下是反证法的形式化推理：

对于任意命题 \(P\)，假设其否定成立且蕴含命题 \(R\)，则有

\[ \neg P \Rightarrow \neg R \land R \equiv \text{False} \]

将该蕴含关系转化为其逆否命题，则有

\[ \text{True} \Rightarrow P \]

下面来看实例：

存在无数个素数。

在证明该定理前，我们可以首先思考是否能够采用前面学习过的证明方法，例如直接证明法。然而，这看起来似乎寸步难行——我们应该怎样构造无数个素数（逻辑构造的复杂性使得逆否命题证明法也难以应用）呢？此时，反证法的精妙之处也就凸显出来了——我们可以在待证命题正向逻辑难以推导的情况下假设这个命题结论的否定，这样我们就可以以逆向逻辑来完成逻辑推导的过程（这里就是得出假设与已知事实矛盾的过程）。

证明该定理时需要使用一个引理，其证明会在学习数学归纳法时提及：
- 每个大于 \(1\) 的自然数要么是一个素数，要么具有一个素因数。
- 证明如下：
  
  使用反证法
  
  假设该命题不成立，即只存在有限个素数，令其为命题 \(P\)，并假设其数量为 \(k\)，则可将其枚举为：
  
  \[ p_1,\ p_2,\ p_3,\ ...,\ p_k \]
  
  现定义数 \(q = p_1 \cdot p_2 \cdot p_3 ... p_k + 1\)，即所有素数的乘积加一。由于其大于所有素数，故其不可能是素数。
  
  根据引理可得，\(q\) 存在一个素因数 \(p\)，令其为命题 \(R\)。
  
  又由于 \(p_1,\ p_2,\ p_3,\ ...,\ p_k\) 以包含所有素数，\(p\) 必等于其中之一；故 \(p\) 能整除数 \(r = p_1 \cdot p_2 \cdot p_3 ... p_k\)
  
  于是有 \(p\ |\ q \land p\ |\ r\)，由前文我们证明的定理可得 \(p\ |\ (q - r)\)。
  
  又由假设得 \(q - r = 1\)，综 \((q - r) = pk,\ k \in \mathbb{N}^{+}\) 可得 \(p \leqslant 1\)，因此 \(p\) 不是素数，即构成命题 \(\neg R\)。
  
  此时即有 \(P \Rightarrow R \land \neg R\)，构成矛盾，故原命题得证。
\(\sqrt{2}\) 是无理数。

证明该定理同样需要一个引理：
- 若 \(a^2\) 是偶数，则 \(a\) 也是偶数。
- 证明如下：
  
  使用反证法
  
  要证明"\(\sqrt{2}\) 是无理数"，即证"不存在满足条件的整数 \(a\) 和 \(b\)，使得 \(\sqrt{2} = a / b\)"。
  
  假设该命题不成立，即存在互质的整数 \(a\) 和 \(b\) 使得 \(\sqrt{2} = a / b\)，令其为命题 \(P\)。不妨设命题 \(R =\) "\(a\) 与 \(b\) 没有除 \(1\) 以外的公因数"。
  
  对于任意整数 \(x\)、\(y\)，易得 \(x = y \Rightarrow x^2 = y^2\)。代入 \(\sqrt{2} = a / b\) 有 \(2 = a^2 / b^2\)，即 \(a^2 = 2b^2\)。
  
  此时，由于 \(b\) 是整数，易得 \(b^2\) 也是整数。又由 \(a^2 = 2b^2\) 得 \(a^2\) 必为偶数，由引理得 \(a\) 为偶数。
  
  此时存在整数 \(c\) 使得 \(a = 2c\)，代入 \(a^2 = 2b^2\) 可得 \(4c^2 = 2b^2\)，即 \(b^2 = 2c^2\)。
  
  又因为 \(c\) 为整数，故 \(b\) 也为偶数。
  
  综上，可得整数 \(a\)、\(b\) 有公因数 \(2\)，构成命题 \(\neg R\)。
  
  此时即有 \(P \Rightarrow R \land \neg R\)，构成矛盾，故原命题得证。

分类讨论¶

有时当我们希望证明某个命题时，并不知道一系列可能的情形中哪些为真，但我们知道其中至少有一种情况是成立的，那么我们就可以列举所有情形（⚠️这里指的是待证命题及其否定，不要与命题陈述的不同情形混淆），并分别对其进行证明。

存在无理数 \(x\)、\(y\) 使得 \(x^y\) 为有理数。
- 证明如下：
  
  采用分类讨论
  
  该命题由存在量词约束，因此要证明该命题，只需展示一组满足条件的 \(x\) 和 \(y\) 即可。
  
  设 \(x = y = \sqrt{2}\)，则可讨论以下情形：
  1. \(\sqrt{2}^\sqrt{2}\) 是有理数
    
    这个情形的陈述显然与待证命题本身重叠，故暂时忽略。
  2. \(\sqrt{2}^\sqrt{2}\) 是无理数
    
    假设 \(\sqrt{2}^\sqrt{2}\) 是无理数，这时不妨令 \(x = \sqrt{2}^\sqrt{2}\)、\(y = \sqrt{2}\)，则有：
    
    \[ x^y = (\sqrt{2}^\sqrt{2})^\sqrt{2} = (\sqrt{2})^2 = 2 \]
    
    在该情形下，\(x\) 被我们假设为无理数，而 \(y\) 显然是一个无理数（在前面的学习中我们也证明了这一点），但 \(x^y\) 的结果 \(2\) 是一个有理数。
  由于情形 \((a)\) 和情形 \((b)\) 必居其一，故原命题成立。

对于整数 \(a\) 和 \(b\)，当且仅当存在整数 \(q\) 使得 \(b = aq\) 时，我们称 \(a\) 整除 \(b\)，记作 \(a\ |\ b\) ↩
求和运算或两个整数的乘积仍是整数，即整数集在加法或乘法运算下封闭。自然数集在加法和乘法运算下同样具有封闭性 ↩