《（本科）第8章 函数ppt课件.ppt》由会员分享，可在线阅读，更多相关《（本科）第8章 函数ppt课件.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程主讲人：（本科）第8章 函数ppt课件电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程离离 散散 数数 学学20222022年年5 5月月1616日星期一日星期一电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-3 32022-5-162022-5-16第第8 8章章 函数函数函数的复合运算函数的复合运算3函数的逆运算函数的逆运算4函数的概念函数的概念1特殊函数特殊函数2函数的运算定理函数的运算定理5内内容容提提要要电子科技大学离散数学课程组电子科
2、技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-4 42022-5-162022-5-168.1 8.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1 函数的概念函数的概念2 2 单射、满射单射、满射和双射函数的和双射函数的概念概念3 3 函数的复合函数的复合运算和逆运算运算和逆运算31 1 置换的计算置换的计算21 1 单射、满射单射、满射和双射函数的和双射函数的证明证明2 2 置换的定义置换的定义 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-5 52022-5
3、-162022-5-168.2 8.2 函数函数 函数也叫函数也叫映射、变换或对应映射、变换或对应。 函数是数学的一个基本概念。这里将高等数学函数是数学的一个基本概念。这里将高等数学中连续函数的概念推广到对离散量的讨论，即将中连续函数的概念推广到对离散量的讨论，即将函函数看作是一种特殊的二元关系数看作是一种特殊的二元关系。 函数的概念在日常生活和计算机科学中非常重函数的概念在日常生活和计算机科学中非常重要要。如各种高级程序语言中使用了大量的函数。实。如各种高级程序语言中使用了大量的函数。实际上，际上，计算机的任何输出都可看成是某些输入的函计算机的任何输出都可看成是某些输入的函数。数。电子科技大
4、学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-6 62022-5-162022-5-16函数的定义函数的定义设设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=Ado
5、mf=A； f(A) f(A)为函数为函数f f的的值域值域，记为，记为ranf=f(A)ranf=f(A)。 当当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-7 72022-5-162022-5-16结论结论如果关系如果关系f f是函数，那么是函数，那么 f f y=f(x)y=f(x)；
6、f f f f y=zy=z； |f|=|A|f|=|A|； f(x)f(x)表示一个变值，表示一个变值，f f代表一个集合，因此代表一个集合，因此ff(x)ff(x)。如果关系如果关系f f具备下列两种情况之一，那么具备下列两种情况之一，那么f f就不是函数：就不是函数： 存在元素存在元素aAaA，在，在B B中没有象；中没有象；1.1. 存在元素存在元素aAaA，有两个及两个以上的象。，有两个及两个以上的象。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-8 82022-5-162022-5-16例例试判断下列关系哪些是函数
7、。试判断下列关系哪些是函数。如果是函数，请写出如果是函数，请写出它的值域。它的值域。（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 Z电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-9 92022-5-162022-5-16例例8.2.1
8、 8.2.1 解解（1 1）在在f f1 1中中, ,因为元素因为元素1 1有两个元素有两个元素a,ba,b与它对应与它对应, ,所所以以f f1 1不是不是A 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中
9、中, ,因为每个元素都有惟一的象和它对应因为每个元素都有惟一的象和它对应, ,所以所以f f4 4是是A A到到B B函数函数, ,且且ranfranf4 42,3,4,2,3,4,。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-10102022-5-162022-5-16例例设设P P是接受一个整数作为输入并产生一个整数作为是接受一个整数作为输入并产生一个整数作为输出的计算机程序。令输出的计算机程序。令A=B=ZA=B=Z，则由，则由P P确定的关系确定的关系f fp p定义如下：定义如下：如果如果ffp p当且仅当输入当且
10、仅当输入m m时，由程序时，由程序P P所产生所产生的输出是的输出是n n。请判断请判断f fp p是否为函数。是否为函数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-11112022-5-162022-5-16例例8.2.2 8.2.2 解解显然，显然，f fp p是一个函数。因为，任意一个特殊的输入是一个函数。因为，任意一个特殊的输入对应唯一的输出。对应唯一的输出。可用任意一个可能的输入集合可用任意一个可能的输入集合A A对应输出集合对应输出集合B B而推而推广到一般情形的程序。所以，通常把广到一般情形的程序。所以，通常
11、把函数看做输入函数看做输入输出的关系。输出的关系。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-12122022-5-162022-5-16例例设设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个。个。电子科技大学离散数学课程组电
12、子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-13132022-5-162022-5-16A 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=,=,。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课
13、程67-67-14142022-5-162022-5-16A A到到B B不同的函数不同的函数 f f1 1=, f=, f2 2=,=,， f f3 3=, f=, f4 4=,=,。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-15152022-5-162022-5-16函数与关系的差别函数与关系的差别函数是一种函数是一种特殊的关系特殊的关系，它与一般关系比较具备如，它与一般关系比较具备如下下差别：差别： 从从A A到到B B的不同的关系有的不同的关系有2 2|A|A| |B|B|个；但从个；但从A A到到B B的的不同的
14、函数却仅有不同的函数却仅有|B|B|A|A|个。个。 ( (个数差别个数差别) ) 关系的第一个元素可以相同；函数的第一元素关系的第一个元素可以相同；函数的第一元素一定是互不相同的。一定是互不相同的。 ( (集合元素的第一个元素存在差别集合元素的第一个元素存在差别) ) 每一个函数的基数都为每一个函数的基数都为| |A|A|个个(|f|=|A|)(|f|=|A|)，但关，但关系的基数却为从零一直到系的基数却为从零一直到| |A|A|B|B|。 ( (集合基数的差别集合基数的差别) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67
15、-16162022-5-162022-5-16 设设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上的函数上的函
16、数f f是双射是双射时，称时，称f f为一个为一个变换变换。函数的类型函数的类型电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-17172022-5-162022-5-16将定义的描述数学化为将定义的描述数学化为 f:ABf:AB是单射是单射当且仅当对任意当且仅当对任意x x1 1,x,x2 2AA，若若x x1 1xx2 2，则，则f(xf(x1 1)f(x)f(x2 2) )； f:ABf:AB是满射当且仅当对任意是满射当且仅当对任意yByB，一定存在，一定存在xAxA，使得，使得f(x)=yf(x)=y； f:ABf:AB
17、是双射当且仅当是双射当且仅当f f既是单射，又是满射；既是单射，又是满射； f:ABf:AB是变换当且仅当是变换当且仅当f f是双射且是双射且A=BA=B。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-18182022-5-162022-5-16例例8.2.4 8.2.4 确定下列函数的类型确定下列函数的类型 设设A=1,2,3,4,5A=1,2,3,4,5，B=a,b,c,dB=a,b,c,d。f:ABf:AB定义定义为：为：,； 设设A=1,2,3A=1,2,3，B=a,b,c,dB=a,b,c,d。f:ABf:AB定义为
18、：定义为：f=,f=,； 设设A=1,2,3A=1,2,3，B=1,2,3B=1,2,3。f:ABf:AB定义为定义为f=,f=,；f f是满射函数是满射函数f f是双射函数且是变换是双射函数且是变换f f是单射函数是单射函数电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-19192022-5-162022-5-16设设A A，B B为为有限集合有限集合，f f是从是从A A到到B B的函数，则：的函数，则： f f是单射的必要条件为是单射的必要条件为|A|B|A|B|； f f是满射的必要条件为是满射的必要条件为|B|A|B|
19、A|；1.1. f f是双射的必要条件为是双射的必要条件为|A|A|B|B|。结论结论A B电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-20202022-5-162022-5-16定理定理设设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)的
20、双射，的双射，因此因此|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-5-162022-5-16定理（续）定理（续）充分性充分性( () )：设设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
21、 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-5-162022-5-16例例设设X=0,1,2,X=0,1,2, ，Y=1,1/2,1/3,Y=1,1/2,1/3, ，f:Xf:XY Y的定义如下：的定义
22、如下： f f1 1=,=, , , f f2 2=,=, , , f f3 3=,=, ,n,1, 。试判断它们的类型。试判断它们的类型。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-23232022-5-162022-5-16例例8.2.5 8.2.5 解解 由已知得，由已知得，根据函数根据函数f f1 1(n)(n)的表达式和单射函数的定义知，的表达式和单射函数的定义知，f f1 1是是单射函数；但是，单射函数；但是，Y Y中元素中元素1 1没有原象，没有原象，所以所以f f1 1不不是满射函数；是满射函数； 由已知得，
23、由已知得，显然显然f f2 2是满射函数。但是，是满射函数。但是，X X中元素中元素0 0和和1 1有相同的象有相同的象1 1，所以，所以f f2 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 n电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-24242022-5-162022-5-16例例8.2.5 8.2.5 解解 由已知得，由已知得，显然显然，f f是双射函
24、数。是双射函数。1 1f(n)=, n = 0, 1,2,f(n)=, n = 0, 1,2,n+1n+1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-25252022-5-162022-5-16例例设设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
25、 f3 3是单射函数。是单射函数。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-26262022-5-162022-5-16典型典型( (自然自然) )映射映射。设。设R R是集合是集合A A上的一个等价关系，上的一个等价关系，g g：AA/RAA/R称为称为A A对商集对商集A/RA/R的的典型典型( (自然自然) )映射映射，其定义为其定义为g(a)g(a)aaR R，a aA.A.证明：典型映射是一个满射。证明：典型映射是一个满射。例例分析：由等价类的定义，对任意分析：由等价类的定义，对任意aaR RA/RA/R，aaa
26、aR R，即，即任意任意A/RA/R中的元素都有原象，中的元素都有原象，所以典型所以典型映射是满射。映射是满射。证明过程留给读者。证明过程留给读者。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-27272022-5-162022-5-16设设是偏序集，是偏序集，对任意对任意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
27、，若，若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-5-162022-5-162)2)f f是是单单射射。对任意对任意a,bAa,bA，ab ab 若若a,ba,b存在偏序存在偏序关系，关系，不妨设不妨设a
28、bab( (或或baba) )，由于由于“”是是反对称反对称的，所以的，所以ba(ba(或或abab) )，从而，从而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)，即，
29、即f(a)f(b)f(a)f(b)。例例( (续续) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-29292022-5-162022-5-16例例( (续续) )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-3
30、0302022-5-162022-5-16设设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的个数。的个数。例例：f f是有限集是有限集A A到到A A的满射，由定理知的满射，由定理知f f是是A A到到A A的双的双射。射。由于由于f f已确定已确定A A中的某中的某k k个元素与另外个元素与另外k k个元素的对应个元素的对应所以只需考虑对剩下所以只需考虑对剩下n-kn-k个元素的对应，为此，令个元素的对
31、应，为此，令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的个数。的个数。根据推论有，根据推论有，从从A A到到A A的满足题目条件的不同满射个的满足题目条件的不同满射个数共有数共有(n-k)!(n-k)!。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-31312022-5-162022-5-16常用函数常用函数（1 1）如果如果A=BA=B，且对，且对任
32、意任意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的一个函数，且的一个函数，且i iAiAii i1uA1uAf(u )=f(u )=0uA0uA电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品
33、课程国家精品课程 双语示范课程双语示范课程67-67-32322022-5-162022-5-16（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)为为下取整函数下取整函数( (弱取整函数弱取整函数) )，记为，记为f(x)= f(x)= ；x x x x 电子科技大学离散数学课程组电子科技大学
34、离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-33332022-5-162022-5-16例例设设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 x x 电
35、子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-34342022-5-162022-5-16函数的应用函数的应用 P(AP(An n) )到到B Bn n可以按照如下的方式建立关系：对任意可以按照如下的方式建立关系：对任意SP(ASP(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个元
36、素的有限个元素的有限集，集，B Bn nbb1 1 b b2 2b b3 3b bn n|b|bi i0,10,1，试建立试建立P(P(A An n) )到到B Bn n的一个双射。的一个双射。例如例如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。电子科技大学离散数学课程组电子科技大学离
37、散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-35352022-5-162022-5-16（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 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 b
38、1 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(续续) )电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示
39、范课程67-67-36362022-5-162022-5-16例例( (续续) )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)，则，则SP(ASP(An n) )，从而，从而f(S)f(S)b b1 1b b2 2b b3 3b bn n，故，故f f是满
40、射。是满射。由由1)1)、2)2)和和3)3)知，知，f f是双射。是双射。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-37372022-5-162022-5-16例例8.2.12 8.2.12 假设在计算机内存中有编号从假设在计算机内存中有编号从0 0到到1010的存储单元，的存储单元，见图。图表示了在初始时刻全为空的单元中，按次见图。图表示了在初始时刻全为空的单元中，按次序序1515、558558、3232、132132、102102和和5 5存入后的情形。现希存入后的情形。现希望能在这些存储单元中存储任意的非负整数并能
41、进望能在这些存储单元中存储任意的非负整数并能进行检索，行检索，试用试用HashHash函数方法完成函数方法完成259259的存储和的存储和558558的的检索检索。132 0 1 2 3 4 5 6 7 8 9 10 0 图图8.2.210215555832电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-3838132 0 1 2 3 4 5 6 7 8 9 10 0 图图8.2.2102155558322022-5-162022-5-16解解因为因为h(259)=259 mod11=6h(259)=259 mod11=6，所以
42、，所以259259应该存放在位置应该存放在位置6 6；例如：例如： h(257)=4=h(15) h(257)=4=h(15) 259又因为又因为h(558)=8h(558)=8，所以检查位置，所以检查位置8 8，558558恰好在位置恰好在位置8 8。对于一个对于一个HashHash函数函数H H，如果，如果H(x)=H(y)H(x)=H(y)，但，但xyxy，便称，便称冲突发生了。为了解决冲突，需要冲突发生了。为了解决冲突，需要冲突消解策略冲突消解策略。 257电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-39392022
43、-5-162022-5-16例例存在计算机磁盘上的数据或数据网络上传输的数存在计算机磁盘上的数据或数据网络上传输的数据通常表示为字节串。据通常表示为字节串。每个字节由每个字节由8 8个字组成个字组成，要表示要表示100100字位的数据需要多少字节。字位的数据需要多少字节。解解 因为因为s= s= ，所以表示，所以表示100100字位的数据字位的数据需要需要1313字节。字节。100/813电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-40402022-5-162022-5-16例例在异步传输模式在异步传输模式(ATM)(ATM
44、)下，下，数据按数据按5353字节分组，字节分组，每组称为一个信元。每组称为一个信元。以速率每秒以速率每秒500500千字位传输千字位传输数据的连接上一分钟能传输多少个数据的连接上一分钟能传输多少个ATMATM信元。信元。解因为一分钟能够传输的字节数为解因为一分钟能够传输的字节数为 =3750000=3750000，所以一分钟能传输的信元数，所以一分钟能传输的信元数为为 。37500007075453500608电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-41412022-5-162022-5-168.38.3函数的运算函数
45、的运算函数的复合运算函数的复合运算考虑考虑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：ACAC ，称为函数，称为函数f f与与g g的的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-42422022-5-162022-5-16注意注意 函数函数f f和和g g可以复合可以复合 ranfranf domgdomg； dom
46、(fog)=domfdom(fog)=domf，ran(fog)ran(fog) rangrang； 对任意对任意xAxA，有，有fog(x)=g(f(x)fog(x)=g(f(x)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-43432022-5-162022-5-16例例设设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=
47、,fog=,电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-44442022-5-162022-5-16例例设设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 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+
48、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-5-162022-5-16（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
49、(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；例例 （续）（续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程67-67-46462022-5-162022-5-16设设f f和和g g分别是分别是A A到到B B和从和从B B到到C C的函数，则：的函数，则
50、：如如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 ：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