高級數(shù)理邏輯第8講

1、模態(tài)邏輯漢語中“模態(tài)”是英語詞Modal的音譯。英語詞modality(模態(tài)性)源出于拉丁文modalitas，含形態(tài)、樣式和形式的意思?，F(xiàn)代模態(tài)邏輯是現(xiàn)代邏輯的重要分支，它在科學(xué)和技術(shù)領(lǐng)域的應(yīng)用越來越廣泛，它的許多課題不僅受到邏輯學(xué)家的注意，而且也受到計算機(jī)科學(xué)家和計算機(jī)工程技術(shù)人員以及其他工程技術(shù)人員的關(guān)注。因此，深入研究和發(fā)展這門科學(xué)，已成為邏輯工作者的一項重要任務(wù)。邏輯學(xué)中在兩種意義上，即在狹義和廣義上使用“模態(tài)”這個術(shù)語。涉及必然性，或然性（偶然性），遺傳性和相容性等模態(tài)屬于狹義模態(tài)。從某種觀點來看，它們表達(dá)的是命題的真假強(qiáng)度。因此，也稱為真值模態(tài)。例如：“物體間存在著引力是必然的”

2、；“到本世紀(jì)末我國國民生產(chǎn)總值翻兩翻是可能的”等都屬于這類模態(tài)命題。我們這章的模態(tài)系統(tǒng)主要研究這類狹義模態(tài)性。廣義模態(tài)性是指命題本身所具有的非真值函項的（或非外延的）種種性質(zhì)。廣義模態(tài)詞較多，除了必然、可能之外，尚有必須（應(yīng)該）、允許、禁止；知道、相信、可接受、可疑、可證；曾經(jīng)、總是、將是、優(yōu)先、中立等。這些模態(tài)詞分別是道義邏輯，認(rèn)識邏輯，時態(tài)邏輯，和價值邏輯研究的對象。還有希望、需要等尚未深入研究的模態(tài)詞。其例子為：“宇宙間存在著黑洞是可信的”；“在商品生產(chǎn)的社會中價值規(guī)律起著重要作用是眾所周知的”；“子女贍養(yǎng)扶助父母是應(yīng)該的”；“世界上還存在著野人是可疑的”等。在這章，我們將討論一些模態(tài)命

3、題邏輯的系統(tǒng)，但首先將給出現(xiàn)代模態(tài)系統(tǒng)所要表達(dá)的某些模態(tài)概念的一般敘述。6.1 模態(tài)邏輯介紹本章主要來介紹模態(tài)邏輯系統(tǒng)基本概念，然后，具體介紹命題模態(tài)邏輯和一階謂詞模態(tài)邏輯。Modal logic 6.1.1 模態(tài)邏輯引入邏輯系統(tǒng)的發(fā)展從命題邏輯發(fā)展到了一階謂詞邏輯，主要是因為命題邏輯系統(tǒng)的描述能力有限。模態(tài)邏輯的出現(xiàn)同樣是為了擴(kuò)充一階謂詞邏輯和命題邏輯的描述能力。1、命題邏輯的缺陷：命題邏輯的原子命題不能細(xì)化，層次太高，而不能完全描述世界；例：所有實數(shù)的平方是非負(fù)的；-是實數(shù)；-的平方是非負(fù)的；一階謂詞邏輯，利用謂詞，函詞和量詞來解決這樣的問題；2、命題邏輯和一階謂詞邏輯的缺陷：這兩種邏輯都

4、不能描述有時間概念的變化。任何一個命題都有一個適用的場合的問題；例命題A：汽車是一個必備的生活工具；中國：假；美國：真古代假，現(xiàn)代真；新加坡：假；例如命題B：112命題B在任何時間和任何地點都是成立的，不像命題A只能在一定的時間和場合那成立。因此，可以看出命題是否成立是與其所在的時間和場合有不同的關(guān)系。為了表示這種時間與場合上的概念，我們引入了模態(tài)邏輯來描述這樣的概念。A命題的真假與場合有關(guān)；A在不同場合的值不同；因此，對于命題A是否是真成立是不好確定。為了解決這樣的問題，對于在某些場合成立的命題，規(guī)定為可能真的；除此之外，對于在所有場合為真的命題，我們規(guī)定為必然真的。w1,w2為了解決這樣命

5、題的描述問題，在模態(tài)邏輯中，引入了對必然和可能的描述?？赡埽篈，表示命題A，至少有一個可以實現(xiàn)的場合中，成立。必然：A，表示命題A，在所有能夠?qū)崿F(xiàn)的場合中，成立。3、模態(tài)邏輯的實質(zhì)l 命題邏輯和一階謂詞邏輯的推廣n 對命題邏輯和一階謂詞邏輯，引入了兩個符號模態(tài)詞；u 引入的模態(tài)詞類似于量詞n 在不同場合中，分別是一階謂詞邏輯和命題邏輯；l 場合之間的關(guān)系n 場合從目前所處的場合是否可以實現(xiàn)（達(dá)到）；n 模態(tài)詞A：表示在當(dāng)前場合到以后可以達(dá)到的場合中都是成立的；n 模態(tài)詞A：表示從當(dāng)前場合到以后可以達(dá)到的場合中，至少有一個是成立的。n 與場合之間關(guān)系有著密切的聯(lián)系。l 場合與現(xiàn)實之間的關(guān)系n 程

6、序設(shè)計中的模塊可以是不同的場合n 時間段也可以是不同的場合l 這些不同的場合在模態(tài)邏輯中，成為可能世界6.1.2 基本模態(tài)概念在真命題中，我們可以區(qū)分出那些僅僅偶爾(happen)是真的命題和那些必然(bound)是真的（或不可能是假的）命題。同樣，在假命題中，我們也可以區(qū)分出那些偶爾是假的命題和那些必然(bound)是假的（或不可能是真的）命題。一個必然是真的命題我們稱之為必真(necessary true)命題，或必然真理(necessary truth)，或簡單的說是必然（necessary）命題；一個必然為假的命題我們稱之為不可能(impossible )命題；而既非必然又非不可能的命

7、題則稱為偶然(contingent)命題。當(dāng)然某些偶然命題將是真的，某些偶然命題將是假的。如果一個命題不是不可能的，則稱為可能(possible)命題。這里的“可能”并不意味著“僅僅可能（merely possible）”，如果說p是僅僅可能的，則意指盡管它可能已經(jīng)是真的，但它實質(zhì)上是假的。在我們的意義下，可能命題包含著所有的真命題（更不必說包含著所有的必然命題）。事實上，它們包含著除不可能命題以外的所有命題。在當(dāng)前的上下文中，我們意指的“必然性（necessity）”通常稱為邏輯必然性（logical necessity）。我們無意在此詳細(xì)敘述邏輯必然性的實質(zhì)總之，這個問題充滿著許多哲學(xué)上的

8、困難。我們所用的術(shù)語“必然（necessary）”的含義通過當(dāng)我們說某個命題是必然的時候大概就可以得到充分的說明。我們的意思并不是：因為事物是怎樣的，或者世界是怎樣的，所以這個命題不可能不真；而是，無論事物是怎樣的，也無論世界的結(jié)果象什么，它都不可能不真。例如，盡管命題：沒有物體比光速更快是由很重要的科學(xué)證據(jù)所支持的，但是我們還是傾向于說在某個重要的意義下，一個物體不可能比光速更快這個命題在我們的意義下仍然不被看作是一個必然命題；因為它的支持是由物質(zhì)世界是怎樣的事實組成，而物質(zhì)世界推測起來它可能是而事實上它不是。而命題：所有的未婚男子都是獨(dú)身的，沒有任何余地，不管今天是不是“星期四”，在我們的

9、意義下它都被看作是必然真理。類似地，我們意指的“不可能性”稱為“邏輯”不可能性；我們意指的“偶然性”稱為“邏輯” 偶然性；我們意指的“可能性”稱為“邏輯”可能性；對于這些說法的含義，我們從剛說過的必然性的情況應(yīng)該是完全清楚了。這四個概念：必然性、不可能性、偶然性、可能性，稱為“模態(tài)”概念。它們顯然注：在中世紀(jì)，邏輯必然性等概念被認(rèn)為是一個命題可能是真的或假的方式。是彼此密切相關(guān)的；事實上我們可以根據(jù)它們中的任一個概念來解釋其余三個概念。特別重要的是下列必然性和可能性之間的聯(lián)系：稱一個命題，p，是必然真的，等價于稱p是假的是不可能的；稱p是可能的（或者可能是真的）等價于稱p是假的不是必然為真的。

10、另一個重要的模態(tài)概念是“遺傳（entailment）”。我們把它理解為“邏輯源于（following logically from）”關(guān)系的逆( converse)：即，稱命題p遺傳（entails）命題q，僅僅是q邏輯源于p的一種替換方法，或者說從p到q的推論是邏輯有效的?！跋嗳?consistence)”也是和“邏輯源于”關(guān)系（從而和遺傳模態(tài)）相關(guān)聯(lián)的一種重要的模態(tài)概念。稱命題p和命題q是相容的當(dāng)且僅當(dāng)它們中任何一個的否定都不邏輯源于另一個，或者說它們中的任何一個都不遺傳另一個的否定。直觀上，命題p和命題q相容，就是它們中任何一個的真都不會妨礙另一個是真的。任意給定命題p，我們當(dāng)然可以形成

11、命題：p是必然的，即我們表述為：必然p（It is necessary that p）的命題。這個命題當(dāng)p本身是必然的時為真。而當(dāng)p不是必然的時為假。因此“必然”是一個作用于命題上的（一元（monadic）命題形成算子（operator）。無論怎樣，它不是一個真值函項（truth-functional）算子；因為雖然從p的假性可得出p不是必然的（即，“必然p”是假的），但僅給出p是真的，我們不能確定p是否是必然的即，從p的真性，我們既不可能演繹出“必然p”的真性，也不可能演繹出它的假性。同樣地，“可能（It is possible that）”也是一個作用于命題上的一元命題形成算子，當(dāng)p是可能

12、的時，命題“可能p”應(yīng)是真的；當(dāng)p是不可能的時，命題“可能p”應(yīng)是假的。它也不是真值函項。事實上，在講真值函項算子時曾引導(dǎo)我們的注意力到“邏輯源于”（因而“遺傳”和“相容”）的非真值函項性。我們把這些算子稱作模態(tài)算子（modal operator）。這些即將要考慮的邏輯系統(tǒng)稱為模態(tài)系統(tǒng)或模態(tài)邏輯。這些系統(tǒng)將都基于我們在第二章所建立的那樣的命題演算上；也就是說，它們將包括所有PC的wff，其解釋和以前一樣（故PC的有效wff在這些模態(tài)系統(tǒng)中仍保留有效性），以及包括PC的初始變形規(guī)則，即一致代入規(guī)則和分離規(guī)則、定義置換規(guī)則。但我們已經(jīng)知道模態(tài)算子不是真值函項算子，這意味著它們不可能由PC的算子（諸

13、如Ø，Ú及它們的復(fù)合）來表達(dá)，這是因為PC的算子都是真值函項。所以要得到一個模態(tài)邏輯（在它里面我們可以表達(dá)諸如“必然p” 這樣的命題），為此，我們不得不增加進(jìn)一步的算子到PC，并擴(kuò)張我們的公式的種類。我們將引進(jìn)符號（L）和¯（M）（作為一元算子），符號（作為二元算子），并分別解釋它們的意義為“必然”、“可能”和“遺傳”，并允許它們把任何公式作為自變元。這樣我們就有了諸如下列這樣的wff：pÚ q（意思是“或p是必然的或q（是真的）”），¯(pÙq) ¯q（意思是“命題q是可能的 邏輯源于命題p 且q是可能的”），等等。按照預(yù)

14、定的解釋，我們將稱是必然性算子（necessity operator）和稱¯是可能性算子（possibility operator）。6.1.3 模態(tài)邏輯系統(tǒng)特性我們認(rèn)為什么樣的模態(tài)公式是有效的？很容易給出一個一般的、直觀的有效性的描述。恰與我們當(dāng)初為PC給出的描述一樣，稱一個公式是有效的，當(dāng)且僅當(dāng)對于它的變項們的所有取值它皆為真。在PC中，因為算子的本質(zhì)是真值函項，這個最初的描述直接導(dǎo)致了一個十分簡單的有效性的形式定義。接下來我們就能夠建立起一個公理化系統(tǒng)，并檢查它是否符合命題類應(yīng)該與已定義的有效公式類恰好一致的標(biāo)準(zhǔn)。然而，由于模態(tài)算子的非真值函項特性，最初的描述并不能為我們給出一

15、個總能給予一個清楚結(jié)果的模態(tài)公式有效性的顯而易見的形式定義。但是，有某些條件，如果它有將系統(tǒng)解釋為模態(tài)系統(tǒng)的能力，那么我們要求系統(tǒng)滿足這些條件，從直觀上來說是合乎情理的。這些條件，我們隨后將列出。它們將要求某些公式被看作是有效的（或是命題，如果這個系統(tǒng)是用公理化表示的），同時要求另外一些公式不被看作是有效的；但對于某些公式其有效性和無效性的未確定性將遺作一個問題。下面（在這一章和第六章）我們將構(gòu)造一系列的公理化模態(tài)系統(tǒng)，每個系統(tǒng)都將滿足所有這些要求。但是在象某些不太明顯的有效公式作為命題時，它們的出現(xiàn)或缺省上，這些系統(tǒng)彼此又互不相同。在這之后，我們將回到用一個精確的方式來定義有效性的問題上。因

16、此，象我們在PC中所做的那樣，我們不是衡量一個公理化系統(tǒng)是否符合一個有效性的定義，而是相反，我們將衡量各種有效性的定義是否符合已構(gòu)造出的公理化系統(tǒng)。我們已經(jīng)談到的直觀要求如下（其中一些在我們早期的敘述中已經(jīng)預(yù)示過）：注：眾所周知，直觀上似乎合情合理的事物往往是因人而異的。在我們的合理的表中未發(fā)現(xiàn)所有要求的讀者。1º. 我們已經(jīng)提到必然性和可能性之間的聯(lián)系。這就導(dǎo)致我們要求：如果和¯被解釋為必然性和可能性算子，則下面的等價式應(yīng)該是有效的，p«Ø¯Ø p，¯p«ØØ p；包含這些等價式的系統(tǒng)無須將和

17、¯都作為初始符號：這種系統(tǒng)可以將作為初始符號，并通過下面的定義引入¯¯a = ØØa；或者選取¯作為初始符號，并定義a = دØa；具有前者的系統(tǒng)我們稱為一個-基系統(tǒng)；具有后者的系統(tǒng)，我們稱之為¯-基系統(tǒng)。在下面的幾章中，我們將要研究的系統(tǒng)事實上是-基系統(tǒng)。但在每種情況下，通過選取¯而不是作為初始符號，我們都能夠給出一個恰當(dāng)?shù)?、平行的系統(tǒng)。2º.我們也已經(jīng)指出模態(tài)算子不是真值函項。這意味著在任一直觀上似乎合理的模態(tài)系統(tǒng)中，p必定不與p的任何真值函項等價（由于所有其它模態(tài)算子

18、都可借助來定義，故只須說明要求、如同它適用于一樣，就足夠了）?，F(xiàn)在，只有四個性質(zhì)不同的p的真值函項：第一個是大家熟悉的p的否定；第二個是p自身（它為真當(dāng)且僅當(dāng)p為真）；第三個是當(dāng)p是真的和p是假的時皆為真的一個真值函項；第四個是當(dāng)p是真的和p是假的時皆為假的一個真值函項。因此，我們就要求下面所列出的任何一個都不應(yīng)該被看作是有效的（或是命題）：p«Øp；p«p；p« pÚØp；p« pÙØp。3º.盡管p«p不是有效的，但是很明顯，它的半邊蘊(yùn)涵、即p®p是有效的；因為這簡單的表

19、達(dá)了必然真為真的原理。這個公式通常稱為必然性公理。一個似的原理是真是可能的；這點可用公式p®¯p（可能性可能）來表達(dá)，這個公式我們同樣認(rèn)為是有效的。p®p和p®¯p可以用PC的等價式和聯(lián)系、¯的等價式而很容易地互相導(dǎo)出。4º.另一個直觀上可以接受的原理是任何一個具有有效公式形式的命題不僅是真的而且是必然真的東西。這也就是說如果a是一個有效的公式，那么不僅具有形式a的每個命題都是真的，而且具有形式a的每個命題也都是真的；而且在這種情況下a本身將是有效的。因此，我們希望在一個模態(tài)邏輯中得到這樣一個原理：如果a是有效的，那么a也是

20、有效的；并且在一個公理化模態(tài)系統(tǒng)中我們希望有這樣一個（初始的或?qū)С龅模┳冃我?guī)則：如果a是一個命題，那么a也是一個命題。用現(xiàn)代數(shù)理邏輯工具研究模態(tài)邏輯領(lǐng)域的問題始于美國邏輯學(xué)家路易斯（Lewis）。他在符號邏輯概觀（1918年）一書中建立了第一個模態(tài)邏輯系統(tǒng)。6.1.4 模態(tài)邏輯的簡單(語義)性質(zhì)為了充分理解模態(tài)邏輯的含義，我們首先介紹模態(tài)邏輯的知覺上的語義關(guān)系。通過以上的 、的語義解釋有：l l l l l l 和可能同時成立Al 和不可能同時成 不 （、）Al 1，2，3，4A,B A,B,A,B, ABl ßl à ()l 在未來的場合中，至少有一個場合或者使A成立，或

21、者使B成立。在未來的場合中，或者至少有一個場合使A成立，或者至少有一個場合使B成立。 從以上的關(guān)系上，我們可以知道模態(tài)詞與量詞在某些性質(zhì)上是相同的。而且對于模態(tài)詞來說，我們可以只有一個模態(tài)詞，或者，因此，、可以進(jìn)行等價的轉(zhuǎn)換。6.2 模態(tài)命題邏輯的形式系統(tǒng)以上我們簡單介紹了模態(tài)邏輯系統(tǒng)的中，模態(tài)詞的一些知覺關(guān)系。下面我們遵從形式系統(tǒng)描述方式來，描述模態(tài)命題形式系統(tǒng)。模態(tài)邏輯形式系統(tǒng)與FSPC的形式系統(tǒng)類似，模態(tài)形式系統(tǒng)根據(jù)對模態(tài)詞不同的解釋形成不同形式系統(tǒng)，這些又被成為正規(guī)系統(tǒng)（Normal System）。下面我們就以各種不同正規(guī)系統(tǒng)為背景介紹模態(tài)形式系統(tǒng)。6.2.1 NSK系統(tǒng)構(gòu)成模態(tài)邏輯

22、是研究各種不同的正規(guī)系統(tǒng)，這些正規(guī)系統(tǒng)中，最簡單的是NSK系統(tǒng)。下面我們給出NSK系統(tǒng)的構(gòu)成。1、 NSK系統(tǒng)語言部分l 符號表：,(,) ；其中為原子命題，為聯(lián)接詞，,為模態(tài)詞，(,)技術(shù)符號。l 項集：空集。l 公式集：由以下遞歸定義：1) 為公式(i=1,2,3,4)2) 如A,B為公式,那么,()都是公式 3) 除由1,2得到外,無其它公式2、NSK推理部分l 公理集：包含以下公理：；通常被成為K公理(A1àA2)à( A1àA2)(A1à(A2àA3)à( A1à(A2àA3)à( A1

23、4;(A2àA3)(AàB)à (AàB)(A1à(A2à(A3àA4)à( A1à(A2à(A3àA4)à A1àA2à(A3àA4)à (A1àA2àA3àA4)全部重言式 (當(dāng)A為公理)（Aà(BàA)）l 推理規(guī)則：分離規(guī)則 ,其他概念與FSPC的概念相同，如定理、證明序列等。6.2.2 NSK性質(zhì)1、如果公式A式NSK的定理，那么也式NSK的定理；即如A,則。證明:由已知有,存

24、在A的證明序列對證明序列的長度n歸納證明:當(dāng)n=1時,A為公理,所以A成立；假設(shè)n<k時，命題成立；當(dāng)n=k時,設(shè)Ak由Ai,Aj由分離規(guī)則得到,不妨設(shè)；由于(是定理，是定理（根據(jù)歸納假設(shè)）；由K公理可知，AiAk為定理。根據(jù)分離規(guī)則有：Ak是定理。因此，命題成立。2、設(shè)和為NSK公式，如果，則(成立。3、如果公式是NSK定理，那么A為NSK定理。證明:由于是NSK的定理，即；根據(jù)性質(zhì)1有是定理，即；利用公理有：,因此成立。所以是NSK的定理。4、如果,則B；推廣則()。5、其他相關(guān)性質(zhì)：(1) (2) (3) (4) (5)( )(6) ()()證明（1）：充分性證明：()()

25、4;()K必要性證明：6、把公式A中的, 分別改為和,所得公式為；如果,則成立。AàB6.2.3 正規(guī)系統(tǒng)語義1、正規(guī)結(jié)構(gòu)定義我們知道，對于每個命題的真假都是和可能世界之間有著密切的關(guān)系。對于正規(guī)系統(tǒng)的語義，必須考慮可能世界?？赡苁澜缡欠浅６嗟模赡苁澜鐦?gòu)成一個集合。每個可能世界對應(yīng)于不同的場合，可能世界之間是可變換的。能夠從一個可能變換到另一個可能世界。從一個可能世界，能否變換到另一個可能世界在賦予真值時是非常重要的。例如，如果一個可能世界不能變換到其他的可能世界上，那么在這個可能世界所討論的A和A真都是指A真這一個概念（當(dāng)然，我們假設(shè)這種關(guān)系具有自反性的條件下）?？赡苁澜缰g的這

26、種關(guān)系，實際上是可能世界的集合中的元素之間的關(guān)系。有了這種可能世界的集合和可能世界之間的關(guān)系，那么我們就可以對正規(guī)系統(tǒng)中任何公式賦予一定的真值。KRIPC正規(guī)結(jié)構(gòu)：有以上分析可知，對于正規(guī)系統(tǒng)語義被成為正規(guī)結(jié)構(gòu)，正規(guī)結(jié)構(gòu)是指三元組<U,R,I>，其中：l U為一非空集合，稱為宇宙；其成員為可能世界，可能世界用來標(biāo)記；l R為U上的一個二元關(guān)系，稱為可能世界間的可達(dá)關(guān)系；l I為賦值映射，是上的映射；即對在每一個可能世界中，對原子命題Pi賦值；P1,P2,P3 I(P1)=?×w1àw2,w1àw3 ×w1, w2,w32、 正規(guī)結(jié)構(gòu)的一些解釋

27、我們對正規(guī)系統(tǒng)中的一些公式進(jìn)行解釋，從而能夠更加了解可能世界的概念。l |=表示：指在宇宙中k的w可能世界中，A為假.w1,w2,w3l |=1表示：|=對于所有，即A為真；w2,w3l 表示：存在，且使成立，即A為真；l 從以上結(jié)果可以看出，實際上，模態(tài)邏輯對于以前的結(jié)果不關(guān)心的。3、 例子：通過三個例子，使大家清楚的理解什么是正規(guī)結(jié)構(gòu)。例1：設(shè)宇宙；可達(dá)關(guān)系，其中用表示可達(dá)關(guān)系，并不是說就是偏序關(guān)系或者小于關(guān)系?？蛇_(dá)關(guān)系的機(jī)構(gòu)，可以用下圖來表示：AA AR: A=1 A A在W4后繼集合 AAàAAàAA=1: A=1 & A=1 ?A=1: A=1 &

28、 A:(PàP) w3 (A=PvP)à AA=1:A V AA A=0 v AA (PVP)=0A:A A=1AàAA在w2成立. A指的是 A在W4可達(dá)集合中至少有一個成立。W2=w4 w4=w6,w2A,說明，A在和中真；A，；B;(A&A)=1, (A&A)=0,A，是真命題；根據(jù)賦值定義可以得到；(PP)A，是假命題；根據(jù)賦值定義可以得到；A，等價于A成立；例2：A在可能世界中表示：存在，使得對于所有的，A。例3：證明：（AB）是永真式。只需證明對于任意的宇宙K和可能世界，（AB）=1。根據(jù)演繹定理有：只需證明（AB）；只需證明，B。對于

29、任意的，因為=1成立且成立，因此，在中成立，因此成立。從而命題成立。6.3 NSk元理論對于NSK的元理論，我們還是從語法構(gòu)成、語法語義關(guān)系等方面來論述。6.3.1 語法構(gòu)成1、 NSK是獨(dú)立的,若把公理A從NSk中刪除后,所得系統(tǒng)不滿足A；2、 NSK是一致的,不存在NSk的公式A,使得NSkA和NSkA同時成立；3、 NSk是不完全的,存在公式A,使NSkA和NSkA都不成立；4、 NSk使可判定的,即對公式A,存在一個算法,判定A使否為定理(定理集合為遞歸集合)；5、 演繹定理：對于任何NSk對公式集及公式A,B, ,當(dāng)且僅當(dāng),；6、 替換原理：在NSk中,如果AB,A為C的子公式,將C

30、中若干個A替換為B,得 到公式D,則CD；7、 對偶原理：對任何NSk中公式A, NSk,其中為A的對偶,且A*遞歸定義如下: (6)(A)*=A* (7) (A)*= A*例: (AàB)à( AàB)(AàB)V(AàB)(AàB)V(AVB)(AVB)V(AVB) (AVB)V(AVB) (A&B)V(A&B) =() =(=(AàB)à (AàB)6.3.2 語法語義關(guān)系1、 合理性: NSk是合理的,即如果對公式A有A ,則|=A；2、 完備性: NSk是完備的,即如果對公式A有

31、|=A, 則A。6.4 其它正規(guī)系統(tǒng)6.4.1 其他公理正規(guī)系統(tǒng)的區(qū)別在于公理系統(tǒng)不同，由于公理系統(tǒng)的差別帶來了可達(dá)關(guān)系的不同。下面介紹其他正規(guī)系統(tǒng)中的公理。NSKTD：AA T：AA, AàAB：AA4：AA5：AAw, w11,w12,w13, 包含于w111,w112，并且包含于w121,w122，并且包含于w131,w132|=v(w11,w12,w13) A=1;|=w11,12,13 A=1; |=w111,w112, A=16.4.2 可達(dá)關(guān)系1、連續(xù)性：對于宇宙上的可達(dá)關(guān)系R，如果對于宇宙中的每個可能世界都有一個后繼，則稱R是連續(xù)的。AàA D有R的連續(xù)性可知，對于AA是永真式。在通常的情況下，A 則 A是成立的，例如： 但是當(dāng)w為U中最后一個元素時，(A)=1而(A)=0，因此，A 則 A不成立。 為了使AA，在任何情況下都成立,則必須限制R為連續(xù)的；因此連續(xù)性保證：從而D 連續(xù)2、自反性：對于宇宙上的可達(dá)關(guān)系R，如果滿足，則稱R為自反的。我們知道對于A成立，而A未必成立。如下圖所示：A 解釋:而A不一