數(shù)理邏輯的推理及形式第一講引言一、課程內(nèi)容·數(shù)理邏輯：是計(jì)算機(jī)科學(xué)的基礎(chǔ)，應(yīng)熟練掌握將現(xiàn)實(shí)生活中的條件化成邏輯公式，并能做適當(dāng)?shù)耐评恚@對(duì)程序設(shè)計(jì)等課程是極有用處的。·集合論：數(shù)學(xué)的基礎(chǔ)，對(duì)于學(xué)習(xí)程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、編譯原理等幾乎所有計(jì)算機(jī)專業(yè)課程和數(shù)學(xué)課程都很有用處。熟練掌握有關(guān)集合、函數(shù)、關(guān)系等基本概·代數(shù)結(jié)構(gòu)：對(duì)于抽象數(shù)據(jù)類型、形式語(yǔ)義的研究很有用處。培養(yǎng)數(shù)學(xué)思維，將以前學(xué)過的知識(shí)系統(tǒng)化、形式化和抽象化。熟練掌握有關(guān)代數(shù)系統(tǒng)的基本概念，以及群、環(huán)、域等代數(shù)結(jié)構(gòu)的基本知識(shí)。許多實(shí)際問題很有用處，對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、編譯原理課程也很有幫助。要求掌握有關(guān)圖、樹的基本概念，以及如何將圖論用于實(shí)際問題的解決，并培養(yǎng)其使用數(shù)學(xué)工具建立模型的思維方式。期，第一學(xué)期講授數(shù)理邏輯與集合論，第二學(xué)期講授代數(shù)結(jié)構(gòu)和圖論。考試內(nèi)容限于書中的內(nèi)容和難度，但講課內(nèi)容不限于書中的內(nèi)容和難二、數(shù)理邏輯發(fā)展史而不限于將計(jì)算機(jī)看成是一門技術(shù)或工程性的學(xué)科。件，了解計(jì)算機(jī)科學(xué)中的一些基本思維方式和一些基本問2.數(shù)理邏輯的發(fā)展前期·前史時(shí)期——古典形式邏輯時(shí)期：亞里斯多德的直言三段論理論·初創(chuàng)時(shí)期——邏輯代數(shù)時(shí)期(17世紀(jì)末)發(fā)展技術(shù)方面起到了相當(dāng)重要的作用。·人們希望使用數(shù)學(xué)的方法來(lái)研究思維，把思維過程轉(zhuǎn)換為數(shù)學(xué)的計(jì)算。·萊布尼茲(Leibniz,1646~1716)完善三段論，提出了建立數(shù)理邏輯或者說(shuō)·提出將推理的正確性化歸于計(jì)算，這種演算能使人們的推理不依賴于對(duì)推理過程中的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。·使用一種符號(hào)語(yǔ)言來(lái)代替自然語(yǔ)言對(duì)演算進(jìn)行描述，將符號(hào)的形式和其含義分開。使得演算從很大程度上取決與符號(hào)的組合規(guī)律，而與其含義無(wú)·布爾(G.Boole,1815~1864)代數(shù)：將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。3.數(shù)理邏輯的奠基時(shí)期成的純思維公式語(yǔ)言》(1879)的出版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分——命題演算和謂詞演算的正式建立。·皮亞諾(GiuseppePeano,1858~1932)：《用一種新的方法陳述的算術(shù)原術(shù)的一個(gè)公理系統(tǒng)。·羅素(BertrandRussell,1872~1970)：《數(shù)學(xué)原理》(與懷特黑合著，1910,1912,1913)從命題演算和謂詞演算開始，然后通過一元和二元命題函項(xiàng)定義了類和關(guān)系的概念，建立了抽象的類演算和關(guān)系演算。由此出發(fā)，在類型論的基礎(chǔ)上用連續(xù)定義和證明的方式引出了數(shù)學(xué)(主要是算術(shù))中的主要概念和定理。GGentzen)的自然推理系統(tǒng)(NaturalDeductionSystem)，邏輯演算的元理論：公理的獨(dú)立性、一致性、完全性等。·各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis,1883~1964)的模態(tài)邏輯，實(shí)質(zhì)蘊(yùn)涵怪論和嚴(yán)格蘊(yùn)涵、相干邏輯等，盧卡西維茨的多值邏輯等。4.集合論的發(fā)展·看待無(wú)窮集合的兩種觀點(diǎn)：實(shí)無(wú)窮與潛無(wú)窮·康托爾(G.Cantor,1845~1918)：以實(shí)無(wú)窮的思想為指導(dǎo)，建立了樸素集合論·外延原則(集合由它的元素決定)和概括原則(每一性質(zhì)產(chǎn)生一集合)。·可數(shù)集和不可數(shù)集，確定無(wú)窮集合的本質(zhì)在于集合本身能與其子集一一對(duì)應(yīng)。能與正整數(shù)集合對(duì)應(yīng)的集合是可數(shù)的，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對(duì)角線法證明了實(shí)數(shù)集合是不可數(shù)的。6.第三次數(shù)學(xué)危機(jī)與邏輯主義、直覺主義與形式主義人們覺得數(shù)學(xué)產(chǎn)生了第三次危機(jī)，提出了數(shù)學(xué)的基礎(chǔ)到底是什么這樣的問題。《數(shù)學(xué)原理》一書是他們這一思想的體現(xiàn)。為解決悖論產(chǎn)生了邏輯類型論。·布勞維爾(Brouwer,1881~1966)的直覺主義：數(shù)學(xué)是心靈的構(gòu)造，只承認(rèn)可Heyting的直覺主義邏輯。·希爾伯特(D.Hilbert)的形式主義：公理化方法與形式化方法，元數(shù)學(xué)和證明論，提倡將邏輯演算和數(shù)學(xué)證明本身形式化，把用普通的語(yǔ)言傳達(dá)的內(nèi)容上的數(shù)學(xué)科學(xué)變?yōu)橛脭?shù)學(xué)符號(hào)和邏輯符號(hào)按一定法則排列的一堆公式。為了消除悖論，要數(shù)學(xué)建立在公理化基礎(chǔ)上，將各門數(shù)學(xué)形式化，構(gòu)成形式系統(tǒng)，并證明其一致性，這是希爾伯特的數(shù)學(xué)綱領(lǐng)。7.數(shù)理邏輯的發(fā)展初期·哥德爾(Godel,1906~1978)不完全性定理：一個(gè)足夠強(qiáng)大的形式系統(tǒng)，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能·各種計(jì)算模型：哥德爾的遞歸函數(shù)理論，邱吉爾的演算，圖靈機(jī)模型·這些計(jì)算模型是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，是計(jì)算機(jī)的理論模型。三、預(yù)備知識(shí)1.集合的基本概念·集合(set)：集合是數(shù)學(xué)中最基本的概念之一，不能以更簡(jiǎn)單的概念來(lái)定義(define)，只能給出它的描述(description)。一些對(duì)象的整體就稱為一個(gè)集合，這個(gè)整體的每個(gè)對(duì)象稱為該集合的一個(gè)元素(member或element)。·集合中的元素是無(wú)序的，不重復(fù)的。通常使用兩種方法來(lái)給出一個(gè)集合：A7,8,9}表示所有小于10的自然數(shù)所構(gòu)成的集合·B={a,b,…,z}表示所有小寫英文字母所構(gòu)成的集合質(zhì)概括法：使用某個(gè)性質(zhì)來(lái)概括集合中的元素，如：·C={n|n是質(zhì)數(shù)}表示所有質(zhì)數(shù)所構(gòu)成的集合·空集(emptyset)：約定存在一個(gè)沒有任何元素的集合，稱為空集，記為，有時(shí)也用{}來(lái)表示。按子集的定義，空集是任何集合的子集(為什么)。素所構(gòu)成的集合，即A={x|xA}。通常來(lái)說(shuō)，是在存在一個(gè)全集U的情況下討論集合的補(bǔ)集。全集U是所討論的問題域中所有元素所構(gòu)成的集合。合的并可推廣到多個(gè)集合，設(shè)A,A,…,A都是集合，它們的并定義為：12nAA…A={x|存在某個(gè)i，使得xA}12nixB}，集合的交也可推廣到多個(gè)集合，設(shè)A,A,…,A都是集合，它們的交定義12nAA…A={x|對(duì)所有的i，都有xA}12ni2.關(guān)系和函數(shù)的基本概念的有序?qū)Γ洖?lt;a,b>，定義為集合{{a},{a,b}}。11221122121212n1122aA是元素，定義有序n元組(orderedn-tuple)<a,a,…,a>為<<a,a,…,ann12n12n->,a>，注意這是一個(gè)，將有序n元組的定義歸結(jié)為有序n-1元組的定義。1n顯然有<a,a,…,a>=<b,b,…,b>當(dāng)且僅當(dāng)a=b且a=12n12n1122nnAB={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}·笛卡爾積可推廣到多個(gè)集合的情況，集合A,A,…,A的笛卡爾積12n12n12n1122nn·集合之間的關(guān)系(relation)：定義n個(gè)集合A,A,…,A之間的一個(gè)n元12nRAAAAAAaa,…,12n12n12n12n12n12n·當(dāng)A=A=…=A=A時(shí)，稱R為A上的n元關(guān)系。12n121212121212研究得最多的是二元關(guān)系，n元關(guān)系的許多性質(zhì)可從二元關(guān)系的性質(zhì)擴(kuò)充而得到。如果沒有特別指明的話，說(shuō)R是一個(gè)關(guān)系則是指R是一個(gè)二元關(guān)系。 12n12n12n12n12xyB12單射，即對(duì)任意的yB，都有唯一的原像，同樣根據(jù)全函數(shù)的定義，對(duì)于任意xA都有·定義無(wú)限集合，不直接定義基數(shù)，而是通過定義兩個(gè)集合之間的等勢(shì)B·稱與自然數(shù)集等勢(shì)的集合為可列集(enumerable)，有限集和可列集統(tǒng)稱為可數(shù)集(countable)。3.小結(jié)的關(guān)系：4.歸納定義和歸納證明·歸納步：定義一些規(guī)則(或者說(shuō)操作)，從該集合中已有的元素來(lái)生·最小化：該集合中的所有元素都是通過基本元素以及所定義的規(guī)則生成的，換句話說(shuō)，該集合是由基本元素及規(guī)則所生成的最小的集合。[3].最小化：所有的自然都通過步驟[1]和[2]得到，或者說(shuō)自然數(shù)集是通過步驟[1]和[2]得到的最小集合。·這種定義方式可推廣到對(duì)其他一些概念的定義，例如上述多個(gè)集合的、、以及多個(gè)元素的都可通過遞歸的方式定義。例如，對(duì)于多個(gè)集合的并可定義為：121212n12n-1n要最小化，因?yàn)檫@里不是定義集合。·數(shù)學(xué)歸納法：關(guān)于自然數(shù)的許多性質(zhì)都可通過數(shù)學(xué)歸納法來(lái)證明，對(duì)于性質(zhì)性質(zhì)R對(duì)所有的自然數(shù)成立。這種證明方法的正確性本身可通過自然數(shù)的歸納定義來(lái)S·數(shù)學(xué)歸納法舉例：使用數(shù)學(xué)歸納法證明1+2+…+n=(n*(n+1))/2(這稱為歸納假設(shè))，現(xiàn)在要證對(duì)于n+1也成立。顯然有：1+2+…+n+(n+1)=(n*(n+1))/2+(n+1)形式系統(tǒng)S·一個(gè)由中字母的有限序列(字符串)所構(gòu)成的集合F，稱為形式系SSSS2,…}，稱為形式系統(tǒng)S的規(guī)則(Rule)集，其中R:FF…FF是n元的部分nSSSS12nnn12n·對(duì)于形式系統(tǒng)中的規(guī)則R:FF…FF，通常表示成下面的形式：nSSSS 12nn12n·形式化實(shí)際上是一個(gè)可機(jī)械實(shí)現(xiàn)的過程，在它里面，符號(hào)、規(guī)則和演在形式系統(tǒng)S中，只能使用字母表S中的符號(hào)，只承認(rèn)公式集F中的符號(hào)串的合理性，只能由公理集，根據(jù)規(guī)則推出有意義的東西來(lái)。S·形式系統(tǒng)一旦完成，就成了符號(hào)串及根據(jù)規(guī)則進(jìn)行的符號(hào)串的改寫，系統(tǒng)與一切實(shí)際意義就毫不相干，或者說(shuō)已經(jīng)通過這種符號(hào)，從實(shí)際問題中抽象出了我們所需要研究的內(nèi)容。在形式系統(tǒng)內(nèi)部，所能認(rèn)識(shí)的只能是符號(hào)串及其改寫，只能在形式系統(tǒng)外對(duì)這種符號(hào)串及規(guī)則賦予意義。·數(shù)理邏輯所研究的是“數(shù)學(xué)推理”，而使用的方法也是數(shù)學(xué)推理，所以有必要區(qū)分這兩個(gè)層次的推理。·把作為研究對(duì)象的“推理”形式化，使用形式語(yǔ)言來(lái)表示作為研究對(duì)象的“推理”的前提、結(jié)論和規(guī)則等，這種形式語(yǔ)言是我們所研究的對(duì)象語(yǔ)言。律的表達(dá)和作為研究方面的推理方式使用另一種語(yǔ)言來(lái)表達(dá)，這個(gè)語(yǔ)言稱為研究的元語(yǔ)言，通常使用半數(shù)學(xué)化的自然語(yǔ)·形式語(yǔ)言的語(yǔ)法是構(gòu)成形式系統(tǒng)的公式集、公理集和規(guī)則集的法則。·形式語(yǔ)言的語(yǔ)義是關(guān)于形式系統(tǒng)的解釋和意思。造它們時(shí)是假想它們能代表某種意義的，特別的當(dāng)我們?cè)谶x擇形式系統(tǒng)的公理時(shí)，總是選擇所研究的問題域中那些最為明顯或最容易公認(rèn)為正確的性質(zhì)。6.習(xí)題集/6*6.*7.遞的嗎為什么使用數(shù)學(xué)歸納法證明：12+22+32+…+n2=(n*(n+1)*(2n+1))設(shè)有函數(shù)f:NNN，f(n)=<n,n+1>，請(qǐng)問f是不是單射、滿射或雙射121212請(qǐng)證明，否則請(qǐng)舉一反例。單射請(qǐng)給出<x,y,z>的集合方式的定義。若定義：[x,y,z]={{x},{x,y},{x,1112221212z=z12第二講數(shù)理邏輯一、命題邏輯(PropositionalLogic)1.內(nèi)容概述·簡(jiǎn)單命題與復(fù)合命題：什么是命題命題聯(lián)結(jié)詞及其含義。·命題公式與賦值：命題邏輯公式的歸納定義，命題公式的真值表。·等值演算：命題公式的等值賦值，重要的等值式。·命題聯(lián)結(jié)詞的完備集：通過等值演算得到命題聯(lián)結(jié)詞的完備集和極·命題演算系統(tǒng)：使用命題邏輯公式進(jìn)行推理的形式系統(tǒng)。·命題演算系統(tǒng)的語(yǔ)義與命題演算系統(tǒng)的元性質(zhì)：注意區(qū)別形式系統(tǒng)2.簡(jiǎn)單命題與復(fù)合命題·命題(proposition)：經(jīng)典命題邏輯中，稱能判斷真假但不能既真又假的陳述句為命題。·命題對(duì)于命題邏輯來(lái)說(shuō)是一個(gè)原始的概念，不能在命題邏輯的范圍內(nèi)給出它的精確定義，只能描述它的性質(zhì)。·命題必須為陳述句，不能為疑問句、祈使句、感嘆句等，3.烏鴉是黑色的3是有理數(shù)2.84.1.這個(gè)小男孩多勇敢啊！鴉是黑色的嗎3.但愿中國(guó)隊(duì)能取勝。烏請(qǐng)下列句子不可能判斷其為真或?yàn)榧伲砸膊皇敲}：1.x+y>102.我正在撒謊·命題必須具有真假值，從某種意義上來(lái)說(shuō)，疑問句、祈使句、感嘆句沒有真假之分。但能判斷真假，并不意味著現(xiàn)在就能確定其是真還是假，只要它具有能夠唯一確定的真假值即可，例如下述陳述句1.明年的中秋節(jié)的晚上是晴天2.地球外的星球上存在生物3.21世紀(jì)末，人類將居住在太空4.哥德巴赫猜想是正確的·經(jīng)典命題邏輯不區(qū)分現(xiàn)在已確定為真，還是將來(lái)可能確定為真這種情況，處理與時(shí)間有關(guān)的真值問題是時(shí)態(tài)邏輯的任務(wù)。經(jīng)典命題邏輯也不區(qū)分是在技術(shù)上可以確定為真，還是現(xiàn)在的技術(shù)條件下不可以確定為真的這種情況，只承認(rèn)在技術(shù)上，或者說(shuō)能給出某種方法確定為真的那些東西才為真是直覺邏輯的觀點(diǎn)。·真命題和假命題：命題是為真或?yàn)榧俚年愂鼍洌Q這種真假的結(jié)果為命題的真值。如果命題的真值為真，則稱為真命題，否則稱為假命下標(biāo)來(lái)表示命題常量或者變量。如果命題符號(hào)p代表命題常量則意味它是某個(gè)具體命題的符號(hào)化，如果p代表命題變量則意味著它可指代任何具體命題。如果沒有特別指明，通常來(lái)說(shuō)命題符號(hào)p等是命題變量，即指代任何命題。·簡(jiǎn)單命題與復(fù)合命題：不能分成更簡(jiǎn)單的陳述句的命題為簡(jiǎn)單命題或原子命題，否則稱為復(fù)合命題，復(fù)合命題使用命題聯(lián)結(jié)詞聯(lián)結(jié)簡(jiǎn)單(非)，記為p。合取(與)，記為pq。析取(或)，記為pq。mplicationequivalence中的術(shù)語(yǔ)，而引號(hào)中給出的復(fù)合命題是自然語(yǔ)言中的典型用法。當(dāng)然，命題邏輯中符號(hào)化形式的復(fù)合命題在自然語(yǔ)言中有許許多多的表達(dá)方法，這也是為什么自然語(yǔ)言有歧義的原因，參見教材中的各例題，并注真。但自然語(yǔ)言中的“或”既可能具有相容性，也可能具有排斥性。命題邏輯中采用了“或”的相容性。這種蘊(yùn)涵有比較大的區(qū)別。簡(jiǎn)單命題邏輯中的這種蘊(yùn)涵常常稱為“實(shí)質(zhì)蘊(yùn)涵”，相對(duì)應(yīng)地有“嚴(yán)格蘊(yùn)涵(p嚴(yán)格蘊(yùn)涵q，意味著p為真，則q不可能為假)”、“相干蘊(yùn)涵”等。實(shí)質(zhì)蘊(yùn)涵意味著可從假的前提推出任何命題來(lái)，或兩個(gè)不沒有內(nèi)在聯(lián)系的命題之間存在蘊(yùn)涵關(guān)系。·將日常生活中的陳述句符號(hào)化為命題邏輯中的公式是在今后的程序編寫等課程中應(yīng)用數(shù)理邏輯知識(shí)的重要基礎(chǔ)。但就數(shù)理邏輯這門課程本身而言，我們只關(guān)心公式之間的真值關(guān)系，而不關(guān)心公式所具體指代q0q0q1q1p1p0q000000000003.命題邏輯公式【定義】命題邏輯公式(propositionallogicformul)a由以下子[1].歸納基：命題常量或命題變量是命題邏輯公式，稱為命題邏輯公式的原子項(xiàng)。□在這里我們隱含地使用的字母表是大小寫的英文字母、命題聯(lián)結(jié)符和園括號(hào)。英文字母還可帶下標(biāo)。其它的符號(hào)都不屬于我們的符號(hào)表，即在命題邏輯公式中不能出現(xiàn)這些符號(hào)。后面我們將命題邏輯公式簡(jiǎn)稱為命題公式，或在沒有二義的情況下進(jìn)一步簡(jiǎn)稱為公式。【例子】((pq)((p)(qr)))是命題公式，它通過以下步驟那么，所有的公式A就都滿足性質(zhì)R。□該定理的證明類似數(shù)學(xué)歸納法的證明，很容易根據(jù)定義得到。[2].deg(A)=deg(A)+1;[3].deg(A*B)=max(deg(A),deg(B))+1，其中*代此定義等價(jià)于教材p11的定義。只不過我們?cè)谶@里給出的是遞歸定義。使用歸納法，我們可證明下面定理：】deg(A)小于等于命題公式A中的命題聯(lián)結(jié)符號(hào)的數(shù)目。1.歸納基：如果A是原子項(xiàng)，則根據(jù)定義有deg(A)=0，顯然定理成立。2.歸納步：假設(shè)定理對(duì)于命題公式A和B成立(歸納假設(shè))，記命題公式A中的命題聯(lián)結(jié)符號(hào)數(shù)為Sym(A)，即有deg(A)max(degdeg(B))+1，而Sym(A*B)=Sym(A)+Sym(B)+1，因而有deg(A*B)Sym(A*B)，從而定理對(duì)所有的命題公式都成立。□【定理】任意命題邏輯公式A中出現(xiàn)相等數(shù)目的左右園括號(hào)，實(shí)際□A(AB)□定理的確切含義包括以下幾點(diǎn)：1.任意命題公式必然具有上述6中形式之一；114.如果(A*B)與(A*B)相同，則必有A與A相同，且1111根據(jù)定理和定理，我們不難明白例子是如何得到該其中命題公式的語(yǔ)法分析樹的。實(shí)際上每個(gè)命題公式的最左邊都是左園括號(hào)，如果從第二個(gè)符號(hào)不是左園括號(hào)，那么這個(gè)公式只有一個(gè)命題聯(lián)結(jié)符。否則找與第二個(gè)左園括號(hào)配對(duì)的右園括號(hào)，從而將命題公式劃分為這樣的形式：((…)*(…))，如果原來(lái)的命題公式為根的話，那么左右兩邊的兩個(gè)命題公式分別為它的左右子樹了，而且對(duì)這兩個(gè)公式可作類似的分析，最在后面，為了書寫方便起見，我們省略最外邊的括號(hào)，并規(guī)定各個(gè)命題聯(lián)結(jié)符的優(yōu)先級(jí)別為大于，大于，大于，大于，從而可省略命題公式中一些不必要的園括號(hào)，例如例子中的公式可寫為：pqpqr。不過在后面我們書寫公式的原則是盡量簡(jiǎn)便，但又能讓讀者容易理解。而有關(guān)命題公式的性質(zhì)的討論，則只針對(duì)可由上面定義所能生成的公式上面討論的命題公式的語(yǔ)法結(jié)構(gòu)，下面討論命題公式的賦值。集合到集合{0,1}的函數(shù)。實(shí)際上，對(duì)于某個(gè)命題公式A來(lái)說(shuō)，我們只關(guān)心t在A中的命題變量上的值。這里我們假定存在一個(gè)所有命題變量所組成的集合U，或者說(shuō)我們所有命題公式中的變量都取之于集合U，我們記命題公式A中的所有命題變量所組成的集合為Var(A)。設(shè)有一個(gè)真【例子】對(duì)于命題公式A=((pq)((p)(qr)))，有：Var(A)={p,q,r}這里不妨假定U=Var(A)，真值賦值就是一個(gè)函數(shù)t:{p,q,r}{0,1}，例如可令：t(p)=0,t(q)=1,t(r)=0tABtAB【例子，續(xù)】對(duì)于命題公式A=((pq)((p)(qr)))，及真值t(p)=0,t(q)=1,t(r)=0=1;t((p)(qt(p)=0,t(q)t(pq)=1;t(qr)=0;r))=0;=1;t(r)=0;t((pq)((p)(qr)))=0;等值演算【定義】當(dāng)={A1,A2,…,An}時(shí)，我們也記╞A為A1,A2,…,號(hào)AB，為了不會(huì)過于混淆，我們也使用這種記號(hào)。實(shí)際上，根據(jù)定義，也就是說(shuō)對(duì)任意的t有t(A)=t(B)。從而定義與教材中關(guān)于命題公式等值的定義是等價(jià)的，即有下述定理：□使用真值表，不難證明下面的定理：A(AA)AB(BA)(AB)[4].結(jié)合律：((AB)B)(A(BB))((AB)B)[5].分配律：(A(BC))((AB)(AC))(A(BC))[6].德摩根律：((AB))((A)(B))((AB))□由于命題聯(lián)結(jié)符號(hào)和都滿足結(jié)合律，因此我們可有如下的簡(jiǎn)寫：12n12n根據(jù)以上簡(jiǎn)寫，我們可推廣為以下定理：【定理】12n12n[2].A,A,…,A╞A當(dāng)且僅當(dāng)╞((A(A(…(AA)…))。12n12n□□根據(jù)引理，不難證明下面的置換規(guī)則：某些B(不需要是替換所有的B)而得到的命題公式，則有AA'。歸納基：如果A是命題變量和命題常量，那么必有B=A，因此定112121212111111111212112211221212□【定義】如果命題公式A中只出現(xiàn)命題變量、命題常量、命題聯(lián)結(jié)符號(hào)、和則稱為限制性(命題)公式。定義：于限制性公式A，將其中的命題聯(lián)結(jié)符號(hào)換成，命題聯(lián)結(jié)[2].對(duì)于限制性公式A，將其中出現(xiàn)的所有原子項(xiàng)(命題變量或【例子】設(shè)公式A=((pq)(r))，則：(1).A的對(duì)偶式Aop=((pq)(r))).A的內(nèi)否式A=(((p)(q))r)[1].(Aop)opA(A)A[2].(AB)opAopBop(AB)AB[3].(AB)opAopBop(AB)AB□引理中的(恒等號(hào))表示兩邊的公式在(語(yǔ)法)形式上完全一樣，例式，得到的公式與先求A的內(nèi)否式，然后再做對(duì)偶操作得到的公式完全一樣，用代數(shù)學(xué)的術(shù)語(yǔ)來(lái)說(shuō)，就是這兩種操作可交換。引理很容易根據(jù)定義證明，也可直觀理解引理所代表的含義。讀者可通過對(duì)一些公式求它的對(duì)偶式和內(nèi)否式來(lái)驗(yàn)證引理的每個(gè)恒等式，例【例子，續(xù)】設(shè)公式A=((pq)(r))，則：(1).Aop=((pq)(r)),(Aop)=(((p)(q))r)(2).A=(((p)(q))r),(A)op=(((p)(q))r)顯然有(Aop)(A)op。【證明】略□在中已經(jīng)看到了推論的許多佐證，例如對(duì)于吸收律(A(AB))A，其中(A(AB))的對(duì)偶公式是(A(AB))，從而有(A(AB))A，這與第二個(gè)吸收律公式(A(AB))A是相同的，因?yàn)锳、B代表任意命題公式。【例子】驗(yàn)證下列等值式【證明】證明的思路有兩種，第一種思路是通過列真值表，可看到上述等值式的兩邊在任何真值賦值下都有相同的真值，從而完成上述等值式的驗(yàn)證。讀者不妨自己按照這種思路進(jìn)行證明。第二種思路是利用中的基本等值式來(lái)證明。可以看到上述等值式主要是關(guān)于蘊(yùn)涵的等值式，證明關(guān)于蘊(yùn)涵的等值式的方法是利用定理中的[12]將蘊(yùn)涵化成只出現(xiàn)與、或、非的公式，再來(lái)驗(yàn)證它們的相等。pqrpqr(p(qr))(p(qr))((pq)r)((pq)r)(p(qr))(p)(qr)12n12n12n12nn。□5.聯(lián)結(jié)詞的完全集聯(lián)結(jié)詞實(shí)際上一個(gè)一元真值函數(shù)：f(0)=1,f(1)=0而聯(lián)結(jié)詞、、和則都是二元真值函數(shù)：f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1f(0,0)=0,f(0,1)=1,f(1,0)=1,f(1,1)=1f(0,0)=1,f(0,1)=1,f(1,0)=0,f(1,1)=1f(0,0)=1,f(0,1)=0,f(1,0)=0,f(1,1)=1反過來(lái)，一個(gè)真值函數(shù)就可看成一個(gè)真值聯(lián)結(jié)詞。設(shè)f:{0,1}n{0,1}是一個(gè)n元真值函數(shù)，則可如下定義一個(gè)n元真值聯(lián)結(jié)詞N:f12nf12n12n12n221234不過是其中的4個(gè)。現(xiàn)在的問題是，是否所有的真值函數(shù)都可使用常用【定義】設(shè)是聯(lián)結(jié)詞的一個(gè)集合，稱為聯(lián)結(jié)詞的一個(gè)完全集，如果任12n12n12n【證明】根據(jù)定義只要證明對(duì)任意n元真值函數(shù)都可由只含、、和12kk+1112k12k212k12k12121212p。現(xiàn)在我們證f可由A=((p)A)(pA)表示，其中p是不同于p,kk+11k+12k+11p,…,p的一個(gè)命題變?cè)＜匆C對(duì)命題變?cè)猵,p,…,p,p的一2k12kk+112kk+112kt)。當(dāng)t=0時(shí)，即p被賦值為0，這時(shí)((p)A)與A等值，而k+1k+1k+1k+111k+1211112k12kk+112k12kk+1【證明】1.要證{,}是聯(lián)結(jié)詞的一個(gè)完全集，只要證任一命題公式可與一個(gè)只含和的命題公式等值，事實(shí)上有：(AB)((A)B)(AB)(((A)(B)))2.{,}是聯(lián)結(jié)詞的一個(gè)完全集，因?yàn)椋?AB)(((A)(B)))(AB)((A)B)3.{,}是聯(lián)結(jié)詞的一個(gè)完全集，因?yàn)椋?AB)(((A)(B)))(AB)((A)B)事實(shí)上，上述每個(gè)集合都是極小的完全集，即不能再?gòu)募现腥サ羧我庖粋€(gè)聯(lián)結(jié)詞還能保持是完全集。【證明】總?cè)?值的真值函數(shù)不能由只含此聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題公式來(lái)表達(dá)，因?yàn)檫@樣的命題公式當(dāng)所有命題變?cè)颊嬷蒂x值為16.命題公式的范式【定義】將命題符號(hào)(代表命題變?cè)蛎}常量)或命題符號(hào)的否定統(tǒng)稱為文字(literal)。僅由有限個(gè)文字構(gòu)成的析取式稱為簡(jiǎn)單析取式。僅由有限個(gè)文字構(gòu)成的合取式稱為簡(jiǎn)單合取式。【例子】文字、簡(jiǎn)單析取式與簡(jiǎn)單合取式：(1)p,q等為文字，也是一個(gè)文字的簡(jiǎn)單析取式和簡(jiǎn)單合取式(2)pq,p(q)等為兩個(gè)文字的簡(jiǎn)單析取式，pq(r)為三個(gè)文字的簡(jiǎn)單析取式(3)pq,p(q)等為兩個(gè)文字的簡(jiǎn)單合取式，pq(r)為三個(gè)文字的簡(jiǎn)單合取式【定理】一個(gè)簡(jiǎn)單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題符號(hào)及其否定，一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題符號(hào)及其【定義】由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式(disjunctivenormalfor)m，由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式(conjunctivenormalfor)m。析取范式和合取范式統(tǒng)稱為范式【例子】析取范式和合取范式：(1)(pq)(pq),(pr)(qrp)(rp)等是析取范式(2)(pq)(pq),(pr)(qrp)(rp)等是合取范式根據(jù)知，一個(gè)析取范式的對(duì)偶式是合取范式，一個(gè)合取范式的對(duì)偶【定理】一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。一個(gè)合取范式是永真式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是永真【定理】(范式存在定理)任意命題公式都存在與之等值的析取范式求一個(gè)公式的范式的步驟如下：[1].利用蘊(yùn)涵等值式(AB)(AB)和等價(jià)等值式(AB)(AB)(AB)消除公式中的聯(lián)結(jié)詞和，使得公式中只含有聯(lián)結(jié)詞、和。[2].利用雙重否定律AA和德摩爾根律將否定放到命題符號(hào)前。[3].利用分配律，求析取范式利用對(duì)的分配律，求合取范式則利【例子】求命題公式的析取范式和合取范式(1).求(pq)(pr)的析取范式和合取范式(2).求(pq)(pr)的析取范式和合取范式(pq)(pr)(pq)(pr)求(pq)(pr)的主析取范式(2).求(pq)(pr)的主析取范式【解答】(1)根據(jù)例子知(pq)(pr)的一個(gè)析取范式是(pr)(qp)(qr)，我們將其中的每個(gè)簡(jiǎn)單合取式展開為含有所有命題變?cè)臉O小項(xiàng)的析(pr)展開為(pqr)(pqr)(qp)展開為(pqr)(pqr)(qr)展開為(pqr)(pqr)因此(pq)(pr)的主析取范式為(pqr)(pqr)(pqr)(pqr)，按極小項(xiàng)所對(duì)應(yīng)的二進(jìn)制數(shù)的大小重新排列為(pqr)(pqr)(pqr)(pqr)。(2)根據(jù)例子知(pq)(pr)的一個(gè)析取范式為(p)q(pr)，將其中每個(gè)簡(jiǎn)單合取式展開為含有所有命題變?cè)臉O小項(xiàng)的析取：(p)展開為(pqr)(pqr)(pqr)(pqr)rpqrprpqrpqr此(pq)(pr)的主析取范式為：(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)主析取范式也可從命題公式的真值表更容易地得到，對(duì)應(yīng)地，根據(jù)命題公式的主析取范式也可容易地構(gòu)造其真值表、判定其類型(矛盾式、可滿足式還是永真式)等。關(guān)于極大項(xiàng)、主合取范式等有關(guān)內(nèi)容學(xué)生根據(jù)教材自學(xué)。7.命題演算系統(tǒng)命題演算系統(tǒng)是研究利用命題邏輯公式進(jìn)行推理的形式系統(tǒng)。這里的推理指的是前提和結(jié)論之間的邏輯關(guān)系，因此這種形式系統(tǒng)本身不注重前提本身的正確性，而關(guān)心的是是否能從前提有效地推出結(jié)論，討論什么是結(jié)論的有效證明。前提本身的正確性要在賦予形式系統(tǒng)一定的解釋的基礎(chǔ)上才能確定，這種解釋可以說(shuō)是形式系統(tǒng)的語(yǔ)義。命題演算系統(tǒng)作為一個(gè)形式系統(tǒng)研究如何從公理，通過有限的規(guī)則來(lái)構(gòu)造有效的證明，這種證明僅僅是符號(hào)的改寫，本身沒有什么含義。一個(gè)形式系統(tǒng)包括符號(hào)表、公式、公理及規(guī)則，符號(hào)表定義形式系統(tǒng)所使用的所有符號(hào)，公式是符號(hào)表上字符串，公式定義哪些字符串是形式系統(tǒng)所研究的合法對(duì)象。公理是構(gòu)造一切證明的前提，公理本身的正確性在形式系統(tǒng)中不關(guān)心，認(rèn)為是不證自明的公式。當(dāng)然在構(gòu)造形式系統(tǒng)的時(shí)候，公理的選擇是一定的外在依據(jù)的。規(guī)則是從公理出發(fā)構(gòu)造形式系統(tǒng)中定理的方法。定理就是從公理出發(fā)，使用規(guī)則能夠構(gòu)造出有效證明的公式，形式系統(tǒng)就是研究能夠得到什么定理。1.P的符號(hào)表包括：[1].命題變?cè)盒懹⑽淖帜覆⒖杉酉聵?biāo)2.P的公式歸納定義為：[1].命題變?cè)枪紸則(A)也是公式[4].所有公式都是通過有限次使用[1]、[2]和[3]得到。3.P的公理有如下三類：4.P的規(guī)則只有一條：[M].分離規(guī)則：由A和(AB)可得到B【注解】關(guān)于以上定義，需要注意以下幾點(diǎn)：失去了使用另外三個(gè)聯(lián)結(jié)詞、和的方便之處，為此可作如下約定，對(duì)于P(AB)代表((A)B)(AB)代表(((A)(B)))(AB)代表((AB)(BA))注意，、和不是系統(tǒng)P的符號(hào)，只不過是為了使用方便而引入的符2.上述給出的公理是一種模式，其中每一條公理實(shí)際上代表了無(wú)限多個(gè)公式，因?yàn)槠渲械腁,B,C是一個(gè)符號(hào)，實(shí)際上可代表任意的(((BC)(BC))(((BC)B)((BC)C))C。同樣分離規(guī)則也是一個(gè)模式。AA,A12n使得對(duì)每個(gè)i(1in)，下列兩個(gè)條件之一成立：(1).Ai是公理，或者(2).A是由上述序列中A之前的某兩個(gè)公式A,A(1j,kn)應(yīng)iijk用分離規(guī)則(M)得到。此時(shí)A,A,…,A稱為A的一個(gè)證明，而A稱為P的一個(gè)內(nèi)定理，記為12nnnn【注解】關(guān)于以上定義，需要注意以下幾點(diǎn)：nnAAM是指{A,A}jkjkjjijkkki12nnii【證明】(A(BA))((AB)(AA))A((BA)A)├├├(A((BA)A))((A(BA))(AA))若[2].若├AB，且├BC，則├AC(A(BC))((AB)(AC))├├├├├AA可靈活地使用公理，公理中的每個(gè)符號(hào)代表的是無(wú)限多的公式，公理中某個(gè)符號(hào)的所有出現(xiàn)可用某個(gè)公式替換。但這與教材p43頁(yè)的置換規(guī)則不同，教材沒有為命題邏輯公式的推理建立形式系統(tǒng)，而是根據(jù)命題邏輯公式的真值來(lái)討論推理，因此有所謂的等值公式的置換，而我們這里所定義的形式系統(tǒng)還沒有涉及到真值賦值，這里的證明僅僅是符號(hào)的改寫。建立形式系統(tǒng)的方法更符合計(jì)算機(jī)的思維方式，因?yàn)槌绦驈谋举|(zhì)來(lái)說(shuō)也是個(gè)形式系統(tǒng)，計(jì)算機(jī)將輸入變換到輸出也只是符號(hào)的改寫，至于程序員所認(rèn)為的程序功能，是程序員賦予程序的解釋，這種解釋計(jì)算機(jī)并不理解。也就是說(shuō)，對(duì)于計(jì)算機(jī)學(xué)科，形式系統(tǒng)的推導(dǎo)和形式系統(tǒng)的含義是分開的，正是這種分離，才使得形式系統(tǒng)的推導(dǎo)可由計(jì)算機(jī)來(lái)機(jī)械地完成，而人們又可以賦予形式系統(tǒng)各種各樣的解釋來(lái)完成人們所需要2.可使用分離規(guī)則和傳遞規(guī)則來(lái)構(gòu)造證明。3.可使用已經(jīng)證明過的內(nèi)定理作為前提，這相當(dāng)于教材p43頁(yè)的結(jié)論4.教材中所討論的推理是在某種前提下的推理，下面我們?cè)诿}演算AA,A12n為前提下推出A的一個(gè)證明，如果對(duì)每個(gè)i(1in)，下列三個(gè)條件之一n(1).A是公理，或者i(2).Ai，或者(3).A是由上述序列中A之前的某兩個(gè)公式A,A(1j,kn)應(yīng)iijk用分離規(guī)則(M)得到。此時(shí)記為├A。n【注解】對(duì)于上述定義，我們需要注意以下幾點(diǎn)：以說(shuō)是假設(shè)的前提，在前提下的證明實(shí)際上是將中的公式當(dāng)作“臨時(shí)公一個(gè)證明。A。【證明】AA(BA)(B(AC))((BA)(BC))ABAABB(B)BBB(BC)CABABABBBCBAAB├ABA(BA)(B(AB))B(AB)BA(BA)(B(AB)))BABABB)CBABACABBBAABBAAAAABBBDABDCBDACBD(A(A(AA)))((AA)(A(AA)))A(AA)A(A(AA))((AA)(A(AA)))AAAABA最后我們來(lái)討論命題演算系統(tǒng)的元問題，即該形式系統(tǒng)的可靠性、一致性和完備性。可靠性是指命題演算系統(tǒng)P中的內(nèi)定理是否都是永真A性是指P是否能推出命題邏輯公式的所有永真式。下面定理說(shuō)明P是可靠的、一致的和完備的。□□有了定理之后，要看一個(gè)公式A是否是內(nèi)定理，只要使用真值表的方法檢查A是否是永真式即可。定理表明我們?cè)谶@里構(gòu)造的形式系統(tǒng)與教材中的推理理論是完全一致的，但正如前面所指出的，形式系統(tǒng)的構(gòu)造才是計(jì)算機(jī)學(xué)科的核心思想。關(guān)于命題邏輯的推理理論的實(shí)際應(yīng)用關(guān)鍵在于將實(shí)際中的陳述句符號(hào)化，具體的例子請(qǐng)讀者自己參考教材。7.命題邏輯的推理理論命題邏輯的推理理論就是利用命題邏輯公式研究什么是有效的推理。推理是從前提出發(fā)推出結(jié)論的思維過程，前提是已知的命題公式，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。如果前提是真命題，從前提出發(fā)推出結(jié)論的推理過程嚴(yán)格遵守推理規(guī)則，則推出的結(jié)論也是真命題。在命題邏輯中，不注重前提和結(jié)論的真假性，而關(guān)心從前提推出結(jié)論的推理過程的正確性，即主要研究推理的規(guī)則。AAAB為推理的形式結(jié)構(gòu)，A,A,…,A為12k12k推理的前提，B為推理的結(jié)論。若(AA…A)B為永真式，則稱從前提A,12k12k12A2k12邏輯結(jié)論或稱有效結(jié)論，否則稱推理不正確。若從前提A,A,…,A推12k出結(jié)論B的推理正確，則記為(AA…A)B。12k12k12k判斷推理是否正確就是驗(yàn)證相應(yīng)的蘊(yùn)涵式是否是永真式，其方法包【例子】教材p39例，要點(diǎn)：將各種命題符號(hào)化，然后使用上述各種方法判斷相應(yīng)的蘊(yùn)涵式是否是永真式。【定義】證明是一個(gè)描述推理過程的命題公式序列A,A,…,A，12n其中的每個(gè)命題公式或者是已知的前提，或者是由某些前提應(yīng)用推理規(guī)則得到的結(jié)論，滿足這樣條件的公式序列A,A,…,A稱為結(jié)論A的證12nn[1].前提引入規(guī)則：在證明的任何步驟都可以引入已知的前提；[2].結(jié)論引入規(guī)則：在證明的任何步驟都可以引入這次已經(jīng)得到[3].置換規(guī)則：在證明的任何步驟上，命題公式中的任何子公式都可用與之等值的公式置換，得到證明的公式序列的另一公式。使用命題邏輯公式進(jìn)行推理還有其他一些推理規(guī)則，這些規(guī)則建立面一些推理定律上：【定理】推理定律是命題邏輯的一些永真蘊(yùn)涵式，重要的推理定律AAB化簡(jiǎn)律：ABBABAB[6].假言三段論：(AB)(BC)(AC)等價(jià)三段論：(AB)(BC)(AC)[8].構(gòu)造性二難：(AB)(CD)(AC)(BD)【注解】1.這些推理定律都是永真式，可用判斷命題公式是否是永真式的方法2.這些推理定律之間不是獨(dú)立的，其中一些定律可從另外一些定律推出，正如我們?cè)诿}演算系統(tǒng)中所討論的，最基本的定律應(yīng)該命題演算的公理及分離規(guī)則。對(duì)于上面給出的這些定律，最重要的是附加律、分離規(guī)則、傳遞規(guī)則、拒取式等。正如教材p44的例所證明的，構(gòu)造性二難規(guī)則可使用傳遞規(guī)則、置換規(guī)則等證明。而拒取式與析取三段論實(shí)際上等價(jià)，因?yàn)?AB)(AB)，那么根據(jù)拒取式有(AB)BA，而AA。定律中某個(gè)符號(hào)的所有出現(xiàn)用另外一個(gè)命題公式代入，那么得到的也是永真式，這個(gè)規(guī)則可稱為代入規(guī)則。注意代入規(guī)則與置換規(guī)則不同。【定理】根據(jù)定理的推理定律得到，在證明中可使用以下一些推理[1].假言推理規(guī)則(分離規(guī)則)：若有AB和A，則可得到B。 (注意證明是命題公式的序列，因此這里的意思是，如果序列中出現(xiàn)AB和A，則可在該序列中添加公式B，或換句話，按照證明的意思就是，如[2].附加規(guī)則：若有A，則可得到AB。B[5].假言三段論(傳遞規(guī)則)：若有AB及BC，則可得到AC【注解】1.假言推理規(guī)則就是最常用的推理方法，例如，如果天下雨(A)，地就是濕的(B)，現(xiàn)在天下雨，所以地是濕的。2.附加規(guī)則、化簡(jiǎn)規(guī)則及合取引入規(guī)則的直觀含義很簡(jiǎn)單。3.拒取式規(guī)則就是通常所使用的反證法，即從A可推出B，但立的。例如，如果天下雨地就是濕的(AB)，但現(xiàn)在地沒有濕(B)，所以天沒有下雨(A)。4.假言三段論表明推理的傳遞性，也是常用的一種三段論(亞里斯多德的《工具論》中共總結(jié)出24中三段論的形式)，例如，如果天下雨(A)，路就會(huì)很難走(B)，路很難走，我上學(xué)就會(huì)遲到(C)，所以如果天下雨我上學(xué)就會(huì)遲到。5.析取三段論本質(zhì)上與拒取式一致，但在邏輯上通常稱為選言推理，或者更通俗地稱為排除法，例如，今天我要么去開會(huì)(A)要么去上課(B)，我不去上課(B)，所以我去開會(huì)(A)。實(shí)際上這里假定前提AB已羅列了所有可能情況，因?yàn)檫@只是一種推理模式，因此這種假定是合理的，具有一般性。6.構(gòu)造性二難推理是析取三段論的推廣，例如如果派小王參加比賽(A)我們就可得到第一名(B)，如果派小張參加比賽(C)就可得到第三名(D)，我們要么派小王去比賽，要么派小張去比賽，所以我們不是得到第一名就是得到第三名。一種極端的二難推理形式是，有AB和AB，那么BAA永真的。【例子】教材p44例，該例子的前提和結(jié)論都是符號(hào)化的命題公式。如何從前提構(gòu)造地證明結(jié)論沒有固定的程式，這里也很難從結(jié)論到推到前提，需要敏銳的直覺和豐富的經(jīng)驗(yàn)。p12k12k利用演繹定理，許多命題公式，特別是蘊(yùn)涵式的證明可得到簡(jiǎn)化，我們可將蘊(yùn)涵式的前件作為前提引入來(lái)進(jìn)行證明。【例子】教材p46例，該例子需要先將命題符號(hào)化，要證明的結(jié)論是一個(gè)蘊(yùn)涵式，可將蘊(yùn)涵式的前件作為已知的前提來(lái)構(gòu)造蘊(yùn)涵式的后件的【例子】驗(yàn)證下述推理是否正確：或者邏輯學(xué)難學(xué)，或者有少數(shù)學(xué)生不喜歡它；如果數(shù)學(xué)容易學(xué)，那么邏輯學(xué)并不難學(xué)。因此如果許多學(xué)生喜歡邏輯，那么數(shù)學(xué)并不難學(xué)。【解答】先將命題符號(hào)化，首先抽取的基本命題包括：A:邏輯學(xué)難學(xué)B:有少數(shù)學(xué)生不喜歡邏輯學(xué)數(shù)學(xué)容易學(xué)則前提是AB，CA，要證明的結(jié)論是BC，可進(jìn)行如下的驗(yàn)證：(1).BACDABBC概述ABAD1111ABC·一階邏輯討論的內(nèi)容與命題邏輯類似，一階邏輯又稱為謂詞邏輯·為什么要引入一階邏輯因?yàn)楹?jiǎn)單命題需要進(jìn)一步分析，才能更好地反映現(xiàn)實(shí)世界中人們所使用的推理模式。·一階邏輯的基本概念：個(gè)體、函數(shù)、謂詞、量詞，在一階邏輯中·一階邏輯公式及其解釋(賦值)公式的等值演算與范式·一階邏輯公式的推理理論：使用一階邏輯公式進(jìn)行推理。2.一階邏輯的基本概念命題邏輯中，命題是最基本的單位，不再分解，不再考慮命題內(nèi)部各成份之間的關(guān)系，這樣忽略了命題本身的豐富內(nèi)含，使得有些直覺上很正確的推理在命題邏輯中無(wú)法描述。【定義】一階邏輯中，命題被分解為個(gè)體和謂詞兩部分。個(gè)體individuals存在的客體，可以是一個(gè)具體的事物，也可以抽象的概念。而謂詞(predication)是用來(lái)刻劃個(gè)體詞的性質(zhì)及事【注解】1.一階邏輯建立在命題邏輯之上，當(dāng)命題邏輯中的命題具有豐富的內(nèi)含時(shí)，需要一階邏輯公式來(lái)符號(hào)化它。2.命題是陳述句，在自然語(yǔ)言中，通常陳述句有主語(yǔ)、謂語(yǔ)和賓語(yǔ)，主語(yǔ)和賓語(yǔ)都可能是個(gè)體，而謂語(yǔ)及其相連的賓語(yǔ)通常被看成是謂詞。(參考書中的例子)3.在一階邏輯中還可描述對(duì)個(gè)體所進(jìn)行的某種變換，即引入所的平方是非負(fù)數(shù)其中是一個(gè)體，的平方也是一個(gè)體，它通過對(duì)做某種操作(變換)而得到，為了刻劃這種變換，引入所謂函詞的概念。4.函詞與謂詞不同，函詞作用在個(gè)體上，而產(chǎn)生另一個(gè)個(gè)體，而謂詞作用在個(gè)體上之后產(chǎn)生的是一個(gè)命題。例如上面命題中，“…的平方”是函詞，而“…是非負(fù)數(shù)”則是一個(gè)謂詞。“的平方”是一個(gè)體，而“的平方是非負(fù)數(shù)”則是一個(gè)命題。5.所謂的個(gè)體常項(xiàng)是表示具體或特定的個(gè)體的個(gè)體詞，而個(gè)體變項(xiàng)是表示抽象或泛指的個(gè)體詞。個(gè)體變項(xiàng)的取值范圍稱為個(gè)體域，后面看到當(dāng)個(gè)體域不同時(shí)，一階邏輯公式的含義不同。為了使公式有一致的含義，可引入一個(gè)全總域，表示宇宙間所有個(gè)體所組成的域。在某些情況下，全總域也可指所討論的問題范圍內(nèi)的所有個(gè)體。6.表示具體性質(zhì)或關(guān)系的詞稱為謂詞常項(xiàng)，表示抽象性質(zhì)或關(guān)系的詞稱為謂詞變項(xiàng)。7.在一階邏輯中，謂詞變項(xiàng)和謂詞常項(xiàng)的區(qū)別并不重要，正如在命題邏輯中，命題常項(xiàng)和命題變項(xiàng)的區(qū)別不重要一樣，這是因?yàn)樵谝浑A邏輯中不能對(duì)謂詞做某些變換(操作)，或者說(shuō)在一階邏輯上不能在謂詞集合上定義函數(shù)。但在個(gè)體域上可定義函數(shù)，因此個(gè)體常項(xiàng)與個(gè)體變項(xiàng)的區(qū)別顯得比較重要。8.實(shí)際上，所謂一階邏輯的“一階”的含義就是指其中的函數(shù)只能作用在個(gè)體上，或者說(shuō)其中的變量只能代表取值于個(gè)體，如果允許函數(shù)作用在謂詞上，則變成二階或高階(進(jìn)一步允許函數(shù)作用在函數(shù)本身上)邏輯。9.可以說(shuō)，一階邏輯一個(gè)很重要的特點(diǎn)是在個(gè)體域上引入了變量。個(gè)體變量既可作為謂詞作用的對(duì)象也可作為函數(shù)作用的對(duì)象。一階邏輯中的階的含義在某種意義上是指?jìng)€(gè)體處于0階，而對(duì)個(gè)體的判斷 (即命題)處于一階，一階邏輯中的函數(shù)作用于0階的個(gè)體而得到個(gè)體，而謂詞作用于個(gè)體得到處于一階的命題。10.謂詞可包含的個(gè)體變項(xiàng)個(gè)數(shù)稱為謂詞的元數(shù)，例如“…是非負(fù)數(shù)”是一元謂詞，而“…和…是好朋友”是二元謂詞。通常來(lái)說(shuō)，二元以上的謂詞比較少見，而且通常可用二元謂詞來(lái)表示。【例子】分析命題中的個(gè)體和謂詞，并將命題在一階邏輯中符號(hào)化：教材例【定義】在一階邏輯中用量詞(quantifier)來(lái)刻劃參與判斷的個(gè)體的數(shù)量。對(duì)于謂詞所作用的個(gè)體數(shù)量，一階邏輯只關(guān)心兩種情況，一種情況是謂詞作用個(gè)體域中所有的個(gè)體，這時(shí)用全稱量詞(universalquantifier)(使用符號(hào)'')來(lái)刻劃，一種情況是謂詞作用個(gè)體域中某些個(gè)體，這時(shí)用存在量詞(existentialquantifie)r(使用符號(hào)'')來(lái)刻劃。【注解】1.一階邏輯中，不關(guān)心個(gè)體的具體數(shù)量，而只關(guān)心謂詞是作用于個(gè)體域中的所有個(gè)體，還是某些個(gè)體。顯然如果謂詞不作用于個(gè)體域中任何個(gè)體，則可用存在量詞再加上否定來(lái)表示。2.在一階邏輯中量詞只限制被謂詞所作用的個(gè)體的數(shù)量，它不限制被函數(shù)作用的個(gè)體數(shù)量，實(shí)際上函數(shù)總是存在自己的定義域和值域，它可作用域在定義域中的任意個(gè)體。3.量詞與個(gè)體域總是聯(lián)系在一起的，因此使用不同的個(gè)體域，同一命題可能在一階邏輯中有不同的符號(hào)化形式，但總可使所有的個(gè)體變量的個(gè)體域?yàn)槿傆颍⑼ㄟ^引入合適的特性謂詞來(lái)從全總域中分離出可使用量詞限制的合適個(gè)體域來(lái)。教材p70頁(yè)的例子。注意所謂全總域，有時(shí)可認(rèn)為討論范圍內(nèi)的所有個(gè)體所組成的集合。4.量詞是有順序的，不能將量詞的順序隨意顛倒。教材p71頁(yè)的說(shuō)明。實(shí)際上，謂詞中的個(gè)體變項(xiàng)也是有順序的，例如“…比…跑得【例子】在一階邏輯中將命題符號(hào)化，教材例、例、例、例【例子】將下列命題符號(hào)化：[1].凡是有理數(shù)都可寫成分?jǐn)?shù)[2].教室里有同學(xué)在講話[4].在我們班中，并非所有同學(xué)都能取得優(yōu)秀成績(jī)[5].有一個(gè)整數(shù)大于其他每個(gè)整數(shù)[6].任給>0，存在>0，如果|x-a|<，則|f(x)-b|<【解答】注意不是(x)(Q(x)F(x))，更不是((x)Q(x))F(x)注意不是(x)(S(x)T(x))，更不是S(x)(x)(T(x))xyzxyz(u)((u=x+y)(u=z)))此命題與“我們班中存在不能取得優(yōu)秀成績(jī)的同學(xué)”等價(jià)，該命題由此可知((x)(C(x)E(x)))和(x)(C(x)E(x))等值，即全稱量詞和存在量詞存在某種等值變換關(guān)系。(x)(Z(x)(y)(Z(y)(x>y)))[6].符號(hào)化為：()((>0)()((>0)((|x-a|<)(f(x)-b|<))))【例子】將下列命題符號(hào)化：[1].每一個(gè)有理數(shù)都是實(shí)數(shù)[2].某些實(shí)數(shù)是有理數(shù)[3].不是沒一個(gè)實(shí)數(shù)都是有理數(shù)[4].存在偶素?cái)?shù)[5].會(huì)叫的狗未必會(huì)咬人[6].每個(gè)人的外祖母都是他母親的母親[7].任何自然數(shù)的后繼數(shù)必大于零[8].有些液體能溶解任何金屬[9].任何金屬均可溶解于某種液體中【解答】(請(qǐng)同學(xué)們下載后，先思考，課堂上講解)【例子】將下列公式翻譯成自然語(yǔ)言，并確定其真值，這里假定個(gè)體【解答】(請(qǐng)同學(xué)們下載后，先思考，課堂上講解)【例子】給定下述謂詞，請(qǐng)把下列公式翻譯成自然語(yǔ)言：[1].P(5)[2].E(2)P(2)【解答】(請(qǐng)同學(xué)們下載后，先思考，課堂上講解)3.一階邏輯公式及解釋每個(gè)系統(tǒng)有它自己的符號(hào)表，由這些符號(hào)表所構(gòu)成的某些符號(hào)串是該系統(tǒng)中的語(yǔ)言，也是我們所研究的目標(biāo)語(yǔ)言。【定義】一階邏輯語(yǔ)言的符號(hào)包括：[1].個(gè)體常項(xiàng)：通常用排在前面的小寫字母表示，a,b,c,…,iii[2].個(gè)體變項(xiàng)：通常用排在后面的小寫字母表示，x,y,z,…,iii[3].函數(shù)符號(hào)：通常用排在中間的小寫字母表示，f,g,h,…,iii[4].謂詞符號(hào)：通常用排在中間的大寫字母表示，F(xiàn),G,H,…,iii[5].量詞符號(hào)：全稱量詞、存在量詞[6].聯(lián)結(jié)符號(hào)：、、、、【注解】1.上述符號(hào)可分為兩大類，一類是非邏輯符號(hào)，包括個(gè)體常項(xiàng)、函數(shù)符號(hào)、謂詞符號(hào)等，一類是邏輯符號(hào)，包括個(gè)體變項(xiàng)、量詞符號(hào)、聯(lián)結(jié)符號(hào)、輔助符號(hào)等。2.在命題邏輯只有邏輯符號(hào)，而沒有任何非邏輯符號(hào)，命題邏輯中的命題常項(xiàng)和命題變量的區(qū)分是非本質(zhì)的，對(duì)于命題邏輯本身來(lái)說(shuō)沒有什么意義，正如在一階邏輯中，謂詞常項(xiàng)和謂詞變項(xiàng)的區(qū)分也是非本質(zhì)的，對(duì)于一階邏輯來(lái)說(shuō)沒有什么意義，但個(gè)體常項(xiàng)和個(gè)體變項(xiàng)的區(qū)分是本質(zhì)的，對(duì)于一階邏輯來(lái)說(shuō)有重要的意義。3.一階邏輯中的邏輯符號(hào)對(duì)于將一階邏輯應(yīng)用于任何問題時(shí)都是通用的、不變的，而其中的非邏輯符號(hào)則在不同的應(yīng)用問題(或者說(shuō)不同的討論范圍)中有所不同，可以變化，因此一階邏輯語(yǔ)言的表達(dá)能力是非常強(qiáng)的，它可通過采用不同的非邏輯符號(hào)來(lái)增強(qiáng)自己的表達(dá)能力。【定義】一階邏輯語(yǔ)言的項(xiàng)(term)遞歸定義為：[1].個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)；12n12n12n[3].一階邏輯語(yǔ)言的所有項(xiàng)都通過有限次使用上述兩步生成。【定義】一階邏輯語(yǔ)言的合式公式(well-formedformul遞歸定義12n12n12n[4].一階邏輯語(yǔ)言的所有公式都通過有限次使用上述步驟生成。ABiiiiii【注解】1.一階邏輯語(yǔ)言的合式公式隨著采用不同的非邏輯符號(hào)而不同，但對(duì)于不同的非邏輯符號(hào)采用相同的方式構(gòu)造公式，一旦非邏輯符號(hào)確定之后，則一階邏輯公式也就確定下來(lái)了，所以可以說(shuō)一階邏輯公式是某個(gè)非邏輯符號(hào)集生成的語(yǔ)言。2.雖然說(shuō)采用不同的非邏輯符號(hào)可生成不同的一階邏輯公式，但所有一階邏輯公式的邏輯符號(hào)是相同的，而我們?cè)谶@里對(duì)一階邏輯的討論只是討論這些邏輯符號(hào)的性質(zhì)，而與非邏輯符號(hào)無(wú)關(guān)，則我們的討論對(duì)于任意的非邏輯符號(hào)生成的一階邏輯公式都是成立的。3.一階邏輯語(yǔ)言的直觀意義容易理解：“符號(hào)表”相當(dāng)于英語(yǔ)的字母表，“項(xiàng)”相當(dāng)于單詞或詞組，它們不表達(dá)完整的判斷，還只是代表個(gè)體，而“公式”則代表完整的句子。而其中的函數(shù)符號(hào)用來(lái)構(gòu)造復(fù)雜的個(gè)體(項(xiàng))，謂詞符號(hào)則用來(lái)構(gòu)造最原子的公式。4.在定義的[4]中，沒有要求個(gè)體變項(xiàng)x一定要出現(xiàn)在合式公式A5.可通過假設(shè)聯(lián)結(jié)符號(hào)及量詞之間的優(yōu)先級(jí)而去掉一些括號(hào)，使得公式的書寫更為簡(jiǎn)潔，約定：(1).公式的最外層括號(hào)可省略；F(x,y)Q(y,z)F(y,z)G(y,x)Q(x,z)F(y,z)表示：(((((F(x,y))Q(y,z))(F(y,z)))G(y,x))(Q(x,z)F(y,z)))，但通常在書寫時(shí)也不可將所有的括號(hào)省略，應(yīng)該既比較簡(jiǎn)潔，又比較容易理解，例如上述公式可寫成：((F(x,y)Q(y,z)F(y,z))G(y,x))(Q(x,z)F(y,z))由于一階邏輯語(yǔ)言的公式比較復(fù)雜，其中的括號(hào)比較多，請(qǐng)注意講究書12n-1n12n-1nxAx)A可分別寫成xA、xA，但要注意明確量詞的轄域(下面定義什么是轄域)。如果該出現(xiàn)處于量詞(x)或(x)的轄域內(nèi)，或者就是量詞中的x。若x在公A出現(xiàn)稱為自由出現(xiàn)。元的自由出現(xiàn)和約束出現(xiàn)：[1].x(F(x,y,z)yG(x,y))[2].xF(x,y)G(x,y)[3].xy(F(x)G(y)H(x,y))【解答】Gxy分別為：x(F(x,y,z)yG(x,y))約束約束自由自由約束約束約束xF(x,y)G(x,y)約束約束自由自由自由(F(x)G(y)H(x,y))。變?cè)淖杂沙霈F(xiàn)和約束出現(xiàn)分別為：xy(F(x)G(y)H(x,y))約束約束約束約束約束約束A【注解】1.變?cè)獂在公式A中可同時(shí)有約束出現(xiàn)和自由出現(xiàn)兩種情況，2.為了明確起見，我們通常在用字母A,B,C,…表示一階邏12n12n3.為了清晰起見，通常運(yùn)用換名規(guī)則和替換規(guī)則使得公式A滿(1).所有變?cè)诠紸中要么自由出現(xiàn)，要么約束出現(xiàn)，不要既有自由出現(xiàn)，又有約束出現(xiàn)。(2).所有量詞后面采用的約束變?cè)ゲ幌嗤Ａ吭~后面的約束變?cè)辉谒妮犛蚶镉幸饬x，處于其轄域以外的同名變?cè)c該約束變?cè)獙?shí)際上無(wú)關(guān)。所以不同量詞采用不同約束變?cè)强梢缘模乙彩潜匾摹＿M(jìn)一步變?cè)妮犛驅(qū)嶋H上是可嵌套的，例如對(duì)于公式：x(F(x)x(G(x)F(x)))x(F(x)y(G(y)F(y)))在使用一階邏輯公式符號(hào)化命題時(shí)，要小心地選擇變?cè)允沟玫降墓綕M足上述兩個(gè)條件。【定理】約束變?cè)獡Q名規(guī)則和自由變?cè)鎿Q規(guī)則：].替換規(guī)則：對(duì)于公式A(x)，設(shè)y不在A中出現(xiàn)，將其中所有【注解】1.這里的等價(jià)于后面要講的等值(目前可參考命題邏輯公式的等值)不一樣，等值建立在某種解釋下，而這里的等價(jià)只與語(yǔ)法有關(guān)，換名規(guī)則和替換規(guī)則只是在某種意義上說(shuō)明公式中使用的變?cè)强扇我膺x擇