【正文】 (9),I（ 11） (?x)(?y)(S(x,y)?S(x,0)) P（ 12） (?y)(S(2, y)?S(2,0)) US，（ 11）（ 13） S(2, 5)?S(2,0) US，（ 12）（ 14） S(2, 0) T,(10),(13),I（ 15） (?x)(?y)(?z)(S(x, y)?S(0, z)) P（ 16） (?y)(?z)(S(2, y)?S(0,z)) US，（ 15）（ 17） (?z)(S(2, 0)?S(0,z)) US，（ 16）電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程81例 證明（續(xù)）（ 18） (S(2, 0)?S(0, 2)) ES，（ 17）（ 19） S(0, 2) T,(14),(18),I（ 20） (?x)(?y)(S(x,y)?S(7,y)) P（ 21） (?y)(S(0,y)?S(7,y)) US，（ 20）（ 22） (S(0,2)?S(7,2)) US，（ 21）（ 23） S(7,2) T,(19),(22),I（ 24） (?x)(?y)(?z)(S(x,y)?S(z,5)) P（ 25） (?y)(?z)(S(7,y)?S(z,5)) US，（ 24）（ 26） (?z)(S(7,2) ?S(z,5)) US，（ 25）電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程82例 證明（續(xù)）（ 27） S(7, 2)?S(4, 5) ES，（ 26）（ 28） S(4, 5) T,(23),(27),I（ 29） (?x)(?y)(S(x,y) ?S(x,0) ) P（ 30） (?y)(S(4,y)?S(4,0)) US，（ 29）（ 31） S(4, 5) ?S(4, 0) US，（ 30）（ 32） S(4, 0) T,(30),(33),I電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程83 數(shù)學(xué)歸納法 數(shù)學(xué)歸納法原理假設(shè)要證明的命題能寫成形式 :?n≥n0，有 P(n) 其中 n0是某個固定的整數(shù)，即：希望證明對所有的整數(shù) n≥n0都有P(n)為真 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程84數(shù)學(xué)歸納法原理假設(shè) 1）驗證 n＝ n0，有 P(n0)為真； (歸納基礎(chǔ) )2）假設(shè)對于 n＝ k(k≥n0)，有 P(k)為真； (歸納假設(shè) )3）證明 n＝ k＋ 1，有 P(k+1)為真。 (歸納結(jié)論 )結(jié)論 對所有的整數(shù) n≥n0，都有 P(n)為真。謂詞表示： (?n0)(P(n0)∧ (?n)((n＝ k)∧ P(k)→P(k+1))＝ 1 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程85強形式數(shù)學(xué)歸納法原理 假設(shè) 1 ） 驗證 n＝ n0 、 n0 +1，有 P(n0)、 P(n0+1)為真； (歸納基礎(chǔ) )2）假設(shè)對于 n≤ k(k≥n0)，有 P(n)為真； (歸納假設(shè))3）證明 n＝ k＋ 1，有 P(k+1)為真。 (歸納結(jié)論 )結(jié)論 對所有的整數(shù) n≥n0，都有 P(n)為真。謂詞表示： (?n0)(P(n0) ∧ P(n0+1) ∧ (?n)((n≤k)∧ P(n)→P(k+1)) ＝ 1 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程86例 用數(shù)學(xué)歸納法證明： 對所有 n≥1，有 1+2+3+…+n= 證明 歸納基礎(chǔ)驗證 1= 顯然 P(1)真值為 1； 歸納假設(shè)假定 對于 n=k(k≥1)，有 P(k)為真，即有 1+2+3+…+k= ； 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程87例 歸納結(jié)論證明 對于 n＝ k＋ 1，有 P(k+1)為真 1+2+3+…+k+(k+1)= +(k+1) =由數(shù)學(xué)歸納法原理得到， P(n)對所有 n≥1為真。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程88例 對每個正整數(shù) n≥1，能惟一地寫 成，其中 pi是素數(shù)且 滿足 p1p2… ps。 分析 設(shè) P(n) ： n＝ ； 由于素數(shù)一定是大于等于 2的正整數(shù)，因此， n0＝ 2。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程89例 ? 證明 歸納基礎(chǔ)驗證? 因為 2=21， 3=31，所以 P(2)、 P(3)為真；? 歸納假設(shè)假定 ? 對 n≤k的所有正整數(shù)，都有 P(n)為真，即? ? n＝ 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程90例 證明 (續(xù) )歸納結(jié)論證明 對 n＝ k＋ 1，需分兩種情況討論：（ 1）如果 n本身就是一個素數(shù)，則 k＋ 1＝ (k+1)1，即 P(k+1)為真；（ 2）如果 n不是一個素數(shù)，則 k＋ 1＝ lm， 其中 2≤l≤k ， 2≤m≤k ，此時由歸納假設(shè)有 l＝ ， m＝其中， p1, p2, …, ps是素數(shù)，且是包含 l、 m中全部分解因子， bi、 ci≥0 的自然數(shù)，電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程91例 證明 (續(xù) )為此有 k＋ 1＝ lm＝ ＝ ＝由于 p1, p2, …, ps是素數(shù)，所以 k+1能分解成素數(shù)的積，又因為 l和 m的因子分解是惟一的，所以 k＋ 1的因子分解也是惟一的，所以 P(k+1)是真的。由數(shù)學(xué)歸納法原理得到， P(n)對所有 n≥1 為真。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程92 數(shù)學(xué)歸納法應(yīng)用例 用數(shù)學(xué)歸納法證明下列偽碼程序的計算結(jié)果時兩個正整數(shù)的最大公因子。其中偽碼程序為 FUNCTION GCD(X, Y) 1. WHILE (X?Y) a. IF (XY) THEN 1. X?XY b. ELSE 1. Y?YX 2. RETURN(X) END OF FUNCTION GCD 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程93例 證明 歸納基礎(chǔ)驗證 因為在循環(huán)開始之前存在變量值X0＝ X， Y0＝ Y，因此， P(0)是命題 GCD(X0, Y0)=GCD(X, Y)，顯然命題為真；歸納假設(shè)假定 設(shè) P(k)是命題 GCD(Xk, Yk)=GCD(X, Y)為真；電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程94例 證明（續(xù)） 歸納結(jié)論證明 首先考慮 P(k＋ 1)的左邊，即 GCD(Xk＋ 1, Yk＋ 1)。在通過 k＋ 1次循環(huán)后，或者 Xk＋ 1＝ Xk和 Yk＋ 1＝ Yk－ Xk；或者 Xk＋ 1＝ Xk－ Yk和 Yk＋ 1＝ Yk； 則由 整數(shù)的基本性質(zhì) 知， P(k＋ 1)＝ GCD(Xk＋1, Yk＋ 1)＝ GCD(Xk, Yk)＝ GCD(X, Y)。 根據(jù) 數(shù)學(xué)歸納法 知：對所有 n?0，有 P(n)為真。為此，該偽碼程序輸出的結(jié)果必是兩個正整數(shù)的最大公因子。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程95鋪瓦問題例 一個直角三正方形，是一個由三個正方形組成的對象，如圖 1所示。如果我們從nn(n為 2的冪 )正方形的板中去掉一個正方形，則余下的圖形可用直角三正方形來鋪成，如圖 2。此處的鋪成是用直角三正方形正好覆蓋全圖的圖形，每個直角三正方形不能有重疊，也不許超出圖形之外。我們?nèi)鄙僖粋€正方形的板稱為一個缺方板，把此問題稱為鋪瓦問題。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程96鋪瓦問題電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程97鋪瓦問題 證明（續(xù)）（ 歸納結(jié)論證明部分） 對于 2k＋ 12k＋ 1的缺方板問題，我們可以將其分成四個 2k2k的板，如圖所示。旋轉(zhuǎn)此板，使缺少的正方形在左上的四分之一中。由歸納假設(shè)，此左上的 2k2k缺方板可由直角三正方形鋪成，把一個直角三正方形 T放在中間，則另外三個四分之一都是 2k2k的缺方板。由歸納假設(shè)，它們的鋪瓦問題都是可以解決的。于是 2k＋ 12k＋ 1的缺方板可由直角三正方形鋪成。 由數(shù)學(xué)歸納法知，對任何的 n， nn正方形的鋪瓦問題都是可以鋪成的。 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程98 按定義證明方法 在離散數(shù)學(xué)中，我們大量的定義描述都是用蘊涵型 “P→Q” 的方式來描述的。如集合中子集的包含關(guān)系的定義描述為： 集合 A ? B ?(?a)(a∈ A→a ∈ B)電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程99 按定義證明方法原理加上題目中的已知G1, G2,…,G n證明問題 H中的 Q規(guī)則觸發(fā)引用公理引入證明問題 H中的 P電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程100 按定義證明方法應(yīng)用例 設(shè) A、 B是兩個任意集合，證明 A ? B ? P(A) ? P(B) 證明 （ 1） 必要性 “ ?” ： 對任意的 x∈P(A )，則 x ? A，由于 A ? B，所以 x ? B，即有 x∈P(B )。由 CP規(guī)則知：P(A)P(B)。 即 A ? B ? P(A) ? P(B) 電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程101例 證明 （續(xù)）（ 2） 充分性 “ ?” ： 對任意的 x∈A ，則 {x}∈P(A )，由于 P(A) ?P(B)，所以 {x}∈P(B )，即有 x∈B 。由 CP規(guī)則知： A ?B。 即 P(A) ? P(B) ? A ? B。 原式得證。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程102例 如果 A ? B，則 A∪ B＝ B且 A∩B＝ A 證明 兩個集合相等 ，即是證明 兩個集合相互包含 ，請學(xué)生自證。電子科技大學(xué)離散數(shù)學(xué)課程組 —— 國家精品課程103作業(yè)1.（ 2）2.（ 1） （ 6）3.（ 3） （ 5）57. (8) (9