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

《离散数学 第2版 教学课件 作者 王元元 离散第3讲 归纳原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室指挥自动化学院计算机系归纳原理Page17to21《离散数学》第3讲回顾集合归纳定义基础条款归纳条款终极条款3§2.1归纳原理举例：成形括号串＝{[，]}（即左括号和右括号所组成的集合），成形括号串集合S是+的子集合，归纳定义如下：基础条款：[]S，即[]是S的元素归纳条款：若xS，yS，则a）[x]Sb）xyS终极条款：只有有限次应用条款（1）、（2）所得之元素才是S的元素4§2.1归纳原理第2章两个常用数学基本原理2.1归纳原理2.2鸽笼原理125§2.1归纳原理内容提要结构归纳

2、原理数学归纳原理第一数学归纳法第二数学归纳法化归于数学归纳法的结构归纳6§2.1归纳原理结构归纳原理归纳定义不仅提供了定义无限集合的一个方法，它也是归纳法证明的基础假定我们希望证明归纳定义的集合S的所有元素都具有某个性质P，则我们可以分两个步骤用下面的归纳法来证明：基础步骤：S定义的基础条款中所指定的每一个元素xS均具有性质P；归纳步骤：如果归纳条款使用的已确定元素都有性质P，那么用S定义中的归纳条款所构成的新元素也具有性质P。也就是说S的归纳定义中的归纳条款是保性质P的。7§2.1归纳原理说明归纳步骤中的假设称为归纳假设；由于集合S仅由（1）（2

3、）条款所确定的元素组成，因此上述证明过程对证明“S中所有元素都有性质P”是足够的；这种推理原理称为归纳原理，应用这一原理进行证明的方法称为归纳法（induction），或结构归纳法，数学归纳法为其特例8§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=R([x])b）L(xy)=L(x)+L(y)=R(x)+R(y)=R(xy)

4、故对任意xS，有L(x)=R(x)举例：成形括号串9§2.1归纳原理还可以用归纳法证明在任何成形括号串的字头中，左括号数不少于右括号数。即对任意xS，x的任意字头w，都有L(w)≥R(w)举例：成形括号串10§2.1归纳原理基础：如果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

5、)b）xy的字头v是“x的字头”或“x与y的字头毗连”两种情况之一，因为对x、y的任意字头w都有L(w)≥R(w)，所以两种情况下均有L(v)≥R(v)归纳完成，命题得证举例：成形括号串11§2.1归纳原理数学归纳原理当在归纳定义的自然数集上进行归纳推理时，就得到了数学归纳原理，它分为基本模式和加强模式两种证明模式基本模式：第一数学归纳法加强模式：第二数学归纳法12§2.1归纳原理第一数学归纳法（基本模式）为证明所有自然数都有性质P，只要作如下推理：（1）基础：对N的基础元素—0，证明具有性质P，即证P(0)为真；（2）归纳：假定N中已知元素k（≥0

6、）具有性质P（归纳假设），去证由k用归纳条款生成的元素k+1也具有性质P，即由P(k)真，去证P(k+1)真。13§2.1归纳原理举例例1：证明对所有的nN，有5n-2n能被3整除例2：证明n＜2n归纳、猜测、证明14§2.1归纳原理讨论命题：我永远吃不饱。证明：基础：吃一粒米吃不饱。归纳：再吃一粒米也吃不饱。结论：永远吃不饱。15§2.1归纳原理第一数学归纳法的变形起始于任意自然数的归纳证明模式起始于多个值的归纳证明模式允许有参变数的归纳证明模式16§2.1归纳原理举例例3：证明可以用4分和5分邮票组成12分或以上的任何一种邮资证法一（起始于任意

7、自然数的归纳证明模式）证法二（起始于多个值的归纳证明模式）17§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)>018§2.1归纳原理举例证对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归纳完成，命题得证。1

8、9§2.1归纳原理数学归纳法的有效性良序性公理：每个非空的非负整数集都有最小元应用良序性证明数学归纳法的有效