《归纳与递归》PPT课件.ppt
归纳与递归,离散数学逻辑和证明南京大学计算机科学与技术系,回顾,证明：直接证明反证法分情形证明等价性证明存在性证明唯一性证明寻找反例数学与猜想,提要,数学归纳法强数学归纳法运用良序公理来证明递归定义结构归纳法,数学归纳法,证明目标n P(n)/n的论域为正整数集合证明框架基础步骤：P(1)为真归纳步骤：对任意正整数k,P(k)P(k+1)./即，证明k(P(k)P(k+1)因此，对任意正整数n,P(n)成立./即：n P(n),数学归纳法（有效性）,良序公理正整数集合的非空子集都有一个最小元素数学归纳法的有效性（归谬法）假设n P(n)不成立，则 n(P(n)成立.令S=n+|P(n)，S是非空子集.根据良序公理，S有最小元素，记为m,m1(m-1)S,即P(m-1)成立.根据归纳步骤，P(m)成立，即mS，矛盾.因此，n P(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+3+5=91+3+5+7=161+3+(2n-1)=n2（n为正整数）运用数学归纳法证明（练习）,运用数学归纳法时犯的错误,平面上任何一组相互间不平行的直线必相交于一点.基础步骤：P(2)为真归纳步骤：对任意正整数k,P(k)P(k+1).前k条交于p1.后k条交于p2.p1=p2,强数学归纳法,证明目标n P(n)/n的论域为正整数集合证明框架基础步骤：P(1)为真归纳步骤：对任意正整数k,P(1),P(k)P(k+1)./即，证明k(P(1)P(k)P(k+1)因此，对任意正整数n,P(n)成立./即：n P(n),强数学归纳法（一般形式）,设P(n)是与整数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).,nZ|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+1).(k+1)!=(k+1)k!(k+1)2k 2k+1 因此，对任意正整数n 4,P(n)成立.,运用良序公理来证明（举例）,设a是整数,d是正整数,则存在唯一的整数q和r满足0 r d a=dq+r证明令S=a-dq|0a-dq，qZ，S非空.非负整数集合具有良序性S有最小元，记为r0=a-dq0.可证 0 r0 d,运用良序公理来证明（举例）,在循环赛胜果图中，若存在长度为m（m3）的回路，则必定存在长度为3的回路。备注：ai aj 表示ai赢了aj证明设最短回路的长度为k（k3）/良序公理的保证a1 a2 a3 ak a1 若a3 a1,存在长度为3的回路，矛盾。若a1 a3,存在长度为(k-1)的回路，矛盾。,递归定义（N上的函数）,递归地定义自然数集合N上的函数。基础步骤：指定这个函数在0处的值；递归步骤：给出从较小处的值来求出当前的值之规则。举例，阶乘函数F(n)=!n的递归定义F(0)=1F(n)=nF(n-1)for n0,Fibonacci 序列,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.,递归定义（集合）,递归地定义集合。基础步骤：指定一些初始元素；递归步骤：给出从集合中的元素来构造新元素之规则；排斥规则（只包含上述步骤生成的那些元素）默认成立举例，正整数集合的子集SxS若xS且yS，则 x+yS。,递归定义（举例）,字母表上的字符串集合*。基础步骤：*（表示空串）;递归步骤：若*且x，则x*。字符串的长度（*上的函数l）。基础步骤：l()=0;递归步骤：l(x)=l()+1,若*且x,递归定义（举例）,*上的字符串连接运算。基础步骤：若*，则=;递归步骤：若1*且2*以及x，则 1(2 x)=(1 2)x。/1 2通常也写成1 2,递归定义（举例）,复合命题的合式公式。基础步骤：T,F,s都是合式公式，其中s是命题变元;递归步骤：若E和F是合式公式，则(E)、(EF)、(EF)、(EF)和(EF)都是合式公式。,结构归纳法,关于递归定义的集合的命题，进行结构归纳证明。基础步骤：证明对于初始元素来说，命题成立;递归步骤：针对生产新元素的规则，若相关元素满足命题，则新元素也满足命题结构归纳法的有效性源于自然数上的数学归纳法第0步（基础步骤），,结构归纳法（举例）,l(xy)=l(x)+l(y),x和y属于*。证明设P(y)表示：每当x属于*，就有l(xy)=l(x)+l(y)。基础步骤：每当x属于*，就有l(x)=l(x)+l()。递归步骤：假设P(y)为真，a属于,要证P(ya)为真。即：每当x属于*，就有l(xya)=l(x)+l(ya)P(y)为真，l(xy)=l(x)+l(y)l(xya)=l(xy)+1=l(x)+l(y)+1=l(x)+l(ya),广义结构归纳法（举例）,NN是良序的（字典序）递归定义am,na0,0=0am,n=am-1,n+1(n=0,m0)am,n=am,n-1+n(n0)归纳证明 am,n=m+n(n+1)/2,0 1 31 2 42 3 5,作业,教材内容：Rosen 4.24.3节课后习题：pp.210-213（英文教材 pp.280-282）:18,20 pp.220-223（英文教材 pp.292-294）:7,12 pp.233-235（英文教材 pp.309-310）：24,32,52,
