离散数学函数.ppt

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

1、5-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。3333R2R1R3R4f下面下面哪些是哪些是R到到R的函数？的函数？ f=|x,yRy= g=|x,yRx2+y2=4

2、 h=|x,yRy= x2 r =|x,yRy=lgx v =|x,yRy= _ 1xx2.定义域、值域和陪域定义域、值域和陪域(共域共域)设设f:XY, f的的定义域定义域(domain)，记作，记作dom f，或或Df 即即 Df =dom f=x|xX y(yY f) =X f的的值域值域(range) ：记作记作ran f， 或或Rf 即或即或f(X) Rf =ran f=f(X)=y| yY x(xX f) f的的陪域陪域(codomain):即是即是Y(称之为称之为f的陪域的陪域)。二二. . 函数的表示方法函数的表示方法 有有 枚举法、枚举法、关系关系图、关系矩阵、谓词描述法。图

3、、关系矩阵、谓词描述法。 三三. .从从X X到到Y Y的的函数的集合函数的集合Y YX X： YX =f| f:XY YX ：它是由：它是由所有所有的从的从X到到Y函数函数构成的集合构成的集合例例 X=1,2,3 Y=a,b 求求所有所有从从X到到Y函数函数结论：结论：若若X X、Y Y是有限集合，且是有限集合，且|X|=m|X|=m，|Y|=n|Y|=n，则，则| |Y YX X|=|Y|=|Y|X|X|=n=nm m。从从X到到Y的关系的关系= |P(X Y)|= Y)|= 2nm.规定：从规定：从 到到 的函数只有的函数只有f=f= 。从从 到到Y Y的函数只有的函数只有f=f= 。若

4、若XX ，则从则从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)。 六六. . 函数的类型函

5、数的类型 例子：例子：X1 Y。123ab。csX Y。123ab4。 。cgX1 Y1。123abd。chX Y。123ab4。 。cfRf=YRs=YRg YRh Y1一对一一对一一对一一对一函数的类型函数的类型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.

6、双射的双射的：f:XY是函数，如果是函数，如果 f 既是满射的，又是既是满射的，又是入射的，则称入射的，则称 f 是是双射的双射的，也称，也称f 是是一一对应的一一对应的。特别地：特别地：Y是单射；是单射； ：是双射。是双射。 思考题思考题：如果：如果 f:XX是入射的函数，则必是满射的，所是入射的函数，则必是满射的，所以以 f 也是双射的。此命题也是双射的。此命题在什么条件下在什么条件下成立吗？成立吗？5-2 5-2 函数的复合函数的复合 关系的复合：关系的复合： 设设R是从是从X到到Y的关系，的关系，S是从是从Y到到Z的关系，的关系，则则R和和S的复合关系记作的复合关系记作R S 。定义为

7、：。定义为： R S =|x X z Zy(y Y R S)函数的复合函数的复合v定义：设定义：设 f:XY, g:WZ是函数是函数,若若f(X) W,则则 g f =|x X z Zy(y Y f g)称为称为g在在f的的左边可左边可复合复合。定理：两个函数的复合是一个函数。定理：两个函数的复合是一个函数。v证明：设证明：设 f:XY, g:WZ是函数是函数,且且f(X) W。v（1）对任意的）对任意的x X，因为，因为f是函数，故存在唯一是函数，故存在唯一的序偶的序偶，使得，使得y=f(x)成立成立,而而f(x) f(X) W,又因为又因为g是函数，故存在唯一的序偶是函数，故存在唯一的序偶

8、，使，使得得z=g(y)成立，根据复合定义，成立，根据复合定义， g f,即即dom g f=X.v（2）假设）假设 g f且且 g f，由复合定，由复合定v义义存在存在y1 Y y2 Y，使得，使得v f g f g,由由于于f、g为函数，所以有，为函数，所以有，y1=y2，因而，因而z1=z2。由（由（1）、（）、（2）得）得g f是是X到到Z的函数。的函数。函数的复合函数的复合一一. . 定义定义: f:XY, g:YZ是函数是函数,则定义则定义 g f =|x X z Zy(y Y f g)则称则称 g f 为为f与与g的复合函数的复合函数(左复合左复合).结论结论: g f(x)=g

9、(f(x)二二. . 复合函数的计算复合函数的计算 计算方法同复合关系的计算计算方法同复合关系的计算. 例例 f:XY, g:YZX=1,2,3 Y=1,2,3,4, Z=1,2,3,4,5, f= ,g= , 则则gf用关系图复合用关系图复合:三三. .函数复合的性质函数复合的性质定理定理1（满足可结合性）（满足可结合性）。 f:XY, g:YZ, h:ZW 是函数是函数,则则 (h g) f=h (g f)。3。2。1。3。2。1。4X Y Z。3。2。1。4。5。3。2。1。3。2。1。4。5X Zg ffg定理定理2. f:XY, g:YZ是两个函数是两个函数, 则则 如果如果f和和g

10、是是 满满射的，则射的，则 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 :X

11、Z,任取任取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 如果如果 g f 是是满满射的，则射的，则g是是 满满射的；射的；如果如果g f 是是入入射的，则射的，则 f 是是入入射的；射的； 如果如果 g f 是是双双射的，则射的，则f是是入入射的射的和和g是是 满满射的。射的。定理定理4 f:XY是函数是函数, 则则 f IX= f 且且 IY f=f 。5-3 5-

12、3 逆函数逆函数R是是A到到B的关系，其逆关系的关系，其逆关系RC是是B到到A的的关系。关系。 RC=| R f:XY fC:YX, 是否是函数？是否是函数？。3。2。1。c。b。a。3。2。1。c。b。af: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。

13、由（由（1）、（）、（2），）， fC是是YX的函数。的函数。逆函数的定义逆函数的定义v定义：设定义：设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

14、: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 :XX , IX:XX可见可见f-1 f 与与IX 具有相同的定义域和陪域。具有相同的定义域和陪域。 再证再证它们的对应规律相同：它们的对应规律相同： xX，因，因f:XY， y Y, 使得使得 y=f(x),又又f 可逆，故可逆，故 f-1(y)=x，于是，于是

15、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具有相同的定义域和陪域。具有相同的定义域和陪域。X Y。123ab。cf。123Xf-1。123X。123XIX证明它们的对应规律相同。证明它们的对应规律相同。 任取任取y Y， 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-1X Y。12ab。cf。12Xg。12X。12XIX