《離散數(shù)學第二章命題演算的推理理論-假設推理系統(tǒng).ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學第二章命題演算的推理理論-假設推理系統(tǒng).ppt（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

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

5、(Q R))((PQ)R),證明: (1) P(Q R) 假設 (2) P Q 假設 (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)分離 由假設推理過程的定義知： P(Q R)，P Q R 由推理定理得： (P(Q R))((PQ)R),(

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

7、S 假設 (4) P 假設, 結(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 假設 (2) PQ 假設 (3) P(QR) 假設 (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 假設 (2) P 假設 (3) Q 假設 (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)) 假設 (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心情謎語,現(xiàn)在是晚上十一點，天很暖。如果我考試通過了， 那么我很快樂。 如果我快樂， 那么陽光燦爛。 解： 設 P： 我考試通過了， Q： 我很快樂， R： 陽光燦爛， S： 天很暖。 前提： PQ， QR， RS,例(續(xù)) Q

12、Q心情謎語,(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é)論是： 我考試沒通過。,例 甲是否盜竊了電腦？,公安人員審一件盜竊案。 已知： (1) 若甲盜竊了電腦， 則作案時間不能發(fā)生在午夜前。 (2) 若乙證詞正確， 則在午夜時屋里燈光未滅。 (3) 若乙證詞不正確， 則作案時間發(fā)生在午夜前。 (4) 午夜時屋里燈光滅了。 問：甲是否盜竊了電腦？,解 設 p： 甲盜竊了電腦 r： 作案時間發(fā)生在午夜前， s： 乙證詞正確， t： 午夜時屋里燈光滅了

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é)論： 甲不是盜竊犯。,例 誰是盜竊犯？,公安人員審一

15、件盜竊案。 已知： (1) 若甲盜竊了電腦， 則作案時間不能發(fā)生在午夜前。 (2) 若乙證詞正確， 則在午夜時屋里燈光未滅。 (3) 若乙證詞不正確， 則作案時間發(fā)生在午夜前。 (4) 午夜時屋里燈光滅了。 問：誰是盜竊犯？,解 設 p： 甲盜竊了電腦 r： 作案時間發(fā)生在午夜前， s： 乙證詞正確， t： 午夜時屋里燈光滅了。 q： 乙盜竊了電腦 前提： pr， st， sr， t， pq,例 (續(xù)) 誰是盜竊犯？,(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 命題演算的假設推理系統(tǒng) 2.2.1 假設推理系統(tǒng)的組成 2.2.2 假設推理系統(tǒng)的推理過程 2.3 命題演算的歸結(jié)推理法,,