離散數(shù)學(xué)高教版第3章

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

2、, Ak推出結(jié)論B的推理是有效的或正確的, 并稱B是有效結(jié)論.,說明：1. 由前提A1, A2, …, Ak推出結(jié)論B的推理是否正確與諸前提的排列次序無關(guān)，前提是一個(gè)有限集的公式集合。前提A1, A2, …, Ak推出結(jié)論B記為{A1, A2, …, Ak} B,推理的形式結(jié)構(gòu)1. {A1, A2, …, Ak} B 若推理正確, 記為{A1,A2,?,An} B,,2. 設(shè)A1, A2, …, Ak,

3、B中共出現(xiàn)n個(gè)命題變項(xiàng)，對(duì)于任一組賦值a1, a2, …, ak（ai =0或者1），前提和結(jié)論的取值 情況共有以下 4種 ： （1） A1?A2?…? Ak 為0，B為 0 （2）A1?A2?…? Ak 為0，B為 1 （3）A1?A2?…? Ak 為1，B為 0 （4）A1?A2?…? Ak 為1，B為 1由定義可知，只要 不出現(xiàn)第 3種情況，推理就是正確的，因而判斷推理是否正確，就是

4、判斷是否 會(huì)出現(xiàn)情況（3）。3.推理正確并不能保證結(jié)論一定成立；前提不正確，不論結(jié)論是否成立，都說推理正確。,3,4,例3.1 判斷下列推理是否正確。 （1） {p,p?q)} q （2） {p, q?p)} q,判斷方法：真值表法。判斷依據(jù)：看是否出現(xiàn)前提合取式為真，而結(jié)論為假的情況。,解:(1) 構(gòu)造真值表：,4,0 00 11 01 1,1101,0101,由真值表可知

5、，推理正確,,5,（2） {p, q?p)} q,解:(1) 構(gòu)造真值表：,5,5,0 00 11 01 1,0011,0101,由真值表可知，推理不正確,6,3.1 推理的形式結(jié)構(gòu),定理3.1 由命題公式A1, A2, …, Ak 推B的推理正確當(dāng)且僅當(dāng)A1?A2?…?Ak?B為重言式注意: 推理正確不能保證結(jié)論一定正確,定理說明： . {A1, A2, …, Ak} B 等

6、同于蘊(yùn)含式A1?A2?…?Ak?B {A1, A2, …, Ak} B 等同于 A1?A2?…?Ak ? B,7,推理的形式結(jié)構(gòu),2. A1?A2?…?Ak?B 若推理正確, 記為A1 ? A2 ? … ? Ak ? B3. 前提： A1, A2, … , Ak 結(jié)論： B判斷推理是否正確的方法: 真值表法 等值演算法 主析取范式法,推理的形式結(jié)構(gòu)1. {A1, A2,

7、…, Ak} B 若推理正確, 記為{A1,A2,?,An} B,例2 判斷下列推理是否正確若a能被4整除，則a能被2整除。a能被4整除。所以a能被2整除.若a能被4整除，則a能被2整除。a能被2整除。所以a能被4整除. 下午馬芳或去看電影或去游泳。她沒去看電影。所以，她去游泳了。 若下午氣溫超過30度，則王小燕必去游泳，她就不去看電影了。所以，若王小燕沒去看電影，下午氣溫必超過30度。,8,推理實(shí)例,解題

8、方法：第一步：將簡(jiǎn)單命題符號(hào)化 第二步：寫出前提、結(jié)論、推理的形式結(jié)構(gòu) 第三步：進(jìn)行判斷。,,解：設(shè) 前提：p ?q, p 結(jié)論：q 推理的形式結(jié)構(gòu): (p ?q) ? p ?q. 構(gòu)造真值表：,9,若a能被4整除，則a能被2整除。

9、a能被4整除。所以a能被2整除.,p:a能被4整除,q:a能被2整除,0 00 11 01 1,1101,1111,,10,2) 若a能被4整除，則a能被2整除。a能被2整除。所以a能被4整除.,解：設(shè) 前提：p ?q, p 結(jié)論：q 推理的形式結(jié)構(gòu): (p ?q) ?

10、p ?q. 用等值演算判斷形式結(jié)構(gòu)是否是重言式。,p:a能被4整除,q:a能被2整除,,（3）下午馬芳或去看電影或去游泳。她沒去看電影。所以，她去游泳了。解：設(shè) 前提： 結(jié)論： 推理的形式 結(jié)構(gòu)：( ) ? . 用等值演算來判斷式子是否 為 等值式。 ( (p ? q) ??p )? q ?( ( )? (

11、 )) ? q?( ) ? q??((q ??p ) ? q? p ??q ? q?1所以 形式 結(jié)構(gòu) 為 重言式，推理 正確。,11,p:馬芳下午去看電影 .,q:馬芳下午去游泳.,p ?q, ?p,q,(p ? q) ??p,q,p ??p,q??p,q ??p,,解：設(shè)：p:下午氣溫超過30度,12,（4）若下午氣溫超過30度，則王小燕必去游泳，她就不去

12、看電影了。所以，若王小燕沒去看電影，下午氣溫必超過30度。,q:王小燕去游泳,r:王小燕去看電影,前提： ,,q??r,結(jié)論,p?q,?r?p,推理的形式結(jié)構(gòu),(p ? q) ?p,((p?q)?(q ??r)) ?(?r?p),用主析取范式判斷上式是否是重言式,((p?q)?(q ??r)) ?(?r?p),?(?p ? q)?(?q ? ?r) ?(?r?p),13,推理實(shí)例,練習(xí) ：判斷下面推理是否正確(1) 若今

13、天是1號(hào)，則明天是5號(hào). 今天是1號(hào). 所以, 明天是5號(hào). (2) 若今天是1號(hào)，則明天是5號(hào). 明天是5號(hào). 所以, 今天是1號(hào).,解 設(shè) p：今天是1號(hào)，q：明天是5號(hào). (1) 推理的形式結(jié)構(gòu):,(p?q)?p?q,用等值演算法 (p?q)?p?q ? ?((?p?q)?p)?q ? ?p??q?q ? 1 由定理3.1可知推理正確,14,推理

14、實(shí)例,(2) 推理的形式結(jié)構(gòu):,(p?q)?q?p,用主析取范式法 (p?q)?q?p ? (?p?q)?q?p ? ? ((?p?q)?q)?p ? ?q?p ? (?p??q)?(p??q)? (p??q)?(p?q) ? m0?m2?m3 結(jié)果不含m1, 故01是成假賦值，所以推理不正確,15,推理

15、定律——重言蘊(yùn)涵式,1. A ? (A?B) 附加律 2. (A?B) ? A 化簡(jiǎn)律3. (A?B)?A ? B 假言推理4. (

16、A?B)??B ? ?A 拒取式 5. (A?B)??B ? A 析取三段論6. (A?B)?(B?C) ? (A?C) 假言三段論7. (A?B)?(B?C) ? (A?C)

17、 等價(jià)三段論8. (A?B)?(C?D)?(A?C) ? (B?D) 構(gòu)造性二難 (A?B)?(?A?B) ? B 構(gòu)造性二難(特殊形式)9. (A?B)?(C?D)?( ?B??D) ? (?A??C) 破壞性二難每個(gè)等值式可產(chǎn)生兩個(gè)推理定律如, 由A???A可產(chǎn)生 A???A 和 ??A?A,16,3.2

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

19、 推出的結(jié)論是系統(tǒng)中的重言式, 稱作定理,17,自然推理系統(tǒng)P,定義3.3 自然推理系統(tǒng) P 定義如下:1. 字母表 (1) 命題變項(xiàng)符號(hào)：p, q, r, …, pi, qi, ri, … (2) 聯(lián)結(jié)詞符號(hào)：?, ?, ?, ?, ? (3) 括號(hào)與逗號(hào)：(, ), ，2. 合式公式（同定義1.6）3. 推理規(guī)則 (1) 前提引入規(guī)則 ：在證明的任何步驟都可以引入前提。 (2) 結(jié)論引入規(guī)則：在證

20、明的任何步驟得到的結(jié)論都可以作為后繼證明的前提。 (3) 置換規(guī)則：在證明的任何步驟，命題公式中的子公式都可以用等值的公式置換，得到公式序列中的又一個(gè)公式。,18,推理規(guī)則,(4) 假言推理規(guī)則 (6) 化簡(jiǎn)規(guī)則 (8) 假言三段論規(guī)則,(5) 附加規(guī)則 (7) 拒取式規(guī)則 (9) 析取三段論規(guī)則,19,推理規(guī)則,(10) 構(gòu)造性二難推理規(guī)則 (11) 破壞性二難推理規(guī)則

21、 (12) 合取引入規(guī)則,20,在自然推理系統(tǒng)P中構(gòu)造證明,設(shè)前提A1, A2,?, Ak,結(jié)論B及公式序列C1, C2,?, Cl. 如果每一個(gè)Ci(1?i?l)是某個(gè)Aj, 或者可由序列中前面的公式應(yīng)用推理規(guī)則得到, 并且Cl =B, 則稱這個(gè)公式序列是由A1, A2,?, Ak推出B的證明例 構(gòu)造下面推

22、理的證明： 若明天是星期一或星期三，我明天就有課. 若我明天有 課，今天必備課. 我今天沒備課. 所以，明天不是星期一、 也不是星期三.,21,直接證明法,例 構(gòu)造下面推理的證明： 若明天是星期一或星期三，我明天就有課. 若我明天有 課，今天必備課. 我今天沒備課. 所以，明天不是星期一、 也不是星期三. 解 (1) 設(shè)命題并符號(hào)化 設(shè)

23、 ， ，(2) 寫出證明的形式結(jié)構(gòu) 前提： 結(jié)論：(3) 證明 ① ② ③

24、 ④ ⑤ ⑥ ⑤置換,p：明天是星期一,q：明天是星期三，,r：我明天有課,s：我今天備課,(p?q)?r, r?s, ?s,?p??q,r?s,前提引入,?s,前提引入,?r,①②拒取式,(p?q)?r,前提引入,?(p?q),③④拒取式,?p??

25、q,,例3.3 在自然推理系統(tǒng)P中構(gòu)造下面的推理證明 前提： 結(jié)論：解：證明,22,p?q，q?r, p?s, ?s,r?(p?q),① ② ③ ④ ⑤ ⑥⑦

26、 ⑧,p?s,前提引入,?s,前提引入,?p,①②拒取式,p?q,前提引入,q,③④析取三段論,r,q?r,前提引入,⑤⑥假言推理,r?(p?q),⑦ ④合取引入,23,附加前提證明法,附加前提證明法 適用于結(jié)論為蘊(yùn)涵式欲證 前提：A1, A2, …, Ak 結(jié)論：C?B等價(jià)地證明 前提：A1, A2, …, Ak, C 結(jié)論：B理由

27、： (A1?A2?…?Ak)?(C?B) ? ?( A1?A2?…?Ak)?(?C?B) ? ?( A1?A2?…?Ak?C)?B ? (A1?A2?…?Ak?C)?B,24,附加前提證明法實(shí)例,例3 構(gòu)造下面推理的證明 2是素?cái)?shù)或合數(shù). 若2是素?cái)?shù)，則 是無理數(shù). 若 是無理數(shù)，則4不是素?cái)?shù). 所以，如果4是素?cái)?shù)，則2是合數(shù). 解 用附加前提證明法構(gòu)造證明

28、 (1) 設(shè) ， ， ， (2) 推理的形式結(jié)構(gòu) 前提： , , 結(jié)論：,(3) 證明 ①

29、 ② ③ ④ ⑤ ⑥ ⑦,p： 2是素?cái)?shù),q：2是合數(shù),r ： 是無理數(shù)

30、,s：4是素?cái)?shù),p?q,p?r,r??s,s?q,s,附加前提引入,p?r,前提引入,r??s,前提引入,p??s,②③假言三段論,?p,①④拒取式,p?q,前提引入,q,⑤⑥析取三段論,25,歸謬法（反證法）,歸謬法 (反證法)：將結(jié)論的否定式作為附加前提引入并推出矛盾式的證明方法稱做歸謬法。欲證 前提：A1, A2, … , Ak 結(jié)論：B做法 在前提中加入?B，推出矛盾.理由

31、 A1?A2?…?Ak?B ? ?(A1?A2?…?Ak)?B ? ?(A1?A2?…?Ak??B) ? ?(A1?A2?…?Ak??B),26,歸謬法實(shí)例,例4 前提：?(p?q)?r, r?s, ?s, p 結(jié)論：?q證明 用歸繆法 ① ②

32、 ③ ④ ⑤ ⑥ ⑦ ⑧

33、 ⑨ ?,q,結(jié)論否定引入,r?s,前提引入,?s,前提引入,?r,②③拒取式,?(p?q)?r,前提引入,?(p?q),④⑤析取三段論,?p??q,⑥置換,?p,①⑦析取三段論,p,前提引入,?p?p,⑧⑨合取,27,第三章 習(xí)題課,主要內(nèi)容推理的形式結(jié)構(gòu)判斷推理是否正確的方法 真值表法 等值演算法

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

35、掌握構(gòu)造證明的直接證明法、附加前提證明法和歸謬 法會(huì)解決實(shí)際中的簡(jiǎn)單推理問題,29,練習(xí)1：判斷推理是否正確,1. 判斷下面推理是否正確: (1) 前提：?p?q, ?q 結(jié)論：?p,解 推理的形式結(jié)構(gòu):,(?p?q)??q??p,方法一：等值演算法 (?p?q)??q??p ? ?((p?q)??q)??p ? (?p??q)?q??p ? (

36、(?p?q)?(?q?q))??p ? ?p?q,易知10是成假賦值，不是重言式，所以推理不正確.,30,練習(xí)1解答,方法二：主析取范式法， (?p?q)??q??p ??((p?q)??q)??p ??p?q ?M2 ?m0?m1?m3未含m2, 不是重言式, 推理不正確.,31,練習(xí)1解答,方法三 真值表法 不是重言式, 推理不正確,方法四 直接

37、觀察出10是成假賦值,32,練習(xí)1解答,用等值演算法 (q?r)?(p??r)?(q??p) ?(?q?r)?(?p??r)?(?q??p) ??((q??r)?(p?r))?(?q??p) ??((q?p)?(q?r)?(?r?p))?(?q??p)? ((q?p)?(q?r)?(?r?p))?(?q??p)?1推理正確,(2) 前提：q?r, p??r 結(jié)論：q??p,解 推理的形式結(jié)構(gòu)：,

38、(q?r)?(p??r)?(q??p),33,練習(xí)2：構(gòu)造證明,2. 在系統(tǒng)P中構(gòu)造下面推理的證明： 如果今天是周六，我們就到頤和園或圓明園玩. 如果頤和 園游人太多，就不去頤和園. 今天是周六，并且頤和園游 人太多. 所以, 我們?nèi)A明園或動(dòng)物園玩.,證明： (1) 設(shè) p：今天是周六，q：到頤和園玩， r：到圓明園玩，s：頤和園游人太多 t：到動(dòng)物園玩

39、 (2) 前提：p?(q?r), s??q, p, s 結(jié)論：r?t,34,練習(xí)2解答,(3) 證明： ① p?(q?r) 前提引入 ② p 前提引入 ③ q?r ①②假言推理 ④ s??q 前提引入