命題邏輯的推理理論

1、第3章 命題邏輯的推理理論離離 散散 數(shù)數(shù) 學(xué)學(xué)計(jì)算機(jī)系計(jì)算機(jī)系本章說明本章說明q本章的主要內(nèi)容本章的主要內(nèi)容推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)自然推理系統(tǒng)自然推理系統(tǒng)P Pq本章與后續(xù)各章的關(guān)系本章與后續(xù)各章的關(guān)系本章是第五章的特殊情況和先行準(zhǔn)備本章是第五章的特殊情況和先行準(zhǔn)備 q3.1 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)q3.2 3.2 自然推理系統(tǒng)自然推理系統(tǒng)P Pq 本章小結(jié)本章小結(jié)q 習(xí)題習(xí)題q 作業(yè)作業(yè)3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)q數(shù)理邏輯的主要任務(wù)是數(shù)理邏輯的主要任務(wù)是用數(shù)學(xué)的方法來研究數(shù)學(xué)中的用數(shù)學(xué)的方法來研究數(shù)學(xué)中的推理推理。q推理推理是指從前提出發(fā)推出結(jié)論的思維過程。是

2、指從前提出發(fā)推出結(jié)論的思維過程。q前提前提是已知命題公式集合。是已知命題公式集合。q結(jié)論結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式。q證明證明是描述推理正確或錯(cuò)誤的過程。是描述推理正確或錯(cuò)誤的過程。q要研究推理，首先應(yīng)該明確什么樣的推理是有效的或要研究推理，首先應(yīng)該明確什么樣的推理是有效的或正確的。正確的。定義定義3.1 3.1 設(shè)設(shè)A A1 1,A,A2 2, ,A,Ak k和和B B都是命題公式，若對于都是命題公式，若對于A A1 1,A,A2 2, ,A,Ak k和和B B中出現(xiàn)的命題變項(xiàng)的任意一組賦值，中出現(xiàn)的命題變項(xiàng)的任意一組賦值，（1 1）或

3、者）或者A A1 1AA2 2 AAk k為假為假; ;（2 2）或者當(dāng)）或者當(dāng)A A1 1AA2 2 AAk k為真時(shí)，為真時(shí)，B B也為真也為真; ;則稱由前提則稱由前提A A1 1,A,A2 2, ,A,Ak k推出推出B B的的推理是有效的或正確推理是有效的或正確的的，并稱，并稱B B是是有效結(jié)論有效結(jié)論。有效推理的定義有效推理的定義關(guān)于有效推理的說明關(guān)于有效推理的說明q A1，A2，Ak由由 推推B的推理記為的推理記為B若推理是正確的，記為若推理是正確的，記為 B若推理是不正確的，記為若推理是不正確的，記為 Bq由前提由前提A1，A2，Ak推結(jié)論推結(jié)論B的推理是否正確的推理是否正確與

4、諸前提的排列次序無關(guān)。與諸前提的排列次序無關(guān)。關(guān)于有效推理的說明關(guān)于有效推理的說明q設(shè)設(shè)A A1 1，A A2 2，A Ak k，B B中共出現(xiàn)中共出現(xiàn)n n個(gè)命題變項(xiàng)，對于任何個(gè)命題變項(xiàng)，對于任何一組賦值一組賦值1 12 2n n(i i=0=0或者或者1 1，i=1,2,i=1,2,n),n)，前提前提和結(jié)論的取值情況有以下四種：和結(jié)論的取值情況有以下四種： (1) (1) A A1 1AA2 2 AAk k為為0 0，B B為為0 0。(2) (2) A A1 1AA2 2 AAk k為為0 0，B B為為1 1。(3) (3) A A1 1AA2 2 AAk k為為1 1，B B為為0

5、 0。(4) (4) A A1 1AA2 2 AAk k為為1 1，B B為為1 1。q只要不出現(xiàn)只要不出現(xiàn)(3)(3)中的情況，推理就是正確的，因而判斷中的情況，推理就是正確的，因而判斷推理是否正確，就是判斷是否會(huì)出現(xiàn)推理是否正確，就是判斷是否會(huì)出現(xiàn)(3)(3)中的情況。中的情況。q推理正確，并不能保證結(jié)論推理正確，并不能保證結(jié)論B B一定為真一定為真。 (1) (1) p,pq qp,pq q (2) p,qp q (2) p,qp q 例例3.13.1 判斷下列推理是否正確。（真值表法）判斷下列推理是否正確。（真值表法） pqp (pq) qp (qp)q0000000101011000

6、10111111例題例題正確正確不正確不正確定理定理3.13.1 命題公式命題公式A A1 1,A,A2 2, ,A,Ak k推推B B的推理正確當(dāng)且僅當(dāng)?shù)耐评碚_當(dāng)且僅當(dāng) ( (A A1 1AA2 2AAk k )B )B 為重言式。為重言式。q該定理是判斷推理是否正確的另一種方法。該定理是判斷推理是否正確的另一種方法。 有效推理的等價(jià)定理有效推理的等價(jià)定理定理定理3.13.1的證明的證明(1)(1)證明必要性。若證明必要性。若A A1 1,A,A2 2, ,A,Ak k推推B B的推理正確，的推理正確，則對于則對于A A1 1,A,A2 2, ,A,Ak k,B,B中所含命題變項(xiàng)的任意一組

7、賦值，不會(huì)出中所含命題變項(xiàng)的任意一組賦值，不會(huì)出現(xiàn)現(xiàn)A A1 1AA2 2AAk k為真，而為真，而B B為假的情況，為假的情況，因而在任何賦值下，蘊(yùn)涵式因而在任何賦值下，蘊(yùn)涵式( (A A1 1AA2 2AAk k )B )B均為真，故它均為真，故它為重言式。為重言式。 (2)(2)證明充分性。若蘊(yùn)涵式證明充分性。若蘊(yùn)涵式( (A A1 1AA2 2AAk k)B)B為重言式，為重言式，則對于任何賦值此蘊(yùn)涵式均為真，因而不會(huì)出現(xiàn)前件為真后件則對于任何賦值此蘊(yùn)涵式均為真，因而不會(huì)出現(xiàn)前件為真后件為假的情況，為假的情況，即在任何賦值下，或者即在任何賦值下，或者A A1 1AA2 2AAk k為假

8、，為假，或者或者A A1 1AA2 2AAk k和和B B同時(shí)為真，這正符合推理正確的定義。同時(shí)為真，這正符合推理正確的定義。 當(dāng)推理正確時(shí)，當(dāng)推理正確時(shí)，q形式（形式（1）記為）記為 B。q形式（形式（2）記為）記為A1 A2 AkB。 表示蘊(yùn)涵式為重言式。表示蘊(yùn)涵式為重言式。q 設(shè)設(shè) = A1, A2, , Ak，記為記為 B。q A1 A2 AkBq 前提：前提： A1, A2, , Ak 結(jié)論：結(jié)論： B推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)q 真值表法真值表法 q 等值演算法等值演算法 q 主析取范式法主析取范式法判斷推理是否正確的方法判斷推理是否正確的方法q是否有其他的證明方法？是否有其他的

9、證明方法？q當(dāng)命題變項(xiàng)較少時(shí)當(dāng)命題變項(xiàng)較少時(shí),這三種方法比較方便這三種方法比較方便。（1 1） 下午馬芳或去看電影或去游泳。她沒去看電影，所以，她下午馬芳或去看電影或去游泳。她沒去看電影，所以，她 去游泳了。去游泳了。例例3.23.2 判斷下列推理是否正確。（等值演算法）判斷下列推理是否正確。（等值演算法） 解：設(shè)解：設(shè)p:p:馬芳下午去看電影，馬芳下午去看電影，q:q:馬芳下午去游泳。馬芳下午去游泳。 前提：前提： p pq q，p p 結(jié)論：結(jié)論： q q 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： (p(pq)q)p)p)q q (p (pq)q)p)p)q q (p(pq)q)p) p) q q

10、 (p pq)q)pp) ) q q (pppp ) )(q qp) p) q q ( (q qp) p) q q 1 1由定理由定理 3.1 3.1可知，可知，推理正確。推理正確。例題例題（2 2）若今天是若今天是1 1號，則明天是號，則明天是5 5號。明天是號。明天是5 5號，所以今天是號，所以今天是1 1號。號。例例3.23.2 判斷下列推理是否正確。（主析取范式法判斷下列推理是否正確。（主析取范式法 ） (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 主析取范式不含主析取范式不含m m1 1，故故不是重言

11、式（不是重言式（0101是成是成假賦值），所以推理假賦值），所以推理不正確。不正確。解：設(shè)解：設(shè)p p：今天是今天是1 1號，號，q q：明天是明天是5 5號。號。 前提：前提：pq，q 結(jié)論：結(jié)論： p 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： (pq) qp 例題例題(1) A (1) A (AB)(AB) 附加律附加律(2) (2) (AB) AB) A A 化簡律化簡律(3)(3) ( (AB)A AB)A B B 假言推理假言推理(4) (4) (AB)B AB)B A A 拒取式拒取式(5) (5) (AB)B AB)B A A 析取三段論析取三段論 (6)(6) ( (AB) (BC)

12、AB) (BC) (AC) (AC) 假言三段論假言三段論(7)(7) ( (A AB) (BB) (BC) C) (A (A C) C) 等價(jià)三段論等價(jià)三段論(8)(8) ( (AB)(CD)(AC) AB)(CD)(AC) (BD)(BD) 構(gòu)造性二難構(gòu)造性二難 ( (AB)(AB)(AA) AB)(AB)(AA) B B 構(gòu)造性二難構(gòu)造性二難 ( (特殊形式特殊形式) )(9)(9)(AB)(CD)(BD) AB)(CD)(BD) (AC) (AC) 破壞性二難破壞性二難 推理定律推理定律-重言蘊(yùn)含式重言蘊(yùn)含式關(guān)于推理定律的幾點(diǎn)說明關(guān)于推理定律的幾點(diǎn)說明qA,B,CA,B,C為元語言符號

13、，代表任意的命題公式。為元語言符號，代表任意的命題公式。q若一個(gè)推理的形式結(jié)構(gòu)與某條推理定律對應(yīng)的蘊(yùn)涵若一個(gè)推理的形式結(jié)構(gòu)與某條推理定律對應(yīng)的蘊(yùn)涵式一致，則不用證明就可斷定這個(gè)推理是正確的。式一致，則不用證明就可斷定這個(gè)推理是正確的。q2.12.1節(jié)給出的節(jié)給出的2424個(gè)等值式中的每一個(gè)都派生出兩條推個(gè)等值式中的每一個(gè)都派生出兩條推理定律。例如雙重否定律理定律。例如雙重否定律A A A A產(chǎn)生兩條推理定產(chǎn)生兩條推理定律律A A A A和和 A AA A。q由九條推理定律可以產(chǎn)生九條推理規(guī)則由九條推理定律可以產(chǎn)生九條推理規(guī)則, ,它們構(gòu)成了它們構(gòu)成了推理系統(tǒng)中的推理規(guī)則推理系統(tǒng)中的推理規(guī)則。3

14、.2 3.2 自然推理系統(tǒng)自然推理系統(tǒng)P Pq判斷推理是否正確的三種方法：真值表法、等值演判斷推理是否正確的三種方法：真值表法、等值演算法和主析取范式法。算法和主析取范式法。q當(dāng)推理中包含的命題變項(xiàng)較多時(shí)，上述三種方法演當(dāng)推理中包含的命題變項(xiàng)較多時(shí)，上述三種方法演算量太大。算量太大。q對于由前提對于由前提A A1 1,A,A2 2, ,A,Ak k推推B B的正確推理應(yīng)該給出嚴(yán)謹(jǐn)?shù)恼_推理應(yīng)該給出嚴(yán)謹(jǐn)?shù)淖C明的證明。q證明是一個(gè)描述推理過程的命題公式序列，其中的證明是一個(gè)描述推理過程的命題公式序列，其中的每個(gè)公式或者是前提，或者是由某些前提應(yīng)用推理每個(gè)公式或者是前提，或者是由某些前提應(yīng)用推理規(guī)則

15、得到的結(jié)論（中間結(jié)論或推理中的結(jié)論）。規(guī)則得到的結(jié)論（中間結(jié)論或推理中的結(jié)論）。q要構(gòu)造出嚴(yán)謹(jǐn)?shù)淖C明就必須在形式系統(tǒng)中進(jìn)行。要構(gòu)造出嚴(yán)謹(jǐn)?shù)淖C明就必須在形式系統(tǒng)中進(jìn)行。形式系統(tǒng)的定義形式系統(tǒng)的定義定義定義3.23.2 一個(gè)一個(gè)形式系統(tǒng)形式系統(tǒng)I由下面四個(gè)部分組成：由下面四個(gè)部分組成：（1 1）非空的字母表，記作）非空的字母表，記作A(I)。（2 2）A(I)中符號構(gòu)造的合式公式集，記作中符號構(gòu)造的合式公式集，記作E(I)。（3 3）E(I)中一些特殊的公式組成的公理集，記作中一些特殊的公式組成的公理集，記作AX(I)。（4 4）推理規(guī)則集，記作推理規(guī)則集，記作R(I)?？梢詫⒖梢詫記為記為4

16、4元組元組 是是I的的形式語言系統(tǒng)形式語言系統(tǒng) 是是I的的形式演算系統(tǒng)形式演算系統(tǒng)形式系統(tǒng)的分類形式系統(tǒng)的分類（1 1）自然推理系統(tǒng)自然推理系統(tǒng)從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算，得到的最后命題公式是推理的結(jié)論行推理演算，得到的最后命題公式是推理的結(jié)論（有時(shí)稱為有效的結(jié)論）。（有時(shí)稱為有效的結(jié)論）。 （2 2）公理系統(tǒng)公理系統(tǒng)從若干給定的公理出發(fā)，應(yīng)用系統(tǒng)中推理規(guī)則進(jìn)行從若干給定的公理出發(fā)，應(yīng)用系統(tǒng)中推理規(guī)則進(jìn)行推理演算，得到的結(jié)論是系統(tǒng)中的定理。推理演算，得到的結(jié)論是系統(tǒng)中的定理。 q本書只介紹自然推理系統(tǒng)本書只介紹自然推理系統(tǒng)

17、P P。自然推理系統(tǒng)的定義自然推理系統(tǒng)的定義定義定義3.33.3 自然推理系統(tǒng)自然推理系統(tǒng)P P的定義的定義1. 1. 字母表字母表（1 1） 命題變項(xiàng)符號：命題變項(xiàng)符號：p， q， r， ， pi，qi，ri ，（2 2） 聯(lián)結(jié)詞符號：聯(lián)結(jié)詞符號： ， ， ， ， （3 3） 括號與逗號：括號與逗號：( )，2. 2. 合式公式（同定義合式公式（同定義1.61.6）自然推理系統(tǒng)的定義自然推理系統(tǒng)的定義3. 3. 推理規(guī)則推理規(guī)則（1 1）前提引入規(guī)則）前提引入規(guī)則 在證明的任何步驟上都可以引入前提。在證明的任何步驟上都可以引入前提。 （2 2）結(jié)論引入規(guī)則）結(jié)論引入規(guī)則 在證明的任何步驟上所

18、得到的結(jié)論都可以作為在證明的任何步驟上所得到的結(jié)論都可以作為后繼證明的前提。后繼證明的前提。 （3 3）置換規(guī)則）置換規(guī)則 在證明的任何步驟上，命題公式中的子公式都在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中的又可以用與之等值的公式置換，得到公式序列中的又一個(gè)公式。一個(gè)公式。自然推理系統(tǒng)的定義自然推理系統(tǒng)的定義（4 4）假言推理規(guī)則）假言推理規(guī)則 A AB B A A B B（5 5）附加規(guī)則）附加規(guī)則 A A A A B B（6 6）化簡規(guī)則）化簡規(guī)則 A A B B A A（4 4）若今天下雪）若今天下雪, ,則將去滑則將去滑雪。今天下雪，所以去滑雪。今

19、天下雪，所以去滑雪。雪。（5 5）現(xiàn)在氣溫在冰點(diǎn)以下。）現(xiàn)在氣溫在冰點(diǎn)以下。因此，要么現(xiàn)在氣溫在冰因此，要么現(xiàn)在氣溫在冰點(diǎn)以下，要么現(xiàn)在下雨。點(diǎn)以下，要么現(xiàn)在下雨。（6 6）現(xiàn)在氣溫在冰點(diǎn)以下并）現(xiàn)在氣溫在冰點(diǎn)以下并且正在下雨。因此，現(xiàn)在且正在下雨。因此，現(xiàn)在氣溫在冰點(diǎn)以下。氣溫在冰點(diǎn)以下。自然推理系統(tǒng)的定義自然推理系統(tǒng)的定義（7 7）拒取式規(guī)則）拒取式規(guī)則 A AB B B B A A（8 8） 假言三段論規(guī)則假言三段論規(guī)則 A AB B B BC C A AC C（9 9）析取三段論規(guī)則）析取三段論規(guī)則 A A B B B B A A自然推理系統(tǒng)的定義自然推理系統(tǒng)的定義（1010）構(gòu)造性二

20、難推理規(guī)則）構(gòu)造性二難推理規(guī)則 A AB B C CD D A A C C B B D D （1111）破壞性二難推理規(guī)則）破壞性二難推理規(guī)則 A AB B C CD D B BD D A AC C（1212） 合取引入規(guī)則合取引入規(guī)則 A A B B A A B B在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造證明中構(gòu)造證明qP P中構(gòu)造證明就是由一組中構(gòu)造證明就是由一組P P中公式作為前提，利用中公式作為前提，利用P P中的規(guī)則，推出結(jié)論。中的規(guī)則，推出結(jié)論。q構(gòu)造形式結(jié)構(gòu)構(gòu)造形式結(jié)構(gòu)A A1 1 A A2 2 A Ak k B B 的推理的的推理的書寫方書寫方法：法：前提：前提： A A1 1

21、,A,A2 2, ,A,Ak k 結(jié)論：結(jié)論： B Bq證明方法：證明方法：直接證明法直接證明法 附加前提法附加前提法歸謬法（或稱反證法）歸謬法（或稱反證法）例題例題例例3.33.3 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明：前提：前提：pq, rq ,rs pq, rq ,rs 結(jié)論：結(jié)論：ps ps pqpq 前提引入前提引入 pq pq 置換置換 rqrq 前提引入前提引入 qr qr 置換置換 pr pr 假言三段論假言三段論 rs rs 前提引入前提引入 ps ps 假言三段論假言三段論 例題例題例例3.33.3 在自然推理系統(tǒng)在自然推理系統(tǒng)P P

22、中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明：前提：前提：pp（qrqr）, p, pq q 結(jié)論：結(jié)論： rs rs pp（qrqr） 前提引入前提引入 p pq q 前提引入前提引入 p p 化簡化簡 q q 化簡化簡 qrqr 假言推理假言推理 r r 假言推理假言推理 rsrs 附加附加 rsrs置換置換例題例題例例3.43.4 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 若數(shù)若數(shù)a a是實(shí)數(shù)，則它不是有理數(shù)就是無理數(shù)；若是實(shí)數(shù)，則它不是有理數(shù)就是無理數(shù)；若a a不能表不能表示成分?jǐn)?shù)，則它不是有理數(shù)；示成分?jǐn)?shù)，則它不是有理數(shù)；a a是實(shí)數(shù)且它不能表示成

23、分?jǐn)?shù)。是實(shí)數(shù)且它不能表示成分?jǐn)?shù)。所以所以a a是無理數(shù)。是無理數(shù)。 構(gòu)造證明：構(gòu)造證明：（1 1）將簡單命題符號化：）將簡單命題符號化： 設(shè)設(shè) p p：a a是實(shí)數(shù)。是實(shí)數(shù)。 q q：a a是有理數(shù)。是有理數(shù)。 r r：a a是無理數(shù)。是無理數(shù)。 s s：a a能表示成分?jǐn)?shù)。能表示成分?jǐn)?shù)。（2 2）形式結(jié)構(gòu)：）形式結(jié)構(gòu)： 前提：前提：p(qr), sq, psp(qr), sq, ps 結(jié)論：結(jié)論：r r ps ps 前提引入前提引入 p p 化簡化簡 s s 化簡化簡 p(qr) p(qr) 前提引入前提引入 qr qr 假言推理假言推理 sqsq 前提引入前提引入 q q 假言推理假言推理

24、 r r 析取三段論析取三段論 例題例題附加前提法附加前提法q有時(shí)推理的形式結(jié)構(gòu)具有如下形式有時(shí)推理的形式結(jié)構(gòu)具有如下形式 ： 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：CBq可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為可將結(jié)論中的前件也作為推理的前提，使結(jié)論只為B B。 前提：前提：A1, A2, , Ak, C 結(jié)論：結(jié)論：Bq理由：理由： ( (A A1 1 A A2 2 A Ak k) )( (C CB B) ) ( ( A A1 1 A A2 2 A Ak k) ) ( ( C C B B) ) ( ( A A1 1 A A2 2 A Ak k C C) ) B B ( (A

25、 A1 1 A A2 2 A Ak k C C) )B B例題例題例例3.53.5 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明。中構(gòu)造下面推理的證明。 如果小張和小王去看電影，則小李也去看電影；小趙不去如果小張和小王去看電影，則小李也去看電影；小趙不去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影或小張去看電影；小王去看電影。所以，當(dāng)小趙去看電影時(shí)，小李也去看電影?？措娪皶r(shí)，小李也去看電影。構(gòu)造證明：構(gòu)造證明：（1 1）將簡單命題符號化：）將簡單命題符號化： 設(shè)設(shè) p:p:小張去看電影。小張去看電影。 q:q:小王去看電影。小王去看電影。 r:r:小李去看電影。小李去看電

26、影。 s:s:小趙去看電影。小趙去看電影。 例題例題（2 2） 形式結(jié)構(gòu)：形式結(jié)構(gòu)： 前提：前提：( (pq)r,sp,q pq)r,sp,q 結(jié)論：結(jié)論：sr sr （3 3）證明：用附加前提證明法）證明：用附加前提證明法 s s 附加前提引入附加前提引入 spsp 前提引入前提引入 p p 析取三段論析取三段論 ( (pq)r pq)r 前提引入前提引入 q q 前提引入前提引入 pqpq 合取合取 r r 假言推理假言推理 歸謬法（反證法）歸謬法（反證法）q 有時(shí)推理的形式結(jié)構(gòu)具有如下形式：有時(shí)推理的形式結(jié)構(gòu)具有如下形式： 前提：前提：A A1 1, , A A2 2, , , , A

27、Ak k 結(jié)論：結(jié)論：B Bq 如果將如果將B B作為前提能推出矛盾來，則說明推理正確。作為前提能推出矛盾來，則說明推理正確。 前提：前提：A A1 1, , A A2 2, , , , A Ak k, , B B 結(jié)論：矛盾結(jié)論：矛盾q 理由：理由：A A1 1 A A2 2 A Ak kB B ( (A A1 1 A A2 2 A Ak k) ) B B ( (A A1 1 A A2 2 A Ak kB B) )q若若A A1 1 A A2 2 A Ak kB B為矛盾式，則說明為矛盾式，則說明( (A A1 1 A A2 2 A Ak kB B) ) 為重言式。為重言式。例題例題例例3.

28、63.6 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明。中構(gòu)造下面推理的證明。 如果小張守第一壘并且小李向如果小張守第一壘并且小李向B B隊(duì)投球，則隊(duì)投球，則A A隊(duì)將取勝；或者隊(duì)將取勝；或者A A隊(duì)隊(duì)未取勝，或者未取勝，或者A A隊(duì)獲得聯(lián)賽第一名；隊(duì)獲得聯(lián)賽第一名；A A隊(duì)沒有獲得聯(lián)賽的第一名隊(duì)沒有獲得聯(lián)賽的第一名；小張守第一壘。因此，小李沒有向；小張守第一壘。因此，小李沒有向B B隊(duì)投球。隊(duì)投球。 構(gòu)造證明：構(gòu)造證明：（1 1）將簡單命題符號化：）將簡單命題符號化： 設(shè)設(shè) p:p:小張守第一壘。小張守第一壘。 q:q:小李向小李向B B隊(duì)投球。隊(duì)投球。 r:Ar:A隊(duì)取勝。隊(duì)取勝

29、。 s:As:A隊(duì)獲得聯(lián)賽第一名。隊(duì)獲得聯(lián)賽第一名。（2 2）形式結(jié)構(gòu)：）形式結(jié)構(gòu)： 前提：前提：( (pq)r,rs,s ,p pq)r,rs,s ,p 結(jié)論：結(jié)論：q q 例題例題（3 3）證明：用歸謬法）證明：用歸謬法 q q 結(jié)論的否定引入結(jié)論的否定引入 rs rs 前提引入前提引入 s s 前提引入前提引入 r r 析取三段論析取三段論 ( (pq)r pq)r 前提引人前提引人 ( (pq)pq) 拒取式拒取式 pq pq 置換置換 p p 前提引入前提引入 q q 析取三段論析取三段論 qqqq 合取合取 由于最后一步為矛盾式，所以推理正確。由于最后一步為矛盾式，所以推理正確。

30、本章主要內(nèi)容本章主要內(nèi)容q 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)：推理的前提推理的前提推理的結(jié)論推理的結(jié)論推理正確推理正確q 判斷推理是否正確的方法：判斷推理是否正確的方法：真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法 q 對于正確的推理，在自然推理系統(tǒng)對于正確的推理，在自然推理系統(tǒng)P P中構(gòu)造證明中構(gòu)造證明: : 自然推理系統(tǒng)自然推理系統(tǒng)P P的定義的定義自然推理系統(tǒng)自然推理系統(tǒng)P P的推理規(guī)則：的推理規(guī)則：附加前提證明法附加前提證明法歸謬法歸謬法本章學(xué)習(xí)要求本章學(xué)習(xí)要求q 理解并記住推理的形式結(jié)構(gòu)的三種等價(jià)形式，即理解并記住推理的形式結(jié)構(gòu)的三種等價(jià)形式，即A1,A2,AkBA1A

31、2AkB前提：前提：A1,A2,Ak 結(jié)論：結(jié)論：B在判斷推理是否正確時(shí)，用；在在判斷推理是否正確時(shí)，用；在P系統(tǒng)中構(gòu)造證明時(shí)用。系統(tǒng)中構(gòu)造證明時(shí)用。 q 熟練掌握判斷推理是否正確的三種方法（真值表法，等值演算熟練掌握判斷推理是否正確的三種方法（真值表法，等值演算法，主析取范式法）。法，主析取范式法）。 q 牢記牢記P系統(tǒng)中的各條推理規(guī)則。系統(tǒng)中的各條推理規(guī)則。 q 對于給定的正確推理，要求在對于給定的正確推理，要求在P系統(tǒng)中給出嚴(yán)謹(jǐn)?shù)淖C明序列。系統(tǒng)中給出嚴(yán)謹(jǐn)?shù)淖C明序列。 q 會(huì)用附加前提證明法和歸謬法。會(huì)用附加前提證明法和歸謬法。 習(xí)題習(xí)題1、用不同的方法驗(yàn)證下面推理是否正確。對于正確的推理還、用不同的方法驗(yàn)證下面推理是否正確。對于正確的推理還要在要在P系統(tǒng)中