離散數(shù)學第三章 命題邏輯的推理理論

《離散數(shù)學第三章 命題邏輯的推理理論》由會員分享，可在線閱讀，更多相關《離散數(shù)學第三章 命題邏輯的推理理論（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、 為假，或當 1∧A2∧…∧Ak為真時，B也為真， 為假，或當A 也為真， ∧ ∧ 為真時， 也為真 則稱由前提 前提A 推出結(jié)論 結(jié)論B的推理是有效的或 則稱由前提 1, A2, …, Ak推出結(jié)論 的推理是有效的或正確 并稱B是有效結(jié)論. 的, 并稱 是有效結(jié)論 定理3.1 由命題公式A B的推理正確當且僅當 定理3.1 由命題公式A1, A2, …, Ak 推B的推理正確當且僅當 A1∧A2∧…∧Ak→B為重言式 ∧ 為重言式 留意: 留意 推理正確不能保證結(jié)論肯定正確 離散數(shù)學課件 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu) 1. {A1, A2, …, Ak} B 若

3、推理正確, 記為{A 若推理正確 記為 1,A2,…,An} B … 2. A1∧A2∧…∧Ak→B ∧ 若推理正確, 記為A1 ∧ A2 ∧ … ∧ Ak B 若推理正確 記為 3. 前提： A1, A2, … , Ak 前提： 結(jié)論： 結(jié)論： B 推斷推理是否正確的方法: 推斷推理是否正確的方法 真值表法 等值演算法 主析取范式法3 離散數(shù)學課件 推理實例例1 推斷下面推理是否正確 (1) 若今日是 號，則明天是 號. 今日是 號. 所以 明天是 號. 若今日是1號 則明天是5號 今日是1號 所以, 明天是5號 (2) 若今日是 號，則明天是 號. 明天是

4、 號. 所以 今日是 號. 若今日是1號 則明天是5號 明天是5號 所以, 今日是1號 解 設 p:今日是 號，q:明天是 號. :今日是1號 ：明天是5號 → ∧ → (1) 推理的形式結(jié)構(gòu) (p→q)∧p→q 推理的形式結(jié)構(gòu): 用等值演算法 (p→q)∧p→q → ∧ → ((p∨q)∧p)∨q ∨ ∧ ∨ ∨q∨ p∨ ∨q 1 ∨ 由定理3.1可知推理正確 由定理 可知推理正確4 離散數(shù)學課件 推理實例→ ∧ → (2) 推理的形式結(jié)構(gòu) (p→q)∧q→p 推理的形式結(jié)構(gòu): 用主析取范式法 (p→q)∧q→p → ∧ → (p∨q)∧q→

5、p ∨ ∧ → ((p∨q)∧q)∨p ∨ ∧ ∨ q∨p ∨ ∧q)∨ ∧ ∧q)∨ ∧ ∧q)∨ ∧ (p∧ ∨(p∧ ∨ (p∧ ∨(p∧q) ∧ m0∨m2∨m3 結(jié)果不含m 是成假賦值， 結(jié)果不含 1, 故01是成假賦值，所以推理不正確 是成假賦值 離散數(shù)學課件 推理定律——重言蘊涵式 推理定律——重言蘊涵式 ——A (A∨B) ∨ 附加律 (A∧B) A ∧ 化簡律 (A→B)∧A B → ∧ 假言推理 (A→B)∧ A ∧B → ∧ 拒取式 (A∨B)∧ A ∧B ∨ ∧ 析取三段論 (A→B)∧

6、(B→C) (A→C) → ∧ → → 假言三段論 (A B)∧(B C) (A C) ∧ 等價三段論 (A→B)∧(C→D)∧(A∨C) (B∨D) → ∧ → ∧ ∨ ∨ 構(gòu)造性二難 (A→B)∧(A→B) B 構(gòu)造性二難(特別形式 特別形式) → ∧ → 構(gòu)造性二難 特別形式 9. (A→B)∧(C→D)∧( B∨ (A∨ ∨D) ∨C) 破壞性二難 → ∧ → ∧ ∨ ∨ 1. 2. 3. 4. 5. 6. 7. 8. 每個等值式可產(chǎn)生兩個推理定律 A可產(chǎn)生 A A 如, 由A 可產(chǎn)生 A 和 A 離散數(shù)學課件

7、 3.2 自然推理系統(tǒng) 自然推理系統(tǒng)P定義3.2 一個形式系統(tǒng) I 由下面四個部分組成： 一個形式系統(tǒng) 由下面四個部分組成： 定義 (1) 非空的字母表，記作 A(I). 非空的字母表， (2) A(I) 中符號構(gòu)造的合式公式集，記作 E(I). 中符號構(gòu)造的合式公式集， (3) E(I) 中一些特別的公式組成的公理集，記作 AX(I). 中一些特別的公式組成的公理集， (4) 推理規(guī)章集，記作 R(I). 推理規(guī)章集， 其中A(I),E(I)是 I 的形式語言 記I=A(I),E(I),AX(I),R(I), 其中 是 系統(tǒng), 形式演算系統(tǒng). 系統(tǒng) AX(I),R(I) 是 I 的形式

8、演算系統(tǒng) 形式系統(tǒng)一般分為兩類： 形式系統(tǒng)一般分為兩類： 自然推理系統(tǒng): 無公理, 自然推理系統(tǒng) 無公理 即AX(I)= 推出的結(jié)論是系統(tǒng)中的重言式, 稱作定理 公理推理系統(tǒng) 推出的結(jié)論是系統(tǒng)中的重言式 稱作定理7 離散數(shù)學課件 自然推理系統(tǒng)P 自然推理系統(tǒng)定義3.3 自然推理系統(tǒng) P 定義如下 定義如下 如下: 定義 1. 字母表 (1) 命題變項符號：p, q, r, …, pi, qi, ri, … 命題變項符號： (2) 聯(lián)結(jié)詞符號：, ∧, ∨, →, 聯(lián)結(jié)詞符號： (3) 括號與逗號：(, ), , 括號與逗號： 2. 合式公式(同定義 )

9、合式公式(同定義1.6) 3. 推理規(guī)章: (1)—(12) 推理規(guī)章 — (1) 前提引入規(guī)章 在證明的任何步驟都可以引入前提 前提引入規(guī)章:在證明的任何步驟都可以引入前提 在證明的任何步驟都可以引入前提. (2) 結(jié)論引入規(guī)章 在證明的任何步驟所得的結(jié)論都有可以 結(jié)論引入規(guī)章:在證明的任何步驟所得的結(jié)論都有可以 作為后繼證明的前提. 作為后繼證明的前提 (3) 置換規(guī)章 在證明的任何步驟 命題公式中的子公式都可 置換規(guī)章:在證明的任何步驟 在證明的任何步驟,命題公式中的子公式都可 以用等值的公式置換,得到公式序列中又一個公式 得到公式序列中又一個公式. 以用等值的公式置換 得到公式序列中又

10、一個公式8 離散數(shù)學課件 推理規(guī)章(4) 假言推理規(guī)章 A→B → A ∴B (6) 化簡規(guī)章 A∧B ∧ ∴A (8) 假言三段論規(guī)章 A→B → B→C → ∴A→C → (5) 附加規(guī)章 A ∴A∨B ∨ (7) 拒取式規(guī)章 A→B → B ∴ A (9) 析取三段論規(guī)章 A∨B ∨ B ∴A 離散數(shù)學課件 推理規(guī)章(10) 構(gòu)造性 二難推理規(guī)章 A→B → C→D → A∨C ∨ ∴B∨D ∨ (12) 合取引入規(guī)章 A B ∴A∧C ∧ (11) 破壞性二難推理規(guī)章 A→B → C→D → ∨D B∨ ∨ ∴A∨C

11、∨ 離散數(shù)學課件 在自然推理系統(tǒng)P中構(gòu)造證明 在自然推理系統(tǒng) 中構(gòu)造證明設前提A 結(jié)論B及公式序列 設前提 1, A2,…, Ak,結(jié)論 及公式序列 1, C2,…, Cl. 假如每 … 結(jié)論 及公式序列C … 一個C ≤ ≤ 是某個 是某個A 一個 i(1≤i≤l)是某個 j, 或者可由序列中前面的公式應用推理 規(guī)章得到, 并且C 則稱這個公式序列是由A 規(guī)章得到 并且 l =B, 則稱這個公式序列是由 1, A2,…, Ak推 … 出B的證明 的 例2 構(gòu)造下面推理的證明： 構(gòu)造下面推理的證明： 若明天是星期一或星期四，我明天就有課. 若明天是星期一或星期四，

12、我明天就有課 若我明天有 今日必備課. 我今日沒備課. 所以，明天不是星期一、 課，今日必備課 我今日沒備課 所以，明天不是星期一、 也不是星期四. 也不是星期四 解 (1) 設命題并符號化 設 p:明天是星期一，q:明天是星期四， :明天是星期一， :明天是星期四， r:我明天有課，s:我今日備課 ：我明天有課， : 離散數(shù)學課件 挺直證明法(2) 寫出證明的形式結(jié)構(gòu) 前提： ∨ → 前提：(p∨q)→r, r→s, s → 結(jié)論： ∧ ∧q 結(jié)論：p∧ (3) 證明 ① r→s → 前提引入 ② s 前提引入 ①②拒取式 ③ r ①②拒取式 ④ (p∨q)→r

13、 ∨ → 前提引入 ③④拒取式 ⑤ (p∨q) ∨ ③④拒取式 ⑥ p∧ ∧q ⑤置換 ∧12 離散數(shù)學課件 附加前提證明法附加前提證明法 適用于結(jié)論為蘊涵式 欲證 前提： 前提：A1, A2, …, Ak 結(jié)論： → 結(jié)論：C→B 等價地證明 前提： 前提：A1, A2, …, Ak, C 結(jié)論： 結(jié)論：B 理由： 理由： (A1∧A2∧…∧Ak)→(C→B) ∧ → → ( A1∧A2∧…∧Ak)∨(C∨B) ∧ ∨ ∨ ( A1∧A2∧…∧Ak∧C)∨B ∧ ∨ (A1∧A2∧…∧Ak∧C)→B ∧ → 離散數(shù)學課件

14、 附加前提證明法實例例3 構(gòu)造下面推理的證明 2是素數(shù)或合數(shù) 若2是素數(shù)，則 是素數(shù)或合數(shù). 是素數(shù)， 是無理數(shù). 是素數(shù)或合數(shù) 是素數(shù) 是無理數(shù) 若 是無理 不是素數(shù). 是素數(shù)， 是合數(shù). 數(shù)，則4不是素數(shù) 所以，假如 是素數(shù)，則2是合數(shù) 不是素數(shù) 所以，假如4是素數(shù) 是合數(shù) 解 用附加前提證明法構(gòu)造證明 (1) 設 p:2是素數(shù)，q:2是合數(shù)， 是素數(shù)， : 是合數(shù) 是合數(shù)， : 是素數(shù) r: 是無理數(shù)，s:4是素數(shù) 是無理數(shù)， : 是素數(shù) ： (2) 推理的形式結(jié)構(gòu) 前提： ∨ →s 前提：p∨q, p→r, r→ → → 結(jié)論： → 結(jié)論：s→q 離散數(shù)學課件

15、 附加前提證明法實例(3) 證明 ①s ② p→r → →s ③ r→ → →s ④ p→ → ⑤ p ⑥ p∨q ∨ ⑦q 附加前提引入 前提引入 前提引入 ②③假言三段論 ②③假言三段論 ①④拒取式 ①④拒 取式 前提引入 ⑤⑥析取三段論 ⑤⑥析取三段論 離散數(shù)學課件 歸謬法(反證法) 歸謬法(反證法)反證法) 歸謬法 (反證法 反證法 欲證 前提： 前提：A1, A2, … , Ak 結(jié)論： 結(jié)論：B 做法 在前提中加入 ,推出沖突. 在前提中加入B,推出沖突 理由 A1∧A2∧…∧Ak→B ∧ (A1∧A2∧…∧Ak)∨B ∧ ∨ (A

16、1∧A2∧…∧Ak∧ ∧ ∧B) (A1∧A2∧…∧Ak∧ ∨0 ∧ ∧B)∨ A1∧A2∧…∧Ak∧ →0 ∧ ∧B→ 離散數(shù)學課件 例4 前提：(p∧q)∨r, r→s, s, p 前提： ∧ ∨ → 結(jié)論： 結(jié)論：q 證明 用歸繆法 ①q 結(jié)論否定引入 ② r→s → 前提引入 ③ s 前提引入 ②③拒取式 ④ r ②③拒取式 ⑤ (p∧q)∨r ∧ ∨ 前提引入 ④⑤析取三段論 ⑥ (p∧q) ∧ ④⑤析取三段論 ∨q ⑦ p∨ ∨ ⑥置換 ①⑦析取三段論 ⑧ p ①⑦析取三段論 ⑨p 前提引入 ⑧⑨合取 p∧p ∧ ⑧⑨合取 歸謬法實例

17、 離散數(shù)學課件 第三章 小結(jié)主要內(nèi)容 推理的形式結(jié)構(gòu) 推斷推理是否正確的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系統(tǒng)P 自然推理系統(tǒng) 構(gòu)造推理證明的方法 挺直證明法 附加前提證明法 歸謬法(反證法 反證法) 歸謬法 反證法18 離散數(shù)學課件 基本要求理解并記住推理形式結(jié)構(gòu)的兩種形式： 理解并記住推理形式結(jié)構(gòu)的兩種形式： 1. (A1∧A2∧…∧Ak)→B ∧ → 2. 前提：A1, A2, … , Ak 前提： 結(jié)論： 結(jié)論：B 嫻熟把握推斷推理是否正確的不同方法(如真值表法、 嫻熟把握推斷推理是否正確的不同方法(如

18、真值表法、等 值演算法、主析取范式法等) 值演算法、主析取范式法等) . P 系統(tǒng)中各條推理規(guī)章 嫻熟把握構(gòu)造證明的挺直證明法、 嫻熟把握構(gòu)造證明的挺直證明法、附加前提證明法和歸謬 法 會解決實際中的簡潔推理問題 離散數(shù)學課件 練近平1: 練. ：推斷推理是否正確1. 推斷下面推理是否正確 推斷下面推理是否正確: (1) 前提：p→q, q 前提： → 結(jié)論： 結(jié)論：p ∧q→ 推理的形式結(jié)構(gòu): → ∧ →p 解 推理的形式結(jié)構(gòu) (p→q)∧ → 方法一：等值演算法 方法一： (p→q)∧ → ∧q→ → ∧ →p ∧q)∨ ((p∨q)∧ ∨ ∨ ∧ ∨

19、p ∧q)∨ ∨ ∨p (p∧ ∨q∨ ∧ ∨p ((p∨q)∧(q∨q))∨ ∨ ∧ ∨ ∨ p∨q ∨ 易知10是成假賦值，不是重言式，所以推理不正確 易知 是成假賦值，不是重言式，所以推理不正確. 是成假賦值20 離散數(shù)學課件 練近平1解答 練近平 解答方法二：主析取范式法， 方法二：主析取范式法， (p→q)∧ → ∧q→ → ∧ →p ((p∨q)∧ ∨p ∨ ∧q)∨ ∧ ∨ p∨ ∨q M2 m0∨m1∨m3 未含m 不是重言式, 推理不正確. 未含 2, 不 是重言式 推理不正確

20、離散數(shù)學課件 練近平1解答 練近平 解答方法三 真值表法 p 0 0 1 1 q 0 1 0 1 p→q → 0 1 1 1 (p→q)∧ → ∧ ∧q 0 0 1 0 (p→q)∧ → → ∧ →p ∧q→ 1 1 0 1 不是重言式, 不是重言式 推理不正確 挺直觀看出10是成假賦值 方法四 挺直觀看出 是成假賦值22 離散數(shù)學課件 練.1解答 練. 解答(2) 前提：q→r, p→ 前提： → →r → 結(jié)論： → →p 結(jié)論：q→ →r)→ → →p) 推理的形式結(jié)構(gòu)： → ∧ → 解 推理的形式結(jié)構(gòu)： (q→r)∧(p→ →(

21、q→ 用等值演算法 (q→r)∧(p→ →(q→ →r)→ → →p) → ∧ → ∨r)→ ∨ ∨p) (q∨r)∧(p∨ →(q∨ ∨ ∧ ∨ ((q∧ ∧r)∨ ∧ → ∨ ∨p) ∧ ∨(p∧r))→(q∨ ((q∨ ∧ ∨ ∧ ∨ → ∨ ∨p) ∨p)∧(q∨r)∧(r∨p))→(q∨ ∨p) ((q∨p)∧(q∨r)∧(r∨p))∨(q∨ ∨ ∧ ∨ ∧ ∨ ∨ ∨ 1 推理正確23 離散數(shù)學課件 練近平2: 練近平 ：構(gòu)造證明2. 在系統(tǒng) 中構(gòu)造下面推理的證明： 在系統(tǒng)P中構(gòu)造下面推理的證明 中構(gòu)造下面推理的證明

22、： 假如今日是星期六，我們就到頤和園或圓明園去玩. 假如今日是星期六，我們就到頤和園或圓明園去玩 假如 頤和園游人太多，我們就不去頤和園玩. 今日是星期六.頤 頤和園游人太多，我們就不去頤和園玩 今日是星期六 頤 和園游人太多. 所以, 我們?nèi)A明園或動物園玩. 和園游人太多 所以 我們?nèi)A明園或動物園玩 證明： 證明： (1) 設 p:今日是周六，q:到頤和園玩， :今日是周六， :到頤和園玩， r:到圓明園玩，s:頤和園游人太多 ：到圓明園玩， : t:到動物園玩 ： (2) 前提：p→(q∨r), s→ p, s 前提： → ∨ →q, → 結(jié)論： ∨ 結(jié)論：r∨t24 離散數(shù)學課件 前提：p→(q∨r), s→ 前提： → ∨ →q, p, s → 結(jié)論： ∨ 結(jié)論：r∨t (3) 證明： 證明： ① p→(q∨r) → ∨ 前提引入 ②p 前提引入 ①②假言推理 ③ q∨r ∨ ①②假言推理 →q ④ s→ → 前提引入 ⑤s 前提引入 ④⑤假言推理 ⑥ q ④⑤假言推理 ③⑥析取三段論 ⑦r ③⑥析取三段論 ⑦附加 ⑧ r∨t ∨ 練近平2解答 練. 解答