清華離散數(shù)學(xué)(第2版)：1.3

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

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

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

4、法歸謬法(反證法反證法)做法做法 假設(shè)假設(shè)A真并且真并且B真真, 推出矛盾推出矛盾, 即證明即證明:A B0理由理由 A B0為真為真 A B為假為假 A為假或?yàn)榧倩?B為真為真 AB為真為真例例3 若若A-B=A, 則則A B=證證 用歸謬法用歸謬法, 假設(shè)假設(shè)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歸謬法歸謬法(續(xù)續(xù))例例4 證明證明 是無理數(shù)是無理數(shù)證證 假設(shè)假設(shè) 是有理數(shù)是有理數(shù), 存在正整數(shù)存在正整數(shù)n,m, 使得使得 =m/n, 不妨設(shè)不妨設(shè)m/n為既約分?jǐn)?shù)為既約分?jǐn)?shù).

5、于是于是m=n , m2=2n2, m2是偶數(shù)是偶數(shù), 從而從而m是偶數(shù)是偶數(shù). 設(shè)設(shè)m=2k, 得得 (2k)2=2n2, n2=2k2, 這又得到這又得到n也也是偶數(shù)是偶數(shù), 與與m/n為既約分?jǐn)?shù)矛盾為既約分?jǐn)?shù)矛盾.間接證明法是歸謬法的特殊形式間接證明法是歸謬法的特殊形式: 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實(shí)例實(shí)例例例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構(gòu)造證明法構(gòu)造證明法推理推理AB, 其中其中B是存在具有某種性質(zhì)的客體是存在具有某種性質(zhì)的客體做法做法 在在A為真的條件下為真的條件下, 構(gòu)造出具有這種性質(zhì)的客體構(gòu)造出具有這種性質(zhì)的客體例例6 對于每個(gè)正整數(shù)對于每個(gè)正整數(shù)n, 存在存在n個(gè)連續(xù)的正合數(shù)個(gè)連續(xù)的正合數(shù)

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

8、的歸納基礎(chǔ)中出現(xiàn)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數(shù)學(xué)歸納法的應(yīng)用對象數(shù)學(xué)歸納法的應(yīng)用對象命題形式命題形式: 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數(shù)學(xué)歸納法的步驟數(shù)學(xué)歸納法的步驟(1)歸納基礎(chǔ)歸納基礎(chǔ) 證證P(n0)為真為真(2)歸納步驟歸納步驟 x(x n0), 假設(shè)假設(shè)P(x)為真為真, 證證P(x+1)為真為真. 稱稱“P(x)為真為真”為為歸納假設(shè)歸納假設(shè) 例例8 證明證明:對所有對所有n 1, 1+2+ +n=n(n+1)/2 證證 歸納基礎(chǔ)歸納基礎(chǔ). 當(dāng)當(dāng)n=1時(shí)時(shí), 1=1 (1+1)/2, 結(jié)論成立結(jié)論成立.歸納步驟歸納步驟. 假設(shè)對假設(shè)對n 1結(jié)論成立結(jié)論成立, 則有則有 1+2+ +n +(n+1)=n(n+1)/2 +(n+1) (歸納假設(shè)歸納假設(shè)) = (n+1)(n+

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

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

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