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

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

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

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

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

5、組成部分組成:1. 字母表字母表(1) 命題變項(xiàng)符號(hào)命題變項(xiàng)符號(hào): p,q,r, pi,qi,ri,(2) 聯(lián)結(jié)詞聯(lián)結(jié)詞: , , , , (3) 括號(hào)與逗號(hào)括號(hào)與逗號(hào): ( ), ,2. 合式公式合式公式3. 推理規(guī)則推理規(guī)則(1) 前提引入規(guī)則前提引入規(guī)則(2) 結(jié)論引入規(guī)則結(jié)論引入規(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) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(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)構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則 AB CD AC BD直接證明法直接證明法例例2 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明:前提前提: pq, qr, ps, s結(jié)論結(jié)論: r(pq)證明證明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 pq 前提引入前提引入 q 析取三段論析取三段論 qr 前提引入前提引入 r 假言推理假言推理 r(pq) 合取合取推理正確推理正

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

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

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

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

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

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