离散数学：第9讲 函数.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,函数,内容提要,函数,(,映射,),定义,象,原象,单射,满射,双射,计数问题,常数函数,恒等函数,特征函数,单调函数,自然映射,复合,逆函数,2,函数,(function),函数,:F,是函数,F,是,单值的,二元关系,F,单值,:xdomF,y,zranF,xFy xFz y=z,函数亦称,映射,(mapping),F(x)=y,F xFy,是函数,称为,空函数,常用,F,G,H,f,g,h,表示函数,.,x,y,z,非单值,单值,3,偏函数,(partial function),偏函数,:domF,A,A,到,B,的偏函数,:,domF,A,且,ranFB,偏函数记作,F:AB,称,A,为,F,的,前域,A,到,B,的全体偏函数记为,AB,AB=F|F:AB,4,例,1,例,1,:,设,A=a,b,B=1,2,求,A,B.,解,:|A|=2,|B|=2,|A,B|=4,|P(A,B)|=2,4,=16.,f,0,=,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,f,7,=,f,8,=,.,A,B=f,0,f,1,f,2,f,3,f,4,f,5,f,6,f,7,f,8,.#,非函数,:,5,全函数,(total function),全函数,:domF=,A,全函数记作,F:AB,A,到,B,的全体全函数记为,B,A,或,AB,B,A,=AB=F|F:AB,6,关于,B,A,的说明,B,A,=F|F:AB=F|F,是,A,到,B,全函数,|B,A,|=|B|,|A|,.,当,A=,时,B,A,=,当,A,且,B,=,时,B,A,=,AB,=,但,AB,=,.,7,真偏函数,(,proper partial function,),真偏函数,:domF,A,真偏函数记作,F:AB,A,到,B,的全体真偏函数记为,AB,AB=F|F:AB,8,例,1(,续,),例,1(,续,),:,设,A=a,b,B=1,2,求,A,B.,解,:f,0,=,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,f,7,=,f,8,=,.,A,B=f,0,f,1,f,2,f,3,f,4,.#,9,三者关系,AB=AB AB,偏函数,AB,domF,A,全函数,AB,domF=,A,真偏函数,A,B,domF,A,说明,:F,A,B,F,domF,B,F,A,B,F,domF,B,10,函数,(function),定义,定义,3.1,：,X,和,Y,是两个集合，,f,是,X,到,Y,的,关系,，如果对于,任意,xX,，有,唯一,的,yY,使得,f,，称关系,f,为函数，记作：,f,：,XY,或,X Y,。称,x,为,原象,y,为,象,。,1.,关系,;,2.X,中任何元都有象,dom f=,A,;,3.,唯一象,11,例,1,例,1,:,设,A=a,b,B=1,2,解,:,f,1,=,f,2,=,f,3,=,f,4,=,X,中任何元都有象,dom f=,A,;,原象对应唯一象,12,函数相等,定义：设函数,f:AB,，,g:CD,，如果,A=C,，,B=D,，且对于所有,xA,和,xC,有,f(x)=g(x),，则称函数,f,和,g,相等，记作,f=g,。,函数是序偶的集合，故两个函数相等可用集合相等的概念予以定义。,13,函数的计数,A=0,1,2,，,B=a,b,，写出,A,到,B,上的所有函数。,14,函数的计数（续）,A=a,b,，,B=1,2,3,，写出,A,到,B,上的所有函数。,15,函数的计数规律,A,到,B,的全体全函数记为,B,A,B,A,=f|f:AB,一般说来，如果,|A|=n,，,|B|=m,，,m,，,n,非零，则,|,B,A,|=m,n,16,满射,定义,3.5(1),：对于,X,Y,的映射,f,，如果,ran f=Y,，即,Y,的每一个元素是,X,中一个或多个元素的象，则称这个映射为,满射,(,或到上映射,),。,(,设,f:XY,是满射，则对,yY,，必有,xX,使得,f(x)=y,，即,f(X)=Y),17,满射,18,单射,定义,3.5(2),：对于,XY,的映射,f,，若,X,中,没有,两个元素有相同的象，则称这个映射为,入射,(,单射,),。,(,设,f:XY,是单射，即是对于任意,x,1,x,2,X,，如果,x,1,x,2,，则,f(x,1,)f(x,2,),或,若,f(x,1,)=f(x,2,),则,x,1,=x,2,),19,单射,20,双射,定义,3.5(3),：从,X,到,Y,的一个映射，若既是满射又是单射，则称此映射为,双射,(,或,一一映射,),21,双射,22,函数性质,设,f,:,AB,单射,(injection):f,是单根的,满射,(surjection):ran f=B,双射,(bijection):f,既是单射又是满射,亦称为,一一对应,(one-to-one mapping).,非单射,非满射,23,例,判断下述函数是否为单射，满射，双射,函数,f:NN,自然数集,，,f(n)=2n,函数,f:NN,，,f(2n)=n,，,f(2n+1)=n,函数,f:NN,，,f(n)=n+1,函数,f:ZZ,，,f(n)=n+1,单射但非满射,满但非单,单射但非满射,双射,24,计数,(counting),问题,设,|A|=n,|B|=m,问,A,B,中有多少单射,满射,双射,?,25,例,2(1),例,2,:(1)A=a,b,B=1,2,3,单射,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,.,P,3,2,26,例,2,（,2,）,例,2,（,2,）,:A=a,b,c,B=1,2,满射,（前多）,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,.,A,分成,|B|,个非空集合的分法,=3,27,例,2(3),例,2,:(3)A=a,b,c,B=1,2,3,一一映射,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,.,阶乘,28,性质,性质：若,X,、,Y,是有限集，且存在双射,f:XY,，则,|X|=|Y|,29,计数,(counting),问题,设,|A|=n,|B|=m,问,A,B,中有多少单射,满射,双射,?,nm,时,A,B,中无单射和双射,满射个数为,（,Stirling,数）,N,个数分出,m,个非空子集数,30,象,(image),原象,(preimage),设,f:,AB,A,A,B,B,象,:A,的象是,f(A,)=y|,x(xA,f(x)=y),B,f(A)=ranf,原象,:B,的原象是,f,-1,(B,)=x|,y(yB,f(x)=y),A,A,f(A,),f,-1,(B,),B,31,象,原象,(,举例,),例,:f:N,N,f(x)=2x,.,A,=N,偶,=0,2,4,6,=,2k,|k,N,f(A,),=0,4,8,12,=,4k,|k,N,B,=,2+4k,|k,N=2,6,10,14,f,-1,(B,),=,1+2k,|k,N=1,3,5,7,=N,奇,#,32,特殊函数,常数函数,:,xA,f(x)=,b,B,恒等函数,:,I,A,:A,A,I,A,(x)=x,特征函数,:,A,:E,0,1,A,(x)=1,xA,单调函数,:f:A,B,偏序集,x,yA,x,A,y f(x),B,f(y),单调,增,单调,减,严格,单调,自然映射,:R,为,A,上等价关系,f:AA/R,f(x)=x,R,.,33,自然映射,(,举例,),例,:A=a,b,c,d,e,f,A/R=a,b,c,d,e,f,a=b=a,b,c=d=e=c,d,e,f=f,F:,AA/R,F(x)=x.,F(a)=a,b,F(b)=a,b,F(c)=c,d,e,F(d)=c,d,e,F(e)=c,d,e,F(f)=f.#,a,b,c,d,e,f,34,函数运算,复合函数,:,性质,左,(,右,),单位元,逆函数及存在条件,35,函数复合,(composite),定义,:,设,g:A,B,f:B,C,则,g,f,=,|xAzCy(yBy=g(x)z=f(y),36,定理,定理：两个函数的复合是一个函数,证明：设,g:YZ,，,f:XY,a),存在性,即,xX,，,使,f,g.,xX,，,f,为函数，,!,序偶,f,使得,f(x)=y,而,f(x)f(X),Y,，加上,g,是函数，故必有,zZ,，,z=g(y),成立，从而,z=g(f(x),，即,f,g,，即,X,中每个,x,对应,Z,中某个,z,b),唯一性,.,设,f,g,中包含序偶,和,则必存在,y,1,y,2,Y,，使得,f,，,、,g,因为,f,是一个函数，故,y,1,=y,2,再由,g,是一个函数，故,z,1,=z,2,37,复合的性质,定理,3.4,:,设,g:A,B,f:B,C,g,f:A,C,则,(a)f,g,均为,满射,则,g,f,也是,满射,.,(b)f,g,均为,单射,则,g,f,也是,单射,.,(c)f,g,均为,双射,则,g,f,也是,双射,.#,38,复合的性质,(,续,),定理,3.5,:,设,g:A,B,f:B,C,则,(1),若,g,f,为,满射,则,f,是,满射,.,(2),若,g,f,为,单射,则,g,是,单射,.,(3),若,g,f,为,双射,则,g,是,单射,f,是,满射,.#,g,g,f,39,复合的左,(,右,),单位元,定理,3.6,:,设,f:A,B,则,f=,I,A,f,=f,I,B,.#,A,A,B,B,I,A,I,B,f,40,复合的单调性,定理,3.7,:,设,f:R,R,g:R,R,且,f,g,按,是单调增的,则,f,g,也是单调增的,.,证明,:xy g(x)g(y)f(g(x)f(g(y).#,41,逆函数的存在性,与关系相类比,逆关系为交换序偶的元素次序,R,-1,R,任意给定一个函数，它的逆不一定是函数。,(,双射才可以,),例如，函数,其逆为,42,定理,3.9,定理,3.9,：设,f:XY,是一双射函数，那么,f,-1,是,YX,的双射函数。,证明：,1.f,-1,为映射,，即任给,yY,都在,X,中有唯一象,:f,为满射，故任给,yY,，存在,xX,，,s.t.f(x)=y,即,f,，因此必有,f,-1,又,f,是单射，因此满足上述条件的,x,必唯一，因此,f,-1,必为映射,2.f,-1,为满射,:ran f,-1,=dom f=X,3.f,-1,为单射,:,任给,y,1,y,2,Y,，,y,1,y,2,，假设,x,1,=f,-1,(y,1,)=f,-1,(y,2,)=x,2,由映射定义知,f(x,1,)=f(x,2,),，即,y,1,=y,2,43,逆函数,(inverse function),定义,:,若,f:A,B,为双射,则,f,-1,:B,A,称为,f,的,逆,(,反,),函数,.,44,例,4,f:Z Z,nn+1,逆函数,f:Z Z,nn-1,函数,f:,-/2,，,/2,-1,，,1,，,y=,sin,x,，可以定义它的反函数,x=,arcsin,y,。,45,单边逆,设,f:A,B,g:B,A,左逆,:g,是,f,的左逆,g,f=,I,A,右逆,:g,是,f,的右逆,fg,=,I,B,A,B,f,g,I,A,I,B,46,单边逆,(,举例,),B,A,B,g,f,A,B,A,g,f,f,g,=,I,B,g,f,=,I,A,47,单边逆的存在条件,定理,10,:,设,f:A,B,且,A,则,(1),f,存在左逆,f,是单射,;,(2),f,存在右逆,f,是满射,;,(3)f,存在左逆,右逆,f,是双射,.#,g,f,f,g,48,构造双射及求反函数,|A|=m,|B|=n,A,B,存在双射,n=m,|A|=,|B|=,B,A,A,B,存在双射,如,f:N,N-0,1,2,f(n)=n+3,0,1,(0,1)?R(0,1)?,N,N,N?,（,任一有限集合的真子集不可能与原子集建立双射关系,）,0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,49,N,N,N,双射,?,50,方法,1:,用自然数性质,nNn0,N,为奇数,使得,n=2,例,:1=2,0,1,2=2,1,1,3=2,0,3,6=2,1,3,100=2,2,25,令,n=2,-1,可以去掉,n0,的条件,令,=2j+1,为奇数,nN,n=2,i,(2j+1)-1,i,jN,此表示唯一,.,51,方法,1:f:N,N,N,f:N,N,N,f,-1,:N,N,N,N,N,f()=,2,i,(2j+1)-1,f,-1,(n)=f,-1,(,2,i,(2j+1)-1,)=.,例,:f()=0,f()=2,f()=1,f,-1,(5)=,f,-1,(101)=,f,-1,(200)=,52,方法,2:Cantor,编码,对角线法,1+2+3+(m+n)+(m+1),=(m+n)(m+n+1)/2+(m+1),对应的自然数为,(m+n)(m+n+1)/2+m,53,方法,2:f:N,N,N,f:N,N,N,f,-1,:N,N,N,N,N,f()=(m+n)(m+n+1)/2+m,求,f,-1,(r)=.,r=(m+n)(m+n+1)/2+m=t(t+1)/2+m,t=m+n,0,mt,求最大,t,使得,r,t(t+1)/2.,t,2,+t-2r,0,m=r-t(t+1)/2,n=t-m.,例,:f,-1,(0)=,f,-1,(1)=,f,-1,(2)=,f,-1,(3)=,54,作业,P68 3,11,14,15,