命題邏輯的推理理論優(yōu)秀課件

1、1第三章第三章 命題邏輯的推理理論命題邏輯的推理理論 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)自然推理系統(tǒng)自然推理系統(tǒng)P2關(guān)于“推理”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é)中的推理。3推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)問題的引入問題的引入 推理舉例推理舉例: (1) 正項(xiàng)級數(shù)收斂當(dāng)且僅當(dāng)部分和上有界正項(xiàng)級數(shù)收斂當(dāng)且僅當(dāng)部分和上有界. (2)

2、若若A C B D，則，則A B且且C D.推理推理: 從前提出發(fā)推出結(jié)論的思維過程從前提出發(fā)推出結(jié)論的思維過程上面上面(1)是正確的推理，而是正確的推理，而(2)是錯(cuò)誤的推理是錯(cuò)誤的推理. 證明證明: 描述推理正確或錯(cuò)誤的過程描述推理正確或錯(cuò)誤的過程. 4推理的形式結(jié)構(gòu) 定義定義 設(shè)設(shè)A1，A2 ，Ak，B都是命題公式都是命題公式, 若對于若對于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ò)誤）.5說明（1）：n由前提由前提A1，A2 ，Ak推結(jié)論推結(jié)論B的推理是否正確的推理是否正確與諸前提的排列次序無關(guān)。與諸前提的排列次序無關(guān)。n因而前提中的公式不一定是序列，而是一個(gè)有限因而前提中的公式不一定是序列，而是一個(gè)有限公式集合，記為公式集合，記為 。n可將由可將由推推B的推理記為的推理記為B B，若推理是正，若推理是正確的，則記為確的，則記為|=B|=B，否則記為，否則記為 | B B。n這里可以稱這里可以稱BB 和和 A1，A2 ，Ak B B 為推理的形式結(jié)構(gòu)。為推理的形式結(jié)構(gòu)。6說明（2）n設(shè)設(shè)A1，A2 ，A

4、k，B中共出現(xiàn)中共出現(xiàn)n個(gè)命題變項(xiàng)，對于任個(gè)命題變項(xiàng)，對于任一組賦值一組賦值 a1a2an （ai0或或1， 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）中的情況。）中的情況。7例3.1

5、判斷下列推理是否正確n（1） p， p q qn（2） p， q p q 解：只要寫出前提的合取式與結(jié)論的真值表，看是解：只要寫出前提的合取式與結(jié)論的真值表，看是否出現(xiàn)前提為真，而結(jié)論為假的情況即可。否出現(xiàn)前提為真，而結(jié)論為假的情況即可。 由下面真值表可看出，（由下面真值表可看出，（1）推理正確，（）推理正確，（2）推理不正確。推理不正確。8 p q p （ p q ） q 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 p q p （ q p ） q 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 19定理定理3.1 命題公式A1，A2 ，Ak推B的推理正確當(dāng)且僅

6、當(dāng)： （A1 A2 Ak ） B B 為重言式。為重言式。證明：必要性 若命題公式A1，A2 ，Ak推B的推理正確，則不會(huì)出現(xiàn)A1 A2 Ak為真，而B為假的情況，因而在任何賦值下，蘊(yùn)涵式（A1 A2 Ak ） B B 均為真，故為重言式。10證明：充分性 若蘊(yùn)涵式（A1 A2 Ak ） B B 為重言式，則對于任何賦值此重言式均為真，因而不會(huì)出現(xiàn)前件為真后件為假的情況。即在任何賦值下，或者A1 A2 Ak為假，或者A1 A2 Ak和B同時(shí)為真，這正符合定義3.1中推理正確的定義。11分析： 由定理3.1可知，可以將由前提A1, A2, , Ak 推B的推理的形式結(jié)構(gòu) A1 A2 Ak B 轉(zhuǎn)

7、換成蘊(yùn)涵式 （A1 A2 Ak ） B B 推理前提的合取式成了蘊(yùn)涵式的前件，結(jié)論成了蘊(yùn)涵式的后件，并將推理正確 A1 A2 Ak | B 轉(zhuǎn)換成 A1 A2 Ak B 其中是一種元語言符號，表示蘊(yùn)涵式為重言式。12判斷推理是否正確的方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法構(gòu)造證明法構(gòu)造證明法 說明：當(dāng)命題變項(xiàng)比較少時(shí)，用前說明：當(dāng)命題變項(xiàng)比較少時(shí)，用前3 3個(gè)方法比較個(gè)方法比較方方便便, , 此時(shí)采用此時(shí)采用形式結(jié)構(gòu)形式結(jié)構(gòu)“ A1 A2 AkB” . 而在而在構(gòu)造證明時(shí)，構(gòu)造證明時(shí)，采用采用“前提前提: A1, A2, , Ak, 結(jié)論結(jié)論: B”. 13例3.2

8、判斷下面推理是否正確 解上述類型的推理問題，首先應(yīng)將簡單命題符號化。然后分別寫出前提、結(jié)論、推理的形式結(jié)構(gòu)，接著進(jìn)行判斷。 14（1）設(shè) p：a能被4整除 q：a能被2整除 前提：p q，p 結(jié)論：q 推理的形式結(jié)構(gòu)：（p q） p q 可知此推理正確，即 （p q） p q 。 （1）若）若a能被能被4整除，則整除，則a能被能被2整除。整除。a能被能被4整除，整除，所以所以a能被能被2整除。整除。15（2）若）若a能被能被4整除，則整除，則a能被能被2整除。整除。a能被能被2整除，整除，所以所以a能被能被4整除。整除。n（2）設(shè) p：a能被4整除 q：a能被2整除 前提：p q，q 結(jié)論：p

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

10、必去游泳。若她去游泳，她就不去看電影。所以，若王小燕沒若她去游泳，她就不去看電影。所以，若王小燕沒去看電影，下午氣溫必超過了去看電影，下午氣溫必超過了30度。度。n（4）設(shè)）設(shè) p：下午氣溫超過：下午氣溫超過30度度 q： 王小燕去游泳王小燕去游泳 r： 王小燕去看電影王小燕去看電影 前提：前提： p q， q r 結(jié)論：結(jié)論： r p 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： （ p q ） （q r） （ r p） 用主析取范式法可知上式不是重言式，所以用主析取范式法可知上式不是重言式，所以推理不正確。推理不正確。18重要的推理定律（重要的推理定律（重言蘊(yùn)涵式重言蘊(yùn)涵式 ） A (A B) 附加律

11、附加律 (A B) A 化簡律化簡律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式 (A B)B A 析取三段論析取三段論 (AB) (BC) (AC) 假言三段論假言三段論 (AB) (BC) (AC) 等價(jià)三段論等價(jià)三段論 (AB) (CD) (A C) (B D) 構(gòu)造性二難構(gòu)造性二難 19推理定律推理定律 (續(xù)續(xù))(AB) ( AB) (AA) B 構(gòu)造性二難（特殊形式）構(gòu)造性二難（特殊形式）(AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難說明：說明： (1)A, B, C為元語言符號，代表任意的命題公式。為元語言符號，代表任意的命題公式。(2)若某

12、推理符合某條推理定律，則它自然是正確的若某推理符合某條推理定律，則它自然是正確的.(3)AB產(chǎn)生兩條推理定律產(chǎn)生兩條推理定律: A B, B A.2021實(shí)例實(shí)例例例 判斷下面推理是否正確判斷下面推理是否正確 (1) 若今天是若今天是1號，則明天是號，則明天是5號號. 今天是今天是1號號. 所所 以明天是以明天是5號號. 解解 設(shè)設(shè) p：今天是：今天是1號，號，q：明天是：明天是5號號. 證明的形式結(jié)構(gòu)為證明的形式結(jié)構(gòu)為: (pq) pq證明（用等值演算法）證明（用等值演算法） (pq) pq ( p q) p) q pq q 1得證推理正確得證推理正確 22實(shí)例實(shí)例 (續(xù)續(xù))(2) 若今天是

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

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

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

16、A(I)中符號構(gòu)造的合式公式集，記做中符號構(gòu)造的合式公式集，記做E(I)。（3） E(I)中一些特殊的公式組成的公理集，記做中一些特殊的公式組成的公理集，記做Ax(I) 。（4）推理規(guī)則集，記做）推理規(guī)則集，記做R(I)。 可以將可以將I記為記為4元組元組。其中。其中是是I的形式語言系統(tǒng)，而的形式語言系統(tǒng)，而為為I的形式演算系統(tǒng)。的形式演算系統(tǒng)。27形式系統(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)是只能從

17、若干條給定的公理公理出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行演算，得到的是系統(tǒng)中的定理（是是重言式重言式）。28 定義3.3 自然推理系統(tǒng)P定義如下： 1、字母表 （1）命題變項(xiàng)符號：p，q，r， （2）聯(lián)結(jié)詞符號： , , , , , , , , （3）括號與逗號 ： （ ） ， ， 2、合式公式 (參見定義1.6 P10）3、 推理規(guī)則29推理規(guī)則推理規(guī)則（1）前提引入規(guī)則 ：在證明的任何步驟上都可以引入前提。 （2）結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以做為后續(xù)證明的前提。 （3）置換規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以作為后續(xù)證明的前提。30推理規(guī)則推理規(guī)則 （續(xù)）（續(xù)）(4)

18、 假言推理規(guī)則假言推理規(guī)則 AB A B(5) 附加規(guī)則附加規(guī)則 A A B (6) 化簡規(guī)則化簡規(guī)則 A B A (7) 拒取式規(guī)則拒取式規(guī)則 AB B A(8) 假言三段論規(guī)則假言三段論規(guī)則 AB BC AC 31推理規(guī)則推理規(guī)則( (續(xù)續(xù)) ) (11) 破壞性二難推理破壞性二難推理規(guī)則規(guī)則 AB CD BD AC(12) 合取引入規(guī)則合取引入規(guī)則 A B A B (9) 析取三段論規(guī)則析取三段論規(guī)則 A B B A (10)構(gòu)造性二難推理構(gòu)造性二難推理規(guī)則規(guī)則 AB CD A C B D32構(gòu)造證明構(gòu)造證明直接證明法直接證明法n例例3.3 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的

19、證明；中構(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 s33（1） 前提：前提：p q， q r， p s ， 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)合取合取34（2）前提：）

20、前提： 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)假言三段論假言三段論 35構(gòu)造證明構(gòu)造證明直接證明法直接證明法n例例3.4 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明；中構(gòu)造下面推理的證明； 若若a是實(shí)數(shù)，則它不是無理數(shù)就是有理數(shù)。是實(shí)數(shù)，則它不是無理數(shù)就是有理數(shù)。若若a不能表示成分?jǐn)?shù)，則它不是有理數(shù)。不能表示成分?jǐn)?shù)，則它不是有理數(shù)

21、。a是實(shí)數(shù)且是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以它不能表示成分?jǐn)?shù)。所以a是無理數(shù)。是無理數(shù)。 解：首先將簡單命題符號化：解：首先將簡單命題符號化： p：a是實(shí)數(shù)。是實(shí)數(shù)。 q ：a是有理數(shù)。是有理數(shù)。 r：a是無理數(shù)。是無理數(shù)。 S：a能表示成分?jǐn)?shù)。能表示成分?jǐn)?shù)。 則可知：則可知： 前提：前提： p (q r) ， s q ， p s 結(jié)論：結(jié)論：r36 前提：前提： p (q r) ， s q ， p s 結(jié)論：結(jié)論：r證明證明: (1) p s 前提引入前提引入 (2) p (1)化簡 (3) s (1)化簡 (4) p (q r) 前提引入前提引入 (5) q r (2)(4)假言推理假言推理

22、 (6) s q 前提引入前提引入 (7) q (3)(6)假言推理假言推理 (8) r (5)(7)析取三段論析取三段論37構(gòu)造證明構(gòu)造證明附加前提證明法附加前提證明法 欲證明欲證明 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：CB等價(jià)地證明等價(jià)地證明 前提：前提：A1, A2, , Ak, C 結(jié)論：結(jié)論：B 理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B將C稱為附加前提38附加前提證明法附加前提證明法n例例3.5 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明。中構(gòu)造下面推理的證明。

23、如果小張和小王去看電影，則小李也去看電影。如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王去看電影。小趙不去看電影或小張去看電影。小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去。所以，當(dāng)小趙去看電影時(shí)，小李也去。解：將簡單命題符號化：解：將簡單命題符號化： p：小張去看電影：小張去看電影 q：小王去看電影：小王去看電影 r：小李去看電影：小李去看電影 s：小趙去看電影：小趙去看電影 39前提：（前提：（p q） r ， s p ，q結(jié)論：結(jié)論：s r證明：證明：(1) (1) s 附加前提引入附加前提引入 (2) (2) s p 前提引入前提引入 (3) (3) p

24、 (1)(2)析取三段論析取三段論 (4) (4) （p q） r 前提引入前提引入 (5) (5) q 前提引入前提引入 (6) (6) p q (3)(5)(3)(5)合取合取 (7) (7) r (4)(6) (4)(6)假言推理假言推理40附加前提證明法附加前提證明法 (續(xù)續(xù)) 222例例 構(gòu)造下面推理的證明構(gòu)造下面推理的證明: 2是素?cái)?shù)或合數(shù)是素?cái)?shù)或合數(shù). 若若2是素?cái)?shù)，則是素?cái)?shù)，則 是無理數(shù)是無理數(shù). 若若 是無理數(shù)，則是無理數(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是

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