鄰域語(yǔ)義學(xué)與推演系統(tǒng)的完全性

1、鄰域語(yǔ)義學(xué)與推演系統(tǒng)的完全性    推演系統(tǒng)并不一定是邏輯系統(tǒng)，在討論一個(gè)推演系統(tǒng)是不是邏輯系統(tǒng)時(shí)，完全性是一個(gè)重要的標(biāo)準(zhǔn)。然而，完全性是相對(duì)于語(yǔ)義解釋的，如果允許任意的語(yǔ)義解釋?zhuān)瑒t完全性標(biāo)準(zhǔn)可能是無(wú)用的。設(shè)想這樣的情況，有一種語(yǔ)義解釋?zhuān)沟盟械耐蒲菹到y(tǒng)對(duì)于它都是完全的。實(shí)際上，確實(shí)有這樣的語(yǔ)義解釋。在本文中，我們構(gòu)造一種適合于一切命題邏輯的語(yǔ)義學(xué)，在這種語(yǔ)義學(xué)中討論推演系統(tǒng)的完全性。并利用這種完全性簡(jiǎn)單地討論怎樣的推演系統(tǒng)是邏輯系統(tǒng)。一、從模態(tài)邏輯談起每個(gè)關(guān)系都可以轉(zhuǎn)化為鄰域映射，但并非所有的鄰域映射都是由關(guān)系轉(zhuǎn)化而來(lái)，所以模態(tài)邏輯的鄰域語(yǔ)義學(xué)是比關(guān)

2、系語(yǔ)義學(xué)更為廣泛的一種語(yǔ)義學(xué)。鄰域語(yǔ)義學(xué)的意義在于它不僅能用于模態(tài)邏輯，而且能用于極大多數(shù)的命題邏輯。用以上類(lèi)似的方法可以將廣義模態(tài)邏輯、時(shí)態(tài)邏輯、相干邏輯、直覺(jué)主義邏輯（及其極小邏輯、初基演算等）、部分條件句邏輯（命題型的條件句邏輯）等邏輯系統(tǒng)的語(yǔ)義轉(zhuǎn)化為鄰域語(yǔ)義。二、形式語(yǔ)言我們抽象地考慮命題邏輯的形式語(yǔ)言，它適合一切命題邏輯。2.1定義形式語(yǔ)言 一個(gè)（命題）形式語(yǔ)言由初始符號(hào)和形成規(guī)則組成：初始符號(hào)（1）命題變項(xiàng)；（2）命題常項(xiàng)集C；（3）命題算子集F。命題變項(xiàng)有可數(shù)個(gè)，用p，q等表示。C的元素用a，b等表示，C可以是空集。F的元素用f，g等表示，每個(gè)fF，有元數(shù)n1，f稱(chēng)為n 元算子，

3、F中至少有元數(shù)2的算子。形成規(guī)則（1）命題變項(xiàng)和命題常項(xiàng)是公式；（2）如果f是n元命題算子，,1，,n是n個(gè)公式，則f,1,n是公式；（3）只有以上的是公式。不同的形式語(yǔ)言的區(qū)別在于命題常項(xiàng)集C和命題算子集F。所以可以將形式語(yǔ)言記為PC，F(xiàn)。P的全體公式記為Form（P）。2.2定義代入 ，,1，,n是公式，p,1，p,n是命題變項(xiàng)。（,1p,1，,np,n）（在中將i代入p,i）歸納定義如下：（2）是命題常項(xiàng)，（,1p,1，,np,n）；（3）f,1,m，（,1p,1，,np,n）f,1（,1p,1，,np,n）,m（,1p,1，,np,n）。2.3定義置換，是公式。 （在中將置換）歸納定義

4、如下：（1）不是的子公式，則；（2），則（3）f,1,n，是,i的子公式，則f,1,i,n。三、框架和模型（1）任給C，都有V（）C,；（2）任給fF，任給公式,1，,n，任給xW，都有xV（f,1,n）當(dāng)且僅當(dāng)V（,1），V（,n）N,f（x）。MK，V稱(chēng)為P的模型。記MK。3.5定理組合原理（1）如果V（,1）V'（,n），V（,n） V'（,n），則V（f,1,n）V'（f,1,n）。（2）如果V（,1）V（,1），V（,n）V（,n），則V（f,1,n）V（f,1,n）。由組合原理（1）可得：賦值V由V在命題變項(xiàng)上的值所確定。由組合原理（2）可得：如果V（）V（

5、），則任給公式， 都有V（）V（）。3.6定義滿(mǎn)足和模型有效MK，V是模型，WM。3.7定義框架有效K是框架，是框架類(lèi)。四、完全性和典范模型A稱(chēng)為公理集，A中的元素稱(chēng)為公理。R稱(chēng)為推演規(guī)則集，R中的元素稱(chēng)為推演規(guī)則。4.2定義證明D是推演系統(tǒng)。D 的一個(gè)證明是一個(gè)有限的公式序列,1，,n，其中每個(gè),i滿(mǎn)足以下條件之一：（1）,iA；（2）存在公式集A，使得A,1，,i-1且A，,iR。4.3定義內(nèi)定理D推演系統(tǒng)。如果存在D的證明,1，,n，使得,n，則稱(chēng)是D的內(nèi)定理，記為。D的全體內(nèi)定理的集合記為T(mén)（D）。4.4定義完全性D是推演系統(tǒng)。（1）如果存在模型M，使得當(dāng)且僅當(dāng)M，則稱(chēng)D是模型完全的。

6、（2）如果存在框架類(lèi)，使得當(dāng)且僅當(dāng)，則稱(chēng)D是框架完全的?？梢宰C明，如果D是框架完全的，則存在框架K，使得當(dāng)且僅當(dāng)K。證明模型完全性最主要的工具是典范模型。（4）任給aC，都有C,aa；（5）任給fF，都有,1，,nN,f（u）當(dāng)且僅當(dāng)f,1,nu；（6）任給命題變項(xiàng)p，都有V（p）p。4.6定理典范模型的性質(zhì)如果MK，V是D的典范模型，WK，則（1）任給公式，都有V（）（也就是uV（）當(dāng)且僅當(dāng)u）。（2）當(dāng)且僅當(dāng)W。4.7定理如果D有典范模型M，則D是模型完全的。MK，V是D的典范模型，則稱(chēng)K是D的典范框架。和典范模型不一樣，D的典范框架并不一定是T（D）的的框架。但如果D 有典范框架K是T（

7、D）的框架，則D是框架完全的。五、一般框架5.1定義合適P是形式語(yǔ)言，KW，C,a，N,f，是P的框架，（W）稱(chēng)為K上一個(gè)合適的子集族，如果滿(mǎn)足以下條件：（1）任給aC，都有C,a；（2）任給fF，都有如果S,1，S,n，則N,f*（S,1，S,n）。5.2定義一般框架P是形式語(yǔ)言，P 的一個(gè)一般框架是四元組GKW，C,a，N,f，其中KW，C,a，N,f是P的框架，是K上一個(gè)合適的子集族。5.3定義賦值和模型GKW，C,a，N,f，是一般框架，V是K上的賦值，如果V滿(mǎn)足：任給命題變項(xiàng)p，都有V（p），則稱(chēng)V是GK上的一個(gè)賦值。稱(chēng)MGK，V為模型。GK上的賦值也是K上的賦值，所以一般框架上的滿(mǎn)

8、足、 模型有效等概念和框架上的相應(yīng)概念一樣。一般框架有效和框架有效稍有差別。5.4定義一般框架有效GK是一般框架，是公式。如果任給GK 上賦值V，都有GK，V5.5定義一般框架完全性D是推演系統(tǒng)。如果存在一般框架GK，使得當(dāng)且僅當(dāng)GK，則稱(chēng)D是一般框架完全的。5.6定理GK是一般框架，V是GK上的賦值，則任給公式， 都有V（）。六、弱框架6.1定義弱框架P是形式語(yǔ)言，P的一個(gè)弱框架是四元組WKW，W,0，C,a，N,f，其中：KW，C,a，N,f是P的框架，W,0是W的子集。6.2定義賦值和弱模型WKW，W,0，C,a，N,f是弱框架，K上的賦值也稱(chēng)為WK上的賦值。WMWK，V稱(chēng)為弱模型。弱框

9、架上的模型在可能世界x 滿(mǎn)足的概念和框架上的相應(yīng)概念一樣，其它概念和框架上的相應(yīng)概念稍有差別。6.3定義弱模型有效WMWK，V是弱模型，是公式。如果任給xW,0，都有WM6.4定義弱框架有效WK是弱框架，W是弱框架類(lèi)，是公式。如果D是弱框架完全的，則存在弱框架WK，使得D是弱框完全的。證明模型完全性用的是典范模型，證明弱模型完全性用的是弱典范模型。6.6定義弱典范模型D是推演系統(tǒng)，WKW，W,0，C,a，N,f是弱框架，弱模型WMWK，V稱(chēng)為D的弱典范模型，如果WM滿(mǎn)足以下條件：（4）任給aC，都有C,aa；（5）任給fF，都有,1，,nN,f（u）當(dāng)且僅當(dāng)f,1,nu；（6）任給命題變項(xiàng)p，

10、都有V（p）p。弱典范模型和典范模型的差別在于條件（2）和（3），（2 ）的要求減弱了，而（3）的要求加強(qiáng)了。6.7定理弱典范模型的性質(zhì)如果MK，V是D的典范模型，WK，則（1）任給公式，都有V（）（也就是uV（）當(dāng)且僅當(dāng)u）。（2）當(dāng)且僅當(dāng)W,0V（）。6.8定理如果D有弱典范模型M，則D是弱模型完全的。6.9定義一般弱框架PC，F(xiàn)是形式語(yǔ)言，P 的一個(gè)一般弱框架是五元組GWKW，W,0，C,a，N,f，其中KW，C,a，N,f是P的框架，W,0是W的子集，是K上一個(gè)合適的子集族。6.11定義賦值和弱模型GWKW，W,0，C,a，N,f，是一般弱框架，V是WK上的賦值，如果V滿(mǎn)足：任給命題變

11、項(xiàng)p，都有V（p），則稱(chēng)V是GWK上的一個(gè)賦值。MGWK，V稱(chēng)為弱模型。GWK上的賦值也是WK上的賦值，所以一般弱框架上的滿(mǎn)足、 模型有效等概念和弱框架上的相應(yīng)概念一樣。一般弱框架有效和弱框架有效稍有差別。6.12定義一般弱框架有效GWK是一般弱框架，是公式。 如果任給GWK上賦值V，都有GWK，V，則稱(chēng)D是一般弱框架完全的。七、完全性的性質(zhì)和意義框架完全性、一般框架完全性和模型完全性依次減弱。弱完全性要比相應(yīng)的完全性弱。弱模型完全性一般弱框架完全性弱框架完全性模型完全性一般框架完全性框架完全性前四種完全性有一般的刻畫(huà)。7.1定義置換封閉性D是推演系統(tǒng)。如果D 滿(mǎn)足：任給，T（D），都有T（D

12、），則稱(chēng)D 有（內(nèi)定理）置換封閉性。7.2定義代入封閉性D是推演系統(tǒng)，如果從T（D）能得到（,1p,1，,np,n）T（D），則稱(chēng)D有代入封閉性。7.3定理任何推演系統(tǒng)D都是是弱模型完全的。7.4定理推演系統(tǒng)D是模型完全的當(dāng)且僅當(dāng)D有置換封閉性。7.5定理推演系統(tǒng)D是一般弱框架完全的當(dāng)且僅當(dāng)D有代入封閉性。7.6定理推演系統(tǒng)D是一般框架完全的當(dāng)且僅當(dāng)D 有置換封閉性和代入封閉性。下面，我們從更一般的語(yǔ)義學(xué)角度來(lái)看以上六種完全性的意義。任何一種語(yǔ)義都是由值域R（一個(gè)非空集合）、 賦值（全體公式集到值域的映射）和有效性的定義三部分組成。賦值和有效性定義中有一些基本的原則。賦值的基本原則有：（1）組

13、合原則賦值V由V在命題變項(xiàng)上的值所確定。這樣， 所有的賦值都是全體命題變項(xiàng)到值域的映射的擴(kuò)充。（2）普遍性原則命題變項(xiàng)可以取值域中的任何值。這樣， 任何一個(gè)全體命題變項(xiàng)到值域的映射都可以擴(kuò)充為一個(gè)賦值。（3）值域是非空集合的冪集。這只是一個(gè)要求而不是一個(gè)原則。有效性定義的基本原則有：（1）值確定原則（弱）有效性是由值所確定的。就是說(shuō)， 如果兩個(gè)公式在任何賦值下的值都相同，則它們的有效性是一樣的。（2）值確定原則（強(qiáng)）存在R的子集I（特指集），使得：一個(gè)公式是有效的當(dāng)且僅當(dāng)它在任何賦值下的值都在I中。（3）唯一性原則特指集I只有一個(gè)元素。組合原則和強(qiáng)的值確定原則是建立鄰域語(yǔ)義學(xué)的基礎(chǔ)，它對(duì)應(yīng)的是

14、弱模型完全性。普遍性原則區(qū)分了模型完全和一般框架完全。賦值的原則（3）區(qū)分了一般框架完全和框架完全。唯一性原則區(qū)分了強(qiáng)和弱。(2)弱模型完全性一般弱框架完全性弱框架完全性(3)模型完全性一般框架完全性框架完全性 (1)(2)(3)反之，任何滿(mǎn)足組合原則和強(qiáng)的值確定原則的語(yǔ)義學(xué)都可以轉(zhuǎn)化成鄰域語(yǔ)義學(xué)，所以鄰域語(yǔ)義學(xué)是滿(mǎn)足組合原則和強(qiáng)的值確定原則的最一般的語(yǔ)義學(xué)。八、什么是邏輯系統(tǒng)？要在鄰域語(yǔ)義學(xué)內(nèi)討論什么是邏輯系統(tǒng)，首先要解決為何邏輯系統(tǒng)必須有組合原則和強(qiáng)的值確定原則。組合原則是弗雷格創(chuàng)立現(xiàn)代邏輯的重要原則之一，也是現(xiàn)有的大多數(shù)邏輯語(yǔ)義學(xué)的基本原則。然而，現(xiàn)在也有不少被稱(chēng)為“邏輯”的推演系統(tǒng)的語(yǔ)

15、義學(xué)不滿(mǎn)足組合原則。也有學(xué)者對(duì)組合原則提出了批評(píng)，但他們的批評(píng)是對(duì)某些語(yǔ)言現(xiàn)象的某種語(yǔ)義分析來(lái)說(shuō)的，所以他們的批評(píng)至多說(shuō)明了這種特定的語(yǔ)義分析不滿(mǎn)足組合原則，并不能說(shuō)明邏輯系統(tǒng)可以不滿(mǎn)足組合原則。邏輯分析是一種語(yǔ)義分析，但語(yǔ)義分析不一定是邏輯分析。邏輯分析是一種徹底的語(yǔ)義分析。所謂徹底，就是說(shuō)我們提出的語(yǔ)義概念能夠完全說(shuō)明系統(tǒng)在這種語(yǔ)義下的性質(zhì)。如用真值（真和假）去分析古典邏輯系統(tǒng)，就是一種徹底的語(yǔ)義分析，因?yàn)橛谜嬷悼梢酝耆f(shuō)明系統(tǒng)在真值意義下的全部性質(zhì)。而用真值去分析模態(tài)邏輯系統(tǒng)，就不是一種徹底的語(yǔ)義分析，因?yàn)閮H用真值一般無(wú)法確定必然命題的真假。既然一般命題邏輯系統(tǒng)中的公式是由命題變項(xiàng)和算子

16、組成，所以公式的語(yǔ)義就應(yīng)該由命題變項(xiàng)和算子的語(yǔ)義所確定，這就是組合原則。弱的值確定原則是類(lèi)似的。在徹底的語(yǔ)義分析中，有效性也應(yīng)該由語(yǔ)義完全確定，所以?xún)蓚€(gè)語(yǔ)義完全相同的公式，它們的有效性當(dāng)然是一樣的。以上討論說(shuō)明了，如果一種語(yǔ)義學(xué)不滿(mǎn)足組合原則和弱的值確定原則，就不是一種徹底的分析，因而不能充當(dāng)一種邏輯意義上的語(yǔ)義學(xué)。我不能為強(qiáng)的值確定原則作辯護(hù)，幸運(yùn)的是命題邏輯中還沒(méi)有發(fā)現(xiàn)不符合強(qiáng)的值確定原則的語(yǔ)義學(xué)。作為邏輯系統(tǒng)，僅有組合原則和弱的值確定原則還是不夠的，普遍性原則也是必須的。這就是說(shuō)僅有模型完全性是不夠的，至少要有一般框架完全性。從一般框架完全性到框架完全性還可以作更細(xì)的分類(lèi)。首先來(lái)看框架完全性的意義。按“內(nèi)涵是可能世界到真值的函數(shù)”的看法，可以對(duì)賦值的條件（3）作出分析。經(jīng)過(guò)簡(jiǎn)單的轉(zhuǎn)化，內(nèi)涵也可以看成可能世界的子集。賦值的條件（3）實(shí)際上包含兩個(gè)關(guān)于內(nèi)涵的原則。原子性原則。任何內(nèi)