离散数学函数.ppt

《离散数学函数.ppt》由会员分享，可在线阅读，更多相关《离散数学函数.ppt（20页珍藏版）》请在课桌文档上搜索。

1、5-1 函数的基本概念,一.概念定义：X与Y集合，f是从X到Y的关系，如果任何xX，都存在唯一yY，使得f,则称f是从X到Y的函数，(变换、映射)，记作f:X Y,或X Y.如果f:XX是函数,也称f是X上的函数.下面给出A=1,2,3上几个关系，哪些是A到A的函数？,下面哪些是R到R的函数？f=|x,yRy=g=|x,yRx2+y2=4 h=|x,yRy=x2 r=|x,yRy=lgx v=|x,yRy=,2.定义域、值域和陪域(共域),设f:XY,f的定义域(domain)，记作dom f，或Df 即 Df=dom f=x|xXy(yYf)=X f的值域(range)：记作ran f，或R

2、f 即或f(X)Rf=ran f=f(X)=y|yYx(xXf)f的陪域(codomain):即是Y(称之为f的陪域)。,二.函数的表示方法 有 枚举法、关系图、关系矩阵、谓词描述法。三.从X到Y的函数的集合YX：YX=f|f:XY YX：它是由所有的从X到Y函数构成的集合例 X=1,2,3 Y=a,b 求所有从X到Y函数结论：若X、Y是有限集合，且|X|=m，|Y|=n，则|YX|=|Y|X|=nm。从X到Y的关系=|P(X Y)|=2nm.规定：从到的函数只有f=。从到Y的函数只有f=。若X，则从X到的函数不存在。,四.特殊函数,1.常值函数：函数f:XY，如果y0Y,使得对xX,有f(x

3、)=y0,即ran f=y0,称f是常值函数。2.恒等函数：恒等关系IX是X到X函数，即IX:XX,称之为恒等函数。显然对于xX，有 IX(x)=x。五.两个函数相等 设有两个函数f:AB g:AB,f=g 当且仅当 对任何xA，有f(x)=g(x)。,六.函数的类型 例子：,一对一,一对一,函数的类型1.满射的：f:XY是函数，如果 ran f=Y,则称f 是满射的。2.入射的：f:XY是函数，如果对于任何x1,x2X,如果 x1x2 有f(x1)f(x2),(或者若f(x1)=f(x2),则x1=x2),则称f 是入射的，也称f 是单射的，也称f 是一对一的。3.双射的：f:XY是函数，如

4、果 f 既是满射的，又是入射的，则称 f 是双射的，也称f 是一一对应的。特别地：Y是单射；：是双射。思考题：如果 f:XX是入射的函数，则必是满射的，所以 f 也是双射的。此命题在什么条件下成立吗？,5-2 函数的复合,关系的复合：设R是从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作R S。定义为：R S=|xXzZy(yY RS),函数的复合,定义：设 f:XY,g:WZ是函数,若f(X)W,则 g f=|xXzZy(yY fg)称为g在f的左边可复合。,定理：两个函数的复合是一个函数。,证明：设 f:XY,g:WZ是函数,且f(X)W。（1）对任意的xX，因为f是函数，故存在

5、唯一的序偶，使得y=f(x)成立,而f(x)f(X)W,又因为g是函数，故存在唯一的序偶，使得z=g(y)成立，根据复合定义，gf,即dom gf=X.（2）假设gf且gf，由复合定义存在y1Y y2Y，使得fg f g,由于f、g为函数，所以有，y1=y2，因而z1=z2。由（1）、（2）得gf是X到Z的函数。,函数的复合,一.定义:f:XY,g:YZ是函数,则定义 g f=|xXzZy(yY fg)则称 g f 为f与g的复合函数(左复合).结论:g f(x)=g(f(x)二.复合函数的计算 计算方法同复合关系的计算.,例 f:XY,g:YZX=1,2,3 Y=1,2,3,4,Z=1,2,

6、3,4,5,f=,g=,则gf用关系图复合:三.函数复合的性质定理1（满足可结合性）。f:XY,g:YZ,h:ZW 是函数,则(h g)f=h(g f),定理2.f:XY,g:YZ是两个函数,则 如果f和g是 满射的，则 g f 也是满射的；如果f和g是入射的，则 g f 也是入射的；如果f和g是双射的，则 g f 也是双射的。证明：设f和g是满射的，因g f:XZ,任取zZ,因g:YZ是满射的，所以存在yY,使得z=g(y),又因f:XY是满射的，所以存在xX,使得y=f(x),于是有z=g(y)=g(f(x)=g f(x),所以 g f 是满射的。设f和g是入射的，因g f:XZ,任取x1

7、,x2X,x1x2，因f:XY是入射的，f(x1)f(x2),而 f(x1),f(x2)Y，因g:YZ是入射的，g(f(x1)g(f(x2)即g f(x1)g f(x2)所以g f 也是入射的。,定理3 如果 gf 是满射的，则g是 满射的；如果gf 是入射的，则 f 是入射的；如果 gf 是双射的，则f是入射的和g是 满射的。定理4 f:XY是函数,则 f IX=f 且 IYf=f。,5-3 逆函数,R是A到B的关系，其逆关系RC是B到A的关系。RC=|R f:XY fC:YX,是否是函数？,定理1 若f是XY的双射，则fC是YX的函数。,证明：（1）对任意的yY，由f是双射，得f是满射，所

8、以ran f=Y 故 dom fC=ran f=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的双射函数。证明：由于ran f-1=dom f=X，所以，f-1是满射。对任意xX，若存在y1,y2 Y,使得 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

9、是双射的函数，则有 f-1 f=IX 且 f f-1=IY。证明：先证明定义域、陪域相等。因为 f:XY是双射的，f-1:YX也是双射的，所以 f-1 f:XX,IX:XX可见f-1 f 与IX 具有相同的定义域和陪域。再证它们的对应规律相同：xX，因f:XY，yY,使得 y=f(x),又f 可逆，故 f-1(y)=x，于是 f-1 f(x)=f-1(f(x)=f-1(y)=x=IX(x)同理可证 f f-1=IY。,3.定理3 令 f:XY,g:YX是两个函数,如果g f=IX 且 f g=IY,则 g=f-1。证明：证f和g都可逆。因为g f=IX，IX是双射的，由关系复合性质3得，f是入射的和g是 满射的。同理由 f g=IY，得g是入射的和f 是 满射的。所以f和g都可逆。显然f-1和g具有相同的定义域和陪域。,证明它们的对应规律相同。任取yY，f-1(y)=f-1 IY(y)=f-1(f g)(y)=(f-1 f)g(y)=(IX g)(y)=g(y)所以f-1=g注：f-1=g 的两个条件必须同时满足，缺一不可。4.定理4,令 f:XY,g:YX是两个双射函数,则(g f)-1=f-1 g-1,