命題邏輯的推理理論

1、第三章第三章命題邏輯的推理理論命題邏輯的推理理論?推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)?自然推理系統(tǒng)自然推理系統(tǒng)P關(guān)于“推理”?推理：指從推理：指從前提前提出發(fā)推出出發(fā)推出結(jié)論結(jié)論的思維過程的思維過程，前提前提是已知命題公式集合，是已知命題公式集合，結(jié)論結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。公式。數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來研究數(shù)數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來研究數(shù)學(xué)中的推理。學(xué)中的推理。推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)問題的引入問題的引入推理舉例推理舉例:(1) 正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和上有界正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和上有界 .(2) 若若A? C?

2、B? D，則，則A? B且且C? D.推理推理: 從前提出發(fā)推出結(jié)論的思維過程從前提出發(fā)推出結(jié)論的思維過程上面上面(1)是正確的推理，而是正確的推理，而(2)是錯(cuò)誤的推理是錯(cuò)誤的推理.證明證明: 描述推理正確或錯(cuò)誤的過程描述推理正確或錯(cuò)誤的過程 . 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)定義定義設(shè)設(shè)A1，A2，Ak，B都是命題公式都是命題公式,若對(duì)于若對(duì)于A1，A2，Ak，B中出現(xiàn)的命題變中出現(xiàn)的命題變項(xiàng)的任意一組賦值，項(xiàng)的任意一組賦值，A1?A2? Ak均為假，均為假，或當(dāng)或當(dāng)A1?A2?Ak為真時(shí)為真時(shí),B也為真也為真, 則稱由則稱由A1,A2,Ak推推B的的推理正確推理正確 ,并稱并稱B是有效的是

3、有效的結(jié)論；結(jié)論； 否則否則推理不正確（錯(cuò)誤）推理不正確（錯(cuò)誤）.說明（1）：?由前提由前提A1，A2 ，Ak推結(jié)論推結(jié)論B的推理是否正確的推理是否正確與諸前提的排列次序無(wú)關(guān)。與諸前提的排列次序無(wú)關(guān)。因而前提中的公式不一定是序列，而是一個(gè)有限因而前提中的公式不一定是序列，而是一個(gè)有限公式集合，記為公式集合，記為?？蓪⒂煽蓪⒂赏仆艬的推理記為的推理記為B，若推理是正確?的，則記為|=B，否則記為 |? B。?這里可以稱B 和A1，A2 ，Ak B 為推理的形式結(jié)構(gòu)。說明（2）設(shè)設(shè)A1，A2 ，Ak，B中共出現(xiàn)中共出現(xiàn)n個(gè)命題變項(xiàng)，對(duì)于任個(gè)命題變項(xiàng)，對(duì)于任一組賦值一組賦值a1a2an（ai0或或1

4、，i1，2，n），前），前提和結(jié)論的取值情況有以下四種：提和結(jié)論的取值情況有以下四種：（1）A1?A2?Ak 為為0，B為為0；?（2）A1?A2?Ak 為為0，B為為1；（3）A1?A2?Ak 為為1，B為為0；（4）A1?A2?Ak 為為1，B為為1。由定義可知，只要不出現(xiàn)（由定義可知，只要不出現(xiàn)（ 3）中的情況，推理就）中的情況，推理就是正確的，因而判斷推理正確與否，就是判斷是否會(huì)是正確的，因而判斷推理正確與否，就是判斷是否會(huì)出現(xiàn)（出現(xiàn)（3）中的情況。）中的情況。例3.1 判斷下列推理是否正確?（1） p， p ?q q?（2） p， q ?p q解：只要寫出前提的合取式與結(jié)論的真值表，

5、看是解：只要寫出前提的合取式與結(jié)論的真值表，看是否出現(xiàn)前提為真，而結(jié)論為假的情況即可。否出現(xiàn)前提為真，而結(jié)論為假的情況即可。由下面真值表可看出，（由下面真值表可看出，（ 1）推理正確，（）推理正確，（推理不正確。推理不正確。2）p q p ?（ p ?q ）q 0 0 0 00 1 0 11 0 0 01 1 1 1 p q p ?（ q ?p ）q0 0 0 00 1 0 11 0 1 01 1 1 1定理定理3.1命題公式A1，A2 ，Ak推B的推理正確當(dāng)且僅當(dāng)：（A1?A2?Ak ）?為重言式。為重言式。證明：必要性若命題公式A1，A2 ，Ak推B的推理正確，則不會(huì)出現(xiàn)A1?A2?Ak為

6、真，而B為假的情況，因而在任何賦值下，蘊(yùn)涵式（A1?A2?Ak ）?均為真，故為重言式。證明：充分性若蘊(yùn)涵式（A1?A2?Ak ）?為重言式，則對(duì)于任何賦值此重言式均為真，因而不會(huì)出現(xiàn)前件為真后件為假的情況。即在任何賦值下，或者A1?A2?Ak為假，或者A1?A2?Ak和?同時(shí)為真，這正符合定義3.1中推理正確的定義。分析：由定理3.1可知，可以將由前提A1, A2, , Ak 推B的推理的形式結(jié)構(gòu)A1?A2?Ak B轉(zhuǎn)換成蘊(yùn)涵式（A1?A2?Ak ）?推理前提的合取式成了蘊(yùn)涵式的前件，結(jié)論成了蘊(yùn)涵式的后件，并將推理正確A1?A2?Ak | B轉(zhuǎn)換成A1?A2?Ak ?B其中?是一種元語(yǔ)言符號(hào)

7、，表示蘊(yùn)涵式為重言式。判斷推理是否正確的方法?真值表法真值表法?等值演算法等值演算法?主析取范式法主析取范式法?構(gòu)造證明法構(gòu)造證明法說明：當(dāng)命題變項(xiàng)比較少時(shí)，用前說明：當(dāng)命題變項(xiàng)比較少時(shí)，用前 3 3個(gè)方法比較方個(gè)方法比較方便便, , 此時(shí)采用形式結(jié)構(gòu)此時(shí)采用形式結(jié)構(gòu)“A1?A2?Ak? B”. 而在而在構(gòu)造證明時(shí)，采用構(gòu)造證明時(shí)，采用“前提前提 : A1, A2, , Ak, 結(jié)論結(jié)論: B”.例3.2 判斷下面推理是否正確解上述類型的推理問題，首先應(yīng)將簡(jiǎn)單命題符號(hào)化。然后分別寫出前提、結(jié)論、推理的形式結(jié)構(gòu)，接著進(jìn)行判斷。（1）若）若a能被能被4整除，則整除，則a能被能被2整除。整除。a能被

8、能被4整除，整除，所以所以a能被能被2整除。整除。（1）設(shè) p：a能被4整除q：a能被2整除前提：p ?q，p結(jié)論：q推理的形式結(jié)構(gòu)：（p ?q）?p ?q 可知此推理正確，即 （p ?q）?p ?q 。（2）若）若a能被能被4整除，則整除，則a能被能被2整除。整除。a能被能被2整除，整除，所以所以a能被能被4整除。整除。?（2）設(shè) p：a能被4整除q：a能被2整除前提：p ?q，q結(jié)論：p推理的形式結(jié)構(gòu)：（p ?q）?q ?p 可知上式不為重言式，所以此推理不正確，即 （p ?q）?p ?q 。（3）下午馬芳或去看電影或去游泳。她沒去看電）下午馬芳或去看電影或去游泳。她沒去看電影。所以，她去

9、游泳了。影。所以，她去游泳了。（3）設(shè)）設(shè) p：馬芳下午去看電影：馬芳下午去看電影q：馬芳下午去游泳：馬芳下午去游泳前提：前提：p ?q，?p ?結(jié)論：結(jié)論：q推理的形式結(jié)構(gòu)：（推理的形式結(jié)構(gòu)：（ p ?q）?p ）?q用等值演算法可知上市為重言式，所以，推理正用等值演算法可知上市為重言式，所以，推理正確。確。?（4）若下午氣溫超過）若下午氣溫超過30度，則王小燕必去游泳。度，則王小燕必去游泳。若她去游泳，她就不去看電影。所以，若王小燕沒若她去游泳，她就不去看電影。所以，若王小燕沒去看電影，下午氣溫必超過了去看電影，下午氣溫必超過了 30度。度。（4）設(shè)）設(shè) p：下午氣溫超過：下午氣溫超過30

10、度度q： 王小燕去游泳王小燕去游泳r： 王小燕去看電影王小燕去看電影前提：前提： p ?q， q ? ?r結(jié)論：結(jié)論：?r ?p推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)：（ p ?q ）?（q ? ?r）?（?r ?p）用主析取范式法可知上式不是重言式，所以用主析取范式法可知上式不是重言式，所以推理不正確。推理不正確。?重要的推理定律（重言蘊(yùn)涵式重要的推理定律（重言蘊(yùn)涵式 ）A ?(A?B)附加律附加律(A?B)? A化簡(jiǎn)律化簡(jiǎn)律(A? B)?A ? B假言推理假言推理(A? B)? B ? ? A拒取式拒取式(A?B)? B ? A析取三段論析取三段論(A? B)?(B? C)?(A? C)假言三段論

11、假言三段論(A? B)?(B? C)?(A? C)等價(jià)三段論等價(jià)三段論(A? B)?(C? D)?(A?C) ?(B?D) 構(gòu)造性二難構(gòu)造性二難推理定律推理定律 (續(xù)續(xù))(A? B)?(? A? B)?(A? A)? B構(gòu)造性二難（特殊形式）構(gòu)造性二難（特殊形式）(A? B)?(C? D)?(? B? D)?(? A? C)破壞性二難破壞性二難說明：說明：(1)A, B, C為元語(yǔ)言符號(hào)，代表任意的命題公式。為元語(yǔ)言符號(hào)，代表任意的命題公式。(2)若某推理符合某條推理定律，則它自然是正確的若某推理符合某條推理定律，則它自然是正確的 .(3)A? B產(chǎn)生兩條推理定律產(chǎn)生兩條推理定律: A ? B

12、, B ? A.實(shí)例實(shí)例例例 判斷下面推理是否正確判斷下面推理是否正確(1) 若今天是若今天是1號(hào)，則明天是號(hào)，則明天是5號(hào)號(hào). 今天是今天是1號(hào)號(hào). 所所以明天是以明天是5號(hào)號(hào).解解 設(shè)設(shè)p：今天是：今天是1號(hào)，號(hào)，q：明天是：明天是5號(hào)號(hào).證明的形式結(jié)構(gòu)為證明的形式結(jié)構(gòu)為:(p? q)?p? q證明（用等值演算法）證明（用等值演算法）(p? q)?p? q?(? p?q)?p)?q? p? q?q ?1得證推理正確得證推理正確實(shí)例實(shí)例 (續(xù)續(xù))(2) 若今天是若今天是1號(hào)，則明天是號(hào)，則明天是5號(hào)號(hào). 明天是明天是5號(hào)號(hào). 所以今天是所以今天是1號(hào)號(hào).解解 設(shè)設(shè)p：今天是：今天是1號(hào)，號(hào)，

13、q：明天是：明天是5號(hào)號(hào).證明的形式結(jié)構(gòu)為證明的形式結(jié)構(gòu)為:(p? q)?q? p證明（用主析取范式法）證明（用主析取范式法）(p? q)?q? p?(? p?q)?q? p? ?(? p?q)?q)?p? ? q?p?(? p? q)?(p? q)?(p? q)?(p?q)? m0?m2?m3結(jié)果不含結(jié)果不含m1,故故01是成假賦值，所以推理不正確是成假賦值，所以推理不正確. 重要的推理定律（重言蘊(yùn)涵式重要的推理定律（重言蘊(yùn)涵式 ）A ?(A?B)附加律附加律(A?B)? A化簡(jiǎn)律化簡(jiǎn)律(A? B)?A ? B假言推理假言推理(A? B)? B ? ? A拒取式拒取式(A?B)? B ? A

14、析取三段論析取三段論(A? B)?(B? C)?(A? C)假言三段論假言三段論(A? B)?(B? C)?(A? C)等價(jià)三段論等價(jià)三段論(A? B)?(C? D)?(A?C) ?(B?D) 構(gòu)造性二難構(gòu)造性二難推理定律推理定律 (續(xù)續(xù))(A? B)?(? A? B)?(A? A)? B構(gòu)造性二難（特殊形式）構(gòu)造性二難（特殊形式）(A? B)?(C? D)?(? B? D)?(? A? C)破壞性二難破壞性二難說明：說明：A, B, C為元語(yǔ)言符號(hào)為元語(yǔ)言符號(hào)若某推理符合某條推理定律，則它自然是正確的若某推理符合某條推理定律，則它自然是正確的A? B產(chǎn)生兩條推理定律產(chǎn)生兩條推理定律: A ?

15、 B, B ? A3.2 自然推理系統(tǒng)P?判斷推理是否正確的三種常用方法：1.真值表技術(shù)2.演繹法3.間接證明方法當(dāng)命題變項(xiàng)較多時(shí)，以上三種方法的演算量太大，此時(shí)可考慮推理證明的方法。而要構(gòu)造嚴(yán)謹(jǐn)?shù)淖C明必須要在形式系統(tǒng)中進(jìn)行。形式系統(tǒng)的定義形式系統(tǒng)的定義?一個(gè)形式系統(tǒng)一個(gè)形式系統(tǒng)I由下面四個(gè)部分組成：由下面四個(gè)部分組成：（1）非空的字母表，記做）非空的字母表，記做 A(I)。（2） A(I)中符號(hào)構(gòu)造的合式公式集，記做中符號(hào)構(gòu)造的合式公式集，記做 E(I)。（3） E(I)中一些特殊的公式組成的公理集，記做中一些特殊的公式組成的公理集，記做 Ax(I)（4）推理規(guī)則集，記做）推理規(guī)則集，記做

16、R(I)。可以將可以將I記為記為4元組元組。其中。其中是是I的形式語(yǔ)言系統(tǒng)，而的形式語(yǔ)言系統(tǒng)，而 為為I的形式演算系統(tǒng)。的形式演算系統(tǒng)。形式系統(tǒng)的分類（1）自然推理系統(tǒng)自然推理系統(tǒng)它的特點(diǎn)是從任意給定的前提前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算，得到的最后命題公式是推理的結(jié)論（可能是重言式，也可能不是可能是重言式，也可能不是）。（2）公理推理系統(tǒng)公理推理系統(tǒng)它的特點(diǎn)是只能從若干條給定的公理公理出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行演算，得到的是系統(tǒng)中的定理（是是重言式重言式）。定義3.3 自然推理系統(tǒng)P定義如下：1、字母表（2、合式公式3、1）命題變項(xiàng)符號(hào)：p，q，r，2）聯(lián)結(jié)詞符號(hào)：? ,? ?

17、,? ?, ?,?3）括號(hào)與逗號(hào) ： （ ） ， ，(參見定義1.6 P10）推理規(guī)則?推理規(guī)則推理規(guī)則（1）前提引入規(guī)則 ：在證明的任何步驟上都可以引入前提。（2）結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以做為后續(xù)證明的前提。（3）置換規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以作為后續(xù)證明的前提。推理規(guī)則推理規(guī)則（續(xù)）（續(xù)）(4) 假言推理規(guī)則假言推理規(guī)則A? BA B(5) 附加規(guī)則附加規(guī)則A A?B(6) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(guī)則A?BA (7) 拒取式規(guī)則拒取式規(guī)則A? B? B? A(8) 假言三段論規(guī)則假言三段論規(guī)則A? BB? C A? C推理規(guī)則推理規(guī)則( (續(xù)續(xù)) )(9)

18、析取三段論規(guī)則析取三段論規(guī)則A?B? B A(10)構(gòu)造性二難推理構(gòu)造性二難推理規(guī)則規(guī)則A? BC? DA?C B?D(11) 破壞性二難推理破壞性二難推理規(guī)則規(guī)則A? BC? D? B? D? A? C(12) 合取引入規(guī)則合取引入規(guī)則AB A?B構(gòu)造證明構(gòu)造證明 直接證明法直接證明法?例例3.3 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明；中構(gòu)造下面推理的證明；（1） 前提：前提：p ?q， q ?r， p ?s ，?s結(jié)論：結(jié)論：r ?（p ?q）（2）前提：）前提：?p ?q， r ? ?q ，r ?s結(jié)論：結(jié)論：p ?s（1） 前提：前提：p ?q， q ?r， p ?s ，

19、?s結(jié)論：結(jié)論：r ?（p ?q）證明證明: (1)p ?s (2) ?s (3) ?p (1)(2)(4) p ?q (5) q (3)(4)(6) q ?r (7) r (5)(6)(8) r ?（p ?q）前提引入前提引入前提引入前提引入拒取式拒取式前提引入前提引入析取三段論析取三段論前提引入前提引入假言推理假言推理(7)(4)合取合?。?）前提：）前提：?p ?q， r ? ?q ，r ?s結(jié)論：結(jié)論：p ?s(1) ?p ?q (2) p ?q (1)(3) r ? ?q (4) q?r (3)(5) p ?r (2)(4)(6) r ?s (7) p ?s (5)(6)前提引入前提

20、引入置換置換前提引入前提引入置換置換假言三段論假言三段論前提引入前提引入假言三段論假言三段論證明：構(gòu)造證明構(gòu)造證明 直接證明法直接證明法?例例3.4 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明；中構(gòu)造下面推理的證明；若若a是實(shí)數(shù)，則它不是無(wú)理數(shù)就是有理數(shù)。是實(shí)數(shù)，則它不是無(wú)理數(shù)就是有理數(shù)。若若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)。不能表示成分?jǐn)?shù)，則它不是有理數(shù)。 a是實(shí)數(shù)且是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以它不能表示成分?jǐn)?shù)。所以 a是無(wú)理數(shù)。是無(wú)理數(shù)。解：首先將簡(jiǎn)單命題符號(hào)化：解：首先將簡(jiǎn)單命題符號(hào)化：p：a是實(shí)數(shù)。是實(shí)數(shù)。q ：a是有理數(shù)。是有理數(shù)。r：a是無(wú)理數(shù)。是無(wú)理數(shù)。S：a能表示成分

21、數(shù)。能表示成分?jǐn)?shù)。則可知：則可知：前提：前提： p ?(q ?r) ，?s ? ?q ， p ? ?s 結(jié)論：結(jié)論：r前提：前提： p ?(q ?r) ，?s ? ?q ， p ? ?s 結(jié)論：結(jié)論：r證明證明: (1) p ? ?s (2) p (1)(3) ?s (4) p ?(q ?r) (5) q ?r (2)(4)(6) ?s ?q (7) ?q(8) r (5)(7)前提引入前提引入化簡(jiǎn)(1)化簡(jiǎn)前提引入前提引入假言推理假言推理前提引入前提引入(3)(6)假言推理假言推理析取三段論析取三段論構(gòu)造證明構(gòu)造證明附加前提證明法附加前提證明法欲證明欲證明前提：前提：A1,A2, ,Ak結(jié)論

22、：結(jié)論：C? B等價(jià)地證明等價(jià)地證明前提：前提：A1,A2, ,Ak,C結(jié)論：結(jié)論：B理由：理由：(A1?A2?Ak)?(C? B)?(A1?A2?Ak)?(? C?B)?(A1?A2? ?Ak?C)?B?(A1?A2?Ak?C)? B將C稱為附加前提附加前提證明法附加前提證明法?例例3.5 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。中構(gòu)造下面推理的證明。如果小張和小王去看電影，則小李也去看電影。如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。所以，當(dāng)小趙去看電影時(shí)，小

23、李也去。解：將簡(jiǎn)單命題符號(hào)化：解：將簡(jiǎn)單命題符號(hào)化：p：小張去看電影：小張去看電影q：小王去看電影：小王去看電影r：小李去看電影：小李去看電影s：小趙去看電影：小趙去看電影?q）?r ，?s ?p ，q結(jié)論：結(jié)論：s ?r前提：（前提：（p 證明：證明：(1)?s 附加前提引入附加前提引入(?)?s ?p 前提引入前提引入(3)?p (1)(2)析取三段論析取三段論(4)?（p ?q）?r 前提引入前提引入(5)?q 前提引入前提引入(6)?p ?q (3)(5)合取合取(7)?r (4)(6)假言推理假言推理附加前提證明法附加前提證明法 (續(xù)續(xù))例例 構(gòu)造下面推理的證明構(gòu)造下面推理的證明 :

24、2是素?cái)?shù)或合數(shù)是素?cái)?shù)或合數(shù). 若若2是素?cái)?shù)，則是素?cái)?shù)，則2是無(wú)理數(shù)是無(wú)理數(shù).若若2是無(wú)理數(shù)，則是無(wú)理數(shù)，則4不是素?cái)?shù)不是素?cái)?shù). 所以，如果所以，如果4是是素?cái)?shù)，則素?cái)?shù)，則2是合數(shù)是合數(shù).用附加前提證明法構(gòu)造證明用附加前提證明法構(gòu)造證明解解 設(shè)設(shè)p：2是素?cái)?shù)，是素?cái)?shù)，q：2是合數(shù)，是合數(shù)，r：22是無(wú)理數(shù)，是無(wú)理數(shù)，s：4是素?cái)?shù)是素?cái)?shù)形式結(jié)構(gòu)形式結(jié)構(gòu)前提：前提：p?q, p? r, r? s結(jié)論：結(jié)論：s? q附加前提證明法附加前提證明法 (續(xù)續(xù))證明證明s附加前提引入附加前提引入p? r前提引入前提引入r? ? s前提引入前提引入p? ? s假言三段論假言三段論? p拒取式拒取式p?q前提引入前提引入q析取三段論析取三段論請(qǐng)用直接證明法證明之請(qǐng)用直接證明法證明之構(gòu)造證明構(gòu)造證明歸謬法（反證法）歸謬法（反證法）欲證明欲證明前提：前提：A1,A2, ,Ak結(jié)論：結(jié)論：B將將? B加入前提，若推出矛盾，則得證推理正確加入前提，若推出矛盾，則得證推理正確 .理由理由:A1?A2?Ak? B?(A1?A2?Ak)?B?(A1?A2? ?Ak? B)括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng)括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1