离散数学离散第8章函数

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院示示 范范 性性 软软 件件 学学 院院20222022年年3 3月月7 7日星期一日星期一2电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7第三篇第三篇 二元关系二元关系第第8 8章章 函数函数3电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.0 8.0 内容提要内容提要集合的概念集合的概念1集合的表示方法集合

2、的表示方法2函数的复合运算函数的复合运算3函数的逆运算函数的逆运算4无限集合无限集合5函数的概念函数的概念1特殊函数特殊函数2函数的运算定理函数的运算定理54电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.1 8.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 函数的概念函数的概念2 2 单射、满射单射、满射和双射函数的和双射函数的概念概念3 3 函数的复合函数的复合运算和逆运算运算和逆运算31 1 置换的计算置换的计算21 1 单射、满射单射、满射和双射函数的和双射函数的证明证明2 2 置换的定义置

3、换的定义 5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.28.2函数函数函数也叫映射、变换或对应。函数也叫映射、变换或对应。函数是数学的一个基本概念。这里将高等数学中函数是数学的一个基本概念。这里将高等数学中连续函数的概念推广到对离散量的讨论，即将函连续函数的概念推广到对离散量的讨论，即将函数看作是一种特殊的二元关系。数看作是一种特殊的二元关系。函数的概念在日常生活和计算机科学中非常重要。函数的概念在日常生活和计算机科学中非常重要。如各种高级程序语言中使用了大量的函数。实际如各种高级程序语言中使用了大量的函数。实际上，计算机的

4、任何输出都可看成是某些输入的函上，计算机的任何输出都可看成是某些输入的函数。数。6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.2.18.2.1函数的定义函数的定义AxBf(x)图图8.2.17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7结论结论（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

5、)。如果关系如果关系f f具备下列两种情况之一，那么具备下列两种情况之一，那么f f就不就不是函数：是函数：（1 1）存在元素）存在元素aAaA，在，在B B中没有象；中没有象；（2 2）存在元素）存在元素aAaA，有两个及两个以上的象。，有两个及两个以上的象。8电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例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

6、1=,f1=,；（2 2）f2=,f2=,；（3 3）f3=,f3=,；（4 4）f4=,f4=,。9电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.1 8.2.1 解解（1 1）在）在f1f1中，因为中，因为A A中每个元素都有唯一的象和它中每个元素都有唯一的象和它对应，所以对应，所以f1f1是函数。其值域是是函数。其值域是A A中每个元素的象的中每个元素的象的集合，即集合，即ranf1=a,c,dranf1=a,c,d；（2 2）在）在f2f2中，因为元素中，因为元素2 2有两个不同的象有两个不同的象a a和和d d，

7、与，与象的唯一性矛盾，所以象的唯一性矛盾，所以f2f2不是函数；不是函数；（3 3）在）在f3f3中，因为中，因为A A中每个元素都有唯一的象和它中每个元素都有唯一的象和它对应，所以对应，所以f3f3是函数。其值域是是函数。其值域是A A中每个元素的象的中每个元素的象的集合，即集合，即ranf3=a,b,c,dranf3=a,b,c,d；（4 4）在）在f4f4中，因为元素中，因为元素1 1没有象，所以没有象，所以f4f4不是函数。不是函数。10电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.28.2.2设设P P是接受一

8、个整数作为输入并产生一个整数作为输是接受一个整数作为输入并产生一个整数作为输出的计算机程序。令出的计算机程序。令A=B=ZA=B=Z，则由，则由P P确定的关系确定的关系fpfp定定义如下：义如下：如果如果fpfp当且仅当输入当且仅当输入m m时，由程序时，由程序P P所产生的所产生的输出是输出是n n。请判断请判断fpfp是否为一函数。是否为一函数。11电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.2 8.2.2 解解显然，显然，fpfp是一个函数。因为，任意一个特殊的输入是一个函数。因为，任意一个特殊的输入对应唯一的

9、输出。对应唯一的输出。可用任意一个可能的输入集合可用任意一个可能的输入集合A A对应输出集合对应输出集合B B而推而推广到一般情形的程序。所以，通常把函数看做输入广到一般情形的程序。所以，通常把函数看做输入输出的关系。输出的关系。12电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.38.2.3设设A=a,b,B=1,2A=a,b,B=1,2，请分别写出，请分别写出A A到到B B的不同关系的不同关系和不同函数。和不同函数。解解 因为因为|A|=2,|B|=2|A|=2,|B|=2，所以，所以|A|AB|=|A|B|=|A|

10、B|=4|B|=4，即即A AB=,B=,，,，此时从，此时从A A到到B B的不同的关系有的不同的关系有24=1624=16个。个。13电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.3 8.2.3 解（续）解（续）分别如下：分别如下：R0=R0=；R1=,R2=,R3=, R1=,R2=,R3=, R4=,R5=,R6=, R4=,R5=,R6=, R7=,R8=,R7=,R8=,R9=,R10=,R9=,R10=,R11=,R12=,R11=,R12=,R13=,R14=, R13=,R14=, R15=,R15=,

11、。14电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7函数是一种特殊的关系，它与一般关系比较具备函数是一种特殊的关系，它与一般关系比较具备如下差别：如下差别：函数与关系的差别函数与关系的差别1)1) 从从A A到到B B的不同的关系有的不同的关系有2|A|2|A|B|B|个；但从个；但从A A到到B B的不同的函数却仅有的不同的函数却仅有|B|A|B|A|个。个。 ( (个数差别个数差别) )2)2) 关系的第一个元素可以相同；函数的第一元素关系的第一个元素可以相同；函数的第一元素一定是互不相同的。一定是互不相同的。3)3) ( (集

12、合元素的第一个元素存在差别集合元素的第一个元素存在差别) )4)4) 3) 3) 每一个函数的基数都为每一个函数的基数都为|A|A|个个(|f|=|A|)(|f|=|A|)，但关系的基数却为从零一直到但关系的基数却为从零一直到|A|A|B|B|。5)5) ( (集合基数的差集合基数的差别别) )15电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.2.28.2.2函数的类型函数的类型16电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7将定义将定义8.2.28.2.2的描述数

13、学化为的描述数学化为（1 1）f:ABf:AB是单射当且仅当对是单射当且仅当对x1,x2Ax1,x2A，若，若x1x2x1x2，则，则f(x1)f(x2)f(x1)f(x2)；（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。17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-7202

14、2-3-7例例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=,；（3 3）设）设A=1,2,3,B=1,2,3A=1,2,3,B=1,2,3。f:ABf:AB定义为定义为f=,f=,；18电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.4 8.2.

15、4 解解（1 1）因为对任意）因为对任意yByB，都存在，都存在xBxB，使得，使得ff，所以，所以f f是满射函数；是满射函数；（2 2）因为）因为A A中不同的元素对应不同的象，所以中不同的元素对应不同的象，所以f f是是单射函数；单射函数；（3 3）因为）因为f f既是单射函数，又是满射函数，所以既是单射函数，又是满射函数，所以f f是双射函数。又因为是双射函数。又因为A=BA=B，所以，所以f f还是变换。还是变换。19电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7设设A A，B B为有限集合，为有限集合，f f是从是从A

16、A到到B B的函数，则：的函数，则：f f是单射的必要条件为是单射的必要条件为|A|B|A|B|；f f是满射的必要条件为是满射的必要条件为|B|A|B|A|；f f是双射的必要条件为是双射的必要条件为|A|A|B|B|。结结论论 A B20电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7定理定理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是

17、单射。显然，是单射。显然，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的满射。的满射。21电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7定理定理8.2.18.2.1（续）（续）充分性充分性( () )：设设f f是满射。任取是满射。任取x1,x2Ax1,x2A，x1x2x1x2，假设，

18、假设f(x1)=f(x2)f(x1)=f(x2)，由于，由于f f是是A A到到B B的满射，所以的满射，所以f f也是也是A-x1A-x1到到B B的满射，故的满射，故|A-x1|B|A-x1|B|，即，即|A|-|A|-1|B|1|B|，这与，这与|A|=|B|A|=|B|矛盾。因此矛盾。因此f(x1)f(x2)f(x1)f(x2)，故故f f是是A A到到B B的单射。的单射。22电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.58.2.5设设X=0,1,2,X=0,1,2,，Y=1,1/2,1/3,Y=1,1/2,

19、1/3,，f:XYf:XY的定义如下：的定义如下：(1)f1=,(1)f1=,(2)f2=,(2)f2=,(3)f3=,(3)f3=,。试判断它们的类型。试判断它们的类型。23电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.5 8.2.5 解解（1 1）由已知得，）由已知得，根据函数根据函数f1(n)f1(n)的表达式和单射函数的定义知，的表达式和单射函数的定义知，f1f1是单射函数；但是，是单射函数；但是，Y Y中元素中元素1 1没有原象，所以没有原象，所以f1f1不不是满射函数；是满射函数；（2 2）由已知得，）由已知

20、得，显然显然f2f2是满射函数。但是，是满射函数。但是，X X中元素中元素0 0和和1 1有相同的有相同的象象1 1，所以，所以f2f2不是单射函数；不是单射函数；1f(n),n0,1,2,n21,0,1f(n)1,n2,3,n24电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.5 8.2.5 解解（3 3）由已知得，）由已知得，显然，显然，f f是双射函数。是双射函数。1f(n),n0,1,2,n125电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.

21、68.2.6设设A=B=R(A=B=R(实数集实数集) )。试判断下列函数的类型。试判断下列函数的类型。（1 1）f1=|xRf1=|xR；（2 2）f2=|xRf2=|xR；（3 3）f3=|xRf3=|xR；解（解（1 1）f1f1仅是一般函数；仅是一般函数；（2 2）f2f2是双射函数；是双射函数；（3 3）f3f3是单射函数。是单射函数。26电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7典型典型( (自然自然) )映射。设映射。设R R是集合是集合A A上的一个等价关系，上的一个等价关系，g g：AA/RAA/R称为称为A

22、A对商集对商集A/RA/R的典型的典型( (自然自然) )映射，映射，其定义为其定义为g(a)g(a)aRaR，aA.aA.证明：典型映射是一个满射。证明：典型映射是一个满射。例例8.2.78.2.7分析：由等价类的定义，对任意分析：由等价类的定义，对任意aRA/R,aaRaRA/R,aaR，即任意，即任意A/RA/R中的元素都有原中的元素都有原象，所以典型映射是满射。象，所以典型映射是满射。证明过程留给读者。证明过程留给读者。27电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7设设是偏序集，对任意是偏序集，对任意aA,aA,令：令：

23、f(a)f(a)x|(xA)(xa)x|(xA)(xa)证明：证明：f f是一个从是一个从A A到到P(A)P(A)的一个单射函数，并且的一个单射函数，并且f f保持保持与与P(A), 的偏序关系，即：对任意的偏序关系，即：对任意a,bAa,bA，若，若abab，则，则f(a)f(a)f(b)f(b)。例例8.2.8 8.2.8 28电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-72)f2)f是单射。对任意是单射。对任意a,bAa,bA，abab若若a,ba,b存在偏存在偏序关系，不妨设序关系，不妨设ab(ab(或或ba)ba)，由于

24、，由于“”“”是反是反对称的，所以对称的，所以ba(ba(或或ab)ab)，从而，从而b bf(a)f(a)x|(xA)xax|(xA)xa（或（或a af(b)f(b)， 而而“”“”是自反的，所以是自反的，所以bb(bb(或或aa),aa),即即bf(b)(bf(b)(或或af(a),af(a),所以所以f(a)f(b)f(a)f(b)。若若a,ba,b不存在偏序关系，则有：不存在偏序关系，则有：abab，从而，从而a af(b)f(b)x|(xA)xbx|(xA)xb，而而“”“”是自反的，所以是自反的，所以aaaa，即，即af(a)af(a)，即，即f(a)f(b)f(a)f(b)。例

25、例8.2.8(8.2.8(续续) )29电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.8(8.2.8(续续) )2) 2) 对任意对任意a,bAa,bA，若，若abab，则：，则：任取任取yf(a)yf(a)，则，则ya,ya,由由abab，根据根据“”“”的传递性，有的传递性，有ybyb，从而，从而yf(b)yf(b)，所以所以f(a)f(a)f(b)f(b)。30电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7设设A1,2,3,n，f是是A到到A的满射，并且

26、具有的满射，并且具有性质：性质：f(xi)yi，i1,2,3,k，kn，xi,yiA。求求f的个数。的个数。例例8.2.98.2.9B BA-xi|iA-xi|i1,2,3,k;C1,2,3,k;CA-yi|iA-yi|i1,2,3,k1,2,3,k则从则从B B到到C C的满射个数的满射个数( (即是双射个数即是双射个数) )就是就是f f的个数。的个数。根据推理根据推理2.3.12.3.1有，从有，从A A到到A A的满足题目条件的不同的满足题目条件的不同满射个数共有满射个数共有(n-k)!(n-k)!。31电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程202

27、2-3-72022-3-78.2.38.2.3常用函数常用函数iAii1uAf (u )0uA32电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7（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)为下取整函数为下取整函数( (弱取整函数

28、弱取整函数) )，记为，记为f(x)= f(x)= ；（6 6）如果）如果f(x)f(x)是集合是集合A A到集合到集合B=0,1B=0,1上的函数，上的函数，则称则称f(x)f(x)为布尔函数。为布尔函数。x x 33电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.108.2.10设设A=B=R(A=B=R(实数集实数集) )。试指出下列函数的类型。试指出下列函数的类型。（1 1）f1=|xRf1=|xR；（2 2）f2=|xR,aRf2=|xR,aR；（3 3）f3=|xRf3=|xR；（4 4）f4=|xRf4=|x

29、R。解（解（1 1）f1f1是恒等函数是恒等函数, ,（2 2）f2f2是常值函数是常值函数, ,（3 3）f3f3是上取整函数是上取整函数, ,（4 4）f4f4是下取整函数。是下取整函数。 x x 34电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.2.58.2.5函数的应用函数的应用.n, 2 , 1iSaSa, 0, 1biii ，当当，当当35电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7（2 2）证明）证明f f是双射。是双射。 1) 1)证证f f是映射。

30、显然，是映射。显然，f f是是P(An)P(An)到到BnBn的映射。的映射。 2) 2)证证f f是单射。任取是单射。任取S1,S2P(An)S1,S2P(An)，S1S2S1S2，则存在元素则存在元素aj(1jn),aj(1jn),使得使得ajS1,ajajS1,ajS2S2或或ajS2,ajajS2,ajS1S1。从而从而f(S1)f(S1)b1b2b3bnb1b2b3bn中必有中必有bjbj1 1，f(S2)f(S2)c1c2c3cnc1c2c3cn必有必有cjcj0 0或或f(S1)f(S1)b1b2b3bnb1b2b3bn中必有中必有bjbj0 0，f(S2)f(S2)c1c2c3

31、cnc1c2c3cn必有必有cjcj1 1。所以。所以f(S1)f(S2)f(S1)f(S2)，即，即f f是单射。是单射。例例8.2.11(8.2.11(续续) )36电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.11(8.2.11(续续) )3) 3) 证证f f是满射。任取二进制数是满射。任取二进制数b1b2b3bnBnb1b2b3bnBn，对每一个二进制数对每一个二进制数b1b2b3bnb1b2b3bn，建立对应的集合，建立对应的集合S SAnAn，S Sai|ai|若若bibi1(1(即若即若bibi1,1,令

32、令aiSaiS，否则否则aiaiS)S)，则，则SP(An)SP(An)，从而，从而f(S)f(S)b1b2b3bnb1b2b3bn，故，故f f是满射。是满射。由由1)1)、2)2)和和3)3)知，知，f f是双射。是双射。例如例如A3=a1,a2,a3A3=a1,a2,a3，则有：，则有： 000,a1110,a2010, 000,a1110,a2010,a3001,a1,a2110,a1,a3101,a3001,a1,a2110,a1,a3101,a2,a3011,a1,a2,a3111a2,a3011,a1,a2,a3111。37电子科技大学离散数学课程组电子科技大学离散数学课程组国家

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

34、257的的存储和存储和558558的检索。的检索。132 0 1 2 3 4 5 6 7 8 9 10 0 图图8.2.21021552595583238电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7解解因为因为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

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

36、要需要1313字节。字节。100/81340电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.2.148.2.14在异步传输模式在异步传输模式(ATM)(ATM)下，数据按下，数据按5353字节分组，字节分组，每组称为一个信元。以速率每秒每组称为一个信元。以速率每秒500500千字位传输千字位传输数据的连接上一分钟能传输多少个数据的连接上一分钟能传输多少个ATMATM信元。信元。解因为一分钟能够传输的字节数为解因为一分钟能够传输的字节数为 =3750000=3750000，所以一分钟能传输的信元数，所以一分钟能传输的信元数为为

37、。3750000707545350060841电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.38.3函数的运算函数的运算8.3.18.3.1函数的复合运算函数的复合运算定义定义8.3.1 8.3.1 考虑考虑f f：ABAB，g g：BCBC是两个函数，是两个函数，则则f f与与g g的复合运算的复合运算R RS S|xAzC|xAzC( (y)(yBxRyySz)y)(yBxRyySz)是从是从A A到到C C的函数，记为的函数，记为f fg g：AC AC ，称为函数，称为函数f f与与g g的复合函数。的复合函数。42电子

38、科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7注意注意（1 1）函数）函数f f和和g g可以复合可以复合ranf=domgranf=domg；（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)。43电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.3.18.3.1设设A=1,2,3,4,5,B=a,b,c,d,

39、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=,44电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.3.28.3.2设设f:RR,g:RR,h:RRf:RR,g:RR,h:RR，满足，满足f(x)=2x,g(x)f(x)=2x,g(x)(x+1)2,h(x)(x+1)2,h(x)x/2x/2。计算：。计算：（1 1）f fg g，g gf f；（

40、2 2）(f(fg)g)h h，f f(g(gh)h)；（3 3）f fh h，h hf f。45电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7（2 2）(f(fg)g)h)(x)h)(x)h(fh(fg)(x)g)(x)h(g(f(x)h(g(f(x) h(g(2x)h(g(2x)h(2x+1)2)h(2x+1)2)(2x+1)2/2(2x+1)2/2； (f (f(g(gh)(x)=(gh)(x)=(gh)(f(x)h)(f(x)h(g(f(x)h(g(f(x) h(g(2x)h(g(2x)h(2x+1)2)h(2x+1)2)(

41、2x+1)2/2 (2x+1)2/2 ；（3 3）f fh(x)h(x)h(f(x)h(f(x)h(2x)h(2x)x x； h hf(x)f(x)f(h(x)f(h(x)f(x/2)f(x/2)x x；例例8.3.2 8.3.2 （续）（续）46电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7设设f f和和g g分别是分别是A A到到B B和从和从B B到到C C的函数，则：的函数，则：如如f,gf,g是满射，则是满射，则f fg g也是从也是从A A到到C C满射；满射；如如f,gf,g是单射，则是单射，则f fg g也是从也是从

42、A A到到C C单射；单射；如如f,gf,g是双射，则是双射，则f fg g也是从也是从A A到到C C双射。双射。定理定理8.3.1 8.3.1 47电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-72) 2) 对任意对任意a1,a2Aa1,a2A，a1a2a1a2，由于，由于f f是单射，所是单射，所以以f(a1)f(a2)f(a1)f(a2)。令令b1b1f(a1)f(a1)，b2b2f(a2)f(a2)，由于，由于g g是单射是单射, ,所以所以g(b1)g(b2)g(b1)g(b2)，即，即g(f(a1)g(f(a2)g(f(

43、a1)g(f(a2)。从而有从而有f fg(a1)fg(a1)fg(a2)g(a2)，所以所以f fg g是单射。是单射。3)3)是是1)1)、2)2)的直接结果。的直接结果。定理定理8.3.1(8.3.1(续续) ) 48电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7定理定理8.3.28.3.2设设f f和和g g分别是从分别是从A A到到B B和从和从B B到到C C的函数，则的函数，则（1 1）如）如fogfog是从是从A A到到C C的满射，则的满射，则f f是从是从A A到到B B的满射；的满射；（2 2）如）如fogfo

44、g是从是从A A到到C C的单射，则的单射，则g g是从是从B B到到C C的单射；的单射；（3 3）如）如fogfog是从是从A A到到C C的双射，则的双射，则f f是从是从A A到到B B的满射，的满射，g g是从是从B B到到C C的单射。的单射。49电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.3.28.3.2函数的逆运算函数的逆运算定义定义8.3.28.3.2设设f:ABf:AB的函数。如果的函数。如果f-1f-1|xAyBf|xAyBf是从是从B B到到A A的函数，则称的函数，则称f-1f-1：BABA的逆函数。

45、的逆函数。由定义由定义8.3.28.3.2可以看出，一个函数的逆运算也是函可以看出，一个函数的逆运算也是函数。即逆函数数。即逆函数f-1f-1存在当且仅当存在当且仅当f f是双射。是双射。50电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.3.38.3.3试求出下列函数的逆函数。试求出下列函数的逆函数。（1 1）设）设A=1,2,3,B=1,2,3A=1,2,3,B=1,2,3。f1:ABf1:AB定义为定义为 f1=,f1=,；（2 2）f2=,f2=,（3 3）f3=|xRf3=|xR。51电子科技大学离散数学课程组电子科

46、技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7解解(1)(1)因因f1=,f1=,，所以，所以 f1-1=, f1-1=,；(2)(2)因因f2=,f2=,所以所以f2-1=,f2-1=,；（3 3）因为）因为f3=|xRf3=|xR，所以，所以 f3-1=|xR f3-1=|xR。52电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7定理定理8.3.3 8.3.3 设设f f是是A A到到B B的双射函数，则：的双射函数，则：f-1f-1f fIBIB|bB|bB；f ff-1f-1IAIA|aA|aA；

47、IAIAf ff fIBIBf f。53电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7定理定理8.3.48.3.4若若f f是是A A到到B B的双射，则的双射，则f f的逆函数的逆函数f-1f-1也是也是B B到到A A的双射。的双射。证明（证明（1 1）证明）证明f f是满射。是满射。因为因为ranf-1=domf=Aranf-1=domf=A，所以，所以f-1f-1是是B B到到A A的满射。的满射。（2 2）说明）说明f f是单射。是单射。对任意对任意b1,b2Bb1,b2B，b1b2b1b2，假设，假设f-1(b1)= f

48、-1(b2)f-1(b1)= f-1(b2)，即存在即存在aAaA，使得，使得f-1, f-1 f-1, f-1 ，即，即f,ff,f，这与，这与f f是函数矛盾，因此是函数矛盾，因此f-f-1(b1) f-1(b2)1(b1) f-1(b2)，故，故f-1f-1是是B B到到A A的单射。的单射。综上，综上，f-1f-1是是B B到到A A的双射。的双射。54电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.3.48.3.4函数运算的应用函数运算的应用55电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程

49、2022-3-72022-3-78.3.48.3.4函数运算的应用函数运算的应用解由表解由表8.3.18.3.1知，知，f-1f-1如如下表所示。如如下表所示。将密文将密文“QAIQORSFDOOBUIPQKJBYAQ”“QAIQORSFDOOBUIPQKJBYAQ”中的每一个字中的每一个字母在母在f-1f-1中找出其对应的象就可得出对应的明文：中找出其对应的象就可得出对应的明文：“THETRUCKARRIVESGONIGHT”“THETRUCKARRIVESGONIGHT”。56电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8

50、.3.58.3.5设按顺序排列的设按顺序排列的1313张红心纸牌，张红心纸牌，A2345678910JQKA2345678910JQK经过经过1 1次洗牌后牌的顺序变为次洗牌后牌的顺序变为38KA410QJ5762938KA410QJ57629再经两次同样方式的洗牌后牌的顺序是怎样的？再经两次同样方式的洗牌后牌的顺序是怎样的？57电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-7例例8.3.5 8.3.5 解解对应结果见下表。对应结果见下表。58电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-3-72022-3-78.48.4置换函数置换函数当当A A是有限集合时，这种情况具有特殊重要性。有是有限集合时，这种情况具有特殊重要性。有限集合上的双射函数在数学、计算机科学和物理学限集合上的双射函数在数学、计算机科学和物理学中有着非常广泛的应用。中有着非常广泛的应用。8.4.18.4.1基本概念基本概念定义定义8.4.1 8.4.1 设设A=a1,a2,anA=a1,a2,an是有限集合。从是有限集合。从A A到到A A的双射函数称为的双射函数称为A A上的置换或排列上的置换或排列(Permutation)(Permut