反证法:从「假如不是」开始

要证 P,先假设非 P,推到一个明确的矛盾,于是非 P 站不住。关键在两处:非 P 到底是什么,以及矛盾必须真的来自这个假设。

5 分钟思维方法: 反证

先假设结论不成立,把自己逼进死胡同

这一片为什么存在

证明写到第三行推出了矛盾,老师却在第一行画了个圈。问题不在推理,在那句「假设不是这样」——它把「至少有两个锐角」的反面写成了「一个锐角都没有」。反面一旦写歪,后面每一步算得再对也全部作废。这一片要做的事很小:把「假如不是」这四个字拆开,看清它该怎么写,以及撞出来的墙算不算数。

内容

先看一个不是反证法的东西。有人要证「任意三角形至少有两个锐角」,随手画一个直角三角形,指着那两个 45° 角说「你看,成立」。这只是一个例子。例子能推翻「所有」,但不能证明「所有」。

反证法走的是另一条路:不去正面搭桥,而是把对岸以外的地方全部封死。要证结论 P,先当作 P 是假的,顺着这个假设往下推,一直推到一件不可能的事——比如某个三角形的内角和超过 180°。既然从「非 P」出发必然撞墙,「非 P」就站不住,剩下的只有 P。

这里有两处最容易滑手。

第一,「非 P」到底是什么。「至少有两个锐角」的反面是「至多有一个锐角」,不是「一个锐角都没有」。把「不是所有」读成「所有都不是」,等于只封死了半边,另半边的路还敞着,证明就漏了。

第二,撞的墙必须是假设撞出来的。如果推导中间用错了公式,或者顺手引进了一个本来就自相矛盾的条件,那矛盾是你自己带进去的,跟「非 P」无关。检验办法很朴素:把假设那一句删掉,矛盾还在吗?还在,就说明它不该由假设背锅。

记待证命题为 P。反证法的骨架是:设 ¬P(读作非 P,即 P 不成立),由 ¬P 连同已知条件 H 推出某个 Q 与 ¬Q 同时成立,这就是矛盾,记作 ⊥。既然 ¬P 导致 ⊥,¬P 不可能成立,于是 P 成立。

带量词时要小心两条改写:
¬(∀x)A(x) 等价于 (∃x)¬A(x);
¬(∃x)A(x) 等价于 (∀x)¬A(x)。
其中 ∀ 读作「对每一个」,∃ 读作「存在一个」,A(x) 是一句关于 x 的话。

还有一条隐含要求:H 自身必须无矛盾。否则单凭 H 就能推出 ⊥,这跟 ¬P 毫无关系,整个证明是空转。

跟着做一遍

证明:任意三角形至少有两个内角是锐角(小于 90°)。动笔前先把「非 P」原原本本写出来,再往下推。

  1. 写出 P:三个内角中至少有两个小于 90°。
  2. 写出 ¬P:锐角至多一个,也就是至少有两个角不小于 90°。注意它不是「三个角都不小于 90°」。
  3. 把这两个角记作 α 和 β,于是 α ≥ 90°,β ≥ 90°,相加得 α + β ≥ 180°。
  4. 第三个角记作 γ,作为三角形的内角必有 γ > 0°。
  5. 用先修的内角和:α + β + γ = 180°。
  6. 代入得 180° = α + β + γ ≥ 180° + γ > 180°,即 180° > 180°,矛盾。
  7. 检验矛盾的出处:删掉第 2 步的假设,α + β ≥ 180° 就没了,矛盾随之消失,说明它确实由 ¬P 逼出来。
  8. 故 ¬P 不成立,P 成立。

结果

任意三角形至少有两个锐角。比结论更值得带走的是那两道检查:¬P 写成的是「至多一个锐角」而非「没有锐角」;删掉假设后矛盾就消失,证明这堵墙是假设撞出来的,不是自带的。

它在树上的位置

概念不是一篇一篇平铺的。下面两组是这一片真实的上下游:它靠着什么,又撑起了什么。

它靠着

它撑起

图上还没有概念把它列为先修。

读完之后

这一页是产品里的一天。产品是那棵树:你学到哪、哪块在衰减、明天该学什么。一篇读物回答不了这三个问题,树才回答。

看看那是什么意思