《离散数学函数》PPT课件.ppt

5-1函数的基本概念,一.概念定义：X与Y集合，f是从X到Y的关系，如果任何xX，都存在唯一yY，使得f,则称f是从X到Y的函数，(变换、映射)，记作f:XY,或XY.如果f:XX是函数,也称f是X上的函数.下面给出A=1,2,3上几个关系，哪些是A到A的函数？,下面哪些是R到R的函数？f=|x,yRy=g=|x,yRx2+y2=4h=|x,yRy=x2r=|x,yRy=lgxv=|x,yRy=,2.定义域、值域和陪域(共域),设f:XY,f的定义域(domain)，记作domf，或Df即Df=domf=x|xXy(yYf)=Xf的值域(range)：记作ranf，或Rf即或f(X)Rf=ranf=f(X)=y|yYx(xXf)f的陪域(codomain):即是Y(称之为f的陪域)。,二.函数的表示方法有枚举法、关系图、关系矩阵、谓词描述法。三.从X到Y的函数的集合YX：YX=f|f:XYYX：它是由所有的从X到Y函数构成的集合例X=1,2,3Y=a,b求所有从X到Y函数结论：若X、Y是有限集合，且|X|=m，|Y|=n，则|YX|=|Y|X|=nm。从X到Y的关系=|P(XY)|=2nm.规定：从到的函数只有f=。从到Y的函数只有f=。若X，则从X到的函数不存在。,四.特殊函数,1.常值函数：函数f:XY，如果y0Y,使得对xX,有f(x)=y0,即ranf=y0,称f是常值函数。2.恒等函数：恒等关系IX是X到X函数，即IX:XX,称之为恒等函数。显然对于xX，有IX(x)=x。五.两个函数相等设有两个函数f:ABg:AB,f=g当且仅当对任何xA，有f(x)=g(x)。,六.函数的类型例子：,一对一,一对一,函数的类型1.满射的：f:XY是函数，如果ranf=Y,则称f是满射的。2.入射的：f:XY是函数，如果对于任何x1,x2X,如果x1x2有f(x1)f(x2),(或者若f(x1)=f(x2),则x1=x2),则称f是入射的，也称f是单射的，也称f是一对一的。3.双射的：f:XY是函数，如果f既是满射的，又是入射的，则称f是双射的，也称f是一一对应的。特别地：Y是单射；：是双射。思考题：如果f:XX是入射的函数，则必是满射的，所以f也是双射的。此命题在什么条件下成立吗？,5-2函数的复合,关系的复合：设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RS。定义为：RS=|xXzZy(yYRS),函数的复合,定义：设f:XY,g:WZ是函数,若f(X)W,则gf=|xXzZy(yYfg)称为g在f的左边可复合。,定理：两个函数的复合是一个函数。,证明：设f:XY,g:WZ是函数,且f(X)W。（1）对任意的xX，因为f是函数，故存在唯一的序偶，使得y=f(x)成立,而f(x)f(X)W,又因为g是函数，故存在唯一的序偶，使得z=g(y)成立，根据复合定义，gf,即domgf=X.（2）假设gf且gf，由复合定义存在y1Yy2Y，使得fgfg,由于f、g为函数，所以有，y1=y2，因而z1=z2。由（1）、（2）得gf是X到Z的函数。,函数的复合,一.定义:f:XY,g:YZ是函数,则定义gf=|xXzZy(yYfg)则称gf为f与g的复合函数(左复合).结论:gf(x)=g(f(x)二.复合函数的计算计算方法同复合关系的计算.,例f:XY,g:YZX=1,2,3Y=1,2,3,4,Z=1,2,3,4,5,f=,g=,则gf用关系图复合:三.函数复合的性质定理1（满足可结合性）。f:XY,g:YZ,h:ZW是函数,则(hg)f=h(gf),定理2.f:XY,g:YZ是两个函数,则如果f和g是满射的，则gf也是满射的；如果f和g是入射的，则gf也是入射的；如果f和g是双射的，则gf也是双射的。证明：设f和g是满射的，因gf:XZ,任取zZ,因g:YZ是满射的，所以存在yY,使得z=g(y),又因f:XY是满射的，所以存在xX,使得y=f(x),于是有z=g(y)=g(f(x)=gf(x),所以gf是满射的。设f和g是入射的，因gf:XZ,任取x1,x2X,x1x2，因f:XY是入射的，f(x1)f(x2),而f(x1),f(x2)Y，因g:YZ是入射的，g(f(x1)g(f(x2)即gf(x1)gf(x2)所以gf也是入射的。,定理3如果gf是满射的，则g是满射的；如果gf是入射的，则f是入射的；如果gf是双射的，则f是入射的和g是满射的。定理4f:XY是函数,则fIX=f且IYf=f。,5-3逆函数,R是A到B的关系，其逆关系RC是B到A的关系。RC=|Rf:XYfC:YX,是否是函数？,定理1若f是XY的双射，则fC是YX的函数。,证明：（1）对任意的yY，由f是双射，得f是满射，所以ranf=Y故domfC=ranf=Y（2）对任意的yY，若存在x1X，x2X使fC且fC则f且f由于f是单射，有x1=x2。由（1）、（2），fC是YX的函数。,逆函数的定义,定义：设f是XY的双射函数，则称fC：YX为f的逆函数，并记f-1。定理：f-1是YX的双射函数。证明：由于ranf-1=domf=X，所以，f-1是满射。对任意xX，若存在y1,y2Y,使得f-1且f-1则f且f，由于f是函数，所以y1=y2，即f-1是单射。因此，f-1是双射。,二.性质,1.定理1设f:XY是双射的函数，则(f-1)-1=f。2.定理2设f:XY是双射的函数，则有f-1f=IX且ff-1=IY。证明：先证明定义域、陪域相等。因为f:XY是双射的，f-1:YX也是双射的，所以f-1f:XX,IX:XX可见f-1f与IX具有相同的定义域和陪域。再证它们的对应规律相同：xX，因f:XY，yY,使得y=f(x),又f可逆，故f-1(y)=x，于是f-1f(x)=f-1(f(x)=f-1(y)=x=IX(x)同理可证ff-1=IY。,3.定理3令f:XY,g:YX是两个函数,如果gf=IX且fg=IY,则g=f-1。证明：证f和g都可逆。因为gf=IX，IX是双射的，由关系复合性质3得，f是入射的和g是满射的。同理由fg=IY，得g是入射的和f是满射的。所以f和g都可逆。显然f-1和g具有相同的定义域和陪域。,证明