复旦大学计算机院赵一鸣离散数学中文课件

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

2、论对所有自然数都成立。2定理(五)：设P(n)是一个与自然数n有关的结论。若对于自然数0，结论成立；并且当对自然数0,1,2,k结论成立时，对于自然数k+1结论也成立，则该结论对所有自然数都成立。3二、集合的递归定义定义4.1:集合A的递归(归纳)定义由三部分组成: (1)基础:设置某些对象是在所要定义的集合A中的 (2)归纳(递归):建立一种由集合A的现有元素产生A中新元素的方法。 (3)闭合：除了有限次应用(1)和(2)产生集合A的元素外,A中再没有其它元素。4例：设整数集Z是全集,非负偶整数集E+=x|x0,且x=2y,yZ,它可以递归定义如下:(1)(基础)0E+。(2)(归纳)如果n

3、E+,则n+2E+。(3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在E+中。例：下面的归纳定义所给出的是怎样的集合？ (1)(基础)3S。(2)(归纳)如果x,yS,则x+yS。(3)(闭合)除有限次应用(1)和(2)产生的整数外,再没有其它的整数在S中。 3的正整数倍全体。5设是一个有限非空字符集,称为字母表。从中选取有限个字符组成的串称为上的字符串或字。设x是上的一个字, x=a1a2an,其中ai,1in,n是正整数,表示字的长度。长度为0的字称为空串,记为。若x,y是上的两个字,x=a1a2an, y=b1b2bm,其中ai,bj(1in, 1jm),则由x和y

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

5、字外, *中再没有其它字。例如,若=0,1, 则*=,0,1,00,01, 10,11,000,001,是有限二进制序列的集合, 其中包含空序列。8算术表达式集合是包含整数, 一元运算符+,-, 以及二元运算符+,-,* ,/的符号序列所组成的集合, (3+5)/4),(-5)+6)*3)9算术表达式集合的递归定义如下:(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)是

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

7、2 若已给出n, 则n+1:=n+=0,1,2,n12定理4.1:(1)0不是任何自然数的后继。(2)任何自然数的后继是唯一的。(3)如果n+=m+,则n=m。贝安诺(Peano)公理(1)0N;(2)对每一个nN,恰存在一个n+N(称n+为n的后继);(3)不存在一个nN,使n+=0;(4)如果n+=m+, 则n=m;(5)如果SN,且0S;如果nS,有n+S, 则S=N。134.2 基数一、基数概念在棋盘的第一个方格内放一粒米，以后每一小格内都比前一小格加一倍，最后摆满所有64格1+2+22+263=264-1约合140亿升所有整数的个数，一条线上所有几何点个数(即区间a,b上 个数)14

8、比较一堆珠子和一堆铜币哪个多，把珠子和铜币逐个比较，最后看哪堆有多余，若同时没有则两者相同。定义4.3：设A,B是任意两个集合,若存在一个双射f:AB,则称A和B对等(或等势),记为 AB;或称A和B的基数相同。A的基数记为|A|;A和B的基数相同记为|A|=|B|15二、无限集定义4.4：设A为一个集合, 若A为空集或与集合0,1,2,n-1的基数相同, 则称A为有限集,且|A|=nN。若集合A不是有限集, 则称A为无限集。定理4.2:自然数集N是无限集。没有一个自然数能作为N的基数,因此今后将记|N|为0,读作阿列夫零。 16定理4.2:自然数集N是无限集。即证明N不是有限集.关键证明对任

9、何nN，不存在从0,1,2,n-1到N的双射。证明：设n是N中任一元素，f是从0,1,2,n-1到N的任一函数，没有一个自然数能作为N的基数,因此今后我们将记|N|为0,读作阿列夫零。 17例:设N与Z之间有如下一一对应:N: 0,1, 2,3, 4,5, 6,Z: 0,1,-1,2,-2,3,-3,即存在双射f:NZ,使对nN,所以|Z|=0。18例:设E=0,2,4, 因为存在f: NE,对任何nN有f(n)=2n , 显然f是NE的双射。这里E是N的真子集,然而|E|=|N|=0。这一事实揭示了无限集的一个重要特征:即无限集可以与它的一个真子集对等。19定理4.3:无限集必与它的一个真子

10、集对等。证明：基本思路A是构造一个真子集,然后证明两者之间存在双射推论:凡不能与自身的任一真子集对等的集合为有限集。凡能与自身的某一真子集对等的集合称为无限集,否则称为有限集。前面的例子和定理说明了这样的事实：在无穷大的世界里，部分可能等于全部。那么是否无穷大数都是相等的？204.3 可列集与不可列集定义4.5：若存在从N到A的双射, 则称A为可列无限集, 简称可列集或可数集, |A|=0。定理(一)：设A是可列集, 若存在从A到B的双射,则B也是可列集。目标证明存在N到A的双射.21定理(二)：集合A是可列集的充要条件是集合A中的元素可以排成一个无穷序列的形式:a0,a1,a2,a3,a4,。利用自然数有序性目标证明存在N到A的双射。定理4.4：任何无限集必含有一个可列子集。采用构造方法,从无限集中构造一个无穷序列22定理4.5：可列集的任何无限子集必为可列集。定理4.6：可列集中加入有限个元素(或删去有限个元素), 仍为可列集。23作业:P76 1,补充:证明定理(五)：设P(n)是一个与自