離散數(shù)學證明方法

1、證明方法離散數(shù)學邏輯和證明大學計算機科學與技術(shù)系內(nèi)容提要引言直接證明反證法分情形證明等價性證明存在性證明唯一性證明尋找反例數(shù)學與猜想引言定理（theorem）能夠被證明為真的陳述，通常是比較重要的陳述。證明（proof）表明陳述（定理）為真的有效論證。定理證明中可以使用的陳述：（當前）定理的前提已經(jīng)證明的定理（推論、命題、引理）公理（假定）術(shù)語的定義猜想（conjecture）引言定理的陳述（舉例）如果xy，其中x和y是正實數(shù)，那么 x2y2。如何理解對所有正實數(shù)x和y，如果xy，那么 x2y2。xy(xy) (x2y2)如何證明定理的陳述為：x (P(x) Q(x)先證明，對論域中的任一元素

2、c， P(c) Q(c)再使用全稱生成，得到x (P(x) Q(x)/論域為正實數(shù)直接證明定義整數(shù)n是偶數(shù)，如果存在一個整數(shù)k使得n=2k;整數(shù)n是奇數(shù)，如果存在一個整數(shù)k使得n=2k+1。備注：一個整數(shù)要么是偶數(shù)，要么是奇數(shù)。定理：若n是奇數(shù)，則n2是奇數(shù)。任意給定一個奇數(shù)n，存在一個整數(shù)k ，n=2k+1n2=2(2k2+2k)+1n2是奇數(shù)所以，對任意奇數(shù)n，n2是奇數(shù)。n (Odd(n) Odd(n2)反證法原理pq qp證明框架q p所以，p q 成立反證法（舉例）若3n+2是奇數(shù)，則n是奇數(shù)。/直接證明的設(shè)想不奏效。假設(shè)結(jié)論不存立(q)n是偶數(shù)，存在一個整數(shù)k使得n=2k3n+2=

3、2(3k+1)3n+2是偶數(shù) (p)因此，若3n+2是奇數(shù)，則n是奇數(shù) (p q)歸謬法原理q qF證明框架q rr所以，q 成立歸謬法（舉例）There is no rational number whose square is 2.ProofExtra hypothesis: (p/q)2=2, and p,q areno common factors except for 1.egers which haveThen, p2=2q2 p2 is even p is even p2 is multiple of 4 q2 is even q is even p,q have 2 as co

4、mmon factor contradiction反證法（廣義）原理p1 . pn q q p1 . pn F證明框架q, p1, ., pn (比如p1 p1)所以， p1 . pn q分情形證明原理p1 . pn q (p1 q)證明框架p1 qpn q因此， p1. pn q . (pn q)分情形證明（舉例）當n是一個正整數(shù)，且n4時，(n+1)33n。n=1, 2, 3, 4.（窮舉）當n是一個整數(shù)時，有n2n。n0n1(x+y)r xr+yr, 這里x, y是正實數(shù), r是0r1的實數(shù).不失一般性，假設(shè)x+y=1.x xr， y yr x+y xr+yr (x+y)r xr+yr等

5、價性證明原理 p1p2pn ( p1p2) ( p2p3) ( pnp1)證明框架p1 p2p2 p3pn p1因此， p1p2pn。存在性證明證明目標x P(x)構(gòu)造性證明存在這樣的正整數(shù)，有兩種方式表示為正整數(shù)的立方和。1729=103+93=123+13非構(gòu)造性證明存在無理數(shù)x和y 使得x y是有理數(shù)y2=2，x= y y，x y=(y y) y=y2=2若x是無理數(shù)， x和y即為所求；否則，y和y即為所求。唯一性證明證明目標x (P(x) y (yxP(y) )x P(x) y z (P(y) P(z) y = z)舉例，設(shè)a0, ax+b=c有唯一的解。尋找反例原理x P(x) x

6、P(x)舉例每個正整數(shù)都是兩個整數(shù)的平方和3每個正整數(shù)都是三個整數(shù)的平方和7每個正整數(shù)都是四個整數(shù)的平方和？證明中的錯誤以下證明“2=1”，錯在哪里？a=ba2=aba2-b2=ab-b2假設(shè)a和b是兩個相等的正整數(shù)兩邊乘以a兩邊乘去b2(a-b) (a+b) = b(a-b)(a+b) = b2b = b2 = 1兩邊除以(a-b)數(shù)學與猜想（費馬大定理）Pierre de Fermat (1601-1665), FranceFermats Last Theorem (1637) （費馬大定理）xn+yn=zn (n2, xyz0)沒有整數(shù)解Andrew Wiles (1953- ), Ox

7、ford, England1994/1995完成了費馬大定理的證明（約10年時間）橢圓曲線理論數(shù)學與猜想（哥德巴赫猜想）Goldbach Conjecture（1742年給的信中）任一大于5的整數(shù)都可寫成三個質(zhì)數(shù)之和。版本（在給哥德巴赫的回信中）任一大于2的偶數(shù)都可寫成兩個質(zhì)數(shù)之和?！癮+b”猜想任一充分大的偶數(shù)都可以表示成為一個素因子個數(shù)不超過a個的數(shù)與另一個素子不超過b個的數(shù)之和。1966年（19331996）證明了“1+2”猜想因數(shù)學與猜想（四色猜想）Four Color TheoremProed by in Francis Guthrie 1852Proven in 1976 by K

8、enneth Ira Appel (1932-, New York) and Wolfgang Haken (1928-, Berlin)Percy John Heawood (1861-1955, Britain) proved the five color theorem in 1890世界數(shù)學難題Hilberts problems (23), ICM1900, ParisMillennium Prize Problems(7) by the Clay Mathematics Institute in 2000P versus NP problemHodge conjecturePoincar conjecture (solved by Perelman)Riemann hypothesis5.Mills existence and mass gapNavierStokes existence and smoothnessBirch and Swinnerton-Dyer conjectureGrigori Perelman (1966-, Russian)In November 2002, Perelmanted theof a series ofeprs to t