反证法：从逻辑基础到算法证明

一、 为什么要先假设结论不成立

要证明“不存在最大的整数”，可以先假设有一个最大的整数，记为 $M$。那么 $M+1$ 也是整数，而且比 $M$ 大。这与“$M$ 最大”冲突，因此最大的整数不存在。

这个证明没有挨个检查整数，而是抓住了“最大”这个假设必须满足的条件，再构造出一个破坏条件的对象。

反证法的基本做法就是：

暂时假设要证明的结论不成立，把这个假设和已知条件放在一起推理，得到矛盾，从而确定原结论成立。

难点通常不在最后一句“所以原命题成立”，而在前面三步：怎样准确否定结论？从假设中能得到什么？应该去哪里找矛盾？

本文先解释这套推理的逻辑依据，再通过 14 个例子练习。前 7 例只需要基本数学知识；后 7 例逐步进入图论和算法正确性。遇到还没学过的算法，可以先理解问题与证明目标，学完对应章节后再回来读。

二、 反证法的数理逻辑基础

2.1 命题与逻辑符号

命题是可以判断真假的陈述。例如，“$7$ 是素数”是真命题，“$7$ 是偶数”是假命题。“求最大的整数”是一个要求，本身不是命题。

含有未指定变量的“$x>0$”要先说明 $x$ 的取值，或加上量词，才能确定陈述的含义。

下面这些符号在本篇中会反复出现。

符号	读法	含义
$\neg P$	非 $P$	$P$ 不成立
$P\land Q$	$P$ 且 $Q$	两者都成立
$P\lor Q$	$P$ 或 $Q$	至少一个成立，也允许两个都成立
$P\Rightarrow Q$	若 $P$，则 $Q$	$P$ 成立时，$Q$ 必须成立
$P\Leftrightarrow Q$	$P$ 当且仅当 $Q$	两个命题真假相同
$\forall x\in D$	对所有属于 $D$ 的 $x$	每个对象都满足后面的性质
$\exists x\in D$	存在属于 $D$ 的 $x$	至少一个对象满足后面的性质
$\bot$	矛盾	不可能成立的陈述

这里的 $\Rightarrow$ 表示逻辑上的蕴含；推理过程中也会用它连接前后两步。

2.2 “若……则……”什么时候为假

命题 $P\Rightarrow Q$ 只排除一种情况：$P$ 为真，而 $Q$ 为假。

$P$	$Q$	$P\Rightarrow Q$
真	真	真
真	假	假
假	真	真
假	假	真

例如，“若一个整数能被 $4$ 整除，则它是偶数”。要反驳它，必须找到一个能被 $4$ 整除却不是偶数的整数。找到一个不能被 $4$ 整除的数，无论它是奇数还是偶数，都不能反驳这句话。

因此：

$$\neg(P\Rightarrow Q)\Leftrightarrow P\land\neg Q.$$

这条公式很实用。否定“若 $P$ 则 $Q$”时，要保留前提 $P$，再否定结论 $Q$。

2.3 反证法为什么成立

设 $H$ 表示已知条件，$P$ 表示要证明的结论。直接证明试图建立：

$$H\Rightarrow P.$$

反证法则先研究：

$$H\land\neg P.$$

如果这些条件能够推出矛盾，就说明“已知条件成立，而结论不成立”这种情况不可能发生。

在本篇采用的经典逻辑中：

$$\boxed{ (H\land\neg P)\Rightarrow\bot \quad\Leftrightarrow\quad H\Rightarrow P }$$

也可以分两步理解：推出矛盾后，得到 $\neg\neg P$；再由经典逻辑的双重否定律 $\neg\neg P\Leftrightarrow P$ 得到 $P$。

这里没有把要证明的结论当作前提。我们只是临时加入 $\neg P$，检查它能否与已知条件同时成立。

最直接的矛盾是同时得到 $R$ 和 $\neg R$：

$$R\land\neg R\Rightarrow\bot.$$

实际题目里，矛盾可能表现为：

• 已知 $x\le y$，却推出 $x>y$。
• 已知两个整数互质，却推出它们都有公因子 $2$。
• 选择了一条最长路径，却构造出更长的路径。
• 假设所有最优方案都不含某个选择，却构造出包含它的最优方案。

“我不会继续算了”“这个结果很奇怪”都不是矛盾。必须指出哪两个陈述不能同时成立。

2.4 否定要覆盖所有剩余情况

在实数范围内：

原陈述	准确的否定	常见误写
$x>0$	$x\le 0$	$x<0$
$x\ge y$	$x<y$	$x\le y$
$x=y$	$x\ne y$	$x>y$
$P\land Q$	$\neg P\lor\neg Q$	$\neg P\land\neg Q$
$P\lor Q$	$\neg P\land\neg Q$	$\neg P\lor\neg Q$

后两条是德摩根律。“两个人都及格”的否定是“至少一个人不及格”，其中包括一个不及格、两个都不及格等情况。

量词的否定同样需要改变结构：

$$\neg\bigl(\forall x\in D,\ P(x)\bigr) \Leftrightarrow \exists x\in D,\ \neg P(x),$$

$$\neg\bigl(\exists x\in D,\ P(x)\bigr) \Leftrightarrow \forall x\in D,\ \neg P(x).$$

例如，“所有整数都是偶数”的否定是“存在一个整数不是偶数”。找出 $3$ 就够了，不必证明所有整数都是奇数。

“存在最短路经过顶点 $v$”的否定，则是“所有最短路都不经过 $v$”。不能写成“存在最短路不经过 $v$”：完全可能有两条最短路，一条经过，一条不经过。

对“恰好一个”的否定还要更小心：

$$\neg(\text{恰好存在一个})\Leftrightarrow (\text{一个也不存在})\lor(\text{至少存在两个}).$$

只有已经证明“至少存在一个”之后，证明唯一性时才可以只考虑“存在两个不同的”这一分支。

2.5 先练习否定，再往下读

写出以下陈述的否定：

1. 所有元素都大于 $0$。
2. 存在一种合法方案，其代价不超过 $K$。
3. 若整数 $n$ 能被 $6$ 整除，则 $n$ 能被 $3$ 整除。
4. 最优方案唯一。

展开答案

1. 存在一个元素小于或等于 $0$。
2. 所有合法方案的代价都大于 $K$。如果没有合法方案，这句话也成立。
3. 整数 $n$ 能被 $6$ 整除，且不能被 $3$ 整除。若原陈述是对所有整数的断言，否定还要加上“存在一个整数 $n$”。
4. 不存在最优方案，或者至少存在两个不同的最优方案。若题目已保证最优方案存在，则只剩后者。

三、 怎样组织一份反证法证明

3.1 四步写法

1. 写清目标。 已知条件是什么？要证明的结论是什么？
2. 准确否定。 假设结论不成立，保留所有已知条件。
3. 追踪矛盾。 使用定义、性质或构造，把假设推到与某条条件冲突。
4. 撤销假设。 点明矛盾，说明否定假设不成立，因此原结论成立。

写证明时可以使用“假设……；于是……；这与……矛盾；故……”的顺序。但找证明时，往往需要先看最后一句：题目中哪条条件最容易被破坏？

“最大”“最短”“互质”“无环”“所有方案都不包含”都是很有用的线索。它们分别约束了大小、路径长度、公因子、图的结构以及方案的范围。

3.2 反证法与逆否证明

命题与其逆否命题等价：

$$(P\Rightarrow Q)\Leftrightarrow(\neg Q\Rightarrow\neg P).$$

两种证明的写法如下：

方法	开始时假设什么	需要推到哪里
直接证明	$P$	$Q$
逆否证明	$\neg Q$	$\neg P$
反证法	$P\land\neg Q$	矛盾

例如，证明“若 $n^2$ 是偶数，则 $n$ 是偶数”时，可以证明“若 $n$ 是奇数，则 $n^2$ 是奇数”。这是逆否证明。若保留“$n^2$ 是偶数”，再假设“$n$ 是奇数”，最后得到 $n^2$ 既奇又偶，就是反证法。

两份证明可能使用同一段计算。判断方法时，应该看它假设了什么，以及最后用这段计算证明了什么。

同样，倒着模拟操作、用总数减去补集，都属于常见的逆向思考，但不一定是在使用反证法。

四、 数学例子：从准确否定到构造矛盾

例 1： 不存在最大的整数

目标。 整数集合 $\mathbb Z$ 中不存在最大元素。

准确否定。 假设存在 $M\in\mathbb Z$，满足：

$$\forall n\in\mathbb Z,\quad n\le M.$$

推理与矛盾。 取 $n=M+1$。因为整数加 $1$ 仍是整数，由假设应当有 $M+1\le M$。但 $M+1>M$，矛盾。因此不存在最大的整数。

怎样想到。 “最大”要求压住所有对象；我们只需构造一个更大的对象来破坏它。

不要把证明记成“最大值加一”。它依赖于集合对这个构造封闭。在集合 $\{1,2,3\}$ 中，$3+1$ 不属于集合，不能拿它来否定 $3$ 是最大元素。

例 2： 两项之和为 1，至少一项不小于一半

目标。 若 $a,b>0$，证明：

$$\frac a{a+b}\ge\frac12 \quad\lor\quad \frac b{a+b}\ge\frac12.$$

先看具体数据：$a=2,b=3$ 时，两项分别为 $\frac25$ 和 $\frac35$。一项小于一半，另一项大于一半。$a=b$ 时，两项都等于一半。

准确否定。 由德摩根律，假设两项都小于一半：

$$\frac a{a+b}<\frac12,\qquad \frac b{a+b}<\frac12.$$

推理与矛盾。 两式相加得到：

$$\frac a{a+b}+\frac b{a+b}<1.$$

但左边等于 $\frac{a+b}{a+b}=1$，因此得到 $1<1$，矛盾。

怎样想到。 已知的总和是固定的；“所有项都小于某个平均值”会把总和压得过小。这种思路还可以推广到 $n$ 个数与它们的平均值。

小练习。 若 $n$ 个实数之和为 $S$，证明至少一个数不小于 $\frac Sn$，其中 $n\ge1$。

展开答案

假设每个数都小于 $\frac Sn$，相加得到总和小于 $n\cdot\frac Sn=S$，与总和为 $S$ 矛盾。注意否定“至少一个不小于”得到的是“所有都小于”。

例 3： 平方是偶数，原数也是偶数

目标。 对整数 $n$，证明：

$$2\mid n^2\Rightarrow2\mid n.$$

符号 $a\mid b$ 表示 $b$ 能被 $a$ 整除。

准确否定。 保留 $n^2$ 是偶数，假设 $n$ 不是偶数。整数只有奇、偶两种情况，因此 $n=2k+1$，其中 $k\in\mathbb Z$。

推理与矛盾。

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

因此 $n^2$ 是奇数，与前提“$n^2$ 是偶数”矛盾。故 $n$ 是偶数。

怎样想到。 直接从“平方含因子 $2$”倒推出原数的结构，可能没有从“原数是奇数”展开平方方便。

如果只保留“$n$ 是奇数”并推出“$n^2$ 是奇数”，这段计算就是逆否证明；加入原命题的前提后，才能写出上面的矛盾。

例 4： 6 个整数中，有两个除以 5 的余数相同

目标。 对任意 6 个整数 $a_1,\ldots,a_6$，存在 $1\le i<j\le6$，使：

$$a_i\equiv a_j\pmod5.$$

例如，$2,8,11,14,17,20$ 的非负余数依次是 $2,3,1,4,2,0$，其中 $2$ 与 $17$ 的余数相同。

准确否定。 假设任意两个不同位置的数，余数都不同：

$$\forall\,1\le i<j\le6,\quad a_i\not\equiv a_j\pmod5.$$

推理与矛盾。 除以 $5$ 的非负余数只有 $0,1,2,3,4$ 共 5 种。假设却要求 6 个数占据 6 种不同余数，与只有 5 种余数矛盾。

因此至少两个数余数相同。这也是抽屉原理的一个具体例子。

怎样想到。 “至少两个相同”的否定是“两两不同”。当类别数量有限时，两两不同会直接限制对象总数。

例 5： $\sqrt2$ 是无理数

目标。 $\sqrt2$ 不能写成两个整数的比。

准确否定。 假设 $\sqrt2$ 是有理数。将其写成最简分数：

$$\sqrt2=\frac pq,\qquad p,q\in\mathbb Z_{>0},\quad \gcd(p,q)=1.$$

“最简”意味着 $p,q$ 没有大于 $1$ 的公因子。

推理与矛盾。 平方并整理：

$$p^2=2q^2.$$

因此 $p^2$ 是偶数。由例 3，$p$ 是偶数，设 $p=2k$。代入：

$$4k^2=2q^2\Rightarrow q^2=2k^2.$$

于是 $q$ 也是偶数。$p,q$ 都有公因子 $2$，与 $\gcd(p,q)=1$ 矛盾。

故 $\sqrt2$ 是无理数。

怎样想到。 假设“有理”会带来分数表示；主动选取最简表示，就多了一个可以利用的限制。只推出“分子分母都是偶数”本身并不矛盾，例如 $\frac24$ 完全合法，关键是它与“已经最简”冲突。

例 6： 素数有无穷多个

目标。 素数的个数不是有限的。

准确否定。 假设所有素数可以完整列为：

$$p_1,p_2,\ldots,p_k.$$

因为 $2$ 是素数，所以 $k\ge1$。

推理与矛盾。 构造：

$$N=p_1p_2\cdots p_k+1.$$

$N>1$，因此有某个素因子 $q$。这里使用一个基本事实：每个大于 $1$ 的整数都有素因子。可以取它大于 $1$ 的最小正因子；若该因子是合数，还能找到更小的非平凡因子，故它必须是素数。

但对列表中的每个 $p_i$ 都有：

$$N\equiv1\pmod{p_i}.$$

所以 $p_i$ 都不能整除 $N$，素因子 $q$ 不在列表中。这与列表包含所有素数矛盾。

故素数有无穷多个。

怎样想到。 “已经列全”容易被一个列表外的对象击破；乘积加一恰好让列表中的每个素数都无法整除新数。

注意：不需要证明 $N$ 自身是素数。 例如 $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509$，这个构造得到的数可以是合数；它有列表外的素因子就够了。

例 7： 最小值唯一，但最优方案未必唯一

目标。 若实数集合 $S$ 存在最小元素，那么这个最小元素唯一。

准确否定。 因为已保证存在，只需假设存在两个不同的最小元素 $m_1,m_2$。

推理与矛盾。 根据“最小元素”的定义：

$$\forall x\in S,\quad m_1\le x,\qquad m_2\le x.$$

由于 $m_1,m_2\in S$，分别代入可得：

$$m_1\le m_2,\qquad m_2\le m_1.$$

从而 $m_1=m_2$，与“两者不同”矛盾。

怎样想到。 证明唯一性时，先假设有两个不同的候选，再让它们分别使用同一个定义，互相约束。

在算法里，需要区分目标值和取得目标值的方案。例如：

$$f(x)=x^2,\qquad x\in\{-1,1\}.$$

最小值只有一个，即 $1$；取得这个值的方案却有两个，即 $x=-1$ 和 $x=1$。

“存在最优解”“最优值是多少”“最优方案是否唯一”是三个不同的问题。

小练习。 两条路径的长度都等于 $5$，且不存在更短路径。能否据此证明最短路唯一？

展开答案

不能。只能说明最短距离为 $5$；如果两条路径不同，它们恰好说明最短路径不唯一。

五、 图论例子：利用有限性与极端对象

例 8： 每个顶点的度至少为 2，图中一定有环

问题与必要概念。 考虑一个非空、有限的无向简单图。简单图不含自环和重边，顶点的度就是与它相邻的顶点数。简单路径不重复经过顶点；环则沿着边走一圈回到起点，除首尾外不重复顶点。

目标。 如果每个顶点的度都至少为 $2$，则图中存在环。

例如，边为 $\{1,2\},\{2,3\},\{3,4\},\{4,1\}$ 的图，每个顶点的度都是 $2$，环是 $1,2,3,4,1$。

准确否定。 保留所有顶点的度至少为 $2$，假设图中没有环。

推理与矛盾。 因为图有限，简单路径也只有有限条，可以选出一条顶点数最多的简单路径：

$$v_0,v_1,\ldots,v_k.$$

由度数条件，图中有边，所以 $k\ge1$。研究端点 $v_k$：

1. 它没有路径外的邻居。否则把那个邻居接在末尾，会得到更长的简单路径，与选择矛盾。
2. 它的度至少为 $2$。除了 $v_{k-1}$，还至少有另一个邻居。
3. 这个邻居只能是路径上的某个 $v_i$，其中 $i\le k-2$。

于是：

$$v_i,v_{i+1},\ldots,v_k,v_i$$

构成一个环，与“图中没有环”矛盾。故图中有环。

怎样想到。 随便取一条路径，端点的邻居可能还在路径外，结构难以确定。主动取最长路径，就把“还可以往外走”的可能性堵住了。这叫使用极端对象：借助“最长”“最小”等额外限制，把选择范围压缩。

补全证明。 为什么不能把上面的“简单图”直接删掉？

展开答案

简单图保证度至少为 $2$ 意味着至少有两个不同的邻居。若允许重边，同一个邻居可能通过多条边贡献度数；若允许自环，度数与邻居数量的关系也会改变。多重图中还需要重新约定环是否包括两条平行边组成的环。原证明不能原样照搬。

例 9： 有向无环图一定有入度为 0 的顶点

问题与必要概念。 在有向图中，边 $u\to v$ 表示可以从 $u$ 走到 $v$。顶点的入度是指向它的边数。有向无环图简称 DAG，意思是不能沿边的方向绕一圈回到原点。

目标。 非空有限 DAG 中，至少有一个顶点的入度为 $0$。

例如，边为 $1\to3,2\to3,3\to4$ 时，顶点 $1,2$ 的入度都是 $0$。

准确否定。 假设所有顶点的入度都不为 $0$。入度是非负整数，因此每个顶点至少有一个前驱。

推理与矛盾。 任取 $v_0$，不断选择一个前驱：

$$v_1\to v_0,\quad v_2\to v_1,\quad v_3\to v_2,\quad\ldots$$

如果图有 $n$ 个顶点，那么选到 $v_n$ 时，$v_0,\ldots,v_n$ 共 $n+1$ 项中一定有重复。取首次出现重复的位置 $j$，设 $v_j=v_i$，其中 $i<j$。由首次重复的选择，中间顶点互不相同，而边的方向给出：

$$v_j\to v_{j-1}\to\cdots\to v_i=v_j.$$

这构成有向环，与 DAG 的条件矛盾。

故存在入度为 $0$ 的顶点。

怎样想到。 “每个点都有前驱”允许不断向前追溯；“顶点有限”迫使追溯重复；重复又产生题目禁止的环。

这解释了拓扑排序为什么总能开始：先取走一个入度为 $0$ 的顶点，剩余图仍然无环；只要还非空，就还能继续取。相关算法见 拓扑排序。

独立练习。 证明：非空有限 DAG 中，至少有一个顶点的出度为 $0$。

展开答案

假设每个顶点的出度至少为 $1$。任取一个起点，每次沿一条出边继续走。有限性迫使顶点重复；首次重复形成有向环，与无环矛盾。

这里不能省去“有限”。顶点为所有非负整数、边为 $i\to i+1$ 的无限有向图没有环，但每个顶点的出度都是 $1$。

六、 算法例子：假设存在一个更好的答案

算法正确性常常需要证明：“对所有合法输入，算法都得到正确答案。”

它的否定是：“存在某个合法输入，使算法得到错误答案。”因此，反证时可以固定一个假想的出错输入，在这个输入中研究第一次错误、更好的方案或能够交换的结构。

这里必须分清两件事：找一个真实反例，可以推翻算法；假设反例存在并推出矛盾，才是在证明算法正确。

例 10： BFS 为什么得到无权图最短路

问题与规则。 图中每条边长度都是 $1$。从起点 $s$ 出发，BFS 使用先进先出的队列：先令 $d(s)=0$ 并入队；每次取出队首 $u$，对尚未发现的邻居 $v$，赋值 $d(v)=d(u)+1$，标记已发现并入队。每个顶点只入队一次。

例如，有无向边 $\{s,a\},\{s,b\},\{a,c\},\{c,t\},\{b,t\}$。BFS 得到：

顶点	$s$	$a$	$b$	$c$	$t$
距离	$0$	$1$	$1$	$2$	$2$

到 $t$ 的最短路是 $s,b,t$；虽然还存在 $s,a,c,t$，但后者更长。

目标。 对所有从 $s$ 可达的顶点 $v$，BFS 的标号 $d(v)$ 等于实际最短距离 $\delta(v)$。

先从队列规则得到两个事实，而不预先使用最短路正确性：

1. 每个有限标号都对应一条实际走过的路径，因此 $d(v)\ge\delta(v)$。
2. 顶点按标号不减的顺序被发现和出队。处理标号为 $k$ 的顶点时，只会产生标号为 $k+1$ 的新顶点；它们排在已有队列元素之后。队列始终至多包含相邻两层，而且较小层在前。

准确否定。 假设有可达顶点的标号错误。由于标号不可能小于真实距离，错误只能是 $d(v)>\delta(v)$。在所有错误顶点中，选一个 $\delta(v)$ 最小的，设 $\delta(v)=k$。

推理与矛盾。 $s$ 的标号正确，所以 $k\ge1$。取一条到 $v$ 的最短路，令 $u$ 是 $v$ 的前一个顶点，则：

$$\delta(u)=k-1.$$

否则，如果能更短地到达 $u$，再走一步就能更短地到达 $v$，违反最短路的定义。

由 $v$ 的选择，$u$ 的标号正确，即 $d(u)=k-1$。BFS 处理 $u$ 时：

• 如果 $v$ 未被发现，就赋值 $d(v)=k$。
• 如果 $v$ 已被发现，由发现标号不减的队列性质，它的标号不超过此时可能新产生的标号 $k$，即 $d(v)\le k$。

两种情况都得到 $d(v)\le k=\delta(v)$，与 $d(v)>\delta(v)$ 矛盾。

故 BFS 得到所有可达顶点的最短距离。不可达顶点保持“未发现”，不具有有限距离；可达顶点都会被发现，因为沿任意一条从 $s$ 出发的路径，前一个顶点出队时都会检查下一个顶点。

怎样想到。 不要同时研究所有错误点。选择“真实距离最小的错误点”，它的最短路前驱就一定正确，这为推理提供了可靠起点。

相关遍历知识见 图的遍历。

例 11： Dijkstra 在哪里用到了非负边权

问题与规则。 边可以有不同权值，但所有权值非负。维护暂定距离 $d$，初始化 $d(s)=0$，其余为 $+\infty$。每次选出尚未确定、暂定距离最小的顶点 $u$，确定它的距离，再用它的出边尝试更新邻居。若最小暂定距离为 $+\infty$，就停止，可达部分已经处理完。

例如，有向边为 $s\to a$ 权 $4$、$s\to b$ 权 $1$、$b\to a$ 权 $2$。处理 $s$ 后，$d(a)=4,d(b)=1$；接着处理 $b$，把 $d(a)$ 改为 $3$；最后确定 $a$。

目标。 每次确定顶点 $u$ 时，都有 $d(u)=\delta(u)$。

每个有限暂定距离都是某条实际路线的长度，因此始终有：

$$d(v)\ge\delta(v).$$

准确否定。 假设算法会出错，取第一个被错误确定的顶点 $u$。此时：

$$d(u)>\delta(u).$$

在它之前确定的所有顶点，距离都正确。

推理与矛盾。 起点 $s$ 第一个被确定，距离为 $0$，所以不会是这个错误顶点。取一条从 $s$ 到 $u$ 的最短路径。在当前确定 $u$ 之前，设这条路径上第一个尚未确定的顶点为 $y$，它的前驱为 $x$。

于是 $x$ 已确定，而且距离正确。最短路径的每段前缀也最短：若某段前缀可缩短，就能缩短整条路线；在非负边权下，即使拼接产生重复顶点，也可以删去环而不增加长度，得到不更长的路径。

处理 $x$ 的出边时已经做过更新，因此：

$$d(y)\le d(x)+w(x,y) =\delta(x)+w(x,y) =\delta(y).$$

结合暂定距离不会低于真实距离，得到 $d(y)=\delta(y)$。

因为从 $y$ 到 $u$ 的剩余边权都非负，所以：

$$\delta(y)\le\delta(u).$$

而算法在所有未确定顶点中选择了暂定距离最小的 $u$，所以：

$$d(u)\le d(y)=\delta(y)\le\delta(u)<d(u).$$

这导致 $d(u)<d(u)$，矛盾。故每次确定的距离都正确。

怎样想到。 “第一个出错”保证此前的结果可以信任；在假想的更短路径上找“已确定与未确定的分界”，就能把已知正确的距离传递到待处理顶点。

非负边权用在哪里？ 上面比较 $\delta(y)\le\delta(u)$ 时用到了它。后半段如果含有负权边，越往后走，距离反而可能越小。

看一个没有负环的反例：

有向边	权值
$s\to a$	$2$
$s\to b$	$5$
$b\to a$	$-4$

标准 Dijkstra 处理 $s$ 后先以距离 $2$ 确定 $a$，但真正的最短距离是 $5-4=1$。这里讨论的是“确定后不再重新处理”的标准算法；允许反复处理顶点的变体，需要另外分析。

这既指出了证明的断点，也给出了真实反例。注意，含负边并不意味着每个输入都会出错，而是一般正确性保证已经失效。相关算法见 dijkstra。

例 12： 区间调度为什么优先选结束最早的区间

问题与规则。 给定有限个区间 $[s_i,f_i)$，其中 $s_i<f_i$。选择尽量多个互不重叠的区间，前一个结束时刻等于后一个开始时刻时，允许相接。每个区间的收益都是 $1$，目标是数量最多。

贪心策略是：每次在与已经选择的区间兼容的候选中，选择结束最早的那个。

例如：

区间	范围
$A$	$[1,3)$
$B$	$[0,2)$
$C$	$[3,4)$
$D$	$[4,5)$
$E$	$[2,5)$

贪心依次选择 $B,C,D$，共 3 个；$A,C,D$ 也能选 3 个。这已经提醒我们：正确的贪心选择未必出现在每个最优方案中。

目标。 贪心最终选择的数量最多。

准确否定。 设贪心得到 $m$ 个区间。假设存在一个最优方案 $O$，含 $k>m$ 个区间。把方案内的区间按时间先后排列。

推理与矛盾。 先比较第一步。设贪心选 $g_1$，最优方案的第一个区间为 $o_1$。因为 $g_1$ 结束最早：

$$f(g_1)\le f(o_1).$$

把 $o_1$ 换成 $g_1$。原来排在 $o_1$ 后面的区间，都在 $f(o_1)$ 之后开始，因此也都能接在 $g_1$ 后面。替换没有破坏合法性，区间数量仍为 $k$。

现在得到一个以 $g_1$ 开头的最优方案。继续比较第二步：贪心是在与 $g_1$ 兼容的区间中选结束最早的 $g_2$，所以可以用同样的理由，把这个最优方案的第二个区间换成 $g_2$。

一般地，若最优方案已经以前 $r$ 个贪心区间开头，则其第 $r+1$ 个区间也是贪心此时的合法候选。用 $g_{r+1}$ 替换它，既能接上已有前缀，又不会挤掉后面的区间，数量保持 $k$。因为区间长度为正，结束更早的 $g_{r+1}$ 也不可能是该方案中排在被替换区间之后的某个区间，不会产生重复选择。

重复 $m$ 次后，得到一个前 $m$ 个区间与贪心完全一致、总数仍为 $k>m$ 的合法方案。

但它还有第 $m+1$ 个区间，可以接在最后一个贪心区间之后。这与贪心已经没有合法候选、因而停止矛盾。

所以不存在数量更多的方案，贪心正确。空输入时两者都只能选择 $0$ 个，结论也成立。

怎样想到。 “结束早”不一定马上增加当前收益，却可能保留后续空间。证明时要把这句话落实为一个可检查的操作：替换之后，原来后面的选择一个都不受影响。

这里有两种方法配合：

• 交换论证负责把一个最优方案逐步改造成带有贪心前缀的最优方案。
• 反证法负责排除“存在一个比贪心选择更多的方案”。

只证明“第一步能换成贪心选择”还不够；还要说明后面的每一步都能重复，以及最终怎样推出整个方案最优。

辨错。 如果区间各自带有不同收益，仍选结束最早的区间，能沿用这个证明吗？

展开答案

不能。原证明使用“替换后区间数量不变”，因此目标值不变。若目标是收益总和，换掉一个区间可能损失收益。例如 $[0,1)$ 收益为 $1$，$[0,2)$ 收益为 $100$；结束最早的选择只能得到 $1$，最优收益却是 $100$。

例 13： 最小生成树的割性质

问题与必要概念。 有限连通无向带权图的生成树，是包含所有顶点、连通且无环的一组边。总权值最小的生成树叫最小生成树，简称 MST。

把顶点分为两个非空部分 $S$ 与 $V\setminus S$，称为一个割；两端位于不同部分的边叫跨割边。

目标。 如果 $e$ 是某个割的一条最轻跨割边，那么：

$$\exists\text{ 一棵最小生成树 }T,\quad e\in T.$$

注意这里是“某棵”，不是“每棵”。如果三角形的三条边权值全为 $1$，任意两条边都构成 MST，任意一条边都可以不选。

准确否定。 假设不存在包含 $e$ 的 MST，也就是：

$$\forall\text{ 最小生成树 }T,\quad e\notin T.$$

推理与矛盾。 图有限且连通，所以至少有一棵生成树，有限个生成树的权值也能取得最小值。任取一棵 MST，记为 $T$。

设 $e$ 的两端是 $a\in S,b\notin S$。在树 $T$ 中，$a,b$ 之间有唯一一条路径。沿这条路径从 $S$ 走到外部时，必定经过另一条跨割边 $f$。

因为 $e$ 是最轻跨割边：

$$w(e)\le w(f).$$

往 $T$ 中加入 $e$，它与原来的 $a,b$ 路径组成唯一的环；再删除环上的 $f$，得到：

$$T'=T-\{f\}+\{e\}.$$

$T'$ 仍然连通、无环，并包含全部顶点，所以仍是生成树。总权值满足：

$$w(T')=w(T)-w(f)+w(e)\le w(T).$$

由于 $T$ 已经最小，生成树 $T'$ 的权值又不可能更小，所以必有 $w(T')=w(T)$。于是 $T'$ 也是 MST，而且包含 $e$。

这与“所有 MST 都不包含 $e$”矛盾。因此，至少有一棵 MST 包含 $e$。

怎样想到。 希望某条边进入最优解，就先强行把它放进去，观察破坏了什么。树中加边只会产生一个环；找到环上不更轻的边删掉，就能恢复合法性而不增加代价。

此处如果 $w(e)=w(f)$，不能声称“找到了更小的生成树，与最优矛盾”。真正的矛盾来自：假设所有 MST 都排斥 $e$，却构造出一个接纳 $e$ 的 MST。

如果 $e$ 是该割唯一最轻的跨割边，则对其他跨割边有严格不等式 $w(e)<w(f)$。同样的换边过程就能证明：每棵 MST 都必须包含 $e$。

割性质是理解 MST 贪心选择的基础。要证明连续选择多条边的算法，还需保证每一步仍能与此前选择共同出现在某棵 MST 中；不能只凭“每条边分别属于某棵 MST”就断言它们能同时选入。相关内容见 最小生成树。

例 14： 不存在相邻逆序对，序列一定有序

问题与目标。 对有限实数序列 $a_1,\ldots,a_n$，“非降有序”指：

$$\forall\,1\le i<j\le n,\quad a_i\le a_j.$$

相邻逆序对是满足 $a_i>a_{i+1}$ 的相邻元素。要证明：

$$\bigl(\forall\,1\le i<n,\ a_i\le a_{i+1}\bigr) \Rightarrow \bigl(\forall\,1\le i<j\le n,\ a_i\le a_j\bigr).$$

例如，$1,2,2,5$ 没有相邻逆序对，也是非降有序的。“有序”允许相等，不是严格递增。

准确否定。 保留不存在相邻逆序对的条件，假设序列不满足整体有序。于是存在 $i<j$，满足 $a_i>a_j$。

推理与矛盾。 对位置 $i$ 到 $j$ 之间的相邻元素，前提给出：

$$a_i\le a_{i+1}\le\cdots\le a_j.$$

由大小关系的传递性，得到 $a_i\le a_j$，与 $a_i>a_j$ 矛盾。故序列非降有序。$n\le1$ 时没有需要比较的元素对，结论自然成立。

怎样想到。 整体不成立会给出一对具体位置；局部条件则能沿着这两个位置之间的链传递，把两者联系起来。

这一例直接证明也很短：将相邻不等式连接起来即可。反证法帮助我们看清“全局错误必须表现为某个局部错误”，但没有必要把所有简单证明都强行改写成反证法。

对于不断交换相邻逆序对的排序算法，这个结论只能证明“停止时有序”。还需要另外证明它一定停止、交换不改变元素集合，才能得到完整的排序正确性。

七、 从例子中提炼寻找矛盾的方法

7.1 根据题目条件选择突破口

题目中的线索	可以尝试的假设或选择	寻找的冲突
最大、最短、最优	假设还有更大的、更短的、更好的；或选取一个极端对象	违反极值的定义
不存在	假设存在，研究这个对象必须满足什么	条件无法同时满足
至少存在一个	假设所有对象都不满足	数量、总和或结构出现冲突
唯一	已证明存在后，再假设有两个不同对象	推出二者相等
有限、每个对象都有后继或前驱	不断追溯	重复、环或类别数量不足
算法每一步都正确	假设会出错，选第一次错误	此前正确结果迫使这一步也正确
某种选择可用于最优解	假设所有最优解都不包含它，尝试交换	构造出包含它的最优解

这些是尝试方向，不是看到关键词就一定适用的模板。例如，一个问题根本没有最优解时，不能先取“一个最优解”再讨论它。

7.2 “不更差”与“严格更好”产生不同的矛盾

设 $O$ 是最小化问题的最优方案，我们构造另一个合法方案 $O'$。

如果：

$$\operatorname{cost}(O')<\operatorname{cost}(O),$$

这就直接违反了 $O$ 的最优性。

如果只有：

$$\operatorname{cost}(O')\le\operatorname{cost}(O),$$

只能结合最优性得出二者代价相等、$O'$ 也是最优方案。要形成矛盾，还需要别的假设，例如“所有最优方案都不包含某个选择”，而 $O'$ 恰好包含它。

最小生成树例子中的等权换边，就属于后一种情况。换出另一个同样好的答案，并不否定原答案最优。

7.3 证明之外，还要检查条件与边界

每次写完证明，都可以重新检查：

1. 否定完整吗？ 是否把“不大于”写成了“小于”，漏掉等号？
2. 对象存在吗？ 取最优解、最长路径或最小错误点之前，是否有条件保证能取到？
3. 构造合法吗？ 新对象是否仍在原问题允许的集合内？
4. 矛盾指向哪里？ 最后一句能否明确指出被违反的前提或临时假设？
5. 证明覆盖整个目标吗？ 一次安全选择不等于完整贪心正确，停止时正确不等于必然停止。

例如，开区间 $(0,1)$ 没有最小元素。不能因为“里面有实数”，就直接取最小的一个。例 7 只证明“如果最小元素存在，那么它唯一”，并没有承诺每个非空集合都有最小元素。

八、 练习：先自己写，再展开答案

8.1 练习 1：给否定加上准确的量词

对以下陈述写出形式化否定：

1. 对数组中每个元素，都有 $a_i\ge K$。
2. 存在一个合法方案 $S$，代价 $\operatorname{cost}(S)<K$。
3. 若一个有限无向图连通，则它至少有 $n-1$ 条边。这里 $n\ge1$ 是顶点数。

展开答案

1. $\exists i,\ a_i<K$，其中 $i$ 属于数组的合法下标范围。
2. $\forall S\in\mathcal F,\ \operatorname{cost}(S)\ge K$，其中 $\mathcal F$ 为合法方案集合。
3. 存在一个有限无向图，它连通、顶点数为 $n\ge1$，但边数小于 $n-1$。既要否定边数结论，也要保留连通前提。

8.2 练习 2：补出最后的矛盾

证明：不存在一个最小的正实数。

已经写出：假设最小的正实数为 $x$。考虑 $y=\frac x2$。请补出后续推理，并说明同样的做法为什么不能证明“不存在最小正整数”。

展开答案

由 $x>0$，得 $0<\frac x2<x$。因此 $y$ 也是正实数，却比假设中最小的 $x$ 更小，矛盾。

对正整数，$\frac x2$ 未必还是正整数。特别是 $x=1$ 时，$\frac12$ 已经不在原集合内，构造不合法。

8.3 练习 3：独立证明平方根的无理性

证明 $\sqrt3$ 是无理数。可先证明辅助结论：若整数 $n^2$ 能被 $3$ 整除，则 $n$ 也能被 $3$ 整除。

展开提示

整数除以 $3$ 的非负余数只有 $0,1,2$。若 $n$ 的余数是 $1$ 或 $2$，则 $n^2$ 的余数都是 $1$。

展开完整证明

先证明辅助结论。假设 $3\mid n^2$，但 $3\nmid n$，则 $n$ 除以 $3$ 的余数是 $1$ 或 $2$，平方的余数都是 $1$，与 $3\mid n^2$ 矛盾。

再假设 $\sqrt3=\frac pq$，其中 $p,q$ 为互质正整数。于是 $p^2=3q^2$，由辅助结论得到 $3\mid p$，设 $p=3k$。代入得 $q^2=3k^2$，故 $3\mid q$。这与 $p,q$ 互质矛盾。因此 $\sqrt3$ 是无理数。

8.4 练习 4：识别缺少条件的图论证明

有人说：“只要一个有向图中每个顶点都有前驱，沿前驱不断找，就一定能找到环。”

这句话漏掉了什么条件？给出一个反例，再写出修正后的命题。

展开答案

漏掉了有限性。令顶点集合为所有整数 $\mathbb Z$，对每个整数 $i$ 都连边 $i\to i+1$。每个顶点都有前驱，但沿有向边行走时编号严格增加，不可能回到起点，所以没有有向环。

修正为：非空有限有向图中，如果每个顶点的入度都至少为 $1$，则图中存在有向环。

8.5 练习 5：为什么“更优解不存在”还要限定合法性

一个最小化问题的合法方案必须使用恰好 $3$ 个物品。某人拿走一个物品，把代价从 $10$ 降到了 $7$，然后宣布：“找到了比最优解更好的方案，矛盾。”

这份证明哪里错了？

展开答案

拿走物品后只剩 $2$ 个，已经不合法。最优性只是在合法方案集合内部比较。交换或构造新方案时，必须先验证所有约束，再比较目标值。

8.6 练习 6：等权换边能证明什么

证明 MST 割性质时，构造出的 $T'$ 与 $T$ 权值相等。以下哪句话正确？

1. $T$ 不是最小生成树。
2. 最小生成树一定唯一。
3. $T'$ 也是最小生成树；若原先假设所有 MST 都不含 $e$，则产生矛盾。

展开答案

第 3 句正确。相等的权值不违反 $T$ 的最优性，也不能证明唯一性。这里排除的是“所有最优解都不包含指定边”的假设。

8.7 练习 7：给排序算法补上终止证明

对有限序列，每次交换一对相邻逆序元素，直到不存在相邻逆序对。例 14 已证明停止时有序。

请证明这个过程一定停止。提示：把所有满足 $i<j$ 且 $a_i>a_j$ 的位置对数量记为 $I$，称为逆序对数量。

展开答案

$I$ 是非负整数，且至多为 $\frac{n(n-1)}2$。

交换相邻的 $x>y$ 后，二者之间的逆序对消失。对这两个位置以外的任意元素，它与 $x,y$ 的左右关系没有改变，涉及这两个元素的逆序对总数也不变，所以 $I$ 恰好减少 $1$。

假设算法不会停止，就会执行无限次交换，让一个有限的非负整数无限次减 $1$，最终小于 $0$，矛盾。因此过程一定停止。再结合停止时有序，以及交换保持原有元素及其出现次数不变，就得到完整的排序正确性。

九、 做题时怎样开始写

拿到一道需要证明的题，先写三行草稿：

已知：……

目标：……

如果目标不成立，那么：……

接着圈出已知或临时假设中的限制：最短、最多、互质、无环、有限、所有方案都不包含。尝试构造一个违反限制的对象；或者选择第一次错误、最小反例、最长路径，让已有条件变得更强。

最后检查：能否把结尾写成“这与……矛盾”，并准确填上那条条件。如果只能写“显然不对”，就回到推理中把冲突补出来。

学完后，不妨合上文章，任选一个数学例子和一个算法例子，自己写出完整证明。能独立说明否定了什么、利用了什么、矛盾在哪里，才算开始掌握反证法。

10 相关题解

暂无相关题解