Ⅲ：逻辑学简介

Logic Basics

数独技巧里经常使用一些逻辑学里惯用的一些思维。如果你对逻辑学并不熟悉，又需要了解的话，可以查看这一部分的内容。

由于教程内容用到众多逻辑学知识点，虽然读者可能不一定是计算机专业或数学系专业的学生，或相关的从业人员，但是为了确保读者能够衔接合适的内容，我打算在教程里插入逻辑学的相关内容方便读者阅读和查阅。

不过这里，我只会给各位介绍本教程会用到的一些常见的逻辑学知识点，并不会完整介绍逻辑学的全部内容，不然就本末倒置了不是。

逻辑学常见术语

先来说说逻辑学的术语或概念。

命题

首先，我们把一个可以判断对错的句子称为一个命题（Proposition）。这里所说的“可判断对错”，并不是说他有严格的正确或错误的倾向性，或者可以论证他的对错，而是说他从字面含义上，要回应/回答这个说法，一般用的是对或错、是或否、真或假这种只有两种对立面情况的词语就可以回应的句子。

比如说，“我有一部小米 15 的手机”。这个句子就是一个命题，因为它只会有“是”或“否”两种状态来回应这个句子。再比如“如果今天我起床之前感冒还没好，我就请假不去上班了”，也是一个命题。

那么，什么不是命题呢？其他的句子。比如说“今天的外卖好吃吗？”就不是命题。首先，它是一个疑问句，其次疑问句的回应对与错并不是用来判断说法的对错的，而是回答这句话的结果的。

再比如说，“我这结婚这事情八字还没一撇呢”也不是命题。这种句子甚至都不是用于回应对错的。

这便是命题的基本概念。可以看出，命题要能表述出对错判断的那个意味，与此同时还只能是一个陈述句。疑问句、祈使句、感叹句全都不是命题。

另外，我们把最基础的、无法继续被拆分的命题称为原子命题（Atomic Proposition）。比如“我有一部小米 15 手机”就是原子命题，因为它没办法继续拆成小的命题了；但是“如果今天我起床之前感冒还没好，我就不去上班了”就不属于原子命题。因为它其实暗含了两个小的命题“今天我起床之前感冒还没好”和“我不去上班”，他们单独拆解出来虽然没有啥意义，但是因为他俩拆出来是可以满足命题的基本定义的，所以带有“如果……则……”的说法的都不属于原子命题。

布尔值

逻辑学经常使用对/错这种说法。在严谨的学科范畴里，对和错一般称为真（True）和假（False）。如果我们把他类比于数字里整数、小数视为同样的表达，也用来衡量数据表示一个量的话，那么真假我们会称为是一个布尔值（Boolean Value，简称 Boolean 或 Bool）。就是说，整数集合包含 0、1、-3 这些，小数包含 0.3 啊、自然常数 e 啊这些。那么相应地，布尔值的集合就只有 true 和 false 两个值。

前提和结论

当命题较为复杂时，我们会常用“如果……，则……”之类的表述来承接条件和结论两部分。我们把前面“如果……”的条件部分称为前提（Premise），而后面的“则……”的部分称为结论（Conclusion）。

这种命题是一种特殊的命题，它具有严格的推论过程，我们后面描述的内容也多以这种结构化的命题出现。

一般的命题，如“地是湿的”，并不能完整表达一些我们严格要说明的内容；但是如果搭配了前提和结论两部分，那么句子就会比较饱满：“如果下雨，地就会被打湿”。这也是我们比较常见的命题类型。

不过要注意的是，这种带有前提和结论的命题类型，前提不一定非得只有一个，可以有多个同时作为条件；也可以使用逻辑的“而且”、“但是”、“或者”搭配形成复杂的结构。

逻辑学符号

针对于前文，我们会用到两部分的符号：命题的表示，以及构造复杂命题用到的连接符号。

命题符号

先来说命题。我们把一个个的原子命题用大写字母 $P$、$Q$、$R$ 等等表示。因为命题的英文单词是 proposition，所以用的是 P；另外，和一般数学变量一样，也是存在多个变量（命题）时直接让选取的字母往字母表后面依次排列就行）。

逻辑符号

我们使用如下的一些符号来联立多个命题：

• 命题取反：$\lnot P$（读作“非 P”）；

• 命题合取：$P \land Q$（读作“P 且 Q”）；

• 命题析取：$P \lor Q$（读作“P 或 Q”）；

• 命题蕴含（也写作“蕴涵”）：$P \to Q$（读作“如果 P 则 Q”）；

• 命题双条件：$P \leftrightarrow Q$（读作“P 当且仅当 Q”）；

• 命题等价：$P \equiv Q$（读作“P 等价于 Q”）。

举个例子。“如果你回家的路上看到了水果店开着，就买一个西瓜”。这个命题拆解成原子命题后有四个部分构成：

• $P$：我回家

• $Q$：我在路上

• $R$：水果店开着

• $S$：我买一个西瓜

于是，这四部分用上述符号表示出来是这样的：

$$P \land Q \land R \to S$$

有人问，这回家和在路上不是一起发生的吗？这还用得着拆成两部分？其实是必要的。因为你回家确实是在路上，但是你在路上不一定暗示你是往家的方向前进。他俩描述的内容从命题的角度来说并不是同一个，只是恰好在这个例子里是包含关系罢了。

推导符号

另外，我们还使用横线表示推断关系，例如“如果条件如何如何，那么我们可以得到什么什么”。这种命题的后半段（结论部分）不是一个简单的命题，而是下结论。我们把下结论记为 $\therefore P$（读作“所以 P”）或 $\vdash P$（读作“推出/得出 P”）。

那么我们假设我们把上面的说法稍加改良。一旦有上面“让他回家路上买西瓜”作为先决条件的话，那么假设他真的带了西瓜回家，我们就可以得到水果店开着的结论。这个可以记作

$$\frac{P \land Q \land R \to S, S}{\therefore R}$$

其中逗号分隔不同的命题，表示罗列，也可以理解为数学上的联立式子。当然，一般也可换行写：

$$\frac{ \begin{matrix} P \land Q \land R \to S \\ S \end{matrix} }{\therefore R}$$

当然，也可以写成一行的形式，就不用横线了，用旋转门符号 $\vdash$。

$$(P \land Q \land R \to S) \land S \vdash R$$

等价式子

根据前面列举的内容，我们知道符号都是怎么写了。下面我们来看看一些常见的等价式。

• 分配律

  • $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$

  • $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$

• 交换律

  • $A \land B \equiv B \land A$

  • $A \lor B \equiv B \lor A$

• 结合律

  • $(A \land B) \land C \equiv A \land (B \land C)$

  • $(A \lor B) \lor C \equiv A \lor (B \lor C)$

• 排中律和矛盾律

  • $A \lor \lnot A \equiv \text{True}$

  • $A \land \lnot A \equiv \text{False}$

• 双重否定律

  • $\lnot \lnot A \equiv A$

• 德摩根律

  • $\lnot (A \land B) \equiv \lnot A \lor \lnot B$

  • $\lnot (A \lor B) \equiv \lnot A \land \lnot B$

• 双条件分解

  • $A \leftrightarrow B \equiv (A \to B) \land (B \to A)$

• 蕴含转化

  • $A \to B \equiv \lnot A \lor B$

其中部分公式比较难以理解，我们暂且不表。我们先回到命题上来。

命题的等价性

在逻辑学里，我们对命题（尤其是描述为“如果……则……”的命题）有严格的真假性等价判断。不过这里我们要介绍四种命题说法。

• 原命题（Source）：最初的那个命题，即 $P \to Q$；

• 逆命题（Converse）：将前提和结论两部分倒置，产生的新命题，即 $Q \to P$；

• 否命题（Inverse）：将前提和结论的描述都取反，产生的新命题，即 $\lnot P \to \lnot Q$；

• 逆否命题（Contrapositive）：将前提和结论均取反后倒置，产生的新命题，即 $\lnot Q \to \lnot P$。

多数时候，逆命题、否命题和逆否命题我们都不是很关心。但是在数独技巧里，我们有时会需要灵活运用这些命题的转换，以便帮助我们理解有些复杂的逻辑。

我们拿一个例子来说明这四个命题。比如说“如果我感冒了，我就会流鼻涕”。下面我们将这个命题转换为这四个命题的说法：

• 原命题：如果我感冒了，我就会流鼻涕；

• 逆命题：如果我流鼻涕了，我就感冒了；

• 否命题：如果我不感冒，我就不会流鼻涕；

• 逆否命题：如果我不流鼻涕了，我就不感冒了。

在逻辑学里，只有互为逆否的命题的真假性才等价。什么意思呢？简单来说就是，原命题和逆否命题同真假性，逆命题和否命题同真假性。

显然，逆命题和否命题也没看出来有什么问题。但是实际上，这两个说法的真假性和原命题其实没有关系。原命题阐述的是感冒和流鼻涕的关系；但流鼻涕就一定是感冒引起的吗？鼻炎有时候也会造成流鼻涕的问题。所以严格来说，逆命题这个说法并不成立。当然，否命题也是如此：我不感冒，万一有鼻炎呢，不也流鼻涕吗。

说实话，我们最常在生活中因为逆命题和否命题的理解问题造成判断失误的情况。我们一定要时刻记清楚“只有互为逆否的命题才是等价的”这一点。

常见逻辑推理技巧

下面介绍本教程惯用的一些基于逻辑学的推理技巧。

分情况讨论和析取消去

这个板块主要介绍的是前面教程里用到的一些更靠近数学知识的一些逻辑，以及他们在数学上严格表达的内容。

首先需要介绍的是第一种用到的逻辑：分情况讨论（Proof of Cases）。分情况讨论也叫分类讨论，指的是将一个需要证明的东西按多个情况拆解开来，并逐个击破。

基本规则

在之前的教程内容里，经常用到这样的证明：

• 如果情况 A 成立的话，则某个结论会得到；

• 如果情况 A 不成立的话，则这个结论仍然可以得到。

由于情况 A 的正反两面涵盖了全部情况，但由于他们均可得到相同的结论，所以这个结论必然是正确的。这就是一种典型的分情况讨论的思路。

不过，从逻辑学上讲（严格来说是叫命题逻辑），我们把这个说法称为析取消去（Disjunction Elimination）。其中“析取”表示对两个或多个情况取“并集”，也就是联立情况的意思。这是个数学上的术语，符号记作 $\lor$，读作“并”；“消去”则指的是在推导下均可达成相同结论，进而归并情况，消去冗余的部分。

我们不妨举个例子。

• 如果我在家里，我会戴着手表；

• 如果我走出门，我也会戴着手表。

所以，我一直都戴着手表。

可以通过这个说法看出，它同时涵盖了家里和出门两种状态，而这个显然是“我”的全部可能的地点的取值，因此我们可归纳为“我”的地理位置的所有情况。

因为全部情况下都戴着手表，所以会一直戴着手表。

当然，也有读者会觉得“我”并非随时都戴着，例如睡觉什么的。如果你这么想的话，那么你还是没有理解它想表达的“所有情况”的含义。

我们再拿一个比较数学一点的命题举个例子。

• 如果 $x$ 为负数，则 $x^2$ 为正数；

• 如果 $x$ 为正数，则 $x^2$ 仍然为正数。

所以，$x$ 只要不为 0，则 $x^2$ 始终都是正数。

我们只需要归纳出一个情况的全部状态，并逐个列举后得到一致结论时，我们就可认为这个结论是正确的。这个称为析取消去。

数学表达

在命题逻辑里，析取消去是有严格的表达方式的。

如果我们想要表示命题和结论的这种映射关系的话，我们一般是用横线表示这种关系。

$$\frac{P\rightarrow R, Q\rightarrow R, P \lor Q}{\therefore R}$$

这是抽象出来的式子表示。另外，数学上用 $\therefore$ 来表示“所以”，不过在命题逻辑里因为横线上方是命题部分，下方是结论部分，所以一般也可省略不写，即“$\therefore R$”也可以直接记作“$R$”。

反证法

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

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

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

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

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

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

基本规则

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

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

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

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

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

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

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

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

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

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

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

数学表达

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

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

$$\frac{\vdash \lnot \lnot P}{\vdash P}$$

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

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

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

逻辑蕴含

在之前（例如牺牲）的内容里我们遇到过蕴含式的用法，下面我们对蕴含进行一个完整的阐述。

基本规则

蕴含，也叫蕴涵，指的是我们在平时使用“如果……就会……”、“如果……则……”之类说法的一个特殊表达。这种说法本来只表示一种承前启后的关系，但是因为在逻辑学中，它被定义为了一个表达式，所以它成为了一种连接两个命题的运算，记作 $P \to Q$。

这个箭头暗示着我们的过程是从前面往后面推导。而这个运算还有一个特殊结果 $\lnot P \lor Q$。

结果推算

不知道你有没有发现前面蕴含的表达式很诡异。首先是蕴含用的箭头推出，暗示的是前提部分和结论部分的这种推出关系。但这玩意儿怎么还有真假性判断的？而且，$P \to Q$ 这玩意儿怎么还可以等价转换成 $\lnot P \lor Q$ 的？

这个问题解释起来有些复杂，我们把他具象化为一个实际例子给各位解释一下。

假设我说两个命题 $P$ 和 $Q$ 分别代指的是“考到驾照了”和“带你去兜风”。也就是说 $P \to Q$ 指的是“如果考到驾照了，就带你兜风”。

在这个说法下，我们需要尝试罗列 $P$ 和 $Q$ 的所有真假情况进行一一排列，于是就会有四种。

• $P, Q$：考到驾照了、带你去兜风；（合理）

• $P, \lnot Q$：考到驾照了、不带你去兜风；（不合理）

• $\lnot P, Q$：没有考到驾照、带你去兜风；（合理）

• $\lnot P, \lnot Q$：没有考到驾照、不带你去兜风。（合理）

在你尝试把这些信息进行组合的时候，你会发现一个很神奇的点：只有第二种组合 $P, \lnot Q$ 不合理。第一种合理是废话；第三种和第四种也合理看起来有点别扭。不过你要这么想：考到驾照才带你去兜风；但是“没考到驾照”并不在“考到驾照”的前提条件下，所以最终兜风与否其实是不一定的。不确定是否发生问题其实并不大，而更大的问题其实只在于第二个和假设直接相悖的说法。换言之，蕴含最终表示的是这三种组合的全部情况的联立状态。

所以四个组合里只有第二种明确不符合题意。那么我们尝试把这个三个式子联立起来，即

$$P \to Q \equiv (P \land Q) \lor (\lnot P \land Q) \lor (\lnot P \land \lnot Q)$$

我们使用前面所学到的公式进行化简：

$$\begin{align*} P \to Q &\equiv (P \land Q) \lor (\lnot P \land Q) \lor (\lnot P \land \lnot Q)\\ &\equiv (P \land Q) \lor ((\lnot P \land Q) \lor (\lnot P \land \lnot Q)) &\text{结合律}\\ &\equiv (P \land Q) \lor (\lnot P \land (Q \lor \lnot Q)) &\text{分配律} \\ &\equiv (P \land Q) \lor \lnot P &\text{排中律} \\ &\equiv \lnot P \lor (P \land Q) &\text{交换次序} \\ &\equiv (\lnot P \lor P) \land (\lnot P \lor Q) &\text{分配律}\\ &\equiv \lnot P \lor Q &\text{排中律} \end{align*}$$

这样我们就有了最后的这个结果。

所以，因为我们有 $P \to Q \equiv \lnot P \lor Q$，所以在逻辑学里，蕴含式可以用于真假性判断（虽然这并不是很常见），这种转化关系将蕴含式以命题拆解的另外一个说法表述了出来，变成了实在的、可以判断真假的命题，这是这个式子的意义。

为什么互为逆否的命题等价

之前我是要求各位按结论记住的。而对于这一点而言，我们可以尝试使用蕴含来证明得到为什么是等价的，而且很简单。

我们将四种命题从蕴含的箭头改为逻辑或运算：

• 原命题 $P \to Q \equiv \lnot P \lor Q$；

• 逆命题 $Q \to P \equiv \lnot Q \lor P$；

• 否命题 $\lnot P \to \lnot Q \equiv \lnot \lnot P \lor \lnot Q \equiv P \lor \lnot Q$；

• 逆否命题 $\lnot Q \to \lnot P \equiv \lnot \lnot Q \lor \lnot P \equiv Q \lor \lnot P$。

可以看出，逆命题和否命题均等于 $Q \lor \lnot P$，原命题和逆否命题均等于 $P \lor \lnot Q$，这便是为什么互为逆否的两个命题等价的本质原因。