第8章-函数-电子科大离散数学内部教学课件.ppt

《第8章-函数-电子科大离散数学内部教学课件.ppt》由会员分享，可在线阅读，更多相关《第8章-函数-电子科大离散数学内部教学课件.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离 散 数 学示 范 性 软 件 学 院26 26 五月五月 2023 20232电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程第三篇第三篇 二元关系二元关系第第8 8章章 函数函数3电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.0 8.0 内容提要内容提要集合的概念集合的概念1集合的表示方法集合的表示方法2函数的复合运算函数的复合运算3函数的逆运算函数的逆运算4无限集合无限集合5函数的概念函数的概念1特殊函数特殊函数2函数的运算定理函数的运算定理54电子

2、科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.1 8.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 函数的概念函数的概念2 2 单射、满射单射、满射和双射函数的和双射函数的概念概念3 3 函数的复合函数的复合运算和逆运算运算和逆运算31 1 置换的计算置换的计算21 1 单射、满射单射、满射和双射函数的和双射函数的证明证明2 2 置换的定义置换的定义 5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.2.18.2.1函数的定

3、义函数的定义定义定义定义定义8.2.1 8.2.1 8.2.1 8.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为函数为函数f f的的定义域定义域，记为，记为domf=Adomf=A；f(A)f(A)为函数为函数f f的的值域值域，记为，记为ranfranf。函数

4、定义的示意图见图函数定义的示意图见图8.2.18.2.1。AxBf(x)图图8.2.17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程结论结论（1 1）ffy=f(x)y=f(x)；（2 2）ffffy=zy=z；（3 3）|f|=|A|f|=|A|；（4 4）f(x)f(x)表示一个变值，表示一个变值，f f代表一个集合，因代表一个集合，因此此ff(x)ff(x)。如果关系如果关系f f具备下列两种情况之一，那么具备下列两种情况之一，那么f f就不就不是函数：是函数：（1 1）存在元素）存在元素aAaA，在，在B B中没有象；中没有象；（2 2）存在元素）存在元

5、素aAaA，有两个及两个以上的象。，有两个及两个以上的象。8电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.18.2.1设设A=1,2,3,4,B=a,b,c,dA=1,2,3,4,B=a,b,c,d，试判断下列关系哪试判断下列关系哪些是函数。些是函数。如果是函数，请写出它的值域。如果是函数，请写出它的值域。（1 1）f f1 1=,=,；（2 2）f f2 2=,=,；（3 3）f f3 3=,=,；（4 4）f f4 4=,=,。9电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程10电子科技大学离散数学课程组电子科技大学离

6、散数学课程组国家精品课程国家精品课程例例判断下图所示的几个关系是否是函数判断下图所示的几个关系是否是函数：A A1 12 23 34 45 56 6a ab bc cd de eB Bf f1 1A A1 12 23 34 45 5e ea ab bc cd df fB Bf f4 4A A1 12 23 34 45 5a ab bc cd de eB Bf f6 6A A1 12 23 34 45 56 6a ab bc cd de eB Bf f2 2A A1 12 23 34 45 56 6a ab bc cd de eB Bf f3 3A A1 12 23 34 45 56 6a ab

7、 bc cd de eB Bf f5 5f f1 1不是函数。因不是函数。因f f1 1中中A A的元素的元素5 5没出现在序偶的第一元素中没出现在序偶的第一元素中f f2 2不是函数。不是函数。f f2 2中中A A的元素的元素4 4出现出现在两个不同序偶的第一元素中。在两个不同序偶的第一元素中。f f3 3是函数是函数f f4 4是函数。是函数。f f5 5是函数是函数f f6 6是函数是函数11电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.28.2.2设设P P是接受一个整数作为输入并产生一个整数作为输是接受一个整数作为输入并产生一个整数作为输出

8、的计算机程序。令出的计算机程序。令A=B=ZA=B=Z，则由，则由P P确定的关系确定的关系f fp p定义定义如下：如下：如果如果ffp p当且仅当输入当且仅当输入m m时，由程序时，由程序P P所产生的所产生的输出是输出是n n。请判断请判断f fp p是否为一函数。是否为一函数。12电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程13电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.38.2.3设设A=a,b,B=1,2A=a,b,B=1,2，请分别写出，请分别写出A A到到B B的的不同关系不同关系和和不同函数不同函数。

9、解解解解 因为因为|A|=2,|B|=2|A|=2,|B|=2，所以，所以|AB|=|A|B|=4|AB|=|A|B|=4，即即AB=,AB=,，,，此时从此时从A A到到B B的不同的关系有的不同的关系有2 24 4=16=16个。个。14电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程15电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程函数是一种函数是一种特殊的关系特殊的关系，它与一般关系比较具备，它与一般关系比较具备如下如下差别：差别：函数与关系的差别函数与关系的差别1)1)从从A A到到B B的不同的关系有的不同的关系有2 2|A

10、|A|B|B|个；但从个；但从A A到到B B的的不同的函数却仅有不同的函数却仅有|B|B|A|A|个。个。(个数差别个数差别)2)2)关系的第一个元素可以相同；函数的第一元素关系的第一个元素可以相同；函数的第一元素一定是互不相同的。一定是互不相同的。3)3)(集合元素的第一个元素存在差别集合元素的第一个元素存在差别)3)3)每一个函数的基数都为每一个函数的基数都为|A|A|个个(|f|=|A|)(|f|=|A|)，但关，但关系的基数却为从零一直到系的基数却为从零一直到|A|B|A|B|。(集合基数的差别集合基数的差别)16电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精

11、品课程定义定义定义定义8.2.28.2.28.2.28.2.2 设设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对应不同的对应不同的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上

12、的函数上的函数f f是双是双射时，称射时，称f f为一个为一个变换变换。8.2.28.2.2函数的类型函数的类型17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程18电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.48.2.4确定下列函数的类型。确定下列函数的类型。（1 1）设）设A=1,2,3,4,5,B=a,b,c,dA=1,2,3,4,5,B=a,b,c,d。f:ABf:AB定义定义为：为：,；（2 2）设）设A=1,2,3,B=a,b,c,dA=1,2,3,B=a,b,c,d。f:ABf:AB定义为：定义为：f=,f

13、=,；（3 3）设）设A=1,2,3,B=1,2,3A=1,2,3,B=1,2,3。f:ABf:AB定义为定义为f=,f=,；19电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.4 8.2.4 解解（1 1）因为对任意）因为对任意yByB，都存在，都存在xBxB，使得，使得ff，所以，所以f f是满射函数是满射函数；（2 2）因为）因为A A中不同的元素对应不同的象，所以中不同的元素对应不同的象，所以f f是是单射函数；单射函数；（3 3）因为）因为f f既是单射函数，又是满射函数，所以既是单射函数，又是满射函数，所以f f是双射函数是双射函数。又因为。

14、又因为A=BA=B，所以，所以f f还是变换还是变换。20电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程设设A A，B B为为有限集合有限集合，f f是从是从A A到到B B的函数，则：的函数，则：f f是单射的必要条件为是单射的必要条件为|A|B|A|B|；f f是满射的必要条件为是满射的必要条件为|B|A|B|A|；f f是双射的必要条件为是双射的必要条件为|A|A|B|B|。结论结论 A B考虑：一个考虑：一个n n元集合到元集合到m m元集合之间存在多元集合之间存在多少不同的函数，存在多少不同的单射、满少不同的函数，存在多少不同的单射、满射和双射？射和双射

15、？21电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程定理定理8.2.18.2.1设设A A，B B是有限集合，且是有限集合，且|A|=|B|A|=|B|，f f是是A A到到B B的函数，的函数，则则f f是单射当且仅当是单射当且仅当f f是满射。是满射。证明必要性证明必要性()：设设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)=B

16、f(A)=B，故，故f f是是A A到到B B的满射。的满射。22电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程定理定理8.2.18.2.1（续）（续）充分性充分性()：设设f f是满射。是满射。任取任取x x1 1,x,x2 2AA，x x1 1xx2 2，假设，假设f(xf(x1 1)=f)=f(x(x2 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|矛盾。因此矛盾。因此

17、f(xf(x1 1)f(x)f(x2 2)，故，故f f是是A A到到B B的单射。的单射。23电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程24电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例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

18、 2是满射函数。但是，是满射函数。但是，X X中元素中元素0 0和和1 1有相同的象有相同的象1 1，所以，所以f f2 2不是单射函数不是单射函数；25电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.5 8.2.5 解解（3 3）由已知得，）由已知得，显然显然，f f是双射函数。是双射函数。26电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.68.2.6设设A=B=R(A=B=R(实数集实数集)。试判断下列函数的类型。试判断下列函数的类型。（1 1）f f1 1=x,x=|xR|xR；（2 2）f f2 2=|x

19、R=|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是单射函数。是单射函数。27电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程28电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程设设是偏序集，是偏序集，对任意对任意aA,aA,令：令：f(a)f(a)x|(xA)(xa)x|(xA)(xa)证明：证明：证明：证明：f f是一个从是一个从A A到到P P(A)A)的一个的一个单射函数单射函数，并且，并且f f保

20、持保持 A,与与P(的的偏序关系偏序关系，即：对任意，即：对任意a,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)的映射的映射。29电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2)2)f f是是单单射射。对任意对任意a,bAa,bA，abab若若a,ba,b存在偏序关系，存在偏序关系

21、，不妨设不妨设abab(或或ba)ba)，由于由于“”“”是是反对称的，所以反对称的，所以ba(ba(或或ab)ab)，从而，从而b b f(a)f(a)x|(xA)xax|(xA)xa（或（或a a f(b)f(b)，而而“”“”是自反的，所以是自反的，所以bb(bb(或或aa),aa),即即bf(b)bf(b)(或或af(a),af(a),所以所以f(a)f(b)f(a)f(b)。例例8.2.88.2.8(续续)30电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程31电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程设设A1,2,3,n

22、，f是是A到到A的满射的满射，并且具有性，并且具有性质：质：f(xi)yi，i1,2,3,k，kn，xi,yiA。求。求f的个数。的个数。例例8.2.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,k;C1,2,3,k;CA-yA-yi i|i|i1,2

23、,3,k1,2,3,k则从则从B B到到C C的满射个数的满射个数(即是双射个数即是双射个数)就是就是f f的个数。的个数。根据推理根据推理2.3.12.3.1有，有，从从A A到到A A的满足题目条件的不同的满足题目条件的不同满射个数共有满射个数共有(n-k)!(n-k)!。32电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.2.38.2.3常用函数常用函数定义定义定义定义8.2.38.2.38.2.38.2.3（1 1）如果）如果A=BA=B，且对，且对 xAxA，都有，都有f(x)=xf(x)=x，则称，则称f f为为A A上的上的恒等函数恒等函数,记为记

24、为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 的一个子集，则子的一个子集，则子集集A A的的特征函数特征函数定义为从定义为从U U到到0,10,1的一个函数，且的一个函数，且33电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程定义定义8.2.38.2.3（续）（续）（4 4）对有理数）对有理数x x，f(x)f(x)为大于等于为大于等于x x的最小的整数，的最小的整数，则称则称f(x)f(

25、x)为为上取整函数上取整函数(强取整函数强取整函数)，记为，记为f(x)=f(x)=；（5 5）对有理数）对有理数x x，f(x)f(x)为小于等于为小于等于x x的最大的整数，的最大的整数，则称则称f(x)f(x)为为下取整函数下取整函数(弱取整函数弱取整函数)，记为，记为f(x)=f(x)=；（6 6）如果）如果f(x)f(x)是集合是集合A A到集合到集合B=0,1B=0,1上的函数，上的函数，则称则称f(x)f(x)为为布尔函数布尔函数。34电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.108.2.10设设A=B=R(A=B=R(实数集实数集)

26、。试指出下列函数的类型。试指出下列函数的类型。（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是下取整函数。是下取整函数。35电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.2.58.2.5函数的应用函数的应用解解解解 P(An)到到Bn可以按照如下的方式建立关系：对任意可以按

27、照如下的方式建立关系：对任意SP(An)P(An)，令，令f(S)b1b2b3bn，其中：其中：例例例例8.2.11 8.2.11 8.2.11 8.2.11 设设Ana1,a2,a3,an是是n个元素的有限集，个元素的有限集，Bnb1 b2b3bn|bi0,1，试建立试建立P(An)到到Bn的的一个双射。一个双射。36电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程（2 2）证明）证明f f是双射。是双射。1)1)证证f f是映射。是映射。显然，显然，f f是是P(AP(An n)到到B Bn n的映射。的映射。2)2)证证f f是单射是单射。任取任取S S1 1

28、,S,S2 2P(AP(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 S S1 1。从而从而f(Sf(S1 1)b b1 1b b2 2b b3 3bbn n中必有中必有b bj j1 1，f(Sf(S2 2)c c1 1c c2 2c c3 3ccn n必有必有c cj j0 0或或f(Sf(S1 1)b b1 1b b2 2b b3 3bbn n中必有中必有b bj j0 0，f(Sf(S2 2)c c1 1c c2 2c c3 3ccn n必有

29、必有c cj j1 1。所以。所以f(Sf(S1 1)f(S)f(S2 2)，即，即f f是单射是单射。例例8.2.118.2.11(续续)37电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.118.2.11(续续)3)3)证证f f是满射是满射。任取二进制数。任取二进制数b b1 1b b2 2b b3 3bbn nBBn n，对，对每一个二进制数每一个二进制数b b1 1b b2 2b b3 3bbn n，建立对应的集合，建立对应的集合S S A An n，S Saai i|若若b bi i1(1(即若即若b bi i1,1,令令a ai iSS，否

30、，否则则a ai i S)S)，则，则SP(ASP(An n)，从而，从而f(S)f(S)b b1 1b b2 2b b3 3bbn n，故故f f是满射。是满射。由由1)1)、2)2)和和3)3)知，知，f f是双射。是双射。例如例如A A3 3=a=a1 1,a,a2 2,a,a3 3，则有：，则有：000,a000,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。38电子科技大学离散数学课程

31、组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.12 8.2.12 HashHash函数函数 假设在计算机内存中有编号从假设在计算机内存中有编号从0 0到到1010的存储单元，的存储单元，见图见图8.2.28.2.2。图。图8.2.28.2.2表示了在初始时刻全为空的单表示了在初始时刻全为空的单元中，按次序元中，按次序1515、558558、3232、132132、102102和和5 5存入后的存入后的情形。现希望能在这些存储单元中存储任意的非负情形。现希望能在这些存储单元中存储任意的非负整数并能进行检索，整数并能进行检索，试用试用HashHash函数方法完成函数方法完成257

32、257的的存储和存储和558558的检索的检索。132 0 1 2 3 4 5 6 7 8 9 10 0 图图8.2.21021552595583239电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程解解因为因为h(259)=259 mod11=6h(259)=259 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)，但，但xyx

33、y，便，便称称冲突发生冲突发生了。为了解决冲突，需要了。为了解决冲突，需要冲突消解策略冲突消解策略。40电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.2.138.2.13存在计算机磁盘上的数据或数据网络上传输的数存在计算机磁盘上的数据或数据网络上传输的数据通常表示为字节串。据通常表示为字节串。每个字节由每个字节由8 8个字组成个字组成，要表示要表示100100字位的数据需要多少字节。字位的数据需要多少字节。解解 因为因为s=s=，所以表示，所以表示100100字位的数据字位的数据需要需要1313字节。字节。41电子科技大学离散数学课程组电子科技大学离散数学

34、课程组国家精品课程国家精品课程例例8.2.148.2.14在异步传输模式在异步传输模式(ATM)(ATM)下，下，数据按数据按5353字节分组，字节分组，每组称为一个信元。每组称为一个信元。以速率每秒以速率每秒500500千字位传输千字位传输数据的连接上一分钟能传输多少个数据的连接上一分钟能传输多少个ATMATM信元。信元。解因为一分钟能够传输的字节数为解因为一分钟能够传输的字节数为 =3750000=3750000，所以一分钟能传输的信元数为，所以一分钟能传输的信元数为 。42电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.38.3函数的运算函数的运算8.3.

35、18.3.1函数的复合运算函数的复合运算定义定义定义定义8.3.1 8.3.1 8.3.1 8.3.1 考虑考虑f f：ABAB，g g：BCBC是两个函数，是两个函数，则则f f与与g g的复合运算的复合运算f f g g|xAzC|xAzC(y)y)(yBxfyygz)(yBxfyygz)是从是从A A到到C C的函数，记为的函数，记为f f g g：ACAC ，称为函数，称为函数f f与与g g的复合的复合函数。函数。43电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程注意注意（1 1）函数）函数f f和和g g可以复合可以复合ranf=domgranf=do

36、mg；（2 2）dom(fog)=domf,ran(fog)=rangdom(fog)=domf,ran(fog)=rang；（3 3）对任意）对任意xAxA，有，有fog(x)=g(f(x)fog(x)=g(f(x)。44电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.3.18.3.1设设A=1,2,3,4,5,B=a,b,c,d,C=1,2,3,4,5,A=1,2,3,4,5,B=a,b,c,d,C=1,2,3,4,5,函数函数f:ABf:AB，g:BCg:BC定义如下：定义如下：f=,f=,；g=,g=,。求求fogfog。解解解解 fog=,fog=

37、,45电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.3.28.3.2设设f:RR,g:RR,h:RRf:RR,g:RR,h:RR，满足，满足f(x)=2x,f(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 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)

38、f(g(x)f(x+1)f(x+1)2 2)2(x+1)2(x+1)2 2；46电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程（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)=(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

39、）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 （续）（续）函数的复合不满足交换律，但满足结合律。函数的复合不满足交换律，但满足结合律。函数的复合不满足交换律，但满足结合律。函数的复合不满足交换律，但满足结合律。47电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程设设f f和和g g分别是分别是A A到到B B和从和从B B到到C C的函数，则：的函数，则：如如f,gf,g是满射，则是满射，则f f g g也是从也是从A A到到C

40、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(a)g(a)g(f(a)g(f(a)g(b)g(b)c c。即即存在存在aAaA，使得：，使得：f f g(

41、a)g(a)c c，所以，所以f f g g是满射是满射。48电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2)2)对任意对任意a a1 1,a,a2 2AA，a a1 1aa2 2，由于由于f f是单射，所以是单射，所以f f(a(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)g(b(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

42、 g g是单射。是单射。3)3)是是1)1)、2)2)的直接结果的直接结果。定理定理8.3.18.3.1(续续)49电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程定理定理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

43、的双射，则的双射，则g g是从是从B B到到C C的满射，的满射，f f是从是从A A到到B B的单射。的单射。50电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.3.28.3.2函数的逆运算函数的逆运算定义定义8.3.28.3.2设设f:ABf:AB的函数。如果的函数。如果f f-1-1|x|xA Ay yBBff是从是从B B到到A A的函数，则称的函数，则称f f-1-1：B BAA的的逆函数。逆函数。由定义由定义8.3.28.3.2可以看出，可以看出，一个函数的逆运算也是函一个函数的逆运算也是函数。即逆函数数。即逆函数f f-1-1存在当且仅当存在当且仅

44、当f f是双射。是双射。51电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.3.38.3.3试求出试求出下列函数的逆函数。下列函数的逆函数。（1 1）设）设A=1,2,3,B=1,2,3A=1,2,3,B=1,2,3。f f1 1:AB:AB定义为定义为 f f1 1=,=,；（2 2）f f2 2=,=,（3 3）f f3 3=|xR=|xR。52电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程解解(1)(1)因因f f1 1=,=,，所以，所以 f f1 1-1-1=,=,；(2)(2)因因f f2 2=,=,所所以以f f2

45、 2-1-1=,=,；（3 3）因为）因为f f3 3=|xR=|xR，所以，所以 f f3 3-1-1=|xR=|xR。53电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程定理定理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 IB Bf f。54电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程定理定理8.3.48.3.4若若f f是是A A到到B B的双射，则的双射，则f

46、 f的逆函数的逆函数f f-1-1也是也是B B到到A A的双射。的双射。证明证明证明证明（1 1）证明证明f f是满射。是满射。因为因为ranfranf-1-1=domf=A=domf=A，所以，所以f f-1-1是是B B到到A A的满射。的满射。（2 2）说明）说明f f是单射。是单射。对任意对任意b b1 1,b,b2 2BB，b b1 1bb2 2，假设，假设f f-1-1(b(b1 1)=f)=f-1-1(b(b2 2)，即，即存在存在aAaA，使得，使得bf-1,f-1,f,a f-1-1 ，即，即a,bf,f,ff，这与，这与f f是函数矛盾，因此是函数矛盾，因此f f-1 1

47、(b(b1 1)f)f-1-1(b(b2 2)，故，故f f-1-1是是B B到到A A的单射。的单射。综上，综上，f f-1-1是是B B到到A A的双射。的双射。55电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.3.48.3.4函数运算的应用函数运算的应用例例例例8.3.48.3.48.3.48.3.4 假设假设f f的定义如下表。的定义如下表。即即f(A)=D,f(B)=E,f(C)=S,f(A)=D,f(B)=E,f(C)=S,等等。等等。试找出给定密文试找出给定密文“QAIQORSFDOOBUIPQKJBYAQ”QAIQORSFDOOBUIPQKJB

48、YAQ”对应对应的明文。的明文。A AB BC CD DE EF FGGHHI IJ JKKL LMMD DE ES ST TI IN NY YA AB BC CF FGGHHN NOOP PQQR RS ST TU UV VWWX XY YZ ZJ JKKL LMMOOP PQQR RU UV VWWX XZ Z56电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程8.3.48.3.4函数运算的应用函数运算的应用解由表解由表8.3.18.3.1知，知，f f-1-1如如下表所示。如如下表所示。将密文将密文“QAIQORSFDOOBUIPQKJBYAQ”QAIQORS

49、FDOOBUIPQKJBYAQ”中的中的每一个字每一个字母在母在f f-1-1中找出其对应的象中找出其对应的象就可得出对应的明文：就可得出对应的明文：“THETRUCKARRIVESGONIGHT”THETRUCKARRIVESGONIGHT”。A AB BC CD DE EF FGGHHI IJ JKKL LMMHHI IJ JA AB BKKL LMME EN NOOP PQQN NOOP PQQR RS ST TU UV VWWX XY YZ ZF FR RS ST TU UC CD DV VWWX XY YGGZ Z57电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国

50、家精品课程例例8.3.58.3.5设按顺序排列的设按顺序排列的1313张红心纸牌，张红心纸牌，A2345678910JQKA2345678910JQK经过经过1 1次洗牌后牌的顺序变为次洗牌后牌的顺序变为38KA410QJ5762938KA410QJ57629再经两次同样方式的洗牌后牌的顺序是怎样的？再经两次同样方式的洗牌后牌的顺序是怎样的？58电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程例例8.3.5 8.3.5 解解对应结果见下表。对应结果见下表。A A A A2 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8