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，你就要否定那假設，從而證明了原命題。這個證明不再訴諸視覺等經驗因素，因此是抽象的。

④　命題這種抽象對象到底存在與否，是哲學家們仍然在爭論的問題。較典型的反對意見認為，我們沒有適當的標準決定兩個“命題”是否同一，因此，命題在本體論上沒有存在的資格。我們在這里談論命題，當然假設命題是存在的。但是，這并不表明邏輯學的建立，必須依賴某種特定的哲學立場。不管有沒有命題，我們都可以采取某些邏輯學家喜歡的做法，只講句子，不說命題（這樣處理起來麻煩一些）。后面要談到的概念、性質、關系等，也有類似的問題。

⑤　這也說明了我們為什么要排除矛盾。如果一個理論中出現了矛盾的命題，則這個理論就要接受所有的命題，因此它不成其為適當的理論——它主張了一切，相當于什么也沒主張。

⑥　在日常語言里，說“有些……是……”往往同時肯定了一種言外之意，即“有些……不是……”。但這里的“有些……是……”，沒有這種言外之意，它只意味著“至少有一個……是……”。

⑦　函數既然是特殊的關系，就也可以處理成集合，具體介紹見下章。這里說的函數即指特別的集合。

⑧　這里我們暫不區分開公式和閉公式，這個區分見后面諸章。本章以下所謂公式，實際上都是閉公式，或語句。

⑨　元語言與對象語言的劃分不只在眼下的情形中出現。比如，你用漢語述說英語語法，這時的漢語是元語言，英語是對象語言。元語言和對象語言不必是兩種不同的語言：你也可以用漢語述說漢語的語法。顯然，元語言和對象語言的劃分是相對的，一種語言在某種情形下是元語言，在另一種情形下可成為對象語言。但是，一旦在某種情形下這個劃分固定了，則這兩個層次的語言就有必要區分清楚，否則會造成一些不愉快的結果。（著名的說謊者悖論，根據某種解釋，就是混同了這兩個層次的結果。）