元数学：命题逻辑和谓词逻辑

Tip

没写完，鸽了。

写在最前面：无需定义的定义

在数学中，我们常常习惯给事物一个定义。比如，我们把偶数定义为“能够被 2 整除的数”。给出一个范围，约束一个性质，只要保证约束是无矛盾的，就可以作为一个合理的定义。因此，给出一个定义常常是比证明一条定理更简单的事情，因为后者需要创造一个推理过程，而前者只需要检验合理性。

但是，当我们涉及到逻辑学或是集合论这样的领域，尤其是试图将它们进行公理化建构时，却发现定义似乎不是那么容易了。究其原因，是因为之前所作的定义，是一个从已知到未知的过程；而对于逻辑学或集合论，它们是数学大厦的基础，在他们之前，根本没有什么是“已知”的，自然没法从一片虚无中衍生出什么东西。

于是这个时候，我们不得不接受“无需定义的定义”。我们需要承认，**有一些东西，是无需定义也天然存在的。**我们无法结构化地描述它们内在的组成，只能形式化地给出它们所适用的外在的规则。比如在公理化集合论里，我们不去定义什么是集合，什么是元素，什么是属于关系，我们只是给出了“属于关系是一个可以作用于集合和元素的二元关系”这一说明。再比如在后文中提到的“个体对象”“谓词”，都是这样的“无需定义的定义”。

如果觉得这仍旧难以理解，不妨做一个类比。在数学中，我们承认公理的存在，公理无需证明就天然正确。而其余的定理，都是从公理中演绎出来的。公理可以无需证明就成立，那么为什么不能有无需定义就存在的东西呢？

命题逻辑

个体对象、逻辑运算符和命题

如前文所述，“个体对象”是一个无需定义的概念，但这并不妨碍我们用直观的方式来理解。

生活中，我们经常会做出各种论断，比如“天是蓝的”“地球是圆的”。这种简单的论断，就是命题的一种，我们称之为原子命题。其中涉及到的各个对象，比如“天”“地球”“蓝”，就是个体对象。

虽然直观来看，原子命题是由个体对象“组装”而成的，但是在命题逻辑里，我们并不知道、也不关心这个“组装”的过程到底是怎样的。命题逻辑把原子命题看作一个不可分的整体，至于个体对象形成命题的过程，要到谓词逻辑才能进行研究。

**原子命题通过一系列逻辑运算符连接，就能得到命题。**如果直观理解，这里的逻辑运算符，是与（$\wedge$）或（$\vee$）非（$\neg$）等组成的一个全功能集。而如果从头开始定义，我们需要选取其中能构成全功能集的一组，对它的性质加以说明，再从中得出其余的运算符。以下定义：

1. 原子命题是命题。
2. 原子命题通过逻辑运算符连接而成的，是命题。
3. 如果$\ast$是一个一元逻辑运算符，$A$为命题，那么$\ast A$也为命题。
4. 如果$\oplus$是一个二元逻辑运算符，$A$和$B$为命题，那么$A\oplus B$也为命题。

这是一组递归定义，并且它给出了命题的完整定义，利用这些我们就可以判定什么是命题。

但对于命题逻辑而言，这些仍旧是不完整的，因为我们还不知道逻辑运算符除去连接命题以外有何作用。但在研究逻辑运算符有何作用之前，我们需要先思考一个问题：既然我们正在做的事情，就是定义逻辑命题如何演算，那么传统的公理化方法，在这里依然适用吗？

形式系统

在集合论公理化的过程中，我们给出了一组公理，然后用他们推导出一系列定理，虽然烧脑，但还是在可接受的范围内的。但到了逻辑学，问题出现了：以往我们是用命题来描述对象的性质，现在我们正在定义什么是命题，那么怎么描述命题本身的性质？

现在只使用数学以内的工具是不行了，因为目前数学以内还没有什么工具是可用的。但方法总还是有的：数学总需要以语言作为载体，要研究数学本身的规则，可以从语言入手。

于是，在 1921 年，希尔伯特提出元数学的概念，并使用形式系统研究元数学。**形式系统是一套形式语言和形式规则的总和。形式语言是对于字符串（字符串是一系列符号的可重复有序排列）是否符合某种形式的论断。**这里我们可以放心地使用“论断”这个词，因为它不是对于一个数学命题的描述，而是在数学之外的对于语言的描述。有些地方使用集合论的语言来定义形式系统，但本文不采用这种做法，因为集合论的公理化是建立在谓词逻辑基础上的，而定义形式系统时，用到的不是完整的公理化集合论，只是简单的朴素集合论语言。

现在，让我们用形式语言的方式，重新写一下命题的定义：

1. 命题涉及到的符号分为三类，原子命题（一般用字母表示）和逻辑运算符。
2. 命题的形式包括：
   1. 原子命题。
   2. 一元逻辑运算符后紧跟着一个命题。
   3. 由二元逻辑运算符连接的两个命题。
   4. 有限次重复使用以上规则，得到的字符串。

注意上面最后一条的说法，这表示命题是一个递归定义。递归定义在形式语言的定义中很常见，因为往往我们无法穷举所有的字符串，只能以递归的方式消解复杂性。

此外，为避免形式语言的歧义，可以在命题中添加括号，来规定逻辑运算符结合的对象。括号的具体规则并非本文的重点，不再赘述。

以刚才的这种方式，给出形式语言的一个定义，称为形式规则。顾名思义，形式规则描述了字符串形式和形式语言之间的关系。一个形式规则包含若干条这样的论断：满足某种形式的字符串是（或不是）某个形式语言。

有了这样的形式规则，我们取一元逻辑运算符为$\neg$，二元逻辑运算符为$\to$，就能够对一些东西是不是命题做判断了，例如：

• $A$是命题，且是原子命题。（规则 1）
• $\neg A$是命题。（规则 1、2）
• $A\to B$是命题。（规则 1、3）
• $A\to (B\to A)$是命题。（规则 1、3、4）
• $(\neg A\to \neg B)\to (B\to A)$是命题。（规则 1、2、3、4）
• $A\to \to A$不是命题，因为形式规则不允许两个二元逻辑运算符直接相邻。
• $\forall x,x^2>0$不是命题，因为量词$\forall$不是原子命题也不是逻辑运算符。做出这种论断，是因为我们仅在命题逻辑的范畴内定义了命题，而对于谓词逻辑，我们会扩充命题的定义，使得$\forall x,x^2>0$也能成为命题。

在形式系统中，我们把符合某些形式规则的字符串，称为合式公式（又称合适公式，英文 well-formed formula，简称 wff），简称公式。因此，有时我们又把命题成为命题公式，因为命题的名称可能与原子命题混淆。

重言式、公理模式

现在，有了命题的定义，我们再来思考一个问题：什么是真命题？

在拥有形式系统这一工具之前，这个问题也许会有五花八门的答案。但从形式系统的角度，结论只有一个：真命题也是一个形式语言，当然，使用的形式规则和命题公式不同。真命题的形式语言称为重言式（读音：chóng yán shì），也可以直接叫做永真式或者真命题。

有形式语言，就有对应的形式规则。在命题逻辑中，当取一元逻辑运算符为$\neg$，二元逻辑运算符为$\to$时，重言式的形式规则包括：

1. （代入规则）对于一个重言式中的某一个符号（原子命题），如果把相同符号全部替换为另一个命题，得到的仍是重言式。
2. （肯定前件）对于重言式$p$和命题$q$，如果$p\to q$是重言式，那么$q$也是重言式。

对于肯定前件，有一点需要指出：**这里的$p$和$q$指的不只是原子命题，而是命题公式。**也就是说，任何符合这一模式的两个命题，都能适用这条规则。比如，当$A\to B$和$(A\to B)\to (A\to C)$为真时，$A\to C$也为真。

像这样对命题公式的形式进行模式上的匹配，然后作出论断的形式规则，又叫做公理模式。一般情况下，狭义的公理模式仅限于对重言式的论断。

代入规则使得一般的命题也可以作为公理模式使用。也许你会留有一点疑虑，如果$A\to B$而$B$是重言式，是不能轻易将$B$替换掉的，但实际上，代入规则只能代换原子命题，而一个单独的原子命题是无法成为重言式的。这也是有的地方把恒真（$\top$）和恒假（$\perp$）作为零元逻辑运算符，而不是作为原子命题处理的原因。

上面所说的两条，并不是重言式完整的形式规则。在命题逻辑中，当取一元逻辑运算符为$\neg$，二元逻辑运算符为$\to$时，重言式的一个完整的形式规则由扬·武卡谢维奇给出，这一组规则称为希尔伯特演绎系统：

1. （代入规则）对于一个重言式中的某一个符号（原子命题），如果把相同符号全部替换为另一个命题，得到的仍是重言式。
2. （肯定前件）对于重言式$p$和命题$q$，如果$p\to q$是重言式，那么$q$也是重言式。
3. $p\to (q\to p)$是重言式。
4. $(p\to (q\to r))\to ((p\to q)\to (p\to r))$ 是重言式。
5. $(\neg p\to \neg q)\to (q\to p)$是重言式。
6. 有限次运用以上规则，得到的字符串是重言式。

这些形式规则中，2、3、4、5 都可以用作公理模式。其中 3、4、5 条中的$p,q,r$指的是原子命题，但是在代入规则下，可以用命题公式代入，因此这三条也能作为公理模式。

与重言式对应的，假命题的形式语言称为矛盾式。矛盾式的形式规则很简单：如果命题$p$满足$\neg p$是重言式，那么$p$是矛盾式。

形式逻辑与自然逻辑

在上一节，我们几乎不加任何思考就接受了“重言式是形式语言”这个说法，但是回过头来，思考一下，这个说法真的很正常吗？

如果你完全感觉不到问题，要么说明你是个理解能力极强的天才，要么说明你对形式语言还存在一些误解。

形式语言作为一个工具，最早是作为判断一个字符串是否符合文法被发明的，这也是我们对于形式语言最容易接受的理解。这种理解在编程语言中应用最广，比如判断f(&a)->b是不是一个合法的 C 语言表达式，就是看他是否符合 C 语言的形式规则。再比如前面提到的命题公式，也是形式语言的这种应用。

在这个过程中，我们做的是“组合”的工作。原子命题是最小的命题，其余所有的命题都是由原子命题和逻辑运算符组合起来的。这个过程中，命题总是越组合越长。在验证一个字符串是不是命题的时候，我们先用规则进行匹配，找到它的子串，再看子串是不是命题。也就是说，创造命题是从小到大的组合，验证命题是从大到小的拆解。

但是，真命题，或者说重言式，这个概念似乎并不符合这一的特点。数学追求简洁的美，但如果真命题只能由其他命题组合而来，得到的结论只能越来越长，与简洁背道而驰。所以，我们需要一个手段，能够在创造的过程中，把组合过的命题拆解开，给出简短的答案。

再来看一看希尔伯特演绎系统里的这些规则，可以发现，1、3、4、5 都是在说命题如何组合，只有肯定前件在描述如何拆开一个命题。它揭示了$q$作为一个重言式$p\to q$的一部分，也有成为重言式的可能。

而当我们去“证明”一个命题，也就是说明这个命题是重言式的时候，我们实际上是在寻找一个更大的、包含我们的目标的命题，然后说明它可以通过肯定前件简化到我们的目标。

也就是说，**肯定前件是重言式和其他的形式语言最重要的区别。**因为肯定前件的存在，重言式可以在创造时进行拆解，在验证时进行组合，这就极大拓展了形式语言的表现力，为我们实现逻辑提供可能。

现在我们解决了为什么能够用形式语言表示重言式的问题。下一个问题是：为什么应该用形式语言表示重言式？

这个问题的答案可以有很多，但最重要的原因在一开始就提到了——因为在此时，我们几乎没有可用的工具。

也许你会想：形式语言是不是唯一的答案？那么，让我们设想一下，如果不使用形式语言，我们还有什么呢？

其实最简单、最直接的方式，就是按照我们对逻辑的经验，提炼演绎的规则，并按照这些规则进行推演。这种逻辑演绎的方式，就是自然逻辑。

在自然逻辑中，我们有很多先验的逻辑运算符以及他们的规则。比如合取（$\wedge$），我们知道如果$A$和$B$均为真，那么$A\wedge B$为真，我们也知道如果$A\wedge B$为真，那么$A$和$B$均为真。

像这样的规则是非常自然，非常符合我们的经验的。不过，如果换个角度来看，这条规则，作为一个形式规则，是不是也完全合理呢？

所以说，形式语言的表现能力是很强的，它完全可以把整个自然逻辑作为自己的子集，再加上形式系统的精确和简洁，形式系统完全是表达逻辑的不二选择。

但是，正因为形式系统的表现能力很强，它所表现出来的东西，并不一定完全是符合人们经验中的逻辑的。只有符合人们的经验逻辑的形式系统，才能称作形式逻辑。为了寻找一组能够准确表达符合人们的经验的形式规则，数学家做出了很多努力。

寻找的过程是极其复杂的。逻辑运算符有很多，哪些要作为“无需定义的定义”，哪些要从其余的运算符里定义推导；设计怎样的形式规则，使之没有矛盾、完整而无冗余……最终，在罗素、弗雷格、希尔伯特、扬·武卡谢维奇、格哈德·根岑等一众数学家的努力下，形式逻辑的两个集大成之作诞生了。

• 希尔伯特演绎系统是最简洁的形式逻辑系统。它只有两个先验的逻辑运算符（$\neg$和$\to$），和五条形式规则。
• 自然演绎系统是最容易理解的形式逻辑系统。它所有的形式规则都直接来源于自然逻辑，没有任何一条规则是“刻意”规定的。

接下来，我们分别来看一看这两个形式系统。

希尔伯特演绎系统（上）

让我们先回顾一下前面提出的希尔伯特演绎系统的规则。在命题逻辑中，当取一元逻辑运算符为$\neg$，二元逻辑运算符为$\to$时，

1. （代入规则）对于一个重言式中的某一个符号（原子命题），如果把相同符号全部替换为另一个命题，得到的仍是重言式。
2. （肯定前件）对于重言式$p$和命题$q$，如果$p\to q$是重言式，那么$q$也是重言式。
3. $p\to (q\to p)$是重言式。
4. $(p\to (q\to r))\to ((p\to q)\to (p\to r))$ 是重言式。
5. $(\neg p\to \neg q)\to (q\to p)$是重言式。
6. 有限次运用以上规则，得到的字符串是重言式。

注意一下在这几条规则之前，特别加粗的字。这句话的意思是，这两个逻辑运算符是作为“无需定义的定义”引入的。它们本身不具有任何含义，只有形式上的作用。形式规则赋予它们各种性质，并保证它们能符合我们对“否”和“蕴含”的心理预期。

下面，我们来试着用这些规则，做一点简单的证明。

---

求证：$A\to A$是重言式。

证明：首先使用规则 4，用$A$代入$p$，$B\to A$代入$q$，$A$代入$r$，得重言式(1)

$$(A\to ((B\to A)\to A))\to ((A\to (B\to A))\to (A\to A))$$

然后使用规则 3，用$A$代入$p$，$B\to A$代入$q$，得重言式(2)

$$A\to ((B\to A)\to A)$$

发现(2)式和(1)式的蓝色部分相同，于是根据肯定前件，得重言式(3)

$$(A\to (B\to A))\to (A\to A)$$

使用规则 3，用$A$代入$p$，$B$代入$q$，得重言式(4)

$$A\to (B\to A)$$

同样，由(3)式、(4)式和肯定前件，得重言式

$$A\to A$$

证毕。

---

求证：（三段论）对于命题$a,b,c$，如果$a\to b$和$b\to c$均为重言式，那么$a\to c$也为重言式。

证明：由规则 3，得重言式

$$(b\to c)\to (a\to (b\to c))$$

又$b\to c$为重言式，故$a\to (b\to c)$为重言式。

由规则 4，得重言式

$$(a\to (b\to c))\to ((a\to b)\to (a\to c))$$

又$a\to (b\to c)$为重言式，故$(a\to b)\to (a\to c)$，而$a\to b$也为重言式，因此得重言式$b\to c$，证毕。

---

求证：（双重否定消去）$\neg \neg A\to A$是重言式。

证明：由规则 3，得重言式

$$\neg A\to (\neg B\to \neg A)$$

由规则 5，得重言式

$$(\neg B\to \neg A)\to (A\to B)$$

由三段论，得重言式

$$\neg A\to (A\to B)$$

用$\neg A$代入$A$，$\neg B$代入$B$，得重言式

$$\neg \neg A\to (\neg A\to \neg B)$$

同上，由规则 5 及三段论，得重言式

$$\neg \neg A\to (B\to A)$$

用$B\to \neg \neg A$代入$B$，得重言式

$$\neg \neg A\to ((B\to \neg \neg A)\to A)$$

由规则 3 及规则 4，分别有重言式

$$\neg \neg A\to (B\to \neg \neg A)$$ $$(\neg \neg A\to ((B\to \neg \neg A)\to A))\to ((\neg \neg A\to (B\to \neg \neg A))\to (\neg \neg A\to A))$$

反复运用肯定前件，即得$\neg \neg A\to A$为重言式，证毕。

---

求证：（双重否定）$A\to \neg \neg A$是重言式。

证明：在$\neg \neg A\to A$中，用$\neg A$代入$A$，得重言式

$$\neg \neg \neg A\to \neg A$$

由规则 5，得重言式

$$(\neg \neg \neg A\to \neg A)\to (A\to \neg \neg A)$$

由肯定前件，得$A\to \neg \neg A$是重言式，证毕。

---

求证：（替换规则）对于命题$p$和命题$q$，如果有$p\to q$和$q\to p$都是重言式（简记为$p\iff q$，这里的$\iff$不是逻辑运算符，而是一个表判断的记号，$p\iff q$是形式规则），那么有：

1. 对于命题$a$，$(a\to p)\iff (a\to q)$。
2. 对于命题$b$，$(p\to b)\iff (q\to b)$。
3. $\neg p\iff \neg q$。

递归地应用替换规则，我们可以把一个重言式中的所有子串$p$都替换为$q$，得到的仍是重言式，这是替换规则名称的来源。

证明概要：结论 1：由规则 3 知$(p\to q)\to (a\to (p\to q))$是重言式，又由规则 4 得$(a\to (p\to q))\to ((a\to p)\to (a\to q))$，结合$p\to q$是重言式即得$(a\to p)\to (a\to q)$是重言式。同理可得$(a\to q)\to (a\to p)$是重言式。

结论 2：

结论 3：根据结论 1、2，以及$p\iff \neg \neg p$，由$q\to p$可得重言式$\neg \neg q\to \neg \neg p$，再由规则 5 即证。

希尔伯特演绎系统（下）

有了替换规则之后，我们就有能力引入其他的逻辑运算符了。因为一般来说，我们对一个符号的定义，指的是形式上的可替代性，而在希尔伯特演绎系统中，是需要替换规则来保证的。接下来，我们定义：

1. （析取）$p\vee q\iff \neg p\to q$
2. （合取）$p\wedge q\iff \neg (p\to \neg q)$
3. （等价）$p\leftrightarrow q\iff (p\to q)\wedge (q\to p)$

注意区分$\leftrightarrow$和$\iff$，前者是逻辑运算符，其连接成的$p\leftrightarrow q$是一个命题，后者是一个表判断的记号，$p\iff q$是形式规则。

同样，我们可以用$p\Rightarrow q$表示“$p\to q$是重言式”。

---

求证：（交换律）

1. $p\vee q\iff q\vee p$
2. $p\wedge q\iff q\wedge p$

证明概要：由$(\neg q\to \neg \neg p)\Rightarrow (p\to \neg q)$及$\neg \neg p\iff p$可知$\neg q\to p\iff p\to \neg q$，之后自然得出交换律。

---

求证：（析取介入）如果$p$是重言式，那么$p\vee q$是重言式。

证明概要：由$p\Rightarrow (\neg q\to p)$可知$q\vee p$是重言式，根据交换律，$p\vee q$也是重言式。

---

求证：（合取介入）如果$p$和$q$都是重言式，那么$p\wedge q$是重言式。

证明：……

---

求证：（析取消除）如果$p\vee q$是重言式，$p$是矛盾式，那么$q$是重言式。

证明概要：$p\vee q$是重言式即为$\neg p\Rightarrow q$，以下显然。

---

求证：（合取消除）如果$p\wedge q$是重言式，那么$p$和$q$都是重言式。

证明：……

---

求证：（结合律）

1. $p\vee (q\vee r)\iff (p\vee q)\vee r$
2. $p\wedge (q\wedge r)\iff (p\wedge q)\wedge r$

证明：……

---

求证：（分配律）

1. $p\vee (q\wedge r)\iff (p\vee q)\wedge (p\vee r)$
2. $p\wedge (q\vee r)\iff (p\wedge q)\vee (p\wedge r)$

证明：……

---

求证：（等价式）

1. 如果$p\leftrightarrow q$是重言式，那么$p\iff q$。
2. 如果$p\iff q$，那么$p\leftrightarrow q$是重言式。

证明概要：这是合取介入和合取消除的直接推论。

自然演绎系统

（待续）