证明方法 I：直接证明、分类讨论与反例

前面几章已经给出了逻辑、量词、集合、关系和函数的语言。从这一章开始，我们把这些语言真正写成证明。证明不是把几个例子算对，也不是把想法写得像结论，而是从定义和假设出发，一步一步推出题目要求的语句。

本章先练三种最常用的动作：直接证明、分类讨论和构造反例。它们看起来朴素，却会决定后面学习逆否证明、反证法、归纳法和图论证明时能不能写清楚。

从定义开始

证明写作的第一步常常很小：把题目中的词换成可操作的式子。词语还停留在“偶数”“整除”“函数”“子集”时，我们很难继续推理；定义展开以后，推理才有抓手。

例如，在整数范围内：

这些定义都有两种用法。若题目已知 $n$ 是偶数，你可以写“设 $n=2k$，其中 $k$ 为整数”。若题目要求证明某个数是偶数，你的目标通常是把它整理成 $2$ 乘以某个整数。

看一个很短的定义展开证明。

命题：若 $m$ 和 $n$ 都是奇数，则 $m+n$ 是偶数。

这里没有用到神秘技巧。关键只是把“奇数”和“偶数”都换成定义，然后检查括号里的数仍然是整数。

练习：证明若 $n$ 是偶数，则 $n+6$ 是偶数。

直接证明

直接证明适合处理形如“若 $P$，则 $Q$”的命题。它的基本路线是：假设 $P$ 成立，使用定义和已知事实，最后推出 $Q$。

若命题带有全称量词，例如

证明时不能只检查 $n=2$、$n=4$、$n=100$。正确的开头是“任取整数 $n$”，然后在不指定 $n$ 的具体值时完成推理。这样得到的结论才覆盖所有可能的 $n$。

命题：若 $n$ 是偶数，则 $n^2$ 是偶数。

直接证明常见的难点不在计算，而在结尾。结尾要回到题目要求的定义。例如这里不能只停在 $n^2=4k^2$，还要明确写成 $2(2k^2)$，说明它符合偶数定义。

下面这个交互把直接证明拆成步骤卡片。你可以先拼顺序，再看每一步在证明中承担什么角色。

再看一个整除命题。

命题：若 $a\mid b$ 且 $a\mid c$，则 $a\mid (b+c)$。

分类讨论

分类讨论用于一个统一证明不好直接写、但对象可以被自然分成几类的情况。分类本身不是装饰，它必须满足两个条件：所有对象都被覆盖，且每个分支的结论都能回到同一个目标。

整数的奇偶性是最常见的分类。每个整数要么是偶数，要么是奇数，没有第三种情况。这使得“按奇偶分类”可以覆盖所有整数。

命题：对任意整数 $n$，$n^2+n$ 是偶数。

分类讨论的最后一句很重要。它告诉读者：分支已经检查完，且没有遗漏对象。

下面的实验台把分类讨论和反例搜索放在一起。先切换奇偶分支，观察同一个结论如何在不同情形下被推出；再输入整数，判断一个候选是否真的构成反例。

练习：证明对任意整数 $n$，$n^2$ 与 $n$ 有相同的奇偶性。

整除证明中的代入

整除命题常常看起来像符号游戏，其实核心仍然是定义展开。已知 $a\mid b$，就把它改写成 $b=ar$；已知 $b\mid c$，就把它改写成 $c=bs$。然后通过代入把链条接起来。

命题：若 $a\mid b$ 且 $b\mid c$，则 $a\mid c$。

在这类证明中，“整数封闭”经常被用到。若 $r,s$ 是整数，那么 $r+s$、$rs$、$r-s$ 仍是整数。这个事实让我们能把括号里的表达式继续当作定义中的“某个整数”。

练习：证明若 $a\mid b$，则 $a\mid bc$。

构造反例

证明用来说明一个命题为真，反例用来说明一个命题为假。对全称命题来说，一个反例就够了。

如果命题是

那么反例是论域 $D$ 中的一个对象 $x$，使得 $P(x)$ 为假。

如果命题是

那么反例必须让 $P(x)$ 为真，同时让 $Q(x)$ 为假。只让结论假还不够；若前件本来就是假，这个对象不能推翻条件命题。

命题：对所有整数 $a,b$，若 $a<b$，则 $a^2<b^2$。

这个命题为假。取 $a=-2$，$b=1$。它们是整数，并且 $-2<1$ 成立；但是

所以 $(-2)^2<1^2$ 不成立。于是 $a=-2,b=1$ 是反例。

构造反例可以按下面的顺序做。

练习：判断命题“对所有整数 $n$，若 $n$ 是偶数，则 $\frac n2$ 是偶数”是否为真。若为假，给出反例。

常见书写错误

证明写错时，通常不是因为公式太难，而是因为逻辑位置写乱了。下面这些错误在初学证明时很常见。

用例子代替证明

为了证明“所有偶数的平方都是偶数”，只写 $2^2=4$、$4^2=16$、$6^2=36$ 不能成立。例子可以帮助猜想，但不能覆盖无限多个整数。

把要证明的结论当作已知

若要证明 $n^2$ 是偶数，不能一开始就写“因为 $n^2=2k$”。这正是结论本身。正确做法是从 $n$ 是偶数出发，设 $n=2k$，再推出 $$。

忘记变量的范围

证明中出现 $k,r,s$ 时，要说明它们是整数。整除和奇偶性的定义都依赖“整数”这个范围。若范围缺失，证明就少了一块地基。

分类没有覆盖全部情况

如果题目讨论所有整数，按“正整数”和“负整数”分类会漏掉 $0$。按“偶数”和“奇数”分类则覆盖所有整数。

反例没有满足假设

要推翻“若 $a<b$，则 $a^2<b^2$”，不能取 $a=2,b=1$。虽然 为假，但 也是假；这个对象没有进入命题真正讨论的情形。

综合练习：证明或给出反例。

1. 若 $n$ 是奇数，则 $n^2$ 是奇数。
2. 对所有整数 $a,b$，若 $a\mid b$，则 $a^2\mid b^2$。

因为 $k+3$ 是整数，所以 $n+6$ 是偶数。

因为 $2k^2+k$ 是整数，所以这一情形下 $n^2+n$ 是偶数。

所以 $n^2$ 是奇数。两类覆盖所有整数，因此 $n^2$ 与 $n$ 有相同的奇偶性。

因为 $k$ 和 $c$ 都是整数，所以 $kc$ 是整数。因此 $a\mid bc$。

所以 $n^2$ 是奇数。

第 2 题为真。若 $a\mid b$，则 $b=ak$，其中 $k$ 为整数。于是 $b^2=a^2k^2$，所以 $a^2\mid b^2$。

第 3 题为真，但用直接证明不太顺手。本章可以先按奇偶分类：若 $n$ 是奇数，则 $n^2$ 是奇数；因此 $n^2$ 为偶数时，$n$ 不能是奇数，只能是偶数。

第 4 题为假。取 $n=1$，它是奇数，但 $n+1=2$ 是偶数，所以不是奇数。