離散數(shù)學之推理

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

2、程描述推理正確的過程. 3推理的形式結構推理的形式結構 定義定義 若對于每組賦值，或者若對于每組賦值，或者A1 A2 Ak 均為假，均為假，或者當或者當A1 A2 Ak為真時為真時, B也為真也為真, 則稱由則稱由A1,A2, , Ak推推B的的推理正確推理正確, 否則否則推理不正確（錯誤）推理不正確（錯誤）.“A1, A2, , Ak 推推B” 的推理正確的推理正確 當且僅當當且僅當 A1 A2 AkB為重言式為重言式.推理的形式結構推理的形式結構: A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 結論：結論： B 若推理正確，則記作：若推理正確，則記作：A1 A2 AkB

3、.4判斷推理是否正確的方法判斷推理是否正確的方法真值表法真值表法等值演算法等值演算法 判斷推理是否正確判斷推理是否正確主析取范式法主析取范式法構造證明法構造證明法 證明推理正確證明推理正確 說明：用前說明：用前3 3個方法時采用個方法時采用形式結構形式結構 “ A1 A2 AkB” . 用構造證明時用構造證明時, 采用采用 “前提前提: A1, A2, , Ak, 結論結論: B”. 5實例實例例例 判斷下面推理是否正確判斷下面推理是否正確 (1) 若今天是若今天是1號，則明天是號，則明天是5號號. 今天是今天是1號號. 所所 以明天是以明天是5號號. 解解 設設 p：今天是：今天是1號，號，

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

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

6、二難（特殊形式）(AB) (CD) ( BD) ( AC) 破壞性二難破壞性二難證明證明: :描述推理過程的命題公式序列，其中每個命描述推理過程的命題公式序列，其中每個命題公式或者是已知的前提，或者是由前面的命題題公式或者是已知的前提，或者是由前面的命題公式應用推理規(guī)則得到的結論公式應用推理規(guī)則得到的結論. .9推理規(guī)則推理規(guī)則 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)構造性二難推理構造性二難推理規(guī)則規(guī)則 AB C

7、D A C B D11構造證明之一構造證明之一直接證明法直接證明法例例 構造下面推理的證明：構造下面推理的證明： 若明天是星期一或星期三，我就有課若明天是星期一或星期三，我就有課. 若有課，若有課，今天必備課今天必備課. 我今天下午沒備課我今天下午沒備課. 所以，所以， 明天不是星期一和星期三明天不是星期一和星期三. 解解 設設 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三， r：我有課，：我有課，s：我備課：我備課推理的形式結構為推理的形式結構為 前提：前提：(p q)r, rs, s 結論：結論： pq 12直接證明法直接證明法 (續(xù)續(xù))證明證明 rs 前提引入前提引

8、入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q) 拒取式拒取式 pq 置換置換 13構造證明之二構造證明之二附加前提證明法附加前提證明法 欲證明欲證明 前提：前提：A1, A2, , Ak 結論：結論：CB等價地證明等價地證明 前提：前提：A1, A2, , Ak, C 結論：結論：B 理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B14附加前提證明法附加前提證明法 (續(xù)續(xù)) 222例例 構造下面推理的證明構造下面推理的證明: 2是素數(shù)或合數(shù)是素數(shù)或合數(shù). 若若2是

9、素數(shù)，則是素數(shù)，則 是無理數(shù)是無理數(shù). 若若 是無理數(shù)，則是無理數(shù)，則4不是素數(shù)不是素數(shù). 所以，如果所以，如果4是是 素數(shù)，則素數(shù)，則2是合數(shù)是合數(shù). 用附加前提證明法構造證明用附加前提證明法構造證明解解 設設 p：2是素數(shù)，是素數(shù)，q：2是合數(shù)，是合數(shù)， r： 是無理數(shù)，是無理數(shù)，s：4是素數(shù)是素數(shù)推理的形式結構推理的形式結構 前提：前提：p q, pr, rs 結論：結論：sq15附加前提證明法附加前提證明法 (續(xù)續(xù))證明證明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段論假言三段論 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段論析取三段論請用直接證明法證明之請用直接證明法證明之 16構造證明之三構造證明之三歸謬法歸謬法(反證法反證法) 欲證明欲證明 前提：前提：A1, A2, , Ak 結論：結論：B將將 B加入前提，若推出矛盾，則得證推理正確加入前提，若推出矛盾，則得證推理正確.理由理由: A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB)括號內(nèi)部為矛盾式當且僅當括號內(nèi)部為矛盾式當且僅當 (A1 A2 AkB)為為重言式重言式 17歸謬法歸謬法 (續(xù)續(xù))例例 構造下面推理的證明構造下面推理的證明 前提：前提： (p q) r, rs, s, p 結論：結論： q證明（用歸繆法）證明（用歸繆