《離散數(shù)學(xué)第二章命題演算的推理理論-假設(shè)推理系統(tǒng).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《離散數(shù)學(xué)第二章命題演算的推理理論-假設(shè)推理系統(tǒng).ppt（25頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第二章 命題演算的推理理論,2.1 命題演算的公理系統(tǒng) 2.2 命題演算的假設(shè)推理系統(tǒng) 2.2.1 假設(shè)推理系統(tǒng)的組成 2.2.2 假設(shè)推理系統(tǒng)的推理過(guò)程 2.3 命題演算的歸結(jié)推理法,,22 命題演算的假設(shè)推理系統(tǒng),假設(shè)推理系統(tǒng)：由于它的推理形式類(lèi)似于日常生活中的推理形式， 也稱(chēng)為自然推理系統(tǒng)。,2.2.1 假設(shè)推理系統(tǒng)的組成,一、擴(kuò)充的推理規(guī)則 二、假設(shè)推理過(guò)程 三、推理定理 四、假設(shè)推理證明定理的方法,一、擴(kuò)充的推理規(guī)則,分離規(guī)則的推廣 A1，A2，，AnA (2) 肯定前提律 A1，A2，A3，，An Ai,分離規(guī)則的推廣,設(shè)有如下的推理規(guī)則

2、 R：若A1，A2，，An ， 可以推出A， 即 R：A1，A2，，An A， 則稱(chēng)A是由 A1，A2，，An實(shí)施規(guī)則R而得。 設(shè)=A1，A2，，An，則上述規(guī)則R可以記為 A 其中為形式前提，A為形式結(jié)論。,肯定前提律,A1，A2，A3，，An Ai (i=1，2，，n)， 即前提中的任何命題均可作為結(jié)論。,二、假設(shè)推理過(guò)程,定義: 如果能夠作出一系列合式公式序列 A1，A2, A3, ，An， 它們(諸Ai)滿(mǎn)足下列性質(zhì)： (1) 或?yàn)楣碇唬?(2) 或?yàn)楣?, 2, ,k之一，每個(gè)i稱(chēng)為假設(shè)； (3) 或由前面的若干個(gè)Ag、Ah利用分離規(guī)則而

3、得； (4) An=B。 稱(chēng)這個(gè)公式序列A1，A2, ，An為由公式 1， 2， ，k證明B的證明過(guò)程.,1， 2， ，k B,三、推理定理,(附加前提證明法 ) 如果，AB，則 AB,要證 (AB)， 即要證 ，A B,附加前提證明法,如果 A1，A2， ，An-1 ，An，AB， 則 A1，A2， ，An-1 ，An AB 進(jìn)而，有下面定理： A1，A2，An-1 An (AB) A1，A2，，An-2 An-1 (An (AB)) 依次類(lèi)推可得定理： A1(A2((An(AB)))),(2) 歸謬法,如果 ，A B 且 ，A B

4、， 則 A。 此定理稱(chēng)為反證律。這里B是一個(gè)公式。,其它公理、規(guī)則同前節(jié)。,四、假設(shè)推理證明定理的方法,(1) 把待證公式的前件一一列出，作為假設(shè)(或把待證公式的后件的否定作為假設(shè))，并在式子后注明為假設(shè)。 (2) 按上述介紹的推理方法進(jìn)行推理，但此時(shí)不能對(duì)假設(shè)實(shí)施代入規(guī)則（因?yàn)榧僭O(shè)不是永真公式）。 (3) 當(dāng)推導(dǎo)出待證公式的后件時(shí)(或推導(dǎo)出矛盾時(shí))就說(shuō)證明了該定理。,第二章 命題演算的推理理論,2.1 命題演算的公理系統(tǒng) 2.2 命題演算的假設(shè)推理系統(tǒng) 2.2.1 假設(shè)推理系統(tǒng)的組成 2.2.2 假設(shè)推理系統(tǒng)的推理過(guò)程 2.3 命題演算的歸結(jié)推理法,,例1：求證 (P

5、(Q R))((PQ)R),證明: (1) P(Q R) 假設(shè) (2) P Q 假設(shè) (3) (PQ)P 公理8 (4) (PQ)Q 公理9 (5) P (3)(2)分離 (6) Q (4)(2)分離 (7) Q R (1)(5)分離 (8) R (6)(7)分離 由假設(shè)推理過(guò)程的定義知： P(Q R)，P Q R 由推理定理得： (P(Q R))((PQ)R),(

6、6) R 在 (5)中用R代入P 有錯(cuò)嗎? 不能對(duì)(5)實(shí)施代入規(guī)則!!!,例2(p21)求證： (PP) P,證明： (1)PP 假設(shè) (2)P 假設(shè)，結(jié)論的否定 (3)P (1)(2)分離 顯然，(2)與(3)表明推出矛盾 (PP), P P (PP), P P 由反證法 得： (PP) P 由推理定理得： (PP) P,例 ((SQ)(PQ)S)P,解: (1) SQ 假設(shè) (2) PQ 假設(shè) (3)

7、S 假設(shè) (4) P 假設(shè), 結(jié)論的否定 (5) Q (1)(3)分離 (6) Q (1)(3)分離 顯然，(5)與(6)表明推出矛盾: SQ, PQ, S, P Q SQ, PQ, S, P Q 由反證法推理定理得： ((SQ)(PQ)S) P,例 (P(QR))((PQ)(PR))),解: (1) P 假設(shè) (2) PQ 假設(shè) (3) P(QR) 假設(shè) (4) Q (1)(2)分離 (

8、5) QR (1)(3)分離 (7) R (4)(5)分離,即證得 P(QR), PQ, P R 亦即證得命題： (P(QR))((PQ)(PR)),例 ((PQ)R)(P(QR)),解: (1) PQR 假設(shè) (2) P 假設(shè) (3) Q 假設(shè) (4) P(Q(PQ)) 公理10 (5) Q(PQ) (2)(4)分離 (6) PQ (3)(5)分離 (7) R (1)(6)分離,即

9、證得 (PQ)R, P, Q R 亦即證得 ((PQ)R)(P(QR)),例 ((PQ)((PR)(QS)))(SR),解: (1) (PQ) ((PR) (QS)) 假設(shè) (2) PQ P 公理8 (3) PQQ 公理9 (4) (PQ) ((PR) (QS)) (PQ) 代入(2) (5) (PQ) ((PR) (QS)) (PR) (QS) 代入(3) (6) PQ (1)(4)分離 (7) (PR)

10、 (QS) (1)(5)分離 (8) ((PR) (QS)) (PR) 代入(2) (9) ((PR) (QS)) (QS) 代入(3) (10) PR (7)(8)分離 (11) QS (7)(9)分離 (12) P (2)(6)分離 (13) Q (3)(6)分離 (14) R (10)(12)分

11、離 (15) S (11)(13)分離 (16) S(R(SR)) 公理10 (17) R(SR) (15)(16)分離 (18) SR (14)(17)分離,例 QQ心情謎語(yǔ),現(xiàn)在是晚上十一點(diǎn)，天很暖。如果我考試通過(guò)了， 那么我很快樂(lè)。 如果我快樂(lè)， 那么陽(yáng)光燦爛。 解： 設(shè) P： 我考試通過(guò)了， Q： 我很快樂(lè)， R： 陽(yáng)光燦爛， S： 天很暖。 前提： PQ， QR， RS,例(續(xù)) Q

12、Q心情謎語(yǔ),(1) PQ 前提引入 (2) QR 前提引入 (3) (PQ)((QR)(PR)) 公理3 (4) (QR)(PR) (1)(3)分離 (5) PR (2)(4)分離 (6) RS 前提引入 (7) PQP 公理8 (8) RSR (7)中,P用R, Q用S代入 (9) R (7)(8)分離 (10) (PQ)(QP) 拒取式，定理3(p18) (11)

13、(PR)(RP) (10)中Q用R代入 (12) RP (5)(11)分離 (13) P (9)(12)分離 所以有效結(jié)論是： 我考試沒(méi)通過(guò)。,例 甲是否盜竊了電腦？,公安人員審一件盜竊案。 已知： (1) 若甲盜竊了電腦， 則作案時(shí)間不能發(fā)生在午夜前。 (2) 若乙證詞正確， 則在午夜時(shí)屋里燈光未滅。 (3) 若乙證詞不正確， 則作案時(shí)間發(fā)生在午夜前。 (4) 午夜時(shí)屋里燈光滅了。 問(wèn)：甲是否盜竊了電腦？,解 設(shè) p： 甲盜竊了電腦 r： 作案時(shí)間發(fā)生在午夜前， s： 乙證詞正確， t： 午夜時(shí)屋里燈光滅了

14、。 前提： pr， st， sr， t,例 (續(xù)) 甲是否盜竊了電腦？,(1) pr (2) st (3) sr (4) t (5) (PQ)(QP) 公理14 (6) (st)(ts) 代入(6) (7) ts (3)(7)分離 (8) s (5)(8)分離 (9) r (4)(9)分離 (10) (pr)(rp) 代入(6) (11) rp (2)(11)分離 (12) p (10)(12)分離,因此可得結(jié)論： 甲不是盜竊犯。,例 誰(shuí)是盜竊犯？,公安人員審一

15、件盜竊案。 已知： (1) 若甲盜竊了電腦， 則作案時(shí)間不能發(fā)生在午夜前。 (2) 若乙證詞正確， 則在午夜時(shí)屋里燈光未滅。 (3) 若乙證詞不正確， 則作案時(shí)間發(fā)生在午夜前。 (4) 午夜時(shí)屋里燈光滅了。 問(wèn)：誰(shuí)是盜竊犯？,解 設(shè) p： 甲盜竊了電腦 r： 作案時(shí)間發(fā)生在午夜前， s： 乙證詞正確， t： 午夜時(shí)屋里燈光滅了。 q： 乙盜竊了電腦 前提： pr， st， sr， t， pq,例 (續(xù)) 誰(shuí)是盜竊犯？,(1) pq (2) pr (3) st (4) sr (5) t,因此可得結(jié)論： 乙是盜竊犯。,(PQ)(QP) 公理14 (st)(ts)

16、 代入(6) ts (3)(7)分離 s (5)(8)分離 r (4)(9)分離 (pr)(rp) 代入(6) rp (2)(11)分離 p (10)(12)分離 (AB) (AB) 析取三段論 (pq) (pq) 代入(14) p q (1)(15)分離 q (13)(16)分離,第二章 命題演算的推理理論,2.1 命題演算的公理系統(tǒng) 2.2 命題演算的假設(shè)推理系統(tǒng) 2.2.1 假設(shè)推理系統(tǒng)的組成 2.2.2 假設(shè)推理系統(tǒng)的推理過(guò)程 2.3 命題演算的歸結(jié)推理法,,