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

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

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

证明从命题出发，依次经过展开定义、写出假设、逐步推出、回到结论的中文流程总览图 — 证明从哪里开始：定义给语言，假设给起点，推理给桥梁，结论要对题。

读一个命题时，先不要急着计算。先找清楚论域、量词、假设和结论，再把关键词换成定义。证明的开头通常就藏在这些信息里。

从定义开始

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

例如，在整数范围内：

n \text{ 是偶数} \Longleftrightarrow \exists k\in \mathbb Z,\ n=2k

n \text{ 是奇数} \Longleftrightarrow \exists k\in \mathbb Z,\ n=2k+1

a\mid b \Longleftrightarrow \exists k\in \mathbb Z,\ b=ak

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

定义展开速查图，三列展示偶数、奇数和整除的证明写法与已知条件设法 — 从定义开始：偶数、奇数与整除的常用展开形式。

写“ $n=2k$ ”时，必须说明 $k$ 是整数。偶数的定义不是“能写成 $2$ 乘以某个东西”，而是“能写成 $2$ 乘以某个整数”。

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

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

任取两个整数 $m,n$ ，并假设它们都是奇数。这个开头对应命题中的“若 $m$ 和 $n$ 都是奇数”。

由奇数定义，存在整数 $r,s$ ，使得 $m=2r+1$ 且 $n=2s+1$ 。

把两个表达式相加，得到

m+n=(2r+1)+(2s+1)=2(r+s+1)

因为 $r+s+1$ 是整数，所以 $m+n$ 写成了 $2$ 乘以一个整数。按偶数定义， $m+n$ 是偶数。

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

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

直接证明

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

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

\forall n\in \mathbb Z,\ P(n)\Rightarrow Q(n)

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

直接证明链条示例图：从任取整数 n、假设 n 为偶数并设 n=2k，推导 n² 等于 2 乘以整数，得到 n² 为偶数 — 直接证明强调对任意对象推理，而不是举例验证。

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

任取整数 $n$ ，并假设 $n$ 是偶数。这里的“任取”表示接下来的论证不能依赖某个特殊数值。

由偶数定义，存在整数 $k$ ，使得 $n=2k$ 。

平方并整理：

n^2=(2k)^2=4k^2=2(2k^2)

因为 $2k^2$ 是整数，所以 $n^2$ 写成了 $2$ 乘以一个整数。由偶数定义， $n^2$ 是偶数。

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

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

再看一个整除命题。

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

任取整数 $a,b,c$ ，并假设 $a\mid b$ 且 $a\mid c$ 。

由整除定义，存在整数 $r,s$ ，使得 $b=ar$ 且 $c=as$ 。

把两个等式相加：

b+c=ar+as=a(r+s)

因为 $r+s$ 是整数，所以 $b+c$ 是 $a$ 乘以一个整数。由整除定义， $a\mid(b+c)$ 。

直接证明的检查问题很固定：我是否任取了对象？是否只使用了假设和定义？最后一句是否真正回到了要证明的结论？

分类讨论

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

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

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

奇偶性分类讨论树：任意整数 n 分为偶数和奇数两类，分别推出 n²+n 含有因子 2，因此为偶数 — 奇偶性分类讨论树：两类穷尽且最后汇合到同一个结论。

任取整数 $n$ 。按奇偶性分类， $n$ 只能是偶数或奇数。

若 $n$ 是偶数，则存在整数 $k$ ，使得 $n=2k$ 。于是

n^2+n=(2k)^2+2k=4k^2+2k=2(2k^2+k)

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

若 $n$ 是奇数，则存在整数 $k$ ，使得 $n=2k+1$ 。于是

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

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

两种情形覆盖了所有整数，并且都推出 $n^2+n$ 是偶数。因此对任意整数 $n$ ， $n^2+n$ 是偶数。

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

分类讨论最容易出错的地方是分类不全。例如只讨论“正数”和“负数”，却忘了 $0$ 。如果题目的论域包括 $0$ ，这个证明就没有覆盖所有对象。

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

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

整除证明中的代入

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

整除传递性的定义展开图：由已知 a 整除 b、b 整除 c 展开为 b=ar、c=bs，代入得到 c=a(rs)，从而推出 a 整除 c — 整除传递性：通过定义展开、代入与整数封闭性证明 $a\mid c$ 。

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

任取整数 $a,b,c$ ，并假设 $a\mid b$ 且 $b\mid c$ 。

由 $a\mid b$ ，存在整数 $r$ ，使得 $b=ar$ 。由 $b\mid c$ ，存在整数 $s$ ，使得 $c=bs$ 。

把 $b=ar$ 代入 $c=bs$ ，得到

c=(ar)s=a(rs)

因为 $r$ 和 $s$ 都是整数，所以 $rs$ 是整数。因此 $c$ 写成了 $a$ 乘以一个整数，按整除定义， $a\mid c$ 。

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

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

构造反例

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

如果命题是

\forall x\in D,\ P(x)

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

如果命题是

\forall x\in D,\ P(x)\Rightarrow Q(x)

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

用反例 a=-2、b=1 推翻全称命题：前件 -2 小于 1 成立，但结论 (-2)² 小于 1² 不成立 — 一例足以推翻全称命题：当前件真而结论假时，全称命题不成立。

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

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

(-2)^2=4,\qquad 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$ ，再推出 $n^2=2(2k^2)$ 。

忘记变量的范围

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

分类没有覆盖全部情况

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

反例没有满足假设

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

写完一个短证明后，可以用三句话检查：我从题目的假设开始了吗？我每次改写都有定义或代数依据吗？最后一句准确回答了题目要证明什么吗？

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

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

第 1 题为真。设 $n=2k+1$ ，则

n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1

所以 $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$ 是偶数，所以不是奇数。

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

读一个命题时，先不要急着计算。先找清楚论域、量词、假设和结论，再把关键词换成定义。证明的开头通常就藏在这些信息里。

从定义开始

例如，在整数范围内：

n \text{ 是偶数} \Longleftrightarrow \exists k\in \mathbb Z,\ n=2k

n \text{ 是奇数} \Longleftrightarrow \exists k\in \mathbb Z,\ n=2k+1

a\mid b \Longleftrightarrow \exists k\in \mathbb Z,\ b=ak

写“ $n=2k$ ”时，必须说明 $k$ 是整数。偶数的定义不是“能写成 $2$ 乘以某个东西”，而是“能写成 $2$ 乘以某个整数”。

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

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

任取两个整数 $m,n$ ，并假设它们都是奇数。这个开头对应命题中的“若 $m$ 和 $n$ 都是奇数”。

由奇数定义，存在整数 $r,s$ ，使得 $m=2r+1$ 且 $n=2s+1$ 。

把两个表达式相加，得到

m+n=(2r+1)+(2s+1)=2(r+s+1)

因为 $r+s+1$ 是整数，所以 $m+n$ 写成了 $2$ 乘以一个整数。按偶数定义， $m+n$ 是偶数。

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

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

直接证明

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

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

\forall n\in \mathbb Z,\ P(n)\Rightarrow Q(n)

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

任取整数 $n$ ，并假设 $n$ 是偶数。这里的“任取”表示接下来的论证不能依赖某个特殊数值。

由偶数定义，存在整数 $k$ ，使得 $n=2k$ 。

平方并整理：

n^2=(2k)^2=4k^2=2(2k^2)

因为 $2k^2$ 是整数，所以 $n^2$ 写成了 $2$ 乘以一个整数。由偶数定义， $n^2$ 是偶数。

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

再看一个整除命题。

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

任取整数 $a,b,c$ ，并假设 $a\mid b$ 且 $a\mid c$ 。

由整除定义，存在整数 $r,s$ ，使得 $b=ar$ 且 $c=as$ 。

把两个等式相加：

b+c=ar+as=a(r+s)

因为 $r+s$ 是整数，所以 $b+c$ 是 $a$ 乘以一个整数。由整除定义， $a\mid(b+c)$ 。

直接证明的检查问题很固定：我是否任取了对象？是否只使用了假设和定义？最后一句是否真正回到了要证明的结论？

分类讨论

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

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

任取整数 $n$ 。按奇偶性分类， $n$ 只能是偶数或奇数。

若 $n$ 是偶数，则存在整数 $k$ ，使得 $n=2k$ 。于是

n^2+n=(2k)^2+2k=4k^2+2k=2(2k^2+k)

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

若 $n$ 是奇数，则存在整数 $k$ ，使得 $n=2k+1$ 。于是

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

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

两种情形覆盖了所有整数，并且都推出 $n^2+n$ 是偶数。因此对任意整数 $n$ ， $n^2+n$ 是偶数。

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

分类讨论最容易出错的地方是分类不全。例如只讨论“正数”和“负数”，却忘了 $0$ 。如果题目的论域包括 $0$ ，这个证明就没有覆盖所有对象。

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

整除证明中的代入

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

任取整数 $a,b,c$ ，并假设 $a\mid b$ 且 $b\mid c$ 。

由 $a\mid b$ ，存在整数 $r$ ，使得 $b=ar$ 。由 $b\mid c$ ，存在整数 $s$ ，使得 $c=bs$ 。

把 $b=ar$ 代入 $c=bs$ ，得到

c=(ar)s=a(rs)

因为 $r$ 和 $s$ 都是整数，所以 $rs$ 是整数。因此 $c$ 写成了 $a$ 乘以一个整数，按整除定义， $a\mid c$ 。

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

构造反例

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

如果命题是

\forall x\in D,\ P(x)

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

如果命题是

\forall x\in D,\ P(x)\Rightarrow Q(x)

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

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

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

(-2)^2=4,\qquad 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$ ，再推出 $n^2=2(2k^2)$ 。

忘记变量的范围

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

分类没有覆盖全部情况

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

反例没有满足假设

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

写完一个短证明后，可以用三句话检查：我从题目的假设开始了吗？我每次改写都有定义或代数依据吗？最后一句准确回答了题目要证明什么吗？

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

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

第 1 题为真。设 $n=2k+1$ ，则

n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1

所以 $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$ 是偶数，所以不是奇数。