离散数学 第2版 教学课件 作者 王元元 离散第3讲 归纳原理

计算机专业基础课程授课人：王元元单位：计算机理论教研室指挥自动化学院计算机系·归纳原理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的。·说明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)真。·举例·例1:证明对所有的n N，有5n-2n能被3整除·例2:证明n＜2n归纳、猜测、证明2.1

归纳原理*指挥自动化学院计算机理论教研室14·讨论2.1

归纳原理*指挥自动化学院计算机理论教研室15·命题:我永远吃不饱。·证明:·基础:吃一粒米吃不饱。·归纳:再吃一粒米也吃不饱。·结论:永远吃不饱。·第一数学归纳法的变形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)。·求证:对任意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)也为真。·结论:所有自然数具有性质P·在接受“自然数集合的任一非空子集都有最小元素”这一事实的基础上,可以证明第二数学归纳法的正确性。2.1

归纳原理*指挥自动化学院计算机理论教研室22·解:假设P(x)不是对所有自然数都成立，那么使P(x)不成立的自然数集为M。由最小数原理知，M中必有最小数k，使P（k）不成立，所以对所有n<k，P（n）成立。又由归纳条件，有P（k）也成立。矛盾。故必对一切自然数都成立。·举例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时命题真。现设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条直线必重合于同一条直线。·证明：n=l时显然命题真。设n=k时命题成立，即任意k条直线均重合于同一条直线。现考虑n=k+1，即有k+1条直线：l1，l2，…，lk，lk+1。据归纳假设，l1，l2，…，lk，这k条直线必重合于同一条；l2，…，lk，lk+1这k条直线也必重合于同一条．由于两组直线中有公共的成员，因此这两组直线事实上重合于同一条直线。归纳完成，命题证毕。问题出在哪儿呢？出在k的任意性在推理中被忽略。不难看