離散數(shù)學24命題邏輯推理理論課件

1、1有效推理有效推理定義定義2.20 若對于每組賦值若對于每組賦值, A1 A2 Ak 為假為假, 或者或者當當A1 A2 Ak為真時為真時, B也為真也為真, 則稱由前提則稱由前提A1,A2, Ak推推B的的推理有效推理有效或或推理正確推理正確, 并稱并稱B是是有效的結論有效的結論定理定理2.8 由前提由前提A1, A2, , Ak 推出推出B 的推理正確當且僅當?shù)耐评碚_當且僅當 A1 A2 AkB為重言式為重言式.2推理的形式結構推理的形式結構形式形式(1) A1 A2 AkB形式形式(2) 前提前提: A1, A2, , Ak 結論結論: B 推理正確記作推理正確記作 A1 A2 AkB

2、判斷推理是否正確的方法判斷推理是否正確的方法:真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法構造證明法構造證明法3實例實例例例1 判斷下面推理是否正確判斷下面推理是否正確:(1) 若今天是若今天是1號號, 則明天是則明天是5號號. 今天是今天是1號號. 所以所以, 明天是明天是5號號. 解解 設設 p: 今天是今天是1號號, q: 明天是明天是5號號 推理的形式結構為推理的形式結構為 (pq) pq證明證明 用等值演算法用等值演算法 (pq) pq ( p q) p) q (pq)p) q pq q 1得證推理正確得證推理正確4實例實例(續(xù)續(xù))(2) 若今天是若今天是1號號, 則

3、明天是則明天是5號號. 明天是明天是5號號. 所以所以, 今天是今天是1號號. 解解 設設p: 今天是今天是1號號, q: 明天是明天是5號號. 推理的形式結構為推理的形式結構為 (pq) qp證明證明 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 01是成假賦值是成假賦值, 所以推理不正確所以推理不正確.5推理定律推理定律重言蘊涵式重言蘊涵式 A (A B) 附加律附加律 (A B) A 化簡律化簡律(AB) A B 假言推理假言推理(AB)B A 拒取式拒取式(A B)B A

4、析取三段論析取三段論(AB) (BC) (AC) 假言三段論假言三段論(AB) (BC) (AC) 等價三段論等價三段論(AB) (CD) (A C) (B D) 構造性二難構造性二難 (AB) ( AB) B 構造性二難構造性二難(特殊形式特殊形式)(AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難6自然推理系統(tǒng)自然推理系統(tǒng)P自然推理系統(tǒng)自然推理系統(tǒng)P由下述由下述3部分組成部分組成:1. 字母表字母表(1) 命題變項符號命題變項符號: p,q,r, pi,qi,ri,(2) 聯(lián)結詞聯(lián)結詞: , , , , (3) 括號與逗號括號與逗號: ( ), ,2. 合式公式合式公式3.

5、推理規(guī)則推理規(guī)則(1) 前提引入規(guī)則前提引入規(guī)則(2) 結論引入規(guī)則結論引入規(guī)則(3) 置換規(guī)則置換規(guī)則7自然推理系統(tǒng)自然推理系統(tǒng)P(續(xù)續(xù))(7) 拒取式規(guī)則拒取式規(guī)則 AB B A(8) 假言三段論規(guī)則假言三段論規(guī)則 AB BC AC (4) 假言推理規(guī)則假言推理規(guī)則 AB A B(5) 附加規(guī)則附加規(guī)則 A A B(6) 化簡規(guī)則化簡規(guī)則 A B A 8自然推理系統(tǒng)自然推理系統(tǒng)P(續(xù)續(xù))(11) 破壞性二難推理規(guī)則破壞性二難推理規(guī)則 AB CD BD AC(12) 合取引入規(guī)則合取引入規(guī)則 A B A B (9) 析取三段論規(guī)則析取三段論規(guī)則 A B B A(10)構造性二難推理規(guī)則構造性

6、二難推理規(guī)則 AB CD A C B D9直接證明法直接證明法例例2 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構造下面推理的證明中構造下面推理的證明:前提前提: p q, qr, ps, s結論結論: r(p q) )證明證明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論 qr 前提引入前提引入 r 假言推理假言推理 r(p q) ) 合取合取推理正確推理正確, , r(p q) )是有效結論是有效結論10實例實例例例3 構造推理的證明構造推理的證明: 若明天是星期一或星期三若明天是星期一或星期三, 我就有我就有課課. 若有課若有課

7、, 今天必需備課今天必需備課. 我今天下午沒備課我今天下午沒備課. 所以所以, 明天明天不是星期一和星期三不是星期一和星期三. 解解 設設 p:明天是星期一明天是星期一, q:明天是星期三，明天是星期三， r:我有課，我有課， s:我備課我備課前提前提: (p q)r, rs, s結論結論: pq 11實例實例(續(xù)續(xù))前提前提: (p q)r, rs, s結論結論: pq 證明證明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換結論有效結論有效, 即明天不是星期一和星期三即明天不是星期一和星期三12附加前

8、提證明法附加前提證明法欲證明欲證明 等價地證明等價地證明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C結論結論: CB 結論結論: B理由理由: (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B13實例實例例例4 構造下面推理的證明構造下面推理的證明:前提前提: p q, q r, rs結論結論: ps證明證明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段論析取三段論 q r 前提引入前提引入 r 析取三段論析取三段論 rs 前提引入前提引入 s 假言推理假言

9、推理推理正確推理正確, , ps是有效結論是有效結論14歸謬法歸謬法(反證法反證法)欲證明欲證明前提：前提：A1, A2, , Ak 結論：結論：B將將 B加入前提加入前提, 若推出矛盾若推出矛盾, 則得證推理正確則得證推理正確. 理由理由: A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB)括號內(nèi)部為矛盾式當且僅當括號內(nèi)部為矛盾式當且僅當 (A1 A2 AkB)為重言式為重言式15實例實例例例5 構造下面推理的證明構造下面推理的證明前提前提: (p q) r, rs, s, p結論結論: q證明證明 用歸繆法用歸繆法 q 結論否定引入結論否定引入 rs 前提引入前提引入 s

10、 前提引入前提引入 r 拒取式拒取式16實例實例(續(xù)續(xù)) (p q) r 前提引入前提引入 (p q) 析取三段論析取三段論 pq 置換置換 p 析取三段論析取三段論 p 前提引入前提引入 p p 合取合取推理正確推理正確, , q是有效結論是有效結論17歸結證明法歸結證明法理由理由 (p q)(p r)(q r) ( (p q)(p r) (q r) ( pq)(pr) q r ( ( pq) q)(pr) r) ( p q)(p r) 1 1歸結規(guī)則歸結規(guī)則 A B A C B C18歸結證明法歸結證明法(續(xù)續(xù))在自然推理系統(tǒng)在自然推理系統(tǒng)P中只需下述推理規(guī)則中只需下述推理規(guī)則:(1) 前

11、提引入規(guī)則前提引入規(guī)則(2) 結論引入規(guī)則結論引入規(guī)則(3) 置換規(guī)則置換規(guī)則(4) 化簡規(guī)則化簡規(guī)則(5) 合取引入規(guī)則合取引入規(guī)則(6) 歸結規(guī)則歸結規(guī)則19歸結證明法的基本步驟歸結證明法的基本步驟1. 將每一個前提化成等值的合取范式將每一個前提化成等值的合取范式, 設所有合取范式的設所有合取范式的全部簡單析取式為全部簡單析取式為A1, A2, At2. 將結論化成等值的合取范式將結論化成等值的合取范式B1 B2 Bs, 其中每個其中每個Bj是簡單析取式是簡單析取式3. 以以A1,A2,At為前提為前提, 使用歸結規(guī)則推出每一個使用歸結規(guī)則推出每一個Bj, 1 j s4. 由合取引入規(guī)則得

12、到結論由合取引入規(guī)則得到結論B1 B2 Bs20實例實例例例6 用歸結證明法構造下面推理的證明用歸結證明法構造下面推理的證明:前提前提: ( (pq)r, rs, s結論結論: ( (pq)()(p s) )解解 ( (pq)r ( (p q)r ( (pq)r ( (p r)(q r) ) rs r s ( (pq)()(p s) () (p q)()(p s) () (pq)(p s) ) p(q s)推理可表成推理可表成前提前提: : p r, , q r, , r s, , s結論結論: p(q s)21實例實例(續(xù)續(xù))前提前提: : p r, , q r, , r s, , s結論結論: p(q s)證明證明 q r 前提引入前提引入 r s 前提引入前提引入 q s 歸結歸結 s 前提引入前提引