命題邏輯的形式系統(tǒng).ppt
《命題邏輯的形式系統(tǒng).ppt》由會員分享,可在線閱讀,更多相關(guān)《命題邏輯的形式系統(tǒng).ppt(39頁珍藏版)》請在裝配圖網(wǎng)上搜索。
第五章命題邏輯的形式系統(tǒng),第一節(jié)公理演算P系統(tǒng)的出發(fā)點第二節(jié)P系統(tǒng)定理的證明第三節(jié)P系統(tǒng)定理的演繹第四節(jié)自然演算NP系統(tǒng)第五節(jié)命題邏輯的系統(tǒng)特征,第一節(jié)公理演算P系統(tǒng)的出法點(1),(一)語法部分,關(guān)于對象語言的理論。1初始符號:(1)p,q,r,s(2),(3)(,)2形成規(guī)則(,A,B,C等為元變項):()初始符號(1)中的任意符號是一合式公式;()如果符號序列A是合式公式,則(A)是合式公式;()如果符號序列A和B是合式公式,則(AB)是合式公式;()只有符合以上三條的符號序列是合式公式。,第一節(jié)公理演算P系統(tǒng)的出法點(2),3定義(用D表示):D1(AB)=Df(AB);(蘊(yùn)涵)D2(AB)=Df(AB);(合取)D3(AB)=Df(AB)(BA);(等值)4公理(用A表示公理,用元符號表示其跟隨的公式是本系統(tǒng)要肯定的):A1(pp)p);(重言律,或去析公理)A2(p(pq);(析取引入律,或加析公理)A3(pq)(qp);(析取交換律,或交析公理)A4(qr)(pq)(pr)。(附加律,或蘊(yùn)析公理),第一節(jié)公理演算P系統(tǒng)的出法點(3),5推理規(guī)則(或變形規(guī)則,用R表示):R1(代入規(guī)則):在一個合式公式A中,用一合式公式B代替A中某變項的每一次出現(xiàn)(或?qū)中的全部代以B),從而得到合式公式A(/B)。即從A可得A(/B)。R2(分離規(guī)則):從A和AB(或(AB)可得B。R3(定義置換規(guī)則):定義兩邊的定義項可以互相替換。設(shè)B=DfC,A(B)為包含公式B的A公式,A(B/C)為在A中用公式C置換B的公式。即從A(B),可得A(B/C)。符號結(jié)合力規(guī)則:(1)公式最外面的一對括號可省略,若有不能省略的括號,其結(jié)合力最優(yōu)先;(2)真值聯(lián)結(jié)詞的結(jié)合力依下列次序遞減:,、,,(二)語義部分,關(guān)于符號和公式解釋的理論,2關(guān)于形成規(guī)則例:判定(qr)(pq)(pr)是否為公式。根據(jù)規(guī)則(1),p,q,r是公式,因為它們都是字母表中的字母,都屬于,進(jìn)而屬于A。根據(jù)規(guī)則(2),q是公式,因為q為A。根據(jù)規(guī)則(3),qr,pq,pr是公式,因為它們均為AB。再根據(jù)規(guī)則(2),(qr),(pq)是公式,它們可看作是A。再兩次根據(jù)規(guī)則(3),最后判定(qr)(pq)(pr)是公式,因為它們可看作是AB。,對公理的解釋,每一條公理都是本系統(tǒng)最基本的重言式,其真值,可用真值表方法判定。,關(guān)于推理規(guī)則(1),(1)關(guān)于代入規(guī)則(R1)該規(guī)則要求只有命題變項才能被代入,而其他多于一個符號的公式,例如p都不能被代入。但是,對于代入的公式B是沒有限制的。另外,如果在A中的出現(xiàn)不止一次,那么在代入時必須到處都用同一公式B代替,不能用不同的公式代替,也不能有的不代替。,舉例:,設(shè)公式A為:pqqpA中被代入的變項為:q代入的公式B為:q合法代入(A(/B):pqqp不合法代入:pqqp(未對在A中的所以出現(xiàn)即每一個q進(jìn)行代替),關(guān)于定義置換規(guī)則(R3),這里的置換和前面的代入是不同的。置換要求置換公式和被置換公式是等值(或可互相定義)的,而且是在被置換公式出現(xiàn)的某些位置上進(jìn)行替換。代入則不要求代入公式和被代入公式等值,但必須在被代入公式出現(xiàn)的所有位置上進(jìn)行替換。,舉例:,設(shè)公式A為:ppqA中被置換的公式B為:Pq置換的公式C為:qp(要求:B=dfC即pqqp)置換后所得公式(A(B/C):p(qp),關(guān)于符號省略規(guī)則,根據(jù)形成規(guī)則所構(gòu)造的公式,其符號過多也過于復(fù)雜。我們可以作些簡化。本規(guī)則是在保證不影響原公式固有層次的前提下,對公式的簡化。例如根據(jù)本規(guī)則,P公理可簡化為:A1pppA2ppqA3pqqpA4(qr)(pqpr),32P系統(tǒng)定理的證明,所謂P定理的證明,乃是一有窮的公式序列A1,An,其中每一公式Ai(1in)都適合以下條件之一:(1)Ai是一公理;(2)Ai是一已證定理;(3)Ai由本序列在先的一個公式經(jīng)代入或置換所得到;(4)Ai由本序列在先的兩個公式Aj和Ak(其形式分別為B和BAi,ji,ki)經(jīng)分離所得到;(5)最后一個公式An是要證明的定理。,定理的證明,T1(qr)(pq)(pr)證:1.(qr)(pqpr)公理42.(qr)(pqpr)1代入p/p3.(qr)(pq)(pr)2定義1置換,T2pp,證:1ppq公理22ppp1代入q/p3ppp公理14、(qr)(pq)(pr)定理15、(ppp)(ppp)(pp)4代入q/pp,r/p6(ppp)(pp)5,3分離7pp6,2分離,T3pp(略)T4pp,證:1pqqp公理32pppp1代入p/p,q/p3pp定理34pp3,2分離,T5pp(略)T6pp,證:1pp定理52pp1代入p/p3(qr)(pqpr)公理44(pp)(pppp)3代入q/p,r/p5pppp4,2分離6pp定理47pp5,6分離8pqqp公理39(pp)(pp)8代入q/p10pp9,7分離11pp10定義1置換,T7(pq)(qp),證:1pp定理52qq1代入p/q3(qr)(pqpr)公理44(qq)(pqpq)3代入r/q,p/p5pqpq4,2分離6pqqp公理37(pq)(qp)6代入p/p,q/q8(qr)(pq)(pr)定理19(pqqp)(pqpq)(pqqp)8代入q/pq,r/qp,p/pq10(pqpq)(pqqp)9,7分離11pqqp10,5分離12(pq)(qp)11定義1置換,T8(pq)pq(略)T9pq(pq),證:1pp定理52pq(pq)1代入p/pq3pq(pq)2定義2置換,定理的簡化證明,使證明簡化的一個主要方法是把本系統(tǒng)中的公理和已證定理當(dāng)作推理規(guī)則使用。這些規(guī)則稱作導(dǎo)出規(guī)則。列舉如下:1.析取交換規(guī)則:從AB可得BA公理32.附加規(guī)則:從BC可得ABAC。公理43.三段論規(guī)則:從BC和AB可得AC。定理14.假言易位規(guī)則:從AB可得BA。定理75.等值構(gòu)成規(guī)則:從AB和BA可得AB。定義36.等值置換規(guī)則:如果A和B等值,即AB,則從A可得B。表示任意合式公式,其中A(或B)是的子公式。A,B可相互置換。這是定義置換規(guī)則的擴(kuò)充。,導(dǎo)出規(guī)則2,7結(jié)合括號省略規(guī)則:(1)從(AB)C可得ABC;(2)從(AB)C可得ABC。8.條件互易規(guī)則:從A(BC)可得B(AC)。9合取構(gòu)成規(guī)則:從A(BC)可得ABC。10條件融合規(guī)則:從A(AB)可得AB。以上8,9,10三條規(guī)則都是相應(yīng)定理的概括。11求否定規(guī)則:設(shè)A為一公式,A中沒有和出現(xiàn)(或已定義為,或),其否定式(記為A-)用以下方法可得:將,互換,同時將和互換(為任一命題變項)。例如,p(qr)r,其否定式為p(qr)r。12對偶規(guī)則:設(shè)A,B為兩個公式,在其中和不出現(xiàn)。A和B是在A和B中把和互換的結(jié)果。我們可有:(1)從AB可得BA;(2)從AB可得AB。,一些已證或待證定理的簡化證明,T2pp證:1ppq公理22ppp1代入q/p3ppp公理14pp2,3三段論T4pp證:1pp公理32pp1析取交換,簡化證明(2),T6pp證:1pp定理52pp1代入p/p3pppp2附加4pp定理45pp3,4分離6pp5析取交換7pp6定義1置換T10pp證:1pp定理52pp定理63pp1,2等值構(gòu)成,簡化證明(3),T7(pq)(qp)證:1pqqp公理32pqqp1代入p/p3pqqp2等值置換4(pq)(qp)3定義置換1T11(pq)pq證:1(pq)pq定理82pq(pq)定理93(pq)pq1,2等值構(gòu)成T12(pq)pq證:1(pq)pq定理112(pq)pq1對偶,簡化證明(4),T13pqpT14pqqpT15pqpT16pqqT17p(qr)q(pr)T18p(qr)(pq)rT19(pq)rp(qr)T20p(qr)(pq)rT21q(pr)p(qr)T22p(qpq)T23(p(qr)(q(pr),簡化證明(5),T24(p(qr)(pqr)T25(p(pq)(pq)T26p(qr)(pq)(pr)T27p(qr)(pq)(pr)T28(pq)(pr)(pqr)T29pp(qqr)T30pp(qqr)T31(pq)(pq)T32(pq)(pq)(qp)T33(pq)(pq)(pq)T34(pq)(pq)(pq)以上只是P系統(tǒng)的部分定理,請讀者自證。,33P系統(tǒng)定理的演繹,令是P中的一組公式,它們可以是P中的公理或定理,也可以不是。P中以為前提的演繹是一有窮的公式序列A1,An,其中每一公式Ai(1in)都適合下列條件之一:(1)Ai是一公理或定理;(2)Ai是中的一個公式(記為Hyp);(3)Ai由本序列在先的一個或兩個公式根據(jù)推理規(guī)則(系統(tǒng)內(nèi)的基本變形規(guī)則和導(dǎo)出規(guī)則,但對假設(shè)前提公式不得使用代入規(guī)則)而得到。如果這樣一個演繹存在,我們就稱該序列最后的一個公式An以為前提是可演繹的,或稱An為P中的后承,記為An。當(dāng)假設(shè)前提集為空集時,P中關(guān)于空前提的演繹就是P中的一個證明。A是P中的定理,記作A,簡記成A。,演繹定理,令A(yù)、B為P中任意公式,為P中任何公式集,如果,AB,那么AB。意即如P中一前提集和另一前提A能推出B,那么,由本身可推出AB。當(dāng)為空集時,如果由一前提A能推出B,那么,AB可無前提推出,即為P的定理(AB)。,反證定理,令A(yù)為P中任意公式,為P中任何公式集,如果,A,那么A。意即如果從P的一前提公式集和一命題公式A的否定推出了矛盾,則從該前提集可推出A。當(dāng)為空集時,如果由一前提A能推出,那么,A可無前提推出,即A為P的定理(A)。,對P系統(tǒng)部分定理的演繹證明(1),T13pqp證:1pHyp2ppq公理23pq2,1分離4pqqp公理35qp4,3分離6pqp1,5演繹定理(又一附加的導(dǎo)出規(guī)則:從p可得qp),演繹證明(2),T14pqqp證:1pqHyp2(pq)1定義2置換3pqqp公理34(qp)(pq)3假言易位5(pq)(qp)4代入p/q,q/p6(qp)5,2分離7qp6定義2置換8pqqp1,7演繹定理(合取交換的導(dǎo)出規(guī)則:從pq可得qp),演繹證明(3),T15pqp證:1pqHyp2(pq)1定義2置換3ppq公理24ppq3代入p/p,q/q5(pq)p4假言易位(R導(dǎo)4)6p5,2分離7p6等值置換(R導(dǎo)6)8pqp1,7演繹定理(導(dǎo)出規(guī)則:從pq可得p。與此相同的方法,可證定理T16pqq,得導(dǎo)出規(guī)則:從pq可得q。它們是合取分解規(guī)則),演繹證明(4),T22p(qpq)證:1pHyp2pp定理23pqpq2代入p/pq4(pq)(pq)3定義1置換5(pq)(pq)4等值置換6p(q(pq)5析取結(jié)合(R導(dǎo)7)7q(pq)6,1分離8qpq7定義置換9p(qpq)1,8演繹定理(合取組合的導(dǎo)出規(guī)則:從p和q可得pq),演繹證明(5),T23(p(qr)(q(pr)證:1p(qr)Hyp2qHyp3pHyp4qr1,3分離5r4,2分離6pr3,5演繹定理7q(pr)2,6演繹定理8(p(qr)(q(pr)1,7演繹定理(由于演繹定理的引入,所有已證定理都可看作是一導(dǎo)出規(guī)則,而且象上節(jié)導(dǎo)出規(guī)則中前提與結(jié)論前的斷定符都可去掉。如“換頭”可表示為:從p(qr)可得q(pr)。),演繹證明(6),T24(p(qr)(pqr)該定理的證明分兩步,先證前件蘊(yùn)涵后件,再證后件蘊(yùn)涵前件。即:證:(p(qr)(pqr)1p(qr)Hyp2pqHyp3p2合取分解4q2合取分解5qr1,3分離6r5,4分離7pqr2,6演繹定理8(p(qr)(pqr)1,7演繹定理(合取構(gòu)成的導(dǎo)出規(guī)則:從p(qr)可得pqr),演繹證明(7),再證:(pqr)(p(qr)1pqrHyp2pHyp3qHyp4pq2,3合取組合5r1,4分離6qr3,5演繹定理7p(qr)2,6演繹定理8(pqr)(p(qr)1,7演繹定理,35命題邏輯的系統(tǒng)特征,當(dāng)我們把命題演算系統(tǒng)作為研究對象時,我們考察的是形式不同的各命題邏輯系統(tǒng)共同的特征,也稱元邏輯問題,即一命題邏輯系統(tǒng)的所有可證公式或者說定理是否都是重言式,即可證的是否都是真的?這個問題稱作系統(tǒng)的一致性問題。另一個問題是,是否所有命題邏輯的重言式都在一命題邏輯系統(tǒng)中可證,即真的是否都可證?這個問題稱作系統(tǒng)的完全性問題。另外還有公理獨立性問題,即一公理系統(tǒng)的每條公理,彼此應(yīng)該互相獨立,不能由一個公理而推出另一個公理;各演算系統(tǒng)間的關(guān)系問題,如P系統(tǒng)和NP系統(tǒng)是等價的,即兩系統(tǒng)的定理集是相同的,相對于某些給出的推理規(guī)則,能彼此證明對方的公理和定理的是自己的公理或定理。以下我們僅考察一致性、完全性和獨立性問題。,(一)一致性,一命題邏輯的形式系統(tǒng)是一致的,即該系統(tǒng)的所有定理都是重言式(語義一致)?;蛘哒f并非該系統(tǒng)的一切公式都是定理(語法一致)?;蛘哒f對于該系統(tǒng)的任一公式A而言,A和A至少有一個不是該系統(tǒng)中的定理(古典的語法一致)。如何能確定或證明一個命題演算系統(tǒng)的所有定理都是重言式?通常的方法是為該系統(tǒng)找到一個解釋,使得:(1)命題演算的公理都是真命題(重言式);(2)應(yīng)用命題演算的推理規(guī)則和定義,都能保證從重言式只能推出重言式。如果條件(1)、(2)都滿足了,應(yīng)用該推理規(guī)則從公理所推出的所有定理也是重言式,則證明了該系統(tǒng)是(語義)一致的。,(二)完全性,一命題邏輯的形式系統(tǒng)是完全的,即一切重言式都在該系統(tǒng)中可證(廣義的、相對的或語義的完全性)。或者說,如果把在該系統(tǒng)不可證的公式作為新公理引進(jìn)該系統(tǒng),就會導(dǎo)致矛盾而使該系統(tǒng)不一致(狹義的、絕對的或語法的完全性)?;蛘哒f,對于該系統(tǒng)任一合式公式A而言,或者A是可證的,或者A是可證的(古典的完全性)??梢宰C明P系統(tǒng)是語義完全的和語法完全的。,(三)獨立性,所謂獨立性就是公理的不可推出性。根據(jù)給定的推理規(guī)則,如果從一類公式推不出某一特定公式,那么這一公式對于那一類公式就是獨立的。不過,若應(yīng)用某些推理規(guī)則推不出來,而用另一些推理規(guī)則就可能推出來。所以,獨立性總是相對于已給定的推理規(guī)則而言的。可以證明P系統(tǒng)的公理都是獨立的。,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 命題邏輯 形式 系統(tǒng)
鏈接地址:http://ioszen.com/p-13205158.html