劉新文

(中國(guó)社會(huì)科學(xué)院 哲學(xué)研究所， 北京 100732)

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

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

一、無量詞“純邏輯演算”的主要內(nèi)容

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

沈有鼎建立的這個(gè)演算以外延為出發(fā)點(diǎn)，把函項(xiàng)與謂項(xiàng)看成是具有同等邏輯地位的對(duì)象，5個(gè)基本概念分別為：T、F、三元聯(lián)結(jié)詞“條件析取(conditioned disjunction)”〔A，B，C〕、等詞x=y以及“雜函項(xiàng)”〈x，A，y〉。這里的小寫字母用作個(gè)體變?cè)薚、F意指真值“真”和“假”之外，大寫字母都表示真值變?cè)?。自由變?cè)▊€(gè)體變?cè)⒄嬷底冊(cè)椭^項(xiàng)變?cè)?，而約束變?cè)辉俪霈F(xiàn)，也就是說，這里定義的語言是帶等詞的一階邏輯的一個(gè)不含量詞的片段。

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

對(duì)于添加“雜函項(xiàng)”的原因，我們稍作疏解。個(gè)體與真值的函項(xiàng)演算包含6種情形，它們分別是：(1)從真值到真值的函項(xiàng)(稱之為“連項(xiàng)”)；(2)從個(gè)體到真值的函項(xiàng)(稱之為“謂項(xiàng)”)；(3)從個(gè)體和真值到真值的函項(xiàng)(稱之為“雜謂項(xiàng)”)；(4)從真值到個(gè)體的函項(xiàng)(稱之為“序項(xiàng)”)；(5)從個(gè)體到個(gè)體的函項(xiàng)(稱之為“狹義函項(xiàng)”，簡(jiǎn)稱“函項(xiàng)”)；(6)從個(gè)體和真值到個(gè)體的函項(xiàng)(稱之為“雜函項(xiàng)”)?！盀榱耸冀K如一地保持我們的外延觀點(diǎn)，我們將把連項(xiàng)、雜謂項(xiàng)、序項(xiàng)和雜函項(xiàng)都看成具有跟謂項(xiàng)和函項(xiàng)同等的邏輯地位的對(duì)象”[8]97，而“雜函項(xiàng)”作為基本概念在引入之后，根據(jù)其語義解釋，它與其他4個(gè)基本概念就形成了表達(dá)完備的基本概念集合；因此，在這個(gè)演算中，函項(xiàng)完備性定理是成立的[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))

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

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

二、思想來源及影響

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

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

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

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

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

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

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

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

公理1(Id公理)：

p,Γ?Δ,p

公理2(f公理)：

f,Γ?Δ

公理3(t公理)：

Γ?Δ,t

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

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

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

四、結(jié)語

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

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