離散數(shù)學(xué)第二章-命題演算的推理理論-命題演算的公理系統(tǒng).ppt

目錄（數(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)如果天氣涼快,小王就不去游泳。天氣不涼快, 所以小王去游泳了。 (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) = m0m2m3m1 永真公式,推理是否正確? 考察主析取范式,(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) = m0m1m2 非永真公式,推理是否正確：真值表,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)象的模式的有限觀察，用公式表達(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é)推理法,21 命題演算的公理系統(tǒng),給出若干條永真公式(稱為公理)， 再給出若干條由永真公式推出永真公式的推理規(guī)則， 由它們出發(fā)推出一切永真公式的系統(tǒng)。,了解公理系統(tǒng)的構(gòu)成規(guī)則和推理形式， 培養(yǎng)讀者構(gòu)造公理系統(tǒng)及利用該公理系統(tǒng)進(jìn)行推理的能力。,211 公理系統(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為公式； (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)頭,傳遞,凝縮, 公理,公理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,常用推理定律(詳見耿素云離散數(shù)學(xué)),P(PQ) 附加 (PQ)P 化簡(jiǎn) (PQ)P)Q 假言推理 (PQ)Q)P 拒取式 (AB)A) B 析取三段論 (AB)(BC) (AC) 假言三段論 (AB)(BC) (AC) 等價(jià)三段論 (AB)(CD)(AC)(BD) 構(gòu)造性二難,P(PQ) 加法式 (PQ)P 簡(jiǎn)化式 (PQ)P)Q 假言推理 (PQ)Q)P 拒取式 (AB)A) B 析取三段論 (AB)(BC) (AC) (假言)前提三段論 (AB)(CD)(AC)(BD) 構(gòu)造性二難 (AB)(CD)(BD)(AC) 破壞性二難, 規(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 命題演算的公理系統(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,例 (PP) P,證明： (1) (PR) (QR) (PQ) R) 公理13 (2) (PP) (PP) (PP) P) (1)式中Q用P、R用P代入 PP 公理1 (PP) (PP) P) (2)(3)分離 (PP) P (3)(4)分離,例 P(PP),證明 (1) (PR) (QR) (PQ) R) 公理13 (2) (PP) (PP) (PP) P) (1)式中Q用P、R用P代入 (3) PP 公理1 (4) (PP) (PP) P) (2)(3)分離 (5) (PP) P (3)(4)分離 (6) P(PQ) 公理11 (7) P(PP) (6)式中Q用P代入 (8) (PQ)(QP)(PQ) 公理7 (9) (P(PP)(PP)P)(P(PP) (8)式中Q用PP代入 (10) (PP)P)(P(PP) (7)(9)分離 (11) P(PP) (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)(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)分離,定理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) (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) 已知引理，試證明(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)分離 (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,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)分離,例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) (PQ)(QP) 公理E (11) (PP )(RR)(RR)(PP ) P用PP，Q用RR代入(10) (12) (RR)(PP ) (11)(9)分離,已知公理 A: (pq) (qp) (pq) B: ppq C: pp D: (pr) (qr) (pq) r) E: pqp 證明定理: p(pp),同前例 !,例3,(1) ppq 公理B (2) ppp 代入 (3) (pr) (qr) (pq) r) 公理D (4) (pp) (pp) (pp) p) 代入 (5) p p 公理C (6) (pp) (pp) p) (4)(5)分離 (7) (pp) p (5)(6)分離,證明：先證 (pp) p,(1) ppq 公理B (2) ppp 代入 (3) (pr) (qr) (pq) r) 公理D (4) (pp) (pp) (pp) p) 代入 (5) p p 公理C (6) (pp) (pp) p) (4)(5)分離 (7) (pp) p (5)(6)分離 (8) (pq) (qp) (pq) 公理A (9) (p(pp) (pp)p) (p(pp) 代入 (10) (pp)p) (p(pp) (2)(9)分離 (11) (p(pp) (7)(10)分離,例3的證明,例4,已知公理 A： (QR)(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,已知公理： A: P(Q P) B: (Q R)(PQ)(PR) C: (PP)P D: Q(PQ) E: (PQ)(QP) 及分離規(guī)則