離散數(shù)學(xué)屈婉玲第三章PPT優(yōu)秀課件

1、1 主要內(nèi)容主要內(nèi)容 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) l 推理的正確與錯誤推理的正確與錯誤 l 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) l 判斷推理正確的方法判斷推理正確的方法 l 推理定律推理定律 自然推理系統(tǒng)自然推理系統(tǒng)P l 形式系統(tǒng)的定義與分類形式系統(tǒng)的定義與分類 l 自然推理系統(tǒng)自然推理系統(tǒng)P l 在在P中構(gòu)造證明中構(gòu)造證明:直接證明法、附加前提證明法、歸謬法直接證明法、附加前提證明法、歸謬法 第三章第三章 命題邏輯的推理理論命題邏輯的推理理論 2 3.1 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 定義定義3.1 設(shè)設(shè)A1, A2, , Ak, B為命題公式為命題公式. 若對于每一組賦值，若對于每一組賦值，

2、 A1 A2 Ak 為假，或當(dāng)為假，或當(dāng)A1 A2 Ak為真時，為真時，B也為真，也為真， 則稱由則稱由前提前提A1, A2, , Ak推出推出結(jié)論結(jié)論B的的推理推理是是有效的有效的或或正確正確 的的, 并稱并稱B是是有效結(jié)論有效結(jié)論. 定理定理3.1 由命題公式由命題公式A1, A2, , Ak 推出推出B的推理正確當(dāng)且僅當(dāng)?shù)耐评碚_當(dāng)且僅當(dāng) A1 A2 AkB為重言式為重言式 注意注意: 推理正確不能保證結(jié)論一定正確推理正確不能保證結(jié)論一定正確 3 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 2. A1 A2 AkB 若推理正確若推理正確, 記為記為A1 A2 Ak B 3. 前提：前提： A1, A2

3、, , Ak 結(jié)論：結(jié)論： B 判斷推理是否正確的方法判斷推理是否正確的方法: 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 1. A1, A2, , Ak B 若推理正確若推理正確, 記為記為A1,A2,An B 4 推理實例推理實例 例例1 判斷下面推理是否正確判斷下面推理是否正確 (1) 若今天是若今天是1號號, 則明天是則明天是5號號. 今天是今天是1號號. 所以所以, 明天是明天是5號號. (2) 若今天是若今天是1號號, 則明天是則明天是5號號. 明天是明天是5號號. 所以所以, 今天是今天是1號號. 解解 設(shè)設(shè) p：今天是：今天是

4、1號，號，q：明天是：明天是5號號. (1) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): (pq) pq 用等值演算法用等值演算法 (pq) pq ( p q) p) q pq q 1 推理正確推理正確 5 推理實例推理實例 (2) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): (pq) qp 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 推理不正確推理不正確 6 推理定律推理定律重言蘊涵式重言蘊涵式 1. A (A B) 附加律附加律 2. (A B) A 化簡律化簡律 3. (AB) A B 假言推理假

5、言推理 4. (AB)B A 拒取式拒取式 5. (A B)B A 析取三段論析取三段論 6. (AB) (BC) (AC) 假言三段論假言三段論 7. (AB) (BC) (AC) 等價三段論等價三段論 8. (AB) (CD) (A C) (B D) 構(gòu)造性二難構(gòu)造性二難 (AB) ( AB) B 構(gòu)造性二難構(gòu)造性二難(特殊形式特殊形式) 9. (AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難 每個等值式可產(chǎn)生兩個推理定律每個等值式可產(chǎn)生兩個推理定律 如如, 由由AA可產(chǎn)生可產(chǎn)生 AA 和和 AA 7 3.2 自然推理系統(tǒng)自然推理系統(tǒng)P 定義定義3.2 一個一個形式系統(tǒng)形式

6、系統(tǒng) I 由下面四個部分組成：由下面四個部分組成： (1) 非空的字母表，記作非空的字母表，記作 A(I). (2) A(I) 中符號構(gòu)造的合式公式集，記作中符號構(gòu)造的合式公式集，記作 E(I). (3) E(I) 中一些特殊的公式組成的公理集，記作中一些特殊的公式組成的公理集，記作 AX(I). (4) 推理規(guī)則集，記作推理規(guī)則集，記作 R(I). 記記I=, 其中其中是是 I 的的形式語言形式語言 系統(tǒng)系統(tǒng), 是是 I 的的形式演算系統(tǒng)形式演算系統(tǒng). 自然推理系統(tǒng)自然推理系統(tǒng): 無公理集無公理集, 即即AX(I)= 公理推理系統(tǒng)公理推理系統(tǒng) 有公理集有公理集, 推出的結(jié)論是系統(tǒng)中的重言式推

7、出的結(jié)論是系統(tǒng)中的重言式, 稱稱 作作定理定理 8 自然推理系統(tǒng)自然推理系統(tǒng)P 定義定義3.3 自然推理系統(tǒng)自然推理系統(tǒng) P 定義定義如下如下: 1. 字母表字母表 (1) 命題變項符號：命題變項符號：p, q, r, , pi, qi, ri, (2) 聯(lián)結(jié)詞符號：聯(lián)結(jié)詞符號： , , , , (3) 括號與逗號：括號與逗號：(, ), ， 2. 合式公式（同定義合式公式（同定義1.6） 3. 推理規(guī)則推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則 (2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則 (3) 置換規(guī)則置換規(guī)則 9 推理規(guī)則推理規(guī)則 (4) 假言推理規(guī)則假言推理規(guī)則 (6) 化簡規(guī)則化簡規(guī)則 (8)

8、 假言三段論規(guī)則假言三段論規(guī)則 AB A B A A B A B A (5) 附加規(guī)則附加規(guī)則 (7) 拒取式規(guī)則拒取式規(guī)則 (9) 析取三段論規(guī)則析取三段論規(guī)則 AB B A AB BC AC A B B A 10 推理規(guī)則推理規(guī)則 (10) 構(gòu)造性二難推理規(guī)則構(gòu)造性二難推理規(guī)則 (11) 破壞性二難推理規(guī)則破壞性二難推理規(guī)則 (12) 合取引入規(guī)則合取引入規(guī)則 AB CD A C B D AB CD BD A C A B A C 11 在自然推理系統(tǒng)在自然推理系統(tǒng)P中構(gòu)造證明中構(gòu)造證明 設(shè)前提設(shè)前提A1, A2, Ak,結(jié)論結(jié)論B及公式序列及公式序列C1, C2, Cl. 如果每如果每 一

9、個一個Ci(1 i l)是某個是某個Aj, 或者可由序列中前面的公式應(yīng)用推理或者可由序列中前面的公式應(yīng)用推理 規(guī)則得到規(guī)則得到, 并且并且Cl =B, 則稱這個公式序列是由則稱這個公式序列是由A1, A2, Ak推推 出出B的的證明證明 例例2 構(gòu)造下面推理的證明：構(gòu)造下面推理的證明： 若明天是星期一或星期三若明天是星期一或星期三, 我明天就有課我明天就有課. 若我明天有課若我明天有課, 今天必備課今天必備課. 我今天沒備課我今天沒備課. 所以所以, 明天不是星期一明天不是星期一, 也不也不 是星期三是星期三. 解解 (1) 設(shè)命題并符號化設(shè)命題并符號化 設(shè)設(shè) p：明天是星期一，：明天是星期一

10、，q：明天是星期三，：明天是星期三， r：我明天有課，：我明天有課，s：我今天備課：我今天備課 12 直接證明法直接證明法 (2) 寫出證明的形式結(jié)構(gòu)寫出證明的形式結(jié)構(gòu) 前提：前提：(p q)r, rs, s 結(jié)論：結(jié)論： pq (3) 證明證明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換 13 附加前提證明法附加前提證明法 附加前提證明法附加前提證明法 適用于結(jié)論為蘊涵式適用于結(jié)論為蘊涵式 欲證欲證 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：CB 等價地證明等價地證明 前提：前提：A1, A

11、2, , Ak, C 結(jié)論：結(jié)論：B 理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B 14 附加前提證明法實例附加前提證明法實例 例例3 構(gòu)造下面推理的證明構(gòu)造下面推理的證明 2是素數(shù)或合數(shù)是素數(shù)或合數(shù). 若若2是素數(shù)是素數(shù), 則則 是無理數(shù)是無理數(shù). 若若 是無理數(shù)是無理數(shù), 則則4不是素數(shù)不是素數(shù). 所以所以, 如果如果4是素數(shù)是素數(shù), 則則2是合數(shù)是合數(shù). 解解 用附加前提證明法構(gòu)造證明用附加前提證明法構(gòu)造證明 (1) 設(shè)設(shè) p：2是素數(shù)，是素數(shù)，q：2是合數(shù)，是合數(shù)， r： 是無理數(shù)，是無理數(shù)

12、，s：4是素數(shù)是素數(shù) (2) 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 前提：前提：p q, pr, rs 結(jié)論：結(jié)論：sq 15 附加前提證明法實例附加前提證明法實例 (3) 證明證明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段論假言三段論 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論 16 歸謬法（反證法）歸謬法（反證法） 歸謬法歸謬法 (反證法反證法) 欲證欲證 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B 做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾. 理由理由 A1 A2 AkB (A1 A2 Ak)

13、 B (A1 A2 AkB) (A1 A2 AkB) 0 A1 A2 AkB0 17 歸謬法實例歸謬法實例 例例4 前提：前提： (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 合取合取 18 第三章第三章 習(xí)題課習(xí)題課 主要內(nèi)容主要內(nèi)容 l 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) l 判斷推理是否正確的方法判斷推理是否正確的方法 真值表法

14、真值表法 等值演算法等值演算法 主析取范式法主析取范式法 l 推理定律推理定律 l 自然推理系統(tǒng)自然推理系統(tǒng)P l 構(gòu)造推理證明的方法構(gòu)造推理證明的方法 直接證明法直接證明法 附加前提證明法附加前提證明法 歸謬法歸謬法(反證法反證法) 19 基本要求基本要求 l 理解并記住推理形式結(jié)構(gòu)的兩種形式：理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：B l 熟練掌握判斷推理是否正確的不同方法（如真值表法、等熟練掌握判斷推理是否正確的不同方法（如真值表法、等 值演算法、主析取范式法等）值演算法、主析取范式法等） l 牢記牢記 P

15、 系統(tǒng)中各條推理規(guī)則系統(tǒng)中各條推理規(guī)則 l 熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬熟練掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬 法法 l 會解決實際中的簡單推理問題會解決實際中的簡單推理問題 20 練習(xí)練習(xí)1：判斷推理是否正確：判斷推理是否正確 1. 判斷下面推理是否正確判斷下面推理是否正確: (1) 前提：前提： pq, q 結(jié)論：結(jié)論： p 解解 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu): ( pq)qp 方法一：等值演算法方法一：等值演算法 ( pq)qp (p q)q)p ( pq) qp ( p q) ( q q)p p q 不是重言式，所以推理不正確不是重言式，所以推理不正確

16、. 21 練習(xí)練習(xí)1解答解答 方法二：主析取范式法，方法二：主析取范式法， ( pq)qp (p q)q)p p q M2 m0 m1 m3 未含未含m2, 不是重言式不是重言式, 推理不正確推理不正確. 22 練習(xí)練習(xí)1解答解答 方法三方法三 真值表法真值表法 不是重言式不是重言式, 推理不正確推理不正確 111 001 110 100 ( pq)qpqp pq 0 1 1 1 ( pq)q 0 0 1 0 方法四方法四 直接觀察出直接觀察出10是成假賦值是成假賦值 23 練習(xí)練習(xí)1解答解答 用等值演算法用等值演算法 (qr) (pr)(qp) ( q r) ( pr)( qp) (qr)

17、(p r)( qp) (q p) (q r) ( r p)( qp) (q p) (q r) ( r p) ( qp) 1 推理正確推理正確 (2) 前提：前提：qr, pr 結(jié)論：結(jié)論：qp 解解 推理的形式結(jié)構(gòu)：推理的形式結(jié)構(gòu)： (qr) (pr)(qp) 24 練習(xí)練習(xí)2：構(gòu)造證明：構(gòu)造證明 2. 在系統(tǒng)在系統(tǒng)P中構(gòu)造下面推理的證明：中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和如果頤和 園游人太多，就不去頤和園園游人太多，就不去頤和園. 今天是周六，并且頤和園游今天是周六，并且頤和園游 人太多人太多. 所以所以, 我們?nèi)A明園或動物園玩我們?nèi)A明園或