逻辑学简要介绍

Brief Introduction to Logic

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

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

逻辑学常见术语

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

命题（Proposition）

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

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

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

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

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

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

布尔值（Boolean）

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

前提（Premise）和结论（Conclusion）

当命题较为复杂时，我们会常用“如果……，则……”之类的表述来承接条件和结论两部分。我们把前面“如果……”的条件部分称为前提（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$。

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

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

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

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

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

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

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

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

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

一些问题

下面我们针对于前面的内容列举一些你可能会有的问题。

问题 1：逻辑蕴含怎么还有真假性的？

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

这个问题解释起来有些复杂，咱还是换回 $P \to 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$，所以在逻辑学里，蕴含式可以用于真假性判断（虽然这并不是很常见），这种转化关系将蕴含式以命题拆解的另外一个说法表述了出来，变成了实在的、可以判断真假的命题，这是这个式子的意义。

问题 2：为什么互为逆否命题等价？

这一点我们可以尝试使用前文蕴含转化的方式来证明得到。我们将四种命题从蕴含的箭头改为逻辑或运算：

• 原命题 $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$，这便是为什么互为逆否的两个命题等价的本质原因。