2.7　谈论无穷

命题逻辑为我们日常推理时不自觉使用的很多方法（如反证法）提供了坚实的保障。但是不得不说，它还弱的很！为什么这么说呢？这是因为，仅在命题逻辑的体系内，我们根本无法谈论日常论证中两个非常重要的概念：“存在”与“任意”。不妨回看一下定义2.45，其表述中含有“对于任意一个命题”的字样。定理2.46的证明开篇也便说道“我们考察任意一个命题”。让我们试着在命题逻辑中形式化一下“任意”。一个办法是，那就把所有的命题罗列出来一个一个论证！但显然按照命题逻辑的语法，命题可是有无穷多的！前面提到过我们建模的一个最基本的要求是只能进行有限论证，任何证明都只能有有限步，所以这一条路走不通。另一条呢？我们直接讨论命题“对任意命题均成立……”的真假不就好了？但是很遗憾，前面也说过，命题逻辑压根不关心一个命题是真是假，仅关心它可真可假有两种可能性，于是“在命题逻辑中论证一个命题是真”本身就是一个毫无意义的话。总而言之，我们不得不遗憾的承认：

洞察2.49　定义2.45所述“一致性”是无法在命题逻辑语言中被形式表达的，定理2.46的证明也是无法形式化成定义2.40所述“证明”的。

为了解决这个问题以更完善地建模我们的推理直觉，我们必须把考察的粒度变得更细。让我们打开原子命题，进入其内部的结构，更加深入地审视我们的演绎推理。我们将要关注的命题，是形如“我爱你”这般的主谓（宾）结构的命题，称之为谓词。

定义2.50　我们称变量（variable）是这样一种形式符号，其在给定解释下可以被替换为不特定值，并称其所有可能的赋值为其论域（domain of discourse）。

简单地说，论域就是我们讨论话题的边界。变量可以代表边界内的任何对象。比如一个字母x，若论域是人，我们可以说它代表“张三”“李四”“王五”……

定义2.51　我们称一个n元原子谓词（atomic predicate）是一个包含n个变量x₁,x₂,…,x_n的符号，其中n⩾0，且其在这n个变量的任何赋值下均是一个命题。我们称x₁,x₂,…,x_n为自由变量（free variable）。当n=0时，原子谓词退化为原子命题。

可以看到变量是比命题粒度更细的符号，是构成命题的局部组件。我们用英文来在观察者语言中代指原子谓词⁽³⁶⁾，比如

· Sunny（x）：“x是晴天”

· Love（x₁,x₂）：“x₁爱x₂”

· Run（t）：“t会跑”

接下来是关键：在任何变量赋值下这些符号会变成一个命题！命题是什么？是一个能且只能为真或假的符号。比如一个可能的赋值与解释是：

· x赋值为“星期二”，Sunny（x）即为“星期二是晴天”，且为真；

· x₁与x₂赋值为“张三”和“李四”，Love（x₁,x₂）即为“张三爱李四”，且为假；

· t赋值为“猪”，Run（t）即为“猪会跑”，且为真。

基于原子谓词，我们终于可以形式地谈论“存在”与“任意”了。

定义2.52　我们称谓词（predicate）是如下递归定义的形式符号：

· 原子谓词是谓词；

· 若P是谓词，那么¬P也是谓词；

· 若P和Q是谓词，那么下述符号也都是谓词：（P∧Q）、（P∨Q）、（P→Q）、（P↔Q）；

· 若P是一个包含若干自由变量的谓词，那么下述符号也都是谓词：（∀x:P）、（∃x:P），其中x是P的某个自由变量。

我们称符号∀为全称量词（universal quantifier），符号∃为存在量词（existential quantifier），称被绑定（bind）量词的符号x为约束变量（bound variable）。特别的，若P只有一个自由变量，其在绑定量词后变为一个命题。

逻辑连词¬、∧、∨、→、↔的定义与命题逻辑的定义2.32相同。对只有一个自由变量的谓词P（x），在给定解释下，若对x论域中的任何值a命题P（a）都为真，那么命题∀x:P（x）为真，否则为假。命题∃x:P（x）的真值被定义为¬（∀x:¬P（x））。

直观说来，“∀x:P（x）”就是在说“对任意x成立P（x）”，“∃x:P（x）”就是在说“存在x成立P（x）”，其被定义为“并非对任意x均不成立P（x）”。

我们之前说过，有限论证的要求使得命题逻辑无法处理无穷，存在与全称量词正是来弥补这个不足的。单独看上去，P（x）只是一个谓词，不同x的赋值会得到不同的命题。但只要把全称或存在量词一加，我们便一揽子谈论了所有可能性，给出了一个或真或假的命题！

举个具体的例子，考虑谓词Sunny（x）：“x是晴天”，x的论域是日期。于是Sunny（星期一）、Sunny（2020年1月1日）都是命题，可真可假。Sunny（x）自己并不是命题，无所谓真假。但∀x:Sunny（x），即“∀x:x是晴天”就是一个命题了⁽³⁷⁾，在我们的世界里其被解释为“对于任意x成立x是晴天”，显然是假的，但在其他世界中可能就是真的（比如没有大气和水的月球上？），总之可真可假，是一个命题。

再来看一个复杂一些的，考虑谓词“x爱y”。那么

∃y:x爱y

是命题吗？不是，因为它还剩一个自由变量x，所以依旧是一个一元谓词。再来一下呢？

是命题吗？这回就是了！因为它已经没有自由变量了，所以是一个可真可假的命题。如果你忍不住要问那它到底是真是假呢？一定要忍住，因为我们不关心这个，也不能问。

当然，在我们所处的世界中，命题（2.6）还是能被说出个真假的。这句话翻译过来就是“对于任意x，存在y，使得x爱y。”如果把论域限定为“人”，那便是“对于任何人，都存在一个人爱他”，看起来是真的呀——任何人都有父母嘛。那现在问题来了，我们把两个量词颠倒一下呢？

翻译成啥呢？“存在一个人，所有人都爱他”，这就不大可能了吧！于是，我们得到了一个重要的领悟：

洞察2.53　存在与全称量词的顺序至关重要。

至此，在命题逻辑的基础上，我们构建了一个更加强大的语言⁽³⁸⁾。

定义2.54　谓词逻辑（predicate logic）是一门形式语言，其字母表与语法定义如下：

· 字母表：在命题逻辑的基础上增加∀、∃、：三个符号，26个小写字母，以及10个数字⁽³⁹⁾；

· 语法：一个公式是合式公式当且仅当其为一个谓词（定义2.52）。

与命题逻辑一样，我们接下来可以继续深入研究谓词逻辑。比如，将其从语言升级为公理系统，然后研究证明与推理等。再比如，谓词逻辑又叫一阶逻辑（first-order logic），于是自然还有二阶、三阶等更高阶逻辑。它们的区别在于，一阶逻辑允许我们谈论“任意变量”，二阶逻辑进一步允许我们谈论“任意一元谓词”，等等。所有这些试图建模人类本能逻辑的形式系统统称为形式逻辑（formal logic）。但我们到此为止——因为够用了。

断言2.55　一个公认的事实是，谓词逻辑足以形式化足够广泛的演绎推理本能，为人类的演绎推理提供了一个坚实的纯形式的公理系统基石。