《离散数学 第2版 教学课件 ppt 作者 王元元 离散第3讲 归纳原理》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第3讲 归纳原理（28页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,指挥自动化学院计算机系,归纳原理,Page 17 to 21,离散数学第3讲,-3-, 2.1 归 纳 原 理,回顾,集合归纳定义 基础条款 归纳条款 终极条款,-4-, 2.1 归 纳 原 理,举例：成形括号串,， （即左括号和右括号所组成的集合），成形括号串集合S是+的子集合，归纳定义如下： 基础条款：S，即是S的元素 归纳条款：若xS，yS，则 a）x S b）xy S 终极条款：只有有限次应用条款（1）、（2）所得之元素才是S的元素,-5-, 2.1 归 纳 原 理,第2章 两个常用数学基本原理,2.1 归纳原理 2.2鸽笼
2、原理,-6-, 2.1 归 纳 原 理,内容提要,结构归纳原理 数学归纳原理 第一数学归纳法 第二数学归纳法 化归于数学归纳法的结构归纳,-7-, 2.1 归 纳 原 理,结构归纳原理,归纳定义不仅提供了定义无限集合的一个方法，它也是归纳法证明的基础 假定我们希望证明归纳定义的集合S的所有元素都具有某个性质P，则我们可以分两个步骤用下面的归纳法来证明： 基础步骤：S定义的基础条款中所指定的每一个元素xS均具有性质P； 归纳步骤：如果归纳条款使用的已确定元素都有性质P，那么用S定义中的归纳条款所构成的新元素也具有性质P。也就是说S的归纳定义中的归纳条款是保性质P的。,-8-, 2.1 归 纳 原
3、 理,说明,归纳步骤中的假设称为归纳假设； 由于集合S仅由（1）（2）条款所确定的元素组成，因此上述证明过程对证明“S中所有元素都有性质P”是足够的； 这种推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法（induction），或结构归纳法，数学归纳法为其特例,-9-, 2.1 归 纳 原 理,用归纳法证明在任何成形括号串中，左括号数等于右括号数 基础（对应于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 =
4、R(x) b）L(xy) = L(x)+L(y) = R(x)+R(y) = R(xy) 故对任意x S，有L(x) = R(x),举例：成形括号串,-10-, 2.1 归 纳 原 理,还可以用归纳法证明在任何成形括号串的字头中，左括号数不少于右括号数。即对任意x S，x的任意字头w，都有L(w) R(w),举例：成形括号串,-11-, 2.1 归 纳 原 理,基础：如果x = ，显然x的字头w（= 、 或 ）的左括号数不少于右括号数（对应于S的基础条款） 归纳：设x和y是S的元素，且对x、y的任意字头w都有L(w) R(w)，则： a）x的字头v是“”、“毗连x的字头”或“x”三种情况之一，
5、因为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) 归纳完成，命题得证,举例：成形括号串,-12-, 2.1 归 纳 原 理,数学归纳原理,当在归纳定义的自然数集上进行归纳推理时，就得到了数学归纳原理，它分为基本模式和加强模式两种证明模式 基本模式：第一数学归纳法 加强模式：第二数学归纳法,-13-, 2.1 归 纳 原 理,第一数学归纳法（基本模式）,为证明所有自然数都有性质P，只要作如下推理： （1）基础：
6、对N的基础元素0，证明具有性质P，即证P(0)为真； （2）归纳：假定N中已知元素k（0）具有性质P（归纳假设），去证由k用归纳条款生成的元素k+1也具有性质P，即由P(k)真，去证P(k+1)真 。,-14-, 2.1 归 纳 原 理,举例,例1：证明对所有的nN，有 5n-2n能被3整除 例2：证明n2n,归纳、猜测、证明,-15-, 2.1 归 纳 原 理,讨论,命题：我永远吃不饱。 证明： 基础：吃一粒米吃不饱。 归纳：再吃一粒米也吃不饱。 结论：永远吃不饱。,-16-, 2.1 归 纳 原 理,第一数学归纳法的变形,起始于任意自然数的归纳证明模式 起始于多个值的归纳证明模式 允许有参
7、变数的归纳证明模式,-17-, 2.1 归 纳 原 理,举例,例3：证明可以用4分和5分邮票组成12分或以上的任何一种邮资 证法一（起始于任意自然数的归纳证明模式） 证法二（起始于多个值的归纳证明模式）,-18-, 2.1 归 纳 原 理,举例,例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,-19-, 2.1 归 纳 原 理,举例,证 对n归纳，把m看作参数。 当n = 0时，f(0,m)=m+10 。 假设当n = k时，设对任意m有f(k,m)0 。 那么
8、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 归纳完成，命题得证。,-20-, 2.1 归 纳 原 理,数学归纳法的有效性,良序性公理： 每个非空的非负整数集都有最小元 应用良序性证明数学归纳法的有效性,-21-, 2.1 归 纳 原 理,第二数学归纳法（加强模式）,严格说来，以上讲的称为数学归纳法第一原理。我们还有数学归纳法第二原理，即强数学归纳法，其方法是： 基础：同第一原理； 归纳：假设对小于n（0）的任意的mN，P(m)均为真（归纳假设），去证P(n)也为真。 结论：所有自然
9、数具有性质P,-22-, 2.1 归 纳 原 理,在接受“自然数集合的任一非空子集都有最小元素”这一事实的基础上，可以证明第二数学归纳法的正确性。 解：假设P(x)不是对所有自然数都成立，那么使P(x)不成立的自然数集为M。由最小数原理知，M中必有最小数k，使P（k）不成立，所以对所有nk，P（n）成立。又由归纳条件，有P（k）也成立。矛盾。 故必对一切自然数都成立。,-23-, 2.1 归 纳 原 理,举例,例5：证明所有大于等于2的整数能写成若干质数的积,-24-, 2.1 归 纳 原 理,举例,例6：取棋子游戏。有数目相等的两堆棋子，甲、乙两人轮流从中取子，不能不取，也不能同时在两堆中取
10、，取到最后一枚棋子者胜。求证：后取者必胜,-25-, 2.1 归 纳 原 理,说明,对于自然数而言，这两个原理是等价的（即假定其中一种是有效的证明技术，可以证明另外一种也是）。但当不是自然数时，两个原理不是等价的。第二个原理的归纳法证明较用第一原理的归纳法证明假设的前提要强 在归纳法中，两个步骤是缺一不可的，并且要注意归纳基础的充分性和归纳推理中k的任意性。见书上例题2-7、2-8 在归纳时，先假设后证明。这是因为我们不是在证明这个性质，而是在证明在此归纳定义下，保持此性质。所以可以假设，也必须假设,-26-, 2.1 归 纳 原 理,这个步骤是有疑问的，因为k22k +1只是在k3时才成立,
11、因而归纳基础只对n = 0进行是不充分的。因此，应对n = 0，n = 1，n = 2, n = 3分别证明（作为归纳基础）后再进行上述归纳推理才对。,找错误,证明：对任何自然数，有 2.5n n2 证：n = 0时， 2.50 = 1 0=02，故命题真。 设n = k时命题真。 现设n = k+1，那么 2.5k+1=2.52.5k22.5k =2.5k+2.5k k2+k2（归纳假设） k2+2k+1=(k+1)2 归纳完成,-27-, 2.1 归 纳 原 理,问题出在哪儿呢？出在k的任意性在推理中被忽略。不难看出，k = 1(n = 2)时，两组直线分别只含一条直线，它们不会有公共成员
12、。,找错误,命题：任意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条直线也必重合于同一条由于两组直线中有公共的成员，因此这两组直线事实上重合于同一条直线。归纳完成，命题证毕。,-28-, 2.1 归 纳 原 理,小结,本小节主要内容包括结构归纳法证明，它分为基础步骤和归纳步骤，二者缺一不可；数学归纳法，是结构归纳的特例，对应自然数集上的归纳证明，分基本模式和加强模式两种证明模式。重点是要掌握并会熟练运用结构归纳和数学归纳原理 作业本作业：P25 5、6 书上作业： P25 10、11,
