1、1,1.5 推理規(guī)則和證明方法,講授重點：推理規(guī)則，直接證明方法與CP規(guī)則 講授難點：直接證明方法，CP規(guī)則與反證法,2,什么是推理？,1.推理和推理規(guī)則,推理:從前提推出結論的思維過程。 前提:指已知的命題公式。 結論:從前提出發(fā)，應用推理規(guī)則推出的命題公式。,本節(jié)內容：從邏輯推理的角度來理解命題演算,前提 結論,推理規(guī)則,推理,3,推理的例子：設x屬于實數(shù), P: x是偶數(shù), Q: x2是偶數(shù)。,例1. 如果x是偶數(shù), 則x2是偶數(shù)。 x是偶數(shù)。 x2是偶數(shù)。,例3. 如果x是偶數(shù), 則x2是偶數(shù)。 x不是偶數(shù)。 x2不是偶數(shù)。,例2. 如果x是偶數(shù), 則x2是偶數(shù)。 x2是偶數(shù)。 x是偶

2、數(shù)。,例4. 如果x是偶數(shù), 則x2是偶數(shù)。 x2不是偶數(shù)。 x不是偶數(shù)。,前提,- 結論,四個例子的推理是否正確？ 所用依據(jù)是什么？,4,1、推理和推理規(guī)則,推理規(guī)則：正確推理的依據(jù)。 任何一條永真蘊含式都可以作為一條推理規(guī)則。 例：析取三段論： 如果，P：他在釣魚，Q：他在下棋 前提：他在釣魚或下棋； 他不在釣魚 結論：所以他在下棋,5,定義1：若H1H2 Hn C, 則稱C是H1, H2, , Hn的有效結論。 特別若A B, 則稱B是A的有效結論，或從A推出B。,1、推理和推理規(guī)則,注意： 不考慮前提的真假，推理正確結論為真。 結論的真假 取決于 前提H1H2 Hn的真假。 前提為真，

3、則結論為真； 前提為假，則結論可真可假。 因此，定義中只說C 是H1, H2, , Hn 的有效結論而不說是正確結論?！坝行А笔侵附Y論的推出合乎推理規(guī)則。,6,有效結論,如Q是PQ，P 的一個有效結論。 即 證P (PQ) 永真蘊含Q 也就是要證： P (PQ) Q 是重言式. 設 P (PQ) 取值為真，則 P為真，且 PQ為真， 故 Q為真 故P (PQ) Q 是重言式.,7,如： Q是P，(P Q) 的有效結論。 即 P(P Q) Q 是一個永真式。,8,推理的形式結構,形式(1) H1H2HnC 形式(2) 前提: H1, H2, , Hn 結論: C 推理正確記作 H1H2HnC,注

4、1. 與的區(qū)別,9,推理的形式結構,形式(1) H1H2HnC 形式(2) 前提: H1, H2, , Hn 結論: C 推理正確記作 H1H2HnC,對于實際中給出的推理: 將推理中的（簡單）命題符號化 寫出前提和結論 判斷該推理是否正確 正確：給出一個證明序列 不正確：給出反例,10,常用的推理規(guī)則 1) 恒等式(E1E24) 2) 永真蘊含式(I1I8,表1.5-1) 3) 替換規(guī)則，代入規(guī)則 4) P規(guī)則和T規(guī)則 P規(guī)則：(前提引入) 在推導的任何步驟上，都可以引入前提。 T規(guī)則：(結論引用) 在推導任何步驟上所得結論都可以作為后繼證明的前提。,1、推理和推理規(guī)則,11,永真蘊含式,1

5、2,13,推理規(guī)則,14,例1：考慮下述論證: 1. 如果這里有球賽, 則通行是困難的。 2. 如果他們按時到達, 則通行是不困難的。 3. 他們按時到達了。 4. 所以這里沒有球賽。 前 3 個斷言是前提, 最后1個斷言是結論, 要求我們從前提推出結論。,設P: 這里有球賽, Q: 通行是困難的, R: 他們按時到達。 即證 PQ，R Q，R P,運用推理規(guī)則形式化證明,15,證： 步驟 斷言(真) 根 據(jù) （1） R P （2） R Q P （3） Q T,(1),(2),I3 （4） PQ P （5） P T,(3),(4),I4,即證 PQ，R Q，R P,16,1.5.2 證明方法定

6、理常見的形式是“P當且僅當Q”，“如果P，那么Q”。 而前者又相當于PQ并且QP， 所以歸根結底，定理的主要形式是PQ。至于其它形式，諸如： P形式，只需證明P是假; PQ形式，只需證明P、Q俱真; PQ形式，可轉化為 PQ形式。我們主要從策略意義上說明如何證明PQ形式的命題，具體的技巧，仍需通過例題來學習。,17,1). 無義證明法 證明 P Q為真，只需證明P為假。 2). 平凡證明法 證明 P Q為真，只需證明Q為真。 無義證明法和平凡證明法應用的次數(shù)較少, 但 對有限的或特殊的情況, 它們常常是重要的。,3. 證明方法,（PQ）,18,3. 證明方法,3).直接證明法假設P是真，如果能

7、推得Q是真，則PQ是真 H1H2 Hn C，由前提利用推理規(guī)則直接推出C。,例2：證明 CD, CR, DS RS,19,證： (1) CD P (2) ( C) D T,(1),E1 (3) C D T,(2),E14 (4) D S P (5) C S T,(3),(4),I6 (6) C R P (7) RC T,(6),E24 (8) R S T,(5),(7),I6 (9) ( R)S T,(8),E14 (10) R S T, (9), E1,例2：證明 CD, CR, DS RS,20,實例,例 構造推理的證明: 若明天是星期一或星期三, 我就有課. 若有課, 今天必須備課. 我

8、今天下午沒備課. 所以, 明天不是星期一和星期三. 解 設 P:明天是星期一, Q:明天是星期三， R:我有課， S:我備課 前提: (PQ)R, RS, S 結論: PQ,21,實例(續(xù)),前提: (PQ)R, RS, S 結論: PQ 證明 RS 前提引入 S 前提引入 R 拒取式 (PQ)R 前提引入 (PQ) 拒取式 PQ 置換 結論有效, 即明天不是星期一和星期三,22,4). 間接證明法-（對原命題的逆否命題進行證明） 證P Q只需證 Q P 因為P Q 也即 PQ永真 ， Q P永真 所以 Q P,3. 證明方法,23,(2) 一個完全數(shù)是一個整數(shù)，它等于它的所有因子(除本身外)

9、的和。 如 6 是一個完全數(shù)，因為 6=1+2+3，同樣 28 也是。定理: 一個完全數(shù)不是一個質數(shù)。證 其逆反如下: 一個質數(shù)不是一個完全數(shù)。 假設P是一質數(shù)，那么P2 并且P恰有兩個因子 1 和P，所以小于P的所有因子的總和是 1。 這得出P不是一個完全數(shù)。這是間接證明法。,24,5). (H1H2 Hn) Q形式命題的證明 H1H2 Hn Q iff H1H2 Hn Q 是重言式 iff (H1H2 Hn )Q 是重言式 iff H1 H2 Hn Q 是重言式 iff (Q H1) (Q H2) (Q Hn)是重言式 iff ( Q H1) ( Q H2) ( Q Hn) 是重言式 若至

10、少有一個i，使得 使 Q Hi, 則原恒等式成立。,25,6. CP規(guī)則（演繹定理） P1P2 Pn ( PQ)形式命題的證明 證： P1P2 Pn PQ 因為 P1P2 Pn PQ iff P1P2 Pn ( PQ) 永真 iff (P1P2 Pn )( P Q) 永真 iff P1 P2 Pn P Q 永真 iff (P1 P2 Pn P ) Q 永真 iff (P1P2 Pn P) Q 永真 iff P1P2 Pn P Q 永真,6. 證明方法,26,CP規(guī)則（演繹定理）,前提: P1, P2, , Pn 結論: PQ,欲證明,等價地證明,前提: P1, P2, , Pn, P(附加前提

11、) 結論: Q,27,例 1.5-7 如果A參加球賽，則B或C也將參加球賽。 如果B參加球賽，則A不參加球賽。 如果D參加球賽，則C不參加球賽。 所以，A若參加球賽，則D不參加球賽。解 設A: A參加球賽，B: B參加球賽，C: C參加球賽，D: D參加球賽。要證明的是A D可從ABC，B A，D C 推出。,28,29,利用CP規(guī)則證明以下例題 練習：證A (B C)， D A，B D C 證： (1) D P（附加前提） (2) D A P (3) A T,(1),(2),I5 (4) A (B C) P (5) B C T,(3),(4),I3 (6) B P (7) C T,(5),(

12、6),I3 (8) D C CP規(guī)則,30,7.分情況證明 證明 P1 P2 Pn Q ， 只需證明對每一i，Pi Q成立。,3. 證明方法,因為 P1 P2 Pn Q iff P1 P2 Pn Q 永真 iff (P1 P2 Pn) Q 永真 iff (P1 P2 Pn) Q 永真 iff ( P1 Q) ( P2 Q) ( Pn Q)永真 iff (P1 Q ) (P2 Q ) (Pn Q ) 永真,31,例 1.5-8 試證記作“”的二元運算“max”是可結合的，即對任何整數(shù)a、b和c，(ab)c=a(bc)。證 對任意 3 整數(shù)a、b、c，下列 6 種情況之一必須成立: abc，acb

13、，bac，bca，cab或cba。情況 1: abc，那么 (ab)c=ac=a a(bc)=ab=a所以 (ab)c=a(bc)其它情況類似可證。,32,8. 反證法（又稱歸謬法、矛盾法） 定義：設公式H1, H2, , Hm中的原子命題變元是P1, P2, , Pn, 如果給P1, P2, , Pn以某一 指派, 能使H1H2 Hm的真值為真, 則稱命題公式集合H1, H2, , Hm是一致的, 否則稱為非一致的。 這個定義也可這樣敘述: 若H1H2Hm RR, 則H1, H2, , Hm是非一致的, 否則是一致的。,3. 證明方法,33,證明：H1H2Hn C RR iff H1H2Hn

14、 C 永假 (1) 而H1, H2, , Hn是一致的， 所以存在一種指派使得H1H2Hn 為真 (2) 由(1),(2)知存在一種指派使得 C 為假，即C為真。 由肯定前件法可得H1H2 Hn C 。,定理：設H1, H2, , Hn是一致的, C是一命題公式, 如果H1, H2, , Hn, C非一致, 則能從H1 , H2, , Hn推出C，即H1H2 Hn C 。,34,歸謬法(反證法),欲證明 前提：A1, A2, , An 結論：B 將B加入前提, 若推出矛盾, 則得證推理正確.,35,例4: P Q R, R S, S P Q 證： (1) ( P Q) P,假設前提 (2) P Q T,(1),E10 (3) P Q T,(1), E1 (4) P Q R P (5) R T,(3),(4),I3 (6) R S P (7) S T ,(5),(6),I5 (8) S P (9) S S T,(7)