电子科技大学离散数学课程组国家精品课程

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

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

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

4、上，上，计算机的任何输出都可看成是某些输入的函计算机的任何输出都可看成是某些输入的函数。数。6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-228.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:A

5、Bf:AB。A A为函数为函数f f的的定义域定义域，记为，记为domf=Adomf=A；f(A)f(A)为函数为函数f f的的值域值域，记为，记为ranfranf。函数定义的示意图见图函数定义的示意图见图8.2.18.2.1。AxBf(x)图图8.2.17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22结论结论（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(

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

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

8、同的象有两个不同的象a a和和d d，与象，与象的唯一性矛盾，的唯一性矛盾，所以所以f f2 2不是函数；不是函数；（3 3）在）在f f3 3中，因为中，因为A A中每个元素都有唯一的象和它对中每个元素都有唯一的象和它对应，应，所以所以f f3 3是函数是函数。其值域是。其值域是A A中每个元素的象的集中每个元素的象的集合，即合，即ranfranf3 3=a,b,c,d=a,b,c,d；（4 4）在）在f f4 4中，因为元素中，因为元素1 1没有象，没有象，所以所以f f4 4不是函数。不是函数。10电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-

9、222022-2-22例例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是否为一函数。是否为一函数。11电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.2 8.2.2 解解显然，显然，f fp p

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

11、2,|B|=2|A|=2,|B|=2，所以，所以|A|AB|=|A|B|=|A|B|=4|B|=4，即即A AB=,B=,，,，此时从此时从A A到到B B的不同的关系有的不同的关系有2 24 4=16=16个。个。13电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.3 8.2.3 解（续）解（续）分别如下：分别如下：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=,R101

12、0=,=,R R1111=,R=,R1212=,=,R R1313=,R=,R1414=, =, R R1515=,=,。f f1 1=,f=,f2 2=,=,f f3 3=,f=,f4 4=,=,。14电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22函数是一种函数是一种特殊的关系特殊的关系，它与一般关系比较具备，它与一般关系比较具备如下如下差别：差别：函数与关系的差别函数与关系的差别1)1) 从从A A到到B B的不同的关系有的不同的关系有2 2|A|A| |B|B|个；但从个；但从A A到到B B的的不同的函数却仅有不同的函数

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

14、 设设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上的函数上的函数f f是双是双射时，称射时，称f f为一个为

15、一个变换变换。8.2.28.2.2函数的类型函数的类型16电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22将定义将定义8.2.28.2.2的描述数学化为的描述数学化为（1 1）f:ABf:AB是单射是单射当且仅当对当且仅当对x x1 1,x,x2 2AA，若若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既是单射

16、，又是满射；既是单射，又是满射；（4 4）f:ABf:AB是变换当且仅当是变换当且仅当f f是双射且是双射且A=BA=B。17电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例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,

17、3,B=1,2,3A=1,2,3,B=1,2,3。f:ABf:AB定义为定义为f=,f=,；18电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例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是双射函数是双射函数。又因为

18、。又因为A=BA=B，所以，所以f f还是变换还是变换。19电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22设设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 B20电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22定理定理8.2.

19、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)=Bf(A)=B，故，故f f是是A A到到B B的满射。的满射。21电子科技大学离散数学课

20、程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22定理定理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 2) )，由于，由于f f是是A A到到B B的满射，所以的满射，所以f f也是也是A-xA-x1 1 到到B B的满射，故的满射，故|A-x|A-x1 1|B|B|，即，即|A|-|A|-1|B|1|B|，这与，这与|A|=|B|A|=|B|矛盾。因此矛盾。因此f(xf(x1 1)f(x)f(x2

21、2) )，故故f f是是A A到到B B的单射。的单射。22电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例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)f(1)f1 1=,=, , , (2)f(2)f2 2=,=, , , ( (3)f3)f3 3=,=, ,n,1, 。试判断它们的类型。试判断它们的类型。23电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022

22、-2-22例例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 2不是单射函数不是单射函数；1f(n),n0,1,2,n21,0,1f(n)1,n2,3,n24电子科技大学离散数学课程

23、组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.5 8.2.5 解解（3 3）由已知得，）由已知得，显然显然，f f是双射函数。是双射函数。1f(n),n0,1,2,n125电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例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=|xR=|xR；（3 3）f f3 3=x,e=|xR|xR；（1 1）f

24、f1 1仅是一般函数；仅是一般函数；（2 2）f f2 2是双射函数；是双射函数；（3 3）f f3 3是单射函数。是单射函数。26电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22复习复习1 1、函数、函数( (f:AB)f:AB)的定义的定义 (1)f (1)f是集合是集合A A到到B B的关系，的关系， (2) (2)对对每个每个xAxA，都存在，都存在惟一惟一的的yByB，使得，使得ff。2 2、函数与关系的区别与联系、函数与关系的区别与联系3 3、函数、函数( (f:AB)f:AB)的类型的类型( (1)f1)f是单射是单

25、射对对x x1 1,x,x2 2AA，若若x x1 1xx2 2，则，则f(xf(x1 1)f(x)f(x2 2) )(2)(2)f f是满射是满射对对yByB，一定存在，一定存在xBxB，使得，使得f(x)=yf(x)=y；(3)(3)f f是双射是双射f f既是单射，又是满射；既是单射，又是满射；(4)f(4)f是变换是变换 f f是双射且是双射且A=BA=B。27电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22典型典型( (自然自然) )映射映射。设。设R R是集合是集合A A上的一个等价关系，上的一个等价关系，g g：AA

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

27、，对任意对任意aA,aA,令：令：f(a)f(a)x|(xA)(xa)x|(xA)(xa)（1 1）f f是一个从是一个从A A到到P P( (A)A)的一个的一个单射函数单射函数， （2 2）f f保持保持 A,与与P( 的的偏序关系偏序关系，即：，即：对任意对任意a,bAa,bA，若，若abab，则，则f(a)f(a) f(b)f(b)。例例8.2.8 8.2.8 29电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.8 8.2.8 证明证明1 1）f f是映射是映射。 任取任取aAaA，由于，由于f(a)f(a)x

28、|(xA)(xa)x|(xA)(xa) A A，所以所以f(a)f(a)P P(A)(A)，即即f f是从是从A A到到P(P(A)A)的映射的映射。30电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-222)2)f f是是单单射射。对任意对任意a,ba,bAA，abab若若a,ba,b存在偏序关系，存在偏序关系， 不妨设不妨设abab( (或或ba)ba)， 由于由于“”是反对称的，是反对称的， 所以所以ba(ba(或或ab)ab)，从而，从而b b f(a)f(a)x|(xA)xax|(xA)xa（或（或a a f(b)f(b)，

29、 而而“”是自反的，是自反的，所以所以bb(bb(或或aa),aa),即即bf(b)bf(b)( (或或af(a),af(a),例例8.2.8 8.2.8 证明证明( (续续) )所以所以f(a)f(b)f(a)f(b)。31电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22若若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.

30、2.8 8.2.8 证明证明( (续续) )32电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.88.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)。33电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22设设A1,2,3,n，f是是A

31、到到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,1,2,3,k;C,k;CA-yA-yi i|i|i1,2,3,1,2,3

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

33、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的一个函数，且的一个函数，且iAii1uAf (u )0uA35电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22（4 4）对有理数）对有理数x x，f(x)f(x)为大于等于为大于等于x x的最小的整数，的最小的整数，则称则称f

34、(x)f(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)为为布尔函数布尔函数。x x 36电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-

35、2-22例例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是下取整函数。是下取整函数。 x x 37电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2

36、-222022-2-228.2.5 8.2.5 函数的应用函数的应用 P(An)到到Bn可以按照如下的方式建立关系：可以按照如下的方式建立关系： 对任意对任意SPP(A(An) )，令，令 f(S)b1b2b3bn，其中：其中：.n, 2 , 1iSaSa, 0, 1biii ，当当，当当设设Ana1,a2,a3,an是是n个元素的有限集，个元素的有限集，Bnb1 b2b3bn|bi0,1，试建立试建立P(An)到到Bn的的一个双射。一个双射。38电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.118.2.11( (续

37、续) )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 S S1 1。从而从而f(Sf(S1 1) )b b1 1b b2 2b b3 3bbn n中必有中必有b bj j1 1， f(S f(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

38、bj j0 0， f(S f(S2 2) )c c1 1c c2 2c c3 3ccn n必有必有c cj j1 1。所以。所以f(Sf(S1 1)f(S)f(S2 2) )，即，即f f是单射是单射。（2 2）证明）证明f f是双射。是双射。 1)1)证证f f是映射。是映射。显然，显然，f f是是P(AP(An n) )到到B Bn n的映射。的映射。 39电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.118.2.11( (续续) )3)3)证证f f是满射是满射。 任取二进制数任取二进制数b b1 1b b2

39、2b bn nBBn n， 建立对应的集合建立对应的集合 S S A An n，S Saai i| |若若b bi i11 ( (即若即若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是双射。是双射。例如例如A A3 3=a=a1 1,a,a2 2,a,a3 3 ，则有：，则有： 000,a000,a1 1100,a100,a2 2010,010,aa3 3001,a001,a

40、1 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。40电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.2.128.2.12存在计算机磁盘上的数据或数据网络上传输的数存在计算机磁盘上的数据或数据网络上传输的数据通常表示为字节串。据通常表示为字节串。每个字节由每个字节由8 8个字组成个字组成，要表示要表示100100字位的数据需要多少字节。字位的数据需要多少字节。解解 因为因为s= s= ，所以表示，所以表示1

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

42、的信元数为所以一分钟能传输的信元数为3750000707545386050000042电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-228.3 8.3 函数的运算函数的运算8.3.18.3.1函数的复合运算函数的复合运算考虑考虑f f：ABAB，g g：BCBC是两个函数，是两个函数，则则f f与与g g的复合运算的复合运算f f g g|xAzC|xAzC( ( y)y)(yBxRyySz)(yBxRyySz)是从是从A A到到C C的函数，记为的函数，记为f f g g：ACAC ，称为函数，称为函数f f与与g g的复合的复合

43、函数。函数。43电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22注意注意（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)。44电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.3.18.3.1设设A=1,2,3,

44、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=,45电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例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

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

46、) 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）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电子科技大学离散数学课程组电子科技大学离散

47、数学课程组国家精品课程国家精品课程2022-2-222022-2-22设设f f和和g g分别是分别是A A到到B B和从和从B B到到C C的函数，则：的函数，则：如如f,gf,g是满射，则是满射，则f f g g也是从也是从A 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 48电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22证明：如证明：如

48、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(a)g(a)c c， 所以所以f f g g是满射是满射。49电子科技大学离散数学课程组电子科技大学离散数学课程组

49、国家精品课程国家精品课程2022-2-222022-2-22证明：证明：如如f,gf,g是单射，则是单射，则f f g g也是从也是从A A到到C C单射；单射； 2)2) 对任意对任意a a1 1,a,a2 2AA，a a1 1aa2 2， 由于由于f f是单射，所以是单射，所以 f(a f(a1 1)f(a)f(a2 2) )。令令b b1 1f(af(a1 1) )，b b2 2f(af(a2 2) )， 由于由于g g是单射是单射, ,所以所以 g(b g(b1 1)g(b)g(b2 2) )，即，即g(f(ag(f(a1 1)g(f(a)g(f(a2 2)。从而有从而有f f g(a

50、g(a1 1)f)f g(ag(a2 2) )，所以所以f f g g是单射。是单射。3)3)是是1)1)、2)2)的直接结果的直接结果。定理定理8.3.18.3.1( (续续) ) 50电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22定理定理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是从是从A A到到B B的的满射；满射；（2 2）如）如fogfog是从是从A A到到C C的的单

51、射单射，则，则f f是从是从B B到到C C的的单射单射；（3 3）如如fogfog是从是从A A到到C C的双射，则的双射，则g g是从是从A A到到B B的满射，的满射，f f是从是从B B到到C C的单射。的单射。51电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-228.3.2 8.3.2 函数的逆运算函数的逆运算定义定义8.3.28.3.2设设f:ABf:AB的函数。如果的函数。如果f f-1-1|x|xA Ay yBBf f 是从是从B B到到A A的函数的函数，则称，则称f f-1-1：B BAA的的逆函数。逆函数。由定

52、义由定义8.3.28.3.2可以看出，可以看出，一个函数的逆运算也是函一个函数的逆运算也是函数。即数。即逆函数逆函数f f-1-1存在当且仅当存在当且仅当f f是双射是双射。52电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例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。53电子科技大学离散数学课程

53、组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22例例8.3.3 8.3.3 解解(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。54电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22定理定理8.3.3 8.3.3 设设f f是是A A到到B B的双射函数，则：的双射函数，则：f f-1-1

54、 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。55电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22定理定理8.3.48.3.4若若f f是是A A到到B B的双射，则的双射，则f f的逆函数的逆函数f f-1-1也是也是B B到到A A的双射。的双射。（1 1）证明证明f f-1-1是满射。是满射。因为因为ranfranf-1-1=domf=A=domf=A，所以，所以f f-1-1是是B B到到A A的满射。的满射。56电子科技大学离散数学课程组

55、电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-22定理定理8.3.4 8.3.4 证明（续）证明（续）（2 2）f f-1-1是单射。是单射。对任意对任意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，使得，使得 b f,af-1-1,b, f,a f-1-1 ，即，即 a,b f,f,ff，这与这与f f是函数矛盾，是函数矛盾，因此因此f f-1-1(b(b1 1) f) f-1-1(b(b2 2) )，故故f f-1-1是是B B到到A A的

56、单射。的单射。综上，综上，f f-1-1是是B B到到A A的双射。的双射。57电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022-2-228.3.48.3.4函数运算的应用函数运算的应用 假设假设f f是的定义如下表。是的定义如下表。即即f(A)=D,f(B)=E,f(C)=S,f(A)=D,f(B)=E,f(C)=S,等等。等等。试找出给定密文试找出给定密文“QAIQORSFDOOBUIPQKJBYAQQAIQORSFDOOBUIPQKJBYAQ”对对应的明文。应的明文。58电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程

57、国家精品课程2022-2-222022-2-228.3.48.3.4函数运算的应用函数运算的应用解由表解由表8.3.18.3.1知，知，f f-1-1如如下表所示。如如下表所示。将密文将密文“QAIQORSFDOOBUIPQKJBYAQQAIQORSFDOOBUIPQKJBYAQ”中的中的每一个字每一个字母在母在f f-1-1中找出其对应的象中找出其对应的象就可得出对应的明文：就可得出对应的明文：“THETRUCKARRIVESGONIGHTTHETRUCKARRIVESGONIGHT”。59电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程2022-2-222022

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