第2章集合.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 集 合,第二章 集 合,2.1 集合论的基本概念,2.2 集合上的运算,2.3 归纳法和自然数,2.4 语言上的运算,2.5 集合的笛卡儿乘积,2.1 集合论的基本概念,2.1.1 集合的概念,集合在某些场合又称为,类,、,族,或,搜集,它是数学中最基本的概念之一,如同几何中的“点”、“线”等概念一样,不可精确定义,现描如下:一个,集合,是能作为整体论述的事物的集体。如;,(1)“高二(1)班的学生”是一集合。;,(2)硬币有两面正面和反面,“正面、反面”构成一集合。;,(3)计算机内存之全体单元构成一集合。;,(4)1,2,3,n,构成正整数集合。;,(5)所有三角形构成三角形集合。;,(6)坐标满足方程,x,2,+,y,2,R,2,的全部点构成图 2.1-1所示的点集。,图 2.1-1,组成集合的每个事物叫做这个集合的,元素,或,成员,。,通常用大写字母,A,B,C,代表集合;用小写字母,a,b,c,代表元素。,如果,a,是集合,A,的一个元素,则记为,a,A,读做“,a,属于,A,”,或说“,a,在,A,中”。;,如果,a,不是集合,A,的一个元素,则记为,a A,读做“,a,不属于,A,”,或说“,a,不在,A,中”。;,任一元素,对某一集合而言,或属于该集合,或不属于该集合,二者必居其一,不可兼得。,通常采用3种方法表示集合。;,第一种是列举法。就是把集合中的元素一一列举出来。例如“所有小于5的正整数”这个集合的元素为1,2,3,4,除这4个元素外,再没有别的元素了。如果把这个集合命名为A,就可记为,A,=1,2,3,4,在能清楚表示集合成员的情况下可使用省略号,例如,从1 到50 的整数集,合可记为1,2,3,50,偶数集合可记为,-4,-2,0,2,4,。,外延公理,两个集合,A,和,B,相等,即,A,=,B,当且仅当它们有相同的成员(也就是,A,的每一元素是,B,的一个元素而,B,的每一元素也是,A,的一个元素)。;,用逻辑符号表达是:,或,外延公理断言:,如果两个集合有相同的元素,那么不管集合是如何表示的,它们都相等。因此,(1)列举法中,元素的次序是无关紧要的。例如,x,y,z,与,z,x,y,相等。,(2)元素的重复出现无足轻重。例如,x,y,x,、,x,y,、,x,x,x,y,是相同的集合。,(3)集合的表示不是唯一的。例如,x,|,x,2,-3,x,+2=0、,x,|,x,I,1,x,2 和1,2均表示同一集合。,2.1.2 罗素悖论,1901年罗素(Bertrand Russell)提出以下悖论:设论述域是所有集合的集合,并定义,S,为下述集合,这样,S,是不以自身为元素的全体集合的集合,我们现在问“,S,是不是它自己的元素?”;,假设,S,不是它自己的元素,那么,S,满足谓词,A A,而该谓词定义了集合,S,所以,S,S,。另一方面,如果,SS,那么,S,必须满足定义,S,的谓词,所以,SS,。,这样,我们导致了一个类似于谎言悖论的矛盾:既非,S,S,也非,SS,是真。一个“集合”,诸如,S,它能导致矛盾的称为,非良定的,。,罗素悖论起因于不受限制的定义集合的方法,特别,集合可以是自己的元素的概念值得怀疑。康脱以后创立的许多公理化集合论都直接地或间接地限制集合成为它自己的元素,因而避免了罗素悖论。,公理化集合论用某个方法避免了罗素悖论,但怎能确信没有其它悖论潜伏在这些形式结构中呢?回答是悲观的,业已证明,应用现今有效的数学技术,没有方法能证明新的悖论不会产生。,2.1.3 集合间的包含关系,定义2.1-1 设,A,和,B,是集合,如果,A,的每一元素是,B,的一个元素,那么,A,是,B,的,子集合,记为,AB,读做“,B,包含,A,”或“,A,包含于,B,中。,用逻辑符表示为:,有时也记作 ,称,B,是,A,的,扩集,。,定义2.1-2,如果,AB,且,A,B,那么称,A,是,B,的,真子集,记作,AB,读作“,B,真包含,A,”。;,用逻辑符表示为:,要注意区分从属关系“”及包含关系“”。从属关系是集合元素与集合本身的关系,包含关系是集合与集合之间的关系。,定理 2.1-1,对任意集合,A,有,证,对任意元素,x,x,U,是真,所以,是真。由全称推广规则得,所以,(这是一个平凡证明的例子),定理 2.1-2,设,A,和,B,是集合,A,=,B,当且仅当,AB,和,BA,。,证,推论 2.1-2,对任何集合,A,恒有,A,A,。;,定理 2.1-3,设,A、B、C,是集合,若,AB,且,BC,则,AC,。,证,设,x,是论述域中任意元素,因为,所以,x,A,x,B,=,x,B,x,C,由前提三段论得,x,A,x,C,由全称推广规则得,即,定义 2.1-3,没有元素的集合叫空集或零集,记为。,定理 2.1-4,对任意集合,A,有 。,证,设,x,是论述域中任意元素,则,常假,所以,无义地真，由全称推广规则得,即,定理,2.1-5 空集是唯一的。,证,设和 都是空集,由定理2.1-4得 和 ,根据定理2.1-2得 。,注意与不同,后者是以空集为元素的一个集合,前者没有元素。,能用空集构造不同集合的无限序列。在序列,中,每一集合除第一个外都确实有一元素,即序列中前面的集合。在序列,中,如果我们从0开始计算,则第i项有i个元素。这一序列的每一集合,以序列中在它之前的所有集合作为它的元素。,例 1,(a)集合,p,q,有4个不同子集:,p,q,、,p,、,q,和,注意,p,p,q,但,p,p,q,p,p,q,但,p,p,q,。再者,p,q,但,(b)集合,q,是单元素集合,它的唯一元素是集合,q,。每一单元素集合恰有两个子集,q,的子集是,q,和 。,一般地,n,个元素的集合有2,n,个不同的子集合.,2.2 集合上的运算,2.2.1 并、交和差运算,;,定义 2.2-1,设,A,和,B,是集合。,(,a,),A,和,B,的并记为,A,B,是集合。,A,B,=,x,|,x,A,x,B,(b),A,和,B,的交记为,A,B,是集合。,A,B,=,x,|,x,A,x,B,(c),A,和,B,的差,或,B,关于,A,的相对补,记为,A,-,B,是集合。,A,-,B,=,x,|,x,A,x,B,例 1,设,A,=,a,b,c,d,)和,B,=,b,c,e,那么,A,B,=,a,b,c,d,e,A,B,=,b,c,;,A-B,=,a,d,;,B-A,=e,定义 2.2-2,如果,A,和,B,是集合,A,B,=,那么称,A,和,B,是不相交的。如果,C,是一个集合的族,使,C,的任意两个不同元素都不相交,那么,C,是(两两)不相交集合的族。;,例 2,如果,C,=0,1,2,=,i,|,i,N,那么,C,是不相交集合的族。,定理 2.2-1,集合的并和交运算是可交换和可结合的。也就是对任意,A、B,和,C,。;,(a),A,B,=,B,A,;,(b),A,B,=,B,A,;,(c)(,A,B,),C,=,A,(,B,C,);,(d)(,A,B,),C,=,A,(,B,C,);,我们仅证明(a)和(c),(b)和(d)是类似的。,证,(,a,)设,x,是论述域,U,的任意元素,那么,的定义,的可交换性,的定义,因为,x,是任意的,得,即,A,B,=,B,A,(,c,)设,x,是任意元素,那么,xA(BC)xAx(BC)的定义,xA(xBxC)的定义,(xAxB)xC 的结合律,x(AB)xC 的定义,x(AB)C 的定义,因为x是任意的,得出,x(xA(BC)x(AB)C),因此,A(BC)=(AB)C。,定理 2.2-2,对任意集合,A、B,和,C,有:;,(,a,)A(BC)=(AB)(AC);,(,b,)A(BC)=(AB)(AC)=,即集合运算和,在上可分配,在上可分配。;,证,设,x,是任意元素,那么,xA(BC)xAx(BC)的定义,xA(xBxC)的定义,(xAxB)(xAxC)在上可分配,(xAB)(xAC)的定义,x(AB)(AC)的定义,因此,A(BC)=(AB)(AC)。,定理 2.2-3,设,A、B、C,和,D,是论述域,U,的任意子集合,那么下列断言是真:;,(a)AA=A;,(b)AA=A;,(c)A=A;,(d)A=;,(e)A-=A;,(f)A-BA;,(g)如果AB和CD,那么,(AC)(BD);,(h)如果AB和CD,那么,(AC)(BD);,(i)AAB;,(j)ABA;,(k)如果AB,那么,AB=B;,(l)如果AB,那么,AB=A,(g)设x是AC的任意元素,那么xAxC。现在分情况证明。,情况1:设xA,因为AB,得xB,所以xBxD,因此xBD。,情况2:设xC,用与情况1相似的论证得xBD。因此,xAC,那么xBD。所以ACBD。,(k)因AB,又BB根据(g)得ABBB,但BB=B,因此ABB。另一方面由(i)得BAB。所以,AB=B。,推论2.2-3,(a)AU=U,(b)AU=A。;,本推论可由定理2.2-3的(k)(l)部分得出。;,2.2.2 补运算,定义2.2-3 设,U,是论述域而,A,是,U,的子集。,A,的(绝对)补,记作,A,是集合。,例 3,(a)如果,U,=,p,q,r,s,和,A,=,p,q,那么,A,=r,s。,(b)如果,U,=,N,和,A,=,x,|,x,0,那么,A,=0。,(c)如果,U=I,和A=2x+1|xI,那么,A,=2,x,|,x,I,。,定理 2.2-4,设,A,是某论述域U的任意子集,那么,证,定理 2.2-5,(补的唯一性)设,A,和,B,是论述域,U,的子集,那么,B=A,当且仅当,A,B,=,U,和,A,B,=。,证,必要性从定理 2.2-4 直接得到。现证明充分性。;,设,A,B,=和,A,B,=,U,那么,B,=,U,B,=(,A,),B,=(,A,B,)(,B,),=(,B,),=(,A,)(,B,),=(,A,B,),=,U,=,推论2.2-5,证,因,U,=,U,和,U,=,所以,。,定理 2.2-6,设,A,是,U,的任意子集,那么 。也就是说,A,的补的补是,A,。,证,因为 ,A,=,U,和 ,A,=,根据上一定理,A,是 的补,但,A,也是的补,而补是唯一的,所以,。,定理2.2-7,(德摩根定律)设,A,和,B,是,U,的任意子集,那么,证,(,a,),根据定理2.2-5,是,A,B,的补,但AB也是AB的补,而补是唯一的,所以,(,b,)的证明是类似的,故略。,定理 2.2-8,设,A,、,B,是,U,的任意子集,若,证,根据逆反律得,x,是任意的,所以,图 2.2-1,另外,根据并、交、补等定义,亦知命题演算中的、,T,、,F,等分别与集合论中的、-、,U,、等有对应关系,因此,有关它们的公式也有相似性。例如命题演算中有公式,(,P,Q,),P,Q,P,T,P,集合论中有对应公式,又如命题演算中有范式等概念,P,Q,R,(,P,Q,R,)(,P,Q,R,)(,P,Q,R,),如果需要,在集合论中也可引入范式等概念,使,ABC=(ABC)(ABC)(ABC),2.2.3 并和交运算的扩展,扩展后并和交运算都定义在集合的搜集上。;,定义 2.2-4,设,C,是某论述域子集的搜集。;,(,a,),C,的成员的并、记为 ,是由下式指定的集合,(,b,)如果,C,C,的成员的交,记为 ,是下式指定的集合,定义说明如果 ,那么,x,至少是一个子集,S,C,的元素;如果 ,那么,x,是每一个子集,S,C,的元素。注意对 的定义来说,C,必须非空,否则,由于 ,蕴含式SCxS对每一S将是无义地真。这样,谓词 s(SCxS)对每一x是真。因此,所定义的集合就是全集合U。要求 ,这个可能消除。,设,D,是一集合,如果给定,D,的任一元素,d,就能确定一个集合,A,d,那么,d,叫做,A,d,的索引,搜集,C,=,A,d,|,d,D,叫做集合的加索引搜集;而,D,叫做搜集的索引集合。当,D,是一个搜集,C,的索引集合,符号 表示 ,而 表示 。,如果加索引搜集,C,的索引集合是前,n,+1个自然数0,1,2,n,或全体自然数0,1,2,那么,C,的成员的并和交能用类似于和式概念的符号表示。例如,一般地,索引集合不必须是,N,的子集,可以是任意集合,例如R,+,。,例4,设论述域是实数,R,。;,(,a,)如果,C,=1,2,4,3,4,5,4,6,那么 =1,2,3,4,5,6和 。,(,b,)我们用0,a,)表示集合,x,|0,x,a,。,如果,S,a,=0,a,),a,R,+,C,=,S,a,|,a,R,+,那么,如果,S,a,=0,a,),a,I,+,C,=,S,a,|,a,I,+,那么,(,c,)设,C,=,A,i,|,i,p,q,r,其中,A,p,=2,3,A,q,=3,4,A,r,=4,6;,a,b,表示,x,|,a,x,b,那么,2.2.4 环和与环积,定义 2.2-5,A、B,两集合的,环和,A,B,是集合,参看图 2.2-2。环和又叫对称差(Symmetric Difference)。,定理 2.2-9,证,因为,但,所以,推论 2.2-9,定理 2.2-10,定理 2.2-11,以上两个定理留给读者自证。但注意并在环和上不可分配,环和在交上不可分配。即,通常,定义 2.2-6,A,、,B,两集合的环积,A,B,是集合,图 2.2-2,定理 2.2-12,定理 2.2-13,证,所以,根据定理2.2-10 得,两边取补,即得,定理 2.2-14,请读者自证,2.2.5 幂集合,定义 2.2-7,设,A,是一集合,A,的,幂集,(,A,),是,A,的所有子集的集合,即,一个给定集合的幂集是唯一的,因此求一个集合的幂集是以集合为运算对象的一元运算。,例 5,(,a,)如果,A,=,那么,(,A,)=。,(,b,)如果,A,=,a,b,那么,(,A,)=,a,b,a,b,。,(,c,)如果A是任意自然数集合,那么,A,(,A,),(,A,)。,下面说明子集的二进制数表示和幂集合的个数。,在集合的定义里,没有规定集合中元素的次序,但为了便于在计算机上表示集合,亦可给集合元素编定次序。例如,A,=,a,b,c,不妨认为,a,b,c,分别是第一、二、三个元素。于是可用三位二进制数做足标表示A的任意子集:二进制数的第i位表示第,i,个元素是否属于该子集,1表示属于,0表示否。例如可用,S,101,表示,a,c,S,011,表示,b,c,三位二进制数可与其子集一一对应。因而,(,A,)=,S,i,|,i,J,这里,J,=000,001,111。为了书写方便,可用十进制数代替二进制数,于是,J,=0,1,2,7。一般地,n,个元素的集合,A,可用,n,位二进制数与其子集一一对应。因而,由此可知,n,个元素的集合,A,其幂集的元素个数是 2,n,。;,如果,A,是无限集,则,(,A,)的元素个数也是无限的。,*2.2.6 有限集的计数,定理 2.2-15,设,A,和,B,都是有限集合,则以下公式成立:,证,A,和,B,之间可能有公共元素,公共元素个数是|,A,B,|,在计算|,A,B,|时每个元素只计算一次,但在计算|,A,|+|,B,|时,公共元素计算了二次,一次在算|A|时,一次在算|,B,|时,因此,右边减去|AB|才能相等。证毕。;,公式(,a,)可以推广,三个集合时为,图 2.2-3,一般地成立以下公式:,证,用归纳法证明(未学过归纳法的同学可在学完下节后,再看此证明)。,n,=2时,已证明成立,即,设,n,-1(,n,3)时公式成立,现证明,n,时也成立。,根据归纳假设得,例 6,(,a,)在一个班级50个学生中,有 26 人在第一次考试中得到A,21人在第二次考试中得到A,假如有17 人两次考试都没有得到A,问有多少学生在两次考试中都得到,A,?,解,设第一次考试得,A,的是集合,A,1,第二次考试得,A,的是集合,A,2,。,则,但,所以,答:两次考试都得,A,的 14 人。,(,b,)某教研室有30名老师,可供他们选修的第二外语是日语、法语、德语。已知有 15 人进修日语,8 人选修法语,6 人选修德语,而且其中 3 人选修三门外语,我们希望知道至少有多少人一门也没有选修。,解,设,A,1,、,A,2,、,A,3,分别表示选修日语、法语和德语的人,因此,因为,我们得,即至多有 23 人在进修第二外语,因此至少有 7 人没有进修第二外语。,2.3 归纳法和自然数,2.3.1 集合的归纳定义,在2.1节介绍了指定集合的两种最常用方法列举法和描述法。但仍然有许多集合难以用这两种方法表示出来,诸如算术表达式集合,命题演算公式集合,ALGOL程序集合等等,这些集合用归纳定义来指定较为方便。归纳定义习惯上称为递归定义。,(1)基础条款(简称基础)。它指出某些事物属于集合。它的功能是给集合以基本元素,使所定义的集合非空。;,(2)归纳条款(简称归纳)。它指出由集合的已有元素构造新元素的方法。归纳条款的形式总是断言:如果事物,x,y,z,是集合的元素,那么用某种方法组合它们而成的一种新事物也在集合中。它的功能是指出为了构造集合的新元素,能够在事物上进行的运算。,(3)极小性条款(简称极小性)。它断言一个事物除非能有限次应用基础和归纳条款构成外,那么这个事物不是集合的成员。,集合,S,的归纳定义的极小性条款还有其它形式,常见的有:;,(i)“集合,S,是满足基础和归纳条款的最小集合”。;,(ii)“如果,T,是,S,的子集,使T满足基础和归纳条款,那么,T,=S”。其意义是:,S,满足基础和归纳条款,但没有,S,的真子集满足它们。,这些极小性条款虽然形式不同,结果是等价的,全部服务于一个目的,即指明崐所定义的集合是满足基础和归纳条款的最小集合,即通常所谓极小性。,例 1,如果论述域是整数,I,那么能为3 整除的正整数集合,S,的谓词定义如下:,同样集合能归纳地定义如下:;,(1)(基础)3,S,;,(2)(归纳)如果,x,S,和,y,S,那么,x,+,y,S,;,(3)(极小性)没有一个整数是,S,的元素,除非它是有限次应用条款1和2得出的。,设表示一个有限的非空的符号(字符)集合、我们称为字母表。由字母表中有限个字符拼接起来的符号串叫做字母表上的一个字(或叫串)。,例 2,(,a,)如果=,a,b,z,那么is,then都是上的字。,(,b,)如果=你,我,人,工,是,那么“你是工人”是上的串。,(,c,)如果=,a,b,z,这里是代表空白。那么that,waslongago是上的串,习惯上印成that was long ago。,设,x,是上的一个字,如果,x,=,a,1,a,2,a,n,这里,n,N,对每一1,i,n,a,i,那么,x,中的符号个数,n,称为,x,的长度,记为,x,。长度为0的串表示为,叫做,空串,。注意空串不是空白符,前者长度为 0,后者长度是1。如果,x,和,y,都是在上的符号串,x,=,a,1,a,2,a,n,和,y,=,b,1,b,2,b,m,这里,对所有,i,和,j,a,i,和,b,j,那么,x,连结,(或叫,并置,毗连,),y,记为,xy,是串,如果,x,=,那么,xy=y,如果,y=,那么,xy=x,。如果,z=xy,那么,x,是,z,的,词头,y,是,z,的,词尾,。如果,x,z,那么,x,是,真词头,;如果,y,z,那么,y,是,真词尾,。如果,w,=,xyz,那么,y,是,w,的,子串,如果,y,w,那么,y,是,真子串,。,定义2.3-1,设,是一个字母表,上的非空串的集合,+,定义如下:,(1)(基础)如果,a,那么,a,+,。,(2)(归纳)如果,x,+,且,a,那么,ax,+,。(,ax,表示串,它由符号,a,和串,x,连结组成)。;,(3)(极小性)集合,+,仅包含这些元素:它能由有限次应用条款1和2构成。,集合,+,包含长度为1,2,3,的串,所以是无限集合。然而,在,+,中没有一个串包含无限数目的符号,这是极小性条款限制的结果。,例 3,如果=,a,b,那么,+,=,a,b,aa,ab,ba,bb,aaa,aab,。,上的所有有限符号串的集合记为*。集合*包含空串,其归纳定义如下:,定义2.3-2 设,是字母表,那么*定义如下:,(1)(基础)*。,(2)(归纳)如果,x,*和,a,那么,ax,*。,(3)(极小性)没有一个串可以是集合,*的元素,除非它能有限次应用条款1和条款2构成。,当然,*也可这样定义:*=,+,例 4,(,a,)如果=,a,b,那么*=,a,b,aa,ab,。,(,b,)如果=0,1,那么*是有限二进制序列的集合,包括空序列。,归纳定义常用来刻画数学中的合式公式,或叫成形公式(Well-Formed Formula)。这方面我们已见过一些例子。如第一章的命题公式定义和谓词公式定义等。,例 5,为简明起见,我们将算术表达式集合限制于仅包含整数,一元运算+和-,和二元运算+、-、*和/。,(1)(基础)如果,D,=0,1,2,3,4,5,6,7,8,9和,x,D,+,那么,x,是一算术表达式。,(2)(归纳)如果,x,和,y,都是算术表达式,那么,(i)(+,x,)是一算术表达式,(ii)(-,x,)是一算术表达式,(iii)(,x,+,y,)是一算术表达式,(iv)(,x,-,y,)是一算术表达式,(v)(,x,*,y,)是一算术表达式,(vi)(,x,/,y,)是一算术表达式。,(3)(极小性)一个符号序列是一算术表达式当且仅当它能得自有限次应用条款1和2。,用这个定义刻画的算术表达式集合包括45,000,(-321),(3+7),(3*(-35)和(+(-(+7/2)等,不包括诸如+)和+6+之类的符号串。,有些归纳定义是以其它归纳定义的集合作基础建立起来的,我们称这样的归纳定义为“二次归纳定义”,二次归纳定义不需要极小性条款,因为基础集合的极小性条款保证了所定义的集合的极小性。作为基础集合最常见的是自然数集合N。因此,以自然数集合为基础集合的归纳定义常不需极小性条款。,例 6,设,a,R,+,且,n,N,。,a,n,的归纳定义如下:,(1)(基础),a,0,=1,(2)(归纳),a,n,+1,=,a,n,a,这个归纳定义的基础集合是N,所以不需要极小性条款。,程序设计语言,诸如ALGOL,它们的语法也常用归纳定义(以巴科斯范式形式给出)描述,2.3.2 自然数,自然数可应用后继集合的概念归纳地定义。,定义 2.3-3 设,A,是任意集合,A,的,后继集合,记为,A,定义为,例 7,(,a,),a,b,的后继集合是,a,b,a,b,=,a,b,a,b,。,(,b,)的后继集合是=,。,定义 2.3-4,自然数,N,是如下集合:,(1)(基础),N,。,(2)(归纳)如果,n,N,那么,n,n,N,。,(3)(极小性)如果 且满足条款1和2,那么,S=N,。,按照这个定义,自然数集合的元素是:,化简后是,图 2.3-1,可能有人会想出这样的定义:;,(1)(基础)0N,;,(2)(归纳)如果nN,那么n+1N,;,(3)(极小性)如果SN且满足条款(1)和(2),那么S=N。,以上3条一般称为归纳特征,下边可以看到它将帮助我们对论述域,N,讨论归纳证明,但作为定义则是不完善的。因为自然数的加法定义是建立在集合,N,上,现在又用加法定义自然数,这就犯了循环定义的错误,所以定义自然数必须不用加法。,可能有人会想:用n来表示自然数n的“后继者”,把第(2)条改为:,(2)(归纳)如果,n,N,那么,n,N,。这样总是可以了吧!其实这样也不行,例如,规定0=0,即模型(图2.3-2)也符合这个定义,显然不是自然数。,图 2.3-2,这些想法也不是完全错的,只要再补上一些条款,也可定义出自然数,N,。可这样定义:;,(1)0,N,(2)如果,n,N,则恰存在一个,n,的后继者,n,N,(3)0 不是任何自然数的后继者,;,(4)如果,n,=,m,那么,n,=,m,(5)如果,S,是,N,的子集,使,(i)0,S,;,(ii)如果,n,S,那么,n,S,那么,S,=,N,。;,这就是有名的皮亚诺(Peano)公设。其中(2)保证后继者是唯一的,(3)保证0只作开端,(4)保证除0外的每一个自然数只有一个直接前趋。,常用(2)和(4)来检查一个序列有没有自然数性质。例如,序列,0,2,4,1,3,5,不具有自然数性质,因为其中1没有直接前趋。,2.3.3 归纳证明,归纳定义不仅提供了定义无限集合的一种方法,也为证明定理形成某些有效技术的基础。对于,xP,(,x,)形式的命题,如果其论述域,S,是归纳定义的集合,则归纳法往往是有效的证明方法。归纳法证明通常由基础步骤和归纳步骤两部分组成,它们分别对应于,S,的定义的基础和归纳条款。,(1)基础步骤。这一步证明,S,的定义中基础条款指定的每一元素,x,S,P,(,x,)是真。,(2)归纳步骤。这一步证明如果事物,x,y,z,有性质,P,那么用归纳条款指定的方法,组合它们所得的新元素也具有性质P。,归纳定义的极小性条款保证,S,的所有元素仅仅应用基础和归纳条款才能构成,因此证明了以上两步,就足以推出,xP,(,x,)。,现在举例说明这一方法。回顾定理1.2-1:“设,A,和,A,*是对偶式。,P,1,P,2,P,n,是出现于,A,和,A,*”中的所有命题变元,于是,A,(,P,1,P,2,P,n,),A,*(,P,1,P,2,P,n,),因为根据对偶式定义,公式A中仅含有联结词、,因此公式,A,可归纳定义如下:,(1),P,i,(1,i,n,)是公式;,T,是公式;,F,是公式。,(2)若,A,和,B,是公式,则,A,、(,A,B,)、(,A,B,)是公式。,(3)只有有限次运用条款(1)和(2)生成的才是公式。,定理1.2-1是建立在归纳定义的公式集合上,因此可以用上述一般的归纳法证明。,(1)(基础步骤),P,i,P,i,(1,i,n,),所以当A是由一个变元或常元构成时,公式(1)成立。,(2)(归纳步骤)设,A,1,(,P,1,P,2,P,n,)、,A,2,(,P,1,P,2,P,n,)对公式(1)成立,即,A,1,(,P,1,P,2,P,n,)A,1,*,(,P,1,P,2,P,n,),A,1,(,P,1,P,2,P,n,)A,1,*,(,P,1,P,2,P,n,),现证明:(,A,1,A,2,)(,A,1,A,2,),A,1,时,公式(1)也成立。,情况1：,E,11,归纳前提,情况 2:,(,A,1,A,2,),方法与情况 1 类似,留给读者自证。,情况3:,A,1,记,A,1,为A,故对,n,个命题变元的一切公式,公式(1)成立。,但通常的归纳证明是涉及自然数的,自然数具有以下归纳特征:,(1)(基础)0,N,。,(2)(归纳)如果,n,N,那么,n,+1,N,。,(3)(极小性)如果 ,且,S,有以下性质:,(i)0,S,;,(ii)对每一,n,N,如果,n,S,那么(,n,+1),S,。,那么,S,=,N,。,这里,极小性条款是习惯上用于自然数定义中的形式,它叫做数学归纳法第一原理。我们适当地改变一下这个条款的形式,就可得到以自然数为论述域的,xP,(,x,)形式的断言的归纳证明过程。,令,S,=,n,|,P,(,n,)是,N,的子集,于是极小性条款可改为“如果,P,(0)为真,n,(,P,(,n,),P,(,n,+1)为真,那么,对一切,n,P,(,n,)为真。”根据这一条款,立即得出归纳证明的过程如下:,(1)(基础)先证明,P,(0)是真。可用任意证明技术。,(2)(归纳)再证明,n,(,P,(,n,),P,(,n,+1)是真。为此,一般先假设“,P,(,n,)对任意,n,N,是真”这叫归纳假设(或归纳前提),由此再推出,P,(,n,+1)也真,一旦证明了,P,(,n,),P,(,n,+1)对任意,n,是真,用全称推广规则得,n,(,P,(,n,),P,(,n,+1)。,再根据数学归纳法第一原理得出,xP,(,x,)。,例 8,证明对所有,n,N,。这里的定理是,nP,(,n,)的形式。,P,(,n,)是断言,证,(1)(基础)证明,P,(0),因为,即0=0,显然成立。,(2)(归纳)证明,n,(,P,(,n,),P,(,n,+1)。,假设对一切,n,N,P,(,n,)是真,即 我们希望证明,P,(,n,+1),也就是,因为,而,n,是任意的,得出,n,(,P,(,n,),P,(,n,+1),应用归纳法第一原理得,xP,(,x,),即对一切自然数,n,成立。,数学归纳法第一原理,事实上是自然数域上的一个推理规则。用1.5节的符号,规则的形式如下:,规则可以有各种变形,例如,我们通常希望证明对某整数,k,谓词,P,对所有,x,k,成立。这时,基础步骤必须换为证明,P,(,k,)。于是推理规则是:,容易证明这两种形式的推理规则是等价的。,例 9,证明,n,4 时,2,n,n,2,证,(1)(基础),n,=5 时,2,5,5,2,显然成立。,(2)(归纳)设,n,时,2,n,n,2,成立,现证,n,+1 时命题也成立,这里,n,5。因为 2,n,+1,=22,n,2,n,2,(根据归纳假设),n,2,+5,n,n,+2,n,+1,=(,n,+1),2,所以,对一切,n,4,2,n,n,2,。征毕。,如果令,n,=,m,+5,上题就成为“证明对一切自然数,m,2,m,+5,(,m,+5),2,”,这样,本题就成为基本形式了。,例 10,设,a,n,如本节例6 所定义,试证明,证,设,m,是任意的,对,n,作归纳,证明断言,n,(,a,m,a,n,=,a,m,+,n,)。,(1)(基础)如果,n,=0,那么,a,m,a,n,=a,m,a,0,=a,m,1,=a,m,=a,m+0,=a,m+n,(2)(归纳)设,a,m,a,n,=a,m+n,对任意,n,成立,那么,a,n,a,n,+1,=,a,m,(,a,n,a,),a,n,的定义,=(,a,m,a,n,),a,乘法结合律,=(,a,m+n,),a,归纳假设,=,a,(,m+n,)+1,a,n,的定义,=,a,m,+(,n,+1),加法结合律,所以,n,a,m,a,n,=,a,m+n,。,因为,m,是任意的,由全称推广规则得,自然数域上的归纳法证明还有另一形式,称为数学归纳法第二原理,第二原理作为推理规则的形式如下:,应用这一推理规则的证明的归纳假设是,即对一切,k,n,P,(,k,)是真。从这一假设出发,我们必须证明,P,(,n,)。一旦在归纳假设的前提下证明了,P,(,n,),就可得出,xP,(,x,)。;,应用第二原理仅需我们证明单一的前提,但它通常需要分情况证明。首先证明,n,=0的情况。,n,=0时,k,0 对一切,k,N,常假,所以,k,k,0,P,(,k,),常真。所以,证明,k,k,0,P,(,k,),P,(0)是真,等价于证明,P,(0)是真。,其次证明:对任意,n,0,如果,P,(,k,)对一切,k,n,成立,那么,P,(,n,)是真。,这样,用第二原理证明和用第一原理证明的唯一不同是:用“对一切,k,n,P,(,k,)是真”的归纳假设代替“,P,(,n,-1)是真”的归纳假设。,虽然两个数学归纳法原理是不同的,但如果论述域是自然数N,则它们的前提是逻辑等价的,因此它们也是等效的。但有其它论述域存在,那里第二原理更有效。,通常,如果证明,P,(,n,+1)为真,即证明元素,n,+1具有性质,P,不仅可能依赖于元素,n,的性质,还可能依赖于,n,以前各元素的性质时,应选用第二原理。第二原理和第一原理一样,也有各种变形。,例11,有数目相等的两堆棋子,两人轮流从任一堆里取几颗棋子,但不能不取也不能同时在两堆里取。规定凡取得最后一颗者胜。求证后取者可以必胜。,证,对每堆棋子数目,n,作归纳证明。为了便于叙述,设甲为先取者,乙为后取者。,n,=1时,甲必须在某堆中取一颗。于是另一堆中的一颗必为乙所得,乙胜。,设,n,k,时,后取者胜。现证,n,=,k,时也是后取者胜。,设第一轮甲在某堆先取,r,颗,0,r,k,。乙的对策是在另一堆中也取,r,颗。这里有两种可能。,(1)若,r,k,经过两人各取一次之后,两堆都只有,k,-,r,颗,k-r,k,现在又是甲先取,根据归纳假设乙胜。,(2)若,r,=,k,显然是乙胜。证毕。,本例不仅说明了归纳法第二原理的应用,还说明有些问题虽然与自然数无直接关系,也可引入自然数作参数,利用有关自然数的归纳法证明。,*2.4 语言上的运算,定义,2.4-1 设,x,是,*的一个元素,对每一,n,N,串,x,n,定义如下:,(1),x,0,=,(2),x,n,+1,=,x,n,x,例 1,(,a,)如果,=,a,b,c,和,x,=,ac,那么,x,0,=,x,1,=,ac,x,2,=,acac,x,3,=,acacac,。,(,b,)集合1,n,0,n,|,n,0表示集合,10,1100,111000,;,在串的运算的基础上可以定义语言上的运算。,定义2.4-2,设,是有限字母表,上的语言是,*的一个子集。,例 2,(,a,)集合,b,ab,aab,aaab,是,=,a,b,上的一个语言。,(,b,)一个由1的序列跟随着0的序列组成的串的集合1,n,0,m,|,n,m,N,是0.1上的语言。,(,c,)FORTRAN程序的集合是FORTRAN字符组成的字母表上的语言。,定义2.4-3,设,A,和,B,是,上语言,A,和,B,的连结积记为,A,B,或,AB,是语言,AB,=,xy,|,x,A,y,B,即语言,AB,是由,A,的一个元素连结,B,的一个元素所形成的所有串组成的集合。,例 3,设=,a,b,A,=,a,和,B,=,b,ab,那么,AB,=,b,ab,aab,BA,=,b,ba,ab,aba,从上例可看出,一般地,AB,BA,也就是说语言的连结积运算是不可交换的。但有以下性质。,定理2.4-1,设,A、B、C,和,D,是上的任意语言,那么;,(a),(b),A,=A=A,(c)(AB)C=A(BC),(d)如果 和 ,那么,证,(,a,)根据定义,A,=,xy,|,x,A,y,但对每一,y,*,y,常假。所以合取式,x,A,y,对一切,x,和,y,是假。因为没有元素,x,和,y,满足这谓词,集合,A,没有成员,即 。类似地可证,(,d,)用直接证明。设,z,是,AC,的任意元素,那么,z,=,xy,这里,x,A,和,y,C,因为 和 ,得出,x,B,和,y,D,。因此,z,=,xy,BD,。因为,z,是,AC,的任意元素,得,(,b,)和(,c,)的证明留作练习。,定理2.4-2,设,A、B、C,和,D,是上的任意语言,那么;,(,a,),A,(,B,C,)=,AB,AC,(,b,)(,B,C,),A,=,BA,CA,(,c,),A,(,B,C,),AB,AC,(,d,)(,B,C,),A,BA,CA,证,(,a,)先证,AB,AC,A(,B,C,)。,因为 ,由定理2.4-1的(,d,)得 因此,。,再证,如果,z,是,A,(,B,C,)的任一元素,那么,z=xy,这里,x,A,和,y,B,C,。因此,x,A,y,B,或,x,A,y,C,得出,z,AB,或,z,AC,。所以,z,AB,AC,。,z,是任意的,故,(,b,)、(,c,)、(,d,)的证明留作练习。;,定理2.4-2,(,c,)和(,d,)中的包含可能是真包含。例如,如果,A,=,0,01,B,=01,11和,C,=101。那么,A,B,C,=,但,AB,AC,=0101。,定义2.4-4,设,A,是,上的一个语言,语言,A,n,归纳地定义如下:,(1),A,0,=,(2),A,n,+1,=,A,n,A,对,n,N,。,语言,A,