ch03命題邏輯的推理理論.ppt

09:35:38,1,主要內(nèi)容 推理的形式結(jié)構(gòu) 自然推理系統(tǒng)P推理的正確與錯(cuò)誤 判斷推理正確的方法 推理定律 形式系統(tǒng)的定義與分類 自然推理系統(tǒng)P 在P中構(gòu)造證明:直接證明法、附加前提證明法、歸謬法,第三章 命題邏輯的推理理論,09:35:38,2,3.1 推理的形式結(jié)構(gòu),定義3.1 設(shè)A1, A2, , Ak, B為命題公式. 若對(duì)于每組賦值，A1A2 Ak 為假，或當(dāng)A1A2Ak為真時(shí)，B也為真，則稱由前提A1, A2, , Ak推出結(jié)論B的推理是有效的或正確的, 并稱B是有效結(jié)論.,定理3.1 由命題公式A1, A2, , Ak 推B的推理正確當(dāng) 且僅當(dāng)A1A2AkB為重言式,09:35:38,3,3.1 推理的形式結(jié)構(gòu),注意: 推理正確不能保證結(jié)論一定正確 必須把推理的有效性和結(jié)論的真實(shí)性區(qū)別開。有效的推理不一定產(chǎn)生真實(shí)的結(jié)論，產(chǎn)生真實(shí)結(jié)論的推理過程未必一定是有效的。再說，有效的推理中可能包含假的前提；而無效的推理卻可能包含真的前提。,09:35:38,4,3.1 推理的形式結(jié)構(gòu),可見，推理的有效性是一回事，前提與結(jié)論的真實(shí)與否是另一回事。所謂推理有效，指它的結(jié)論是它的前提的合乎邏輯的結(jié)果，也即，如果它的前提都為真，那么所得結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或?yàn)榧?。如果推理是有效的話，那么不可能它的前提都為真時(shí)而它的結(jié)論為假。,09:35:38,5,推理的形式結(jié)構(gòu),2. A1A2AkB 若推理正確, 記為A1 A2 Ak B 3. 前提： A1, A2, , Ak 結(jié)論： B 判斷推理是否正確的方法: 真值表法 等值演算法 主析取范式法,推理的形式結(jié)構(gòu) 1. A1, A2, , Ak B 若推理正確, 記為A1,A2,An B,09:35:38,6,推理實(shí)例,例1 判斷下面推理是否正確 (1) 若今天是1號(hào)，則明天是5號(hào). 今天是1號(hào). 所以, 明天是5號(hào). (2) 若今天是1號(hào)，則明天是5號(hào). 明天是5號(hào). 所以, 今天是1號(hào).,解 設(shè) p：今天是1號(hào)，q：明天是5號(hào). (1) 推理的形式結(jié)構(gòu):,(pq)pq,用等值演算法 (pq)pq (pq)p)q pqq 1 由定理3.1可知推理正確,09:35:38,7,推理實(shí)例,(2) 推理的形式結(jié)構(gòu):,(pq)qp,用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 結(jié)果不含m1, 故01是成假賦值，所以推理不正確,09:35:38,8,推理實(shí)例,例2 判斷下面推理是否正確 如果小張和小王去看電影，則小李也去看電影。小趙不去看電影或小張去看電影。小王也去看電影。所以，當(dāng)小趙去看電影時(shí)，小李必定也去。 解：令 p: 小張去看電影； q: 小王去看電影； r: 小李去看電 影； s: 小趙去看電影。 推理的形式結(jié)構(gòu): 前提： (p q) r, sp, q 結(jié)論： s r ( (p q) r) ( sp) q (s r),推理的形式結(jié)構(gòu):,09:35:38,9,推理定律重言蘊(yùn)涵式,1. A (AB) 附加律 2. (AB) A 化簡(jiǎn)律 3. (AB)A B 假言推理 4. (AB)B A 拒取式 5. (AB)B A 析取三段論 6. (AB)(BC) (AC) 假言三段論 7. (AB)(BC) (AC) 等價(jià)三段論 8. (AB)(CD)(AC) (BD) 構(gòu)造性二難 (AB)(AB) B 構(gòu)造性二難(特殊形式) 9. (AB)(CD)( BD) (AC) 破壞性二難 每個(gè)等值式可產(chǎn)生兩個(gè)推理定律 如, 由AA可產(chǎn)生 AA 和 AA,09:35:38,10,自然推理系統(tǒng)簡(jiǎn)介,自然推理系統(tǒng)。與公理系統(tǒng)相對(duì)，是按照自然演繹思想構(gòu)造的形式系統(tǒng)。其出發(fā)點(diǎn)是一些變形規(guī)則或推演規(guī)則，但沒有公理。應(yīng)用變形規(guī)則可以推出一些定理。 自然推理系統(tǒng)更接近于一般的數(shù)學(xué)思維，所以許多成熟的邏輯演算公理系統(tǒng)都有與之等價(jià)的自然推理系統(tǒng)。自然推理系統(tǒng)是在世紀(jì)年代第一次分別由甘岑和杰司柯夫斯基獨(dú)立提出。自然推理系統(tǒng)主要是強(qiáng)調(diào)推理規(guī)則的重要性，通過對(duì)規(guī)則的應(yīng)用可以從假設(shè)得出推斷。,09:35:38,11,3.2 自然推理系統(tǒng)P,定義3.2 一個(gè)形式系統(tǒng) I 由下面四個(gè)部分組成： (1) 非空的字母表，記作 A(I). (2) A(I) 中符號(hào)構(gòu)造的合式公式集，記作 E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作 R(I). 記I=, 其中是 I 的 形式語言系統(tǒng), 是 I 的形式演算系統(tǒng). 自然推理系統(tǒng): 無公理, 即AX(I)= 公理推理系統(tǒng) 推出的結(jié)論是系統(tǒng)中的重言式, 稱作定理,09:35:38,12,自然推理系統(tǒng)P,定義3.3 自然推理系統(tǒng) P 定義如下: 1. 字母表 (1) 命題變項(xiàng)符號(hào)：p, q, r, , pi, qi, ri, (2) 聯(lián)結(jié)詞符號(hào)：, , , , (3) 括號(hào)與逗號(hào)：(, ), ， 2. 合式公式（同定義1.6） 3. 推理規(guī)則 (1) 前提引入規(guī)則 (2) 結(jié)論引入規(guī)則 (3) 置換規(guī)則,09:35:38,13,推理規(guī)則,(4) 假言推理規(guī)則 (6) 化簡(jiǎn)規(guī)則 (8) 假言三段論規(guī)則,(5) 附加規(guī)則 (7) 拒取式規(guī)則 (9) 析取三段論規(guī)則,09:35:38,14,推理規(guī)則,(10) 構(gòu)造性二難推理規(guī)則 (11) 破壞性二難推理規(guī)則 (12) 合取引入規(guī)則,09:35:38,15,在自然推理系統(tǒng)P中構(gòu)造證明,設(shè)前提A1, A2, Ak,結(jié)論B及公式序列C1, C2, Cl.如果每一個(gè)Ci(1il)是某個(gè)Aj, 或者可由序列中前面的公式應(yīng)用推理規(guī)則得到, 并且Cl =B, 則稱這個(gè)公式序列是由A1, A2, Ak推出B的證明,09:35:38,16,在自然推理系統(tǒng)P中構(gòu)造證明,例3 構(gòu)造下面推理的證明： 若明天是星期一或星期三，我明天就有課. 若我明天有 課，今天必備課. 我今天沒備課. 所以，明天不是星期一、也不是星期三. 解 (1) 設(shè)命題并符號(hào)化 設(shè) p：明天是星期一，q：明天是星期三， r：我明天有課，s：我今天備課,09:35:38,17,直接證明法,(2) 寫出證明的形式結(jié)構(gòu) 前提：(pq)r, rs, s 結(jié)論：pq (3) 證明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置換,09:35:38,18,附加前提證明法,附加前提證明法: 適用于結(jié)論為蘊(yùn)涵式 欲證 前提：A1, A2, , Ak 結(jié)論：CB 等價(jià)地證明 前提：A1, A2, , Ak, C 結(jié)論：B 理由：(A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,09:35:38,19,附加前提證明法實(shí)例,例4 構(gòu)造下面推理的證明 2是素?cái)?shù)或合數(shù). 若2是素?cái)?shù)，則 是無理數(shù). 若 是無理數(shù)，則4不是素?cái)?shù). 所以，如果4是素?cái)?shù)，則2是合數(shù). 解 用附加前提證明法構(gòu)造證明 (1) 設(shè) p：2是素?cái)?shù)，q：2是合數(shù)， r： 是無理數(shù)，s：4是素?cái)?shù) (2) 推理的形式結(jié)構(gòu) 前提：pq, pr, rs 結(jié)論：sq,09:35:38,20,附加前提證明法實(shí)例,(3) 證明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段論 p 拒取式 pq 前提引入 q 析取三段論,09:35:38,21,歸謬法（反證法）,歸謬法 (反證法) 欲證 前提：A1, A2, , Ak 結(jié)論：B 做法: 在前提中加入B，推出矛盾. 理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,09:35:38,22,歸謬法實(shí)例,例5 前提：(pq)r, rs, s, p 結(jié)論：q 證明 用歸繆法 q 結(jié)論否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段論 pq 置換 p 析取三段論 p 前提引入 pp 合取,09:35:38,23,第三章 習(xí)題課,主要內(nèi)容 推理的形式結(jié)構(gòu) 判斷推理是否正確的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系統(tǒng)P 構(gòu)造推理證明的方法 直接證明法 附加前提證明法 歸謬法(反證法),09:35:38,24,基本要求,理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 結(jié)論：B 熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等） 牢記 P 系統(tǒng)中各條推理規(guī)則 熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬 法 會(huì)解決實(shí)際中的簡(jiǎn)單推理問題,09:35:38,25,練習(xí)1：判斷推理是否正確,1. 判斷下面推理是否正確: (1) 前提：pq, q 結(jié)論：p,解 推理的形式結(jié)構(gòu):,(pq)qp,方法一：等值演算法 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq,易知10是成假賦值，不是重言式，所以推理不正確.,09:35:38,26,練習(xí)1解答,方法二：主析取范式法， (pq)qp (pq)q)p pq M2 m0m1m3 未含m2, 不是重言式, 推理不正確.,09:35:38,27,練習(xí)1解答,方法三 真值表法 不是重言式, 推理不正確,方法四 直接觀察出10是成假賦值,09:35:38,28,練習(xí)1解答,用等值演算法 (qr)(pr)(qp) (qr)(pr)(qp) (qr)(pr)(qp) (qp)(qr)(rp)(qp) (qp)(qr)(rp)(qp) 1 推理正確,(2) 前提：qr, pr 結(jié)論：qp,解 推理的形式結(jié)構(gòu)：,(qr)(pr)(qp),09:35:38,29,練習(xí)2：構(gòu)造證明,2. 在系統(tǒng)P中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和 園游人太多，就不去頤和園. 今天是周六，并且頤和園游 人太多. 所以, 我們?nèi)A明園或動(dòng)物園玩.,證明： (1) 設(shè) p：今天是周六，q：到頤和園玩， r：到圓明園玩，s：頤和園游人太多 t：到動(dòng)物園玩 (2) 前提：p(qr), sq, p, s 結(jié)論：rt,09:35:38,30,練習(xí)2解答,(3) 證明： p(qr) 前提引入 p 前提引入 qr 假言推理 sq 前提引入 s 前提引入 q 假言推理 r 析取三段論 rt 附加,09:35:38,31,命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用,邏輯難題 可以用邏輯推理解決的難題稱為邏輯難題。求解邏輯難題是實(shí)踐邏輯規(guī)則的一種好方法。同樣，涉及用于執(zhí)行邏輯推理的計(jì)算機(jī)程序通常也使用著名的邏輯難題來演示它們的能力。許多人對(duì)求解邏輯難題感興趣，有許多書和雜志也登載邏輯難題以供娛樂。,09:35:38,32,命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用,這是著名物理學(xué)家愛因斯坦出過的一道題。 一個(gè)土耳其商人，想找一個(gè)十分聰明的助手協(xié)助他經(jīng)商，有兩個(gè)人前來應(yīng)聘。這個(gè)商人為了試一試哪一個(gè)聰明些，就把兩個(gè)人帶進(jìn)一間漆黑的屋子里，他打開電燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的?，F(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€(gè)人每人摸一頂帽子戴在頭上，在我開燈后，請(qǐng)你們盡快地說出自己頭上戴的帽子是什么顏色的。”說完之后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時(shí)商人將余下的兩頂帽子藏了起來接著把電燈打開，這時(shí)那兩個(gè)應(yīng)試者看到商人頭上戴的是一頂紅帽子，過了一會(huì)兒，其中一個(gè)人便喊到：“我戴的是黑帽子?！?請(qǐng)問這個(gè)人猜得對(duì)嗎？是怎么推導(dǎo)出來的？,09:35:38,33,命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用,分析1：如果我戴的也是紅帽子，那么，B就馬上可以猜到自己是戴黑帽子(因?yàn)榧t帽子只有兩頂)；而現(xiàn)在B并沒有立刻猜到，可見，我戴的不是紅帽子。 可見，B的反應(yīng)太慢了。,09:35:38,34,命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用,分析2：設(shè)P1表示“猜對(duì)的人戴紅帽子”；P2表示“猜對(duì)的人戴黑帽子”；Q1表示“另一個(gè)人戴紅帽子”；Q2表示“另一個(gè)人戴黑帽子”；R1表示“商人戴紅帽子”。 現(xiàn)在知道，商人頭上戴的是紅帽子，即R1為真，又知道另一個(gè)人沒有作出斷定，即既不能斷定Q1為真，也不能斷定Q2為真。,09:35:38,35,命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用,根據(jù)題設(shè)條件，可得如下公式： R1P1Q2：如果商人和猜對(duì)的人戴的都是紅帽子，那么另一個(gè)戴的就是黑帽子，因?yàn)榧t帽子只有兩頂。 R1Q1P2：如果商人和另一個(gè)戴的都是紅帽子，那么猜對(duì)的人戴的就是黑帽子。 P1P2：如果猜對(duì)的人戴的不是紅帽子，那么他戴的就是黑帽子。 Q1Q2：如果另一個(gè)人戴的不是紅帽子，那