1、第三章第三章 命題邏輯的推理理論命題邏輯的推理理論3.1 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)3.2 3.2 自然推理系統(tǒng)自然推理系統(tǒng) P P 推理的例子推理的例子止楚攻宋的故事止楚攻宋的故事 如果一個(gè)人放著自己的豪華馬車不坐，卻想偷如果一個(gè)人放著自己的豪華馬車不坐，卻想偷鄰居的破車；放著自己的錦繡衣裳不穿，卻想鄰居的破車；放著自己的錦繡衣裳不穿，卻想偷鄰居的黑粗布褂，他必定患了偷竊病。偷鄰居的黑粗布褂，他必定患了偷竊病。 楚王就是這樣的人；楚王就是這樣的人； 所以楚王有偷竊病。所以楚王有偷竊病。 墨經(jīng)墨經(jīng)、墨辨墨辨3.1 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 定義：定義： 推理推理就是從就是

2、從前提前提出發(fā)推出出發(fā)推出結(jié)論結(jié)論的思維的思維過程。過程。前提與結(jié)論都是一組命題公式前提與結(jié)論都是一組命題公式。 推理的推理的形式結(jié)構(gòu)形式結(jié)構(gòu)： AA1 1,A,A2 2,A,Ak k B B 從從形式形式的角度研究推理的規(guī)律。的角度研究推理的規(guī)律。有效有效( (正確）的推理正確）的推理定義定義3.13.1對(duì)于任意一組賦值，對(duì)于任意一組賦值， 或者或者A A1 1 A A2 2 A Ak k為假，為假，B B任意任意 或者或者A A1 1 A A2 2 A Ak k為真，為真，B B也為真也為真則推理則推理AA1 1,A,A2 2,A,Ak k B B 為為有效的、正確的有效的、正確的 稱稱B

3、 B是是有效的結(jié)論有效的結(jié)論, ,記為記為 AA1 1,A,A2 2,A,Ak k B B 注意：注意：有效的結(jié)論并不能保證一定為真有效的結(jié)論并不能保證一定為真。例題例題【例【例3.13.1】 判斷推理是否正確判斷推理是否正確 （1 1）p,pq qp,pq q （2 2）p,qp qp,qp q推理的蘊(yùn)涵式結(jié)構(gòu)推理的蘊(yùn)涵式結(jié)構(gòu)定理定理3.13.1 推理推理AA1 1,A,A2 2,A,Ak k B B 為有效的、正確的為有效的、正確的，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) （A A1 1AA2 2AAk k）BB 為重言式。為重言式。 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) （A A1 1AA2 2AAk k） B B

4、若（若（A A1 1AA2 2AAk k）BB）1 1，即推理是有，即推理是有效（正確）的，記為：效（正確）的，記為： A A1 1AA2 2AAk k B B判斷推理正確的方法判斷推理正確的方法 前提：前提： A A1 1，A A2 2，A Ak k 結(jié)論：結(jié)論： B B 形式結(jié)構(gòu)形式結(jié)構(gòu) （A A1 1AA2 2AAk k） B B四種方法四種方法 1.1. 真值表法真值表法 2. 2. 等值演算法等值演算法 3. 3. 主析取范式法主析取范式法 4. 4. 推理定律法（蘊(yùn)涵演算法）推理定律法（蘊(yùn)涵演算法）例題例題: :判斷推理是否正確判斷推理是否正確【例】【例】“如果我有時(shí)間，那么我就去

5、上街；如果我有時(shí)間，那么我就去上街；如果我上街，那么我就去書店買書；但我沒如果我上街，那么我就去書店買書；但我沒有去書店買書，所以我沒有時(shí)間。有去書店買書，所以我沒有時(shí)間?！?令令 p p：我有時(shí)間。：我有時(shí)間。 q q：我去上街。：我去上街。 r r：我去書店買書。：我去書店買書。 前提：前提：pqpq，qrqr，rr 結(jié)論：結(jié)論：pp 結(jié)論結(jié)論例題例題pqrpq qrrp00011110011101010101101111011000110101010011010101111100 (p(pq)q)(q(qr)r)r r p p推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： （(pq)(qr)r ） p

6、真值表真值表形式上有效的推形式上有效的推理理九條推理定律九條推理定律重言蘊(yùn)涵式：重言蘊(yùn)涵式：1.1.附加律附加律 A AABAB， B BABAB2.2.化簡律化簡律 ABABA A， ABABB B3.3.假言推理假言推理 A(AB)A(AB)B B4.4.拒取式拒取式 B(AB)B(AB)A A聯(lián)言推理聯(lián)言推理ABABA A， ABABB B或或 A,BA,B ABAB 一個(gè)旅行家到歐洲旅行，要坐船回英國。一個(gè)旅行家到歐洲旅行，要坐船回英國。但僅有買船票的錢了，準(zhǔn)備餓著肚子乘但僅有買船票的錢了，準(zhǔn)備餓著肚子乘船了。船了。 挨了一天，實(shí)在受不了了。到餐廳吃完挨了一天，實(shí)在受不了了。到餐廳吃完

7、飯，要帳單。飯，要帳單。 侍者告訴他：飯費(fèi)含在船票里了。侍者告訴他：飯費(fèi)含在船票里了。充分條件假言推理充分條件假言推理A(AB)A(AB)B B 史密斯先生看到一群小孩圍著一只小狗。史密斯先生看到一群小孩圍著一只小狗。問問: :你們干什么呢？你們干什么呢？ “我們?cè)诒荣愓f謊。誰的謊話最大，誰我們?cè)诒荣愓f謊。誰的謊話最大，誰就能得到這只小狗。就能得到這只小狗。” 史密斯：胡鬧！我在你們這個(gè)年齡，可史密斯：胡鬧！我在你們這個(gè)年齡，可從來不說謊話。從來不說謊話。 “史密斯先生，你贏了，小狗歸你。史密斯先生，你贏了，小狗歸你?！北匾獥l件假言推理必要條件假言推理B(AB)B(AB)AA 一班文武官員在看

8、一班文武官員在看七擒孟獲七擒孟獲的川劇。的川劇。 一個(gè)武官：真想不到，孟子的后代孟獲居一個(gè)武官：真想不到，孟子的后代孟獲居然如此野蠻。眾人聽后，不禁掩口而笑。然如此野蠻。眾人聽后，不禁掩口而笑。 哪知一個(gè)文官接口道：仁兄所見極是，還哪知一個(gè)文官接口道：仁兄所見極是，還是孔夫子的后代孔明強(qiáng)一些。是孔夫子的后代孔明強(qiáng)一些。 推理推理：如果孟獲是孟子的后代，那么孔明：如果孟獲是孟子的后代，那么孔明就是孔子的后代了；孔明不是孔子的后代。就是孔子的后代了；孔明不是孔子的后代。所以，所以，九條推理定律九條推理定律重言蘊(yùn)涵式：重言蘊(yùn)涵式：5.5.析取三段論析取三段論 A(AB)A(AB)B B B(AB)B

9、(AB)A A6.6.假言三段論假言三段論 (AB)(BC)(AB)(BC)(AC)(AC)7.7.等價(jià)三段論等價(jià)三段論 (A(AB)(BB)(BC)C)(A(AC)C)選言推理選言推理析取三段論析取三段論 (AB)A(AB)AB B 有一個(gè)議員為了競選州長請(qǐng)海明威為其寫一篇頌揚(yáng)有一個(gè)議員為了競選州長請(qǐng)海明威為其寫一篇頌揚(yáng)的文章。的文章。 第二天，議員收到海明威送來的一封信，卻是一封第二天，議員收到海明威送來的一封信，卻是一封情書。情書。 議員以為海明威弄錯(cuò)了，還是要求幫忙。議員以為海明威弄錯(cuò)了，還是要求幫忙。 議員又收到海明威送來的一封信，卻是一封遺囑。議員又收到海明威送來的一封信，卻是一封

10、遺囑。 海明威：我家除了情書，就是遺囑，你還要什么呢？海明威：我家除了情書，就是遺囑，你還要什么呢？ 選言推理選言推理析取三段論析取三段論 (AB)A(AB)AB B 莎莎替爸爸到郵局買郵票，不知該怎么稱呼莎莎替爸爸到郵局買郵票，不知該怎么稱呼柜臺(tái)里的阿姨，想到人們常稱呼爸爸柜臺(tái)里的阿姨，想到人們常稱呼爸爸“老老板板”，就說：，就說：“老板，我買郵票。老板，我買郵票。”。 “我不是老板，以后別這么喊，好嗎？我不是老板，以后別這么喊，好嗎？” 過了幾天，莎莎又來買郵票：老板娘，我買過了幾天，莎莎又來買郵票：老板娘，我買郵票。郵票。九條推理定律九條推理定律重言蘊(yùn)涵式：重言蘊(yùn)涵式：8.8.構(gòu)造性二難

11、構(gòu)造性二難 (AB)(CD)(AC) (AB)(CD)(AC) BDBD (AB)(AB)(AB)AB)(A(AA)A) B B9.9.破壞性二難破壞性二難 (AB)(CD)(AB)(CD)(BBD) D) ( (AAC)C)上帝不是全能的上帝不是全能的上帝能否創(chuàng)造一塊連他自己也舉不起的石頭？上帝能否創(chuàng)造一塊連他自己也舉不起的石頭？ 如果能，則上帝不是全能的；如果能，則上帝不是全能的； 如果不能，上帝也不是全能的；如果不能，上帝也不是全能的； 或者上帝能創(chuàng)造一塊連他自己也舉不起的石或者上帝能創(chuàng)造一塊連他自己也舉不起的石頭，或者不能，總之上帝不是全能的。頭，或者不能，總之上帝不是全能的。蘇格拉底

12、蘇格拉底 如果你娶到一個(gè)好老婆，你會(huì)獲得人生的如果你娶到一個(gè)好老婆，你會(huì)獲得人生的幸福；幸福； 如果你娶到一個(gè)壞老婆，你會(huì)成為一個(gè)哲如果你娶到一個(gè)壞老婆，你會(huì)成為一個(gè)哲學(xué)家；學(xué)家； 或者娶到好老婆，或者娶到壞老婆；或者娶到好老婆，或者娶到壞老婆； 所以，你或者獲得幸福，或者成為哲學(xué)家。所以，你或者獲得幸福，或者成為哲學(xué)家。不死酒不死酒 有人向漢武帝獻(xiàn)不死酒，被東方朔偷去喝有人向漢武帝獻(xiàn)不死酒，被東方朔偷去喝掉了。掉了。 漢武帝大怒，要?dú)|方朔。漢武帝大怒，要?dú)|方朔。 東方朔說：東方朔說： 我喝的是不死酒，你殺不死我；我喝的是不死酒，你殺不死我； 如果我被殺了，不死酒就是假的。如果我被殺了，不

13、死酒就是假的。竹竿進(jìn)城竹竿進(jìn)城 一個(gè)人進(jìn)城，橫著、豎著都進(jìn)不一個(gè)人進(jìn)城，橫著、豎著都進(jìn)不了城門。了城門。 一個(gè)智者告訴他：為什么不鋸成一個(gè)智者告訴他：為什么不鋸成兩截呢？兩截呢？ 順著拿順著拿P P先生是哪個(gè)島上的人？先生是哪個(gè)島上的人？ 兩個(gè)島，兩個(gè)島，A A島上的人說真話、島上的人說真話、B B島上的人說假島上的人說假話。兩個(gè)島上的人相互往來。話。兩個(gè)島上的人相互往來。 航海家來到一個(gè)島上，碰到航海家來到一個(gè)島上，碰到P P先生。不知他先生。不知他是哪個(gè)島上的人，也不知道這是哪個(gè)島。是哪個(gè)島上的人，也不知道這是哪個(gè)島。 P P先生回答問題只能用先生回答問題只能用“是是”或或“不是不是”。

14、提一個(gè)問題，判斷提一個(gè)問題，判斷P P先生是哪個(gè)島的；先生是哪個(gè)島的； 再提一個(gè)問題，判斷所到的是哪一個(gè)島。再提一個(gè)問題，判斷所到的是哪一個(gè)島。只提一個(gè)問題，判別所到的只提一個(gè)問題，判別所到的是哪一個(gè)島。是哪一個(gè)島。3.2 3.2 自然推理系統(tǒng)自然推理系統(tǒng)P P【例】用推理定理證明【例】用推理定理證明 (pq)(qr)p(pq)(qr)pr r 證明：證明： pq pq p p q q 假言推理假言推理 qr qr r r 假言推理假言推理公式序列公式序列前提前提結(jié)論結(jié)論自然推理系統(tǒng)自然推理系統(tǒng)P P中的證明過程中的證明過程 證明的過程是構(gòu)造一個(gè)證明的過程是構(gòu)造一個(gè)命題公式序列命題公式序列 每

15、個(gè)公式或者是已知的前提，或者是中每個(gè)公式或者是已知的前提，或者是中間結(jié)果間結(jié)果。 換言之，證明的過程是換言之，證明的過程是真值真值1 1傳遞傳遞的過程。的過程。 證明需要在證明需要在形式系統(tǒng)形式系統(tǒng)中進(jìn)行。中進(jìn)行。形式系統(tǒng)形式系統(tǒng)定義定義3.23.2 一個(gè)形式系統(tǒng)一個(gè)形式系統(tǒng) I I 由四部分組成：由四部分組成：（1 1）非空的）非空的字母表字母表 A A；（2 2）合式公式集合式公式集 E E，每個(gè)公式僅含字母表中的符號(hào)；，每個(gè)公式僅含字母表中的符號(hào)；（3 3）公理集公理集 A AX X，每個(gè)公理來自于公式集，每個(gè)公理來自于公式集E E；（4 4）推理規(guī)則集推理規(guī)則集 R R。 記為記為 I

16、=A,E,AI= ,R 四元組（四元組（4 tuple)4 tuple)的形式。的形式。 形式系統(tǒng)分為形式系統(tǒng)分為自然推理系統(tǒng)自然推理系統(tǒng)與與公理推理系統(tǒng)公理推理系統(tǒng)。自然推理系統(tǒng)自然推理系統(tǒng)P P定義定義3.33.3 一個(gè)自然推理系統(tǒng)一個(gè)自然推理系統(tǒng) P P 由三部分組成：由三部分組成： 1.1.字母表字母表 （1 1）命題變?cè)?hào)：）命題變?cè)?hào)：p,q,r, p,q,r, （2 2）聯(lián)結(jié)詞符號(hào)：）聯(lián)結(jié)詞符號(hào)：， （3 3）逗號(hào)，與括號(hào)（）逗號(hào)，與括號(hào)（） 2.2.合式公式合式公式 3.3.推理規(guī)則推理規(guī)則推理規(guī)則推理規(guī)則（1 1）前提引入規(guī)則前提引入規(guī)則 在證明的任何步驟上，都可以引入前

17、提。在證明的任何步驟上，都可以引入前提。 （2 2）結(jié)論引入規(guī)則結(jié)論引入規(guī)則 在證明的任何步驟上，所得到的結(jié)論均可作在證明的任何步驟上，所得到的結(jié)論均可作后續(xù)證明的前提加以引用。后續(xù)證明的前提加以引用。 （3 3）置換規(guī)則置換規(guī)則 在證明的任何步驟上，命題公式中的任何子在證明的任何步驟上，命題公式中的任何子公式都可以用與之等值的公式置換。公式都可以用與之等值的公式置換。推理規(guī)則推理規(guī)則（4 4）假言推理規(guī)則（或分離規(guī)則）假言推理規(guī)則（或分離規(guī)則）： ABAB A A B B （5 5）附加規(guī)則附加規(guī)則： A A ABAB推理規(guī)則推理規(guī)則（6 6）化簡規(guī)則化簡規(guī)則： ABAB A A （7 7）

18、拒取式規(guī)則拒取式規(guī)則： ABAB B B A A （8 8，9 9）三段論規(guī)則三段論規(guī)則： AB ABAB AB BC B BC B AC AAC A 推理規(guī)則推理規(guī)則（1010）構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則： ABAB CD CD ACAC BD BD（1111）破壞性二難推理規(guī)則破壞性二難推理規(guī)則： ABAB CD CD B DB D A A C C通過附加前提，通過附加前提，可由其它規(guī)則推可由其它規(guī)則推出出推理規(guī)則推理規(guī)則（1212）合取引入規(guī)則合取引入規(guī)則： 在證明的在證明的序列序列中出現(xiàn)公式中出現(xiàn)公式A A與與B B，則，則可以在任意步引入可以在任意步引入ABAB。 A A

19、B B ABAB 自然推理系統(tǒng)中的自然推理系統(tǒng)中的“證明證明” 有效的推理：有效的推理： 前提：前提： A A1 1，A A2 2，A Ak k 結(jié)論：結(jié)論： B B 記為：記為：A A1 1AA2 2AAk k B B它的它的證明證明就是構(gòu)造就是構(gòu)造“公式序列公式序列”： C C1 1，C C2 2，C Cl l滿足：滿足： 每個(gè)每個(gè)C Ci i要么是某個(gè)前提要么是某個(gè)前提A Aj j； 要么由推理規(guī)則得到；要么由推理規(guī)則得到； 且且C Cl lB B。 例題例題【例【例3.43.4】 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 若若a a是實(shí)數(shù)，則它不是

20、有理數(shù)就是無理數(shù)；是實(shí)數(shù)，則它不是有理數(shù)就是無理數(shù)； 若若a a不能表示成分?jǐn)?shù)，則它不是有理數(shù)；不能表示成分?jǐn)?shù)，則它不是有理數(shù)； a a是實(shí)數(shù)且不能表示成分?jǐn)?shù)；是實(shí)數(shù)且不能表示成分?jǐn)?shù)； 所以所以，a a是無理數(shù)。是無理數(shù)。 解：命題與推理的符號(hào)化解：命題與推理的符號(hào)化 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ù)。形式化與規(guī)范化的形式化與規(guī)范化的“證明證明”前提：前提：p(qr), sq, psp(qr), sq, ps結(jié)論：結(jié)論：r r 證明證明：（1 1）ps ps 前提引入前提引入（2 2

21、）P P （1 1）化簡）化簡（3 3）s s （1 1）化簡）化簡（4 4）p(qr) p(qr) 前提引入前提引入（5 5）qr qr （2 2）（）（4 4）假言推理）假言推理 （6 6）sq sq 前提引入前提引入（7 7）q q （3 3）（）（6 6）假言推理）假言推理 （8 8）r r （5 5）（）（7 7）三段論）三段論例題例題【例【例3.33.3】 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 前提：前提：pq, qr, ps, pq, qr, ps, s s 結(jié)論：結(jié)論：r(pq) r(pq) 證明證明：（1 1）ps ps 前提引入前提

22、引入（2 2）s s 前提引入前提引入（3 3）p p （1 1）（）（2 2）拒取式）拒取式（4 4）pq pq 前提引入前提引入（5 5）q q （3 3）（）（4 4）三段論）三段論 （6 6）qr qr 前提引入前提引入（7 7）r r （5 5）（）（6 6）假言推理）假言推理 （8 8）r(pq) r(pq) （4 4）（）（7 7）合取引入）合取引入練習(xí)練習(xí)在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明：（1 1）前提：）前提：p(qr), pqp(qr), pq 結(jié)論：結(jié)論： r s r s （2 2）前提：）前提：(pq)r, r s, (pq)r, r s, sp sp 結(jié)論：結(jié)論： q q三種證明方法三種證明方法直接證明法直接證明法附加前提證明法附加前提證明法歸謬法歸謬法附加前提證明法附加前提證明法適用范圍：結(jié)論為蘊(yùn)涵式適用范圍：結(jié)論為蘊(yùn)涵式 A A1 1AA2 2AAn n(AB)(AB) 將推理形式轉(zhuǎn)化為等值形式：將推理形式轉(zhuǎn)化為等值形式： A A1 1AA2 2AAn n AAB B例題例題【例【例3.53.5】 在自然推理系統(tǒng)在自然推理系統(tǒng)P P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 前提：前提：(pq)r, (pq)r, sp, qsp, q 結(jié)論：結(jié)論： sr sr 證明證明：（1 1）s s 附加前提引入