定理（二）设S是自然数集N的非空子集,如果0S,且.ppt

《定理（二）设S是自然数集N的非空子集,如果0S,且.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、定理(二)：设S是自然数集N的非空子集，如果0S，且当nS时，必有n+1S，则S=N。定理(三)：设S是自然数集N的非空子集，如果0S，且当0,1,2,nS时，必有n+1S，则S=N。数学归纳法，有两种形式：(1)第一数学归纳法要证一个结论对所有自然数都真，只须做两件事：1)当n=0时，结论成立。2)若当n=k结论成立，则当n=k+1结论也成立。(2)第二数学归纳法要证一个结论对所有自然数都真，只须做两件事：①当n=0时，结论成立。②若当nk结论成立，则当n=k+1结论也成立定理(四)：设P(n)是一个

2、与自然数n有关的结论。若对于自然数0，结论成立；并且当对自然数k结论成立时，对于自然数k+1结论也成立，则该结论对所有自然数都成立。定理(五)：设P(n)是一个与自然数n有关的结论。若对于自然数0，结论成立；并且当对自然数0,1,2,k结论成立时，对于自然数k+1结论也成立，则该结论对所有自然数都成立。二、集合的递归定义定义4.1:集合A的递归(归纳)定义由三部分组成:(1)基础:设置某些对象是在所要定义的集合A中的(2)归纳(递归):建立一种由集合A的现有元素产生A中新元素的方法。(3)闭合：除了有限次应用(1)和

3、(2)产生集合A的元素外,A中再没有其它元素。例：设整数集Z是全集,非负偶整数集E+={x

4、x≧0,且x=2y,yZ},它可以递归定义如下:(1)(基础)0E+。(2)(归纳)如果nE+,则n+2E+。(3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在E+中。例：下面的归纳定义所给出的是怎样的集合？(1)(基础)3S。(2)(归纳)如果x,yS,则x+yS。(3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在S中。3的正整数倍全体。设Σ是一个有限非空字符集,称为字

5、母表。从Σ中选取有限个字符组成的串称为Σ上的字符串或字。设x是Σ上的一个字,x=a1a2…an,其中aiΣ,1≦i≦n,n是正整数,表示字的长度。长度为0的字称为空串,记为。若x,y是Σ上的两个字,x=a1a2…an,y=b1b2…bm,其中ai,bjΣ(1≦i≦n,1≦j≦m),则由x和y毗连得到新的字记为xy。即:xy=a1a2…anb1b2…bm。例:设Σ是一个字母表,Σ上所有的有限非空字符串集合记为Σ+,递归定义如下:(1)(基础)如果aΣ,则aΣ+。(2)(归纳)如果xΣ+,且aΣ,则axΣ+

6、(ax表示字符a与字x毗连得到的新的字。(3)(闭合)除有限次应用(1)和(2)产生Σ+中的字外,Σ+中再没有其它字。集合Σ+包含长度为1,2,3,…的字,即Σ+包含无限个字,但每个字的字符个数是有限的。例:设Σ是一个字母表,Σ上所有的有限字符串集合记为Σ*,Σ*包含空串，即Σ*=Σ+∪{},可递归定义如下:(1)(基础)Σ*。(2)(归纳)如果xΣ*,且aΣ,则axΣ*。(3)(闭合)除有限次应用(1)和(2)产生Σ*中的字外,Σ*中再没有其它字。例如,若Σ={0,1},则Σ*={,0,1,00,01,

7、10,11,000,001…},是有限二进制序列的集合,其中包含空序列。算术表达式集合是包含整数,一元运算符+,-,以及二元运算符+,-,*,/的符号序列所组成的集合,((3+5)/4),(((-5)+6)*3)算术表达式集合的递归定义如下:(1)(基础)如果D={0,1,2,3,4,5,6,7,8,9}和xD+,则x是算术表达式。其中D+是D上所有非空数字串的集合。(2)(归纳)如果x和y都是算术表达式,则(+x)是算术表达式;(-x)是算术表达式;(x+y)是算术表达式;(x-y)是算术表达式;(x*y)是算术表

8、达式;(x/y)是算术表达式。(3)(闭合)一个符号序列是一个算术表达式当且仅当它能通过有限次应用(1)和(2)而得到。后继集合的概念:设A是任一给定集合,A∪{A}称为A的后继集合,简称后继,记为A+。定义4.2:设N为自然数集,它的递归定义如下:(1)(基础)N。(2)(归纳)如果nN,则n+N(这里n+=n∪{n})。(3)(闭合)如果SN,且S满足(1)、(2)则S=N。自然数集的元素为:,+,(+)+,((+)+)+,…,即为:,∪{},∪{}∪{∪{}}…可以简化为:,{

9、},{,{}},…用记号:=给这些集合命名例如命名为0,记为0:=0:=;1:=0+={}={0};2:=1+={,{}}={0,1};3:=2+={,{},{,{}}}={0,1,2}…若已给出n,则n+1:=n+={0,1,2,…,n}定理4.1:(1)0不是任何自然数的后继。(2)任何自然数的后继是唯