離散數(shù)學(xué)課件：第1章 命題邏輯4

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

2、正確的過程的過程. 3推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 定義定義 若若(A1 A2 Ak ) B為重言式，則稱：為重言式，則稱：由前由前提提A1, A2, , Ak推出結(jié)論推出結(jié)論B的的推理正確推理正確（或者說，（或者說， B是是A1, A2, , Ak的的邏輯結(jié)論或有效結(jié)論邏輯結(jié)論或有效結(jié)論）。）。概念上可稱概念上可稱(A1 A2 Ak ) B 為由為由A1,A2, , Ak推出結(jié)論推出結(jié)論B的的推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)。推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)的另一常見表達(dá)為以下格式：的另一常見表達(dá)為以下格式： 前提：前提： A1, A2, , Ak 結(jié)論：結(jié)論： B 若推理正確，則記作：若推理正確，

3、則記作：A1 A2 AkB.4判斷推理是否正確的方法判斷推理是否正確的方法真值表法真值表法等值演算法等值演算法 判斷判斷推理是否正確推理是否正確主范式法主范式法構(gòu)造構(gòu)造證明法證明法 展現(xiàn)推理過程正確展現(xiàn)推理過程正確 說明：用前說明：用前3 3個(gè)方法時(shí)采用的個(gè)方法時(shí)采用的形式結(jié)構(gòu)形式結(jié)構(gòu)表述是表述是 “ A1 A2 AkB” . 用構(gòu)造證明時(shí)用構(gòu)造證明時(shí), 采用的采用的形式結(jié)構(gòu)形式結(jié)構(gòu)表述表述前提前提: A1, A2, , Ak, 結(jié)論結(jié)論: B5實(shí)例實(shí)例例例 判斷下面推理是否正確判斷下面推理是否正確 (1) 若今天是若今天是1號，則明天是號，則明天是5號號. 今天是今天是1號號. 所所 以明天

4、是以明天是5號號. 解解 設(shè)設(shè) p：今天是：今天是1號，號，q：明天是：明天是5號號. 推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為: (pq) pq證明（用等值演算法）證明（用等值演算法） (pq) pq ( p q) p) q pq q 1可知可知推理正確推理正確 6實(shí)例實(shí)例 (續(xù)續(xù))(2) 若今天是若今天是1號，則明天是號，則明天是5號號. 明天是明天是5號號. 所以今天是所以今天是1號號. 解解 設(shè)設(shè)p：今天是：今天是1號，號，q：明天是：明天是5號號. 推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為: (pq) qp 證明（化主析取范式）證明（化主析取范式） (pq) qp ( p q) qp ( p q)

5、q) p q p pq M1 m0 m2 m3 結(jié)果不含結(jié)果不含m1, 故故01是成假賦值，所以推理不正確是成假賦值，所以推理不正確. 7重言蘊(yùn)涵式重言蘊(yùn)涵式推理定律推理定律重要的推理定律重要的推理定律 A (A B) 附加律附加律 (A B) A 化簡律化簡律 (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) 破壞性二難破壞性二難構(gòu)造證明構(gòu)造證明就是：描述推理過程的命題公式就是：描述推理過程的命題公式序列序列，其中每個(gè)命題公式或是其中每個(gè)命題公式或是已知的前提已知的前提，或是由在其，或是由在其之前出現(xiàn)的命題公式應(yīng)用推理規(guī)則之前出現(xiàn)的命題公式應(yīng)用推理規(guī)則推出的結(jié)論推出的結(jié)論. .9推理規(guī)則推理規(guī)則(1) 前提引入規(guī)則前提引入規(guī)則(P)(2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則(3) 置換規(guī)則置換規(guī)則(等值等值)(4) 假言推理規(guī)則假言推理規(guī)則 AB A B(5) 附加規(guī)則附加規(guī)則 A A B (6) 化簡規(guī)則化簡規(guī)則 A B A

7、(7) 拒取式規(guī)則拒取式規(guī)則 AB B A(8) 假言三段論規(guī)則假言三段論規(guī)則 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構(gòu)造證明（一）構(gòu)造證明（一）直接證明法直接證明法例例 構(gòu)造下面推理的證明：構(gòu)造下面推理的證明： 若明天是星期二或星期五，我就有課若明天是星期二或星期五，我就有課. 若明天若明天有課，今天必備課有課，今天必備課.

8、我今天沒備課我今天沒備課. 所以所以， 明天不是星期二和星期五明天不是星期二和星期五. 解解 設(shè)設(shè) p：明天是星期二，：明天是星期二，q：明天是星期五，：明天是星期五， r：我明天有課，：我明天有課，s：我今天備課：我今天備課推理的形式結(jié)構(gòu)為推理的形式結(jié)構(gòu)為 前提：前提：(p q)r, rs, s 結(jié)論：結(jié)論： pq 12直接證明法直接證明法 (續(xù)續(xù))證明證明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換 13構(gòu)造證明（二）構(gòu)造證明（二）附加前提法附加前提法 例例 構(gòu)造下面推理的證明構(gòu)造下面推理的證明:

9、 2是素?cái)?shù)或合數(shù)是素?cái)?shù)或合數(shù). 若若2是素?cái)?shù)，則是素?cái)?shù)，則 是無理數(shù)是無理數(shù). 若若 是無理數(shù)，則是無理數(shù)，則4不是素?cái)?shù)不是素?cái)?shù). 所以，如果所以，如果4是是 素?cái)?shù)，則素?cái)?shù)，則2是合數(shù)是合數(shù). 解：設(shè)解：設(shè) p：2是素?cái)?shù)，是素?cái)?shù)，q：2是合數(shù)，是合數(shù)， r： 是無理數(shù)，是無理數(shù)，s：4是素?cái)?shù)是素?cái)?shù)推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 前提：前提：p q, pr, rs 結(jié)論：結(jié)論：sq試證一下。試證一下。22214附加前提證明法附加前提證明法 (續(xù)續(xù))欲證明欲證明 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：CB等價(jià)于等價(jià)于證明證明 前提：前提：A1, A2, , Ak, C 結(jié)論：結(jié)論：B C

10、P規(guī)則規(guī)則理由：理由： (A1 A2 Ak) (CB) ( A1 A2 Ak) ( C B ) ( A1 A2 Ak C) B (A1 A2 Ak C) B15附加前提證明法附加前提證明法 (續(xù)續(xù))證明證明 ： s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段論假言三段論 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論 sq CP16構(gòu)造證明（三）構(gòu)造證明（三）歸謬法歸謬法(反證法反證法) 欲證明欲證明 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B將將 B加入前提，若推出矛盾，則得證推理正確加入前提，若推出矛盾，則得證推

11、理正確.理由理由: A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB)可見：可見：(A1 A2 AkB)為重言式當(dāng)且僅當(dāng)為重言式當(dāng)且僅當(dāng)括號括號內(nèi)部為矛盾式內(nèi)部為矛盾式17歸謬法歸謬法 (續(xù)續(xù))例例 構(gòu)造下面推理的證明構(gòu)造下面推理的證明 前提：前提： (p q) r, rs, s, p 結(jié)論：結(jié)論： q證明（用歸繆法）證明（用歸繆法） q 結(jié)論否定引入結(jié)論否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式18歸謬法歸謬法 (續(xù)續(xù)) (p q) r 前提引入前提引入 (p q) 析取三段論析取三段論 pq 置換置換 p 析取三段論析取三段論 p 前提引入前提引入 p p 合取合取 （這是矛盾式！這是矛盾式?。┱堄弥苯幼C明法證明之請用直接證明法證明之 19本章小結(jié)本章小結(jié)一一. 主范式與真值表的關(guān)系主范式與真值表的關(guān)系(主析取