離散數(shù)學(xué)：1-6 推理理論

1、11.6 命題邏輯的推理理論命題邏輯的推理理論 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)判斷推理是否正確的方法判斷推理是否正確的方法推理定律與推理規(guī)則推理定律與推理規(guī)則構(gòu)造證明法構(gòu)造證明法 2推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)問(wèn)題的引入問(wèn)題的引入 推理舉例推理舉例: (1) 正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界正項(xiàng)級(jí)數(shù)收斂當(dāng)且僅當(dāng)部分和有上界. (2) 若若A C B D，則，則A B且且C D.推理推理: 從前提出發(fā)推出結(jié)論的思維過(guò)程從前提出發(fā)推出結(jié)論的思維過(guò)程上面上面(1)是正確的推理，而是正確的推理，而(2)是錯(cuò)誤的推理是錯(cuò)誤的推理. 證明證明: 描述推理正確的過(guò)程描述推理正確的過(guò)程. 3推理的形式結(jié)構(gòu)推理的

2、形式結(jié)構(gòu) 定義定義 若對(duì)于每組賦值，或者若對(duì)于每組賦值，或者A1 A2 Ak 均為假，均為假，或者當(dāng)或者當(dāng)A1 A2 Ak為真時(shí)為真時(shí), B也為真也為真, 則稱由則稱由A1,A2, , Ak推推B的的推理正確推理正確, 否則否則推理不正確（錯(cuò)誤）推理不正確（錯(cuò)誤）.“A1, A2, , Ak 推推B” 的推理正確的推理正確 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A1 A2 AkB為重言式為重言式.推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 結(jié)論：結(jié)論： B 若推理正確，則記作：若推理正確，則記作：A1 A2 AkB.4判斷推理是否正確的方法判斷推理是否正確的方

3、法真值表法真值表法等值演算法等值演算法 判斷推理是否正確判斷推理是否正確主析取范式法主析取范式法構(gòu)造證明法構(gòu)造證明法 證明推理正確證明推理正確 說(shuō)明：當(dāng)命題變項(xiàng)比較少時(shí)，用前說(shuō)明：當(dāng)命題變項(xiàng)比較少時(shí)，用前3 3個(gè)方法比較個(gè)方法比較方方便便, , 此時(shí)采用此時(shí)采用形式結(jié)構(gòu)形式結(jié)構(gòu)“ A1 A2 AkB” . 而在而在構(gòu)構(gòu)造證明時(shí)，造證明時(shí)，采用采用“前提前提: A1, A2, , Ak, 結(jié)論結(jié)論: B”. 5實(shí)例實(shí)例例例 判斷下面推理是否正確判斷下面推理是否正確 (1) 若今天是若今天是1號(hào)，則明天是號(hào)，則明天是5號(hào)號(hào). 今天是今天是1號(hào)號(hào). 所所 以明天是以明天是5號(hào)號(hào). 解解 設(shè)設(shè) p：今

4、天是：今天是1號(hào)，號(hào)，q：明天是：明天是5號(hào)號(hào). 推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為: (pq) pq證明（用等值演算法）證明（用等值演算法） (pq) pq ( p q) p) q pq q 1得證推理正確得證推理正確 6實(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 ( p q) qp ( p q) q) p q p ( pq) (p

5、q) (pq) (p q) m0 m2 m3 結(jié)果不含結(jié)果不含m1, 故故01是成假賦值，所以推理不正確是成假賦值，所以推理不正確. 7推理定律推理定律重言蘊(yùn)涵式重言蘊(yùn)涵式 重要的推理定律重要的推理定律 A (A B) 附加律附加律 (A B) A 化簡(jiǎn)律化簡(jiǎn)律 (AB) A B 假言推理假言推理 (AB)B A 拒取式拒取式 (A B)B A 析取三段論析取三段論 (AB) (BC) (AC) 假言三段論假言三段論 (AB) (BC) (AC) 等價(jià)三段論等價(jià)三段論 (AB) (CD) (A C) (B D) 構(gòu)造性二難構(gòu)造性二難 8推理定律推理定律 (續(xù)續(xù))(AB) ( AB) B 構(gòu)造性

6、二難（特殊形式）構(gòu)造性二難（特殊形式）(AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難說(shuō)明：說(shuō)明： A, B, C為元語(yǔ)言符號(hào)為元語(yǔ)言符號(hào)若某推理符合某條推理定律，則它自然是正確的若某推理符合某條推理定律，則它自然是正確的AB產(chǎn)生兩條推理定律產(chǎn)生兩條推理定律: A B, B A9推理規(guī)則推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則(2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則(3) 置換規(guī)則置換規(guī)則(4) 假言推理規(guī)則假言推理規(guī)則 AB A B(5) 附加規(guī)則附加規(guī)則 A A B (6) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(guī)則 A B A (7) 拒取式規(guī)則拒取式規(guī)則 AB B A(8) 假言三段論規(guī)則假言三段論規(guī)

7、則 AB BC AC 10推理規(guī)則推理規(guī)則( (續(xù)續(xù)) ) (11) 破壞性二難推理破壞性二難推理規(guī)則規(guī)則 AB CD BD AC(12) 合取引入規(guī)則合取引入規(guī)則 A B A B (9) 析取三段論規(guī)則析取三段論規(guī)則 A B B A (10)構(gòu)造性二難推理構(gòu)造性二難推理規(guī)則規(guī)則 AB CD A C B D11直接證明法例例2 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明:前提前提: p q, qr, ps, s結(jié)論結(jié)論: r(p q) )12直接證明法例例2 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造下面推理的證明中構(gòu)造下面推理的證明:前提前提: p q, qr, ps,

8、 s結(jié)論結(jié)論: r(p q) )證明證明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論 qr 前提引入前提引入 r 假言推理假言推理 r(p q) ) 合取合取推理正確推理正確, , r(p q) )是有效結(jié)論是有效結(jié)論13構(gòu)造證明構(gòu)造證明直接證明法直接證明法例例 構(gòu)造下面推理的證明：構(gòu)造下面推理的證明： 若明天是星期一或星期三，我就有課若明天是星期一或星期三，我就有課. 若有課，若有課，今天必備課今天必備課. 我今天下午沒(méi)備課我今天下午沒(méi)備課. 所以，所以， 明天不是星期一和星期三明天不是星期一和星期三. 解解 設(shè)設(shè) p：

9、明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三， r：我有課，：我有課，s：我備課：我備課推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為 前提：前提：(p q)r, rs, s 結(jié)論：結(jié)論： pq 14直接證明法直接證明法 (續(xù)續(xù))證明證明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換 15附加前提證明法欲證明欲證明 等價(jià)地證明等價(jià)地證明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C結(jié)論結(jié)論: CB 結(jié)論結(jié)論: B理由理由: (A1 A2 Ak)(CB) (A1 A2

10、 Ak) ( C B) (A1 A2 Ak C) B (A1 A2 Ak C)B16實(shí)例例例4 構(gòu)造下面推理的證明構(gòu)造下面推理的證明:前提前提: p q, q r, rs結(jié)論結(jié)論: ps證明證明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段論析取三段論 q r 前提引入前提引入 r 析取三段論析取三段論 rs 前提引入前提引入 s 假言推理假言推理推理正確推理正確, , ps是有效結(jié)論是有效結(jié)論17歸謬法(反證法)欲證明欲證明前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B將將 B加入前提加入前提, 若推出矛盾若推出矛盾, 則得證推理正確則得證推理正確. 理由理由:

11、 A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB)括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng)括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1 A2 AkB)為重言式為重言式18實(shí)例例例5 構(gòu)造下面推理的證明構(gòu)造下面推理的證明前提前提: (p q) r, rs, s, p結(jié)論結(jié)論: q證明證明 用歸繆法用歸繆法 q 結(jié)論否定引入結(jié)論否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q) r 前提引入前提引入 (p q) 析取三段論析取三段論 pq 置換置換 p 析取三段論析取三段論 p 前提引入前提引入 p p 合取合取 推理正確推理正確, , q是有效結(jié)論是有效結(jié)論19歸結(jié)證明

12、法理由理由 (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歸結(jié)規(guī)則歸結(jié)規(guī)則 A B A C B C20歸結(jié)特殊形式歸結(jié)規(guī)則歸結(jié)規(guī)則 A B A B歸結(jié)規(guī)則歸結(jié)規(guī)則 A A C C歸結(jié)規(guī)則歸結(jié)規(guī)則 A A 021歸結(jié)證明法(續(xù))在自然推理系統(tǒng)在自然推理系統(tǒng)P中只需下述推理規(guī)則中只需下述推理規(guī)則:(1) 前提引入規(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ī)則22歸結(jié)證明法的基本

13、步驟1. 將每一個(gè)前提化成等值的合取范式將每一個(gè)前提化成等值的合取范式, 設(shè)所有合取范式的設(shè)所有合取范式的 全部簡(jiǎn)單析取式為全部簡(jiǎn)單析取式為A1, A2, At2. 將結(jié)論化成等值的合取范式將結(jié)論化成等值的合取范式B1 B2 Bs, 其中每個(gè)其中每個(gè)Bj 是簡(jiǎn)單析取式是簡(jiǎn)單析取式3. 以以A1,A2,At為前提為前提, 使用歸結(jié)規(guī)則推出每一個(gè)使用歸結(jié)規(guī)則推出每一個(gè)Bj, 1 j s4. 由合取引入規(guī)則得到結(jié)論由合取引入規(guī)則得到結(jié)論B1 B2 Bs23實(shí)例例例6 用歸結(jié)證明法構(gòu)造下面推理的證明用歸結(jié)證明法構(gòu)造下面推理的證明:前提前提: ( (pq)r, rs, s結(jié)論結(jié)論: ( (pq)()(p

14、 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結(jié)論結(jié)論: p (q s)24實(shí)例(續(xù))前提前提: : p r, , q r, , r s, , s結(jié)論結(jié)論: p(q s)證明證明 q r 前提引入前提引入 r s 前提引入前提引入 q s 歸結(jié)歸結(jié) s 前提引入前提引入 r 歸結(jié)歸結(jié) p r 前提引入前提引入 p 歸結(jié)歸結(jié) p(q s) 合取引入合

15、取引入 25歸結(jié)證明法的基本步驟1. 將每一個(gè)前提化成等值的合取范式將每一個(gè)前提化成等值的合取范式, 設(shè)所有合取設(shè)所有合取范式的全部簡(jiǎn)單析取式為范式的全部簡(jiǎn)單析取式為A1, A2, At2. 將結(jié)論的反面化成等值的合取范式將結(jié)論的反面化成等值的合取范式B1 B2 Bs, 其中每個(gè)其中每個(gè)Bj 是簡(jiǎn)單析取式是簡(jiǎn)單析取式3. 以以A1,A2,At和和Bj, 1 j s為前提導(dǎo)出矛盾！為前提導(dǎo)出矛盾！26實(shí)例例例6 用歸結(jié)證明法構(gòu)造下面推理的證明用歸結(jié)證明法構(gòu)造下面推理的證明:前提前提: ( (pq)r, rs, s結(jié)論結(jié)論: ( (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) () (pq)(p s) ) ( (p q)(ps) ) (p q) (ps) ) 推理可表成推理可表成前提前提: : p r, , q