1、11.3 證明方法概述證明方法概述 邏輯推理的形式結構邏輯推理的形式結構 證明方法證明方法 直接證明法直接證明法 間接證明法間接證明法 歸謬法歸謬法(反證法反證法) 數學歸納法數學歸納法 窮舉法窮舉法 構造證明法構造證明法 空證明法空證明法 平凡證明法平凡證明法 舉反例舉反例命題為假的證明命題為假的證明2邏輯推理的形式結構邏輯推理的形式結構邏輯推理的形式結構邏輯推理的形式結構 A1 A2 AkB (*)當當(*)為重言式時為重言式時, 記作記作 A1 A2 AkB (*)并稱并稱推理有效推理有效或或推理正確推理正確, 又稱又稱B是是A1,A2,Ak的的有效有效(或或邏輯邏輯)結論結論; 否則稱

2、否則稱推理不正確推理不正確.ABAB(1)001(2)011(3)100(4)111(1),(2),(4)推理正確推理正確(3)推理不正確推理不正確(1)中中B是是A的邏輯結論的邏輯結論,但不但不是正確結論是正確結論; (2)和和(4)中中B既既是邏輯結論是邏輯結論,又是正確結論又是正確結論.3邏輯推理的證明邏輯推理的證明推理的常見形式推理的常見形式:(1)若若A, 則則B AB (2)A當且僅當當且僅當B AB(3)證明證明B B都可歸結為形式都可歸結為形式(1)4直接證明法直接證明法做法做法 證明證明“若若A為真為真, 則則B為真為真” 理由理由 “若若A為真為真, 則則B為真為真” “A

3、B為真為真”例例1 若若n是奇數是奇數, 則則n2也是奇數也是奇數.證證 存在存在k N, n=2k+1. 于是于是, n2 = (2k+1)2 = 2(2k2+2k)+1得證得證n2是奇數是奇數.5間接證明法間接證明法做法做法 證明證明“ B A”為真為真理由理由 “AB為真為真” “ B A為真為真”例例2 若若n2是奇數是奇數, 則則n也是奇數也是奇數.證證 用間接證明法用間接證明法. 只要證只要證:若若n是偶數是偶數, 則則n2也是偶數也是偶數.假設假設n是偶數是偶數, 則存在則存在k N, n=2k. 于是于是, n2 = (2k)2 = 2(2k2)得證得證n2是偶數是偶數.6歸謬

4、法歸謬法(反證法反證法)做法做法 假設假設A真并且真并且B真真, 推出矛盾推出矛盾, 即證明即證明:A B0理由理由 A B0為真為真 A B為假為假 A為假或為假或 B為真為真 AB為真為真例例3 若若A-B=A, 則則A B=證證 用歸謬法用歸謬法, 假設假設A B, 則存在則存在x,使得使得 x A B x A x B x A-B x B (A-B=A) x A x B x B x B x B, 矛盾矛盾7歸謬法歸謬法(續續)例例4 證明證明 是無理數是無理數證證 假設假設 是有理數是有理數, 存在正整數存在正整數n,m, 使得使得 =m/n, 不妨設不妨設m/n為既約分數為既約分數.

5、于是于是m=n , m2=2n2, m2是偶數是偶數, 從而從而m是偶數是偶數. 設設m=2k, 得得 (2k)2=2n2, n2=2k2, 這又得到這又得到n也也是偶數是偶數, 與與m/n為既約分數矛盾為既約分數矛盾.間接證明法是歸謬法的特殊形式間接證明法是歸謬法的特殊形式: B A, A A022228窮舉法窮舉法(分情況證明法分情況證明法)推理推理AB, 其中其中A= A1 A2 Ak.做法做法 證明證明A1B, A2B, AkB 均為真均為真理由理由 A1 A2 AkB (A1 A2 Ak) B (A1 A2 Ak) B (A1 B) (A2 B) (Ak B) (A1B) (A2B)

6、 (AkB) 9實例實例例例5 證明證明:max(a, max(b,c)=max(max(a,b),c)證證 情況情況u=max(b,c)max(a,u)v=max(a,b)max(v,c)a b cc c b ca c b b b b b b a cc cacb c acaaac a b b b b b c b a b aaa10構造證明法構造證明法推理推理AB, 其中其中B是存在具有某種性質的客體是存在具有某種性質的客體做法做法 在在A為真的條件下為真的條件下, 構造出具有這種性質的客體構造出具有這種性質的客體例例6 對于每個正整數對于每個正整數n, 存在存在n個連續的正合數個連續的正合數

7、.證證 令令x=(n+1)! 則則 x+2, x+3, x+n+1是是n個連續的正合數個連續的正合數: i | x+i, i=2,3,n+111空證明法與平凡證明法空證明法與平凡證明法空證明法空證明法(前件假證明法前件假證明法)做法做法 證明證明“A恒為假恒為假”理由理由 “A恒為假恒為假” “AB為真為真”例如例如, “是任何集合的子集是任何集合的子集”(定理定理1.1)的證明的證明平凡證明法平凡證明法(后件真證明法后件真證明法)做法做法 證明證明“B恒為真恒為真”理由理由 “B恒為真恒為真” “AB為真為真”例如例如, 若若a b, 則則a0 b0.常在歸納證明的歸納基礎中出現常在歸納證明

8、的歸納基礎中出現12命題為假的證明命題為假的證明舉反例舉反例例例7 判斷下述命題是真是假判斷下述命題是真是假: 若若A B=A C, 則則B=C. 解解 反例反例: 取取A=a,b, B=a,b,c, C=a,b,d, 有有 A B=A C = a,b但但B C, 故命題為假故命題為假.13數學歸納法的應用對象數學歸納法的應用對象命題形式命題形式: x(x N x n0), P(x)命題的提出命題的提出歸納與猜想歸納與猜想例如例如, 觀察觀察11+21+2+31+2+3+4 =1 (1+1)/2=3=2 (2+1)/2=6=3 (3+1)/2=10=4 (4+1)/2猜想猜想 對所有對所有n

9、1, 1+2+ +n=n(n+1)/2 14數學歸納法的步驟數學歸納法的步驟(1)歸納基礎歸納基礎 證證P(n0)為真為真(2)歸納步驟歸納步驟 x(x n0), 假設假設P(x)為真為真, 證證P(x+1)為真為真. 稱稱“P(x)為真為真”為為歸納假設歸納假設 例例8 證明證明:對所有對所有n 1, 1+2+ +n=n(n+1)/2 證證 歸納基礎歸納基礎. 當當n=1時時, 1=1 (1+1)/2, 結論成立結論成立.歸納步驟歸納步驟. 假設對假設對n 1結論成立結論成立, 則有則有 1+2+ +n +(n+1)=n(n+1)/2 +(n+1) (歸納假設歸納假設) = (n+1)(n+

10、2)/2得證當得證當n+1時結論也成立時結論也成立.15數學歸納法的步驟數學歸納法的步驟(續續)注意注意: 歸納基礎與歸納步驟兩者缺一不可歸納基礎與歸納步驟兩者缺一不可反例反例1 命題命題 n 1, 21+22+ 2n= 2n+1證證 假設假設 n 1, 結論成立結論成立, 則則 21+22+ 2n+2n+1= 2n+1+2n+1 = 2n+2對對n+1結論成立結論成立, 故命題成立故命題成立. 16數學歸納法的步驟數學歸納法的步驟(續續)反例反例2 觀察觀察2n-1-1 是否被是否被n整除整除n2n-1-1整除整除n2n-1-1整除整除33Y10511N47N111023Y515Y12204

11、7N631N134095Y763Y148191N8127N1516383N9255N1632767N17反例反例2(續續)由上表可能會提出下述命題由上表可能會提出下述命題命題命題 設設n 3, n是素數的充分必要條件是是素數的充分必要條件是2n-1-1被被n整除整除.但此命題不真但此命題不真. 561=3 11 17是合數是合數, 而而2560-1能被能被561整除整除.n2n-1-1整除整除n2n-1-1整除整除1765535Y211048575N18131071N222097151N19262143Y234194303Y20524287N248388607N18第二數學歸納法第二數學歸納法

12、歸納基礎歸納基礎 證明證明P(n0)為真為真歸納步驟歸納步驟 x(x n0), 假設假設P(n0),P(n0+1),P(x)為真為真, 證證P(x+1)為真為真.歸納假設歸納假設 y(n0 y x), P(y)為真為真例例9 任何大于等于任何大于等于2的整數均可表成素數的乘積的整數均可表成素數的乘積證證 歸納基礎歸納基礎. 對于對于2, 結論顯然成立結論顯然成立.歸納步驟歸納步驟. 假設對所有的假設對所有的k(2 k n)結論成立結論成立, 要證結論要證結論對對n+1也成立也成立. 若若n+1是素數是素數, 則結論成立則結論成立; 否則否則n+1=ab,2 a,bn. 由歸納假設由歸納假設, a,b均可表成素數的乘積均可表成素數的乘積, 從而從而n+1也可表成素數的乘積也可表成素數的乘積. 得證結論對得證結論對n+1成立成立.19注釋注釋歸納基礎歸納基礎 證證P(n0),P(n0+1),P(n1)為真為真, n0 n1.例例10 可用可用4分和分和5分郵票組成分郵票組成n分郵資分郵資, n 12.證證 歸納基礎歸納基礎. 12=3 4, 13=2 4