《離散數(shù)學(xué)課件》命題邏輯3

1、1/66,上堂課的內(nèi)容、重點(diǎn)與難點(diǎn),合(析)取式與成真(假)解釋求解范式、主范式,等價(jià)公式的熟練運(yùn)用等價(jià)變換法、解釋法、真值表法的靈活運(yùn)用,合取式、析取式析取范式、合取范式極小項(xiàng)、極大項(xiàng) 主析取范式、主合取范式,第六講 推理理論,1.有效結(jié)論 2.論證方法 3.構(gòu)造證明法4.間接證法 （歸謬法）5.間接證法 （附加前提證法）,2,3/66,邏輯推理,演繹推理（數(shù)學(xué)家使用）歸納推理（科學(xué)家使用） 溯因推

2、理（偵探使用）,從真的前提出發(fā)，得到的結(jié)論只能夠要求它與前提是協(xié)調(diào)的，但不一定是真的。,從前提出發(fā)，通過(guò)推導(dǎo)即“演繹”，得出結(jié)論的過(guò)程。前提和結(jié)論之間有可推導(dǎo)性關(guān)系：前提的真蘊(yùn)涵結(jié)論的真。,生成假設(shè)來(lái)解釋觀察或結(jié)論。,若下雨，則草地會(huì)變濕。因?yàn)榻裉煜掠炅耍越裉觳莸厥菨竦摹?每次下雨，草地都是濕的。因此若明天下雨，草地就會(huì)變濕。,若下雨，草地會(huì)變濕。因?yàn)椴莸厥菨竦?，所以曾下過(guò)雨。,一個(gè)土耳其商人想找一個(gè)十分聰明的助手協(xié)助他經(jīng)商。有兩

3、人前來(lái)應(yīng)聘，這個(gè)商人為了試試哪個(gè)更聰明，就把兩個(gè)人帶進(jìn)了一間漆黑的屋子里。他打開(kāi)燈后說(shuō)：“這張桌子上有5頂帽子，2頂紅色的，3頂黑色的，現(xiàn)在，我把燈關(guān)掉，并把帽子擺放的位子弄亂，然后，我們?nèi)嗣咳嗣豁斆弊哟髟谧约旱念^上。在我開(kāi)燈后，請(qǐng)你們盡快說(shuō)出自己頭上帽子的顏色。” 說(shuō)完后，商人將燈關(guān)掉，然后三人戴好帽子，同時(shí)，商人將剩余的兩頂帽子藏了起來(lái)，接著開(kāi)燈。這時(shí)，應(yīng)試者看到商人頭上的是紅帽子，其中一人便喊到：“我戴的是黑帽子

4、?！?4/66,邏輯推理,請(qǐng)問(wèn)這個(gè)人說(shuō)的對(duì)嗎？他是怎么推導(dǎo)的？ 該問(wèn)題實(shí)際就是由一些諸如“商人戴的是紅帽子”這樣的前提能否推出“猜出答案的應(yīng)試者戴的是黑帽子”這樣的結(jié)論。這需要經(jīng)歷如下過(guò)程：1、什么是前提？有哪些前提？2、結(jié)論是什么？3、根據(jù)什么進(jìn)行推理？4、怎么推理？,5/66,6/66,例 判斷下面兩個(gè)推理是否正確:,(1) 如果今天是星期二, 今天有數(shù)學(xué)課。 今天是星期二， 所以今天有

5、數(shù)學(xué)課。 (2) 如果今天是星期二, 今天有數(shù)學(xué)課。 今天不是星期二， 所以今天沒(méi)有數(shù)學(xué)課。,第二章 命題演算的推理理論,7/66,推理是否正確？,記： P表示今天是星期二， Q表示今天有數(shù)學(xué)課。(1) 如果今天是星期二, 今天有數(shù)學(xué)課。 今天是星期二，所以今天有數(shù)學(xué)課。((P?Q)?P)?Q (2) 如果今天是星期二, 今天有數(shù)學(xué)課。 今天不是星期二，

6、所以今天沒(méi)有數(shù)學(xué)課。 ((P?Q)??P)??Q,8/66,從真值表看推理是否正確：,P Q ((P?Q)?P)?Q ((P?Q)??P)??QT T T TT F T

7、 TF T T FF F T T,,,,永真公式三段論,非永真,9/66,1、有效推理,若有重言式則稱由前提A1，…， An 推出結(jié)論B的 推理有效，并稱B是 A1，A2， …， An

8、 的邏輯結(jié)論，記為： A1，A2， …， An ┣ B或 A1，A2， …， An ? B,(A1 ? A2 ? … ? An) ? B,10/66,“A1, A2, …, Ak 推B” 的推理正確 當(dāng)且僅當(dāng) A1ÙA2Ù…ÙAk®B為重言式.推理的形式結(jié)構(gòu): A1ÙA2Ù…&

9、#217;Ak®B 或 前提： A1, A2, … , Ak 結(jié)論： B 若推理正確，則記作：A1ÙA2Ù…ÙAkÞB.,判斷推理是否正確的方法:真值表法等值演算法主析取范式法構(gòu)造證明法,11/66,前提和結(jié)論間具有可推導(dǎo)性的形式關(guān)系,大前提：如果 1+1=3，則雪是黑的。 小前提：1+1=3。 結(jié) 論 ：雪是黑的。,

10、該推理過(guò)程正確,但不意味著前提與結(jié)論正確,解：設(shè)Ｐ：天下雨；Ｑ：小王去跑步。 前提：Ｐ→?Ｑ，Ｐ。 結(jié)論：?Ｑ 。 推理的形式結(jié)構(gòu)為： ((Ｐ→?Ｑ)∧Ｐ)??Ｑ………（*）（1）真值表法,12,例１ 判斷下面的推理是否正確： 如果天下雨，小王就不去跑步。今天天下雨，所以小王沒(méi)去跑步。,2. 論證方法,（3）主析取范式法 ((P→?Q)∧P

11、)→?Q ?((?P∨?Q)∧P)→?Q ?(P∧Q)∨?P∨?Q ?(P∧Q)∨(?P∧(Q∨?Q))∨((P∨?P)∧?Q) ? (P∧Q)∨(?P∧Q)∨(?P∧?Q)∨(P∧?Q)∨(?P∧?Q) ? (?P∧?Q)∨(?P∧Q)∨(P∧?Q)∨(P∧Q) ? ∑0,1,2,3,13,（2）等值演算法 ((P→?Q)∧P)→?Q ?((?P∨?Q)∧P)→?Q ?((P∧Q)∨?P)

12、∨?Q ?(P∨?P∨?Q)∧(Q∨?P∨?Q) ? 1∧1?1,14,直接證法 直接證法就是由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)或蘊(yùn)含公式，推演得出有效結(jié)論。常用的推理規(guī)則：Ｐ規(guī)則：在推理的任何步驟都可以引入前提。Ｔ規(guī)則：在推理的過(guò)程中，如果前面的步驟中有一個(gè)或多個(gè)命題公式蘊(yùn)含命題公式Ｓ，則可以把公式Ｓ引入推導(dǎo)過(guò)程。,3、構(gòu)造證明法,重要的推理定律 A Þ (AÚB

13、) 附加律 (AÙB) Þ A 化簡(jiǎn)律 (A®B)ÙA Þ B 假言推理 (A®B)ÙØB Þ 

14、16;A 拒取式 (AÚB)ÙØB Þ A 析取三段論 (A®B)Ù(B®C) Þ (A®C) 假言三段論 (A«B)Ù(B«C) Þ (A&

15、#171;C) 等價(jià)三段 (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 構(gòu)造性二難,15,推理定律——重言蘊(yùn)涵式,推理定律 (續(xù)),(A®B)Ù(ØA®B)Ù(AÚØA) Þ B

16、 構(gòu)造性二難（特殊形式）(A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC) 破壞性二難,16,說(shuō)明： A, B, C為元語(yǔ)言符號(hào)若某推理符合某條推理定律，則它自然是正確的AÛB產(chǎn)生兩條推理定律

17、: A Þ B, B Þ A,17,推理規(guī)則,18,例1 構(gòu)造下面推理的證明： 若明天是星期一或星期三，我就有課. 若有課，今天必備課. 我今天下午沒(méi)備課. 所以，明天不是星期一和星期三. 解  設(shè) p：明天是星期一，q：明天是星期三， r：我有課，s：我備課形式結(jié)構(gòu)為 前提：(pÚq)®r, r®s, Ø

18、s 結(jié)論：ØpÙØq,19,直接證明法 (續(xù)),證明 ① r®s 前提引入 ② Øs 前提引入 ③ Ør ①②拒取式 ④ (pÚq)®r 前提引入 ⑤ Ø(pÚq

19、) ③④拒取式 ⑥ ØpÙØq ⑤置換,20,前提：(pÚq)®r, r®s, Øs結(jié)論：ØpÙØq,21,例2 找出下列推理的有效結(jié)論。 如果我考試通過(guò)了，那么我很快樂(lè)。如果我快樂(lè)。那么陽(yáng)光燦爛?，F(xiàn)在陽(yáng)光不燦爛且天很暖。因此我考試沒(méi)通過(guò)。 解 設(shè)

20、p： 我考試通過(guò)了， q： 我很快樂(lè)， r： 陽(yáng)光燦爛， s： 天很暖。 前提：p→q， q→r， Ø r Ù s 結(jié)論： ? p,22,前提：p→q， q→r， Ø r Ù s結(jié)論： ? p（1） p→q 前提引入（2） q→r 前提引入（3）

21、 p→r （1）（2）假言三段論（4） ? r∧s 前提引入（5） ? r （4）化簡(jiǎn)（6） ? p （5）（3）拒取式 所以有效結(jié)論是： 我考試沒(méi)通過(guò)。,23,例3 證明Ｒ∨Ｓ是前題Ｃ∨Ｄ，Ｃ→Ｒ，Ｄ→Ｓ的有效結(jié)論，即證明： (C∨D)∧(C→R)∧(D→S)?(R∨S)。

22、證明：① C∨D 前提引入 ② ?C→D 置換 ③ D→S 前提引入 ④ ?C→S ②③ ⑤ C→R 前 提 ⑥ ?R→?C ⑤ ⑦ ?R→S ④⑥ ⑧ R∨S 置換,24,4、間接證法,（1）附加前提證明法,欲證明

23、 前提：A1, A2, …, Ak 結(jié)論：C®B等價(jià)地證明 前提：A1, A2, …, Ak, C 結(jié)論：B 理由： (A1ÙA2Ù…ÙAk)®(C®B) Û Ø( A1ÙA2Ù…ÙAk)Ú(ØCÚB)

24、 Û Ø( A1ÙA2Ù…ÙAkÙC)ÚB Û (A1ÙA2Ù…ÙAkÙC)®B,25,例 構(gòu)造下面推理的證明: 2是素?cái)?shù)或合數(shù). 若2是素?cái)?shù)，則 是無(wú)理數(shù). 若 是無(wú)理數(shù)，則4不是素?cái)?shù). 所以，如果4是素?cái)?shù)，則2是合

25、數(shù). 用附加前提證明法構(gòu)造證明解 設(shè) p：2是素?cái)?shù)，q：2是合數(shù)， r： 是無(wú)理數(shù)，s：4是素?cái)?shù)形式結(jié)構(gòu) 前提：pÚq, p®r, r®Øs 結(jié)論：s®q,26,證明 ① s 附加前提引入 ② p®r 前提引入 ③ r

26、74;Øs 前提引入 ④ p®Øs ②③假言三段論 ⑤ Øp ①④拒取式 ⑥ pÚq 前提引入 ⑦ q ⑤⑥析取三段論,前提：pÚq, p®r, r®Øs

27、結(jié)論：s®q,27,（2）歸謬法（反證法）,欲證明 前提：A1, A2, … , Ak 結(jié)論：B將ØB加入前提，若推出矛盾，則得證推理正確.理由: A1ÙA2Ù…ÙAk®B Û Ø(A1ÙA2Ù…ÙAk)ÚB Û Ø(A1&#

28、217;A2Ù…ÙAkÙØB)括號(hào)內(nèi)部為矛盾式當(dāng)且僅當(dāng) (A1ÙA2Ù…ÙAk®B)為重言式 .,28,例 構(gòu)造下面推理的證明 前提：Ø(pÙq)Úr, r®s, Øs, p 結(jié)論：Øq證明（用歸繆法） ① q 結(jié)論否定引入

29、 ⑩ ØpÙp ⑧⑨合取 ② r®s 前提引入 ③ Øs 前提引入 ④ Ør ②③拒取式 ⑤ Ø(pÙq)Úr 前提引入 ⑥ Ø(pÙq) ④⑤析取三段論 ⑦ Ø

30、;pÚØq ⑥置換 ⑧ Øp ①⑦析取三段論 ⑨ p 前提引入,證：① A→B 前提 ② A 否定結(jié)論 ③ B ①② ④ ?(B∨C) 前提 ⑤ ?B∧?C

31、 ③置換 ⑥ ?B ④ ⑦ B∧?B （矛盾）,29,練習(xí)1 證明 ?(B∨C)∧(A→B) ? ? A,6、課內(nèi)練習(xí),證：⑴ ?(A→?C) 否定結(jié)論 ⑵ A∧C 1置換 ⑶ A 2化簡(jiǎn) ⑷

32、C 2化簡(jiǎn) ⑸ ?A∨B 前提 ⑹ B 3、5 ⑺ C→?B 前提 ⑻ ?B 4、7 ⑼ B∧?B (矛盾) 6、8,30,練習(xí)2 證明 ? A∨B，C→? B ? A→? C,31,練習(xí)2 證明 ? A∨B，C→? B ? A→

33、? C,證: (1) A 附加前提引入 (2) ?A∨B 前提 (3) B 1、2 (4) C→?B 前提 (5) ?C 3、4,本節(jié)課小結(jié) 推理理論,32,1、有效結(jié)論 A→B永真則為A ?B2、推理規(guī)則