《归纳与递归》PPT课件.ppt

《《归纳与递归》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《归纳与递归》PPT课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、 P(n)不成立，则 n(P(n)成立.l令S=n+|P(n)，S是非空子集.l根据良序公理，S有最小元素，记为m,m1l(m-1)S,即P(m-1)成立.l根据归纳步骤，P(m)成立，即mS，矛盾.l因此，n P(n)成立.数学归纳法（举例）数学归纳法（举例）lHk=1+1/2+1/k（k为正整数）l证明：H2n 1+n/2 （n为正整数）l基础步骤：P(1)为真，H2=1+1/2l归纳步骤：对任意正整数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 l因此，对任意正整数n,P(n)成立.数学归纳法（举例

3、）数学归纳法（举例）l猜测前n个奇数的求和公式，并证明之。l1=1l1+3=4l1+3+5=9l1+3+5+7=16ll1+3+(2n-1)=n2（n为正整数）l运用数学归纳法证明（练习）运用数学归纳法时犯的错误运用数学归纳法时犯的错误l平面上任何一组相互间不平行的直线必相交于一点.l基础步骤：P(2)为真l归纳步骤：对任意正整数k,P(k)P(k+1).l前k条交于p1.l后k条交于p2.lp1=p2强数学归纳法强数学归纳法l证明目标ln P(n)/n的论域为正整数集合l证明框架l基础步骤：P(1)为真l归纳步骤：对任意正整数k,P(1),P(k)P(k+1)./即，证明k(P(1)P(k)

4、P(k+1)l因此，对任意正整数n,P(n)成立./即：n P(n)强数学归纳法（一般形式）强数学归纳法（一般形式）l设P(n)是与整数n有关的陈述，a和b是两个给定的整数，且a b.l如果能够证明下列陈述lP(a),P(a+1),P(b).l对任意k b,P(a)P(k)P(k+1)l则下列陈述成立l对任意n a,P(n).n Z|n a 是良序的是良序的 强数学归纳法（举例）强数学归纳法（举例）l任意整数n(n 2)可分解为（若干个）素数的乘积ln=2.l考察 k+1.l用4分和5分就可以组成12分及以上的每种邮资.lP(12),P(13),P(14),P(15).l对任意k 15,P(1

5、2)P(k)P(k+1)数学归纳法（举例）数学归纳法（举例）l对每个正整数n 4，n!2nl基础步骤：P(4)为真，24 16l归纳步骤：对任意正整数k 4,P(k)P(k+1).(k+1)!=(k+1)k!(k+1)2k 2k+1 l因此，对任意正整数n 4,P(n)成立.运用良序公理来证明（举例）运用良序公理来证明（举例）l设a是整数,d是正整数,则存在唯一的整数q和r满足l0 r d la=dq+rl证明l令S=a-dq|0a-dq，qZ，S非空.l非负整数集合具有良序性lS有最小元，记为r0=a-dq0.l可证 0 r0 0Fibonacci 序列序列 lFibonacci 序列 fn

6、 定义如下lf0=0,lf1=1,lfn=fn 1+fn 2,对任意n 2.l其前几个数l0,1,1,2,3,5,8,l证明：对对任意n 0，其中，归纳证明归纳证明:Fibonacci 序列序列 l验证：当n=0,1时，陈述正确。l对于k+1,注意：2=+1，且n+1=n+n 1 对任意n 1.递归定义（集合递归定义（集合）l递归地定义集合。l基础步骤：指定一些初始元素；l递归步骤：给出从集合中的元素来构造新元素之规则；l排斥规则（只包含上述步骤生成的那些元素）默认成立l举例，正整数集合的子集SlxSl若xS且yS，则 x+yS。递归定义（举例递归定义（举例）l字母表上的字符串集合*。l基础步

7、骤：*（表示空串）;l递归步骤：若*且x ，则x*。l字符串的长度（*上的函数l）。l基础步骤：l()=0;l递归步骤：l(x)=l()+1,若*且x 递归定义（举例递归定义（举例）l*上的字符串连接运算。l基础步骤：若*，则 =;l递归步骤：若1*且2*以及x ，则 1 (2 x)=(1 2)x。/1 2通常也写成1 2 递归定义（举例递归定义（举例）l复合命题的合式公式。l基础步骤：T,F,s都是合式公式，其中s是命题变元;l递归步骤：若E和F是合式公式，则(E)、(EF)、(EF)、(EF)和(EF)都是合式公式。结构归纳法结构归纳法l关于递归定义的集合的命题，进行结构归纳证明。l基础步

8、骤：证明对于初始元素来说，命题成立;l递归步骤：针对生产新元素的规则，若相关元素满足命题，则新元素也满足命题l结构归纳法的有效性源于自然数上的数学归纳法l第0步（基础步骤），结构归纳法（举例）结构归纳法（举例）ll(xy)=l(x)+l(y),x和y属于*。l证明l设P(y)表示：每当x属于*，就有l(xy)=l(x)+l(y)。l基础步骤：每当x属于*，就有l(x)=l(x)+l()。l递归步骤：假设P(y)为真，a属于,要证P(ya)为真。l即：每当x属于*，就有l(xya)=l(x)+l(ya)lP(y)为真，l(xy)=l(x)+l(y)ll(xya)=l(xy)+1=l(x)+l(y)+1=l(x)+l(ya)广义结构归纳法（举例）广义结构归纳法（举例）lNN是良序的（字典序）l递归定义am,nla0,0=0lam,n=am-1,n+1 (n=0,m0)lam,n=am,n-1+n (n0)l 归纳证明 am,n=m+n(n+1)/20 1 31 2 42 3 5 作业作业l教材内容：Rosen 4.24.3节l课后习题：lpp.210-213（英文教材 pp.280-282）:18,20 lpp.220-223（英文教材 pp.292-294）:7,12 lpp.233-235（英文教材 pp.309-310）：24,32,52