复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）07/30

定理(二):设S是自然数集N的非空子集, 如果0∈S,且当n∈S时,必有n+1∈S,则 S=N。 定理(三):设S是自然数集N的非空子集, 如果0∈S,且当0,1,2,n∈S时,必有n+1eS, 则S=N 数学归纳法,有两种形式: 1)第一数学归纳法 要证一个结论对所有自然数都真,只须做两件 事:1)当m=0时,结论成立。 2)若当m=k结论成立,则当n=k+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时,结论成立。 ②若当nk结论成立,则当n=k+1结论也成立 定理(四):设P(n)是一个与自然数n有关 的结论。若对于自然数0,结论成立;并 且当对自然数k结论成立时,对于自然数 k+结论也成立,则该结论对所有自然数 都成立

(2)第二数学归纳法 要证一个结论对所有自然数都真，只须做两件 事： ①当n=0时，结论成立。 ②若当nk结论成立，则当n=k+1结论也成立 定理(四)：设P(n)是一个与自然数n有关 的结论。若对于自然数0，结论成立；并 且当对自然数k结论成立时，对于自然数 k+1结论也成立，则该结论对所有自然数 都成立

定理(五):设P(n)是一个与自然数n有关 的结论。若对于自然数0,结论成立;并 且当对自然数0,1,2,k结论成立时,对 于自然数k+1结论也成立,则该结论对所 有自然数都成立

定理(五)：设P(n)是一个与自然数n有关 的结论。若对于自然数0，结论成立；并 且当对自然数0,1,2,k结论成立时，对 于自然数k+1结论也成立，则该结论对所 有自然数都成立

二、集合的递归定义 定义41:集合A的递归(归纳)定义由三部 分组成: (1)基础设置某些对象是在所要定义的集 合A中的 元素产生A中新元素的方法A的现有 (2)归纳(递归):建立一种由集合 (3)闭合:除了有限次应用1)和(2)产生集 合A的元素外,A中再没有其它元素

二、集合的递归定义 定义4.1:集合A的递归(归纳)定义由三部 分组成: (1)基础:设置某些对象是在所要定义的集 合A中的 (2)归纳(递归):建立一种由集合A的现有 元素产生A中新元素的方法。 (3)闭合：除了有限次应用(1)和(2)产生集 合A的元素外,A中再没有其它元素

例:设整数集Z是全集,非负偶整数集 E+={xx三0,且x=2y,y∈Z},它可以递归定义如下: (1)(基础)0∈E十。 (2)(归纳)如果n∈E则n+2∈E (3)(闭合)除有限次应用(1)和(2)产生的整数外再 没有其它的整数在E+中。 例:下面的归纳定义所给出的是怎样的集合? (1)(基础)3∈S。 (2)(归纳)如果xy∈S,则x+yeS。 (3)(闭合)除有限次应用(1)和(2)产生的整数外,再 没有其它的整数在S中。 3的正整数倍全体

例 ： 设 整 数 集 Z 是全集 , 非 负 偶 整 数 集 E+={x|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的正整数倍全体

设∑是一个有限非空字符集称为字母表 从∑中选取有限个字符组成的串称为∑上 的字符我或字。 设x是∑上的一个字,x=a12a2,an,其中 a1∈∑1sin,n是正整数表示字的长度。 长度为0的字称为空生记为。 若xy是∑上的两个字,x=a1a2,an, y=b1b2…!bm其中a,b∈∑(三isn, 1三jm,则由x和毗连得到新的字记为 xy。即:xy=a1a2,anbb2bmo

设Σ是一个有限非空字符集,称为字母表。 从Σ中选取有限个字符组成的串称为Σ上 的字符串或字。 设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∈∑,则ax∈(ax表示 字符a与字x毗连得到的新的字。 (3)闭合)除有限次应用(1)和(2)产生∑中的 字外,∑+中再没有其它字。 集合∑包含长度为1,2,3,的字,即∑包含 无限个字,但每个字的字符个数是有限的

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

例:设∑是一个字母表,∑上所有的有限字 符串集合记为∑,包含空串,即 ∑*=∑+∪{},可递归定义如下: 1)(基础∈∑。 (2)(归纳)如果x∈∑,且a∈∑,则ax∈∑。 (3)(闭合除有限次应用(1)和(2产生∑中的 字外,∑中再没有其它字。 例如,若∑={0,1},则∑=,0,1,0001 10,1,00001是有限二进制序列的集 合,其中包含空序列

例:设Σ是一个字母表, Σ上所有的有限字 符 串 集 合 记 为 Σ* ,Σ* 包 含 空 串 ， 即 Σ*=Σ+∪{},可递归定义如下: (1)(基础)Σ* 。 (2)(归纳)如果xΣ* ,且aΣ,则axΣ* 。 (3)(闭合)除有限次应用(1)和(2)产生Σ*中的 字外, Σ*中再没有其它字。 例 如 , 若 Σ={0,1}, 则 Σ*={,0,1,00,01, 10,11,000,001…},是有限二进制序列的集 合, 其中包含空序列

算术表达式集合是包含整数,一元运算符 +,以及二元运算符+,,,/的符号序列所 组成的集合, (3+5)/4) ((5)+6)*3)

算术表达式集合是包含整数, 一元运算符 +,-, 以及二元运算符+,-,* ,/的符号序列所 组成的集合, ((3+5)/4), (((-5)+6)*3)

算术表达式集合的递归定义如下: (1)(基础)如果D={0,1,2,3,456,7,8,9}和 x∈D+,则x是算术表达式。其中D是D上 所有非空数字申的集合。 (2)(归纳如果x和y都是算术表达式,则 (+x)是算术表达式;(-x)是算术表达式; (x+y)是算术表达式;(x-y)是算术表达式; (x*y)是算术表达式;(x/y)是算术表达式。 (3)(闭合)一个符号序列是一个算术表达式 当且仅当它能通过有限次应用(1)和(2)而 得到

算术表达式集合的递归定义如下: ( 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)是算术表达式; (x/y)是算术表达式。 (3)(闭合)一个符号序列是一个算术表达式 当且仅当它能通过有限次应用(1)和(2)而 得到