反证法

反证法（英语：proof by contradiction；拉丁语：reductio ad absurdum）是一种在经典逻辑中有效的数学证明方法，适用于证明一个数学命题为真。当命题$A$为假时，可应用反证法到$\lnot A$。反证法是一种间接证明方法，常用于难以直接证明的情形。

反证法的操作步骤是：

- 假设原命题的否定为真部分中学数学教材或网络资料的表述里“反证法第一步是假设‘在原命题的条件下，结论不成立’”是面向简单蕴含式的中学教学简化说法，并非经典逻辑中反证法的严格定义。严格意义上，反证法的第一步是假设整个原命题为假（否定原命题），而非仅否定结论。二者在复杂命题中存在本质区别。例如“证明不存在最大的素数”、“证明有的全等三角形是直角三角形”、“证明存在两个无理数$a,b$，使得$a^b$是有理数”，此类命题没有明确的“条件-结论”二分结构，否定结论自然无从谈起。
- 经过一系列正确的推理，得出根据矛盾律知恒为假的矛盾。
- 根据否定后件律，矛盾的根源只可能是原命题的否定为假（即假设不成立）。
- 根据排中律，知原命题为真。

反证法中得到的矛盾，有以下三种可能：

- 与已知条件矛盾。
- 与已知定理、公理、定义、法则或显然成立的事实等矛盾。
- 与假设矛盾。

## 理据

给出命题 $p$ 和命题 $\bar{p}$（非 $p$），根据排中律，两者之中起码有一个是真（更强的说法为，除了真和假之外并无其他的情况），所以如果其中一个是假的，另一个就必然是真。给出命题 $q$ 和命题 $\bar{q}$（非 $q$），根据无矛盾律，两者同时为真的情况为假。给出命题 $\bar{p}$ 和 $r$，根据否定后件律，如果若 $\bar{p}$ 成立时出现 $r$，则 $r$ 为假时 $\bar{p}$ 即为假。反证法在要证明 $p$ 时，透过显示出若 $\bar{p}$ 成立时出现矛盾（$q$ 和 $\bar{q}$），即 $\bar{p}$ 为假，从而证明 $p$ 为真。

## 例子

### 单称命题：$\sqrt{2}$是无理数的证明（古希腊）

证明：假设原命题不成立，即$\sqrt{2}$不是无理数，那么$\sqrt{2}$是有理数这里用到了隐含前提：$\sqrt{2}$是实数。在实数集中，有理数集与无理数集互为补集（不交且并集为全体实数），二者非此即彼，满足反证法的排中律要求。根据有理数的定义，$\sqrt{2}$可以写成 $\frac{p}{q}$ 的形式，其中 $p$、$q$ 皆为正整数且 $p$、$q$ 互质。等式两边同乘$q$得$p=\sqrt{2}\, q$，故$p^2=2 q^2$，由此可知 $p^2$是偶数，所以 $p$ 也是偶数这里又使用一次反证法/逆否命题法：假设$p$为奇数，则可把$p$表示为$p=2k+1$（其中$k$为整数），$\Longrightarrow p^2 = (2k+1)^2 = 2(2k^2 +2k)+1$为奇数，所以奇数的平方一定为奇数，这和$p^2$是偶数矛盾，故$p$必为偶数。因此可设 $p=2s$，从而 $p^2 = 4s^2$，代入上式，得$q^2=2s^2$。同理可知 $q^2$也是偶数，故 $q$ 也为偶数。此时 $p$、$q$ 均为偶数，不互质，这与 $p$、$q$ 互质的初始假设矛盾本证明的核心矛盾是“$p,q$互质”的前提与推导得出的“$p,q$不互质”相冲突。事实上，反证法初始假设中“$p,q$互质”并非必需条件：若假设$\sqrt{2}$为有理数时不附加互质约束，重复上述推导可得到无穷多组数值不断缩小的正整数解，这正是无穷递降法的证明思路，无穷递降法本质上是反证法的一种特殊形式。因此原假设不成立，$\sqrt{2}$为无理数。

### 全称蕴含式：$\forall a,b \in \mathbb{Z}$，$(a+b\sqrt{2} =0) \rightarrow b=0$.的证明

证明：反证法。

假设原命题的否定为真，即假设：$$\exists a_0 ,b_0 \in \mathbb{Z}, (a_0 + b_0 \sqrt{2}=0)\land \lnot (b_0 =0)$$为真。

则$b_0 \neq 0$，推出$\sqrt{2} = \cfrac{a_0}{b_0}$，这是矛盾，因为无理数$\sqrt{2}$是不可能等于有理数$\cfrac{a_0}{b_0}$的。因此假设不成立，即原命题的否定为假，故原命题为真。

## 其他可用反证法证明的例子

数学上有许多的定理可用反证法来证明，以下是一小部分的例子：

- 证明有无限多个质数。
- 任意6人当中，求证或者有3人两两相识，或者有3人互不相识。
- 现有90张纸，每张纸都写有一个非负整数，已知这90个数之和小于1980，证明至少有三张数目相同的纸。
- 集合 $S = \{x: 0<x<1\}$ 没有最小值。
- 设 $n$ 是大于1的整数，若所有小于或等于$\sqrt{n}$的质数都不能整除 $n$，则 $n$ 是质数。
- 已知三角形ABC是锐角三角形，且$\angle A>\angle B>\angle C$。求证：$\angle B>45^\circ$。
- 已知 $a$、$b$ 为正实数，求证：$\frac{a+b}{2}\ge \sqrt{ab}$。
- 已知 $a$、$b$、$c$、$d$ 是实数，且$ad-bc=1$，求证：$a^2+b^2+c^2+d^2+ab+cd\neq 1$。
- 一个群若同时是交换群和单群，则该群是循环群
- 若一个循环群是单群，则该群的阶为质数
- 若一个循环群的阶为质数，则该群为单群
- 鸽笼原理

## 数学家哈代关于反证法的名言

- 英国数学家高德菲·哈罗德·哈代在他的文章《一个数学家的辩白》描述：“反证法是数学家的拿手好戏。它比任何棋手弃子取胜的策略都更高明：棋手可能愿意丢车保帅，但数学家却是把全盘置诸死地而后生。”

## 辨析——数学教育中的反证法

反证法一词，在不同地区、不同数学圈子里有不同的含义。

### 高中数学教育中的反证法

- 台湾高中数学教育圈常将英文'proof by contradiction'翻译为"归谬证法"，将英文'proof by contrapositive'翻译为"反证法"。
- 在香港高中数学教育圈，'proof by contradiction'翻译为“反证法”或者“归谬法”，而'proof by contrapositive'翻译为逆否命题证明法（或简称逆否证法）。
- 在中国大陆高中数学教育圈，普通高中教学中往往将'proof by contrapositive'和'proof by contradiction'杂糅在一起，称为“反证法”，实际指代的和台湾高中数学教育圈的"反证法"之意类似，证法的内容主体都是'proof by contrapositive'，原理都是原命题和逆否命题同真假，但却用了“导出矛盾”的'proof by contradiction'框架的说法。'proof by contrapositive'的名词在大陆公元2017年高中数学课纲中没有提到，因为课纲已删除了四种命题（原命题、逆命题、否命题、逆否命题），高中阶段不再出现逆否命题证明法这一名词，只以反证法之名行逆否命题证明法（'proof by contrapositive'）之实。

反证法是中学数学到大学数学教育衔接的难点之一，在不同国家地区都是一个教育难题。

### 大学数学教育中的反证法

大学数学的中文教材，对反证法的定义回归到严谨的数学定义，均指'proof by contradiction'；并且大学数学教材严格区分反证法（'proof by contradiction'）与逆否命题证明法（'proof by contrapositive'）。

## 进一步阅读

- J. Franklin and A. Daoud, Proof in Mathematics: An Introduction, Quakers Hill Press, 1996, ch. 6