《归纳与递归》ppt课件

《《归纳与递归》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、归纳与递归离散数学─逻辑和证明南京大学计算机科学与技术系回顾证明：直接证明反证法分情形证明等价性证明存在性证明唯一性证明寻找反例数学与猜想提要数学归纳法强数学归纳法运用良序公理来证明递归定义结构归纳法数学归纳法证明目标nP(n)//n的论域为正整数集合证明框架基础步骤：P(1)为真归纳步骤：对任意正整数k,P(k)P(k+1).//即，证明k(P(k)P(k+1))因此，对任意正整数n,P(n)成立.//即：nP(n)数学归纳法（有效性）良序公理正整数集合的非空子集都有一个最小元素数学归纳法的有效性（归谬法）假设nP(n)不成立，则n(P(n))成立.令S={n

2、+

3、P(n)}，S是非空子集.根据良序公理，S有最小元素，记为m,m1(m-1)S,即P(m-1)成立.根据归纳步骤，P(m)成立，即mS，矛盾.因此，nP(n)成立.数学归纳法（举例）Hk=1+1/2+…+1/k（k为正整数）证明：H2n1+n/2（n为正整数）基础步骤：P(1)为真，H2=1+1/2归纳步骤：对任意正整数k,P(k)P(k+1).H2k+1=H2k+1/(2k+1)+…+1/2k+1(1+k/2)+2k(1/2k+1)=1+(1+k)/2因此，对任意正整数n,P(n)成立.数学归纳法（举例）猜测前n个奇数的求和公式，并证明之。1=11+3=41+

4、3+5=91+3+5+7=16…1+3+…+(2n-1)=n2（n为正整数）运用数学归纳法证明（练习）运用数学归纳法时犯的错误平面上任何一组相互间不平行的直线必相交于一点.基础步骤：P(2)为真归纳步骤：对任意正整数k,P(k)P(k+1).前k条交于p1.后k条交于p2.p1=p2强数学归纳法证明目标nP(n)//n的论域为正整数集合证明框架基础步骤：P(1)为真归纳步骤：对任意正整数k,P(1),…,P(k)P(k+1).//即，证明k(P(1)…P(k)P(k+1))因此，对任意正整数n,P(n)成立.//即：nP(n)强数学归纳法（一般形式）设P(n)是与整

5、数n有关的陈述，a和b是两个给定的整数，且ab.如果能够证明下列陈述P(a),P(a+1),…,P(b).对任意kb,P(a)…P(k)P(k+1)则下列陈述成立对任意na,P(n).{nZ

6、na}是良序的强数学归纳法（举例）任意整数n(n2)可分解为（若干个）素数的乘积n=2.考察k+1.用4分和5分就可以组成12分及以上的每种邮资.P(12),P(13),P(14),P(15).对任意k15,P(12)…P(k)P(k+1)数学归纳法（举例）对每个正整数n4，n!2n基础步骤：P(4)为真，2416归纳步骤：对任意正整数k4,P(k)P(k+

7、1).(k+1)!=(k+1)k!(k+1)2k2k+1因此，对任意正整数n4,P(n)成立.运用良序公理来证明（举例）设a是整数,d是正整数,则存在唯一的整数q和r满足0r

8、0a-dq，qZ}，S非空.非负整数集合具有良序性S有最小元，记为r0=a-dq0.可证0r0

9、a3,存在长度为(k-1)的回路，矛盾。递归定义（N上的函数）递归地定义自然数集合N上的函数。基础步骤：指定这个函数在0处的值；递归步骤：给出从较小处的值来求出当前的值之规则。举例，阶乘函数F(n)=!n的递归定义F(0)=1F(n)=nF(n-1)forn>0Fibonacci序列Fibonacci序列{fn}定义如下f0=0,f1=1,fn=fn–1+fn–2,对任意n2.其前几个数0,1,1,2,3,5,8,…证明：对对任意n0，其中，归纳证明:Fibonacci序列验证：当n=0,1时，陈述正确。对于k+1,注意：2=+1，且n+1=n+n–1对任意n1

10、.递归定义（集合）递归地定义集合。基础步骤：指定一些初始元素；递归步骤：给出从集合中的元素来构造新元素之规则；排斥规则（只包含上述步骤生成的那些元素）默认成立举例，正整数集合的子集SxS若xS且yS，则x+yS。递归定义（举例）字母表上的字符串集合*。基础步骤：*（表示空串）;递归步骤：若*且x，则x*。字符串的长度（*上的函数l）。基础步骤：l()=0;递归步骤：l(x)=l()+1,若*且x递归定义（举例）