5　推演系统

5.1　公式模式与推理规则

所有一阶命题，都可以表达为某个一阶语言中的公式，所有用一阶命题进行的推理，也因此可以表达为某个一阶语言中的推理。比如，自然语言中的推理

在L₁中就“翻译”成如下推理：

既然一阶公式表达了一阶命题的真假，推理的合规则性，现在就可以放在一阶语言里考察。如何考察呢？头一个问题是，既然决定一个推理是否合规则的是命题和推理的形式，那么，一阶公式是否表达了一阶命题的形式？7′）中的三个公式，是否分别表达了7）中的三个命题的形式，因而使得7′）成为7）的推理形式？

还不是。跟7）的情形类似，7′）的合规则性或有效性，与a，b，F，G等非逻辑符号如何解释无关。如果这些非逻辑符号在L₁中有具体解释的话，则7′）中的公式就仍然有某种“内容”，而这些内容对这个推理是否正确没有影响。因此，从一阶命题到一阶公式的翻译，并不是恰好得到了那个命题的形式。

实际上，决定一阶命题的形式的，是一阶公式中的逻辑符号。仅从命题形式的角度来看，非逻辑符号无所贡献，可以看成空位，或者用合适的变项替换掉。比如，我们用变项α、β等代表L₁中的那些个体常项，用变项π、γ等代表其中的谓词，则7）中的三个命题的形式以及它们组成的推理形式就可以表达成：

注意，α、β、π、γ（包括前面使用的代表一阶公式的变项φ、ψ）等不是一阶语言中的符号，而是我们为了讨论一阶语言的公式形式而使用的变项。因此，7″）中的那些符号序列不是一阶公式。这里出现了两个层次的语言，一是一阶语言（在这里具体是L₁），它是我们眼下讨论和研究的对象，称为对象语言；另一个是我们讨论对象语言时使用的语言，就目前情形而言，它是汉语加上一些特别的符号（包括L₁中的逻辑符号），这称为元语言。^⑨

7″）中的三个元语言公式，我们称为7′）中相应的L₁-公式的模式。这跟前面介绍的模式概念是统一的。一般而言，一个公式模式是用元语言变项替换一个公式中的非逻辑符号而得到的，这个公式是这个模式的一个实例，其他同形的公式也是这个模式的实例。比如，公式模式

∀x（π（x，β）→γ（x））

在L₁中的实例有：

∀x（G（x，b）→F（x）），

∀x（H（x，a）→F（x）），

∀x（H（x，f（a，b））→I（x）），

等等。在其他一阶语言中也有类似的实例。而公式模式

φ→ψ

的实例是所有一阶蕴涵公式。

总之，给定一阶命题A，我们可以把它表达成一阶公式A′，再借助元语言变项得到A′的模式A″，A″即可以看成A的命题形式（同时是A′的形式）。命题形式一旦明了，推理形式也就得到澄清。由于一个推理规则表达为一个基本的推理形式，所以，我们的推理规则，就用一阶公式的模式来表达。比如，可以这样表达某种“全称量词消去”规则：

撇开技术性术语，公式φ（x）相当于一个（复杂的）谓词，表示个体的一个（复杂）性质，而φ（α）是说个体常项α所代表的个体具有性质φ（x）。因此，这个规则直观上说的是，如果所有个体都有某性质，则特别地个体α也有此性质。它符合我们的“从一般推出个别”的直观原则。前面提到的命题逻辑的肯定前件式和否定后件式规则，可以分别表达为：

和

不过在这里我们统一从语形上考虑，把它们称作蕴涵消去规则（前提中的那个蕴涵号在结论中不复存在）。

5.2　形式推演系统

一组选定的推理规则形成一个推演系统。这些规则既然表达了所有一阶语言的基本推理模式，就可以应用于任何一个一阶语言里。假定我们选定了一个推演系统。在任意一个一阶语言里，从一组给定的前提Φ出发，经过一系列（有穷的）推理步骤，若每一步都合乎的一个规则，而最后得到公式φ，我们就称这个过程是前提Φ在中对结论φ的一个推演。推演是对推理的合规则性的精确的表达。我们看一个例子。假设包含全称量词消去和蕴涵消去规则，当应用于L₁，推理7′）及其每一个中间步骤就可以用一个树形图来表示：

这便是中的一个推演。其中每一个横线都表示一个推理步骤，横线右边标出这个步骤所根据的推理规则，横线上下的公式组成这个规则的一个实例。其上无横线的公式（叶）是证明的前提，其下无横线的公式（根）是总结论，上下都有横线的公式同时是上个步骤的结论和下个步骤的前提。这种推演称自然推演，主要是甘岑（Gentzen, 1934）的发明。

如果在中存在从Φ到φ的一个推演，则称Φ在中可推演φ，记为Φφ。此时我们也称φ是Φ的语形后承。上例8）显示：

｛∀x（G（x，b）→F（x）），G（a，b）｝F（a）

日常使用的自然语言中的推理一般而言不具有确定性，就是说，我们常常无法严格地判定一个推理是不是合乎规则。这首先是因为我们没有一组明确的规则，即使在欧几里得的公理系统中，也没有明确规定哪些规则可以用，哪些不可以用，因此容易导致推理上的错误。其次，由于自然语言意义模糊，且形式不严格，所以一个推理步骤是否合乎某个规则，我们经常确定不下来。

一阶语言中的推演必须避免这些缺点。显然，一切推演都是在给定的系统中做出的，所以，事先给定一组明确的规则这一条已经得到满足；然后，为了使推演具有最终的确定性，我们要求每一个推演都满足下面的条件：

第一，必须在有穷步内完成（否则你无法按部就班地推出结论）。

第二，我们可以能行地检验推演中每一个推理步骤是否合乎系统的某个规则（否则你就没有判定推演是否合法的严格标准）。“能行”的意思是，有一套指令或程序，使得一台机器或者一个被动地（“不用脑子地”）服从指令的人，可以在有穷时间内完成这套程序，从而判定（即给出是或否的回答）某个问题（这里的问题是：一个推理步骤是否合乎系统的某个规则）。

第三，推演的前提与结论可以能行地找出来。

满足这些条件的证明系统称为形式推演系统。第一个条件包含在推演的定义里面；第三个条件可以通过对推演的树形图做例8）中那样的约定得到满足。第二个条件就复杂一些，它要求我们能够机械地检验一个语言L中的公式是不是某个模式的实例，这进一步要求如下的问题是能行可判定的：

i．任意一个符号是不是L的符号；

ii．L中任意符号是一个逻辑符号还是非逻辑符号；

iii．L中任意符号是哪一类逻辑符号或非逻辑符号；

iv．任意符号序列是不是一个L-公式或其组成部分。

如果在L中i—iv都是能行可判定的，则称L是一个形式语言。在形式语言中，我们需要对公式、词项等对象进行严格的归纳定义，也就是用一种能行的方法把它们从符号表中构造出来，以使它们满足可判定的要求。

建立在形式语言之上的形式推演系统使推理成为计算，成为机械的过程。给定一套公式的变形过程，它是否构成一个推演，在形式系统里是可以能行地判定的。这部分满足了莱布尼茨的要求。他设想“通用文字”要有这样的功能：当两个使用者对于一个推理的正确性产生争执的时候，只须坐下来，“让我们算一下吧”。

现在可以比较准确地概括本书的主题了。我们要建立这样一个形式推演系统：对任意给定一个一阶形式语言L，第一，它的规则在L中产生且仅产生有效推理的实例，这就是说，对任何L-公式集Φ和公式φ，如果Φ⊢φ，则Φ⊧φ；第二，L中所有有效推理的实例，都可以用系统的规则产生，换言之，如果Φ⊧φ，则Φ⊦φ。第一点称为系统的可靠性（或健全性），第二点称为完全性。二者合起来就是这样一个要求：Φ⊦φ，当且仅当Φ⊧φ。这表明了语形后承和语义后承这两个概念（在外延上）的重合，精确解释了推理的合规则性与有效性相互吻合的直观思想。一阶逻辑的这个结果，由哥德尔（Gödel, 1930）证明。

这里说的完全性是经典逻辑的完全性，直觉主义逻辑只接受一部分经典意义下有效的推理。实际上，从某一组完全的经典逻辑规则中，除掉排中律或与之等价的某个规则，就得到直觉主义逻辑的全部规则。这组规则在某种意义下也是完全的，但这个完全性不是针对有效性而言的。逻辑学家们对直觉主义逻辑设计了另外几种语义学，使得这组直觉主义规则恰好产生这样一种语义下全部正确的推理。

莱布尼茨将推理变成计算的思想，大概还蕴涵着这样一个要求：有一个机械过程，对任意的Φ和φ，都可以能行地判定Φ⊦φ是否成立。这个要求称为系统的可判定性。但丘奇（A. Church, 1936）证明，一般而言，形式推演系统不具有可判定性。与此相关的还有著名的哥德尔不完全性定理，它表明形式化的算术理论不能穷尽真算术命题。这些是形式化的代价，其中的哲学意义也许可以这样表述：当我们从直观一步步走向形式，确定性和清晰性都逐步加强，但直观方面的一些内容却不可避免地损失掉了。

注释

①　先秦的名家、辩者与后期墨家等的确深入思考过这类问题，但他们的作品传世既少，在后来的两千年里又未受到重视，虽然百余年来开始得到研究，但如今仍然是聚讼纷纭的疑案。

②　参考Arpad Szabo（1964）。

③　想象一下，你当然不能用摆石子来直接证明“任何多个（而不只是某几个具体的）偶数的和是偶数”这个全称命题，因为你没有无穷多石子；即使有，你也摆不完。但是，RAA可以帮助你间接地证明这个定理：假设这命题为假，然后你推出矛盾，根据RAA，你就要否定那假设，从而证明了原命题。这个证明不再诉诸视觉等经验因素，因此是抽象的。

④　命题这种抽象对象到底存在与否，是哲学家们仍然在争论的问题。较典型的反对意见认为，我们没有适当的标准决定两个“命题”是否同一，因此，命题在本体论上没有存在的资格。我们在这里谈论命题，当然假设命题是存在的。但是，这并不表明逻辑学的建立，必须依赖某种特定的哲学立场。不管有没有命题，我们都可以采取某些逻辑学家喜欢的做法，只讲句子，不说命题（这样处理起来麻烦一些）。后面要谈到的概念、性质、关系等，也有类似的问题。

⑤　这也说明了我们为什么要排除矛盾。如果一个理论中出现了矛盾的命题，则这个理论就要接受所有的命题，因此它不成其为适当的理论——它主张了一切，相当于什么也没主张。

⑥　在日常语言里，说“有些……是……”往往同时肯定了一种言外之意，即“有些……不是……”。但这里的“有些……是……”，没有这种言外之意，它只意味着“至少有一个……是……”。

⑦　函数既然是特殊的关系，就也可以处理成集合，具体介绍见下章。这里说的函数即指特别的集合。

⑧　这里我们暂不区分开公式和闭公式，这个区分见后面诸章。本章以下所谓公式，实际上都是闭公式，或语句。

⑨　元语言与对象语言的划分不只在眼下的情形中出现。比如，你用汉语述说英语语法，这时的汉语是元语言，英语是对象语言。元语言和对象语言不必是两种不同的语言：你也可以用汉语述说汉语的语法。显然，元语言和对象语言的划分是相对的，一种语言在某种情形下是元语言，在另一种情形下可成为对象语言。但是，一旦在某种情形下这个划分固定了，则这两个层次的语言就有必要区分清楚，否则会造成一些不愉快的结果。（著名的说谎者悖论，根据某种解释，就是混同了这两个层次的结果。）