3.2 直接证明、分情况证明与逆否证明

第 3.1 节已经区分例子与证明。证明必须处理任意对象，而不是少量特选数值。现在，我们要学习三种用于全称蕴含的证明策略：

\forall x\in D,\;P(x)\to Q(x).

三种策略证明的是同一类命题，但选择不同路线：

直接证明从 $P(x)$ 出发，向前推到 $Q(x)$ ；

分情况证明把全部可能性拆成容易处理的分支；

逆否证明改为证明 $\neg Q(x)\to\neg P(x)$ 。

直接证明的基本结构

对 $P\to Q$ 作直接证明（direct proof）时，先取论域中的任意对象，假设它满足前提 $P$ ，再使用定义和已知事实，直到结论 $Q$ 成立。

这里的“假设”不是猜测定理为真。在一个蕴含内部，我们可以专门研究前提成立的世界，随后必须证明在每一个这样的世界中，结论也成立。

可以复用的直接证明结构是：

1. 在指定论域中任取对象 $x$ ；

2. 假设前提 $P(x)$ 成立；

3. 把定义展开成可以使用的数学形式；

4. 经过有理由支持的步骤变换这些形式；

5. 让结果与 $Q(x)$ 的定义匹配；

6. 明确写出结论。

完整例子：偶数加奇数仍是奇数

定理。 若 $a$ 为偶数、 $b$ 为奇数，则 $a+b$ 为奇数。

先取满足前提的任意整数 $a$ 、 $b$ 。

因为 $a$ 是偶数，根据定义，存在整数 $r$ 使

a=2r.

因为 $b$ 是奇数，存在整数 $s$ 使

b=2s+1.

把两个式子相加：

\begin{aligned} a+b &=2r+(2s+1)\\ &=2(r+s)+1. \end{aligned}

整数对加法封闭，所以 $r+s$ 仍是整数。最终结果具有 $2k+1$ 的形式，其中整数见证是 $k=r+s$ 。根据奇数定义， $a+b$ 为奇数。

观察证明方向：

\text{前提} \longrightarrow \text{定义} \longrightarrow \text{代数变形} \longrightarrow \text{结论定义}.

每句话都有任务。只写“所以 $a+b$ 是奇数”是在重复结论，而不是说明理由。

正在加载交互实验...

请按依赖顺序搭建证明桥。定义尚未引入 $r$ 、 $s$ 之前，不能突然使用它们进行代入。最后一步还必须说明 $r+s$ 为整数，因为奇数定义要求一个整数见证。

正在加载概念检查...

正在加载本节练习...

分情况证明要拆出穷尽论域的分支

有时，同一条前向论证不适合全部对象。分情况证明（proof by cases）把论域分成若干分支，在每个分支中证明结论，最后再合并。

有效情况应满足两个要求：

穷尽：每个可能对象至少属于一个情况；

重叠可控：情况可以重叠，但重叠部分也必须得到一致处理。互不重叠的情况通常更容易使用。

对整数而言，“偶数”和“奇数”构成一组穷尽且互斥的情况：每个整数恰好属于一个分支。

按奇偶性分情况的完整证明

定理。 对每个整数 $n$ ，乘积 $n(n+1)$ 都是偶数。

分成两种情况。

情况 1： $n$ 是偶数。 存在整数 $k$ 使 $n=2k$ 。于是

n(n+1)=2k(n+1)=2\bigl(k(n+1)\bigr).

$k(n+1)$ 是整数，所以乘积为偶数。

情况 2： $n$ 是奇数。 存在整数 $k$ 使 $n=2k+1$ ，因此

n+1=2k+2=2(k+1).

于是

n(n+1)=n\cdot2(k+1)=2\bigl(n(k+1)\bigr),

它也是偶数。

两种情况覆盖每个整数，并且结论在两个分支都成立，所以对每个整数 $n$ ， $n(n+1)$ 都是偶数。

常见错误是选择了遗漏边界的情况。对实数 $x$ ， $x<0$ 与 $x>0$ 会漏掉 $x=0$ 。可以改用 $x<0$ 和 $x\ge0$ ，或使用 $x<0$ 、 $x=0$ 、 $x>0$ 三种情况。

逆否证明会交换并否定推理方向

第 2 章已经证明逻辑等价

P\to Q\equiv\neg Q\to\neg P.

$\neg Q\to\neg P$ 是 $P\to Q$ 的逆否命题。逆否证明（proof by contraposition）不直接证明原命题，而是证明逆否命题。

当结论的否定能够提供更具体、更容易计算的形式时，这种策略尤其有用。

完整例子：平方为偶数，则原整数为偶数

定理。 如果 $n^2$ 是偶数，那么 $n$ 是偶数。

直接证明会从 $n^2=2k$ 出发，试图从平方中提取因数 $2$ 。这需要尚未建立的更多整除工具。逆否命题更简单：

> 如果 $n$ 不是偶数，那么 $n^2$ 不是偶数。

整数不是偶数就一定是奇数。令

n=2k+1,

其中 $k$ 为整数。于是

\begin{aligned} n^2 &=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned}

$2k^2+2k$ 是整数，所以 $n^2$ 是奇数，也就不是偶数。逆否命题得到证明。因为逆否命题与原命题逻辑等价，原定理也成立。

正在加载交互实验...

先在轨道场中验证奇数与偶数确实覆盖每个整数，再进入平方隧道。具体数值用来观察模式，而符号形式 $(2k+1)^2=2(2k^2+2k)+1$ 才提供适用于任意奇数的逆否证明。

正在加载概念检查...

正在加载本节练习...

怎样选择证明策略

先明确写出前提和结论，再查看它们的定义：

题目特征	值得尝试的策略
前提立即提供有用代数形式	直接证明
论域自然分成少量穷尽类型	分情况证明
结论的否定给出具体形式或更简单条件	逆否证明

这张表只是指导，不是自动规则。同一定理可能有多种证明。优秀的证明者会寻找最容易使用定义、最容易看清逻辑责任的路线。

不要把逆否命题与逆命题混淆。 $P\to Q$ 的逆否命题是 $\neg Q\to\neg P$ ，它与原命题等价；逆命题 $Q\to P$ 是另一条命题，可能为假。

注意

分情况证明仍然要在每种情况内部完成证明。只写“

n

是偶数或奇数”仅仅创建了分支，并没有在任何一个分支中证明结论。

通向下一节

直接证明、分情况证明和逆否证明都通过蕴含建立结论。有些命题更适合暂时假设它的否定，再说明这个假设不可能成立。第 3.3 节会介绍反证法，然后把证明存在性与证明唯一性分成两个不同任务。

3.2 直接证明、分情况证明与逆否证明

第 3.1 节已经区分例子与证明。证明必须处理任意对象，而不是少量特选数值。现在，我们要学习三种用于全称蕴含的证明策略：

\forall x\in D,\;P(x)\to Q(x).

三种策略证明的是同一类命题，但选择不同路线：

直接证明从 $P(x)$ 出发，向前推到 $Q(x)$ ；

分情况证明把全部可能性拆成容易处理的分支；

逆否证明改为证明 $\neg Q(x)\to\neg P(x)$ 。

直接证明的基本结构

对 $P\to Q$ 作直接证明（direct proof）时，先取论域中的任意对象，假设它满足前提 $P$ ，再使用定义和已知事实，直到结论 $Q$ 成立。

这里的“假设”不是猜测定理为真。在一个蕴含内部，我们可以专门研究前提成立的世界，随后必须证明在每一个这样的世界中，结论也成立。

可以复用的直接证明结构是：

1. 在指定论域中任取对象 $x$ ；

2. 假设前提 $P(x)$ 成立；

3. 把定义展开成可以使用的数学形式；

4. 经过有理由支持的步骤变换这些形式；

5. 让结果与 $Q(x)$ 的定义匹配；

6. 明确写出结论。

完整例子：偶数加奇数仍是奇数

定理。 若 $a$ 为偶数、 $b$ 为奇数，则 $a+b$ 为奇数。

先取满足前提的任意整数 $a$ 、 $b$ 。

因为 $a$ 是偶数，根据定义，存在整数 $r$ 使

a=2r.

因为 $b$ 是奇数，存在整数 $s$ 使

b=2s+1.

把两个式子相加：

\begin{aligned} a+b &=2r+(2s+1)\\ &=2(r+s)+1. \end{aligned}

整数对加法封闭，所以 $r+s$ 仍是整数。最终结果具有 $2k+1$ 的形式，其中整数见证是 $k=r+s$ 。根据奇数定义， $a+b$ 为奇数。

观察证明方向：

\text{前提} \longrightarrow \text{定义} \longrightarrow \text{代数变形} \longrightarrow \text{结论定义}.

每句话都有任务。只写“所以 $a+b$ 是奇数”是在重复结论，而不是说明理由。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

分情况证明要拆出穷尽论域的分支

有时，同一条前向论证不适合全部对象。分情况证明（proof by cases）把论域分成若干分支，在每个分支中证明结论，最后再合并。

有效情况应满足两个要求：

穷尽：每个可能对象至少属于一个情况；

重叠可控：情况可以重叠，但重叠部分也必须得到一致处理。互不重叠的情况通常更容易使用。

对整数而言，“偶数”和“奇数”构成一组穷尽且互斥的情况：每个整数恰好属于一个分支。

按奇偶性分情况的完整证明

定理。 对每个整数 $n$ ，乘积 $n(n+1)$ 都是偶数。

分成两种情况。

情况 1： $n$ 是偶数。 存在整数 $k$ 使 $n=2k$ 。于是

n(n+1)=2k(n+1)=2\bigl(k(n+1)\bigr).

$k(n+1)$ 是整数，所以乘积为偶数。

情况 2： $n$ 是奇数。 存在整数 $k$ 使 $n=2k+1$ ，因此

n+1=2k+2=2(k+1).

于是

n(n+1)=n\cdot2(k+1)=2\bigl(n(k+1)\bigr),

它也是偶数。

两种情况覆盖每个整数，并且结论在两个分支都成立，所以对每个整数 $n$ ， $n(n+1)$ 都是偶数。

常见错误是选择了遗漏边界的情况。对实数 $x$ ， $x<0$ 与 $x>0$ 会漏掉 $x=0$ 。可以改用 $x<0$ 和 $x\ge0$ ，或使用 $x<0$ 、 $x=0$ 、 $x>0$ 三种情况。

逆否证明会交换并否定推理方向

第 2 章已经证明逻辑等价

P\to Q\equiv\neg Q\to\neg P.

$\neg Q\to\neg P$ 是 $P\to Q$ 的逆否命题。逆否证明（proof by contraposition）不直接证明原命题，而是证明逆否命题。

当结论的否定能够提供更具体、更容易计算的形式时，这种策略尤其有用。

完整例子：平方为偶数，则原整数为偶数

定理。 如果 $n^2$ 是偶数，那么 $n$ 是偶数。

直接证明会从 $n^2=2k$ 出发，试图从平方中提取因数 $2$ 。这需要尚未建立的更多整除工具。逆否命题更简单：

> 如果 $n$ 不是偶数，那么 $n^2$ 不是偶数。

整数不是偶数就一定是奇数。令

n=2k+1,

其中 $k$ 为整数。于是

\begin{aligned} n^2 &=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned}

$2k^2+2k$ 是整数，所以 $n^2$ 是奇数，也就不是偶数。逆否命题得到证明。因为逆否命题与原命题逻辑等价，原定理也成立。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

怎样选择证明策略

先明确写出前提和结论，再查看它们的定义：

题目特征	值得尝试的策略
前提立即提供有用代数形式	直接证明
论域自然分成少量穷尽类型	分情况证明
结论的否定给出具体形式或更简单条件	逆否证明

这张表只是指导，不是自动规则。同一定理可能有多种证明。优秀的证明者会寻找最容易使用定义、最容易看清逻辑责任的路线。

不要把逆否命题与逆命题混淆。 $P\to Q$ 的逆否命题是 $\neg Q\to\neg P$ ，它与原命题等价；逆命题 $Q\to P$ 是另一条命题，可能为假。

注意

分情况证明仍然要在每种情况内部完成证明。只写“

n

是偶数或奇数”仅仅创建了分支，并没有在任何一个分支中证明结论。