当前位置:高等教育资讯网  >  中国高校课件下载中心  >  大学文库  >  浏览文档

南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)集合论——第9章 归纳与递归

资源类别:文库,文档格式:PDF,文档页数:41,文件大小:1.86MB,团购合买
 归纳  数学归纳法  强数学归纳法  运用良序公理来证明  递归  递归定义  结构归纳法  递归算法
点击下载完整版文档(PDF)

归纳与递归 离散数学一归纳与递归 南京大学计算机科学与技术系

归纳与递归 离散数学─归纳与递归 南京大学计算机科学与技术系

内容提要 ·归纳 ·数学归纳法 ·强数学归纳法 ●运用良序公理来证明 ·递归 ●递归定义 ·结构归纳法 。递归算法

内容提要  归纳  数学归纳法  强数学归纳法  运用良序公理来证明  递归  递归定义  结构归纳法  递归算法

数学归纳法 ●证明目标 ●VnP(n) n的论域为正整数集合 。证明框架 。基础步骤:P(1)为真 ●归纳步骤:证明k(P(k)→Pk+1) 。/对任意正整数k,给出P()上P(k+1)的论证步骤. ●… 。因此,对任意正整数n,P(n)成立.∥即:nP(n)

数学归纳法 

数学归纳法(有效性) ●良序公理 。正整数集合的非空子集都有一个最小元素 ·数学归纳法的有效性(归谬法) ●假设VnP(n)不成立,则n(P(n)成立, 。令S={neZ|P(nm)},S是非空子集, 。根据良序公理,S有最小元素,记为m,≠1 ●(m-1)eS,即P(m-1)成立. ●根据归纳步骤,P(m成立,即mS,矛盾 。因此,HnP(n)成立

数学归纳法(有效性)  良序公理  正整数集合的非空子集都有一个最小元素  数学归纳法的有效性(归谬法)  假设n P(n)不成立,则 n (P(n))成立.  令S={ n+ | P(n)},S是非空子集.  根据良序公理,S有最小元素,记为m, m1  (m-1)S, 即P(m-1)成立.  根据归纳步骤,P(m)成立,即mS,矛盾.  因此,n P(n)成立

数学归纳法(举例) 。Hk=1+1/2+..+1/k(k为正整数) ● 证明:H,"≥1+n/2(n为正整数) 。基础步骤:P(1)为真,H2=1+1/2 。归纳步骤:对任意正整数k,P)→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)成立

数学归纳法(举例)  Hk=1+1/2+…+1/k (k为正整数)  证明:H2 n 1+n/2 (n为正整数)  基础步骤:P(1)为真, H2=1+1/2  归纳步骤:对任意正整数k, P(k) P(k+1). H2 k+1 = H2 k +1/(2k+1)+…+1/2k+1 (1+k/2)+2k (1/2k+1) =1+(1+k)/2  因此,对任意正整数n, P(n) 成立

数学归纳法(举例) ·猜测前个奇数的求和公式,并证明之。 。1=1 01+3=4 ●1+3+5=9 。1+3+5+7=16 。。。 ●1+3+..+(2n-1)=n2(n为正整数) ●运用数学归纳法证明(练习)

数学归纳法(举例)  猜测前n个奇数的求和公式,并证明之。  1=1  1+3=4  1+3+5=9  1+3+5+7=16  …  1+3+…+(2n-1)=n2(n为正整数)  运用数学归纳法证明(练习)

运用数学归纳法时犯的错误 平面上任何一组相互间不平行的直线必相交于一点. ●基础步骤:P(2)为真 。归纳步骤:对任意正整数k,P()上Pk+1) 。前k条交于P1 。后k条交于P2 0P1=P2

运用数学归纳法时犯的错误 

数学归纳法证明时常见错误 例1:任意个人,他们一定全部在同一天出生. 错误证明: o Basis:当n=1时,只有一个人,命题显然成立; IH:假设任意k个人,他们全部在同一天出生,则: oI.S.:当有k+1个人时(编号为1,2,…,k,k+1),根据 归纳假设,第1人至第k人(共k个人)一定在同一天出 生;第2至第k+1人(共k个人)也一定在同一天出生。 因此,这k+1人全部在同一天出生。根据数学归纳法, 命题成立.口 o归纳基础错误:P(1)rP(2)川

数学归纳法证明时常见错误

数学归纳法证明时常见错误 例2:证明∑12i-1=n2 错误证明: Basis:当n=1时,=12i-1=12命题成立; I.H.:假设当n=k时∑12i-1=k2成立,则: 。I.S.:根据等差数列的求和公式,∑12i-1=1+3+ 5+…+2(k+1)-1=1+2k+)-k+=(k+1)2。 2 根据数学归纳法,命题成立.口 o归纳过程错误:未证明P(k)→P(k+1)!

数学归纳法证明时常见错误

强数学归纳法 ●证明目标 ●廿nP(n)n的论域为正整数集合 ·证明框架 。基础步骤:P(1)为真 ●归纳步骤:证明k(P(1)A·AP(k)→P(k+1) 。/对任意正整数k,给出P(1),,P(上P(k+1)的论证步骤 ●… 。因此,对任意正整数n,P(n)成立.∥即:廿nP(n)

强数学归纳法 

点击下载完整版文档(PDF)VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
共41页,可试读14页,点击继续阅读 ↓↓
相关文档

关于我们|帮助中心|下载说明|相关软件|意见反馈|联系我们

Copyright © 2008-现在 cucdc.com 高等教育资讯网 版权所有