《離散數學課件》命題邏輯3

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

2、理（偵探使用）,從真的前提出發(fā)，得到的結論只能夠要求它與前提是協(xié)調的，但不一定是真的。,從前提出發(fā)，通過推導即“演繹”，得出結論的過程。前提和結論之間有可推導性關系：前提的真蘊涵結論的真。,生成假設來解釋觀察或結論。,若下雨，則草地會變濕。因為今天下雨了，所以今天草地是濕的。,每次下雨，草地都是濕的。因此若明天下雨，草地就會變濕。,若下雨，草地會變濕。因為草地是濕的，所以曾下過雨。,一個土耳其商人想找一個十分聰明的助手協(xié)助他經商。有兩

3、人前來應聘，這個商人為了試試哪個更聰明，就把兩個人帶進了一間漆黑的屋子里。他打開燈后說：“這張桌子上有5頂帽子，2頂紅色的，3頂黑色的，現在，我把燈關掉，并把帽子擺放的位子弄亂，然后，我們三人每人摸一頂帽子戴在自己的頭上。在我開燈后，請你們盡快說出自己頭上帽子的顏色?！?說完后，商人將燈關掉，然后三人戴好帽子，同時，商人將剩余的兩頂帽子藏了起來，接著開燈。這時，應試者看到商人頭上的是紅帽子，其中一人便喊到：“我戴的是黑帽子

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

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

6、所以今天沒有數學課。 ((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 推出結論B的 推理有效，并稱B是 A1，A2， …， An

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

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

10、該推理過程正確,但不意味著前提與結論正確,解：設Ｐ：天下雨；Ｑ：小王去跑步。 前提：Ｐ→?Ｑ，Ｐ。 結論：?Ｑ 。 推理的形式結構為： ((Ｐ→?Ｑ)∧Ｐ)??Ｑ………（*）（1）真值表法,12,例１ 判斷下面的推理是否正確： 如果天下雨，小王就不去跑步。今天天下雨，所以小王沒去跑步。,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,直接證法 直接證法就是由一組前提，利用一些公認的推理規(guī)則，根據已知的等價或蘊含公式，推演得出有效結論。常用的推理規(guī)則：Ｐ規(guī)則：在推理的任何步驟都可以引入前提。Ｔ規(guī)則：在推理的過程中，如果前面的步驟中有一個或多個命題公式蘊含命題公式Ｓ，則可以把公式Ｓ引入推導過程。,3、構造證明法,重要的推理定律 A Þ (AÚB

13、) 附加律 (AÙB) Þ A 化簡律 (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) 等價三段 (A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 構造性二難,15,推理定律——重言蘊涵式,推理定律 (續(xù)),(A®B)Ù(ØA®B)Ù(AÚØA) Þ B

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

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

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

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

20、p： 我考試通過了， q： 我很快樂， r： 陽光燦爛， s： 天很暖。 前提：p→q， q→r， Ø r Ù s 結論： ? p,22,前提：p→q， q→r， Ø r Ù s結論： ? p（1） p→q 前提引入（2） q→r 前提引入（3）

21、 p→r （1）（2）假言三段論（4） ? r∧s 前提引入（5） ? r （4）化簡（6） ? p （5）（3）拒取式 所以有效結論是： 我考試沒通過。,23,例3 證明Ｒ∨Ｓ是前題Ｃ∨Ｄ，Ｃ→Ｒ，Ｄ→Ｓ的有效結論，即證明： (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 結論：C®B等價地證明 前提：A1, A2, …, Ak, C 結論：B 理由： (A1ÙA2Ù…ÙAk)®(C®B) Û Ø( A1ÙA2Ù…ÙAk)Ú(ØCÚB)

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

25、數. 用附加前提證明法構造證明解 設 p：2是素數，q：2是合數， r： 是無理數，s：4是素數形式結構 前提：pÚq, p®r, r®Øs 結論：s®q,26,證明 ① s 附加前提引入 ② p®r 前提引入 ③ r

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

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

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

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

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

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

32、C 2化簡 ⑸ ?A∨B 前提 ⑹ B 3、5 ⑺ C→?B 前提 ⑻ ?B 4、7 ⑼ B∧?B (矛盾) 6、8,30,練習2 證明 ? A∨B，C→? B ? A→? C,31,練習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é)課小結 推理理論,32,1、有效結論 A→B永真則為A ?B2、推理規(guī)則