反证法

Proof by Contradiction

除了前面分情况讨论外，我们也经常使用反证法来得到删数结果的成立：

• 假设某个候选数是正确的填数，那么我们会因为一系列的推演得到一个矛盾。

所以这个假设是错误的，因此候选数不是正确的填数，应被我们删除。

这种处理逻辑被我们称为反证法（Proof by Contradiction）。

从逻辑的角度来看，我们往往是因为候选数无法判别是否正确，因此我们先假设成正确的填数，进而开始推演。为什么我们非得经常假设填入进去而不是假设它上来就是错误的填数呢？这是因为，盘面在全标后，由于一个单元格最终只能填入一个正确填数，所以剩余的所有候选数从答案的角度来看，均是错误的填数。

正是因为我们无法确保哪个数字正确，那很明显我们知道，假设数字正确而得到删数的逻辑性价比更高，毕竟大多数候选数都是错误的。这便是我们使用反证法的底气。

基本规则

下面我们针对于反证法举例。先还是说一个生活中的例子。

假设一个场景。比如说你晚上下班离开了公司锁上了办公室。但是第二天发现门打不开了。于是你开始怀疑起钥匙丢在哪里了。

在这个例子里，很明显钥匙是不会遗忘在办公室里的。这一点可以用反证法得到：

• 如果你的钥匙在办公室里，那么门在下班的时候就锁不上，因为你没钥匙锁这个门。

所以，钥匙不可能在办公室里。

这个例子比较容易理解。下面我们来看另外一个数学上的证明例子。

数学上有一个东西叫质数，也叫素数。指的是一个大于 1 的整数，这个数无法找出两个正整数相乘能等于它自己。当然，这里“1 乘以自身等于自身”的说法就不算了，因为所有正整数都具备这个特性。

我们要证明质数的数量是无限多的。看起来这很难证明。但实际上反证法却可以绕开任何的数学公式给予正确答案：

• 如果质数的数量是有限的的话，那么我们将所有质数全乘起来，它肯定不是质数。但是，只要我们将这个结果再加 1 个单位，就无法被任何数整除了。换言之，就不能找出两个数乘起来等于它了。

所以，质数的数量是无限多的。

可以看到，很多时候显得非常“无力”的反证法，在一些时候也会发挥它非常不错的作用。

数学表达

下面还是讲一下它的数学表达。

我们把“可以得到命题成立”记作 $\vdash P$，并把对命题的假设取反记作 $eg P$。有了这些个写法后，我们用前文的横线记号可得反证法的记号为：

$$\frac{\vdash \neg \neg P}{\vdash P}$$

这个记号理解为“如果可得到 $P$ 命题的反面情况的反面情况成立，则可得到 $P$ 命题成立”。

可能你一脸懵逼。这为啥要双重取反，这不负负得正了么，还用得着证明？实际上你得把这个两个取反记号 $eg$ 看成两个不同的意思。内层的 $eg P$ 表示一个新的命题，只是这个命题是和原来的命题想证明的内容完全相反；而外层的取反记号则要看成是在说里面的 $eg P$ 这个新命题是被证伪了，即被证明是错误的了。因为取反后可得到是错误的，所以 $P$ 自身正确。

不过这里要补充一句。旋转门记号 $\vdash$ 也可以使用划斜杠的写法，即 $ot\vdash$ 表达。但是，这并不是说“能证明这个说法是错误的”，而是说“不能证明得到”。所以不要用错了。