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

1、目錄（ 數(shù)理邏輯） 第一章 命題演算基礎(chǔ) （ 6學(xué)時(shí)） 第二章 命題演算的推理理論（ 4學(xué)時(shí) ） 第三章 謂詞演算基礎(chǔ)（ 5學(xué)時(shí)） 第四章 謂詞演算的推理理論（ 5學(xué)時(shí)） 第五章 遞歸函數(shù)論（ 4學(xué)時(shí)） 第二章 命題演算的推理理論 例 判斷下面各推理是否正確 : (1) 如果天氣涼快 ,小王就不去游泳。 天氣涼快 , 所以小王沒去游泳。 (2) 如果天氣涼快 ,小王就不去游泳。 天氣不涼快 , 所以小王去游泳了。 推理是否正確： 形式化 引入符號(hào)： P表示天氣涼快， Q表示小王去游泳 (1)如果天氣涼快 ,小王就不去游泳。天氣涼快 , 所以小王沒去游泳。 (PQ)P)Q (2)如果天氣涼快 ,

2、小王就不去游泳。天氣不涼 快 , 所以小王去游泳了。 (PQ)P)Q 推理是否正確 ? 考察主析取范式 (PQ)P)Q = (PQ)P)Q =(PQ)PQ =(P Q) P Q =(P Q) P Q =(P Q) ( P (QQ) (Q (PP) =(P Q) ( P Q)( P Q) (Q P) = m0 m2 m3 m1 永真公式 推理是否正確 ? 考察主析取范式 (PQ) P) Q = (PQ) P) Q =(PQ)PQ =(P Q) P Q =(P Q) P Q =(P Q) (P(QQ) ( Q (PP) =(P Q) (PQ) ( Q P) = m0 m1 m2 非永真公式 推理是

3、否正確：真值表 P Q (PQ)P)Q (PQ)P)Q T T T T T F T T F T T F F F T T (PQ)P)Q為永真公式 而 (PQ)P)Q不是永真的。 三段 論 三段論 可用三段論表示 (PQ)P)Q 如下： P Q 大前提 P 小前提 Q 結(jié) 論 例 如果今天下雨，則運(yùn)動(dòng)會(huì)將推遲舉行； 今天下雨； 運(yùn)動(dòng)會(huì)將推遲舉行。 邏輯推理 由前提推出結(jié)論 （ 前提與結(jié)論都是命題，可真可假） 演繹推理 歸納推理 歸納推理 從真的前提出發(fā)，得到的結(jié)論只能夠要求它與 前提是 協(xié)調(diào)的 ，但不一定是真的。 它基于對(duì)特殊的代表的有限觀察， 或基于對(duì)反 復(fù)再現(xiàn)的現(xiàn)象的模式的有限觀察，用公式表

4、達(dá) 規(guī)律。 所有觀察到的烏鴉都是黑的。 所以所有烏鴉都是黑的。 演繹推理 可推導(dǎo)性 當(dāng)前提的真蘊(yùn)涵結(jié)論的真時(shí)，稱前提和 結(jié)論之間有可推導(dǎo)性關(guān)系，即前提和結(jié) 論之間的推理是正確的。 演繹推理 前提和結(jié)論之間有可推導(dǎo)性關(guān)系的這種 推理。 前提和結(jié)論間的形式關(guān)系 (而 不考慮內(nèi)容 ) 如果 1+1=3，則雪是黑的。 1+1=3。 雪是黑的。 該推理過程正確 , 但不意味著前提 與結(jié)論正確 第二章 命題演算的推理理論 2.1 命題演算的公理系統(tǒng) 2.1.1 公理系統(tǒng)的組成部分 2.1.2 公理系統(tǒng)的推理過程 2.2 命題演算的假設(shè)推理系統(tǒng) 2.3 命題演算的歸結(jié)推理法 2 1 命題演算的公理系統(tǒng) 給出

5、若干條永真公式 (稱為公理 )， 再給出若干條由永真公式推出永真公式 的推理規(guī)則， 由它們出發(fā)推出一切永真公式的系統(tǒng)。 了解公理系統(tǒng)的構(gòu)成規(guī)則和推理形式， 培養(yǎng)讀者構(gòu)造公理系統(tǒng)及利用該公理系統(tǒng)進(jìn) 行推理的能力。 2 1 1 公理系統(tǒng)的組成部分 一、語法部分 基本符號(hào) 公理系統(tǒng)所允許出現(xiàn)的全體符號(hào)的集合 公理 規(guī)則 二、語義部分 基本符號(hào) 命題變?cè)?P， Q， R， 等字母表示命題變?cè)?聯(lián)結(jié)詞 、 、 、 、 是聯(lián)結(jié)詞 括號(hào) (， )是括號(hào) 合式公式 (1) 任何命題變?cè)枪剑?(2) 如果 P為公式，則 P為公式； (3) 如果為 P， Q為公式，則 PQ， PQ， PQ， PQ為公式；

6、(4) 當(dāng)且僅當(dāng)經(jīng)過有限次使用 (1),(2),(3) 所組成的符號(hào)串才是公式。 推出符 表示其后的公式為永真公式 (教材中遺漏 ) 公理 公理 1 PP 公理 2 (P(QR)(Q(PR) 公理 3 (PQ)(QR)(PR) 公理 4 (P(PQ)(PQ) 公理 5 (PQ)(PQ) 公理 6 (PQ)(QP) 公理 7 (PQ)(QP)(PQ) 調(diào)頭 傳遞 凝縮 與 有關(guān) 公理 公理 8 (PQ)P 公理 9 (PQ)Q 公理 10 P(Q(PQ) 公理 11 P(PQ) 公理 12 Q(PQ) 公理 13 (PR)(QR)(PQ)R) 公理 14 (PQ)(QP) 公理 15 PP 與

7、有關(guān) 與 有關(guān) 與 有關(guān) 常用推理定律 (詳見耿素云 離散數(shù)學(xué) ) P(P Q) 附加 (P Q)P 化簡(jiǎn) (PQ) P)Q 假言推理 (PQ) Q)P 拒取式 (A B) A) B 析取三段論 (AB) (BC) (AC) 假言三段論 (AB) (BC) (AC) 等價(jià)三段論 (AB) (CD) (A C)(B D) 構(gòu)造性二難 常用推理定律 (詳見方世昌的 離散數(shù)學(xué) ) P(P Q) 加法式 (P Q)P 簡(jiǎn)化式 (PQ) P)Q 假言推理 (PQ) Q)P 拒取式 (A B) A) B 析取三段論 (AB) (BC) (AC) (假言 )前提三段論 (AB) (CD) (A C)(B D

8、) 構(gòu)造性二難 (AB) (CD) (B D)(A C) 破壞性二難 規(guī)則 (1)代入規(guī)則：將公式 中出現(xiàn)的某一符號(hào) B 每處均代以某一公式 C， 所到的公式 D 稱為 C 對(duì) 的 代入。 (2)分離規(guī)則：如果 AB且 A，則 B。 二、語義部分 (1) 公理是永真公式。 (2) 規(guī)則規(guī)定如何從永真公式推出永真公式。分離規(guī) 則指明，如果 AB永真且 A永真，則 B也為永真 公式。 (3) 代入規(guī)則指明如果 為永真公式，則某一個(gè)公式 正確代入公式 后所得的公式也為永真公式。 (4) 定理為永真公式，它們是從公理出發(fā)利用分離規(guī) 則和代入規(guī)則推出來的公式。 第二章 命題演算的推理理論 2.1 命題演

9、算的公理系統(tǒng) 2.1.1 公理系統(tǒng)的組成部分 2.1.2 公理系統(tǒng)的推理過程 2.2 命題演算的假設(shè)推理系統(tǒng) 2.3 命題演算的歸結(jié)推理法 定理 1(p18) PP 證明： (1) (PQ)(QP) 公理 14 (2) (PP)(PP) P用 P， Q用 P代入 (3) PP 公理 1 (4) PP P用 P代入 (5) PP (2)(4)分離 P=P 例 (P P) P 證明： (1) (PR) (QR) (P Q) R) 公理 13 (2) (PP) (PP) (P P) P) (1)式中 Q用 P、 R用 P代入 (3) PP 公理 1 (4) (PP) (P P) P) (2)(3)分

10、離 (5) (P P) P (3)(4)分離 例 P(PP) 證明 (1) (PR) (QR) (P Q) R) 公理 13 (2) (PP) (PP) (P P) P) (1)式中 Q用 P、 R用 P代入 (3) P P 公理 1 (4) (PP) (P P) P) (2)(3)分離 (5) (P P) P (3)(4)分離 (6) P(P Q) 公理 11 (7) P(P P) (6)式中 Q用 P代入 (8) (PQ)(QP)(PQ) 公理 7 (9) (P(P P)(P P)P)(P(P P) (8)式中 Q用 P P代入 (10) (P P)P)(P(P P) (7)(9)分離 (

11、11) P(P P) (5)(10)分離 定理 2(p18) (PQ)(RP)(RQ) 分析：由傳遞公理 3知道 (RP)(PQ)(RQ) 與要求證的公式的聯(lián)系是兩個(gè)前件次序換 一換，就可以用調(diào)頭公理 2： (P(QR)(Q(PR) 加頭公式 定理 2(p18) (PQ)(RP)(RQ) 證明： (1) (PQ)(QR)(PR) 公理 3 (2) (RP)(PQ)(RQ) P用 R， Q用 P， R用 Q代入 (3) (P(QR)(Q(PR) 公理 2 (4) (RP)(PQ)(RQ) (PQ)(RP)(RQ) P用 RP， Q用 PQ， R用 RQ代入 (5) (PQ)(RP)(RQ) (4

12、)(2)分離 定理 3 (p18,拒取式 ) (PQ)(QP) 分析：由公理 14， (PQ)(QP)， 可以得到 (PQ)(QP) 下面就是要建立 (PQ)與 (PQ)之間的聯(lián)系。 如果 (PQ) (PQ)， 則由傳遞性知道結(jié)論成立。 下面先證明 (PQ) (PQ)。 證明：先證 (PQ) (PQ) (1)PP 定理 1 (2)QQ P用 Q代入 (3)(PQ)(QP) 公理 14 (4)(PQ)(QP) Q用 Q代入 (5)(PQ)(RP)(RQ) 加頭 定理 2 (6)(QQ)(PQ)(PQ) (5)式中 P用 Q代入， Q用 Q代入， R用 P代入 (7)(PQ)(PQ) (6)(2)

13、分離 定理 3 (p18,拒取式 ) (PQ)(QP) 證明： (1)PP 定理 1 (2)QQ P用 Q代入 (3)(PQ)(QP) 公理 14 (4)(PQ)(QP) Q用 Q代入 (5)(PQ)(RP)(RQ) 定理 2 (6)(QQ)(PQ)(PQ) (5)式中 P用 Q代入， Q用 Q代入， R用 P代入 (7)(PQ)(PQ) (6)(2)分離 (8)(PQ)(QR)(PR) 公理 3 (9)(PQ)(PQ) (PQ)(QP)(PQ)(QP) (8)式中 P用 PQ， Q用 PQ， R用 QP代入 (10)(PQ)(QP)(PQ)(QP) (9)(7)分離 (11)(PQ)(QP)

14、 (10)(4)分離 例 （同定理 3） 已知公理 A: PP B: (PQ) (QP) C: (PQ) (RP) (RQ) D: (PQ) (QR) (PR) 要證 (PQ) (QP)為本系統(tǒng)中的定理。 公理推理證明定理的方法 對(duì)于簡(jiǎn)單題，可以把待證明的公式變成永 真蘊(yùn)涵式的后件，再證明前件永真。 引理 P(PQ)Q) 證明： (1) (P(QR)(Q(PR) 公理 2 (2) (PQ)(PQ) (P(PQ)Q) Q用 P代入 ， R用 Q代入 ， P用 P Q代入 (3) PP 公理 1 (4) (PQ)(PQ) 代入 (5) P(PQ)Q) 分離 (2)(4) 例 1(p18) 已知引理

15、，試證明 (PP) P (1) P(PQ)Q) 定理 (2) P(PP)P) Q用 P代入 (3) (PQ)(QP) 公理 14 (4) (PP)P)(P(PP) P用 PP代入， Q用 P代入 (5) (PQ)(RP)(RQ) 定理 2 (6) (PP)P)(P(PP) (P(PP)P)(P(P(PP) P用 (PP)P， Q用 P(PP)， R用 P代入 (7) (P(PP)P)(P(P(PP) (6)(4)分離 (8) P(P(PP) (7)(2)分離 (9) (P(PQ)(PQ) 公理 4 (10) (P(P(PP)(P(PP) Q用 (PP)代入 (11) (P(PP) (10)(8

16、)分離 (12) (P(PP)(PP) P) (3)式中 Q用 PP代入 (13) (PP) P (12)(11)分離 例 2(p19) 已知公理： A P(Q P) B (P(Q R)(PQ)(PR) C (P(QR)(Q(PR) D P(PQ) E (PQ)(QP) 及分離規(guī)則和代入規(guī)則 證明公式 (RR)(PP)為定理。 PP？ 例 2的分析 先要證明 PP 如果用公理 A： P（ QP），得到 P（ PP）， 難以繼續(xù)。 證明 : 先證 PP (1) P(Q P) 公理 A (2) (P(Q R)(PQ)(PR) 公理 B (3) (P(Q P)(PQ)(PP) R用 P代入 (2)

17、(4) (PQ)(PP) (3)(1)分離 (5) (P(Q P)(PP) Q用 Q P代入 (4) (6) PP (5)(1)分離 例 2的證明 (p19) (1) P(Q P) 公理 A (2) (P(Q R)(PQ)(PR) 公理 B (3) (P(Q P)(PQ)(PP) R用 P代入 (2) (4) (PQ)(PP) (3)(1)分離 (5) (P(Q P)(PP) Q用 Q P代入 (4) (6) PP (5)(1)分離 (7) P(PQ) 公理 D (8) (PP)(PP )(RR) P用 PP， Q用 RR代入 (7) (9) (PP )(RR) (8)(6)分離 (10) (

18、PQ)(QP) 公理 E (11) (PP )(RR)(RR)(PP ) P用 PP， Q用 RR代入 (10) (12) (RR)(PP ) (11)(9)分離 已知公理 A: (pq) (qp) (pq) B: pp q C: pp D: (pr) (qr) (p q) r) E: p qp 證明定理 : p(p p) 同 前 例 ! 例 3 (1) pp q 公理 B (2) pp p 代入 (3) (pr) (qr) (p q) r) 公理 D (4) (pp) (pp) (p p) p) 代入 (5) p p 公理 C (6) (pp) (p p) p) (4)(5)分離 (7) (

19、p p) p (5)(6)分離 證明：先證 (p p) p (1) pp q 公理 B (2) pp p 代入 (3) (pr) (qr) (p q) r) 公理 D (4) (pp) (pp) (p p) p) 代入 (5) p p 公理 C (6) (pp) (p p) p) (4)(5)分離 (7) (p p) p (5)(6)分離 (8) (pq) (qp) (pq) 公理 A (9) (p(p p) (p p)p) (p(p p) 代入 (10) (p p)p) (p(p p) (2)(9)分離 (11) (p(p p) (7)(10)分離 例 3的證明 例 4 已知公理 A： (Q

20、R)(PQ)(PR) B： (P(QR)(Q(PR) C： (PQ)(QR) (PR) D： PP 及分離規(guī)則和代入規(guī)則 ,試證明下式為定理 (PQ)R)(PQ)R) 例 4的證明 (1) PP 公理 4 (2) QQ P用 Q代入 (3) (QR)(PQ)(PR) 公理 1 (4) (QQ)(PQ)(PQ) Q用 Q代入 , R用 Q代入 (5) (PQ)(PQ) (4)、 (2)分離 (6) (PQ)(QR)(PR) 公理 3 (7) (PQ)(PQ) (PQ)R)(PQ)R) P用 PQ代入， Q用 PQ代入， R用 R代入 (8) (PQ)R)(PQ)R) (7)、 (5)分離 例 5

21、 已知公理： A: P(Q P) B: (Q R)(PQ)(PR) C: (PP)P D: Q(PQ) E: (PQ)(QP) 及分離規(guī)則和代入規(guī)則 試證明 PP 為定理 例 5的證明 (1) P(Q P) 公理 A (2) (Q R)(PQ)(PR) 公理 B (3) (P P)P 公理 C (4) Q(PQ) 公理 D (5) (P Q)(Q P) 公理 E (6) (P P) P) (P(P P) (PP) (2)式中 Q用 P P、 R用 P代入 (7) (P(P P) (PP) (3)(6)分離 (8) P(P P) (4)式中 Q用 P代入 (9) PP (7)(8)分離 第二章 命題演算的推理理論 2.1 命題演算的公理系統(tǒng) 2.1.1 公理系統(tǒng)的組成部分 2.1.2 公理系統(tǒng)的推理過程 2.2 命題演算的假設(shè)推理系統(tǒng) 2.3 命題演算的歸結(jié)推理法