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

1、2.4 命題邏輯推理理論命題邏輯推理理論 2.4.1 推理的形式結構推理的形式結構 推理的前提與結論推理的前提與結論,正確推理正確推理 推理定律推理定律 2.4.2 自然推理系統(tǒng)自然推理系統(tǒng)P 推理規(guī)則推理規(guī)則 直接證明法直接證明法, 附加前提證明法附加前提證明法, 歸謬法歸謬法(反證法反證法), 歸結證明法歸結證明法有效推理有效推理定義定義2.20 若對于每組賦值若對于每組賦值, A1A2 Ak 為假為假, 或者或者當當A1A2Ak為真時為真時, B也為真也為真, 則稱由前提則稱由前提A1,A2, Ak推推B的推理有效或推理正確的推理有效或推理正確, 并稱并稱B是有效的結論是有效的結論定理定

2、理2.8 由前提由前提A1, A2, , Ak 推出推出B 的推理正確當且僅當?shù)耐评碚_當且僅當 A1A2AkB為重言式為重言式.推理的形式結構推理的形式結構形式形式(1) A1A2AkB形式形式(2) 前提前提: A1, A2, , Ak 結論結論: B 推理正確記作推理正確記作 A1A2AkB判斷推理是否正確的方法判斷推理是否正確的方法:真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法構造證明法構造證明法實例實例例例1 判斷下面推理是否正確判斷下面推理是否正確:(1) 若今天是若今天是1號號, 則明天是則明天是5號號. 今天是今天是1號號. 所以所以, 明天是明天是5號號. 解

3、解 設設 p: 今天是今天是1號號, q: 明天是明天是5號號 推理的形式結構為推理的形式結構為 (pq)pq證明證明 用等值演算法用等值演算法 (pq)pq (pq)p)q (pq)p)q pqq 1得證推理正確得證推理正確實例實例(續(xù)續(xù))(2) 若今天是若今天是1號號, 則明天是則明天是5號號. 明天是明天是5號號. 所以所以, 今天是今天是1號號. 解解 設設p: 今天是今天是1號號, q: 明天是明天是5號號. 推理的形式結構為推理的形式結構為 (pq)qp證明證明 用主析取范式法用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0

4、m2m3 01是成假賦值是成假賦值, 所以推理不正確所以推理不正確.推理定律推理定律重言蘊涵式重言蘊涵式 A (AB) 附加律附加律 (AB) A 化簡律化簡律(AB)A B 假言推理假言推理(AB)B A 拒取式拒取式(AB)B A 析取三段論析取三段論(AB)(BC) (AC) 假言三段論假言三段論(AB)(BC) (AC) 等價三段論等價三段論(AB)(CD)(AC) (BD) 構造性二難構造性二難 (AB)(AB) B 構造性二難構造性二難(特殊形式特殊形式)(AB)(CD)( BD) (AC) 破壞性二難破壞性二難自然推理系統(tǒng)自然推理系統(tǒng)P自然推理系統(tǒng)自然推理系統(tǒng)P由下述由下述3部分

5、組成部分組成:1. 字母表字母表(1) 命題變項符號命題變項符號: p,q,r, pi,qi,ri,(2) 聯(lián)結詞聯(lián)結詞: , , , , (3) 括號與逗號括號與逗號: ( ), ,2. 合式公式合式公式3. 推理規(guī)則推理規(guī)則(1) 前提引入規(guī)則前提引入規(guī)則(2) 結論引入規(guī)則結論引入規(guī)則(3) 置換規(guī)則置換規(guī)則自然推理系統(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 AB(6) 化簡規(guī)則化簡規(guī)則 AB A 自然推理系統(tǒng)自然推理系統(tǒng)P(續(xù)續(xù))(

6、11) 破壞性二難推理規(guī)則破壞性二難推理規(guī)則 AB CD BD AC(12) 合取引入規(guī)則合取引入規(guī)則 A B AB (9) 析取三段論規(guī)則析取三段論規(guī)則 AB B A(10)構造性二難推理規(guī)則構造性二難推理規(guī)則 AB CD AC BD直接證明法直接證明法例例2 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構造下面推理的證明中構造下面推理的證明:前提前提: pq, qr, ps, s結論結論: r(pq)證明證明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 pq 前提引入前提引入 q 析取三段論析取三段論 qr 前提引入前提引入 r 假言推理假言推理 r(pq) 合取合取推理正確推理正

7、確, r(pq)是有效結論是有效結論實例實例例例3 構造推理的證明構造推理的證明: 若明天是星期一或星期三若明天是星期一或星期三, 我就有我就有課課. 若有課若有課, 今天必需備課今天必需備課. 我今天下午沒備課我今天下午沒備課. 所以所以, 明天明天不是星期一和星期三不是星期一和星期三. 解解 設設 p:明天是星期一明天是星期一, q:明天是星期三，明天是星期三， r:我有課，我有課， s:我備課我備課前提前提: (pq)r, rs, s結論結論: pq 實例實例(續(xù)續(xù))前提前提: (pq)r, rs, s結論結論: pq 證明證明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒

8、取式 (pq)r 前提引入前提引入 (pq) 拒取式拒取式 pq 置換置換結論有效結論有效, 即明天不是星期一和星期三即明天不是星期一和星期三附加前提證明法附加前提證明法欲證明欲證明 等價地證明等價地證明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C結論結論: CB 結論結論: B理由理由: (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B實例實例例例4 構造下面推理的證明構造下面推理的證明:前提前提: pq, qr, rs結論結論: ps證明證明 p 附加前提引入附加前提引入 pq 前提引入前提引入 q 析取

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

10、歸繆法用歸繆法 q 結論否定引入結論否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式實例實例(續(xù)續(xù)) (pq)r 前提引入前提引入 (pq) 析取三段論析取三段論 pq 置換置換 p 析取三段論析取三段論 p 前提引入前提引入 pp 合取合取推理正確推理正確, q是有效結論是有效結論歸結證明法歸結證明法理由理由 (pq)(pr)(qr) (pq)(pr)(qr) (pq)(pr)qr (pq)q)(pr)r) (pq)(pr) 1歸結規(guī)則歸結規(guī)則 A B A C B C歸結證明法歸結證明法(續(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ī)則歸結證明法的基本步驟歸結證明法的基本步驟1. 將每一個前提化成等值的合取范式將每一個前提化成等值的合取范式, 設所有合取范式的設所有合取范式的全部簡單析取式為全部簡單析取式為A1, A2, At2. 將結論化成等值的合取范式將結論化成等值的合取范式B1B2Bs, 其中每個其中每個Bj是簡單析取式是簡單析取式3. 以以A1,A2,At為前提為前提, 使用歸結規(guī)則推出每一個使用歸結規(guī)則推出每一個Bj, 1js4. 由合取引入規(guī)則得到結論由

12、合取引入規(guī)則得到結論B1B2Bs實例實例例例6 用歸結證明法構造下面推理的證明用歸結證明法構造下面推理的證明:前提前提: (pq)r, rs, s結論結論: (pq)(ps)解解 (pq)r (pq)r (pq)r (pr)(qr) rs rs (pq)(ps) (pq)(ps) (pq)(ps) p(qs)推理可表成推理可表成前提前提: pr, qr, rs, s結論結論: p(qs)實例實例(續(xù)續(xù))前提前提: pr, qr, rs, s: pr, qr, rs, s結論結論: p(qs): p(qs)證明證明 qr qr 前提引入前提引入 rs rs 前提引入前提引入 qs qs 歸結歸結 s s 前提引入前提引入 s0 s0 置換置換 r