離散數(shù)學(xué) 第2版 教學(xué)課件 作者 王元元 離散第3講 歸納原理

計(jì)算機(jī)專業(yè)基礎(chǔ)課程授課人：王元元單位：計(jì)算機(jī)理論教研室指揮自動(dòng)化學(xué)院計(jì)算機(jī)系·歸納原理Page

17

to

21《離散數(shù)學(xué)》第3講·回顧2.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室3·集合歸納定義·基礎(chǔ)條款·歸納條款·終極條款·舉例:成形括號(hào)串2.1

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

兩個(gè)常用數(shù)學(xué)基本原理歸納原理鴿籠原理122.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室5·內(nèi)容提要2.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室6·結(jié)構(gòu)歸納原理·數(shù)學(xué)歸納原理·第一數(shù)學(xué)歸納法·第二數(shù)學(xué)歸納法·化歸于數(shù)學(xué)歸納法的結(jié)構(gòu)歸納·結(jié)構(gòu)歸納原理2.1

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

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室8·歸納步驟中的假設(shè)稱為歸納假設(shè)；·由于集合S僅由（1）（2）條款所確定的元素組成,因此上述證明過(guò)程對(duì)證明“S中所有元素都有性質(zhì)P是足夠的；·這種推理原理稱為歸納原理,應(yīng)用這一原理進(jìn)行證明的方法稱為歸納法（induction）,或結(jié)構(gòu)歸納法數(shù)學(xué)歸納法為其特例·用歸納法證明在任何成形括號(hào)串中，左括號(hào)數(shù)等于右括號(hào)數(shù)·基礎(chǔ)（對(duì)應(yīng)于S的基礎(chǔ)條款）:如果x=[]，那么L(x)=R(x)=1·歸納（對(duì)應(yīng)于S的歸納條款）:設(shè)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)·故對(duì)任意x S，有L(x)=R(x)2.1

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

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

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室11·舉例:成形括號(hào)串·數(shù)學(xué)歸納原理2.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室12·當(dāng)在歸納定義的自然數(shù)集上進(jìn)行歸納推理時(shí)，就得到了數(shù)學(xué)歸納原理，它分為基本模式和加強(qiáng)模式兩種證明模式·基本模式:第一數(shù)學(xué)歸納法·加強(qiáng)模式:第二數(shù)學(xué)歸納法·第一數(shù)學(xué)歸納法（基本模式）2.1

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

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室14·討論2.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室15·命題:我永遠(yuǎn)吃不飽?！ぷC明:·基礎(chǔ):吃一粒米吃不飽。·歸納:再吃一粒米也吃不飽。·結(jié)論:永遠(yuǎn)吃不飽。·第一數(shù)學(xué)歸納法的變形2.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室16·起始于任意自然數(shù)的歸納證明模式·起始于多個(gè)值的歸納證明模式·允許有參變數(shù)的歸納證明模式·舉例2.1

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

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

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

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室20·良序性公理: 每個(gè)非空的非負(fù)整數(shù)集都有最小元·應(yīng)用良序性證明數(shù)學(xué)歸納法的有效性·第二數(shù)學(xué)歸納法（加強(qiáng)模式）2.1

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

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

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室23·例5:證明所有大于等于2的整數(shù)能寫成若干質(zhì)數(shù)的積·舉例2.1

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

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室25·對(duì)于自然數(shù)而言,這兩個(gè)原理是等價(jià)的（即假定其中一種是有效的證明技術(shù),可以證明另外一種也是）。但當(dāng)不是自然數(shù)時(shí),兩個(gè)原理不是等價(jià)的。第二個(gè)原理的歸納法證明較用第一原理的歸納法證明假設(shè)的前提要強(qiáng)·在歸納法中,兩個(gè)步驟是缺一不可的,并且要注意歸納基礎(chǔ)的充分性和歸納推理中k的任意性。見(jiàn)書上例題2-7、2-8·在歸納時(shí),先假設(shè)后證明。這是因?yàn)槲覀儾皇窃谧C明這個(gè)性質(zhì),而是在證明在此歸納定義下,保持此性質(zhì)。所以可以假設(shè),也必須假設(shè)·這個(gè)步驟是有疑問(wèn)的,因?yàn)閗2≥2k+1只是在k≥3時(shí)才成立,因而歸納基礎(chǔ)只對(duì)n=0進(jìn)行是不充分的。因此,應(yīng)對(duì)n=0,n=1,n=2,n=3分別證明（作為歸納基礎(chǔ)）后再進(jìn)行上述歸納推理才對(duì)。2.1

歸納原理*指揮自動(dòng)化學(xué)院計(jì)算機(jī)理論教研室26·找錯(cuò)誤·證明:對(duì)任何自然數(shù)，有2.5n≥n2證:n=0時(shí)，2.50=1≥0=02，故命題真。設(shè)n=k時(shí)命題真?，F(xiàn)設(shè)n=k+1，那么2.5k+1=2.5·2.5k>2·2.5k=2.5k+2.5k≥k2+（歸納假設(shè)）≥

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

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