归纳与递归ppt课件.ppt

归纳与递归离散数学─逻辑和证明南京大学计算机科学与技术系回想回想l证明：l直接证明l反证法l分情形证明l等价性证明l存在性证明l独一性证明l寻觅反例l数学与猜测提要提要l数学归纳法l强数学归纳法l运用良序公理来证明l递归定义l构造归纳法数学归纳法数学归纳法l证明目的ln P(n) //n的论域为正整数集合l证明框架l根底步骤：P(1)为真l归纳步骤：对恣意正整数k, P(k) P(k+1). l //即，证明k (P(k)P(k+1))l因此，对恣意正整数n, P(n) 成立. // 即：n P(n) 数学归纳法〔有效性〕数学归纳法〔有效性〕l良序公理l正整数集合的非空子集都有一个最小元素l数学归纳法的有效性〔归谬法〕l假设n P(n)不成立，那么 n (P(n))成立.l令S={ n+ | P(n)}，S是非空子集.l根据良序公理，S有最小元素，记为m, m1l(m-1)S, 即P(m-1)成立. l根据归纳步骤，P(m)成立，即mS，矛盾.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). l H2k+1 = H2k +1/(2k+1)+…+1/2k+1l (1+k/2)+2k(1/2k+1) =1+(1+k)/2 l因此，对恣意正整数n, P(n) 成立. 数学归纳法〔举例〕数学归纳法〔举例〕l猜测前n个奇数的求和公式，并证明之。

l1=1l1+3=4l1+3+5=9l1+3+5+7=16l…l1+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证明目的ln P(n) //n的论域为正整数集合l证明框架l根底步骤：P(1)为真l归纳步骤：对恣意正整数k, P(1), …, P(k) P(k+1). l //即，证明k (P(1)…  P(k)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(12)… P(k)P(k+1)数学归纳法〔举例〕数学归纳法〔举例〕l对每个正整数n  4，n!  2nl根底步骤：P(4)为真，24 16l归纳步骤：对恣意正整数k 4, P(k) P(k+1). l (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 | 0a-dq ，qZ}，S非空.l非负整数集合具有良序性lS有最小元，记为r0 = a-dq0.l可证 0  r0 < d 运用良序公理来证明〔举例〕运用良序公理来证明〔举例〕l在循环赛胜果图中，假设存在长度为m〔m3〕的回路，那么必定存在长度为3的回路。

l 备注： ai  aj 表示ai赢了ajl证明l设最短回路的长度为k 〔k3〕 //良序公理的保证la1  a2  a3 …  ak a1 l假设a3 a1, 存在长度为3的回路，矛盾l假设a1  a3, 存在长度为(k-1)的回路，矛盾递归定义〔递归定义〔N上的函数〕上的函数〕l递归地定义自然数集合N上的函数l根底步骤：指定这个函数在0处的值；l递归步骤：给出从较小处的值来求出当前的值之规那么l举例，阶乘函数F(n)=!n的递归定义lF(0)=1lF(n)=nF(n-1) for n>0Fibonacci 序列序列 lFibonacci 序列 {fn} 定义如下lf0 = 0,lf1 = 1,lfn = fn – 1 + fn – 2, 对恣意n  2.l其前几个数l0, 1, 1, 2, 3, 5, 8, …l证明：对对恣意n  0，l 其中，归纳证明归纳证明: Fibonacci 序列序列 l验证：当n=0,1时，陈说正确l对于k+1,l 留意：2 =  + 1，且n + 1 = n + n – 1 对恣意n  1.递归定义〔集合〕递归定义〔集合〕l递归地定义集合。

l根底步骤：指定一些初始元素；l递归步骤：给出从集合中的元素来构造新元素之规那么；l排斥规那么〔只包含上述步骤生成的那些元素〕默许成立l举例，正整数集合的子集SlxSl假设xS且yS，那么 x+yS递归定义〔举例〕递归定义〔举例〕l字母表上的字符串集合*l根底步骤：* 〔表示空串〕;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 l // 1  2通常也写成1 2 递归定义〔举例〕递归定义〔举例〕l复合命题的合式公式l根底步骤：T, F, s都是合式公式，其中s是命题变元;l递归步骤：假设E和F是合式公式，那么 (E)、(EF)、 (EF)、 (EF)和(EF)都是合式公式。

构造归纳法构造归纳法l关于递归定义的集合的命题，进展构造归纳证明l根底步骤：证明对于初始元素来说，命题成立;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)广义构造归纳法〔举例〕广义构造归纳法〔举例〕lNN是良序的〔字典序〕l递归定义am,nla0,0 = 0lam,n= am-1,n +1 (n=0, m>0)lam,n= am,n-1 +n (n>0)l 归纳证明 am,n= m+n(n+1)/20 1 31 2 42 3 5 作业作业l教材内容：[Rosen] 4.2—4.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。