《命題邏輯的推理理論.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《命題邏輯的推理理論.ppt（13頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

,漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系,第三章命題邏輯的推理理論,2020年5月19日8時(shí)52分,第二章命題邏輯等值演算,推理的形式結(jié)構(gòu)自然推理系統(tǒng)P知識(shí)點(diǎn)：推理的形式結(jié)構(gòu)、推理理論、自然系統(tǒng)P、推理規(guī)則教學(xué)要求：深刻理解和掌握命題邏輯中的基本推理方法教學(xué)重點(diǎn)：推理理論、推理規(guī)則學(xué)時(shí):2,2020年5月19日8時(shí)52分,3.1推理的形式結(jié)構(gòu),論證是指由一些前提出發(fā)得到某個(gè)結(jié)論，在數(shù)理邏輯中需要討論論證的有效性提出正確的推理規(guī)則和可行的推理方法A1,A2,…,An為前提,B為結(jié)論稱{A1,A2,…,An}┝B為推理的形式結(jié)構(gòu)定理3.1命題公式A1,A2,…,An推B是正確的當(dāng)且僅當(dāng)A1?A2?…?An?B為重言式,即A1?A2?…?An?B并稱B為前提A1,A2,…,An的有效結(jié)論或稱B為前提A1,A2,…,An的邏輯結(jié)果當(dāng)前提為真時(shí)結(jié)論也為真,但推理正確并不能保證有效結(jié)論B一定為真例如：設(shè)p為“太陽從西邊升起”,q為”太陽從東邊落下”p?q為“如果太陽從西邊升起則太陽從東邊落下”推理{p,p?q}┝q是正確的,即q是前提的有效結(jié)論,但q是個(gè)假命題,,2020年5月19日8時(shí)52分,3.1推理的形式結(jié)構(gòu),推理的形式結(jié)構(gòu):前提:A1,A2,…,An結(jié)論:B重要的推理定律A∧B?A,A∧B?B(化簡(jiǎn)律)A?A∨B,B?A∨B(附加律)(A→B)∧A?B(假言推論)(A→B)∧┐B?┐A(拒取式)(A∨B)∧┐B?A(析取三段論)(A→B)∧(B→C)?A→C(假言三段論)(A?B)∧(B?C)?A?C(等價(jià)三段論)(A→B)∧(C→D)∧(A∨C)?(B∨D)(構(gòu)造性二難)(A→B)∧(┐A→B)?B構(gòu)造性二難(特殊形式)(A→B)∧(C→D)∧(┐B∨┐D)?(┐A∨┐C)破壞性二難,,2020年5月19日8時(shí)52分,3.1推理的形式結(jié)構(gòu),論證的方法真值表法等值演算法將推理過程形式化,證明公式A1?A2?…?An?B是重言式即證明(A1?A2?…?An?B)?1,,,形式系統(tǒng)一般分為兩類一類是自然推理系統(tǒng)，它的特點(diǎn)是從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算，得到的最后命題公式是推理的結(jié)論（有時(shí)稱為有效的結(jié)論，它可能是重言式，也可能不是）一類是公理推理系統(tǒng)，它只能從若干給定的公理出發(fā)，應(yīng)用系統(tǒng)中推理規(guī)則進(jìn)行推理演算，得到的結(jié)論是系統(tǒng)中的重言式，稱為系統(tǒng)中的定理。,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,定義3.2一個(gè)形式系統(tǒng)I由下面四個(gè)部分組成：（1）非空的字符表集，記作A(I)（2）A(I)中符號(hào)構(gòu)造的合式公式集，記作E(I)（3）E(I)中一些特殊的公式組成的公理集，記作AX(I)（4）推理規(guī)則集，記作R(I)可以將I記為其中是I的形式語言系統(tǒng)為I的形式演算系統(tǒng)。定義3.3自然推理系統(tǒng)P定義如下：1．字母表（1）命題變項(xiàng)符號(hào)：p，q，r，…,pi，qi，ri，…（2）聯(lián)結(jié)詞符號(hào)：┐,∧,∨,→,?（3）括號(hào)和逗號(hào)：(,)，，2．合式公式同定義1.63．推理規(guī)則,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,定理3.1{A1,A2,…,An}┝Ai,i=1,2,…,n證明因?yàn)锳1?A2?…?An?(A1?A2?…?Ai–1?Ai+1?…?An)?Ai?Ai所以{A1,A2,…,An}┝Ai定理3.2若{A1,A2,…,An}┝Bi,i=1,2,…,m且{B1,B2,…,Bm}┝C,則{A1,A2,…,An}┝C證明由重言蘊(yùn)涵的性質(zhì)和題設(shè)可知A1?A2?…?An?B1?B2?…?Bm再由重言蘊(yùn)涵的傳遞性可知A1?A2?…?An?C,即{A1,A2,…,An}┝C定理3.3若{A1,A2,…,An,B}┝C,則{A1,A2,…,An}┝(B?C)證明因?yàn)閧A1,A2,…,An,B}┝C,所以1?A1?A2?…?An?B?C??(A1?A2?…?An?B)?C??(A1?A2?…?An)??B?C??(A1?A2?…?An)?(B?C)?(A1?A2?…?An)?(B?C)即{A1,A2,…,An}┝B?C,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,P規(guī)則在推演過程中可以隨時(shí)引用前提T規(guī)則在推演過程中可以隨時(shí)引用前面已經(jīng)得到的結(jié)論CP規(guī)則若{A1,A2,…,An,B}┝C則{A1,A2,…,An}┝(B?C)B稱為附加前提在推理過程中可以隨時(shí)使用重言等價(jià)式(E)在推理過程中可以隨時(shí)使用重言蘊(yùn)涵式(I)在推理過程中可以隨時(shí)引用置換規(guī)則和代入替則,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,直接證明法：由一組前提遵循P規(guī)則和T規(guī)則,根據(jù)已知的重言等價(jià)式和重言蘊(yùn)涵式推演出有效結(jié)論的論證方法例1前提：p∨q,q→r,p→s,┐s結(jié)論：r∧(p∨q)證明：①p→s前提引入②┐s前提引入③┐p①②拒取式④p∨q前提引入⑤q③④析取三段論⑥q→r前提引入⑦r⑤⑥假言推理⑧r∧(p∨q)⑦④合取此證明的序列長(zhǎng)為8，最后一步為推理的結(jié)論，所以推理正確，r∧(p∨q)是有效結(jié)論。,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,例2:在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：若數(shù)a是實(shí)數(shù)，則它不是有理數(shù)就是無理數(shù)；若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)；a是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以a是無理數(shù)。解首先將簡(jiǎn)單命題符號(hào)化：證明：①p∧┐s前提引入②p①化簡(jiǎn)律③┐s①化簡(jiǎn)律④p→(q∨r)前提引入⑤q∨r②④假言推理⑥┐s→┐q前提引入⑦┐q③⑥假言推理⑧r⑤⑦假言推理,設(shè)p:a是實(shí)數(shù),q:a是有理數(shù),r:a是無理數(shù),s:a能表示成分?jǐn)?shù)推理的形式結(jié)構(gòu)為{p→(q∨r),┐s→┐q,p∧┐s}┝r,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,間接證明法：由一組前提遵循P規(guī)則、T規(guī)則和CP規(guī)則推演出有效結(jié)論,或者將否定結(jié)論作為附加前提,利用P規(guī)則和T規(guī)則得出矛盾式的論證方法。后一種情形又稱為反證法在構(gòu)造形式結(jié)構(gòu)為(A1∧A2∧…∧Ak)┝B的推理證明中，如果將┐B作為前提能推出矛盾來，比如說得出(A∧┐A)，則說明推理正確。其原因如下：(A1∧A2∧…∧Ak)→B?┐(A1∧A2∧…∧Ak)∨B?┐(A1∧A2∧…∧Ak∧┐B)若(A1∧A2∧…∧Ak∧┐B)為矛盾式，正說明(A1∧A2∧…∧Ak)→B為重言式，即(A1∧A2∧…∧Ak)?B原故推理是正確,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,例3在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去看電影。解將簡(jiǎn)單命題符號(hào)化：前提：(p∧q)→r,┐s∨p,q結(jié)論：s→r證明：用附加前提證明法。①s附加前提引入②┐s∨p前提引入③p①②析取三段論④(p∧q)→r前提引入⑤q前提引入⑥p∧q③⑤合取⑦r④⑥假言推理,設(shè)p:小張去看電影,q:小王去看電影,r:小李去看電影,s:小趙去看電影,,2020年5月19日8時(shí)52分,3.2自然推理系統(tǒng)P,例4：在自然推理系統(tǒng)A中構(gòu)造下面推理的證明。如果小張守第一壘并且小李向B隊(duì)投球，則A隊(duì)將取勝；或者A隊(duì)未取勝，或者A隊(duì)獲得聯(lián)賽第一名；A隊(duì)沒有獲得聯(lián)賽的第一名；小張守第一壘。因此，小李沒有向B隊(duì)投球。證明:①q結(jié)論的否定引入②┐r∨s前提引入③┐s前提引入④┐r②③析取三段論⑤(p∧q)→r前提引入⑥┐(p∧q)④⑤假言推理⑦┐p∨┐q⑥置換⑧p前提引入⑨┐q⑦⑧析取三段論⑩q∧┐q①⑨合取由于最后一步q∧┐q?0，即原推理正確,先將簡(jiǎn)單命題符號(hào)化設(shè)p:小張守第一壘q:小李向B隊(duì)投球r:A隊(duì)取勝s:A隊(duì)獲得聯(lián)賽第一名推理的形式結(jié)構(gòu){(p∧q)→r,┐r∨s,┐s,p}┝┐q,,