离散数学-函数.ppt

5-1 5-1 函数的基本概念函数的基本概念一一.概念概念定义：定义：X与与Y集合，集合，f是从是从X到到Y的关系，如果任何的关系，如果任何x X，都存在唯一都存在唯一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。3333R2R1R3R4下面下面哪些是哪些是R到到R的函数？的函数？f=|x,y R y=g=|x,y R x2+y2=4 h=|x,y R y=x2 r=|x,y R y=lgx v=|x,y R y=_ 1xx2.定义域、值域和陪域定义域、值域和陪域(共域共域)设设f:XY,f的定义域的定义域(domain)，记作，记作dom f，或或Df 即即 Df=dom f=x|x X y(y Y f)=X f的值域的值域(range)：记作记作ran f，或或Rf 即或即或f(X)Rf=ran f=f(X)=y|y Y x(x X f)f的陪域的陪域(codomain):即是即是Y(称之为称之为f的陪域的陪域)。二二.函数的表示方法函数的表示方法 有有 枚举法、枚举法、关系关系图、关系矩阵、谓词描述法。图、关系矩阵、谓词描述法。三三.从从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=。若若XX，则从则从X X到到 的函数不存在的函数不存在。四四.特殊函数特殊函数 1.常值函数：函数常值函数：函数f:XY，如果，如果 y0Y,使得对使得对 x X,有有f(x)=y0,即即ran f=y0,称称f是常值函数。是常值函数。2.恒等函数：恒等关系恒等函数：恒等关系IX是是X到到X函数，即函数，即IX:XX,称之为称之为恒等函数。显然对于恒等函数。显然对于 x X，有，有 IX(x)=x。五五 .两个函数相等两个函数相等 设有两个函数设有两个函数f:AB g:AB,f=g 当且仅当当且仅当 对任何对任何x A，有，有f(x)=g(x)。六六.函数的类型函数的类型 例子：例子：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,x2 X,如果如果 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 5-2 函数的复合函数的复合 关系的复合：关系的复合：设设R是从是从X到到Y的关系，的关系，S是从是从Y到到Z的关系，的关系，则则R和和S的复合关系记作的复合关系记作R S。定义为：。定义为：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是函数，故存在唯一的是函数，故存在唯一的序偶序偶，使得，使得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(f(x)二二.复合函数的计算复合函数的计算 计算方法同复合关系的计算计算方法同复合关系的计算.例例 f:XY,gYZX=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是是 满射的，则满射的，则 g f 也是满射的；也是满射的；如果如果f和和g是是入射的，则入射的，则 g f 也是入射的；也是入射的；如果如果f和和g是是双射的，则双射的，则 g f 也是双射的。也是双射的。证明：证明：设设f和和g是是满射的，因满射的，因g f:XZ,任取任取z Z,因因g:YZ是是满射的，所以存在满射的，所以存在y Y,使得使得z=g(y),又因又因f:XY是是满射的，所以存在满射的，所以存在x X,使得使得y=f(x),于是有于是有z=g(y)=g(f(x)=g f(x),所以所以 g f 是是满射的。满射的。设设f和和g是是入射的，因入射的，因g f:XZ,任取任取x1,x2 X,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-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）对任意的）对任意的y Y，由，由f是双射，得是双射，得f是满射，是满射，所以所以ran f=Y 故故 dom fC=ran f=Y （2）对任意的）对任意的y Y，若存在，若存在x1 X，x2 X使使 fC 且且 fC 则则 f 且且 f 由于由于f是单射，有是单射，有x1=x2。由（由（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是满射。是满射。对任意对任意x X，若存在，若存在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:XX,IX:XX可见可见f-1 f 与与IX 具有相同的定义域和陪域。具有相同的定义域和陪域。再证它们的对应规律相同：再证它们的对应规律相同：xX，因，因f:XY，y Y,使得使得 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具有相同的定义域和陪域。具有相同的定义域和陪域。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