离散数学第8章函数

1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程离离 散散 数数 学学20222022年年4 4月月2727日星期三日星期三电子科技大学计算机科学与工程学院电子科技大学计算机科学与工程学院电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-2 22022-4-272022-4-27第第8 8章章 函数函数函数的复合运算函数的复合运算3函数的逆运算函数的逆运算4函数的概念函数的概念1特殊函数特殊函数2函数的运算定理函数的运算定理5内内容容提提要要电子科技大学离散数学课程组电子科技大

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

3、72022-4-278.2 8.2 函数函数 函数也叫函数也叫映射、变换或对应映射、变换或对应。 函数是数学的一个基本概念。这里将高等数学函数是数学的一个基本概念。这里将高等数学中连续函数的概念推广到对离散量的讨论，即将中连续函数的概念推广到对离散量的讨论，即将函函数看作是一种特殊的二元关系数看作是一种特殊的二元关系。 函数的概念在日常生活和计算机科学中非常重函数的概念在日常生活和计算机科学中非常重要要。如各种高级程序语言中使用了大量的函数。实。如各种高级程序语言中使用了大量的函数。实际上，际上，计算机的任何输出都可看成是某些输入的函计算机的任何输出都可看成是某些输入的函数。数。电子科技大学离

4、散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-5 52022-4-272022-4-278.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为函数为函数f f的的定义域定义域，记为，记

5、为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-4-272022-4-27结论结论如果关系如果关系f f是函数，那么是函数，那么1.1. f f y=f(x)y=f(

6、x)；2.2. f f f f y=zy=z；3.3. |f|=|A|f|=|A|；4.4. f(xf(x) )表示一个变值，表示一个变值，f f代表一个集合，因此代表一个集合，因此ff(xff(x) )。如果关系如果关系f f具备下列两种情况之一，那么具备下列两种情况之一，那么f f就不是函数：就不是函数：1.1. 存在元素存在元素aAaA，在，在B B中没有象；中没有象；2.2. 存在元素存在元素aAaA，有两个及两个以上的象。，有两个及两个以上的象。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-7 72022-4-272

7、022-4-27例例8.2.18.2.1设设A=1,2,3,4A=1,2,3,4，B=B=a,b,c,da,b,c,d ，试判断下列关系试判断下列关系哪些是函数。哪些是函数。如果是函数，请写出它的值域。如果是函数，请写出它的值域。（1 1）f f1 1=,=,；（2 2）f f2 2=,=,；（3 3）f f3 3=,=,；（4 4）f f4 4=,=,。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-8 82022-4-272022-4-27例例8.2.1 8.2.1 解解（1 1）在）在f f1 1中，因为中，因为A A中每

8、个元素都有唯一的象和它对中每个元素都有唯一的象和它对应，应，所以所以f f1 1是函数。是函数。其值域是其值域是A A中每个元素的象的集中每个元素的象的集合，即合，即ranfranf1 1=a,c,da,c,d ；（2 2）在）在f f2 2中，因为元素中，因为元素2 2有两个不同的象有两个不同的象a a和和d d，与象，与象的唯一性矛盾，的唯一性矛盾，所以所以f f2 2不是函数；不是函数；（3 3）在）在f f3 3中，因为中，因为A A中每个元素都有唯一的象和它对中每个元素都有唯一的象和它对应，应，所以所以f f3 3是函数是函数。其值域是。其值域是A A中每个元素的象的集中每个元素的象

9、的集合，即合，即ranfranf3 3=a,b,c,da,b,c,d ；（4 4）在）在f f4 4中，因为元素中，因为元素1 1没有象，没有象，所以所以f f4 4不是函数。不是函数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-9 92022-4-272022-4-27例例判断下图所示的几个关系是否是函数判断下图所示的几个关系是否是函数：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

10、 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 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出现出现在两个不同序偶的第一元素中。在两个不同序偶的第一元

11、素中。f f3 3是函数是函数f f4 4是函数。是函数。 f f5 5是函数是函数f f6 6是函数是函数电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-10102022-4-272022-4-27例例8.2.28.2.2设设P P是接受一个整数作为输入并产生一个整数作为是接受一个整数作为输入并产生一个整数作为输出的计算机程序。令输出的计算机程序。令A=B=ZA=B=Z，则由，则由P P确定的关系确定的关系f fp p定义如下：定义如下：如果如果 f fp p当且仅当输入当且仅当输入m m时，由程序时，由程序P P所产生所产生

12、的输出是的输出是n n。请判断请判断f fp p是否为函数。是否为函数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-11112022-4-272022-4-27例例8.2.2 8.2.2 解解显然，显然，f fp p是一个函数。因为，任意一个特殊的输入是一个函数。因为，任意一个特殊的输入对应唯一的输出。对应唯一的输出。可用任意一个可能的输入集合可用任意一个可能的输入集合A A对应输出集合对应输出集合B B而推而推广到一般情形的程序。所以，通常把广到一般情形的程序。所以，通常把函数看做输入函数看做输入输出的关系。输出的关系。电

13、子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-12122022-4-272022-4-27例例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 AB=,B=,，,，此时从此时从A A到到B B的不同的关系有的不同的关系有2 24 4=16=16个。个。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品

14、课程国家精品课程 双语示范课程双语示范课程67-67-13132022-4-272022-4-27A 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-14142022-

15、4-272022-4-27A A到到B B不同的函数不同的函数 f f1 1=, f=, f2 2=,=,， f f3 3=, f=, f4 4=,=,。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-15152022-4-272022-4-27函数与关系的差别函数与关系的差别函数是一种函数是一种特殊的关系特殊的关系，它与一般关系比较具备如，它与一般关系比较具备如下下差别：差别：1.1. 从从A A到到B B的不同的关系有的不同的关系有2 2|A|A| |B|B|个；但从个；但从A A到到B B的的不同的函数却仅有不同的函数却仅

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

17、62022-4-272022-4-27 设设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

18、是双射是双射时，称时，称f f为一个为一个变换变换。8.2.28.2.2函数的类型函数的类型电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-17172022-4-272022-4-27将定义将定义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，使得，

19、使得f(xf(x)=y)=y；3.3. f:ABf:AB是双射当且仅当是双射当且仅当f f既是单射，又是满射；既是单射，又是满射；4.4. f:ABf:AB是变换当且仅当是变换当且仅当f f是双射且是双射且A=BA=B。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-18182022-4-272022-4-27例例8.2.48.2.4确定下列函数的类型。确定下列函数的类型。1.1. 设设A=1,2,3,4,5A=1,2,3,4,5，B=B=a,b,c,da,b,c,d 。f:ABf:AB定义定义为：为：,；2.2. 设设A=1,

20、2,3A=1,2,3，B=B=a,b,c,da,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-19192022-4-272022-4-27例例8.2.4 8.2.4 解解1.1. 因为对任意因为对任意yByB，都存在，都存在xBxB，使得，使得 ff，所以所以f f是满射函数是满射函数；2.2. 因为因为A A中不同的元素对应不同的象，所以中不同的元素对

21、应不同的象，所以f f是单是单射函数；射函数；3.3. 因为因为f f既是单射函数，又是满射函数，所以既是单射函数，又是满射函数，所以f f是是双射函数双射函数。又因为。又因为A=BA=B，所以，所以f f还是变换还是变换。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-20202022-4-272022-4-27设设A A，B B为为有限集合有限集合，f f是从是从A A到到B B的函数，则：的函数，则：1.1. f f是单射的必要条件为是单射的必要条件为|A|B|A|B|；2.2. f f是满射的必要条件为是满射的必要条件为

22、|B|A|B|A|；3.3. f f是双射的必要条件为是双射的必要条件为|A|A|B|B|。结结论论A BA A1 12 23 34 45 56 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 6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-21212022-4-27

23、2022-4-27定理定理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(Af(A) )的满射，的满射，故故f f是是A A到到f(Af(A) )的双射，的双射，因此因此|A|=|A|=|f(Af(A)|)|。由由| |f(Af(A)|=|B|)|=|B|，且，且f(A)f(A) B B，得得f(Af(A)=B)=B，故故f f是是A A到到B B的满射

24、。的满射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-22222022-4-272022-4-27定理定理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|-1|B|A|-1|B|，这与这与|A|=|B|

25、A|=|B|矛盾。矛盾。因此因此f(xf(x1 1)f(x)f(x2 2) )，故故f f是是A A到到B B的单射。的单射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-23232022-4-272022-4-27例例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 2=,=, , , 3.3. f f3 3=,=, ,n,1, 。试判断它们的类型。试判断它们的类

26、型。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-24242022-4-272022-4-27例例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有相同的象有相同的象

27、1 1，所以，所以f f2 2不是单射函数不是单射函数；1 1f f( (n n) )= =, , n n = = 0 0, , 1 1, ,2 2, ,n n+ + 2 21,0, 11,0, 1f(n)=f(n)=1 1, n = 2,3, n = 2,3,n n电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-25252022-4-272022-4-27例例8.2.5 8.2.5 解解3.3. 由已知得，由已知得，显然显然，f f是双射函数。是双射函数。1 1f f( (n n) )= =, , n n = = 0 0, ,

28、 1 1, ,2 2, ,n n+ +1 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-26262022-4-272022-4-27例例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 f1 1仅是一般函数；仅是一般函数；（2 2）f f2 2是双射函数；是双射函数；（3 3）f f3 3是单射函数。是单射函数。电子科技

29、大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-27272022-4-272022-4-27典型典型( (自然自然) )映射映射。设。设R R是集合是集合A A上的一个等价关系，上的一个等价关系，g g：AA/RAA/R称为称为A A对商集对商集A/RA/R的的典型典型( (自然自然) )映射映射，其定义为其定义为g(ag(a) ) aaR R，a aA A. .证明：典型映射是一个满射。证明：典型映射是一个满射。例例8.2.78.2.7分析：由等价类的定义，对任意分析：由等价类的定义，对任意 aaR RAA/R/R，aaaaR R，即

30、，即任意任意A/RA/R中的元素都有原象，中的元素都有原象，所以典型所以典型映射是满射。映射是满射。证明过程留给读者。证明过程留给读者。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-28282022-4-272022-4-27设设是偏序集，是偏序集，对任意对任意aAaA，令：，令：f(a)f(a)x|(xA)(xa)x|(xA)(xa)f f是一个从是一个从A A到到P P( (A)A)的一个的一个单射函数单射函数，并且，并且f f保持保持 A,与与P( 的的偏序关系偏序关系，即：对任意，即：对任意a,bAa,bA，若，若ab

31、ab，则，则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-29292022-4-272022-4-272)2)f f是是单单射射。对任意对任意a,ba,bAA，abab若若a,ba,b存在偏序存在偏序关系，关系，不妨设不妨设abab( (或或

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

33、，即，即f(a)f(bf(a)f(b) )。例例8.2.88.2.8( (续续) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-30302022-4-272022-4-27例例8.2.88.2.8( (续续) )2) 2) 对任意对任意a,bAa,bA，若若abab，则：，则：任取任取yf(ayf(a) )，则，则yaya，由由abab，根据根据“”的传递性的传递性，有，有ybyb，从而，从而yf(byf(b) )，所以所以f(a)f(a) f(bf(b) )。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程

34、国家精品课程 双语示范课程双语示范课程67-67-31312022-4-272022-4-27设设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.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个元素的对应

35、个元素的对应所以只需考虑对剩下所以只需考虑对剩下n-kn-k个元素的对应，为此，令个元素的对应，为此，令B BA-A-x xi i|i|i1,2,3,1,2,3, ,k;Ck;CA-A-y yi i|i|i1,2,3,1,2,3,k,k则从则从B B到到C C的满射个数的满射个数( (即是双射个数即是双射个数) )就是就是f f的个数。的个数。根据推论根据推论2.3.12.3.1有，有，从从A A到到A A的满足题目条件的不同的满足题目条件的不同满射个数共有满射个数共有( (n-kn-k)!)!。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范

36、课程67-67-32322022-4-272022-4-278.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 的一个子集，则子的一个子集，则子集集A A的的特征函数特征函数定义为从定义为从U U到到0,10,1的一个函数，且的

37、一个函数，且i iAiAii i1uA1uAf(u )=f(u )=0uA0uA电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-33332022-4-272022-4-27（4 4）对有理数）对有理数x x，f(xf(x) )为大于等于为大于等于x x的最小的整数，的最小的整数，则称则称f(xf(x) )为为上取整函数上取整函数( (强取整函数强取整函数) )，记为，记为f(xf(x)= )= ；（5 5）对有理数）对有理数x x，f(xf(x) )为小于等于为小于等于x x的最大的整数，的最大的整数，则称则称f(xf(x) )

38、为为下取整函数下取整函数( (弱取整函数弱取整函数) )，记为，记为f(xf(x)= )= ；x x x x 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-34342022-4-272022-4-27例例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是恒等函数，是恒等

39、函数，（2 2）f f2 2是常值函数，是常值函数，（3 3）f f3 3是上取整函数，是上取整函数，（4 4）f f4 4是下取整函数。是下取整函数。 x x x x 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-35352022-4-272022-4-278.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

40、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 2b b3 3b bn n|b|bi i0,10,1，试建立试建立P P( (A An n) )到到B Bn n的一个双射。的一个双射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-36362022-4-272022-4-27（2 2）证明）证明f f是双射。是双射。 1)1

41、)证证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 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

42、 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-37372022-4-272022-4-27例例8.2.118.2.11( (续续) )3) 3) 证证f f是满射是满射。任取二进制数。任取二进制数

43、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 S a ai i| |若若b bi i1(1(即若即若b bi i1 1，令，令a ai iSS，否，否则则a ai i S S) )，则，则SPSP(A(An n) )，从而，从而f(Sf(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

44、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-38382022-4-272022-4-27例例8.2.12 8.2.12 假设在计算机内存中有编号从假设在计算机内存中有编号从0 0到到1010的存储单元，的存储单元，见图见图8

45、.2.28.2.2。图。图8.2.28.2.2表示了在初始时刻全为空的单表示了在初始时刻全为空的单元中，按次序元中，按次序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.210215525955832电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国

46、家精品课程 双语示范课程双语示范课程67-67-39392022-4-272022-4-27解解因为因为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(xH(x)=)=H(yH(y) )，但，但xyxy，便，便称称冲突发生冲突发生了。为了解决冲突，需要了。为了解决冲突，需要冲突消解策略冲突消解策略。 电子科技大学离散数学课程组电子科

47、技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-40402022-4-272022-4-27例例8.2.138.2.13存在计算机磁盘上的数据或数据网络上传输的数存在计算机磁盘上的数据或数据网络上传输的数据通常表示为字节串。据通常表示为字节串。每个字节由每个字节由8 8个字组成个字组成，要表示要表示100100字位的数据需要多少字节。字位的数据需要多少字节。解解 因为因为s= s= ，所以表示，所以表示100100字位的数据字位的数据需要需要1313字节。字节。100/813电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范

48、课程双语示范课程67-67-41412022-4-272022-4-27例例8.2.148.2.14在异步传输模式在异步传输模式(ATM)(ATM)下，下，数据按数据按5353字节分组，字节分组，每组称为一个信元。每组称为一个信元。以速率每秒以速率每秒500500千字位传输千字位传输数据的连接上一分钟能传输多少个数据的连接上一分钟能传输多少个ATMATM信元。信元。解 因 为 一 分 钟 能 够 传 输 的 字 节 数 为解 因 为 一 分 钟 能 够 传 输 的 字 节 数 为 = 3 7 5 0 0 0 0= 3 7 5 0 0 0 0 ， 所 以 一 分 钟 能 传 输 的 信 元 数，

49、 所 以 一 分 钟 能 传 输 的 信 元 数为为 。375000070754535 0 06 08电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-42422022-4-272022-4-278.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)(yBxRyySz)(yBxRyySz)是从是从A A到到C C的函数，记为的函数，记为f f g g：

50、ACAC ，称为函数，称为函数f f与与g g的的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-43432022-4-272022-4-27注意注意1.1. 函数函数f f和和g g可以复合可以复合 ranfranf= =domgdomg；2.2. dom(fogdom(fog)=)=domfdomf，ran(fogran(fog)=rang)=rang；3.3. 对任意对任意xAxA，有，有fog(xfog(x)=)=g(f(xg(f(x)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语

51、示范课程双语示范课程67-67-44442022-4-272022-4-27例例8.3.18.3.1设设A=1,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-45452022-4-272022-4-27例例8.3.28.3.2设设f:RRf:RR，g:RRg:RR，h:RRh:

52、RR，满足，满足f(xf(x)=2x)=2x，g(xg(x) )(x+1)(x+1)2 2，h(xh(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)f(g(x)f(x+1)f(x+1)2 2) )2(x+1)2(x+1)2 2；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程

53、 双语示范课程双语示范课程67-67-46462022-4-272022-4-27（2 2）(f f g)g) h)(xh)(x) )h(fh(f g)(xg)(x)h(g(f(xh(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)(xh)(x)=()=(g g h h)(f(x)(f(x)h(g(f(xh(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(xh(x) )h(f(xh(f(x

54、)h(2x)h(2x)x x； h h f(xf(x) )f(h(xf(h(x)f(x/2)f(x/2)x x；例例8.3.28.3.2 （续）（续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-47472022-4-272022-4-27设设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

55、是双射，则是双射，则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是满射是满射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精

56、品课程 双语示范课程双语示范课程67-67-48482022-4-272022-4-272)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是单射。是单射。3)

57、3) 是是1)1)、2)2)的直接结果的直接结果。定理定理8.3.18.3.1( (续续) ) 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-49492022-4-272022-4-27定理定理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. 如如

58、fogfog是是A A到到C C的双射，则的双射，则f f是是A A到到B B的单射，的单射，g g是是B B到到C C的满射。的满射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-50502022-4-272022-4-278.3.28.3.2函数的逆运算函数的逆运算定义定义8.3.2 8.3.2 设设f:ABf:AB的函数。如果的函数。如果f f-1-1|x xA Ay yBB f f 是从是从B B到到A A的函数，则称的函数，则称f f-1-1：B BAA的的逆函数。逆函数。由定义由定义8.3.28.3.2可以看出，可

59、以看出，一个函数的逆运算也是函一个函数的逆运算也是函数。即数。即逆函数逆函数f f-1-1存在当且仅当存在当且仅当f f是双射是双射。A A1 12 23 34 45 56 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 6电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67

60、-51512022-4-272022-4-27例例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=|=|xRxR 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-52522022-4-272022-4-27解解(1)(1)因因f f1 1=,=,，所以，所以 f f1 1-1-1=,=,；(2)(2)因因f f2 2=