離散數(shù)學(xué)第二章3

1、1,2.4 推理,2.4.1 推理的形式結(jié)構(gòu)推理的前提與結(jié)論,正確推理2.4.2 推理的證明推理規(guī)則直接證明法, 附加前提證明法, 歸謬法(反證法)2.4.3 歸結(jié)證明法2.4.4 對證明方法的補充說明,2,有效推理,定義2.20 若對于每組賦值, A1ÙA2Ù…Ù Ak 為假, 或者當(dāng)A1ÙA2Ù…ÙAk為真時, B也為真, 則稱由前提A1,A2,…

2、, Ak推B的推理有效或推理正確, 并稱B是有效的結(jié)論定理2.8 由前提A1, A2, …, Ak 推出B 的推理正確當(dāng)且僅當(dāng) A1ÙA2Ù…ÙAk®B為重言式.,3,推理的形式結(jié)構(gòu),形式(1) A1ÙA2Ù…ÙAk®B形式(2) 前提: A1, A2, … , Ak 結(jié)論:

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

4、 (p®q)Ùp®q Û Ø((ØpÚq)Ùp)Úq Û ((pÙØq)ÚØp)Úq Û ØpÚØqÚq Û 1得證推理正確,5,實例(續(xù)),(2) 若今天

5、是1號, 則明天是5號. 明天是5號. 所以, 今天是1號. 解 設(shè)p: 今天是1號, q: 明天是5號. 推理的形式結(jié)構(gòu)為 (p®q)Ùq®p證明 用主析取范式法 (p®q)Ùq®p Û (ØpÚq)Ùq®p Û Ø ((Ø

6、pÚq)Ùq)Úp Û ØqÚp Û (ØpÙØq)Ú(pÙØq)Ú (pÙØq)Ú(pÙq) Û m0Úm2Úm3 01是成假賦值, 所以推理不正確.,6,推理定律——重言蘊涵

7、式,A Þ (AÚB) 附加律 (AÙB) Þ A 化簡律(A®B)ÙA Þ B

8、 假言推理(A®B)ÙØB Þ ØA 拒取式(AÚB)ÙØB Þ A 析取三段論(A®B)Ù(B®C) &

9、#222; (A®C) 假言三段論(A«B)Ù(B«C) Þ (A«C) 等價三段論(A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 構(gòu)造性二難 (

10、A®B)Ù(ØA®B) Þ B 構(gòu)造性二難(特殊形式)(A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破壞性二難,7,推理規(guī)則,,8,推理規(guī)則(續(xù)),9,直接證明法,例2 構(gòu)造下面推理的證明:前提: pÚ

11、;q, q®r, p®s, Øs結(jié)論: rÙ(pÚq)證明 ① p®s 前提引入② Ø s 前提引入③ Ø p ①②拒取式④ pÚq

12、 前提引入⑤ q ③④析取三段論 ⑥ q®r 前提引入⑦ r ⑤⑥假言推理⑧ rÙ(pÚq) ⑦④合取推理正確, r&#

13、217;(pÚq)是有效結(jié)論,10,實例,例3 構(gòu)造推理的證明: 若明天是星期一或星期三, 我就有課. 若有課, 今天必需備課. 我今天下午沒備課. 所以, 明天不是星期一和星期三. 解 設(shè) p:明天是星期一, q:明天是星期三， r:我有課， s:我備課前提: (pÚq)®r, r®s, Øs結(jié)論: ØpÙ&

14、#216;q,11,實例(續(xù)),前提: (pÚq)®r, r®s, Øs結(jié)論: ØpÙØq 證明① r®s 前提引入 ② Øs 前提引入③ Ør ①②拒取式④ (pÚq)®r

15、 前提引入⑤ Ø(pÚq) ③④拒取式⑥ ØpÙØq ⑤置換結(jié)論有效, 即明天不是星期一和星期三,12,附加前提證明法,欲證明 等價地證明前提: A1, A2, …, Ak 前提: A1, A2, …, Ak, C結(jié)論: C&

16、#174;B 結(jié)論: B,理由: (A1ÙA2Ù…ÙAk)®(C®B) Û Ø( A1ÙA2Ù…ÙAk)Ú(ØCÚB) Û Ø( A1ÙA2Ù…ÙAkÙ

17、C)ÚB Û (A1ÙA2Ù…ÙAkÙC)®B,13,實例,例4 構(gòu)造下面推理的證明:前提: ØpÚq, ØqÚr, r®s結(jié)論: p®s證明 ① p 附加前提引入② ØpÚq

18、 前提引入③ q ①②析取三段論④ ØqÚr 前提引入⑤ r ③④析取三段論 ⑥ r®s 前提引入⑦ s

19、 ⑤⑥假言推理推理正確, p®s是有效結(jié)論,14,歸謬法(反證法),欲證明前提：A1, A2, … , Ak 結(jié)論：B將ØB加入前提, 若推出矛盾, 則得證推理正確.,理由: A1ÙA2Ù…ÙAk®B Û Ø(A1ÙA2Ù…ÙAk)&

20、#218;B Û Ø(A1ÙA2Ù…ÙAkÙØB) Û Ø(A1ÙA2Ù…ÙAkÙØB)?0 ? (A1ÙA2Ù…ÙAk??B) ®0,15,實例,例5 構(gòu)造下面推理的證明前提: Ø(p

21、7;q)Úr, r®s, Øs, p結(jié)論: Øq證明 用歸繆法① q 結(jié)論否定引入② r®s 前提引入③ Øs 前提引入④ Ør ②③拒取式,16,實例(續(xù)),⑤ Ø(pÙq)&

22、#218;r 前提引入 ⑥ Ø(pÙq) ④⑤析取三段論⑦ ØpÚØq ⑥置換⑧ Øp ①⑦析取三段論⑨ p 前提引入⑩ ØpÙp ⑧⑨合

23、取推理正確, Øq是有效結(jié)論,17,歸結(jié)證明法,理由 (pÚq)Ù(ØpÚr)®(qÚr)Û Ø((pÚq)Ù(ØpÚr))Ú(qÚr)Û (ØpÙØq)Ú(pÙØr)ÚqÚrÛ

24、((ØpÙØq)Úq)Ú((pÙØr)Úr)Û (ØpÚq)Ú(pÚr)Û 1,18,歸結(jié)證明法的基本步驟,1. 將每一個前提化成等值的合取范式, 設(shè)所有合取范式的全部簡單析取式為A1, A2,…, At2. 將結(jié)論的否定化成等值的合取范式B1ÙB2Ù…ÙBs,

25、 其中每個Bj是簡單析取式3. 以A1,A2,…,At和B1,B2,?,Bs為前提, 使用歸結(jié)規(guī)則推出0除前提引入規(guī)則外, 只使用歸結(jié)規(guī)則,19,實例,例6 用歸結(jié)證明法構(gòu)造下面推理的證明:前提: (p®q)®r, r®s, Øs結(jié)論: p??q解 (p®q)®r Û Ø(ØpÚq)Úr Û (p

26、17;Øq)Úr Û (pÚr)Ù(ØqÚr) r®s Û ØrÚs ?(p??q) Û ØpÚq把推理的前提改寫成前提: pÚr, ØqÚr, ØrÚs, Øs, ØpÚq(結(jié)論均為0, 不必寫出)

27、,20,實例(續(xù)),前提: pÚr, ØqÚr, ØrÚs, Øs , ØpÚq證明 ① pÚr 前提引入② ØpÚq 前提引入③ qÚr ①②歸結(jié)

28、④ ØqÚr 前提引入⑤ r ③④歸結(jié)⑥ ØrÚs 前提引入⑦ s ⑤⑥歸結(jié)⑧ ?s

29、 前提引入⑨ 0 ⑦⑧合取,21,對證明方法的補充說明,直接證明法 當(dāng)A為真時B為真, 則A?B為真前提假證明法 若A為矛盾式, 則A?B為真. 結(jié)論真證明法 若B為永真式, 則 A?B為真 (不管A如何)間接證明法 A?B??B??A分情況證明法 (A1?A2???Ak)?B