離散數(shù)學(xué)之推理

1、11.7 推理理論推理理論 推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)判斷推理是否正確的方法判斷推理是否正確的方法推理定律與推理規(guī)則推理定律與推理規(guī)則構(gòu)造證明構(gòu)造證明 直接證明法直接證明法, 附加前提證明法附加前提證明法, 歸繆法歸繆法 2推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)問題的引入問題的引入 推理舉例推理舉例: (1) 正項級數(shù)收斂當(dāng)且僅當(dā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 均為假，均為假，或者當(dāng)或者當(dāng)A1 A2 Ak為真時為真時, B也為真也為真, 則稱由則稱由A1,A2, , Ak推推B的的推理正確推理正確, 否則否則推理不正確（錯誤）推理不正確（錯誤）.“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

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

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

5、q) m0 m2 m3 結(jié)果不含結(jié)果不含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) 構(gòu)造性二難構(gòu)造性二難 8推理定律推理定律 (續(xù)續(xù))(AB) ( AB) B 構(gòu)造性二難（特殊形式）構(gòu)造性

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

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

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

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