1、 定理 (二 )：设 S是自然数集 N的非空子集 ， 如果 0S， 且当 nS时 ， 必有 n+1S， 则 S=N。 定理 (三 )：设 S是自然数集 N的非空子集，如果 0S， 且当 0,1,2, nS时，必有 n+1S，则 S=N。 数学归纳法 ， 有两种形式： (1)第一数学归纳法 要证一个结论对所有自然数都真 ， 只须做两件事： 1)当 n=0时 ， 结论成立 。 2)若当 n=k结论成立 ， 则当 n=k+1结论也成立 。 (2)第二数学归纳法 要证一个结论对所有自然数都真 ， 只须做两件事： 当 n=0时 ， 结论成立 。 若当 nk结论成立 ， 则当 n=k+1结论也成立 定理
2、(四 )：设 P(n)是一个与自然数 n有关的结论 。 若对于自然数 0， 结论成立；并且当对自然数 k结论成立时 ， 对于自然数k+1结论也成立 ， 则该结论对所有自然数都成立 。 定理 (五 )：设 P(n)是一个与自然数 n有关的结论 。 若对于自然数 0， 结论成立；并且当对自然数 0,1,2, k结论成立时 ， 对于自然数 k+1结论也成立 ， 则该结论对所有自然数都成立 。 二、集合的递归定义 定义 4.1:集合 A的递归 (归纳 )定义由三部分组成 : (1)基础 :设置某些对象是在所要定义的集合 A中的 (2)归纳 (递归 ):建立一种由集合 A的现有元素产生 A中新元素的方法
3、。 (3)闭合：除了有限次应用 (1)和 (2)产生集合 A的元素外 ,A中再没有其它元素。 例：设整数集 Z是全集 ,非负偶整数集E+=x|x 0,且 x=2y,yZ,它可以递归定义如下 : (1)(基础 )0E+。 (2)(归纳 )如果 nE+,则 n+2E+。 (3)(闭合 )除有限次应用 (1)和 (2)产生的整数外 ,再没有其它的整数在 E+中 。 例：下面的归纳定义所给出的是怎样的集合 ？ (1)(基础 )3S。 (2)(归纳 )如果 x,yS,则 x+yS。 (3)(闭合 )除有限次应用 (1)和 (2)产生的整数外 ,再没有其它的整数在 S中 。 3的正整数倍全体 。 设 是一
4、个有限非空字符集 ,称为 字母表 。 从 中选取有限个字符组成的串称为 上的 字符串 或 字 。 设 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 an b1b2 bm。 例 :设 是一个字母表 , 上所有的有限非空字符串集合记为 +,递归定义如下 : (1)(基础 )如果 a,则 a+。 (2)(归纳 )如果 x+,且 a,则
5、 ax+(ax表示字符 a与字 x毗连得到的新的字 。 (3)(闭合 )除有限次应用 (1)和 (2)产生 +中的字外 , +中再没有其它字 。 集合 +包含长度为 1,2,3, 的字 ,即 +包含无限个字 , 但每个字的字符个数是有限的 。 例 :设 是一个字母表 , 上所有的有限字符串集合记为 *,* 包含空串 ， 即*=+ ,可递归定义如下 : (1)(基础 )*。 (2)(归纳 )如果 x*,且 a,则 ax*。 (3)(闭合 )除有限次应用 (1)和 (2)产生 *中的字外 , *中再没有其它字 。 例如 , 若 =0,1, 则 *=,0,1,00,01, 10,11,000,001
6、 ,是有限二进制序列的集合 , 其中包含空序列 。 算术表达式集合是包含整数 , 一元运算符+,-, 以及二元运算符 +,-,* ,/的符号序列所组成的集合 , (3+5)/4), (-5)+6)*3) 算术表达式集合的递归定义如下 : ( 1 )(基础 )如果 D=0,1,2,3,4,5,6,7,8,9和xD+ ,则 x是算术表达式 。 其中 D+是 D上所有非空数字串的集合 。 (2)(归纳 )如果 x和 y都是算术表达式 , 则 (+x)是算术表达式 ; (-x)是算术表达式 ; (x+y)是算术表达式 ; (x-y)是算术表达式 ; (x*y)是算术表达式 ; (x/y)是算术表达式 。 (3)(闭合 )一个符号序列是一个算术表达式当且仅当它能通过有限次应用 (1)和 (2)而得到 。
