數(shù)理邏輯的推理及形式證明

修數(shù)理邏輯的推理及形式證明-CAL-FENGHAI.NetworkInformationTechnologyCompany.2020YEAR第一講引言一、課程內(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ǎng)數(shù)學(xué)思維，將以前學(xué)過的知識(shí)系統(tǒng)化、形式化和抽象化。熟練掌握有關(guān)代數(shù)系統(tǒng)的基本概念，以及群、環(huán)、域等代數(shù)結(jié)構(gòu)的基本知識(shí)。圖論：對(duì)于解決許多實(shí)際問題很有用處，對(duì)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、編譯原理課程也很有幫助。要求掌握有關(guān)圖、樹的基本概念，以及如何將圖論用于實(shí)際問題的解決，并培養(yǎng)其使用數(shù)學(xué)工具建立模型的思維方式。講課時(shí)間為兩個(gè)學(xué)期，第一學(xué)期講授數(shù)理邏輯與集合論，第二學(xué)期講授代數(shù)結(jié)構(gòu)和圖論?？荚噧?nèi)容限于書中的內(nèi)容和難度，但講課內(nèi)容不限于書中的內(nèi)容和難度。二、數(shù)理邏輯發(fā)展史目的?了解有關(guān)的背景，加深對(duì)計(jì)算機(jī)學(xué)科的全面了解，特別是理論方面的了解，而不限于將計(jì)算機(jī)看成是一門技術(shù)或工程性的學(xué)科。?通過重要的歷史事件，了解計(jì)算機(jī)科學(xué)中的一些基本思維方式和一些基本問題。數(shù)理邏輯的發(fā)展前期前史時(shí)期一一古典形式邏輯時(shí)期：亞里斯多德的直言三段論理論初創(chuàng)時(shí)期一一邏輯代數(shù)時(shí)期(17世紀(jì)末)資本主義生產(chǎn)力大發(fā)展，自然科學(xué)取得了長(zhǎng)足的進(jìn)步，數(shù)學(xué)在認(rèn)識(shí)自然、發(fā)展技術(shù)方面起到了相當(dāng)重要的作用。人們希望使用數(shù)學(xué)的方法來研究思維，把思維過程轉(zhuǎn)換為數(shù)學(xué)的計(jì)算。萊布尼茲(Leibniz,1646~1716)完善三段論，提出了建立數(shù)理邏輯或者說理性演算的思想：?提出將推理的正確性化歸于計(jì)算，這種演算能使人們的推理不依賴于對(duì)推理過程中的命題的含義內(nèi)容的思考，將推理的規(guī)則變?yōu)檠菟愕囊?guī)則。?使用一種符號(hào)語言來代替自然語言對(duì)演算進(jìn)行描述，將符號(hào)的形式和其含義分開。使得演算從很大程度上取決與符號(hào)的組合規(guī)律，而與其含義無關(guān)。布爾(G.Boole,1815~1864)代數(shù)：將有關(guān)數(shù)學(xué)運(yùn)算的研究的代數(shù)系統(tǒng)推廣到邏輯領(lǐng)域，布爾代數(shù)既是一種代數(shù)系統(tǒng)，也是一種邏輯演算。數(shù)理邏輯的奠基時(shí)期弗雷格(G.Frege,1848~1925)：《概念語言一一一種按算術(shù)的公式語言構(gòu)成的純思維公式語言》(1879)的出版標(biāo)志著數(shù)理邏輯的基礎(chǔ)部分一一命題演算和謂詞演算的正式建立。皮亞諾(GiuseppePeano,1858~1932)：《用一種新的方法陳述的算術(shù)原理》(1889)提出了自然數(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ù))中的主要概念和定理。邏輯演算的發(fā)展：甘岑(G.仃6也6川的自然推理系統(tǒng)(NaturalDeductionSystem),邏輯演算的元理論：公理的獨(dú)立性、一致性、完全性等。各種各樣的非經(jīng)典邏輯的發(fā)展：路易斯(Lewis,1883~1964)的模態(tài)邏輯，實(shí)質(zhì)蘊(yùn)涵怪論和嚴(yán)格蘊(yùn)涵、相干邏輯等，盧卡西維茨的多值邏輯等。集合論的發(fā)展?看待無窮集合的兩種觀點(diǎn)：實(shí)無窮與潛無窮?康托爾(G.Cantor,1845~1918)：以實(shí)無窮的思想為指導(dǎo)，建立了樸素集合論?外延原則(集合由它的元素決定)和概括原則(每一性質(zhì)產(chǎn)生一集合)。?可數(shù)集和不可數(shù)集，確定無窮集合的本質(zhì)在于集合本身能與其子集一一對(duì)應(yīng)。能與正整數(shù)集合對(duì)應(yīng)的集合是可數(shù)的，否則是不可數(shù)的。證明了有理數(shù)集是可數(shù)的，使用對(duì)角線法證明了實(shí)數(shù)集合是不可數(shù)的。超窮基數(shù)和超窮序數(shù)樸素集合論的悖論：羅素悖論公理集合論的建立：ZFC系統(tǒng)第三次數(shù)學(xué)危機(jī)與邏輯主義、直覺主義與形式主義集合論的悖論使得人們覺得數(shù)學(xué)產(chǎn)生了第三次危機(jī)，提出了數(shù)學(xué)的基礎(chǔ)到底是什么這樣的問題。羅素等的邏輯主義：數(shù)學(xué)的基礎(chǔ)是邏輯，倡導(dǎo)一切數(shù)學(xué)可從邏輯符號(hào)推出，《數(shù)學(xué)原理》一書是他們這一思想的體現(xiàn)。為解決悖論產(chǎn)生了邏輯類型論。布勞維爾(Brouwer,1881~1966)的直覺主義：數(shù)學(xué)是心靈的構(gòu)造，只承認(rèn)可構(gòu)造的數(shù)學(xué)，強(qiáng)調(diào)構(gòu)造的能行性，與計(jì)算機(jī)科學(xué)有重要的聯(lián)系。堅(jiān)持潛無窮，強(qiáng)調(diào)排中律不能用于無窮集合。海T(Heyting)的直覺主義邏輯。希爾伯特(D.Hilbert)的形式主義：公理化方法與形式化方法，元數(shù)學(xué)和證明論，提倡將邏輯演算和數(shù)學(xué)證明本身形式化，把用普通的語言傳達(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)。數(shù)理邏輯的發(fā)展初期哥德爾(Godel,1906~1978)不完全性定理：一個(gè)足夠強(qiáng)大的形式系統(tǒng)，如果是一致的則不是完全的，即有的判斷在其中是不可證的，既不能斷定其為假，也不能證明其為真。各種計(jì)算模型：哥德爾的遞歸函數(shù)理論，邱吉爾的演算，圖靈機(jī)模型這些計(jì)算模型是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)，是計(jì)算機(jī)的理論模型。三、預(yù)備知識(shí)集合的基本概念?集合(set):集合是數(shù)學(xué)中最基本的概念之一，不能以更簡(jiǎn)單的概念來定義(define),只能給出它的描述(description)。一些對(duì)象的整體就稱為一個(gè)集合，這個(gè)整體的每個(gè)對(duì)象稱為該集合的一個(gè)元素(member或element)。用大寫字母A,B,C等表示集合，用小寫字母a,b,c等表示集合的元素aA表示：a是集合A的元素，或說a屬于集合AaA表示：a不是集合A的元素，或說a不屬于集合A?集合中的元素是無序的，不重復(fù)的。通常使用兩種方法來給出一個(gè)集合：列元素法：列出某集合的所有元素，如：A={0,1,2,3,4,5,6,7,8,9}表示所有小于10的自然數(shù)所構(gòu)成的集合B={a,b，…,z}表示所有小寫英文字母所構(gòu)成的集合性質(zhì)概括法：使用某個(gè)性質(zhì)來概括集合中的元素，如：?A={n|n是小于10的自然數(shù)}?C={n|n是質(zhì)數(shù)}表示所有質(zhì)數(shù)所構(gòu)成的集合?集合由它的元素所決定，換句話說，兩個(gè)集合A和B相等，記為A=B,如果A和B具有相同的元素，即a屬于集合A當(dāng)且僅當(dāng)a屬于集合B。.子集(subset)：說集合A是集合B的子集，記為A=B,如果a屬于集合A則a也屬于集合B。因此A=B當(dāng)且僅當(dāng)AcB且B=A。說集合A是集合B的真子集(propersubset),如果AcB且A不等于B(A中B)。.空集(emptyset):約定存在一個(gè)沒有任何元素的集合，稱為空集，記為也有時(shí)也用{}來表示。按子集的定義，空集是任何集合的子集(為什么？)。冪集(powerset):集合A的冪集，記為軟A),是A的所有子集所構(gòu)成的集合，即：.P(A)={BIBcA}.例如，A={0,1},則P(A)={{},{0},{1},{0,1}},顯然，對(duì)任意集合A,有人P(A)和AeP(A),補(bǔ)集(complementset):集合A的補(bǔ)集，記為A,是那些不屬于集合A的元素所構(gòu)成的集合，即A={xIxeA}。通常來說，是在存在一個(gè)全集U的情況下討論集合的補(bǔ)集。全集U是所討論的問題域中所有元素所構(gòu)成的集合。,集合的并(union):集合A和B的并AuB定義為：AuB={xIxeA或者xeB},集合的并可推廣到多個(gè)集合，設(shè)A「A2,…，解3是集合，它們的并定義為：A1uA2_uAn={xI存在某個(gè)z?，使得xeA.)?集合的交(in^ersec力on):集合A和B的并AcB定義為：AcB={xIxeA而且xeB},集合的交也可推廣到多個(gè)集合，設(shè)A1,A2,…,An都是集合，它們的交定義為：A〃A2..2An={xI對(duì)所有的?，都有xeA.},集合的差(呦erence):集合A和B的差A(yù)-B定義為：A-B={xIxeA而且xeB}。2. 關(guān)系和函數(shù)的基本概念有序?qū)?orderedpair):設(shè)A和B是兩個(gè)集合，aeA,beB是兩個(gè)元素，a和b的有序?qū)?，記?lt;a,b>，定義為集合{{a},{a,b}}。,設(shè)<a1,%>和<a2,b2>是兩個(gè)有序?qū)?，可以證明<a1,b1>=<a2,b2>當(dāng)且僅當(dāng)a1=a2且b1=b2。(如何證？),有序?qū)赏茝V到n個(gè)元素，設(shè)A1,A2,…,An是集合，a1eA1,a2eA2,…,aneAn是元素，定義有序n元組(。46%2n-tuple)<a1,a2,…，an>為<<a1,a2，??.,an_1>,an>，注意這是一個(gè)歸納(inductive)定義，將有序n元組的定義歸結(jié)為有序n-1元組的定義。,顯然有<a1,a2，…，an>=<b1,b2,…，bn>當(dāng)且僅當(dāng)a1=b1且a2=b2且…且an=b。n,集合的笛卡爾積(cartesianproduct):兩個(gè)集合A和B的笛卡爾積AxB定義為：AxB={<a,b>IaeA且beB},例如，設(shè)A={a,b,c},B={1,2},則：AxB={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}笛卡爾積可推廣到多個(gè)集合的情況，集合A1,A2,…,An的笛卡爾積定義為：A1xA2X…xAn={<a1,a2，…，an>Ia1eA1且a2eA2且…且.eAn},集合之間的關(guān)系(relation):定義n個(gè)集合A1,A2,…,An之間的一個(gè)n元關(guān)系R為集合A1,A2,…，An的笛卡爾積A1xA2x...xAn的一個(gè)子集。設(shè)<a1,a2，…，an>eA1xA2x...xAn，若<a1a2,…,an>eR,則稱a1,a2,…,an間具有關(guān)系R,否則稱它們不具有關(guān)系R。特別地：,當(dāng)A1=A2=…=An=A時(shí)，稱R為A上的n兀關(guān)系。,當(dāng)n=2時(shí)，有口之人1以2,稱R為A1與A2間的一個(gè)二元關(guān)系?naryrelation)。這時(shí)若＜a1,a2＞eR則簡(jiǎn)記為a1Ra2，否則(即＜a1,a2＞任R)記為a1Ra2。通常研究得最多的是二元關(guān)系，n元關(guān)系的許多性質(zhì)可從二元關(guān)系的性質(zhì)擴(kuò)充而得到。如果沒有特別指明的話，說R是一個(gè)關(guān)系則是指R是一個(gè)二元關(guān)系。,當(dāng)n=1時(shí)，這時(shí)可認(rèn)為R是集合A上滿足某種性質(zhì)的子集。,關(guān)系的一些性質(zhì)：設(shè)R是A上的二元關(guān)系：,說R是自反的(re/lexive)，如果對(duì)任意的aeA有aRa。,說R是反自反的(irre/lexive)，如果對(duì)任意的aeA有aRa。,說R是對(duì)稱的(symmetric)，如果對(duì)任意的a,beA有若aRb則bRa。■說R是反對(duì)稱的(antisymmetric)，如果對(duì)任意的a,beA有若aRb且bRa貝1Ja=b。,說R是傳遞的(transitive)，如果對(duì)任意的a,b,ceA有若aRb且bRc則aRco,說R是等價(jià)關(guān)系(equivalence)，如果R是自反的、對(duì)稱的和傳遞的。,集合之間的函數(shù)(/Unction，或說映射mapping):定義集合A到B的函數(shù)f是A和B的笛卡爾積AxB的一個(gè)子集，且滿足若＜x,y＞ef及＜x,z＞ef則y=z。因此函數(shù)是A和B之間的一個(gè)特殊的二元關(guān)系。通常記集合A到B的函數(shù)f為f:AfB。,函數(shù)f:AfB的定義域(domain)dom(f)定義為：domf)={xI存在某個(gè)yeB使得＜x,y＞ef},函數(shù)f:AfB的值域(range)ran(f)定義為：ran(f)={yI存在某個(gè)xeA使得＜x,y＞ef},若＜x,y＞ef，通常記y為fx)，并稱y為x在函數(shù)f下的像(image),x為y在函數(shù)f下的原像。,函數(shù)也可推廣到n元的情形：f:A1xA2x…xAnfB,意味著：f是A]XA2x...xAnxB的一個(gè)子集，且?<x1,々，…，％y>ef且<11，々，…，％z>ef貝Iy=z。,函數(shù)的一些性質(zhì)：設(shè)f：A-B是集合A到B的函數(shù)：,說f是全函數(shù)(加㈤function)，若domf)=A,否則稱f是偏函數(shù)加"初function)。下面如果沒有特別指明的話，都是指全函數(shù)。說f是滿射(surjection,或說fmapsAontoB),如果ran(f)=B,即對(duì)任意的yeB都有原像。,說f是單射(injection，或說fisone-one)，如果有f(x1)=f(i2)則x1=12,即對(duì)任意的yeB,如果它有原像的話，則有唯一的原像。,說f是雙射Sjection，或說f是一對(duì)應(yīng))，如果f既是滿射，又是單射，即對(duì)任意的yeB,都有唯一的原像，同樣根據(jù)全函數(shù)的定義，對(duì)于任意xeA都有唯一的像。這時(shí)可以定義f的逆函數(shù)(inversefunction)，記為f-1：B-A,f-1(y)=x當(dāng)且僅當(dāng)fx)=y。顯然f-1也是雙射。,集合的基數(shù)(cardinalnumber)或說勢(shì)：集合A的基數(shù)記為IAI,且有：,對(duì)于有限集合A,令A(yù)的基數(shù)為A中元素的個(gè)數(shù)。,定義無限集合，不直接定義基數(shù)，而是通過定義兩個(gè)集合之間的等勢(shì)關(guān)系來刻劃集合的基數(shù)或勢(shì)，說集合A和集合B是等勢(shì)的(equipotent)，如果存在一個(gè)從A到B的雙射。根據(jù)雙射的性質(zhì)，可以證明等勢(shì)是集合上的一個(gè)等價(jià)關(guān)系。,稱與自然數(shù)集等勢(shì)的集合為可列集(enumerable)，有限集和可列集統(tǒng)稱為可數(shù)集(countable)。,設(shè)A和B是有限集合，有IP(A)I=2iai,|AxBI-IAIxIBI。小結(jié),下面以樹的形式給出了以上主要概念之間的關(guān)系：集合

子集合的補(bǔ)、并、交、差有序?qū)缂芽柗e子集合的補(bǔ)、并、交、差有序?qū)缂芽柗e關(guān)系的自反、對(duì)稱、傳遞性 函數(shù)單射、滿射、雙射歸納定義和歸納證明?一個(gè)集合的歸納定義(比血。小6definition)通常分為三步：歸納基：一些基本的元素屬于該集合；歸納步：定義一些規(guī)則(或者說操作)，從該集合中已有的元素來生成該集合的新的元素；最小化：該集合中的所有元素都是通過基本元素以及所定義的規(guī)則生成的，換句話說，該集合是由基本元素及規(guī)則所生成的最小的集合。?自然數(shù)集N的歸納定義：.歸納基：0是一個(gè)自然數(shù)，即0eN。.歸納步：若n是自然數(shù)，則n的后繼也是自然數(shù)。記n的后繼為succ(n)，即若neN,則succ(n)eN。為方便起見，后面也記n的后繼為n+1。. 最小化：所有的自然都通過步驟［1］和［2］得到，或者說自然數(shù)集是通過步驟［1］和［2］得到的最小集合。,這種定義方式可推廣到對(duì)其他一些概念的定義，例如上述多個(gè)集合的并、交、笛卡爾積以及多個(gè)元素的有序n元組都可通過遞歸的方式定義。例如，對(duì)于多個(gè)集合的并可定義為：,歸納基：A1uA2={xIxeA1或者xeA2},歸納步：A1uA2…uAn=(A1uA2…uAn-1)uAn,這里不需要最小化，因?yàn)檫@里不是定義集合。,數(shù)學(xué)歸納法：關(guān)于自然數(shù)的許多性質(zhì)都可通過數(shù)學(xué)歸納法來證明，對(duì)于性質(zhì)R,如果它對(duì)0成立，而且如果對(duì)于n成立的話，能夠得到它對(duì)于n+1也成立，那么性質(zhì)R對(duì)所有的自然數(shù)成立。這種證明方法的正確性本身可通過自然數(shù)的歸納定義來得到證明：,定義集合S={neNI性質(zhì)R對(duì)n成立},歸納基：根據(jù)上面的定義有0eS,歸納步：根據(jù)上面的定義有如果neS,則n+1eS,所以S是滿足上面自然數(shù)集的歸納定義中的1、2點(diǎn)的一個(gè)集合，而自然數(shù)集N是滿足這兩點(diǎn)的最小集合，所以有N=S,而顯然有SgN，所以S=N。,數(shù)學(xué)歸納法舉例：使用數(shù)學(xué)歸納法證明1+2+…+n=(n*(n+1))/2,歸納基：當(dāng)n=0時(shí)顯然成立。,歸納步：如果對(duì)于n成立，則有1+2+…+n=(n*(n+1))/2(這稱為歸納假設(shè))，現(xiàn)在要證對(duì)于n+1也成立。顯然有：1+2+…+n+(n+1)=(n*(n+1))/2+(n+1) //根據(jù)歸納假設(shè)=(n*(n+1)+2*(n+1))/2=((n+1)*((n+1)+1))/2因此要證的公式對(duì)于n+1成立，所以對(duì)于所有的自然數(shù)成立。?顯然在數(shù)學(xué)歸納法中，對(duì)于歸納基改為R對(duì)于自然數(shù)k成立，歸納步不變的話，則可證明R對(duì)于所有大于k的自然數(shù)都成立。,在數(shù)學(xué)歸納法中，也可將歸納步改為如果R對(duì)于所有小于n的自然數(shù)成立，則推出R對(duì)于n也成立，即歸納步是假設(shè)對(duì)于所有小于n的自然數(shù)性質(zhì)R成立來導(dǎo)出性質(zhì)R對(duì)于自然數(shù)n成立。這種形式的數(shù)學(xué)歸納法通常稱為第二數(shù)學(xué)歸納法。形式系統(tǒng),形式系統(tǒng)的定義：一個(gè)形式系統(tǒng)S由下列4個(gè)集合構(gòu)成：,一個(gè)非空集合￡S，稱為形式系統(tǒng)S的字母表或說符號(hào)(Sy機(jī)3/)表；,一個(gè)由￡S中字母的有限序列(字符串)所構(gòu)成的集合FS，稱為形式系統(tǒng)S的公式(Formula)集；,從FS中選取一個(gè)子集AS，稱為形式系統(tǒng)S的公理(A羽0m)集；?FS上有一個(gè)部分函數(shù)集RS={RnIRn:FSxFSx...xFSfFS,n=1,2，…}，稱為形式系統(tǒng)S的規(guī)則(Rule)集，其中Rn:FSxFSx...xFSfFS是n元的部分函數(shù)，我們稱其為n元規(guī)則。,形式系統(tǒng)中的定理(Theorem)：,歸納基：teAS是形式系統(tǒng)S中的定理。,歸納步：11,12,…，tn是形式系統(tǒng)S中的定理，而Rne是S中的規(guī)則，那么Rn(11,12,…，tn)也是形式系統(tǒng)S中的定理。,對(duì)于形式系統(tǒng)中的規(guī)則Rn：FSxFSx...xFSfFS，通常表示成下面的形式： 11,12,…，tnRn(t1,12,…,tn),形式系統(tǒng)具有兩個(gè)特征：,形式化實(shí)際上是一個(gè)可機(jī)械實(shí)現(xiàn)的過程，在它里面，符號(hào)、規(guī)則和演算等被表示得嚴(yán)密、精確。在形式系統(tǒng)S中，只能使用字母表￡S中的符號(hào)，只承認(rèn)公式集FS中的符號(hào)串的合理性，只能由公理集，根據(jù)規(guī)則推出有意義的東西來。,形式系統(tǒng)一旦完成，就成了符號(hào)串及根據(jù)規(guī)則進(jìn)行的符號(hào)串的改寫，系統(tǒng)與一切實(shí)際意義就毫不相干，或者說已經(jīng)通過這種符號(hào)，從實(shí)際問題中抽象出了我們所需要研10究的內(nèi)容。在形式系統(tǒng)內(nèi)部，所能認(rèn)識(shí)的只能是符號(hào)串及其改寫，只能在形式系統(tǒng)外對(duì)這種符號(hào)串及規(guī)則賦予意義。,對(duì)象語言(。勿0以language)與元語言(Metalanguage)：,數(shù)理邏輯所研究的是“數(shù)學(xué)推理”，而使用的方法也是數(shù)學(xué)推理，所以有必要區(qū)分這兩個(gè)層次的推理。,把作為研究對(duì)象的“推理”形式化，使用形式語言來表示作為研究對(duì)象的“推理”的前提、結(jié)論和規(guī)則等，這種形式語言是我們所研究的對(duì)象語言。,另一方面，關(guān)于形式系統(tǒng)的性質(zhì)、規(guī)律的表達(dá)和作為研究方面的推理方式使用另一種語言來表達(dá)，這個(gè)語言稱為研究的元語言，通常使用半數(shù)學(xué)化的自然語言。,形式語言的語法(Syntax)與語義(Semantic)：,形式語言的語法是構(gòu)成形式系統(tǒng)的公式集、公理集和規(guī)則集的法則。,形式語言的語義是關(guān)于形式系統(tǒng)的解釋和意思。,形式語言本身沒有含義，但我們?cè)跇?gòu)造它們時(shí)是假想它們能代表某種意義的，特別的當(dāng)我們?cè)谶x擇形式系統(tǒng)的公理時(shí)，總是選擇所研究的問題域中那些最為明顯或最容易公認(rèn)為正確的性質(zhì)。習(xí)題.令集合A={nIn<10且n是奇數(shù)},B={nIn<10且n是素?cái)?shù)}，請(qǐng)回答下列問題：請(qǐng)用列元素的方法列出集合A和集合B,請(qǐng)問集合B是否是集合A的子集？請(qǐng)計(jì)算AuB、AcB、A-B、AxB以及P(A)(即A的冪集)。.設(shè)關(guān)系R={<a,b>Ia和b是互質(zhì)的自然數(shù)}，請(qǐng)問R是自反的嗎對(duì)稱的嗎傳遞的嗎為什么.設(shè)f:AfB是函數(shù)，R是A上的如下二元關(guān)系：R={<a,b>Ia,beA,f(a)=f(b)},證明R是A上的一個(gè)等價(jià)關(guān)系。. 使用數(shù)學(xué)歸納法證明：12+22+32+…切2=(n*(n+1)*(2n+1))/6115.設(shè)有函數(shù)f：NfNxN,f(n)=<n,n+1>,請(qǐng)問f是不是單射、滿射或雙射？5.*6.設(shè)R1和R2都是A上的等價(jià)關(guān)系，請(qǐng)問R1uR2和R1nR2是否還是A上的等價(jià)關(guān)系？如果是請(qǐng)證明，否則請(qǐng)舉一反例。*7.設(shè)R是集合A上的等價(jià)關(guān)系，a￡A，可定義：[a]={beAIaRb}，稱[a]為a關(guān)于R的等價(jià)類；A/R={[a]IaeA}，稱A關(guān)于R的商集。設(shè)函數(shù)f：AfA/R定義為對(duì)任意aeA有fa)=[a]，請(qǐng)問R滿足怎樣的條件時(shí)f是單射？*8請(qǐng)給出<x,y,z>的集合方式的定義。若定義：[x,y,z]={{x},{x,y},{九y,z}}，則如果有[xyyyz1]=[x2,y2,z2]是否意味著有x1=x2且y1=y2且z1=z212第二講數(shù)理邏輯一、命題邏輯(PropositionalLogic).內(nèi)容概述,簡(jiǎn)單命題與復(fù)合命題：什么是命題？命題聯(lián)結(jié)詞及其含義。,命題公式與賦值：命題邏輯公式的歸納定義，命題公式的真值表。,等值演算：命題公式的等值賦值，重要的等值式。,命題聯(lián)結(jié)詞的完備集：通過等值演算得到命題聯(lián)結(jié)詞的完備集和極小完備集。,命題公式的范式：析取范式與合取范式。,命題演算系統(tǒng)：使用命題邏輯公式進(jìn)行推理的形式系統(tǒng)。,命題演算系統(tǒng)的語義與命題演算系統(tǒng)的元性質(zhì)：注意區(qū)別形式系統(tǒng)的語法和語義。. 簡(jiǎn)單命題與復(fù)合命題,命題(proposition經(jīng)典命題邏輯中，稱能判斷真假但不能既真又假的陳述句為命題。,命題對(duì)于命題邏輯來說是一個(gè)原始的概念，不能在命題邏輯的范圍內(nèi)給出它的精確定義，只能描述它的性質(zhì)。,命題必須為陳述句，不能為疑問句、祈使句、感嘆句等，例如下述句子為命題：1. 3是有理數(shù) 2. 8小于10133.2是素?cái)?shù)4.烏鴉是黑色的下列句子不是命題：TOC\o"1-5"\h\z1. 這個(gè)小男孩多勇敢?。?2. 烏鴉是黑色的嗎？3. 但愿中國(guó)隊(duì)能取勝。 4. 請(qǐng)把門開一開！下列句子不可能判斷其為真或?yàn)榧?，所以也不是命題：1.x+y>10 2.我正在撒謊,命題必須具有真假值，從某種意義上來說，疑問句、祈使句、感嘆句沒有真假之分。但能判斷真假，并不意味著現(xiàn)在就能確定其是真還是假，只要它具有能夠唯一確定的真假值即可，例如下述陳述句是命題：1. 明年的中秋節(jié)的晚上是晴天 2.地球外的星球上存在生物3. 21世紀(jì)末，人類將居住在太空 4.哥德巴赫猜想是正確的,經(jīng)典命題邏輯不區(qū)分現(xiàn)在已確定為真，還是將來可能確定為真這種情況，處理與時(shí)間有關(guān)的真值問題是時(shí)態(tài)邏輯的任務(wù)。經(jīng)典命題邏輯也不區(qū)分是在技術(shù)上可以確定為真，還是現(xiàn)在的技術(shù)條件下不可以確定為真的這種情況，只承認(rèn)在技術(shù)上，或者說能給出某種方法確定為真的那些東西才為真是直覺邏輯的觀點(diǎn)。14,真命題和假命題：命題是為真或?yàn)榧俚年愂鼍洌Q這種真假的結(jié)果為命題的真值。如果命題的真值為真，則稱為真命題，否則稱為假命題。,命題常量與命題變量：使用符號(hào)來表示命題，通常用p,q或帶下標(biāo)來表示命題常量或者變量。如果命題符號(hào)p代表命題常量則意味它是某個(gè)具體命題的符號(hào)化，如果p代表命題變量則意味著它可指代任何具體命題。如果沒有特別指明，通常來說命題符號(hào)p等是命題變量，即可指代任何命題。,簡(jiǎn)單命題與復(fù)合命題：不能分成更簡(jiǎn)單的陳述句的命題為簡(jiǎn)單命題或原子命題，否則稱為復(fù)合命題，復(fù)合命題使用命題聯(lián)結(jié)詞聯(lián)結(jié)簡(jiǎn)單命題而得到。,復(fù)合命題的聯(lián)結(jié)詞通常包括：,設(shè)p是任意命題，復(fù)合命題“非p”稱為p的否定(非)，記為「p。設(shè)p和q是任意命題，復(fù)合命題“p且q”稱為p和q的合取(與)，記為paq。設(shè)p和q是任意命題，復(fù)合命題“p或q”稱為p和q的析取(或)，記為pvq。設(shè)p和q是任意命題，復(fù)合命題“如果p則q”稱為p蘊(yùn)涵q，記為pTq。,設(shè)p和q是任意命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱為p與q等價(jià)，記為p?q。,上述定義中的非(negation)、合取(conjunction)、析取(d時(shí)unction)、蘊(yùn)涵(implication)和等價(jià)(equivalence)是在命題邏輯中的術(shù)語，而弓1號(hào)中給出的復(fù)合命題是自然語言中的典型用法。當(dāng)然，命題邏輯中符號(hào)化形式的復(fù)合命題在自15然語言中有許許多多的表達(dá)方法，這也是為什么自然語言有歧義的原因，參見教材中的各例題，并注意以下幾點(diǎn)：?pVq的邏輯關(guān)系是pVq為真當(dāng)且僅當(dāng)p和q中至少有一個(gè)為真。但自然語言中的“或”既可能具有相容性，也可能具有排斥性。命題邏輯中采用了“或”的相容性。?pfq的邏輯關(guān)系是pfq為假當(dāng)且僅當(dāng)p為真，而q為假，稱p為蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件?，F(xiàn)實(shí)世界中的“如果…則…”與這種蘊(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)涵意味著可從假的前提推出任何命題來，或兩個(gè)不沒有內(nèi)在聯(lián)系的命題之間存在蘊(yùn)涵關(guān)系?！鰧⑷粘Ｉ钪械年愂鼍浞?hào)化為命題邏輯中的公式是在今后的程序編寫等課程中應(yīng)用數(shù)理邏輯知識(shí)的重要基礎(chǔ)。但就數(shù)理邏輯這門課程本身而言，我們只關(guān)心公式之間的真值關(guān)系，而不關(guān)心公式所具體指代的命題?！鰪?fù)合命題與簡(jiǎn)單命題之間的真值關(guān)系可用下表給出，其中0代表假，1代表真：pq「pp△qpVqpfqp—q00100110110110100010011011113. 命題邏輯公式【定義1.1】命題邏輯公式(propose力??！ā?logicformula)由以下子句歸納定義：16. 歸納基：命題常量或命題變量是命題邏輯公式，稱為命題邏輯公式的原子項(xiàng)。.歸納步：如果A,B是邏輯公式，則(「A)、(AaB)、(AvB)s(A-B)和(A?B)也是命題邏輯公式。. 最小化：所有的命題邏輯公式都通過1和2得到?！踉谶@里我們隱含地使用的字母表是大小寫的英文字母、命題聯(lián)結(jié)符和園括號(hào)。英文字母還可帶下標(biāo)。其它的符號(hào)都不屬于我們的符號(hào)表，即在命題邏輯公式中不能出現(xiàn)這些符號(hào)。后面我們將命題邏輯公式簡(jiǎn)稱為命題公式，或在沒有二義的情況下進(jìn)一步簡(jiǎn)稱為公式。【例子1.1】((pvq)f((「p)妗(qar)))是命題公式，它通過以下步驟生成：p是公式； 〃根據(jù)定義1.1的[1]q是公式； 〃根據(jù)定義1.1的[1](pvq)是公式； 〃根據(jù)定義1.1的[2](「p)是公式； 〃根據(jù)定義1.1的[2]r是公式； 〃根據(jù)定義1.1的[1]17

6.(qa6.(qar)是公式；//根據(jù)定義1.1的[2]((「p)妗(qar))是公式； 〃根據(jù)定義1.1的[2],以及4,6((pvq)T((「p)―(qar)))是公式。 //根據(jù)定義1.1的[2],以及3,7這種生成過程，可以形象地用下面的一棵樹來表示：((Pvq)T((「p)—(qar)))(pvq) ((「p)—(qar))Z\ ,、 ，p/q (「p) (qar)p qr這種樹在形式語言與自動(dòng)機(jī)中就稱為語法分析樹?！痉蠢?.2】,根據(jù)定義1.1,paq不是公式，因?yàn)閮蛇厸]有園括號(hào),根據(jù)定義1.1,(paqar)不是公式，實(shí)際上，由定義1.1生成的公式,每個(gè)命題聯(lián)結(jié)符都會(huì)對(duì)應(yīng)一對(duì)園括號(hào)。,顯然(pqTr)、(qT(rAp)等都不是公式?！径ɡ?.2】設(shè)R是某個(gè)性質(zhì)，如果有：. 對(duì)于所有的原子項(xiàng)P,都滿足性質(zhì)R；.如果對(duì)任意的公式A和B都滿足性質(zhì)R,就有(「A)、(AaB)、(AvB)、(AtB)和(A—B)也滿足性質(zhì)R。18那么，所有的公式A就都滿足性質(zhì)R?！踉摱ɡ淼淖C明類似數(shù)學(xué)歸納法的證明，很容易根據(jù)定義1.1得到。【定義1.3]命題公式A的復(fù)雜程度deg(A)定義為：. 如果A是原子項(xiàng)，則deg(A)=0；. deg([A)=deg(A)+1;.deg(A*B)=max(deg(A),deg(B))+1,其中*代表a、vs“、》之一。 □此定義等價(jià)于教材p11的定義1.7。只不過我們?cè)谶@里給出的是遞歸定義。使用歸納法，我們可證明下面定理：【定理1.4]deg(A)小于等于命題公式A中的命題聯(lián)結(jié)符號(hào)的數(shù)目?！咀C明]根據(jù)命題公式A的結(jié)構(gòu)進(jìn)行歸納證明：歸納基：如果A是原子項(xiàng)，則根據(jù)定義1.3有deg(A)=0,顯然定理成立。歸納步：假設(shè)定理對(duì)于命題公式A和B成立(歸納假設(shè))，記命題公式A中的命題聯(lián)結(jié)符號(hào)數(shù)為Sym(A),即有deg(A)<Sym(A)和deg(B)<SyMB)。那么由于deg([A)=deg(A)+1,而Sym([A)=Sym(A)+1,所以定理對(duì)于「A也成立。同樣由于deg(A*B)=max(deg(A),deg(B))+1,而Sym(A*B)=Sym(A)+Sym(B)+1,因而有deg(A*B)<Sym(A*B),從而定理對(duì)所有的命題公式都成立?！?9【定理1.5】任意命題邏輯公式A中出現(xiàn)相等數(shù)目的左右園括號(hào)，實(shí)際上，左右園括號(hào)的個(gè)數(shù)都等于A中的命題聯(lián)結(jié)符號(hào)數(shù)?！酢径ɡ?.6】任意命題邏輯公式A具有下列6種形式之一，且只具有其中一種形式：[1]. A為原子項(xiàng)； [2]. ([A) [3].(AaB)[4]. (AvB) [5]. (AfB). (A?B) □定理1.6的確切含義包括以下幾點(diǎn)：任意命題公式必然具有上述6中形式之一；這6中形式都互不相同；如果(「A)與(「AJ相同，則必有A與A1相同；如果(A*B)與%*BJ相同，則必有A與A1相同，且B與b1相同。根據(jù)定理1.5和定理1.6,我們不難明白例子1.1是如何得到該其中命題公式的語法分析樹的。實(shí)際上每個(gè)命題公式的最左邊都是左園括號(hào)，如果從第二個(gè)符號(hào)不是左園括號(hào)，那么這個(gè)公式只有一個(gè)命題聯(lián)結(jié)符。否則找與第二個(gè)左園括號(hào)配對(duì)的右園括號(hào)，從而將命題公式劃分為這樣的形式：((…)*(…)如果原來的命題公式為根的話，那么左右兩邊的兩個(gè)命題公式分別為它的左右子樹了，而且對(duì)這兩個(gè)公式可作類似的分析，最后到原子項(xiàng)。在后面，為了書寫方便起見，我們省略最外邊的括號(hào)，并規(guī)定各個(gè)命題聯(lián)結(jié)符的優(yōu)先級(jí)別為「大于a，a大于v，v大于f，f大于分，從而可省略命題20公式中一些不必要的園括號(hào)，例如例子1.1中的公式可寫為：pVqf「p?qar。不過在后面我們書寫公式的原則是盡量簡(jiǎn)便，但又能讓讀者容易理解。而有關(guān)命題公式的性質(zhì)的討論，則只針對(duì)可由上面定義1.1所能生成的公式形式。上面討論的命題公式的語法結(jié)構(gòu)，下面討論命題公式的賦值?！径x1.7]對(duì)命題公式的一次真值賦值t是從所有命題變量所組成的集合到集合{0,1}的函數(shù)。實(shí)際上，對(duì)于某個(gè)命題公式A來說，我們只關(guān)心t在A中的命題變量上的值。這里我們假定存在一個(gè)所有命題變量所組成的集合U,或者說我們所有命題公式中的變量都取之于集合U,我們記命題公式A中的所有命題變量所組成的集合為Vw(A)。設(shè)有一個(gè)真值賦值t:Uf{0,1},而對(duì)于命題公式A的真值賦值來說，我們只關(guān)心t在Vw(A)上的值?！纠?.3】對(duì)于命題公式A=((pvq)f((「p)?(qar))),有：Var(A)={p,q,r}這里不妨假定U=Var(A),真值賦值就是一個(gè)函數(shù)t:{p,q,r}f{0,1},例如可令：t(p)=0,t(q)=1,t(r)=0【定義1.8]命題公式A在真值賦值t:Uf{0,1}下的真值t(A)遞歸定義如下：. 如果命題公式A是一個(gè)命題常量p,則如果p為真，t(A)=1,否則t(A)=0；. 如果命題公式A是一個(gè)命題變量p,則t(A)=t(p). 若 t(A) =0則t(「A)=1，否則t(「A)=0。. 若 t(A) =t(B)=1,則t(AaB)=1，否則t(AaB)= 0。. 若 t(A) =t(B)=0,則t(AvB)=0,否則t(AvB)= 1。21

.若t(A)=0或者t(B)=1,則t(AfB)=1,否則t(AfB)=0。.若t(A)=t(B),貝1Jt(A?B)=1，否則t(A?B)=0?！纠?.3，續(xù)】對(duì)于命題公式A=((pvq)T((「p)妗(qar))),及真值賦值函數(shù)t：t(p)=0,t(q)=1,t(r)=0有：t(p)=0,t(q)=1;t(pvq)=1;義1.8的[5]t(「p)=1;義1.8的[3]t(r)=0;t(qar)=0;義1.8的[4]t((「p)妗(qar))=0;[7]t((pvq)T((「p)妗(qar)))=0;[6]因此命題公式A在上述真值賦值下的真值t(A)是0。//根據(jù)定//根據(jù)定//根據(jù)定//根據(jù)定//根據(jù)定//根據(jù)定//根據(jù)定義1.8的//根據(jù)定義1.8的命題公式的真值只與命題公式中所出現(xiàn)的命題變量的真值賦值有關(guān)，如果命題公式中含有n個(gè)命題變量，則對(duì)這些命題變量的真值賦值共有2n種不同情22

況，可通過一個(gè)表，列出在這所有情況下命題公式的真值，這種表稱為該命題公式的真值表，例如上述命題公式A的真值表為：pqr(pvq)(「p)(qAr)((「p)?(qAr))((pvq)f((「p)?(qAr)))0000100100101001010110000111111110010011101100111101001111110100【定義1.9］如果命題公式A在任意的真值賦值函數(shù)t:Uf{0,1}下的真值t(A)都為1,則稱命題公式A為永真式(Sm加。gy)(或稱重言式)；如果命題共A在任意的真值賦值函數(shù)下的真值都為0,則稱A為矛盾式(contradiction)；如果A不是矛盾式，則稱為可滿足式。【例子1.4］根據(jù)命題公式A=((pvq)-((「p)?(qar)))的真值表，我們知該命題公式是可滿足式，但不是永真式。而公式B=((p-(qvp))vr)是永真式，其真值表為：pqr(qvp)(pf(qvp))((pf(qvp))vr)000011001011010111011111100111101111110111111111而公式(((「(pfq))Aq)Ar)(教材14頁簡(jiǎn)寫為「(pfq)AqAr)是矛盾式，其真值表為：pqr(pfq)(「(pfq))((「(pfq))Aq)(((「(pfq))Aq)Ar)0001000230011000010100001110001000100101010011010001111000【定義1.10］我們使用符號(hào)￡來表示一組命題公式所構(gòu)成的集合。定義￡在真值賦值函數(shù)t:Uf{0,1}下的真值t(￡)為：t(￡)=1當(dāng)且僅當(dāng)對(duì)￡中任意公式A有t(A)=1,否則定義t(￡)=0(注意只要￡中存在某個(gè)公式A使得t(A)=0,就有t(￡)=0)。說￡是可滿足的，如果存在某個(gè)真值賦值函數(shù)t使得t(￡)=1,這時(shí)稱t滿足￡?！径x1.11】設(shè)￡是一組命題公式的集合，說命題公式A是以￡為前提的永真式，如果滿足對(duì)任意滿足￡的真值賦值函數(shù)t都有t(A)=1,這時(shí)我們記為￡-A。注意在定義1.11中，如果￡為空集，則。卜A表示A為永真式，因?yàn)閷?duì)于空集￡來說，顯然任意的真值賦值函數(shù)t都滿足它(因?yàn)椤曛袥]有命題公式)，從而。卜A意味著對(duì)任意的真值賦值函數(shù)t都有t(A)=1,即A為永真式。等值演算【定義1.12】當(dāng)￡={A1,A2,…,An}時(shí)，我們也記￡M為A1,A2,…，An&A。如果有APB且BkA,則稱命題公式A與B等值，記為AoB。實(shí)際上公式A與B等值記為AHB會(huì)更準(zhǔn)確些，但教材采用了符號(hào)人。8,為了不會(huì)過于混淆，我們也使用這種記號(hào)。實(shí)際上，根據(jù)定義1.11,AoB就意味著對(duì)任意的真值賦值函數(shù)t有t(A)=1當(dāng)且僅當(dāng)t(B)=1，也就是24

說對(duì)任意的t有t(A)=t(B)。從而定義1.12與教材中關(guān)于命題公式等值的定義是等價(jià)的，即有下述定理：【定理1.13】AoB當(dāng)且僅當(dāng)A?B是永真式。□使用真值表，不難證明下面的定理：【定理1.14】設(shè)A,B,C是任意的命題公式，有：[1]. 雙重否定律:[1]. 雙重否定律:Ao-A)).等冪律： Ao(AvA)Ao(AaA).交換律： (AvB)o(BvA)(AaB)o(BaA)[4], 結(jié)合律： ((AvB)vB)o(Av(BvB))((AaB)aB)o(Aa(BaB)). 分配律： (Av(BaC))o((AvB)a(AvC))(Aa(BvC))o((AaB)v(AaC)). 德摩根律：(」(AvB))o((「A)a(「B)) (「(AaB))o((lA)v([B)).吸收律： (Av(AaB))oA(Aa(AvB))oA.零律： (Av1)o1(Aa0)o0.同一律： (Av0)oA(Aa1)oA.排中律： (Av(」A))o1.矛盾律： (Aa(「A))o0[12].蘊(yùn)涵等值式:[12].蘊(yùn)涵等值式:(A-B)o((」A)vB)25

25.等價(jià)等值式： (A?B)o((AfB)a(B-A)).假言易位：(A-B)o((「B)T「A)).等價(jià)否定等值式：(A?B)o((「A)?([B)).歸謬論： ((AfB)a(A—(「B)))o(「A)□要注意的是，上述定理中的0代表真值為0的任意命題常量，而1代表真值為1的任意命題常量。由于命題聯(lián)結(jié)符號(hào)a和v都滿足結(jié)合律，因此我們可有如下的簡(jiǎn)寫：A1AA2A...aA江A1VA2V-VAn根據(jù)以上簡(jiǎn)寫，我們可推廣定理1.13為以下定理1.15：【定理1.15】[1].A1，[1].A1，A2,.,AnPA當(dāng)且僅當(dāng)。卜((A1AA2A…AAn)-A)。. A#A2,…,AnPA當(dāng)且僅當(dāng)。卜((A1TA2f(.(An-A).))?！疽?.16】設(shè)有AoA和BoB'，則有：. (「A)o(「A'). (AaB)o(A'aB'). (AvB)o(A'vB'). (AfB)o(A'fB'). (A?B)o(A'?B')□根據(jù)弓[理1.16,不難證明下面的置換規(guī)則：【定理1.17]設(shè)有BoC,而A'是命題公式A通過使用C替換A中出現(xiàn)的某些B(不需要是替換所有的B)而得到的命題公式，則有AoA'。26【證明】對(duì)命題公式A的結(jié)構(gòu)進(jìn)行歸納。首先如果B=A,則有C=A',從而有AoA'。歸納基：如果A是命題變量和命題常量，那么必有B=A，因此定理成立。歸納步：根據(jù)定理1.6,命題公式A必為如下5種形式之一：「A1,A1AA2,A1VA2,A1fA2,Ai?A2。設(shè)A的形式為-1A「如果B=A則定理成立，否則必有B出現(xiàn)A1中，將A1中的B用C替換后得到的為A；，按歸納假設(shè)有A產(chǎn)A；，再根據(jù)弓[理1.15有[A]=「A；。定理成立。若A的形式為A1*A2，則如果B=A則定理成立，否則必有B出現(xiàn)在A1或A2中，或同時(shí)出現(xiàn)在這兩者中。設(shè)將A1中的B用C替換后得到的為A；,而將A2中的B用C替換后得到的為A2’,按歸納假設(shè)有A10Al和A2oA2'，再根據(jù)弓[理1.15有AJA20Al*A2，即定理成立。□【定義1.18】如果命題公式A中只出現(xiàn)命題變量、命題常量、命題聯(lián)結(jié)符號(hào)「、a和v則稱為限制性(命題)公式。定義：.對(duì)于限制性公式A,將其中的命題聯(lián)結(jié)符號(hào)A換成V,命題聯(lián)結(jié)符號(hào)V換成a得到的公式稱為A的對(duì)偶公式(曲Mformula)，記為A卻。.對(duì)于限制性公式A,將其中出現(xiàn)的所有原子項(xiàng)(命題變量或命題常量)p換成「p得到的公式稱為A的內(nèi)否式，記為A「。【例子1.5]設(shè)公式A=」((pvq)A(「r)),則：. A的對(duì)偶式A0P=」((pAq)v(「r)). A的內(nèi)否式A「=「(((「p)v(「q))Ar)27【引理1.19】設(shè)公式A、B都是限制性公式，有：. (Aop)op. (Aop)op=A. (AvB)op=AopaBop. (AaB)op=AopvBop. (Aop)「=(A「)op(A「)「=A(AvB)「=A「vB」(AaB)「=A「aB「□弓[理1.19中的三(恒等號(hào))表示兩邊的公式在(語法)形式上完全一樣，例如(Aop)o=A表示對(duì)A的對(duì)偶公式Aop再做一次對(duì)偶操作得到的就是A本身。而(Ao)「三(A「)op表示對(duì)A做一次對(duì)偶操作得到Aop，然后再求Ao的內(nèi)否式，得到的公式與先求A的內(nèi)否式，然后再做對(duì)偶操作得到的公式完全一樣，用代數(shù)學(xué)的術(shù)語來說，就是這兩種操作可交換。弓[理1.19很容易根據(jù)定義1.18證明，也可直觀理解弓[理1.19所代表的含義。讀者可通過對(duì)一些公式求它的對(duì)偶式和內(nèi)否式來驗(yàn)證弓I理1.19的每個(gè)恒等式，例如：【例子1.5，續(xù)】設(shè)公式A=」((pvq)A(「r)),則：. A0P=「((pAq)v([r)),(A0P)「=」(((「p)A([q))vr).A=」(((「p)v([q))ar),(A「)0P=」(((「p)a([q))vr)顯然有(Aop卜三(A「)op?！径ɡ?.20】設(shè)公式A是任意的限制性公式，有：. ([A)opo「(Aop) (「A)」o」(A」). (Aop)「o「A【證明】略□【推論1.21】設(shè)公式A和B都是限制性公式，有AoB貝1J(Aop)[o(B0P)[28【證明】 根據(jù)弓I理1.16及「(「A)oA不難得到AoB當(dāng)且僅當(dāng)「Ao「B。則：(Aop)「o-1A^o-1Bo(Bop)「□在定理1.14中已經(jīng)看到了推論1.21的許多佐證，例如對(duì)于吸收律(Av(AaB))oA,其中(Av(AaB))的對(duì)偶公式是(「AA(「Av「B)),從而有(「Aa(「Av「B))o「A,這與第二個(gè)吸收律公式(Aa(AvB))oA是相同的，因?yàn)锳、B代表任意命題公式?！纠?.6】驗(yàn)證下列等值式. ((p—q)-r)o((「qAp)vr). (p-(q-r))o((pAq)-r). ((pvq)-r)o((p-r)A(q—r)). ((pAq)-r)o((p-r)v(q-r)). (p-(qvr))o((p-q)v(p-r)). (p-(qAr))o((p-q)A(p-r))【證明】證明的思路有兩種，第一種思路是通過列真值表，可看到上述等值式o的兩邊在任何真值賦值下都有相同的真值，從而完成上述等值式的驗(yàn)證。讀者不妨自己按照這種思路進(jìn)行證明。第二種思路是利用定理1.14中的基本等值式來證明?？梢钥吹缴鲜龅戎凳街饕顷P(guān)于蘊(yùn)涵的等值式，證明關(guān)于蘊(yùn)涵的等值式的方法是利用定理1.14中的［12］將蘊(yùn)涵化成只出現(xiàn)與、或、非的公式，再來驗(yàn)證它們的相等。. ((p-q)-r)o((「pvq)-r) //定理1.14中的［12］：蘊(yùn)涵等值式o(「(「pvq))vr //定理1.14中的［12］：蘊(yùn)涵等值式29

//德摩爾根律o(pA([q))v//德摩爾根律o(JqAp)vr). (p-(q—r))o(」pv(qfr))oJpvJqvr))o((「pv「q)vr)oJ(pAq)vr)用o((pAq)-r)用. ((pvq)-r)o(^(pvq)vr)o((「pA「q)vr)o((「pvr)A(「qvr))o((p-r)A(q-r)). (p-(qvr))o(「p)v(qvr)o(「p)vjp)v(qvr)o(」pvq)v(「pvr)o(p—q)v(p—r)(4)(6)留作練習(xí)//a的交換律////a的交換律//蘊(yùn)涵等值式//蘊(yùn)涵等值式//v的結(jié)合律//德摩爾根律，反向運(yùn)//蘊(yùn)涵等值式，反向運(yùn)//蘊(yùn)涵等值式//德摩爾根律//分配律與交換律//蘊(yùn)涵等值式//蘊(yùn)涵等值式//v的冪等律//v的交換律和結(jié)合律//蘊(yùn)涵等值式(1).(2).」(A1VA2V...vAn)o([A1)a([A2)a...A([An(1).(2).」(A1AA2A-aAn)o(」A1)v([A2)v-v(」An)30【證明】對(duì)n實(shí)施數(shù)學(xué)歸納法，或直接從定理1.20[2]得到?！?.聯(lián)結(jié)詞的完全集【定義1.22】{0,1}上的n元函數(shù)f:{0,1}nf{0,1}就稱為一個(gè)n元真值函數(shù)。聯(lián)結(jié)詞「實(shí)際上一個(gè)一元真值函數(shù)：戶(0)=1,a(1)=0而聯(lián)結(jié)詞△、V、一和》則都是二元真值函數(shù)：fX(0,0)=0,f\(0,1)=0,f\(1,0)=0,f\(1,1)=1fV(0,0)=0,fV(0,1)=1,fV(1,0)=1,fV(1,1)=1ff(0,0)=1,ff(0,1)=1,ff(1,0)=0,ff(1,1)=1f^(0,0)=1,N(0,1)=0,H0)=0,H1)=1反過來，一個(gè)真值函數(shù)就可看成一個(gè)真值聯(lián)結(jié)詞。設(shè)f：{0,1}nf{0,1}是一個(gè)n元真值函數(shù)，則可如下定義一個(gè)n元真值聯(lián)結(jié)詞Nf：對(duì)于n個(gè)命題變?cè)猵1,p2,…,pn，命題公式Nf(p1,p2,…,pn)在真值賦值函數(shù)<11,12,…，tn>下的真值為f11,12,…，tn)。顯然互不相同的n元真值函數(shù)的個(gè)數(shù)為22n，因此可定義22n個(gè)n元真值聯(lián)結(jié)詞，例如1元真值函數(shù)有四個(gè)：f1:0f0,1f0 f2:0f0,1f1 f3:0f1,1f0 f4:0f1,1f1而2元真值函數(shù)有16個(gè)，可定義16個(gè)真值聯(lián)結(jié)詞，而我們常用的只不過是其中的4個(gè)?，F(xiàn)在的問題是，是否所有的真值函數(shù)都可使用常用的這5個(gè)真值聯(lián)結(jié)詞來表示呢？【定義1.23】設(shè)Q是聯(lián)結(jié)詞的一個(gè)集合，稱Q為聯(lián)結(jié)詞的一個(gè)完全集，如果任意真值函數(shù)f都可用僅含Q中聯(lián)結(jié)詞的命題公式A來表示，即對(duì)A中命題變31元的任意一個(gè)真值賦值＜t1,t2,…，tn＞,A在＜t1,12,…，tn＞下的真值為f11,12,…,tn)o【定理1.24]｛「,a,v,f｝是聯(lián)結(jié)詞的一個(gè)完全集。【證明】根據(jù)定義1.23只要證明對(duì)任意n元真值函數(shù)都可由只含「、a、v和f的n元命題公式來表示即可。對(duì)真值函數(shù)的元數(shù)n進(jìn)行歸納證明。歸納基：當(dāng)n=1時(shí)，一元真值函數(shù)只有4個(gè)，可分別用pa（「p）、p、「p和pv（「p）來表示，因此定理成立。歸納步：假設(shè)當(dāng)n=k時(shí)定理成立，要證n=k+1定理也成立。設(shè)fx1,x2,…,xk,xk+1）是一個(gè)k+1元真值函數(shù)，定義如下兩個(gè)k元真值函數(shù)：f（x1,X2，…,Xk）=fX1,X2，…,Xk,0） 于2（x1,X2，…,Xk）=f（xx1,X2，?！?，Xk,1）由歸納假設(shè)知f和f2都可由只含「、a、V和f的k元命題公式來表示，設(shè)它們分別可由A1和A2表示，且假定A1和A2中的k個(gè)命題變?cè)獮閜1M2,…，pko現(xiàn)在我們證f可由a=（（「pk+1）fA1）A（pk+1fA2）表示，其中pk+1是不同于p1,p2,…,pk的一個(gè)命題變?cè)＜匆C對(duì)命題變?cè)猵1M2,…，pk,pk+1的一個(gè)真值賦值＜11,12,…，tk,tk+1＞時(shí)，A的真值是f11,t2,…，tk,tk+1）o當(dāng)tk+1=0時(shí)，即pk+1被賦值為0,這時(shí)（（「pk+1）fA1）與A1等值，而（pk+1-八2）的真值為1,所以A與A1等值，而按歸納假設(shè)有A1的真值為f（t1,12,…，tk）,即為fx1,x2,…,xk,0）。同理可證當(dāng)tk+1=1時(shí)A的真值是fx1,x2,…,xk,1）,從而A的真值是f11,12,…，％)o【推論1.25]｛「,f｝,｛「,修和｛「,0都是聯(lián)結(jié)詞的完全集。32【證明】1.要證｛「,f｝是聯(lián)結(jié)詞的一個(gè)完全集，只要證任一命題公式可與一個(gè)只含「和一的命題公式等值，事實(shí)上有：(AvB)o((「A)-B) (AaB)o(「((「A)v([B)))｛「,a｝是聯(lián)結(jié)詞的一個(gè)完全集，因?yàn)椋?AvB)o(「((「A)a([B))) (A-B)o((「A)vB)｛「,v｝是聯(lián)結(jié)詞的一個(gè)完全集，因?yàn)椋?AaB)o(「((「A)v([B))) (A-B)o((「A)vB)事實(shí)上，上述每個(gè)集合都是極小的完全集，即不能再?gòu)募现腥サ羧我庖粋€(gè)聯(lián)結(jié)詞還能保持是完全集?！酢径ɡ?.26]｛f,a,v,?｝不是聯(lián)結(jié)詞的完全集?！咀C明】總?cè)?值的真值函數(shù)不能由只含此聯(lián)結(jié)詞集中的聯(lián)結(jié)詞的命題公式來表達(dá)，因?yàn)檫@樣的命題公式當(dāng)所有命題變?cè)颊嬷蒂x值為1時(shí)真值為1,不可能為0。 □6. 命題公式的范式1.27]將命題符號(hào)(代表命題變?cè)蛎}常量)或命題符號(hào)的否定統(tǒng)稱為文字(liter)。!僅由有限個(gè)文字構(gòu)成的析取式稱為簡(jiǎn)單析取式。僅由有限個(gè)文字構(gòu)成的合取式稱為簡(jiǎn)單合取式?！纠?.8]文字、簡(jiǎn)單析取式與簡(jiǎn)單合取式：p,「q等為文字，也是一個(gè)文字的簡(jiǎn)單析取式和簡(jiǎn)單合取式pvq,pv(「q)等為兩個(gè)文字的簡(jiǎn)單析取式，pvqv(「r為mj文字的簡(jiǎn)單析取式pAq,pA(「q)等為兩個(gè)文字的簡(jiǎn)單合取式，pAqA(「r為mj文字的簡(jiǎn)單合取式33【定理1.28】一個(gè)簡(jiǎn)單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題符號(hào)及其否定，一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)命題符號(hào)及其否定?！酢径x1.29]由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式(disjunctivenormalform)，由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式(conjunctivenormalform)。析取范式和合取范式統(tǒng)稱為范式(normalform)。【例子1.9]析取范式和合取范式：(pAq)v(「pA「q),(pAr)v(qA「rAp)v(「rA「p)等是析取范式(pvq)A(「pv「q),(pvr)A(qv「rvp)A(「rv「p)等是合取范式根據(jù)定義1.18知，一個(gè)析取范式的對(duì)偶式是合取范式，一個(gè)合取范式的對(duì)偶式是析取范式。【定理1.30]一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。一個(gè)合取范式是永真式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是永真式?！径ɡ?.31](范式存在定理)任意命題公式都存在與之等值的析取范式與合取范式。求一個(gè)公式的范式的步驟如下：. 利用蘊(yùn)涵等值式(AfB)o(「AvB)和等價(jià)等值式(A?B)o(「AvB)a(Av「B)消除公式中的聯(lián)結(jié)詞-和》,使得公式中只含有聯(lián)結(jié)詞「、A和V。. 利用雙重否定律「「AoA和德摩爾根律將否定放到命題符號(hào)前。. 利用分配律，求析取范式利用a對(duì)V的分配律，求合取范式則利用V對(duì)A的分配律。34【例子1.9】求命題公式的析取范式和合取范式. 求(」pfq)A(p-r)的析取范式和合取范式. 求(p-q)v(pAr)的析取范式和合取范式【解答】(1)求(」p-q)A(p-r)的析取范式：(」pfq)A(p-r)o(「「pvq)A(「pvr) //蘊(yùn)涵等值式o(pvq)A(「pvr)o(pA「p)v(pAr)v(qA「p)v(qAr) //雙重否定律和分配律o(pAr)v(qA「p)v(qAr) //(pA「p)是矛盾式顯然(」p-q)A(p-r)的合取范式為(pvq)Ajpvr)。(2)求(p-q)v(pAr)的合取范式：(pfq)v(pAr)o(「pvq)v(pAr)o(^pvqvp)A(^pvqvr)顯然(p—q)v(pAr)的析取范式為(lp)vqv(pAr)。注意：一個(gè)命題公式的合取范式和析取范式不具有唯一性。【定義1.32】在含有〃個(gè)文字的簡(jiǎn)單合取式中，若每個(gè)命題符號(hào)和其否定不同時(shí)存在，而二者之一必須出現(xiàn)且只出現(xiàn)一次，且第i個(gè)命題變?cè)蛘叻穸ǔ霈F(xiàn)在從左邊算起的第i個(gè)位置上(若命題變?cè)獰o下標(biāo)，則按字典順序排列)，這樣的簡(jiǎn)單合取式稱為極小項(xiàng)。極小項(xiàng)是特殊的簡(jiǎn)單合取式。含〃個(gè)文字的極小項(xiàng)中，由于每個(gè)命題變?cè)栽位蚍穸ǔ霈F(xiàn)且僅出現(xiàn)一次，因此n個(gè)命題變?cè)部僧a(chǎn)生2n個(gè)不同的極小項(xiàng)。若在極小項(xiàng)中，將命題變?cè)脑螌?duì)應(yīng)1，否定對(duì)應(yīng)0，則每個(gè)極小項(xiàng)唯一地對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，該二進(jìn)制數(shù)的每一位正是使該極小項(xiàng)的真值為1的真值賦值。35

【例子1.10]兩個(gè)命題變?cè)猵,q生成的4個(gè)極小項(xiàng)為：」pA「q對(duì)應(yīng)00,記為m0pA「q對(duì)應(yīng)10,記為m2為m2「pAq對(duì)應(yīng)01,記為m1pAq對(duì)應(yīng)「pAq對(duì)應(yīng)01,記為m1pAq對(duì)應(yīng)11,記「pA「qA「r對(duì)應(yīng)000，記為m0「pA「qAr對(duì)應(yīng)001,記「pAqA「r對(duì)應(yīng)010,記為m2「pAqAr對(duì)應(yīng)011,記為pA「qA「r對(duì)應(yīng)100,記為m4pA「qAr對(duì)應(yīng)101,記為pAqA「r對(duì)應(yīng)110,記為m6pAqAr對(duì)應(yīng)111,記為【定義1.33]若析取范式中的簡(jiǎn)單合取式都是極小項(xiàng)，則稱該析取范式為主析取范式?！径ɡ?.34]任何命題公式存在唯一的主析取范式。求一個(gè)公式的主析取范式是：先求該公式的一個(gè)析取范式。如果該析取范式的某個(gè)簡(jiǎn)單合取式A中既不含某個(gè)命題變?cè)猵,也不含它的否定「p,則該簡(jiǎn)單合取式變?yōu)槿缦滦问剑海ˋap）v（Aa「p）。消除重復(fù)出現(xiàn)的命題變?cè)蛎}變?cè)姆穸?，矛盾式及重?fù)出現(xiàn)的極小項(xiàng)，并將每個(gè)極小項(xiàng)的命題變?cè)蚱浞穸ò聪聵?biāo)順序或字典順序排列?！纠?.11]求命題公式的主析取范式(1).求—pfq）A（pfr）的主析取范式(1).36（2）. 求（p-q）v（pAr）的主析取范式【解答】（1）根據(jù)例子1.9知（「pfq）A（p-r）的一個(gè)析取范式是（pAr）v（qA「p）v（qz）,我們將其中的每個(gè)簡(jiǎn)單合取式展開為含有所有命題變?cè)臉O小項(xiàng)的析?。海╬^r）展開為（p^qAr）v（pA「qAr） （q^「p）展開為（^pAqAr）v（^pAqA^r）（qAr）展開為（pAqAr）v（「pAqAr）因此（「pfq）A（p-r）的主析取范式為（pAqAr）v（pA「qAr）v（「pAqAr）v（「pAqA「r），按極小項(xiàng)所對(duì)應(yīng)的二進(jìn)制數(shù)的大小重新排列為（「pAqA「r）v（「pAqAr）v（pA「qAr）v（pAqAr）。（2）根據(jù)例子1.9知（pfq）v（pAr）的一個(gè)析取范式為（「p）vqv（pAr），將其中每個(gè)簡(jiǎn)單合取式展開為含有所有命題變?cè)臉O小項(xiàng)的析?。海ā竝）展開為（「pAqAr）v（「pA「qAr）v（「pAqA」r）v（「pA」qA「r）q展開為（pAqAr）v（「pAqAr）v（pAqA「r）v（「pAqA「r） （pAr）展開為（pAqAr）v（pA「qAr）因此（pfq）v（pAr）的主析取范式為：（「pA「qA「r）v（「pA「qAr）v（「pAqA「r）v（「pAqAr）v（pA「qAr）v（pAqA「r）v（pAqAr）主析取范式也可從命題公式的真值表更容易地得到，對(duì)應(yīng)地，根據(jù)命題公式的主析取范式也可容易地構(gòu)造其真值表、判定其類型（矛盾式、可滿足式還是永真式）等。關(guān)于極大項(xiàng)、主合取范式等有關(guān)內(nèi)容學(xué)生根據(jù)教材自學(xué)。作業(yè)：教材p60的9,10,11,15,17。377.命題演算系統(tǒng)命題演算系統(tǒng)是研究利用命題邏輯公式進(jìn)行推理的形式系統(tǒng)。這里的推理指的是前提和結(jié)論之間的邏輯關(guān)系，因此這種形式系統(tǒng)本身不注重前提本身的正確性，而關(guān)心的是是否能從前提有效地推出結(jié)論，討論什么是結(jié)論的有效證明。前提本身的正確性要在賦予形式系統(tǒng)一定的解釋的基礎(chǔ)上才能確定，這種解釋可以說是形式系統(tǒng)的語義。命題演算系統(tǒng)作為一個(gè)形式系統(tǒng)研究如何從公理，通過有限的規(guī)則來構(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.35]命題演算系統(tǒng)P定義為：P的符號(hào)表包括：. 命題變?cè)盒懹⑽淖帜覆⒖杉酉聵?biāo).聯(lián)結(jié)詞：「、T.輔助符號(hào)：（,）（園括號(hào)）P的公式歸納定義為：.命題變?cè)枪?8. 若A是公式，則(「A)也是公式. 若A和B是公式，則(AfB)也是公式. 所有公式都是通過有限次使用[1]、[2]和[3]得到。P的公理有如下三類：[A1].(Af(BfA))[A2].((Af(BfC))f((AfB)f(AfC))[A3].(((「A)T「B))-(B-A))P的規(guī)則只有一條：[M]. 分離規(guī)則：由A和(AfB)可得到B□【注解】關(guān)于以上定義，需要注意以下幾點(diǎn)：在系統(tǒng)P中只使用聯(lián)結(jié)詞「和f，這使得系統(tǒng)P比較簡(jiǎn)單，但也失去了使用另外三個(gè)聯(lián)結(jié)詞A、▽和》的方便之處，為此可作如下約定，對(duì)于P中公式A和B：(AvB)代表((「A)fB) (AaB)代表(「((「A)v([B)))(A?B)代表((AfB)A(BfA))注意，a、▽和》不是系統(tǒng)P的符號(hào)，只不過是為了使用方便而弓|入的符號(hào)。上述給出的公理是一種模式，其中每一條公理實(shí)際上代表了無限多個(gè)公式，因?yàn)槠渲械腁,B,C是一個(gè)符號(hào)，實(shí)際上可代表任意的公式，例如對(duì)于[A2],其中A可代表BfC得到：(((BfC)f(BfC))f(((BfC)fB)f((BfC)fC))注意在使用公式A替換公式B的符號(hào)C時(shí)，要將公式A替換B中所有的C。同樣分離規(guī)則也是一個(gè)模式。39【定義1.36］命題演算系統(tǒng)P中的證明是由P中公式組成的一個(gè)序列：A1,A2,…，An使得對(duì)每個(gè)i(1V"n)，下列兩個(gè)條件之一成立：. Ai是公理，或者. Ai是由上述序列中Ai之前的某兩個(gè)公式A廣Ak(1<j,k<n)應(yīng)用分離規(guī)則(M)得到。此時(shí)A#A2,…,An稱為An的一個(gè)證明，而An稱為P的一個(gè)內(nèi)定理，記為卜An?！酢咀⒔狻筷P(guān)于以上定義，需要注意以下幾點(diǎn)：卜也不是P中的符號(hào)，只是用卜An來表明An是一個(gè)內(nèi)定理。所謂的用兩個(gè)公式Aj,Ak應(yīng)用分離規(guī)則(M)得到，是指｛Aj,Ak｝=｛Aj,A,-Ai｝或｛%A卜｝=｛Ak,A卜fAi｝。若AyA2,…,An是An的一個(gè)證明，則對(duì)每個(gè)Ai(1<i<n)都有卜Ai。P的每個(gè)公理都是P中的內(nèi)定理。要證明一個(gè)公式A為P的內(nèi)定理，只要給出A的證明序列即可。【例子1.12】設(shè)A,B是P中的公式，證明：HA-B)f(AfA)【證明】. 卜Af(BfA) //公理［A1］. k(Af(BfA))f((AfB)f(AfA)) //公理［A2］,其中C用A代替40

. HA-B)”(AfA)⑴和⑵【例子1.13】設(shè)A是P中的公式，證明：HA-A)【證明】. 卜AT(BfA)fA)公理[Al]. k(Af((BfA)-A))f((A-(B—A))f(A-A)). 卜((A-(B-A))f(AfA))分離規(guī)則(M)及⑴和(2).HA-(B-A)//公理[Al]⑸.Ha-a)〃分離規(guī)則(M)及⑶和(4)【定理1.37】設(shè)A,B,C是P中的三個(gè)公式：.若卜A,且卜AfB,則卜B[2],若HA^B,且卜B-C,則【證明】山就是分離規(guī)則。對(duì)于⑵，證明如下：.HbfotatbfC))[Al]⑵.Hb-。〃前提.HAf(Bf。)〃分離規(guī)則(M)及〃分離規(guī)則(M)及////公理[A2]//41

.HAf(BfC))f((A-B)f(AfC))//[A2]//.Ha-b)f(afc)//分離規(guī)則.卜(A-B)〃前提⑺.Ha-。//分離規(guī)則I以后稱此定理的⑵為傳遞規(guī)則(Tr)?！纠?.15]證明：卜(「A)f(AfB)【證明】(1)? 卜([A)f ([A))//[Al]. 卜((「B)-(「A))f(A-B) //[A3]. 卜(「A)-(A-B)//傳遞規(guī)則【例子1.16]證明：[1]?kA.卜A—>(―?―iA)【證明】川的證明如下：. 卜(―?-iA)—>(-iA->―?―?―iA) 〃例子1.1542

[A3](2). 卜[A3](2). 卜(「A"[「A)f(「「A—A)//. 卜(「「A)f(「「A—A)//傳遞規(guī)則. 卜(「「A—(「「A'A))f((「「Ae「A)T」[A-A))〃[A2]⑸.卜(⑸.卜(一?―iA—>―?―iA)—>(―?―iA—>A)//分離規(guī)則. 卜(「「A"[A)//例子1.13. 卜(「「A-A)//分離規(guī)則[2]的證明如下：. 卜(i11A)—(1A)//[1]. 卜(「「「AeA)—(A"[A)//[A3]. 卜A"[A//分離規(guī)則【注解】通過以上例子，我們可發(fā)現(xiàn)在構(gòu)造公式的證明中可使用如下方法：.可靈活地使用公理，公理中的每個(gè)符號(hào)代表的是無限多的公式，公理中某個(gè)符號(hào)的所有出現(xiàn)可用某個(gè)公式替換。但這與教材p43頁的置換規(guī)則不同，教材沒有為命題邏輯公式的推理建立形式系統(tǒng)，而是根據(jù)命題邏輯公式的真值43來討論推理，因此有所謂的等值公式的置換，而我們這里所定義的形式系統(tǒng)還沒有涉及到真值賦值，這里的證明僅僅是符號(hào)的改寫。建立形式系統(tǒng)的方法更符合計(jì)算機(jī)的思維方式，因?yàn)槌绦驈谋举|(zhì)來說也是個(gè)形式系統(tǒng)，計(jì)算機(jī)將輸入變換到輸出也只是符號(hào)的改寫，至于程序員所認(rèn)為的程序功能，是程序員賦予程序的解釋，這種解釋計(jì)算機(jī)并不理解。也就是說，對(duì)于計(jì)算機(jī)學(xué)科，形式系統(tǒng)的推導(dǎo)和形式系統(tǒng)的含義是分開的，正是這種分離，才使得形式系統(tǒng)的推導(dǎo)可由計(jì)算機(jī)來機(jī)械地完成，而人們又可以賦予形式系統(tǒng)各種各樣的解釋來完成人們所需要的功能。.可使用分離規(guī)則和傳遞規(guī)則來構(gòu)造證明。.可使用已經(jīng)證明過的內(nèi)定理作為前提，這相當(dāng)于教材p43頁的結(jié)論弓|入規(guī)則。.教材中所討論的推理是在某種前提下的推理，下面我們?cè)诿}演算系統(tǒng)P中來定義這種推理。【定義1.38］設(shè)￡是P中的一個(gè)公式集，稱P中的公式序列：A#A2,…，nA為前提￡下推出An的一個(gè)證明，如果對(duì)每個(gè)Z(1<"n)，下列三個(gè)條件之一成立：. Ai是公理，或者. Af￡，或者. Ai是由上述序列中Ai之前的某兩個(gè)公式AjAk(1<j,k<n)應(yīng)用分離規(guī)則(M)得到。此時(shí)記為￡kAn。44【注解】對(duì)于上述定義，我們需要注意以下幾點(diǎn)：.￡中的公式不一定是P中的公理或內(nèi)定理，也不一定是有限集合。可以說￡是假設(shè)的前提，在前提￡下的證明實(shí)際上是將￡中的公式當(dāng)作“臨時(shí)公理”的一個(gè)證明。.易證：當(dāng)￡=。時(shí)，。卜A當(dāng)且僅當(dāng)卜A，或者說卜A就是沒有前提的證明。.易證：對(duì)P中的任意公式A及公式集￡和￡’，若￡匕￡，且￡'kA，則有￡kA。.易證，若Ae￡，則有￡kA?！纠?.17］證明：｛A,Bf(A-。｝k(Bf。【證明】.A//前提. Af(BfA)//公理［A1］. (B-A)//分離規(guī)則:(1)和(2). (Bf(Af。)//前提. (B