不同邏輯間翻譯的完備性畢業(yè)論文

1、 畢 業(yè) 設(shè) 計(jì) (論 文) 專(zhuān)專(zhuān) 業(yè)業(yè) 信息與計(jì)算科學(xué)信息與計(jì)算科學(xué) 班班 級(jí)級(jí) 07 信息（信息（2）班）班 學(xué)生姓名學(xué)生姓名 學(xué)學(xué) 號(hào)號(hào) 課課 題題 不同邏輯間翻譯的完備性不同邏輯間翻譯的完備性 指導(dǎo)教師指導(dǎo)教師 2011 年年 5 月月 31 日日 不同邏輯間翻譯的完備性 摘要摘要: 數(shù)理邏輯是用數(shù)學(xué)方法來(lái)研究推理的形式結(jié)構(gòu)和推理規(guī)律的數(shù)學(xué)學(xué)科.它與數(shù) 學(xué)的其他分支、計(jì)算機(jī)科學(xué)、人工智能、語(yǔ)言學(xué)等學(xué)科均有密切的聯(lián)系，它日益顯示 出它的重要作用和更加廣泛的應(yīng)用前景.數(shù)理邏輯是形式邏輯與數(shù)學(xué)思想結(jié)合的產(chǎn)物但 數(shù)理邏輯研究的是各學(xué)科共同遵從的一般性的邏輯規(guī)律，而各門(mén)學(xué)科只研究自身的具 體規(guī)律

2、. 本論文討論了在論域有限的情況下，命題邏輯與一階邏輯的關(guān)系.該文提出了語(yǔ) 義忠實(shí)和語(yǔ)義滿(mǎn)兩條邏輯性質(zhì)來(lái)確?？蓾M(mǎn)足的公式翻譯為可滿(mǎn)足的公式，不可滿(mǎn)足公 式翻譯翻譯為不可滿(mǎn)足公式.本文說(shuō)明了在 henkin 語(yǔ)義下，二階邏輯到一階邏輯的翻 譯是滿(mǎn)足完備性的. 關(guān)鍵字關(guān)鍵字: : 完備性；語(yǔ)義忠實(shí)翻譯；語(yǔ)義滿(mǎn)翻譯；二階邏輯；一階邏輯 logical completeness on translation between different logical abstract mathematical logic is to use mathematical methods to study the

3、structure and reasoning in the form of the law of mathematics reasoning. it with other branches of mathematics, computer science, artificial intelligence, linguistics and other subjects are closely linked, it is increasingly shows its important role and a more broad application prospects. mathematic

4、al logic is the product of the combination of formal logic and mathematical thinking, but mathematical logic is the study of various disciplines together to comply with the general laws of logic, but all subjects only research their own specific rules. the situation of this paper discusses the domai

5、n limited , the relationship between propositional logic and first-order logic. in this paper, two logic properties: the failthfulness and the fullness are defined to ensure the preservations of the satisfiability and the unsatisfiability. in this paper, translation between second-order logic and fi

6、rst-order logic meets completeness in henkin semantics. key words completeness; faithful translation; full translation; second-order logic; first- order 目目 錄錄 摘要摘要.ii abstract .iii 第一章第一章 緒論緒論.1 1.1 課題背景.1 1.2 主要問(wèn)題及研究意義.1 第二章第二章 命題邏輯與一階邏輯命題邏輯與一階邏輯.3 2.1 命題符號(hào)化及聯(lián)結(jié)詞.3 2.2 命題公式及分類(lèi).4 2.3 一階邏輯基本概念.4 2.4 量

7、詞.5 2.5 一階邏輯的合式公式.5 2.6 一階邏輯的模型及賦值.6 2.7 命題邏輯與一階邏輯的關(guān)系.6 2.7.1總體說(shuō)明兩者的關(guān)系.6 2.7.2分析一階邏輯與命題邏輯間的公式間的關(guān)系.6 2.7.3實(shí)例討論一階邏輯與命題邏輯間的關(guān)系.7 第三章第三章 二階邏輯二階邏輯.9 3.1 二階邏輯的簡(jiǎn)介.9 3.2 二階邏輯到一階邏輯的翻譯的性質(zhì).11 3.2.1 性質(zhì)的介紹及證明.11 3.2.2 完備性定理.12 3.2.3 二階邏輯到一階邏輯翻譯的完備性的分析.17 第四章第四章 總結(jié)與展望總結(jié)與展望.18 4.1 總結(jié).18 4.2 展望.18 參考文獻(xiàn)參考文獻(xiàn).19 致謝致謝.2

8、0 第一章第一章 緒論緒論 1.1 課題背景 數(shù)理邏輯這門(mén)學(xué)科建立以后，發(fā)展比較迅速，促進(jìn)它發(fā)展的因素也是多 方面的.比如，非歐幾何的建立，促使人們?nèi)パ芯糠菤W幾何和歐氏幾何的無(wú) 矛盾性. 數(shù)理邏輯近年來(lái)發(fā)展特別迅速，主要原因是這門(mén)學(xué)科對(duì)于數(shù)學(xué)其它分支 如集合論、數(shù)論、代數(shù)、拓?fù)鋵W(xué)等的發(fā)展有重大的影響，特別是對(duì)新近形成 的計(jì)算機(jī)科學(xué)的發(fā)展起了推動(dòng)作用 .反過(guò)來(lái)，其他學(xué)科的發(fā)展也推動(dòng)了數(shù)理 邏輯的發(fā)展. 正因?yàn)樗且蚤T(mén)新近興起而又發(fā)展很快的學(xué)科，所以它本身也存在許多 問(wèn)題有待于深入研究 .現(xiàn)在許多數(shù)學(xué)家正針對(duì)數(shù)理邏輯本身的問(wèn)題進(jìn)行研究. 人工智能邏輯方面的研究很廣闊，一般說(shuō)來(lái)，所有的哲學(xué)邏輯都是人

9、工智 能邏輯，方向上涉及心理學(xué)、認(rèn)知、決策、計(jì)算機(jī)等等都可以，數(shù)理邏輯和模 態(tài)邏輯是它的基礎(chǔ). 在人工智能知識(shí)表示領(lǐng)域根據(jù)不同的實(shí)際應(yīng)用需求，人們可以使用多種不 同的式工具表示知識(shí).比如：直覺(jué)多值邏輯，模糊模態(tài)邏輯，描述邏輯等等.表 達(dá)能力和推理任務(wù)是一個(gè)邏輯的兩個(gè)重要的特征.面對(duì)這些不同形式的邏輯，如 何比較它們?cè)诒磉_(dá)能力和推理任務(wù)上的差異，目前通常的做法是建立兩個(gè)邏輯 間的翻譯，即把一個(gè)邏輯（源邏輯）翻譯到另一個(gè)邏輯（目標(biāo)邏輯）之上，怎 樣確保翻譯是好的翻譯，在提出語(yǔ)義忠實(shí)與語(yǔ)義滿(mǎn)兩條邏輯性質(zhì)來(lái)說(shuō)明可滿(mǎn)足 的公式翻譯為可滿(mǎn)足的公式，不可滿(mǎn)足公式翻譯翻譯為不可滿(mǎn)足公式，并進(jìn)一 步可以證明在

10、henkin 語(yǔ)義下，二階邏輯到一階邏輯的語(yǔ)義忠實(shí)與語(yǔ)義滿(mǎn)的翻譯， 也是滿(mǎn)足完備性. 應(yīng)用前景，坦白說(shuō)，不管是學(xué)人工智能邏輯還是數(shù)理邏輯，將來(lái)最合適的 還是呆在研究機(jī)構(gòu)里搞研究，而且主要是搞將元理論應(yīng)用于其他理論的交叉研 究；至于能否應(yīng)用于實(shí)際，這個(gè)比前面說(shuō)的將理論應(yīng)用于理論要難很多，要看 研究人員的機(jī)遇、原來(lái)的學(xué)科背景和能力了. 1.2 主要問(wèn)題及研究意義 一個(gè)邏輯的表達(dá)能力可以從以下的 3 個(gè)角度來(lái)分析：（1）給定一個(gè)邏輯， 什么樣的符號(hào)串是該邏輯的公式（well-formed formula） ；（2）一個(gè)邏輯公式 的語(yǔ)義解釋?zhuān)唬?）利用翻譯把一個(gè)邏輯翻譯到另一個(gè)邏輯之上，然后比較兩個(gè)

11、邏輯的相對(duì)表達(dá)能力. 現(xiàn)有的許多翻譯主要側(cè)重討論兩個(gè)邏輯間語(yǔ)法的對(duì)應(yīng)關(guān)系，建立邏輯語(yǔ)言 間的翻譯和公式間的翻譯，驗(yàn)證這樣的翻譯具備如下邏輯性質(zhì)：（1）可靠性 （the soundness）.對(duì)任意的公式，如果可滿(mǎn)足則翻譯后的公式也滿(mǎn)足. （2）完備性（the completeness）.對(duì)任意的公式，如果可滿(mǎn)足，則可 滿(mǎn)足.由式（1）和式（2）可知，公式的可滿(mǎn)足性在可靠和完備的翻譯下被保持.但 是這樣的翻譯不保持不可滿(mǎn)足性，即可靠的和完備的翻譯可以將不可滿(mǎn)足的公 式翻譯為可滿(mǎn)足的公式.造成這一問(wèn)題的主要原因是在建立翻譯的時(shí)候只考慮了 語(yǔ)言間的翻譯和公式間的翻譯，沒(méi)有建立其相應(yīng)的語(yǔ)義翻譯. 針對(duì)

12、上述問(wèn)題，定義一個(gè)邏輯到另一個(gè)邏輯間的翻譯由語(yǔ)法層翻譯和語(yǔ)義 層翻譯組成.語(yǔ)法層翻譯是由邏輯語(yǔ)言間的翻譯和公式間的翻譯構(gòu)成；語(yǔ)義層翻 譯是由模型間的翻譯和賦值間的翻譯構(gòu)成.為了確保源邏輯的可滿(mǎn)足公式翻譯為 目標(biāo)邏輯的可滿(mǎn)足公式，不可滿(mǎn)足公式翻譯為不可滿(mǎn)足公式. 第二章第二章 命題邏輯與一階邏輯命題邏輯與一階邏輯 2.1 命題符號(hào)化及聯(lián)結(jié)詞 數(shù)理邏輯研究的中心問(wèn)題是推理，而推理的前提和結(jié)論都是表達(dá)判斷 的陳述句.因而，表達(dá)判斷的陳述句構(gòu)成了推理的基本單位.于是，稱(chēng)能判斷真 假的陳述句為命題.這種陳述句的判斷只有兩種可能，一種是正確的判斷，一種 是錯(cuò)誤的判斷.稱(chēng)判斷為正確的命題的真值為真，稱(chēng)判斷為

13、錯(cuò)誤的命題的真值為 假，因而又可以稱(chēng)命題邏輯是具有唯一真值的陳述句.如：（1）2 是素?cái)?shù). （2）3 能被 2 整除.（1）和（2）都是簡(jiǎn)單的陳述句，都不能分解成更簡(jiǎn)單的 句子，稱(chēng)這樣的命題為簡(jiǎn)單命題或原子命題.本論文中用小寫(xiě)的英文字母，p ， ，, ,表示簡(jiǎn)單命題，將表示命題的符號(hào)放在該命題的前面，qr i p i q i r 稱(chēng)為命題符號(hào)化. 以上討論的是簡(jiǎn)單命題.在命題邏輯中，主要是研究由簡(jiǎn)單命題用聯(lián)結(jié)詞聯(lián) 結(jié)而成的命題，這樣的命題稱(chēng)為復(fù)合命題.以下是對(duì)聯(lián)結(jié)詞的定義： 定義 2.1.1 設(shè)為任一命題.復(fù)合命題“非”（或“的否定”）稱(chēng) 2 ppp 為的否定式，記作.為否定聯(lián)結(jié)詞.為真當(dāng)且僅

14、當(dāng)為假.pppp 定義 2.1.2 設(shè)，為兩命題.復(fù)合命題“并且”（或“和”） 2 pqpqpq 稱(chēng)作與的合取式，記作.為合取聯(lián)結(jié)詞.為真當(dāng)且僅當(dāng)與同pqpqpqpq 時(shí)為真. 定義 2.1.3 設(shè)，為兩命題.復(fù)合命題“或”稱(chēng)作與的析取式， 2 pqpqpq 記作.為析取聯(lián)結(jié)詞.為真當(dāng)且僅當(dāng)與中至少一個(gè)為真.pqpqpq 定義 2.1.4 設(shè)，為兩命題.復(fù)合命題“如果，則”稱(chēng)作與的 2 pqpqpq 蘊(yùn)涵式，記作，稱(chēng)蘊(yùn)涵式的前件，為蘊(yùn)涵式的后件.稱(chēng)作蘊(yùn)涵聯(lián)結(jié)pqpq 詞.為假當(dāng)且僅當(dāng)為真且為假.pqpq 定義 2.1.5 設(shè)，為兩命題.復(fù)合命題“當(dāng)且僅當(dāng)”稱(chēng)作與的 2 pqpqpq 等價(jià)式，記

15、作.稱(chēng)作等價(jià)聯(lián)結(jié)詞.真當(dāng)且僅當(dāng)，真值相同.pqpqpq 2.2 命題公式及分類(lèi) 真值可以變化的簡(jiǎn)單陳述句稱(chēng)為命題變項(xiàng)或命題變?cè)?，也用?，pqr , ,表示.命題變項(xiàng)不是命題.若在復(fù)合命題中， 等不僅可以 i p i q i rpqr 代表常項(xiàng)，還可以代表命題變項(xiàng)，這樣組成的復(fù)合命題形式稱(chēng)為命題公式.抽象 的說(shuō)，命題公式是由命題常項(xiàng)，命題變項(xiàng)，聯(lián)結(jié)詞，括號(hào)等組成的符號(hào)串.但并 不是由這些符號(hào)組成的符號(hào)串都是命題公式，因而，必須給出命題公式的嚴(yán)格 定義： 定義定義 2.2.12.2.1 （1）單個(gè)命題常項(xiàng)或變項(xiàng)， ，, ,，0，1pqr i p i q i r 是合式公式； （2）如果是合式公式

16、，則（）也是合式公式；aa （3）如果，是合式公式，則（） ， （） ， （） ， （abababab ）也是合式公式；ab （4）只有有限次地應(yīng)用（1）（3）組成的符號(hào)串才是合式公式. 在本論文中將合式公式稱(chēng)為命題公式，或簡(jiǎn)稱(chēng)為公式. 定義定義 2.2.22.2.2 設(shè)為一個(gè)命題公式.a （1）若在它的各種賦值下取值均為真，則稱(chēng)為重言式或永真式；aa （2）若在它的各種賦值下取值均為假，則稱(chēng)為矛盾式或永假式；aa （3）若至少存在一組賦值是成真賦值，則是可滿(mǎn)足式.aa 2.3 一階邏輯基本概念 在一階邏輯中，簡(jiǎn)單命題被分解成個(gè)體詞和謂詞兩部分.所謂個(gè)體詞是指可 以獨(dú)立存在的客體，它可以是一個(gè)

17、具體的事物，也可以是一個(gè)抽象的概念.例如， 李明，玫瑰花，黑板，自然數(shù)等都可以作為個(gè)體詞.而謂詞是刻畫(huà)個(gè)體詞的性質(zhì) 或個(gè)體詞之間關(guān)系的詞，如下面 2 個(gè)簡(jiǎn)單命題中：（1）王宏是程序員.（2）小 李比小趙高 2 厘米.“王宏”，“小李”，“小趙”都是個(gè)體詞.“.是程 序員”，“.比.高 2 厘米”都是謂詞. 表示具體的或特定的個(gè)體的詞稱(chēng)為個(gè)體常項(xiàng)，一般用小寫(xiě)的英文自母,ab ,.表示.表示抽象的，或泛指的個(gè)體的詞稱(chēng)為個(gè)體變項(xiàng)，常用小寫(xiě)英文字母c ，表示.個(gè)體變項(xiàng)的取值范圍稱(chēng)為個(gè)體域或論域，個(gè)體域可以是有xyz 限事物的集合，也可以是無(wú)限事物的集合. 稱(chēng)表示具體性質(zhì)或關(guān)系的謂詞謂詞常項(xiàng)，用大寫(xiě)英文

18、字母，fgh 表示，例如表示“是無(wú)理數(shù)”.而表示抽象的或泛指的謂詞稱(chēng)為謂詞變項(xiàng)，f 也用，表示.個(gè)體變項(xiàng)具有性質(zhì)，記作.個(gè)體變項(xiàng)，fghxf( )f xx 具有性質(zhì)，記作，論文中稱(chēng)這種個(gè)體變項(xiàng)和謂詞的聯(lián)合體，yl( , )l x y 2 ( )f x 等為謂詞.( , )l x y 2.4 量詞 在一階命題邏輯中，除了個(gè)體詞和謂詞外，還有表示數(shù)量的詞，稱(chēng)表示數(shù) 量的詞為量詞.量詞有兩種： 1.全稱(chēng)量詞：對(duì)應(yīng)日常語(yǔ)言中的“一切” ， “所有的” ， “任意的”等詞，用 符號(hào)“”表示.表示對(duì)個(gè)體域里的所有個(gè)體.表示個(gè)體域里的所有x( )xf x 個(gè)體都有性質(zhì).f 2.存在量詞：對(duì)應(yīng)日常語(yǔ)言中的“存

19、在著” ， “有一個(gè)” ， “至少有一個(gè)”等 詞，用符號(hào)“”表示.表示存在個(gè)體域里的個(gè)體.表示存在著個(gè)體域x( )xf x 里的個(gè)體具有性質(zhì).f 命題邏輯中的五中聯(lián)結(jié)詞在一階邏輯中均可應(yīng)用. 2.5 一階邏輯的合式公式 定義定義 2.5.12.5.1 項(xiàng)的定義如下： （1） 個(gè)體常項(xiàng)和變項(xiàng)是項(xiàng) （2） 若是任意元函數(shù)， ，是項(xiàng)，則 12 ( ,.,) n x xxn 1 t 2 t n t 也是項(xiàng)； 12 ( , ,.,) n t tt （3） 只有有限次的使用（1） ， （2）生成的符號(hào)串才是項(xiàng). 定義定義 2.5.22.5.2 設(shè)是任意的元謂詞， ，是項(xiàng)，則稱(chēng) 12 ( ,.,) n r

20、x xxn 1 t 2 t n t 為原子公式. 12 ( , ,.,) n r t tt 定義定義 2.5.32.5.3 合式公式的定義如下： （1） 原子公式是合式公式； （2） 若是合式公式，則（）也是合式公式；aa （3） 若 ，是合式公式，則（） ， （） ， （） ， （）ababababab 也是合式公式； （4） 若是合式公式，則，也是合式公式；axaxa （5） 只有有限次地應(yīng)用（1）（4）構(gòu)成的符號(hào)串才是合式公式（也稱(chēng)謂詞公 式）. 定義定義 2.5.42.5.4 設(shè)為一謂詞公式，如果在任何賦值下都是真的，則稱(chēng)為邏輯aaa 有效式；如果在任何賦值下都是假的，則稱(chēng)是不可滿(mǎn)足式

21、；若至少存在一aa 個(gè)賦值使為真，則是可滿(mǎn)足式.aa 2.6 一階邏輯的模型及賦值 一般情況下，一個(gè)一階邏輯合式公式中含有：個(gè)體常項(xiàng)，個(gè)體變項(xiàng)，謂詞變 項(xiàng)等.由此我們可以定義一個(gè)模型：i 定義定義 2.6.12.6.1 一個(gè)模型由下面 4 部分組成：i 9 （1） 非空個(gè)體域；d （2）中一部分特定元素；d （3）上一些特定的函數(shù)；d （4）上一些特定的謂詞；d 對(duì)各種變項(xiàng)指定特殊的常項(xiàng)去代替，就構(gòu)成了一個(gè)公式的賦值. 2.7 命題邏輯與一階邏輯的關(guān)系 2.7.1 總體說(shuō)明兩者的關(guān)系總體說(shuō)明兩者的關(guān)系 在謂詞中所包含的個(gè)體詞數(shù)稱(chēng)為元數(shù).含（）個(gè)個(gè)體詞的謂詞稱(chēng)為n1n 元謂詞.用表示元謂詞，它是

22、以個(gè)體變項(xiàng)的個(gè)體域?yàn)槎x域n 12 ( ,.) n p x xxn （論文中為有限域） ，以0，1為值域的元函數(shù)，在這里個(gè)個(gè)變項(xiàng)的順序不nn 能隨意改動(dòng).謂詞不是命題，它的真值無(wú)法確定，要想使它成為命 12 ( ,.) n p x xx 題，必須指定某一謂詞常項(xiàng)代替，同時(shí)還要用個(gè)個(gè)體常項(xiàng)代替?zhèn)€個(gè)體變pnn 項(xiàng).例如，是一個(gè) 2 元謂詞，它不是命題.當(dāng)令表示“小于”( , )l x y( , )l x yxy 之后，該謂詞中的謂詞部分已為常項(xiàng)，但它還不是命題.當(dāng)取為 2，為 3 時(shí)，ab 才是命題，并且是真命題.當(dāng)取 為 2，為 1 時(shí)，為假命題.將不( , )l a bcd( , )l c d

23、 帶個(gè)體變項(xiàng)的謂詞稱(chēng)為 0 元謂詞，例如，等都是 0 元謂詞.一旦( , )l a b( , )l c d 其中的的意義明確之后，0 元謂詞都是命題.因而命題邏輯中的簡(jiǎn)單命題都可l 以用 0 元謂詞表示. 2.7.2 分析一階邏輯與命題邏輯間的公式間的關(guān)系分析一階邏輯與命題邏輯間的公式間的關(guān)系 在上文我們定義可知個(gè)體變項(xiàng)和謂詞（在這里我們規(guī)定此謂詞為謂詞常項(xiàng)） 的聯(lián)合體，等為謂詞，我們又知在一階邏輯中，簡(jiǎn)單命題被分為個(gè)( )f x( , )l x y 體詞和謂詞（這里的謂詞是謂詞常項(xiàng)）.由上文對(duì)命題變?cè)亩x可知，命題變 元可被分為個(gè)體變項(xiàng)與謂詞.所以我們可以對(duì)，等謂詞可以用命題( )f x(

24、 , )l x y 邏輯中的命題變?cè)?，表?所以可以總結(jié)出：pq 設(shè)是含一階邏輯的原子公式，的謂詞公式， 0 a 1 a 2 a n a ，是個(gè)命題變?cè)蛎}常元，可以用處處代替（） ， 1 p 2 p n pn i p i a1in 所得命題公式稱(chēng)為的替代.a 0 a 在有限域中，如，由量詞的意義對(duì)于任意的謂詞，都 12 ,., n da aa( )a x 有： （1），此時(shí)的為個(gè) 12 ( )()().() n xa xa aa aa a 8 ( )(1,2,., ) i a ain i a 體常項(xiàng)，即為 0 元謂詞，則可以用命題邏輯中的簡(jiǎn)單命題表示.所以對(duì)( ) i a a i p 此形

25、式的在命題邏輯中可以用復(fù)合命題來(lái)表示.( )xa x 12.n ppp （2），此時(shí)的為個(gè) 12 ( )()().() n xa xa aa aa a 8 ( )(1,2,., ) i a ain i a 體常項(xiàng)，即為 0 元謂詞，則可以用命題邏輯中的簡(jiǎn)單命題表示.所以對(duì)( ) i a a i q 此形式的在命題邏輯中可以用復(fù)合命題表示.( )xa x 2 . in qqq 2.7.3 實(shí)例討論一階邏輯與命題邏輯間的關(guān)系實(shí)例討論一階邏輯與命題邏輯間的關(guān)系 對(duì)于謂詞公式，并且對(duì)模型賦值為個(gè)體域?yàn)橛邢抻? )( )xf xxf x ，這里沒(méi)有特定元素和函數(shù)，謂詞定義為“大于 0”.由以上1,2,3

26、d ( )f xx 的一階邏輯與命題邏輯公式間的替換規(guī)則可知，該謂詞公式可以替換為命題邏 輯中的復(fù)合命題公式（）（）.我們知道 0 元謂詞就 123 ppp 123 ppp 是命題邏輯中的簡(jiǎn)單命題，在這里就是表示的意義，即 大于 0.對(duì) i p( )(1,2,3)f i i i 賦值后的謂詞公式進(jìn)行分析，在這里表示“1，2，3( )( )xf xxf x ( )xf x 都大于 0” ，則為真，在這里表示“在 1，2，3 中存在大于 0 的( )xf x( )xf x 數(shù)” ，則為真，可知謂詞公式在此種賦值情況下為真.( )xf x( )( )xf xxf x 分析翻譯后的復(fù)合命題公式（）（）

27、 ，由表示的意 123 ppp 123 ppp i p 義可知為真，則和都為真，則復(fù)合命題公式（ i p 123 ppp 123 ppp ）（）為真，有以上分析，可以歸納為： 123 ppp 123 ppp （1） 謂詞公式：；( )( )xf xxf x （2） 個(gè)體域；1,2,3d （3） 謂詞：表示“大于 0” ；( )f xx （4） 翻譯：（）（） （( )( )xf xxf x 123 ppp 123 ppp 表示“ 大于 0” ，與意義相同） ；并且在這種賦值情況(1,2,3) i p i i( )(1,2,3)f i i 下替換前和替換后的公式的真值都為真. 上面的例子說(shuō)明在模

28、型中不一定要寫(xiě)出特定元素與特定的函數(shù)，下面的例 子來(lái)做含有此兩項(xiàng)的討論：對(duì)于一階邏輯合式公式，規(guī)( ( ( )( ,( )x f f xg a f x 定個(gè)體域?yàn)?；中的特定元素；函?shù)為，2,3d d2a ( )f x(2)3f ；謂詞表示“是偶數(shù)” ，表示“大于” ；有公式間的(3)2f( )f xx( , )g x yxy 替換規(guī)則可知可被替換為命題邏輯中的復(fù)合公式( ( ( )( ,( )x f f xg a f x ，并且與表示相同的意義，即“3 是偶數(shù)” ，所以 1122 ()()pqpq 1 p( (2)f f 的真值為假，與表示相同的意義，即“2 是偶數(shù)” ，所以的真值 1 p 2

29、 p( (3)f f 2 p 為真；與表示相同的意義.即“2 大于 2” ，所以真值為假，與 1 q( ,(2)g a f 1 q 2 q 表示相同的意義，即“2 大于 3” ，真值為假，可知( ,(3)g a f 2 q 的真值為假；而此時(shí)表示“在 2，3 1122 ()()pqpq( ( ( )( ,( )x f f xg a f x 中存在偶數(shù)并且存在著小于 2 的數(shù)” ，可知的真值為假.( ( ( )( ,( )x f f xg a f x 在這里要知道函數(shù)的定義域與值域必須是論域的除空集的子集，如果值( )f xd 域不是論域的除空集的子集，比如說(shuō)的值域有不是中的元素，則對(duì)謂詞( )

30、f xd 進(jìn)行賦值時(shí)就會(huì)含有不是論域中的個(gè)體常項(xiàng)，則進(jìn)一步就說(shuō)明論域要含有d ，則與不含有矛盾，所以的值域論域的除空集的子集.d( )f xd 第三章第三章 二階邏輯二階邏輯 3.1 二階邏輯的簡(jiǎn)介 為了得到比一階邏輯更豐富，更富有表現(xiàn)力的語(yǔ)言，我們可以對(duì)謂詞符號(hào)和 函數(shù)符號(hào)添加量詞.例如，是一個(gè)謂詞公式，而( ( )( )x p xxp x 是一個(gè)二階邏輯的公式.為了說(shuō)明二階邏輯的公式，下面( ( )( )p x p xxp x 介紹一下邏輯符號(hào)： （1） 謂詞變?cè)簩?duì)于每個(gè)正整數(shù)，我們有元謂詞變?cè)?10 nn 1 n x 2 n x （2） 函數(shù)變?cè)簩?duì)于每個(gè)正整數(shù)，我們有元函數(shù)變?cè)?

31、10 nn 1 n f 2 n f 下面定義二階邏輯的合式公式： 定義定義 5.5.15.5.1 設(shè)是任意的元謂詞， ，是項(xiàng)，則稱(chēng) 12 ( ,.,) n r x xxn 1 t 2 t n t 為原子公式. 12 ( , ,.,) n r t tt 定義定義 5.5.25.5.2 合式公式的定義如下： （1） 原子公式是合式公式； （2） 若是合式公式，則（）也是合式公式；aa （3） 若 ，是合式公式，則（） ， （） ， （） ， （）ababababab 也是合式公式； （4） 若是合式公式，則，也是合式公式；axaxa （5） 若是合式公式，則，也是合式公式；a n i x a n

32、i f a （6） 只有有限次地應(yīng)用（1）（5）構(gòu)成的符號(hào)串才是合式公式. 對(duì)于二階邏輯的模型其滿(mǎn)足一階邏輯模型的 4 部分，并且有所擴(kuò)展：設(shè)是v 所有個(gè)體變?cè)?，謂詞變?cè)秃瘮?shù)變?cè)募希⒃O(shè) 是上的函數(shù)，且滿(mǎn)足sv 是論域中的一個(gè)元素，是論域中的元關(guān)系，是元運(yùn)算， 1 ( )s v() n s xun() n s fn 這樣可知謂詞變?cè)秃瘮?shù)變?cè)募蠟?2u 11 現(xiàn)在對(duì)二階邏輯做出總結(jié)，在這之前我們我們來(lái)看一個(gè)定義： 定義定義 5.5.35.5.3 若任一真值函數(shù)都可以用僅含某一聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題公式 表示，則稱(chēng)該聯(lián)結(jié)詞集為全功能集. 由定義 5.5.3 可知為一全功能集，在證明這

33、個(gè)結(jié)論前，先來(lái)介紹幾, 6 個(gè)等值式，設(shè)為任意的命題公式： 12 ,a b （蘊(yùn)涵等值式）abab (雙重否定律)aa （等價(jià)等值式）()()ababba ，；（德.摩根律）()abab ()abab 證明：由以上分析可知 5 個(gè)聯(lián)結(jié)詞組成的聯(lián)結(jié)詞集為.由于, , , （1）pq （雙重否定律）pqpq （蘊(yùn)涵等值式）pqpq 即pqpq （2）pq （雙重否定律）()pqpq （德.摩根律）()()pqpq （蘊(yùn)涵等值式）()()pqpq 即()pqpq （3）pq （等價(jià)等值式）()()pqpqqp （雙重否定律）()()()()pqqppqqp （德.摩根律）()()( ()()pqqp

34、pqqp （蘊(yùn)涵等值式）( ()()()()pqqppqqp 由定義 5.5.1 可知為全功能集 ，證完., 我們可以用替換.x x 7 由以上我們總結(jié)二階邏輯：二階邏輯語(yǔ)言包含下列符號(hào)： 元謂詞符號(hào)：，；n 0 p 1 p 邏輯聯(lián)結(jié)詞：；, 全稱(chēng)量詞符號(hào)：； 個(gè)體變?cè)?，?0 x 1 x 函數(shù)變量符號(hào)和謂詞變量符號(hào)：，； 0 x 1 x 標(biāo)點(diǎn)符號(hào)：（， ）. 二階邏輯的公式，定義為： 12 ( , ,.,)|( )|() n r t ttxxxx 二階邏輯有兩種語(yǔ)義：一種是標(biāo)準(zhǔn)語(yǔ)義；另一種是 henkin 語(yǔ)義.如果二 1 階邏輯采用的是標(biāo)準(zhǔn)語(yǔ)義，那么完備性定理在二階邏輯中不成立；如果二階

35、邏 輯采用的是 henkin 語(yǔ)義，那么完備性定理在二階邏輯中成立. 二階邏輯在 henkin 語(yǔ)義下的模型是一個(gè)三元組（， ） ，mu nn n a i 其中為一個(gè)非空集合，為的非空子集，表示函數(shù)變量符號(hào)和謂詞變量u n a2u 符號(hào)的取值域，是一個(gè)解釋?zhuān)沟檬巧系膸ь?lèi)型的關(guān)系. n x n ai i pu 一個(gè)賦值函數(shù) 是變量集合到模型論域上的一個(gè)函數(shù)：對(duì)于任何個(gè)體變量， vx ；對(duì)任何函數(shù)變量和謂詞變量，.( )v xu n x nn xa 二階邏輯在 henkin 語(yǔ)義下到一階邏輯的翻譯既是語(yǔ)義滿(mǎn)的又是語(yǔ)義忠 實(shí)的. 1 3.2 二階邏輯到一階邏輯的翻譯的性質(zhì) 3.2.1 性質(zhì)的介紹及

36、證明性質(zhì)的介紹及證明 一個(gè)邏輯到另一個(gè)邏輯間的翻譯由語(yǔ)法層翻譯和語(yǔ)義層翻譯組成.語(yǔ)法層翻 譯是由邏輯語(yǔ)言間的翻譯和公式間的翻譯構(gòu)成；語(yǔ)義層翻譯是由模型間的翻譯 和賦值間的翻譯組成.現(xiàn)在用表示一個(gè)邏輯，表示邏輯所在的邏輯語(yǔ)言；ss 表示可滿(mǎn)足關(guān)系；假定的邏輯語(yǔ)言不含相等符號(hào)；表示上全體|s( )forms 公式所構(gòu)成的集合；表示上所有模型所構(gòu)成的集合；是上所有( )mods( )vs 賦值所構(gòu)成的集合，給出如下到翻譯的定義：s s 定義定義 3.2.13.2.1 給定兩個(gè)邏輯和，一個(gè)到的翻譯是滿(mǎn)足如下條件的s ss s 一個(gè)映射： （1）語(yǔ)法層.對(duì)中的任意非邏輯符號(hào) ，映射 為中的非邏輯符號(hào)；

37、1 ss 對(duì)中的任意公式，映射為中的公式.( )form ()form （2）語(yǔ)法層.對(duì)中的任意模型，映射為中的模型； 1 ( )modmm ()mod 對(duì)中的任意賦值 ，映射中的賦值.( )vv ()v 定義定義 3.2.23.2.2 設(shè)是到的一個(gè)翻譯，如果滿(mǎn)足：對(duì)于任意給定的上s ss 的公式，模型，賦值 ，都有（， ）當(dāng)且僅當(dāng)（，）mvmv|()m( )v ，則稱(chēng)為一個(gè)語(yǔ)義忠實(shí)的翻譯.|( ) 定義定義 3.2.33.2.3 設(shè)是到的一個(gè)翻譯，如果滿(mǎn)足：對(duì)于任意給定的 3 s s 上的公式，任意的模型，賦值都有：如果（，），那s s m v m v|( ) 么存在的模型和賦值 使得（，

38、）并且，則smvmv| ()mm ( )vv 稱(chēng)為一個(gè)語(yǔ)義滿(mǎn)的翻譯. 命題命題 3.2.43.2.4.如果一個(gè)翻譯是到的既語(yǔ)義忠實(shí)又語(yǔ)義滿(mǎn)的翻譯，那么s s 對(duì)的任意公式，在中不可滿(mǎn)足當(dāng)且僅當(dāng)在中不可滿(mǎn)足.ss( ) s 證明：假設(shè)在中不可滿(mǎn)足但是在中可滿(mǎn)足，那么存在模型和賦s( ) s m 值使得（，）.因?yàn)槭钦Z(yǔ)義滿(mǎn)翻譯，所以就有：的模型和 v m v|( ) sm 賦值 使得（， ）.這與在中不可滿(mǎn)足矛盾.反之，若在中vmv|s( ) s 不可滿(mǎn)足，但是在中可滿(mǎn)足，那么存在模型和賦值 使得（， ）ssmvmv .因?yàn)槭钦Z(yǔ)義忠實(shí)的翻譯，所以就有（，）.這與|()m( )v|( ) 在中不可滿(mǎn)

39、足矛盾.證畢.( ) s 3.2.2 完備性定理完備性定理 定義定義 3.2.53.2.5（協(xié)調(diào)性）（表示公式的集合） ，當(dāng)且僅當(dāng) 4 ( )form ，使得并且（表示形式可推演性關(guān)系）( )aforma a 14 定義定義 3.2.63.2.6 （極大協(xié)調(diào)性）公式集是極大協(xié)調(diào)的，當(dāng)且僅當(dāng)滿(mǎn)足 15 一下的（1）和（2）： （1）是協(xié)調(diào)集； （2）對(duì)于任何，是不協(xié)調(diào)的.a a 定理定理 3.2.73.2.7 設(shè)是極大協(xié)調(diào)集.于是，對(duì)于任何，當(dāng)且僅當(dāng).aa a 證明：如果，則有（） ，.下面證明其逆命題，設(shè).如果aaa ，則由于是極大協(xié)調(diào)的，所以是不協(xié)調(diào)的.于是，因而a aa 不協(xié)調(diào)，這與的極大

40、協(xié)調(diào)性矛盾.因此.a 定理定理 3.2.83.2.8 設(shè)是極大協(xié)調(diào)集.則對(duì)于任何和，ab （1），當(dāng)且僅當(dāng)；a a （2），當(dāng)且僅當(dāng)并且；abab （3），當(dāng)且僅當(dāng)或；abab （4），當(dāng)且僅當(dāng)蘊(yùn)涵；abab （5），當(dāng)且僅當(dāng)?shù)戎涤?abab 證明：證（1）先證.設(shè).如果，則有（）可得aa a a 和，即是不協(xié)調(diào)的，與假設(shè)的的極大協(xié)調(diào)性矛盾.因此.aa a 下面證.設(shè)，如果，則可依次得到：aa aa （1）是不協(xié)調(diào)的；a （2）；a （3）.a 這與矛盾.因此.aa 證（2）先證并且.設(shè)并且.由定理 3.2.7 可abab ab 得及（） （如果，則）：a b ab （1）；aa （2）.bb

41、 因此.ab 下面證并且.設(shè).如果“并且”aba babab 不成立，則依次可得： （1），；ab （2）， （由本定理（1） ） ；ab （3）（由本定理（2） ） ；ab （4）；ab （5）ab 又由假設(shè)可知，這樣是不協(xié)調(diào)的，與的極大協(xié)調(diào)性矛盾.因abab 此并且.ab 證（3）先證或.設(shè)或.由定理 3.2.7 及abab ab （） （如果則，）可得：a abba （1）；aaabab （2）.bbabab 因此.ab 下面證或.設(shè).如果“或”不aba babab 成立，則依次可得： （1），；ab （2）， （由本定理（1） ） ；ab （3）（由本定理（3） ） ；ab （4）；a

42、b （5）()ab 又由假設(shè)可知，這樣是不協(xié)調(diào)的，與的極大協(xié)調(diào)性矛盾.因abab 此或.ab 證（4）先證蘊(yùn)涵.有定理 3.2.7 及（） （如果，ababa 則,）和（） （如果,則）： a abab .bb , ababab 因此ab 下面證蘊(yùn)涵.如果“蘊(yùn)涵”不成立，ababab 依次可得： （1），；ab （2）（由本定理（1） ） ；b （3）（由本定理（3） ） ；ab （4）；ab （5）()ab 又由于可知，即，這樣是不協(xié)調(diào)的，與ab()ab()ab 的極大協(xié)調(diào)性矛盾.因此蘊(yùn)涵.ab 證（5）先證等值于.由定理 3.2.7 及（） （如果abab ，則）和（）可得：, ab,ba

43、ab （1）；aa ,ba （2）；,bbab 由（1） （2）可知，所以.abab 下面證等值于.如果“等值于”不成立，ababab 依次可得： （1），；ab （2）（由本定理（1） ） ；b （3）（由本定理（1） ， （2） ， （3） ） ；( ()()abba （4）；( ()()abba （5）()()abba 又由于可知，這樣是不協(xié)調(diào)的，與的ab()()abba 極大協(xié)調(diào)性矛盾.所以等值于.證畢.ab 定理定理 3.2.93.2.9 如果，存在有限的，使得.a 0 0 a 證：對(duì)的結(jié)構(gòu)作歸納.aa 基始.有規(guī)則（ref）生成的的前提本身是一個(gè)公式，所以 16 aaa 有定理中所

44、說(shuō)的性質(zhì).aa 歸納步驟.證明在剩下十種推演規(guī)則的情形. 規(guī)則（）的情形： 如果，a 則，. a 由歸納假設(shè)，存在有限的，使得.也是，的有限子集.因 0 0 a 0 此規(guī)則（）保存定理中所說(shuō)的性質(zhì). 規(guī)則（）的情形： 如果，ab ，ab 則.a 我們先要證明： （1）存在有限的，使得，. 1 1 ab （2）存在有限的，使得，. 2 2 ab 由歸納假設(shè)，存在有限的，使得.若，則是 ,a b a 的有限子集.根據(jù)（） ，有可得，.令，這就 b ab 1 ab 是（1）.若，則是的有限子集.令.我們有 a a 1 a ，從而得到（1）. 1 ,a （2）的證明是類(lèi)似的. 根據(jù)（） ，可以由（1）

45、和（2）得到： ， 1 2 ab ， 1 2 ab 由此可得，其中的，是的有限子集.故規(guī)則（）保存 1 2 a 1 2 5 定理中所說(shuō)的性質(zhì). 規(guī)則（）的情形： 如果，ab ，a 則.b 由歸納假設(shè)，存在的有限子集和，使得并且.根據(jù) 1 2 1 ab 2 a （） ，可得： ， 1 2 ab ，. 1 2 a 于是有，其中的，是的有限子集.故規(guī)則（）保存定理 1 2 b 1 2 中所說(shuō)的性質(zhì). 其他情形的證明是類(lèi)似的. 由基始和歸納步驟，定理得證. 定理定理 3.2.103.2.10（lindenbaum）任何協(xié)調(diào)的公式集能夠擴(kuò)充為極大協(xié)調(diào)集. 17 證：設(shè)是協(xié)調(diào)的公式集.是可數(shù)無(wú)限集.另(

46、)form （1），是所有公式的任何一個(gè)排列.定義的無(wú)限 0 a 1 a 2 a( ) n form 序列（）如下：0n ，如果協(xié)調(diào)，則，否則 ；于是有： 0 nn a 1 nnn a 1nn （2）. 1nn （3）是協(xié)調(diào)的. n 其中的（2）是顯然的， （3）能夠由對(duì)作歸納而證明.n 令.顯然有.下面證明是本定理所要求的極大協(xié)調(diào)集. * n n n * * 先證是協(xié)調(diào)集.如果不協(xié)調(diào)，即有，使得并且.根據(jù) * * b * b * b 定理 3.2.9，有中的有限個(gè)公式，和，使得： * 1 b k b 1k b l b ，； 1 b k bb ，. 1k b l bb 由此得到： ，. 1 b

47、 l bbb 故，是不協(xié)調(diào)的. 1 b l b 設(shè)，并且.由（2）可得，(1) i it bil 1 max( ,.,) n ttt 1 b l b t 因此是不協(xié)調(diào)的，這和（3）矛盾.故是協(xié)調(diào)的. t * 令，即.是（1）中的公式，令.根據(jù)的構(gòu) * c(0) n cnc m ca 1m 作情形，可知（即）是不協(xié)調(diào)的.（如果是協(xié)調(diào)的， mm a m c mm a 則，因此，即，這與，矛盾.） 1 mmm a 1mm a 1m c n c (0)n 這樣，因?yàn)椋适遣粎f(xié)調(diào)的，因此是極大協(xié)調(diào)集. * m * c * 引理 3.2.11 設(shè)是極大協(xié)調(diào)集.構(gòu)作真假賦值 ，使得對(duì)于任何原 * () p

48、form v 子公式，當(dāng)且僅當(dāng)，于是，對(duì)于任何，當(dāng)且p1 v p * p() p aform1 v a 僅當(dāng). * a 證明：對(duì)的結(jié)構(gòu)作歸納.a 基始.是原子公式.由假設(shè)，引理成立.a 歸納步驟.有，或五種情形.abbcbcbcbc 的情形：ab * b （由定理 3.2.8（1） ） * b （由歸納假設(shè)）0 v b .()1 v b 的情形：abc * bc 或（由定理 3.2.8（3） ） * b * c 或（由歸納假設(shè)）1 v b 1 v c ()1 v bc 的情形abc bc * 并且（由定理 3.2.8（2） ） * b * c 并且（由歸納假設(shè)）1 v b 1 v c ()1

49、v bc 的情形：abc * bc 蘊(yùn)涵（由定理 3.2.8（4） ） * b * c 蘊(yùn)涵（由歸納假設(shè)）1 v b 1 v c ()1 v bc 的情形：abc * bc 等值于（由定理 3.2.8（5） ） * b * c 等值于（由歸納假設(shè)）1 v b 1 v c ()1 v bc 由基始和歸納步驟，引理得證. 定理 3.2.12（完備性）設(shè)，() p form () p aform （1）如果是協(xié)調(diào)的，則是可滿(mǎn)足的； （2）如果是協(xié)調(diào)的，則是可滿(mǎn)足的.aa 證：設(shè)是協(xié)調(diào)的.取任何.把擴(kuò)充為極大協(xié)調(diào)集（由定理 3.2.10） ，b * 則有.由引理 3.2.11，使用其中的真假賦值 ，可得.因此 滿(mǎn)足， * bv1 v b v 這就證明了（1）.（2）是（1）的特殊情形.得證. 3.2.3 二階邏輯到一階邏輯翻譯的完備性的分析二階邏輯到一階邏輯翻譯的完備性的分析 如果二階邏輯在 henkin 語(yǔ)義下的翻譯不是完備性翻譯，我們可令二階邏輯 合式公式集是滿(mǎn)足完備性的，但翻譯為一階邏輯的合式公式集后不滿(mǎn)足完