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

1、目錄（ 數理邏輯） 第一章 命題演算基礎 （ 6學時） 第二章 命題演算的推理理論（ 4學時 ） 第三章 謂詞演算基礎（ 5學時） 第四章 謂詞演算的推理理論（ 5學時） 第五章 遞歸函數論（ 4學時） 第二章 命題演算的推理理論 例 判斷下面各推理是否正確 : (1) 如果天氣涼快 ,小王就不去游泳。 天氣涼快 , 所以小王沒去游泳。 (2) 如果天氣涼快 ,小王就不去游泳。 天氣不涼快 , 所以小王去游泳了。 推理是否正確： 形式化 引入符號： 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 結 論 例 如果今天下雨，則運動會將推遲舉行； 今天下雨； 運動會將推遲舉行。 邏輯推理 由前提推出結論 （ 前提與結論都是命題，可真可假） 演繹推理 歸納推理 歸納推理 從真的前提出發(fā)，得到的結論只能夠要求它與 前提是 協調的 ，但不一定是真的。 它基于對特殊的代表的有限觀察， 或基于對反 復再現的現象的模式的有限觀察，用公式表

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

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

6、(4) 當且僅當經過有限次使用 (1),(2),(3) 所組成的符號串才是公式。 推出符 表示其后的公式為永真公式 (教材中遺漏 ) 公理 公理 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) 調頭 傳遞 凝縮 與 有關 公理 公理 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、有關 與 有關 與 有關 常用推理定律 (詳見耿素云 離散數學 ) P(P Q) 附加 (P Q)P 化簡 (PQ) P)Q 假言推理 (PQ) Q)P 拒取式 (A B) A) B 析取三段論 (AB) (BC) (AC) 假言三段論 (AB) (BC) (AC) 等價三段論 (AB) (CD) (A C)(B D) 構造性二難 常用推理定律 (詳見方世昌的 離散數學 ) P(P Q) 加法式 (P Q)P 簡化式 (PQ) P)Q 假言推理 (PQ) Q)P 拒取式 (A B) A) B 析取三段論 (AB) (BC) (AC) (假言 )前提三段論 (AB) (CD) (A C)(B D

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

9、算的公理系統(tǒng) 2.1.1 公理系統(tǒng)的組成部分 2.1.2 公理系統(tǒng)的推理過程 2.2 命題演算的假設推理系統(tǒng) 2.3 命題演算的歸結推理法 定理 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) 與要求證的公式的聯系是兩個前件次序換 一換，就可以用調頭公理 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)之間的聯系。 如果 (PQ) (PQ)， 則由傳遞性知道結論成立。 下面先證明 (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)中的定理。 公理推理證明定理的方法 對于簡單題，可以把待證明的公式變成永 真蘊涵式的后件，再證明前件永真。 引理 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 命題演算的假設推理系統(tǒng) 2.3 命題演算的歸結推理法