电子科技大学离散数学第8章函数课件.ppt

1、离离 散散 数数 学学20222022年年8 8月月1515日星期一日星期一电子科技大学电子科技大学67-67-2 22022-8-152022-8-15第第8 8章章 函数函数函数的复合运算函数的复合运算3函数的逆运算函数的逆运算4函数的概念函数的概念1特殊函数特殊函数2函数的运算定理函数的运算定理5内内容容提提要要67-67-3 32022-8-152022-8-158.1 8.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 函数的概念函数的概念2 2 单射、满射单射、满射和双射函数的和双射函数的概念概念3 3 函数的复合函数的复合运算和逆运算运算和逆运算31

2、 1 置换的计算置换的计算21 1 单射、满射单射、满射和双射函数的和双射函数的证明证明2 2 置换的定义置换的定义 67-67-4 42022-8-152022-8-158.2 8.2 函数函数 函数也叫函数也叫映射、变换或对应映射、变换或对应。函数是数学的一个基本概念。这里将高等数学函数是数学的一个基本概念。这里将高等数学中连续函数的概念推广到对离散量的讨论，即将中连续函数的概念推广到对离散量的讨论，即将函函数看作是一种特殊的二元关系数看作是一种特殊的二元关系。函数的概念在日常生活和计算机科学中非常重函数的概念在日常生活和计算机科学中非常重要要。如各种高级程序语言中使用了大量的函数。实。如

3、各种高级程序语言中使用了大量的函数。实际上，际上，计算机的任何输出都可看成是某些输入的函计算机的任何输出都可看成是某些输入的函数。数。67-67-5 52022-8-152022-8-158.2.18.2.1函数的定义函数的定义设设f f是集合是集合A A到到B B的关系，如果对每个的关系，如果对每个xAxA，都存在惟一的，都存在惟一的yByB，使得，使得 ff，则称关，则称关系系f f为为A A到到B B的的函数函数(Function)(Function)(或或映射映射(Mapping)(Mapping)、变换变换(Transform)(Transform)，记为记为f:ABf:AB。A A

4、为函数为函数f f的的定义域定义域，记为，记为domfdomf=A=A；f(A)f(A)为函数为函数f f的的值域值域，记为，记为ranfranf。当当 ff时，通常记为时，通常记为y=f(x)y=f(x)，这时称，这时称x x为为函数函数f f的的自变量自变量，y y为为x x在在f f下的下的函数值函数值(或或象象)，也也称称x x为为y y在在f f下的下的原象原象 。67-67-6 62022-8-152022-8-15结论结论如果关系如果关系f f是函数，那么是函数，那么1.1.f f y=f(x)y=f(x)；2.2.f f f f y=zy=z；3.3.|f|=|A|f|=|A|

5、；4.4.f(x)f(x)表示一个变值，表示一个变值，f f代表一个集合，因此代表一个集合，因此ff(x)ff(x)。如果关系如果关系f f具备下列两种情况之一，那么具备下列两种情况之一，那么f f就不是函数：就不是函数：1.1.存在元素存在元素aAaA，在，在B B中没有象；中没有象；2.2.存在元素存在元素aAaA，有两个及两个以上的象。，有两个及两个以上的象。67-67-7 72022-8-152022-8-15例例8.2.18.2.1设设A=1,2,3,4A=1,2,3,4，B=a,b,c,dB=a,b,c,d，试判断下列关系哪试判断下列关系哪些是函数。些是函数。如果是函数，请写出它的

6、值域。如果是函数，请写出它的值域。（1 1）f f1 1,其中其中A A1,2,3,B1,2,3,Ba,b,ca,b,c；（2 2）f f2 2,其中其中A Aa,b,c,Ba,b,c,Bb,cb,c；（3 3）f f3 3|y|yx x1,x,yR,1,x,yR,其中其中A AB BR R（4 4）f f4 4|y|yx x1,x,yZ1,x,yZ,其中其中A AB BZ Z67-67-8 82022-8-152022-8-15例例8.2.1 8.2.1 解解（1 1）在在f f1 1中中,因为元素因为元素1 1有两个元素有两个元素a,ba,b与它对应与它对应,所所以以f f1 1不是不是A

7、 A到到B B函数；函数；（2 2）在）在f f2 2中中,每个元素都有惟一的象和它对应每个元素都有惟一的象和它对应,所以所以f f2 2是是A A到到B B函数。函数。RanfRanf2 2b,cb,c；（3 3）在）在f f3 3中中,因为每个元素都有惟一的象和它对应因为每个元素都有惟一的象和它对应,所以所以f f3 3是是A A到到B B函数函数,且且ranfranf3 3R R；（4 4）在）在f f4 4中中,因为每个元素都有惟一的象和它对应因为每个元素都有惟一的象和它对应,所以所以f f4 4是是A A到到B B函数函数,且且ranfranf4 42,3,4,2,3,4,。67-6

8、7-9 92022-8-152022-8-15例例8.2.28.2.2设设P P是接受一个整数作为输入并产生一个整数作为是接受一个整数作为输入并产生一个整数作为输出的计算机程序。令输出的计算机程序。令A=B=ZA=B=Z，则由，则由P P确定的关系确定的关系f fp p定义如下：定义如下：如果如果ffp p当且仅当输入当且仅当输入m m时，由程序时，由程序P P所产生所产生的输出是的输出是n n。请判断请判断f fp p是否为函数。是否为函数。67-67-10102022-8-152022-8-15例例8.2.2 8.2.2 解解显然，显然，f fp p是一个函数。因为，任意一个特殊的输入是一

9、个函数。因为，任意一个特殊的输入对应唯一的输出。对应唯一的输出。可用任意一个可能的输入集合可用任意一个可能的输入集合A A对应输出集合对应输出集合B B而推而推广到一般情形的程序。所以，通常把广到一般情形的程序。所以，通常把函数看做输入函数看做输入输出的关系。输出的关系。67-67-11112022-8-152022-8-15例例8.2.38.2.3设设A=a,bA=a,b，B=1,2B=1,2，请分别写出，请分别写出A A到到B B的的不同关系不同关系和和不同函数不同函数。因为因为|A|=2|A|=2，|B|=2|B|=2，所以，所以|A|AB|=|A|B|=|A|B|=4|B|=4，即即A

10、 AB=,B=,，,，此时从此时从A A到到B B的不同的关系有的不同的关系有2 24 4=16=16个。个。67-67-12122022-8-152022-8-15A A到到B B不同的关系不同的关系R R0 0=；R R1 1=；R R2 2=；R R3 3=；R R4 4=；R R5 5=,=,；R R6 6=,=,；R R7 7=,=,；R R8 8=,=,；R R9 9=,=,；R R1010=,=,；R R1111=,=,；R R1212=,=,；R R1313=,=,；R R1414=,=,；R R1515=,=,。67-67-13132022-8-152022-8-15A A到

11、到B B不同的函数不同的函数 f f1 1=,f=,f2 2=,=,，f f3 3=,f=,f4 4=,=,。67-67-14142022-8-152022-8-15函数与关系的差别函数与关系的差别函数是一种函数是一种特殊的关系特殊的关系，它与一般关系比较具备如，它与一般关系比较具备如下下差别：差别：1.1.从从A A到到B B的不同的关系有的不同的关系有2 2|A|A|B|B|个；但从个；但从A A到到B B的的不同的函数却仅有不同的函数却仅有|B|B|A|A|个。个。(个数差别个数差别)2.2.关系的第一个元素可以相同；函数的第一元素关系的第一个元素可以相同；函数的第一元素一定是互不相同的

12、。一定是互不相同的。(集合元素的第一个元素存在差别集合元素的第一个元素存在差别)3.3.每一个函数的基数都为每一个函数的基数都为|A|A|个个(|f|=|A|)(|f|=|A|)，但关，但关系的基数却为从零一直到系的基数却为从零一直到|A|A|B|B|。(集合基数的差别集合基数的差别)67-67-15152022-8-152022-8-15 设设f f是从是从A A到到B B的函数，的函数，对任意对任意x x1 1,x,x2 2AA，如果，如果x x1 1xx2 2，有，有f(xf(x1 1)f(x)f(x2 2)，则称则称f f为从为从A A到到B B的的单射单射（不同的（不同的x x对应不

13、同的对应不同的y)y)；如果如果ranfranfB B，则称，则称f f为为从从A A到到B B的的满射满射；若若f f是是满射且是单射满射且是单射，则称，则称f f为从为从A A到到B B的的双射双射。若若A AB B，则称，则称f f为为A A上的函数上的函数；当；当A A上的函数上的函数f f是双射是双射时，称时，称f f为一个为一个变换变换。8.2.28.2.2函数的类型函数的类型67-67-16162022-8-152022-8-15将定义将定义8.2.28.2.2的描述数学化为的描述数学化为1.1.f:ABf:AB是单射是单射当且仅当对任意当且仅当对任意x x1 1,x,x2 2A

14、A，若若x x1 1xx2 2，则，则f(xf(x1 1)f(x)f(x2 2)；2.2.f:ABf:AB是满射当且仅当对任意是满射当且仅当对任意yByB，一定存在，一定存在xBxB，使得，使得f(x)=yf(x)=y；3.3.f:ABf:AB是双射当且仅当是双射当且仅当f f既是单射，又是满射；既是单射，又是满射；4.4.f:ABf:AB是变换当且仅当是变换当且仅当f f是双射且是双射且A=BA=B。67-67-17172022-8-152022-8-15例例8.2.48.2.4确定下列函数的类型。确定下列函数的类型。1.1.设设A=1,2,3,4,5A=1,2,3,4,5，B=a,b,c,

15、dB=a,b,c,d。f:ABf:AB定义定义为：为：,；2.2.设设A=1,2,3A=1,2,3，B=a,b,c,dB=a,b,c,d。f:ABf:AB定义为：定义为：f=,f=,；3.3.设设A=1,2,3A=1,2,3，B=1,2,3B=1,2,3。f:ABf:AB定义为定义为f=,f=,；67-67-18182022-8-152022-8-15例例8.2.4 8.2.4 解解1.1.因为对任意因为对任意yByB，都存在，都存在xBxB，使得，使得ff，所以所以f f是满射函数是满射函数；2.2.因为因为A A中不同的元素对应不同的象，所以中不同的元素对应不同的象，所以f f是单是单射函

16、数；射函数；3.3.因为因为f f既是单射函数，又是满射函数，所以既是单射函数，又是满射函数，所以f f是是双射函数双射函数。又因为。又因为A=BA=B，所以，所以f f还是变换还是变换。67-67-19192022-8-152022-8-15设设A A，B B为为有限集合有限集合，f f是从是从A A到到B B的函数，则：的函数，则：1.1.f f是单射的必要条件为是单射的必要条件为|A|B|A|B|；2.2.f f是满射的必要条件为是满射的必要条件为|B|A|B|A|；3.3.f f是双射的必要条件为是双射的必要条件为|A|A|B|B|。结论结论A BA A1 12 23 34 45 56

17、 6a ab bc cd de eB Bf f3 3A A1 12 23 34 45 5e ea ab bc cd df fB Bf f4 4A A1 12 23 34 45 56 6a ab bc cd de eB Bf f5 5A A1 12 23 34 45 5a ab bc cd de eB Bf f6 667-67-20202022-8-152022-8-15定理定理8.2.18.2.1设设A A，B B是有限集合，且是有限集合，且|A|=|B|A|=|B|，f f是是A A到到B B的函数，的函数，则则f f是单射当且仅当是单射当且仅当f f是满射。是满射。证明证明 必要性必要性(

18、)：设设f f是单射是单射。显然，显然，f f是是A A到到f(A)f(A)的满射，的满射，故故f f是是A A到到f(A)f(A)的双射，的双射，因此因此|A|=|f(A)|A|=|f(A)|。由由|f(A)|=|B|f(A)|=|B|，且，且f(A)f(A)B B，得得f(A)=Bf(A)=B，故故f f是是A A到到B B的满射。的满射。67-67-21212022-8-152022-8-15定理定理8.2.18.2.1（续）（续）充分性充分性()：设设f f是满射。是满射。任取任取x x1 1,x,x2 2AA，x x1 1xx2 2，假设，假设f(xf(x1 1)=f(x)=f(x2

19、 2)，由于由于f f是是A A到到B B的满射，的满射，所以所以f f也是也是A-xA-x1 1 到到B B的满射，的满射，故故|A-x|A-x1 1|B|B|，即即|A|-1|B|A|-1|B|，这与这与|A|=|B|A|=|B|矛盾。矛盾。因此因此f(xf(x1 1)f(x)f(x2 2)，故故f f是是A A到到B B的单射。的单射。67-67-22222022-8-152022-8-15例例8.2.58.2.5设设X=0,1,2,X=0,1,2,，Y=1,1/2,1/3,Y=1,1/2,1/3,，f:Xf:XY Y的定义如下：的定义如下：1.1.f f1 1=,=,2.2.f f2

20、2=,=,3.3.f f3 3=,=,n,1,。试判断它们的类型。试判断它们的类型。67-67-23232022-8-152022-8-15例例8.2.5 8.2.5 解解1.1.由已知得，由已知得，根据函数根据函数f f1 1(n)(n)的表达式和单射函数的定义知，的表达式和单射函数的定义知，f f1 1是是单射函数；但是，单射函数；但是，Y Y中元素中元素1 1没有原象，没有原象，所以所以f f1 1不不是满射函数；是满射函数；2.2.由已知得，由已知得，显然显然f f2 2是满射函数。但是，是满射函数。但是，X X中元素中元素0 0和和1 1有相同的象有相同的象1 1，所以，所以f f2

21、 2不是单射函数不是单射函数；1 1f(n)=,n=0,1,2,f(n)=,n=0,1,2,n+2n+21,0,11,0,1f(n)=f(n)=1 1,n=2,3,n=2,3,n n67-67-24242022-8-152022-8-15例例8.2.5 8.2.5 解解3.3.由已知得，由已知得，显然显然，f f是双射函数。是双射函数。1 1f(n)=,n=0,1,2,f(n)=,n=0,1,2,n+1n+167-67-25252022-8-152022-8-15例例8.2.68.2.6设设A=B=R(A=B=R(实数集实数集)。试判断下列函数的类型。试判断下列函数的类型。（1 1）f f1

22、1=x,x=|xR|xR；（2 2）f f2 2=|xR=|xR；（3 3）f f3 3=x,e=|xR|xR；（1 1）f f1 1仅是一般函数；仅是一般函数；（2 2）f f2 2是双射函数；是双射函数；（3 3）f f3 3是单射函数。是单射函数。67-67-26262022-8-152022-8-15典型典型(自然自然)映射映射。设。设R R是集合是集合A A上的一个等价关系，上的一个等价关系，g g：AA/RAA/R称为称为A A对商集对商集A/RA/R的的典型典型(自然自然)映射映射，其定义为其定义为g(a)g(a)aaR R，a aA.A.证明：典型映射是一个满射。证明：典型映射

23、是一个满射。例例8.2.78.2.7分析：由等价类的定义，对任意分析：由等价类的定义，对任意aaR RA/RA/R，aaaaR R，即，即任意任意A/RA/R中的元素都有原象，中的元素都有原象，所以典型所以典型映射是满射。映射是满射。证明过程留给读者。证明过程留给读者。67-67-27272022-8-152022-8-15设设是偏序集，是偏序集，对任意对任意aAaA，令：，令：f(a)f(a)x|(xA)(xa)x|(xA)(xa)f f是一个从是一个从A A到到P P(A)A)的一个的一个单射函数单射函数，并且，并且f f保持保持 A,与与P(的的偏序关系偏序关系，即：对任意，即：对任意a

24、,bAa,bA，若，若abab，则，则f(a)f(a)f(b)f(b)。例例8.2.8 8.2.8 1)1)f f是映射是映射。任取任取aAaA，由于，由于f(a)f(a)x|(xA)(xa)x|(xA)(xa)A A，所以所以f(a)f(a)P P(A)(A)，即即f f是从是从A A到到P(P(A)A)的映射的映射。67-67-28282022-8-152022-8-152)2)f f是是单单射射。对任意对任意a,ba,bAA，ab ab 若若a,ba,b存在偏序存在偏序关系，关系，不妨设不妨设abab(或或baba)，由于由于“”是反对称是反对称的，所以的，所以ba(ba(或或abab)

25、，从而，从而b b f(a)f(a)x|(xA)xax|(xA)xa（或（或a a f(b)f(b)，而而“”是自反的，所以是自反的，所以bb(bb(或或aaaa)，即，即bf(b)bf(b)(或或af(a)af(a)，所以，所以f(a)f(b)f(a)f(b)。若若a,ba,b不存在偏序关系，不存在偏序关系，则有：则有：abab，从而，从而a a f(b)f(b)x|(xA)xbx|(xA)xb，而而“”是自反的，所以是自反的，所以aaaa，即，即af(a)af(a)，即，即f(a)f(b)f(a)f(b)。例例8.2.88.2.8(续续)67-67-29292022-8-152022-8-

26、15例例8.2.88.2.8(续续)2)2)对任意对任意a,bAa,bA，若若abab，则：，则：任取任取yf(a)yf(a)，则，则yaya，由，由abab，根据根据“”的传递性的传递性，有，有ybyb，从而，从而yf(b)yf(b)，所以所以f(a)f(a)f(b)f(b)。67-67-30302022-8-152022-8-15设设A A1,2,3,1,2,3,n,n，f f是是A A到到A A的满射的满射，并且具有性，并且具有性质：质：f(xf(xi i)y yi i，i i1,2,3,1,2,3,k,k，knkn，x xi i,y,yi iAA。求求f f的个数。的个数。例例8.2.

27、98.2.9：f f是有限集是有限集A A到到A A的满射，由定理的满射，由定理8.2.18.2.1知知f f是是A A到到A A的双射。的双射。由于由于f f已确定已确定A A中的某中的某k k个元素与另外个元素与另外k k个元素的对应个元素的对应所以只需考虑对剩下所以只需考虑对剩下n-kn-k个元素的对应，为此，令个元素的对应，为此，令B BA-xA-xi i|i|i1,2,3,1,2,3,k;C,k;CA-yA-yi i|i|i1,2,3,1,2,3,k,k则从则从B B到到C C的满射个数的满射个数(即是双射个数即是双射个数)就是就是f f的个数。的个数。根据推论根据推论2.3.12.

28、3.1有，有，从从A A到到A A的满足题目条件的不同的满足题目条件的不同满射个数共有满射个数共有(n-k)!(n-k)!。67-67-31312022-8-152022-8-158.2.38.2.3常用函数常用函数（1 1）如果如果A=BA=B，且对，且对任意任意xAxA，都有，都有f(x)=xf(x)=x，则称，则称f f为为A A上的上的恒等函数，恒等函数，记为记为I IA A。（2 2）如果如果 bBbB，且对，且对任意任意xAxA，都有，都有f(x)=bf(x)=b，则，则称称f f为为常值函数常值函数。（3 3）设设A A是全集是全集U=uU=u1 1,u,u2 2,u,un n

29、的一个子集，则子的一个子集，则子集集A A的的特征函数特征函数定义为从定义为从U U到到0,10,1的一个函数，且的一个函数，且i iAiAii i1uA1uAf(u)=f(u)=0uA0uA67-67-32322022-8-152022-8-15（4 4）对有理数）对有理数x x，f(x)f(x)为大于等于为大于等于x x的最小的整数，的最小的整数，则称则称f(x)f(x)为为上取整函数上取整函数(强取整函数强取整函数)，记为，记为f(x)=f(x)=；（5 5）对有理数）对有理数x x，f(x)f(x)为小于等于为小于等于x x的最大的整数，的最大的整数，则称则称f(x)f(x)为为下取整

30、函数下取整函数(弱取整函数弱取整函数)，记为，记为f(x)=f(x)=；x x x x 67-67-33332022-8-152022-8-15例例8.2.108.2.10设设A=B=R(A=B=R(实数集实数集)。试指出下列函数的类型。试指出下列函数的类型。（1 1）f f1 1=|xR=|xR；（2 2）f f2 2=|xR,aR=|xR,aR；（3 3）f f3 3=|xR=|xR；（4 4）f f4 4=|xR=|xR。（1 1）f f1 1是恒等函数，是恒等函数，（2 2）f f2 2是常值函数，是常值函数，（3 3）f f3 3是上取整函数，是上取整函数，（4 4）f f4 4是下

31、取整函数。是下取整函数。x x x x 67-67-34342022-8-152022-8-158.2.58.2.5函数的应用函数的应用 P(AP(An n)到到B Bn n可以按照如下的方式建立关系：对任意可以按照如下的方式建立关系：对任意S SPP(A(An n)，令，令f(S)f(S)b b1 1b b2 2b b3 3b bn n，其中：其中：i ii ii i1,aS，1,aS，b=i=1,2,n.b=i=1,2,n.0,aS，0,aS，设设A An naa1 1,a,a2 2,a,a3 3,a,an n 是是n n个元素的有限个元素的有限集，集，B Bn nbb1 1 b b2 2

32、b b3 3b bn n|b|bi i0,10,1，试建立试建立P P(A An n)到到B Bn n的一个双射。的一个双射。67-67-35352022-8-152022-8-15（2 2）证明）证明f f是双射。是双射。1)1)证证f f是映射。是映射。显然，显然，f f是是P(AP(An n)到到B Bn n的映射。的映射。2)2)证证f f是单射是单射。任取任取S S1 1,S,S2 2PP(A(An n)，S S1 1SS2 2，则存在元素则存在元素a aj j(1jn)(1jn)，使得，使得a aj jSS1 1，a aj j S S2 2或或a aj jSS2 2，a aj j

33、S S1 1。从而从而f(Sf(S1 1)b b1 1b b2 2b b3 3b bn n中必有中必有b bj j1 1，f(Sf(S2 2)c c1 1c c2 2c c3 3c cn n必有必有c cj j0 0或或f(Sf(S1 1)b b1 1b b2 2b b3 3b bn n中必有中必有b bj j0 0，f(Sf(S2 2)c c1 1c c2 2c c3 3c cn n必有必有c cj j1 1。所以。所以f(Sf(S1 1)f(S)f(S2 2)，即即f f是单射是单射。例例8.2.11(8.2.11(续续)67-67-36362022-8-152022-8-15例例8.2.

34、118.2.11(续续)3)3)证证f f是满射是满射。任取二进制数。任取二进制数b b1 1b b2 2b b3 3b bn nBBn n，对，对每一个二进制数每一个二进制数b b1 1b b2 2b b3 3b bn n，建立对应的集合，建立对应的集合S S A An n，S Saai i|若若b bi i1(1(即若即若b bi i1 1，令，令a ai iSS，否则，否则a ai i S)S)，则，则SPSP(A(An n)，从而，从而f(S)f(S)b b1 1b b2 2b b3 3b bn n，故，故f f是满射。是满射。由由1)1)、2)2)和和3)3)知，知，f f是双射。是

35、双射。例如例如A A3 3=a=a1 1,a,a2 2,a,a3 3，则有：，则有：000,000,a a1 1110,a110,a2 2010,010,aa3 3001,a001,a1 1,a,a2 2110,a110,a1 1,a,a3 3101,101,aa2 2,a,a3 3011,a011,a1 1,a,a2 2,a,a3 3111111。67-67-37372022-8-152022-8-15例例8.2.12 8.2.12 假设在计算机内存中有编号从假设在计算机内存中有编号从0 0到到1010的存储单元，的存储单元，见图见图8.2.28.2.2。图。图8.2.28.2.2表示了在初

36、始时刻全为空的单表示了在初始时刻全为空的单元中，按次序元中，按次序1515、558558、3232、132132、102102和和5 5存入后的存入后的情形。现希望能在这些存储单元中存储任意的非负情形。现希望能在这些存储单元中存储任意的非负整数并能进行检索，整数并能进行检索，试用试用HashHash函数方法完成函数方法完成257257的的存储和存储和558558的检索的检索。132 0 1 2 3 4 5 6 7 8 9 10 0 图图8.2.21021552595583267-67-38382022-8-152022-8-15解解因为因为h(259)=259 mod11=6h(259)=25

37、9 mod11=6，所以，所以257257应该存放在位应该存放在位置置6 6；又因为又因为h(558)=8h(558)=8，所以检查位置，所以检查位置8 8，558558恰好在位置恰好在位置8 8。对于一个对于一个HashHash函数函数H H，如果，如果H(x)=H(y)H(x)=H(y)，但，但xyxy，便，便称称冲突发生冲突发生了。为了解决冲突，需要了。为了解决冲突，需要冲突消解策略冲突消解策略。67-67-39392022-8-152022-8-15例例8.2.138.2.13存在计算机磁盘上的数据或数据网络上传输的数存在计算机磁盘上的数据或数据网络上传输的数据通常表示为字节串。据通常

38、表示为字节串。每个字节由每个字节由8 8个字组成个字组成，要表示要表示100100字位的数据需要多少字节。字位的数据需要多少字节。解解 因为因为s=s=，所以表示，所以表示100100字位的数据字位的数据需要需要1313字节。字节。100/81367-67-40402022-8-152022-8-15例例8.2.148.2.14在异步传输模式在异步传输模式(ATM)(ATM)下，下，数据按数据按5353字节分组，字节分组，每组称为一个信元。每组称为一个信元。以速率每秒以速率每秒500500千字位传输千字位传输数据的连接上一分钟能传输多少个数据的连接上一分钟能传输多少个ATMATM信元。信元。解

39、 因 为 一 分 钟 能 够 传 输 的 字 节 数 为解 因 为 一 分 钟 能 够 传 输 的 字 节 数 为 =3 7 5 0 0 0 0=3 7 5 0 0 0 0，所 以 一 分 钟 能 传 输 的 信 元 数，所 以 一 分 钟 能 传 输 的 信 元 数为为 。3750000707545350060867-67-41412022-8-152022-8-158.38.3函数的运算函数的运算8.3.18.3.1函数的复合运算函数的复合运算考虑考虑f f：ABAB，g g：BCBC是两个函数，则是两个函数，则f f与与g g的复合运算的复合运算R R S S|xAzC|xAzC(y)y

40、)(yBxRyySz)(yBxRyySz)是从是从A A到到C C的函数，记为的函数，记为f f g g：ACAC ，称为函数，称为函数f f与与g g的的。67-67-42422022-8-152022-8-15注意注意1.1.函数函数f f和和g g可以复合可以复合 ranfranf domgdomg；2.2.dom(fog)=domfdom(fog)=domf，ran(fog)ran(fog)rangrang；3.3.对任意对任意xAxA，有，有fog(x)=g(f(x)fog(x)=g(f(x)。67-67-43432022-8-152022-8-15例例8.3.18.3.1设设A=1

41、,2,3,4,5A=1,2,3,4,5，B=a,b,c,dB=a,b,c,d，C=1,2,3,4,5C=1,2,3,4,5，函数函数f:ABf:AB，g:BCg:BC定义如下：定义如下：f=,f=,；g=,g=,。求求fogfog。fog=,fog=,67-67-44442022-8-152022-8-15例例8.3.28.3.2设设f:RRf:RR，g:RRg:RR，h:RRh:RR，满足，满足f(x)=2xf(x)=2x，g(x)g(x)(x+1)(x+1)2 2，h(x)h(x)x/2x/2。计算：。计算：（1 1）f f g g，g g f f；（2 2）(f(f g)g)h h，f

42、f(g(g h h)；（3 3）f f h h，h h f f。（1 1）f f g(x)g(x)g(f(x)g(f(x)g(2x)g(2x)(2x+1)(2x+1)2 2；g g f(x)f(x)f(g(x)f(g(x)f(x+1)f(x+1)2 2)2(x+1)2(x+1)2 2；67-67-45452022-8-152022-8-15（2 2）(f(f g)g)h)(x)h)(x)h(fh(f g)(x)g)(x)h(g(f(x)h(g(f(x)h(g(2x)h(g(2x)h(2x+1)h(2x+1)2 2)(2x+1)(2x+1)2 2/2/2；(f(f(g g h)(x)=(h)(x

43、)=(g g h h)(f(x)(f(x)h(g(f(x)h(g(f(x)h(g(2x)h(g(2x)h(2x+1)h(2x+1)2 2)(2x+1)(2x+1)2 2/2/2；（3 3）f f h(x)h(x)h(f(x)h(f(x)h(2x)h(2x)x x；h h f(x)f(x)f(h(x)f(h(x)f(x/2)f(x/2)x x；例例8.3.28.3.2 （续）（续）67-67-46462022-8-152022-8-15设设f f和和g g分别是分别是A A到到B B和从和从B B到到C C的函数，则：的函数，则：如如f,gf,g是满射，则是满射，则f f g g也是从也是从A

44、A到到C C满射；满射；如如f,gf,g是单射，则是单射，则f f g g也是从也是从A A到到C C单射；单射；如如f,gf,g是双射，则是双射，则f f g g也是从也是从A A到到C C双射。双射。定理定理8.3.1 8.3.1：1)1)对对任意任意cCcC，由于由于g g是满射，所以存在是满射，所以存在bBbB，使得，使得g(b)g(b)c c。对于对于bBbB，又因又因f f是满射，是满射，所以存在所以存在aAaA，使得，使得f(a)f(a)b b。从而有从而有 f f g g(a)(a)g(f(a)g(f(a)g(b)g(b)c c。即即存在存在aAaA，使得：，使得：f f g

45、g(a)(a)c c，所以，所以f f g g是满射是满射。67-67-47472022-8-152022-8-152)2)对任意对任意a a1 1,a,a2 2AA，a a1 1aa2 2，由于由于f f是单射，所以是单射，所以f(af(a1 1)f(a)f(a2 2)。令令b b1 1f(af(a1 1)，b b2 2f(af(a2 2)，由于由于g g是单射，所以是单射，所以g(bg(b1 1)g(b)g(b2 2)，即，即g(f(ag(f(a1 1)g(f(a)g(f(a2 2)。从而有从而有f f g(ag(a1 1)f)f g(ag(a2 2)，所以所以f f g g是单射。是单射

46、。3)3)是是1)1)、2)2)的直接结果的直接结果。定理定理8.3.18.3.1(续续)67-67-48482022-8-152022-8-15定理定理8.3.28.3.2设设f f和和g g分别是分别是A A到到B B和和B B到到C C的函数，则的函数，则1.1.如如fogfog是是A A到到C C的的满射满射，则，则g g是是B B到到C C 的的满射；满射；2.2.如如fogfog是是A A到到C C的的单射单射，则，则f f是是A A到到B B的的单射单射；3.3.如如fogfog是是A A到到C C的双射，则的双射，则f f是是A A到到B B的单射，的单射，g g是是B B到到

47、C C的满射。的满射。67-67-49492022-8-152022-8-15证明证明 （1）对任意cC,由于fog是从A到C的满射,所以存在aA,使得fog(a)c,即g(f(a)c。又因为f是从A到B的函数,所以存在bB,使得f(a)b。即对任意cC,存在bB使得g(b)c。根据满射的定义,g是从B到C的满射。67-67-50502022-8-152022-8-15（2）对任意a1,a2A,a1a2。由于fog是从A到C的单射,所以fog(a1)fog(a2),即g(f(a1)g(f(a2)。又因为g是从B到C的函数,所以f(a1)f(a2),即f是从A到B的单射。（3）由(1)和(2)直

48、接得到。67-67-51512022-8-152022-8-158.3.28.3.2函数的逆运算函数的逆运算定义定义8.3.2 8.3.2 设设f:ABf:AB的函数。如果的函数。如果f f-1-1|x|xA Ay yBBf f 是从是从B B到到A A的函数，则称的函数，则称f f-1-1：B BAA的的逆函数。逆函数。由定义由定义8.3.28.3.2可以看出，可以看出，一个函数的逆运算也是函一个函数的逆运算也是函数。即数。即逆函数逆函数f f-1-1存在当且仅当存在当且仅当f f是双射是双射。A A1 12 23 34 45 56 6a ab bc cd de eB Bf f3 3A A1

49、 12 23 34 45 5e ea ab bc cd df fB Bf f4 4A A1 12 23 34 45 56 6a ab bc cd de eB Bf f5 5A A1 12 23 34 45 5a ab bc cd de eB Bf f6 667-67-52522022-8-152022-8-15例例8.3.38.3.3试求出试求出下列函数的逆函数。下列函数的逆函数。（1 1）设）设A=1,2,3A=1,2,3，B=1,2,3B=1,2,3。f f1 1:AB:AB定义为定义为 f f1 1=,=,；（2 2）f f2 2=,=,（3 3）f f3 3=|xR=|xR。67-67

50、-53532022-8-152022-8-15解解(1)(1)因因f f1 1=,=,，所以，所以 f f1 1-1-1=,=,；(2)(2)因因f f2 2=,=,，所以所以f f2 2-1-1=,=,；（3 3）因为）因为f f3 3=|xR=|xR，所以，所以 f f3 3-1-1=|xR=|xR =|xR=|xR。67-67-54542022-8-152022-8-15定理定理8.3.3 8.3.3 设设f f是是A A到到B B的双射函数，则：的双射函数，则：f f-1-1 f fI IB B|bB|bB；f f f f-1-1I IA A|aA|aA；I IA A f ff f I