離散數學 第2版 教學課件 作者 王元元 離散第3講 歸納原理

計算機專業(yè)基礎課程授課人：王元元單位：計算機理論教研室指揮自動化學院計算機系·歸納原理Page

17

to

21《離散數學》第3講·回顧2.1

歸納原理*指揮自動化學院計算機理論教研室3·集合歸納定義·基礎條款·歸納條款·終極條款·舉例:成形括號串2.1

歸納原理*指揮自動化學院計算機理論教研室4＝{[，]}（即左括號和右括號所組成的集合）成形括號串集合S是 +的子集合，歸納定義如下:·基礎條款:[] S，即[]是S的元素·歸納條款:若x S，y S，則a）[x] Sb）xy S·終極條款:只有有限次應用條款（1）、（2）所得之元素才是S的元素·第2章

兩個常用數學基本原理歸納原理鴿籠原理122.1

歸納原理*指揮自動化學院計算機理論教研室5·內容提要2.1

歸納原理*指揮自動化學院計算機理論教研室6·結構歸納原理·數學歸納原理·第一數學歸納法·第二數學歸納法·化歸于數學歸納法的結構歸納·結構歸納原理2.1

歸納原理*指揮自動化學院計算機理論教研室7·歸納定義不僅提供了定義無限集合的一個方法，它也是歸納法證明的基礎·假定我們希望證明歸納定義的集合S的所有元素都具有某個性質P，則我們可以分兩個步驟用下面的歸納法來證明:·基礎步驟:S定義的基礎條款中所指定的每一個元素xS均具有性質P；·歸納步驟:如果歸納條款使用的已確定元素都有性質P，那么用S定義中的歸納條款所構成的新元素也具有性質P。也就是說S的歸納定義中的歸納條款是保性質P的?！ふf明2.1

歸納原理*指揮自動化學院計算機理論教研室8·歸納步驟中的假設稱為歸納假設；·由于集合S僅由（1）（2）條款所確定的元素組成,因此上述證明過程對證明“S中所有元素都有性質P是足夠的；·這種推理原理稱為歸納原理,應用這一原理進行證明的方法稱為歸納法（induction）,或結構歸納法數學歸納法為其特例·用歸納法證明在任何成形括號串中，左括號數等于右括號數·基礎（對應于S的基礎條款）:如果x=[]，那么L(x)=R(x)=1·歸納（對應于S的歸納條款）:設x和y是S的元素，有L(x)=R(x)，L(y)=R(y)，則:a）L([x])=L(x)+1=R(x)+1=R([x])b）L(xy)=L(x)+L(y)=R(x)+R(y)=R(xy)·故對任意x S，有L(x)=R(x)2.1

歸納原理*指揮自動化學院計算機理論教研室9·舉例:成形括號串·還可以用歸納法證明在任何成形括號串的字頭中,左括號數不少于右括號數。即對任意x S,x的任意字頭w,都有L(w)≥R(w)2.1

歸納原理*指揮自動化學院計算機理論教研室10·舉例:成形括號串·基礎:如果x=[]，顯然x的字頭w（= 、[或[]）的左括號數不少于右括號數（對應于S的基礎條款）·歸納:設x和y是S的元素，且對x、y的任意字頭w都有L(w)≥R(w)，則:·a）[x]的字頭v是“ ”、“[毗連x的字頭”或“[x]”三種情況之一，因為x的任意字頭w都有L(w)≥R(w)，所以無論是哪種情況，都有L(v)≥R(v)·b）xy的字頭v是“x的字頭”或“x與y的字頭毗連”兩種情況之一，因為對x、y的任意字頭w都有L(w)≥R(w)，所以兩種情況下均有L(v)≥R(v)·歸納完成，命題得證2.1

歸納原理*指揮自動化學院計算機理論教研室11·舉例:成形括號串·數學歸納原理2.1

歸納原理*指揮自動化學院計算機理論教研室12·當在歸納定義的自然數集上進行歸納推理時，就得到了數學歸納原理，它分為基本模式和加強模式兩種證明模式·基本模式:第一數學歸納法·加強模式:第二數學歸納法·第一數學歸納法（基本模式）2.1

歸納原理*指揮自動化學院計算機理論教研室13·為證明所有自然數都有性質P，只要作如下推理:·（1）基礎:對N的基礎元素—0，證明具有性質P，即證P(0)為真；·（2）歸納:假定N中已知元素k（≥0）具有性質P（歸納假設），去證由k用歸納條款生成的元素k+1也具有性質P，即由P(k)真，去證P(k+1)真?！づe例·例1:證明對所有的n N，有5n-2n能被3整除·例2:證明n＜2n歸納、猜測、證明2.1

歸納原理*指揮自動化學院計算機理論教研室14·討論2.1

歸納原理*指揮自動化學院計算機理論教研室15·命題:我永遠吃不飽?！ぷC明:·基礎:吃一粒米吃不飽。·歸納:再吃一粒米也吃不飽?！そY論:永遠吃不飽。·第一數學歸納法的變形2.1

歸納原理*指揮自動化學院計算機理論教研室16·起始于任意自然數的歸納證明模式·起始于多個值的歸納證明模式·允許有參變數的歸納證明模式·舉例2.1

歸納原理*指揮自動化學院計算機理論教研室17·例3:證明可以用4分和5分郵票組成12分或以上的任何一種郵資·證法一（起始于任意自然數的歸納證明模式）·證法二（起始于多個值的歸納證明模式）·舉例2.1

歸納原理*指揮自動化學院計算機理論教研室18·例4:設f是以自然數集為定義域的函數，滿足·（1）f(0,m)=m+1·（2）f(n+1,m)=f(n,m2)·f(n,2nm)?！で笞C:對任意m，n，有f(n,m)>0·舉例2.1

歸納原理*指揮自動化學院計算機理論教研室19· 證對n歸納,把m看作參數。當n=0時,f(0,m)=m+1>0。假設當n=k時,設對任意m有f(k,m)>0。那么n=k+1時,f(n,m)=f(k+1,m)=f(k,m2)f(k,2km)據歸納假設f(k,m2)>0,f(k,2km)>0,故f(k+1,m)>0歸納完成,命題得證。·數學歸納法的有效性2.1

歸納原理*指揮自動化學院計算機理論教研室20·良序性公理: 每個非空的非負整數集都有最小元·應用良序性證明數學歸納法的有效性·第二數學歸納法（加強模式）2.1

歸納原理*指揮自動化學院計算機理論教研室21·嚴格說來，以上講的稱為數學歸納法第一原理。我們還有數學歸納法第二原理，即強數學歸納法，其方法是:·基礎:同第一原理；N,P(m)均·歸納:假設對小于n（≥0）的任意的m為真（歸納假設），去證P(n)也為真?！そY論:所有自然數具有性質P·在接受“自然數集合的任一非空子集都有最小元素”這一事實的基礎上,可以證明第二數學歸納法的正確性。2.1

歸納原理*指揮自動化學院計算機理論教研室22·解:假設P(x)不是對所有自然數都成立，那么使P(x)不成立的自然數集為M。由最小數原理知，M中必有最小數k，使P（k）不成立，所以對所有n<k，P（n）成立。又由歸納條件，有P（k）也成立。矛盾。故必對一切自然數都成立?！づe例2.1

歸納原理*指揮自動化學院計算機理論教研室23·例5:證明所有大于等于2的整數能寫成若干質數的積·舉例2.1

歸納原理*指揮自動化學院計算機理論教研室24·例6:取棋子游戲。有數目相等的兩堆棋子，甲、乙兩人輪流從中取子，不能不取，也不能同時在兩堆中取，取到最后一枚棋子者勝。求證:后取者必勝·說明2.1

歸納原理*指揮自動化學院計算機理論教研室25·對于自然數而言,這兩個原理是等價的（即假定其中一種是有效的證明技術,可以證明另外一種也是）。但當不是自然數時,兩個原理不是等價的。第二個原理的歸納法證明較用第一原理的歸納法證明假設的前提要強·在歸納法中,兩個步驟是缺一不可的,并且要注意歸納基礎的充分性和歸納推理中k的任意性。見書上例題2-7、2-8·在歸納時,先假設后證明。這是因為我們不是在證明這個性質,而是在證明在此歸納定義下,保持此性質。所以可以假設,也必須假設·這個步驟是有疑問的,因為k2≥2k+1只是在k≥3時才成立,因而歸納基礎只對n=0進行是不充分的。因此,應對n=0,n=1,n=2,n=3分別證明（作為歸納基礎）后再進行上述歸納推理才對。2.1

歸納原理*指揮自動化學院計算機理論教研室26·找錯誤·證明:對任何自然數，有2.5n≥n2證:n=0時，2.50=1≥0=02，故命題真。設n=k時命題真?，F設n=k+1，那么2.5k+1=2.5·2.5k>2·2.5k=2.5k+2.5k≥k2+（歸納假設）≥

k2+2k+1=(k+1)2歸納完成·找錯誤2.1

歸納原理*指揮自動化學院計算機理論教研室27·命題：任意n條直線必重合于同一條直線?！ぷC明：n=l時顯然命題真。設n=k時命題成立，即任意k條直線均重合于同一條直線?，F考慮n=k+1，即有k+1條直線：l1，l2，…，lk，lk+1。據歸納假設，l1，l2，…，lk，這k條直線必重合于同一條；l2，…，lk，lk+1這k條直線也必重合于同一條．由于兩組直線中有公共的成員，因此這兩組直線事實上重合于同一條直線。歸納完成，命題證畢。問題出在哪兒呢？出在k的任意性在推理中被忽略。不難看