命題邏輯的推理理論課件

1、1第三章第三章:命題邏輯的推理理論命題邏輯的推理理論q主要內(nèi)容主要內(nèi)容l推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)l自然推理系統(tǒng)自然推理系統(tǒng)Pq本章與其他各章的聯(lián)系本章與其他各章的聯(lián)系l本章是第五章的特殊情況和先行準(zhǔn)備本章是第五章的特殊情況和先行準(zhǔn)備2 第一節(jié)：推理的形式結(jié)構(gòu)第一節(jié)：推理的形式結(jié)構(gòu)33.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q何為推理？何為證明？何為推理？何為證明？ 例子：例子： （1）若）若A B且且C D，則，則A C B D （2）若今天是星期一，則明天是星期二）若今天是星期一，則明天是星期二 （3）若）若A C B D，則，則A B且且C Dq推理推理 從前提出發(fā)推出結(jié)論的思維過程從前提出發(fā)推

2、出結(jié)論的思維過程 上例中，（上例中，（1），（），（2）是正確的推理，而）是正確的推理，而（3）是錯(cuò)誤的推理）是錯(cuò)誤的推理q證明證明 描述推理正確或錯(cuò)誤的過程描述推理正確或錯(cuò)誤的過程 43.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q邏輯邏輯(語義語義)蘊(yùn)涵：給定蘊(yùn)涵：給定A1,Ak和和Bv對任意賦值對任意賦值v: 如果如果v(Ai)=T,則則v(B)=T 或者存在或者存在Aj，使得使得v(Aj)=Fv稱由前提稱由前提A1,Ak 推出結(jié)論推出結(jié)論B的推理是有效的的推理是有效的vB為有效結(jié)論為有效結(jié)論v符號：符號：A1,Ak Bq討論討論v蘊(yùn)涵跟蘊(yùn)涵式的關(guān)系？蘊(yùn)涵跟蘊(yùn)涵式的關(guān)系？v注意注意: 推理正確不能保證

3、結(jié)論一定正確推理正確不能保證結(jié)論一定正確5q 例子例子vp, p q qvp, q p qpqp(pq)qp(q p)qFFFFFFFTFTFTTFFFTFTTTTTT3.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)6q定理：定理：A1,Ak B 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A1 Ak B 為重言式為重言式證明證明 必要性必要性：任意：任意v, 不會(huì)出現(xiàn)不會(huì)出現(xiàn)A1 Ak 為真且為真且 B為假的情況，所以為假的情況，所以v(A1 Ak B)=T 充分性充分性：任意：任意v, v(A1 Ak B)=T 則或者：則或者： A1 Ak 和和B同時(shí)為同時(shí)為T 或者：或者： A1 Ak 為假為假 所以所以A1,Ak B 3.1

4、推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)7q蘊(yùn)涵元符號：蘊(yùn)涵元符號：qA1 Ak B 代表代表 A1,Ak Bq推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)v前提：前提：A1,Akv結(jié)論：結(jié)論：Bv推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： A1 Ak B3.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)8q 判斷推理是否正確方法判斷推理是否正確方法v 真值表法真值表法v 等值演算法等值演算法v 主析取范式法主析取范式法3.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)9推理實(shí)例推理實(shí)例例例 判斷下面推理是否正確判斷下面推理是否正確(1) 若今天是若今天是1號，則明天是號，則明天是5號號. 今天是今天是1號號. 所以所以, 明天是明天是5號號. (2) 若今天是若今天是

5、1號，則明天是號，則明天是5號號. 明天是明天是5號號. 所以所以, 今天是今天是1號號. 解解 設(shè)設(shè) p：今天是：今天是1號，號，q：明天是：明天是5號號. (1) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): (pq) pq用等值演算法用等值演算法 (pq) pq ( p q) p) q pq q 1 由定理由定理3.1可知推理正確可知推理正確10推理實(shí)例推理實(shí)例(2) 推理的形式結(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, 故故0

6、1是成假賦值，所以推理不正確是成假賦值，所以推理不正確113.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q推理定律推理定律l推理定律推理定律重言蘊(yùn)涵式重言蘊(yùn)涵式l重要的推理定律：重要的推理定律： A (A B) 附加律附加律 (A B) A 化簡律化簡律例例1： 如果誰驕傲自滿，那么他就要落后；小張驕傲自滿，如果誰驕傲自滿，那么他就要落后；小張驕傲自滿， 所以，小張必定要落后所以，小張必定要落后 (AB) A B 假言推理假言推理例例2： 如果誰得了肺炎，他就一定要發(fā)燒；小李沒發(fā)燒，如果誰得了肺炎，他就一定要發(fā)燒；小李沒發(fā)燒， 所以，小李沒患肺炎所以，小李沒患肺炎 (AB)B A 拒取式拒取式123.1 推

7、理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q例例3： 如果降落的物體不受外力的影響，那么，它不如果降落的物體不受外力的影響，那么，它不 會(huì)改變降落的方向；這個(gè)物體受到了外力的會(huì)改變降落的方向；這個(gè)物體受到了外力的 影響，影響， 所以，它會(huì)改變降落的方向所以，它會(huì)改變降落的方向 q例例4： 如果趙某是走私犯，那么，他應(yīng)受法律制裁；如果趙某是走私犯，那么，他應(yīng)受法律制裁； 經(jīng)查明，趙某確實(shí)受到了法律制裁，經(jīng)查明，趙某確實(shí)受到了法律制裁， 所以，趙某是走私犯所以，趙某是走私犯133.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q例例5： 我要么選擇湯要么選擇色拉；我不選擇湯。我要么選擇湯要么選擇色拉；我不選擇湯。 所以，我選擇色拉所以

8、，我選擇色拉 (A B)B A 析取三段論析取三段論q例例6： 如果我不能起床，則我不能上班。如果我不能起床，則我不能上班。 如果我不能上班，則我不能得到報(bào)酬。如果我不能上班，則我不能得到報(bào)酬。 所以，如果我不能起床，則我不能得到報(bào)酬所以，如果我不能起床，則我不能得到報(bào)酬 (AB) (BC) (AC) 假言三段論假言三段論 (AB) (BC) (AC) 等價(jià)三段論等價(jià)三段論143.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q 例例7： 東方朔偷飲了漢武帝求得的據(jù)說飲了能夠不死的酒，東方朔偷飲了漢武帝求得的據(jù)說飲了能夠不死的酒，漢武帝要?dú)⑺?，他說：漢武帝要?dú)⑺?，他說：“如果這酒真能使人不死，那么如果這酒真能使

9、人不死，那么你就殺不死我；如果這酒不能使人不死你就殺不死我；如果這酒不能使人不死(你能殺得死我你能殺得死我)，那么它就沒有什么用處（不必殺我）；這酒或者能使人那么它就沒有什么用處（不必殺我）；這酒或者能使人不死，或者不能使人不死；所以你或者殺不死我，或者不死，或者不能使人不死；所以你或者殺不死我，或者不必殺我。不必殺我?！?(AB) (CD) (A C) (B D) 構(gòu)造性二難構(gòu)造性二難 (AB) ( AB) B 構(gòu)造性二難構(gòu)造性二難 （特殊形式）（特殊形式）153.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q例例8： If it rains, we will stay inside. If it is s

10、unny, we will go for a walk. Either we will not stay inside, or we will not go for a walk. Therefore, either it will not rain, or it will not be sunny. (AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難163.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)q普羅泰戈拉收了一名學(xué)生叫歐提勒士。普氏與他簽訂了這樣一份合同：前者向后普羅泰戈拉收了一名學(xué)生叫歐提勒士。普氏與他簽訂了這樣一份合同：前者向后者傳授辯論技巧，教他幫人打官司；后者入學(xué)時(shí)交一半學(xué)費(fèi)，

11、另一半學(xué)費(fèi)則在他者傳授辯論技巧，教他幫人打官司；后者入學(xué)時(shí)交一半學(xué)費(fèi)，另一半學(xué)費(fèi)則在他畢業(yè)后幫人打官司贏了之后再交。時(shí)光荏苒，歐氏從普氏那里畢業(yè)了。但他總不畢業(yè)后幫人打官司贏了之后再交。時(shí)光荏苒，歐氏從普氏那里畢業(yè)了。但他總不幫人打官司，普氏于是就總得不到那另一半學(xué)費(fèi)。幫人打官司，普氏于是就總得不到那另一半學(xué)費(fèi)。普氏為了要那另一半學(xué)費(fèi)，他去與歐氏打官司，并打著這樣的如意算盤：普氏為了要那另一半學(xué)費(fèi)，他去與歐氏打官司，并打著這樣的如意算盤： 如果歐氏打贏了這場官司，按照合同的規(guī)定，他應(yīng)該給我另一半學(xué)費(fèi)。如果歐氏打贏了這場官司，按照合同的規(guī)定，他應(yīng)該給我另一半學(xué)費(fèi)。 如果歐氏打輸了這場官司，按照法

12、庭的裁決，他應(yīng)該給我另一半學(xué)費(fèi)。如果歐氏打輸了這場官司，按照法庭的裁決，他應(yīng)該給我另一半學(xué)費(fèi)。 歐氏或者打贏這場官司，或者打輸這場官司。歐氏或者打贏這場官司，或者打輸這場官司。 總之，他應(yīng)該付給我另一半學(xué)費(fèi)?？傊?，他應(yīng)該付給我另一半學(xué)費(fèi)。 但歐氏卻對普氏說：但歐氏卻對普氏說： 如果這場官司我打贏了，按照法庭的裁決，我不應(yīng)該給您另一半學(xué)費(fèi)。如果這場官司我打贏了，按照法庭的裁決，我不應(yīng)該給您另一半學(xué)費(fèi)。 如果這場官司我打輸了，按照合同的規(guī)定，我不應(yīng)該給您另一半學(xué)費(fèi)。如果這場官司我打輸了，按照合同的規(guī)定，我不應(yīng)該給您另一半學(xué)費(fèi)。 我或者打贏這場官司，或者打輸這場官司。我或者打贏這場官司，或者打輸這場

13、官司。 總之，我不應(yīng)該付另一半學(xué)費(fèi)總之，我不應(yīng)該付另一半學(xué)費(fèi) 究竟誰的說法對呢？究竟誰的說法對呢？17q推理定律推理定律A (A B)(A B) A(A B) A B(A B) B A(A B) B A(A B) (B C) (A C) (A B) (B C) (A C) (A B) (C D) (A C) (B D)(A B) ( A B) B(A B) (C D) ( B D) ( A C)附加律附加律破壞性二難破壞性二難構(gòu)造性二難（特殊形式）構(gòu)造性二難（特殊形式）構(gòu)造性二難構(gòu)造性二難等價(jià)三段論等價(jià)三段論假言三段論假言三段論析取三段論析取三段論拒取式拒取式假言推理假言推理化簡律化簡律3.1

14、 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)18證明：證明：(A B) (B C) (A C) (A B) (B C) (A C) ( A B) ( B C) (A C) ( A B) ( B C) (A C) (A B) (B C) (A C) (A B) (B C) ( A C) (A B) A ) (B C) C) ( B A ) (B C) 13.1 推理形式結(jié)構(gòu)推理形式結(jié)構(gòu)19 第二節(jié)：自然推理系統(tǒng)第二節(jié)：自然推理系統(tǒng)P203.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq自然演繹推理自然演繹推理：從一組已知為真的事實(shí)出發(fā)，：從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯推理規(guī)則推出結(jié)論的過程直接運(yùn)用經(jīng)典邏輯推理規(guī)則推

15、出結(jié)論的過程q為什么要自然演繹為什么要自然演繹(Natural Deduction)？給出驗(yàn)證給出驗(yàn)證的推理過程的推理過程q需要引入需要引入證明證明的概念的概念 一個(gè)描述推理過程的命題公式序列，其中的每個(gè)公一個(gè)描述推理過程的命題公式序列，其中的每個(gè)公式或者是已知前提，或者是由前面的公式應(yīng)用到推理規(guī)式或者是已知前提，或者是由前面的公式應(yīng)用到推理規(guī)則得到的結(jié)論則得到的結(jié)論q自然演繹模擬人類的推理自然演繹模擬人類的推理A1 Ak B213.2 自然推理系統(tǒng)自然推理系統(tǒng)P定義定義3.2 一個(gè)一個(gè)形式系統(tǒng)形式系統(tǒng) I 由下面四個(gè)部分組成：由下面四個(gè)部分組成： (1) 非空的字母表，記作非空的字母表，記作

16、 A(I). (2) A(I) 中符號構(gòu)造的合式公式集，記作中符號構(gòu)造的合式公式集，記作 E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作中一些特殊的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作推理規(guī)則集，記作 R(I). 記記I=, 其中其中是是 I 的的形形式語言系統(tǒng)式語言系統(tǒng), 是是 I 的的形式演算系統(tǒng)形式演算系統(tǒng).自然推理系統(tǒng)自然推理系統(tǒng): 無公理無公理, 即即AX(I)=公理推理系統(tǒng)公理推理系統(tǒng) 推出的結(jié)論是系統(tǒng)中的重言式推出的結(jié)論是系統(tǒng)中的重言式, 稱作稱作定理定理22自然推理系統(tǒng)自然推理系統(tǒng)P定義定義3.3 自然推理系統(tǒng)自然推理系統(tǒng) P 定義如

17、下定義如下:1. 字母表字母表 (1) 命題變項(xiàng)符號：命題變項(xiàng)符號：p, q, r, , pi, qi, ri, (2) 聯(lián)結(jié)詞符號：聯(lián)結(jié)詞符號： , , , , (3) 括號與逗號：括號與逗號：(, ), ，2. 合式公式（同定義合式公式（同定義1.6）3. 推理規(guī)則推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則 (2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則 (3) 置換規(guī)則置換規(guī)則233.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 假言推理規(guī)則假言推理規(guī)則 A B A 結(jié)論：結(jié)論：B(A B) A BAll men are mortal Socrates is a man Therefore Socrates is

18、 mortal 243.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 附加規(guī)則附加規(guī)則 A 結(jié)論：結(jié)論：A BA (A B)253.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 化簡規(guī)則化簡規(guī)則 A B 結(jié)論：結(jié)論：A q 合取引入規(guī)則合取引入規(guī)則 A B 結(jié)論：結(jié)論：A B(A B) A263.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq證明證明: p, q, p q r r273.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 證明證明: p, q, p q r r p q p q p q r r推理過程可以寫成證明樹推理過程可以寫成證明樹283.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 拒取式規(guī)則拒取式規(guī)則 A B B 結(jié)論：結(jié)論： A q 假

19、言三段式規(guī)則假言三段式規(guī)則 A B B C 結(jié)論：結(jié)論：A C(A B) B A(A B) (B C) (A C) 293.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 析取三段式規(guī)則析取三段式規(guī)則 A B B 結(jié)論：結(jié)論： A q 構(gòu)造二難推理規(guī)則構(gòu)造二難推理規(guī)則 A B C D A C 結(jié)論：結(jié)論： B D(A B) B A(A B) (C D) (A C) (B D)303.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 破壞性二難推理規(guī)則破壞性二難推理規(guī)則 A B C D B D 結(jié)論：結(jié)論： A C (A B) (C D) ( B D) ( A C)313.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 形式推演形式推演(

20、語法蘊(yùn)涵語法蘊(yùn)涵)：給定給定A1,Ak和和Bv 符號：符號：A1,Ak Bv 存在公式序列存在公式序列C1, C2,Cn，對每個(gè)，對每個(gè)i(i=1,n),Ci是某個(gè)是某個(gè)Aj或者或者Ci是由序列中前面的公式應(yīng)用推理規(guī)則得到是由序列中前面的公式應(yīng)用推理規(guī)則得到Cn=Bv 稱稱C1,Cn是由是由A1,Ak推推B的證明的證明 323.2 自然推理系統(tǒng)自然推理系統(tǒng)P：考慮下述論證v如果這里有球賽，則通行是困難的如果這里有球賽，則通行是困難的v如果他們按時(shí)到達(dá)，則通行是不困難的如果他們按時(shí)到達(dá)，則通行是不困難的v他們按時(shí)到達(dá)了他們按時(shí)到達(dá)了 問：得到什么結(jié)論？問：得到什么結(jié)論？333.2 自然推理系統(tǒng)自

21、然推理系統(tǒng)P：考慮下述論證v 如果這里有球賽，則通行是困難的如果這里有球賽，則通行是困難的v 如果他們按時(shí)到達(dá)，則通行是不困難的如果他們按時(shí)到達(dá)，則通行是不困難的v 他們按時(shí)到達(dá)了他們按時(shí)到達(dá)了 問：得到什么結(jié)論？問：得到什么結(jié)論？設(shè)設(shè) p:這里有球賽這里有球賽 q:通行是困難的通行是困難的 r:他們按時(shí)到達(dá)他們按時(shí)到達(dá) p q r q r p 343.2 自然推理系統(tǒng)自然推理系統(tǒng)Pv 前提前提p q， r q，rv 結(jié)論：結(jié)論： p 解解： rv r qv qv p q p 前提引入前提引入前提引入前提引入假言推理假言推理前提引入前提引入拒取式拒取式353.2 自然推理系統(tǒng)自然推理系統(tǒng)Pc

22、d, c r, d s r s 解解： c dv c dv d sv c sv c rv r cv r s r s 前提引入前提引入前提引入前提引入假言三段論假言三段論前提引入前提引入 置換規(guī)則置換規(guī)則置換規(guī)則置換規(guī)則假言三段論假言三段論置換規(guī)則置換規(guī)則363.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 構(gòu)造證明的方法構(gòu)造證明的方法v 附加前提證明法附加前提證明法v 歸謬法歸謬法 373.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 附加前提證明法附加前提證明法v 對形如對形如 (A1 Ak) (A B)的證明的證明 轉(zhuǎn)化為：轉(zhuǎn)化為： A1, , Ak, A B383.2 自然推理系統(tǒng)自然推理系統(tǒng)P(p(q s)(

23、rp)q) (r s) 393.2 自然推理系統(tǒng)自然推理系統(tǒng)P(p(q s)(rp)q) (r s) 解解： rv rpv r pv pv p(q s)v q sv q s 前提引入前提引入前提引入前提引入假言推理假言推理前提引入前提引入置換規(guī)則置換規(guī)則假言推理假言推理假言推理假言推理前提引入前提引入403.2 自然推理系統(tǒng)自然推理系統(tǒng)Pq 歸謬法歸謬法v 對形如對形如 (A1 Ak) B的證明的證明 轉(zhuǎn)化為：轉(zhuǎn)化為： A1 Ak B為矛盾式為矛盾式413.2 自然推理系統(tǒng)自然推理系統(tǒng)Prq rs sq pq p423.2 自然推理系統(tǒng)自然推理系統(tǒng)Prq rs sq pq p解解： pv p

24、qv qv s qv q sv sv rsv rv rq q43第三章第三章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)l 判斷推理是否正確的方法判斷推理是否正確的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系統(tǒng)自然推理系統(tǒng)Pl 構(gòu)造推理證明的方法構(gòu)造推理證明的方法 直接證明法直接證明法 附加前提證明法附加前提證明法 歸謬法歸謬法(反證法反證法)44基本要求基本要求l 理解并記住推理形式結(jié)構(gòu)的兩種形式：理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)

25、論：Bl 熟練掌握判斷推理是否正確的不同方法（如真值熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）表法、等值演算法、主析取范式法等）l 牢記牢記 P 系統(tǒng)中各條推理規(guī)則系統(tǒng)中各條推理規(guī)則l 熟練掌握構(gòu)造證明的直接證明法、附加前提證明熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬法法和歸謬法l 會(huì)解決實(shí)際中的簡單推理問題會(huì)解決實(shí)際中的簡單推理問題45練習(xí)練習(xí)1：判斷推理是否正確：判斷推理是否正確1. 判斷下面推理是否正確判斷下面推理是否正確: (1) 前提：前提： pq, q 結(jié)論：結(jié)論： p 解解 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): ( pq)qp 方法一：等值演算法方法一：等值演算法 ( pq)qp (p q)q)p ( pq) qp ( p q) ( q q)p p q易知易知10是成假賦值，不是重言式，所以推理不正確是成假賦值，不是重言式，所以推理不正確.46練習(xí)練習(xí)1解答解答方法二：主析取范式法，方法二：主析取范式法， ( pq)qp (p q)q)p p q M2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正確推理不正確.47練習(xí)練習(xí)1解答解答方法三方法三 真值表法真值表法 不是重言式不是重言式, 推理不正確推理不正確111001110100( pq)qpqp pq 0 1 1