《离散数学 函数资料》由会员分享，可在线阅读，更多相关《离散数学 函数资料（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的函数？ 1。 2。 1。 2。 1。 2。 1。 2。333 3 R2R1R3R4 下面哪些是R到R的函数？ f=|x,yRy= g=|x,yRx2+y2=4 h=|x,yRy= x2 r =|x,yRy=lgx v =|x,yRy= _ 1 x x 2.定义域、值域和陪域(共域) 设f:XY, f的定义域(domain)
2、，记作dom f，或Df 即 Df =dom f=x|xXy(yYf) =X f的值域(range) ：记作ran f， 或Rf 即或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)|= 2
3、nm. 规定：从到的函数只有f=。 从到Y的函数只有f=。 若X，则从X到的函数不存在。 四. 特殊函数 1. 常值函数：函数f:XY ，如果y0Y, 使得对xX, 有f(x)=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)。 六. 函数的类型 例子： X1 Y 。 。 。 。 。 1 2 3 a b 。c s X Y 。 。 。 。 。 1 2 3 a b 4。 。 c g X
4、1 Y1 。 。 。 。 。 1 2 3 a b d 。 。c h X Y 。 。 。 。 。 1 2 3 a b 4。 。 c f Rf=Y Rs=Y RgY RhY1 一对一一对一 函数的类型 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是函数，如果 f 既是满射的，又是 入射的，则称 f 是双射的，也称f 是一一对应的。 特别地：Y是单射；
5、 ：是双射。 思考题：如果 f:XX是入射的函数，则必是满射的，所 以 f 也是双射的。此命题在什么条件下成立吗？ 5-2 函数的复合 关系的复合： 设R是从X到Y的关系，S是从Y到Z的关系， 则R和S的复合关系记作R S 。定义为： R S =|xXzZy(yY RS) 函数的复合 v定义：设 f:XY, g:WZ是函数,若f(X)W, 则 g f =|xXzZy(yY fg) 称为g在f的左边可复合。 定理：两个函数的复合是一个函数。 v证明：设 f:XY, g:WZ是函数,且f(X)W。 v（1）对任意的xX，因为f是函数，故存在唯一 的序偶，使得y=f(x)成立,而f(x)f(X)W,
6、 又因为g是函数，故存在唯一的序偶，使 得z=g(y)成立，根据复合定义，gf,即 dom gf=X. v（2）假设gf且gf，由复合定 v义存在y1Y y2Y，使得 vfg 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:YZ X=1,2,3 Y=1,2,3,4, Z=1,2,3,4,5
7、, f= , g= , 则gf 用关系图复合: 三.函数复合的性质 定理1（满足可结合性）。 f:XY, g:YZ, h:ZW 是函数,则 (h g) f=h (g f) 。 3 。 2 。 1 。 3 。 2 。 1 。 4 X Y Z 。3 。2 。1 。4 。5 。 3 。 2 。 1 。3 。2 。1 。4 。5 X Z g f f g 定理2. f:XY, g:YZ是两个函数, 则 如果f和g是 满射的，则 g f 也是满射的； 如果f和g是入射的，则 g f 也是入射的； 如果f和g是双射的，则 g f 也是双射的。 证明： 设f和g是满射的，因g f :XZ,任取zZ, 因 g:
8、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, 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
9、:XY是函数, 则 f IX= f 且 IYf=f 。 5-3 逆函数 R是A到B的关系，其逆关系RC是B到A的 关系。 RC=|R f:XY fC:YX, 是否是函数？ 。 3 。 2 。 1 。c 。b 。a 。3 。2 。1 。 c 。 b 。 a f:X YfC:Y X 定理1 若f是XY的双射，则fC是YX的函数。 v证明：（1）对任意的yY，由f是双射，得f是满射 ，所以ran f=Y 故 dom fC=ran f=Y （2）对任意的yY，若存在x1X， x2X使 fC 且 fC 则 f 且 f 由于f是单射，有x1=x2。 由（1）、（2）， fC是YX的函数。 逆函数的定义 v
10、定义：设f是XY的双射函数，则称fC：YX为f的逆函 数，并记f-1。 v定理： f-1是YX的双射函数。 v证明：由于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是双射的函数，则有 f-1 f= IX 且 f f-1 = IY 。 证明：先证明定义域、陪域相等。 因为 f:XY是双射的，f-1:YX也是双射的，所以 f-1 f :X
11、X , 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都可逆。 显然
12、f-1和g具有相同的定义域和陪域。 X Y 。 。 。 。 。 1 2 3 a b 。 c f 。 。 。 1 2 3 X f-1 。 。 。 1 2 3 X 。 。 。 1 2 3 X IX 证明它们的对应规律相同。 任取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 X Y 。 。 。 。 1 2 a b 。 c f 。 。 1 2 X g 。 。 1 2 X 。 。 1 2 X IX
