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

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

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

3、是明天是5號號. 解解 設(shè)設(shè) p: 今天是今天是1號號, q: 明天是明天是5號號 推理的方式構(gòu)造為推理的方式構(gòu)造為 (pq)pq證明證明 用等值演算法用等值演算法 (pq)pq (pq)p)q (pq)p)q pqq 1得證推理正確得證推理正確實例實例(續(xù)續(xù))(2) 假設(shè)今天天冷，小王就穿羽絨服。小王就穿羽絨服。假設(shè)今天天冷，小王就穿羽絨服。小王就穿羽絨服。 所所以以,今天天冷。今天天冷。 解解 設(shè)設(shè)p:今天天冷今天天冷, q:小王穿羽絨服小王穿羽絨服. 推理的方式構(gòu)造為推理的方式構(gòu)造為 (pq)qp證明證明 用主析取范式法用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (

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

5、理系統(tǒng)自然推理系統(tǒng)P由下述由下述3部分組成部分組成:1. 字母表字母表(1) 命題變項符號命題變項符號: p,q,r, pi,qi,ri,(2) 結(jié)合詞結(jié)合詞: , , , , (3) 括號與逗號括號與逗號: ( ), ,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、6) 化簡規(guī)那么化簡規(guī)那么 AB A 自然推理系統(tǒng)自然推理系統(tǒng)P(續(xù)續(xù))(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 析取三段論析

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

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

9、r, rs結(jié)論結(jié)論: ps證明證明 p 附加前提引入附加前提引入 pq 前提引入前提引入 q 析取三段論析取三段論 qr 前提引入前提引入 r 析取三段論析取三段論 rs 前提引入前提引入 s 假言推理假言推理推理正確推理正確, ps是有效結(jié)論是有效結(jié)論歸謬法歸謬法(反證法反證法)欲證明欲證明前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B將將B參與前提參與前提, 假設(shè)推出矛盾假設(shè)推出矛盾, 那么得證推理正確那么得證推理正確. 理由理由: A1A2AkB (A1A2Ak)B (A1A2AkB)括號內(nèi)部為矛盾式當(dāng)且僅當(dāng)括號內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1A2AkB)為重言式為重言式實例實例例例5

10、 構(gòu)造下面推理的證明構(gòu)造下面推理的證明前提前提: (pq)r, rs, s, p結(jié)論結(jié)論: q證明證明 用歸繆法用歸繆法 q 結(jié)論否認(rèn)引入結(jié)論否認(rèn)引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式實例實例(續(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

11、 B C歸結(jié)證明法歸結(jié)證明法(續(xù)續(xù))在自然推理系統(tǒng)在自然推理系統(tǒng)P中只需下述推理規(guī)那么中只需下述推理規(guī)那么:(1) 前提引入規(guī)那么前提引入規(guī)那么(2) 結(jié)論引入規(guī)那么結(jié)論引入規(guī)那么(3) 置換規(guī)那么置換規(guī)那么(4) 化簡規(guī)那么化簡規(guī)那么(5) 合取引入規(guī)那么合取引入規(guī)那么(6) 歸結(jié)規(guī)那么歸結(jié)規(guī)那么歸結(jié)證明法的根本步驟歸結(jié)證明法的根本步驟1. 將每一個前提化成等值的合取范式將每一個前提化成等值的合取范式, 設(shè)一切合取范式的設(shè)一切合取范式的全部簡單析取式為全部簡單析取式為A1, A2, At2. 將結(jié)論化成等值的合取范式將結(jié)論化成等值的合取范式B1B2Bs, 其中每個其中每個Bj是簡單析取式是簡單析取式3. 以以A1,A2,At為前提為前提, 運用歸結(jié)規(guī)那么推出每一個運用歸結(jié)規(guī)那么推出每一個Bj, 1js4. 由合取引入規(guī)那么得到結(jié)論由合取引入規(guī)那么得到結(jié)論B1B2Bs實例實例例例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)實例實例(續(xù)續(xù))