沈有鼎的“純邏輯演算”思想源流
——紀念沈有鼎先生逝世30周年

劉新文

(中國社會科學院 哲學研究所， 北京 100732)

作為我國較早從事數(shù)理邏輯研究的邏輯學家，沈有鼎先生(1908—1989)在數(shù)理邏輯方面所做的工作主要是邏輯演算，其成果體現(xiàn)在《初基演算》[1](1957年)和《“純邏輯演算”中不依賴量詞的部分》[2](1981年)兩篇論文之中。前者發(fā)表之后，莫紹揆先生(1917—2011)、劉壯虎先生等著名邏輯學家對其進行了后續(xù)研究(1)莫紹揆先生認為“沈有鼎先生的初基演算，可以說是用直覺主義的眼光來討論模態(tài)系統(tǒng)，也可以說是用模態(tài)的觀點來推廣直覺主義系統(tǒng)。這是一個新嘗試，是一條很可繼續(xù)研究的道路”。莫先生在公理的選擇上對初基演算加以改進，提出了3個改進的初基演算系統(tǒng)，參見文獻[3]第134-136頁。2000年，劉壯虎先生建立了初基演算的鄰域語義學并證明了對于這一語義的完全性定理，參見文獻[4]第258-267頁。；后者是《個體與真值的演算》(英文未刊稿)的主要內容，至今研究者甚少。1995年，先師張清宇先生(1944—2011)將《個體與真值的演算》譯為中文發(fā)表在文集《理由固然》中[5]，而作為原文的英文版則發(fā)表于2000年的文集《摹物求比》中[6]；張尚水先生在1998年的綜述性論文中記錄了該文的大致寫成時間(2)1998年，張尚水先生提到：“《‘純邏輯演算’中不依賴量詞的部分》是沈先生在60年代初期用英文寫成的長篇論文《個體與真值的演算》的主要部分。在《個體與真值的演算》中還有更多的內容和結果?！眳⒁娢墨I[7]。。

沈有鼎關于不帶量詞的“純邏輯演算”具有很多漂亮的性質，是從帶等詞的一階邏輯中分離出來的一個完全的、可判定的子系統(tǒng)。本文擬探討它的時代背景、它所研究的問題和思想在20世紀四五十年代丘齊(A.Church，1903—1995)工作中的直接來源及其對后來研究者的影響，并沿著其中的一個方向做進一步推進。

一、無量詞“純邏輯演算”的主要內容

根據(jù)張尚水的記錄，《個體與真值的演算》完成于20世紀60年代初期，《“純邏輯演算”中不依賴量詞的部分》是其主要部分。我們以正式發(fā)表的后者為主，結合兩篇論文來概述其主要內容和思想。

沈有鼎建立的這個演算以外延為出發(fā)點，把函項與謂項看成是具有同等邏輯地位的對象，5個基本概念分別為：T、F、三元聯(lián)結詞“條件析取(conditioned disjunction)”〔A，B，C〕、等詞x=y以及“雜函項”〈x，A，y〉。這里的小寫字母用作個體變元，而除了T、F意指真值“真”和“假”之外，大寫字母都表示真值變元。自由變元包括個體變元、真值變元和謂項變元，而約束變元不再出現(xiàn)，也就是說，這里定義的語言是帶等詞的一階邏輯的一個不含量詞的片段。

在這些基本概念之中，作為三元聯(lián)結詞的“條件析取”〔A，B，C〕在自然語言中表述為“如果B，那么A；否則C”(相當于英語中的表達式“A，if B，otherwise C”)，或者用經典命題邏輯的4個基本聯(lián)結詞定義為：(B→A)∧(﹁ B→C)或(B∧A)∨(﹁ B∧C)；“條件析取”是一種稱之為“連項”的真值函項，即從真值到真值的函項。等詞x=y是一個二元謂項，表示的是“個體x就是個體y”；謂項是從個體到真值的函項?！半s函項”是從個體和真值到個體的函項，在〈x，A，y〉中，當A取T為真值的時候，它的值同于x，當A取F為真值的時候，它的值同于y；“雜函項”是沈有鼎新引入的基本概念，所以他說“本系統(tǒng)的邏輯常項中，除了真值函項以外，基本概念不止‘同一’概念(=)，還加了一個”[2]，這里所說的“加了一個”指的就是“雜函項”。

對于添加“雜函項”的原因，我們稍作疏解。個體與真值的函項演算包含6種情形，它們分別是：(1)從真值到真值的函項(稱之為“連項”)；(2)從個體到真值的函項(稱之為“謂項”)；(3)從個體和真值到真值的函項(稱之為“雜謂項”)；(4)從真值到個體的函項(稱之為“序項”)；(5)從個體到個體的函項(稱之為“狹義函項”，簡稱“函項”)；(6)從個體和真值到個體的函項(稱之為“雜函項”)。“為了始終如一地保持我們的外延觀點，我們將把連項、雜謂項、序項和雜函項都看成具有跟謂項和函項同等的邏輯地位的對象”[8]97，而“雜函項”作為基本概念在引入之后，根據(jù)其語義解釋，它與其他4個基本概念就形成了表達完備的基本概念集合；因此，在這個演算中，函項完備性定理是成立的[2]，[8]97-100，證明如下：

﹁A〔F,A,T〕A→B〔B,A,T〕A∧B〔A,B,F〕A∨B〔T,A,B〕A?B〔A,B,﹁A〕x≠y〔F,x=y,T〕[x,y,z,v]〈x,y=z,v〉α(x,y,z)[x,x,y,z]β(x,y,z)[x,y,z,z]γ(x,y,z)α(x,y,β(x,y,z))ε(x,y,z)[x,y,z,β(y,x,z)]δ(x,y,z)α(x,y,ε(x,y,z))

這些關于一元聯(lián)結詞和二元聯(lián)結詞的定義都是如下意義上最簡單可能的定義[9]134：互相對偶的聯(lián)結詞的定義也相互對偶，而否定的定義是自我對偶的。

在上述句法和語義的基礎上，沈有鼎不帶量詞的“純邏輯演算”以“值表”的方式給出，而不是像通常那樣列出公理和推演規(guī)則來建立推理系統(tǒng)。他指出，該系統(tǒng)采用的判定方法類似于命題演算中運用真值表判定一個公式是否為定理的方式，在這個系統(tǒng)中，連項的值表就是通常的命題聯(lián)結詞的真值表，而每一個在系統(tǒng)中可以定義的謂項、雜謂項、函項、雜函項都有自己相應的值表。根據(jù)其中給出的邏輯解釋，“‘純邏輯演算’中不依賴量詞的部分”中的這個系統(tǒng)是完全的，雖然它是帶等詞的一階邏輯演算中極其微小的部分。

二、思想來源及影響

沈有鼎的《個體與真值的演算》和《“純邏輯演算”中不依賴量詞的部分》的主要內容，在于給出“帶等詞的一階邏輯”的一個片段(或稱“部分演算”)，這個片段是可判定的，而且給出了判定過程。這些工作在那兩篇論文中都沒有說明任何時代背景和問題來源，我們現(xiàn)在把其中使用的三元聯(lián)結詞“條件析取”以及所述問題的來源稍加追溯。

1948年，丘齊給出了一個三元聯(lián)結詞的真值表并使用“[p，q，r]”來表示這個聯(lián)結詞，把它讀作“p或r，取決于q或非q”，這就是“條件析取”名稱的來源[10]87。這個括號記法源自鮑施(A.F.Bausch)的建議[10]89，給與對偶化相關的工作中帶來了便利。然后，丘齊證明了以下函項完備性定理：“條件析取、t和f是命題演算獨立初始聯(lián)結詞的完備集合”[9]131，[10]88，其中的t和f是命題常項，或稱零元聯(lián)結詞，而且這個集合還具有自我對偶性[9]133，[10]89。在此之前，波斯特(E.Post,1897—1954)對命題演算獨立初始聯(lián)結詞的完備系統(tǒng)做過系統(tǒng)的處理。初版于1944年、修訂版于1956年出版的《數(shù)理邏輯導論(第一部)》在第24節(jié)“命題演算的初始聯(lián)結詞”中考察的唯一一個三元聯(lián)結詞就是這個“條件析取”[9]161。丘齊的這部教材是數(shù)理邏輯史上的名著，產生過廣泛而深遠的影響，半個多世紀以來一直在修訂印行，我國的很多數(shù)理邏輯學家則直接受教于它。胡世華在20世紀60年代寫成、后由陸鐘萬整理出版的《數(shù)理邏輯基礎》介紹了這個“條件析取”函項[11]；1963年，沈有鼎指導周禮全、張尚水、諸葛殷同、宋文淦等人學習這本書[8]380，而《“純邏輯演算”中不依賴量詞的部分》的完整版本《個體與真值的演算》正是在這一時期完成的。沈有鼎的這(兩)篇論文提到，“已經知道，所有的連項都可用T、F、〔A，B，C〕來表示”[8]106，這個結果直接來自于丘齊的《數(shù)理邏輯導論(第一部)》；然后，沈有鼎做了進一步推廣，以大量的篇幅證明了“不僅所有的連項可用T、F、〔A，B，C〕、x=y和〈x，A，y〉來表示，而且所有可由真值表表示的謂項、雜謂項、函項和雜函項也都可用它們來表示”[8]116。

丘齊在《數(shù)理邏輯導論(第一部)》中并沒有為T、F和〔A，B，C〕建立起公理系統(tǒng)，而是提出了以下這個問題作為習題(25.16)：“令初始聯(lián)結詞為條件析取、t和f。令推演規(guī)則為替換規(guī)則和以下規(guī)則：從[A，B，C]和B推出A。建立一些公理，使得所得系統(tǒng)對于命題演算來說是足夠的。盡可能簡化每一條公理，然后減少它們的數(shù)量(不計對偶)”[9]139，并且在腳注中說明“這個習題不能當做通常意義上的習題，而是作為一個尚未解決的問題留作研究之用。作者還沒有試圖找到解決辦法”[9]139。沈有鼎建立了自己的系統(tǒng)，并且認為這個“系統(tǒng)采用一種和命題演算中運用真值表判定一公式是否定理的方法相類似的判定方法，而這個方法本身就可以理解為一種公理系統(tǒng)”[2]。判定問題是數(shù)理邏輯的核心問題之一；20世紀初，希爾伯特在數(shù)學基礎研究中提出形式主義綱領，致力于通過有窮多一階公理來對各種數(shù)學分支進行公理化。原則上，這樣的公理化把數(shù)學命題的證明歸約為在一個指定的形式邏輯系統(tǒng)中執(zhí)行一種機械的推導，在這樣的情況下，判定問題尤其重要。另一方面，沈有鼎并沒有停留在丘齊的這個問題上，他的系統(tǒng)在命題演算的基礎上做了擴充，以包含等詞、謂項、雜謂項、函項和雜函項。此外，“既然本系統(tǒng)是可判定的，那么在原則上可以把所有定理都規(guī)定為公理，同時不要任何推理規(guī)則”[2]。不過，他也提到，在這個演算中引進全稱算子而把它擴張成帶等詞一階謂詞演算的一個相替代的演算時，考慮到丘齊的著名結論，即一階邏輯不是可判定的，“當然就不可期望仍有一個能行的判定過程，因此在這情形下有一個公理系統(tǒng)就相當必要”[8]132，只是這個想法沒有繼續(xù)討論。

至此我們已經看到，在沈有鼎建立的“純邏輯演算”中，條件析取“〔A，B，C〕”和雜函子“〈x，A，y〉”都作為初始概念出現(xiàn)，前者的括號記法承續(xù)自丘齊等人的工作，后者是沈有鼎“引進的新概念”[8]99。此外，通過定義引進的雜函項[x，y，z，v]、α、β、γ、ε和δ都采用了方括號記法。這些初始概念中的括號兼具了括號和聯(lián)結詞的作用，隨后，沈有鼎的弟子張清宇研究了這些工作，對括號記法做了進一步發(fā)揮。

三、條件析取的后承系統(tǒng)

為建立條件析取、t和f這3個經典命題邏輯聯(lián)結詞的后承演算系統(tǒng)，我們首先把丘齊所給經典命題邏輯語言中的公式整理如下：

α∷=p|f|t| [α,β,γ]

公式的語義解釋在前面已經給出。后承演算系統(tǒng)由以下5條公理和規(guī)則組成：

公理1(Id公理)：

p,Γ?Δ,p

公理2(f公理)：

f,Γ?Δ

公理3(t公理)：

Γ?Δ,t

規(guī)則1(括號引入規(guī)則1)：

規(guī)則2(括號引入規(guī)則2)：

這個系統(tǒng)的可靠性和完全性定理證明的具體細節(jié)，以及與沈有鼎不帶量詞的“純邏輯演算”系統(tǒng)相關的其他工作(如公理系統(tǒng)等)將在另文詳述，此處不贅。

四、結語

沈有鼎先生在20世紀60年代所建立的不帶量詞的“純邏輯演算”接續(xù)了丘齊、波斯特在20世紀四五十年代的工作，這些成果不僅豐富了經典的判定問題，而且豐富了函數(shù)代數(shù)領域。對于本文提到的各種未解決問題，我們將在另外的工作中做進一步研究。

致謝：馬明輝教授在本文尤其是第三節(jié)的寫作過程中提供過具體的意見，特此感謝！