離散數(shù)學離散第8章函數(shù)

1、電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程離離 散散 數(shù)數(shù) 學學電子科技大學電子科技大學計算機科學與工程學院計算機科學與工程學院示示 范范 性性 軟軟 件件 學學 院院20222022年年3 3月月7 7日星期一日星期一2電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7第三篇第三篇 二元關系二元關系第第8 8章章 函數(shù)函數(shù)3電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.0 8.0 內(nèi)容提要內(nèi)容提要集合的概念集合的概念1集合的表示方法集合

2、的表示方法2函數(shù)的復合運算函數(shù)的復合運算3函數(shù)的逆運算函數(shù)的逆運算4無限集合無限集合5函數(shù)的概念函數(shù)的概念1特殊函數(shù)特殊函數(shù)2函數(shù)的運算定理函數(shù)的運算定理54電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.1 8.1 本章學習要求本章學習要求重點掌握重點掌握一般掌握一般掌握了解了解11 1 函數(shù)的概念函數(shù)的概念2 2 單射、滿射單射、滿射和雙射函數(shù)的和雙射函數(shù)的概念概念3 3 函數(shù)的復合函數(shù)的復合運算和逆運算運算和逆運算31 1 置換的計算置換的計算21 1 單射、滿射單射、滿射和雙射函數(shù)的和雙射函數(shù)的證明證明2 2 置換的定義置

3、換的定義 5電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.28.2函數(shù)函數(shù)函數(shù)也叫映射、變換或對應。函數(shù)也叫映射、變換或對應。函數(shù)是數(shù)學的一個基本概念。這里將高等數(shù)學中函數(shù)是數(shù)學的一個基本概念。這里將高等數(shù)學中連續(xù)函數(shù)的概念推廣到對離散量的討論，即將函連續(xù)函數(shù)的概念推廣到對離散量的討論，即將函數(shù)看作是一種特殊的二元關系。數(shù)看作是一種特殊的二元關系。函數(shù)的概念在日常生活和計算機科學中非常重要。函數(shù)的概念在日常生活和計算機科學中非常重要。如各種高級程序語言中使用了大量的函數(shù)。實際如各種高級程序語言中使用了大量的函數(shù)。實際上，計算機的

4、任何輸出都可看成是某些輸入的函上，計算機的任何輸出都可看成是某些輸入的函數(shù)。數(shù)。6電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.2.18.2.1函數(shù)的定義函數(shù)的定義AxBf(x)圖圖8.2.17電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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就不就不是函數(shù)：是函數(shù)：（1 1）存在元素）存在元素aAaA，在，在B B中沒有象；中沒有象；（2 2）存在元素）存在元素aAaA，有兩個及兩個以上的象。，有兩個及兩個以上的象。8電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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，試判斷下列關系哪，試判斷下列關系哪些是函數(shù)。如果是函數(shù)，請寫出它的值域。些是函數(shù)。如果是函數(shù)，請寫出它的值域。（1 1）f

6、1=,f1=,；（2 2）f2=,f2=,；（3 3）f3=,f3=,；（4 4）f4=,f4=,。9電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.1 8.2.1 解解（1 1）在）在f1f1中，因為中，因為A A中每個元素都有唯一的象和它中每個元素都有唯一的象和它對應，所以對應，所以f1f1是函數(shù)。其值域是是函數(shù)。其值域是A A中每個元素的象的中每個元素的象的集合，即集合，即ranf1=a,c,dranf1=a,c,d；（2 2）在）在f2f2中，因為元素中，因為元素2 2有兩個不同的象有兩個不同的象a a和和d d，

7、與，與象的唯一性矛盾，所以象的唯一性矛盾，所以f2f2不是函數(shù)；不是函數(shù)；（3 3）在）在f3f3中，因為中，因為A A中每個元素都有唯一的象和它中每個元素都有唯一的象和它對應，所以對應，所以f3f3是函數(shù)。其值域是是函數(shù)。其值域是A A中每個元素的象的中每個元素的象的集合，即集合，即ranf3=a,b,c,dranf3=a,b,c,d；（4 4）在）在f4f4中，因為元素中，因為元素1 1沒有象，所以沒有象，所以f4f4不是函數(shù)。不是函數(shù)。10電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.28.2.2設設P P是接受一

8、個整數(shù)作為輸入并產(chǎn)生一個整數(shù)作為輸是接受一個整數(shù)作為輸入并產(chǎn)生一個整數(shù)作為輸出的計算機程序。令出的計算機程序。令A=B=ZA=B=Z，則由，則由P P確定的關系確定的關系fpfp定定義如下：義如下：如果如果fpfp當且僅當輸入當且僅當輸入m m時，由程序時，由程序P P所產(chǎn)生的所產(chǎn)生的輸出是輸出是n n。請判斷請判斷fpfp是否為一函數(shù)。是否為一函數(shù)。11電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.2 8.2.2 解解顯然，顯然，fpfp是一個函數(shù)。因為，任意一個特殊的輸入是一個函數(shù)。因為，任意一個特殊的輸入對應唯一的

9、輸出。對應唯一的輸出?？捎萌我庖粋€可能的輸入集合可用任意一個可能的輸入集合A A對應輸出集合對應輸出集合B B而推而推廣到一般情形的程序。所以，通常把函數(shù)看做輸入廣到一般情形的程序。所以，通常把函數(shù)看做輸入輸出的關系。輸出的關系。12電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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的不同關系的不同關系和不同函數(shù)。和不同函數(shù)。解解 因為因為|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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.3 8.2.3 解（續(xù)）解（續(xù)）分別如下：分別如下：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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7函數(shù)是一種特殊的關系，它與一般關系比較具備函數(shù)是一種特殊的關系，它與一般關系比較具備如下差別：如下差別：函數(shù)與關系的差別函數(shù)與關系的差別1)1) 從從A A到到B B的不同的關系有的不同的關系有2|A|2|A|B|B|個；但從個；但從A A到到B B的不同的函數(shù)卻僅有的不同的函數(shù)卻僅有|B|A|B|A|個。個。 ( (個數(shù)差別個數(shù)差別) )2)2) 關系的第一個元素可以相同；函數(shù)的第一元素關系的第一個元素可以相同；函數(shù)的第一元素一定是互不相同的。一定是互不相同的。3)3) ( (集

12、合元素的第一個元素存在差別集合元素的第一個元素存在差別) )4)4) 3) 3) 每一個函數(shù)的基數(shù)都為每一個函數(shù)的基數(shù)都為|A|A|個個(|f|=|A|)(|f|=|A|)，但關系的基數(shù)卻為從零一直到但關系的基數(shù)卻為從零一直到|A|A|B|B|。5)5) ( (集合基數(shù)的差集合基數(shù)的差別別) )15電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.2.28.2.2函數(shù)的類型函數(shù)的類型16電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7將定義將定義8.2.28.2.2的描述數(shù)

13、學化為的描述數(shù)學化為（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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-7202

14、2-3-7例例8.2.48.2.4確定下列函數(shù)的類型。確定下列函數(shù)的類型。（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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.4 8.2.

15、4 解解（1 1）因為對任意）因為對任意yByB，都存在，都存在xBxB，使得，使得ff，所以，所以f f是滿射函數(shù)；是滿射函數(shù)；（2 2）因為）因為A A中不同的元素對應不同的象，所以中不同的元素對應不同的象，所以f f是是單射函數(shù)；單射函數(shù)；（3 3）因為）因為f f既是單射函數(shù)，又是滿射函數(shù)，所以既是單射函數(shù)，又是滿射函數(shù)，所以f f是雙射函數(shù)。又因為是雙射函數(shù)。又因為A=BA=B，所以，所以f f還是變換。還是變換。19電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7設設A A，B B為有限集合，為有限集合，f f是從是從A

16、A到到B B的函數(shù)，則：的函數(shù)，則：f f是單射的必要條件為是單射的必要條件為|A|B|A|B|；f f是滿射的必要條件為是滿射的必要條件為|B|A|B|A|；f f是雙射的必要條件為是雙射的必要條件為|A|A|B|B|。結結論論 A B20電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7定理定理8.2.18.2.1設設A A，B B是有限集合，且是有限集合，且|A|=|B|A|=|B|，f f是是A A到到B B的函數(shù)，的函數(shù)，則則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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7定理定理8.2.18.2.1（續(xù)）（續(xù)）充分性充分性( () )：設設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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.5 8.2.5 解解（1 1）由已知得，）由已知得，根據(jù)函數(shù)根據(jù)函數(shù)f1(n)f1(n)的表達式和單射函數(shù)的定義知，的表達式和單射函數(shù)的定義知，f1f1是單射函數(shù)；但是，是單射函數(shù)；但是，Y Y中元素中元素1 1沒有原象，所以沒有原象，所以f1f1不不是滿射函數(shù)；是滿射函數(shù)；（2 2）由已知得，）由已知

20、得，顯然顯然f2f2是滿射函數(shù)。但是，是滿射函數(shù)。但是，X X中元素中元素0 0和和1 1有相同的有相同的象象1 1，所以，所以f2f2不是單射函數(shù)；不是單射函數(shù)；1f(n),n0,1,2,n21,0,1f(n)1,n2,3,n24電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.5 8.2.5 解解（3 3）由已知得，）由已知得，顯然，顯然，f f是雙射函數(shù)。是雙射函數(shù)。1f(n),n0,1,2,n125電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.

21、68.2.6設設A=B=R(A=B=R(實數(shù)集實數(shù)集) )。試判斷下列函數(shù)的類型。試判斷下列函數(shù)的類型。（1 1）f1=|xRf1=|xR；（2 2）f2=|xRf2=|xR；（3 3）f3=|xRf3=|xR；解（解（1 1）f1f1僅是一般函數(shù)；僅是一般函數(shù)；（2 2）f2f2是雙射函數(shù)；是雙射函數(shù)；（3 3）f3f3是單射函數(shù)。是單射函數(shù)。26電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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)的一個單射函數(shù)，并且的一個單射函數(shù)，并且f f保持保持與與P(A), 的偏序關系，即：對任意的偏序關系，即：對任意a,bAa,bA，若，若abab，則，則f(a)f(a)f(b)f(b)。例例8.2.8 8.2.8 28電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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(續(xù)續(xù)) )29電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.8(8.2.8(續(xù)續(xù)) )2) 2) 對任意對任意a,bAa,bA，若，若abab，則：，則：任取任取yf(a)yf(a)，則，則ya,ya,由由abab，根據(jù)根據(jù)“”“”的傳遞性，有的傳遞性，有ybyb，從而，從而yf(b)yf(b)，所以所以f(a)f(a)f(b)f(b)。30電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7設設A1,2,3,n，f是是A到到A的滿射，并且

26、具有的滿射，并且具有性質(zhì)：性質(zhì)：f(xi)yi，i1,2,3,k，kn，xi,yiA。求求f的個數(shù)。的個數(shù)。例例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的滿射個數(shù)的滿射個數(shù)( (即是雙射個數(shù)即是雙射個數(shù)) )就是就是f f的個數(shù)。的個數(shù)。根據(jù)推理根據(jù)推理2.3.12.3.1有，從有，從A A到到A A的滿足題目條件的不同的滿足題目條件的不同滿射個數(shù)共有滿射個數(shù)共有(n-k)!(n-k)!。31電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程202

27、2-3-72022-3-78.2.38.2.3常用函數(shù)常用函數(shù)iAii1uAf (u )0uA32電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7（4 4）對有理數(shù)）對有理數(shù)x x，f(x)f(x)為小于等于為小于等于x x的最大的整數(shù)，的最大的整數(shù)，則稱則稱f(x)f(x)為上取整函數(shù)為上取整函數(shù)( (強取整函數(shù)強取整函數(shù)) )，記為，記為f(x)= f(x)= ；（5 5）對有理數(shù)）對有理數(shù)x x，f(x)f(x)為大于等于為大于等于x x的最小的整數(shù)，的最小的整數(shù)，則稱則稱f(x)f(x)為下取整函數(shù)為下取整函數(shù)( (弱取整函數(shù)

28、弱取整函數(shù)) )，記為，記為f(x)= f(x)= ；（6 6）如果）如果f(x)f(x)是集合是集合A A到集合到集合B=0,1B=0,1上的函數(shù)，上的函數(shù)，則稱則稱f(x)f(x)為布爾函數(shù)。為布爾函數(shù)。x x 33電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.108.2.10設設A=B=R(A=B=R(實數(shù)集實數(shù)集) )。試指出下列函數(shù)的類型。試指出下列函數(shù)的類型。（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是恒等函數(shù)是恒等函數(shù), ,（2 2）f2f2是常值函數(shù)是常值函數(shù), ,（3 3）f3f3是上取整函數(shù)是上取整函數(shù), ,（4 4）f4f4是下取整函數(shù)。是下取整函數(shù)。 x x 34電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.2.58.2.5函數(shù)的應用函數(shù)的應用.n, 2 , 1iSaSa, 0, 1biii ，當當，當當35電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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(續(xù)續(xù)) )36電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.11(8.2.11(續(xù)續(xù)) )3) 3) 證證f f是滿射。任取二進制數(shù)是滿射。任取二進制數(shù)b1b2b3bnBnb1b2b3bnBn，對每一個二進制數(shù)對每一個二進制數(shù)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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家

33、精品課程國家精品課程2022-3-72022-3-7例例8.2.12 Hash8.2.12 Hash函數(shù)函數(shù) 假設在計算機內(nèi)存中有編號從假設在計算機內(nèi)存中有編號從0 0到到1010的存儲單元，的存儲單元，見圖見圖8.2.28.2.2。圖。圖8.2.28.2.2表示了在初始時刻全為空的單表示了在初始時刻全為空的單元中，按次序元中，按次序1515、558558、3232、132132、102102和和5 5存入后的存入后的情形。現(xiàn)希望能在這些存儲單元中存儲任意的非負情形?，F(xiàn)希望能在這些存儲單元中存儲任意的非負整數(shù)并能進行檢索，試用整數(shù)并能進行檢索，試用HashHash函數(shù)方法完成函數(shù)方法完成257

34、257的的存儲和存儲和558558的檢索。的檢索。132 0 1 2 3 4 5 6 7 8 9 10 0 圖圖8.2.21021552595583238電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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函數(shù)函數(shù)H H，如果，如果H(x)=H(y

35、)H(x)=H(y)，但，但xyxy，便，便稱沖突發(fā)生了。為了解決沖突，需要沖突消解策略。稱沖突發(fā)生了。為了解決沖突，需要沖突消解策略。 39電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.138.2.13存在計算機磁盤上的數(shù)據(jù)或數(shù)據(jù)網(wǎng)絡上傳輸?shù)臄?shù)存在計算機磁盤上的數(shù)據(jù)或數(shù)據(jù)網(wǎng)絡上傳輸?shù)臄?shù)據(jù)通常表示為字節(jié)串。每個字節(jié)由據(jù)通常表示為字節(jié)串。每個字節(jié)由8 8個字組成，個字組成，要表示要表示100100字位的數(shù)據(jù)需要多少字節(jié)。字位的數(shù)據(jù)需要多少字節(jié)。解解 因為因為s= s= ，所以表示，所以表示100100字位的數(shù)據(jù)字位的數(shù)據(jù)需

36、要需要1313字節(jié)。字節(jié)。100/81340電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.2.148.2.14在異步傳輸模式在異步傳輸模式(ATM)(ATM)下，數(shù)據(jù)按下，數(shù)據(jù)按5353字節(jié)分組，字節(jié)分組，每組稱為一個信元。以速率每秒每組稱為一個信元。以速率每秒500500千字位傳輸千字位傳輸數(shù)據(jù)的連接上一分鐘能傳輸多少個數(shù)據(jù)的連接上一分鐘能傳輸多少個ATMATM信元。信元。解因為一分鐘能夠傳輸?shù)淖止?jié)數(shù)為解因為一分鐘能夠傳輸?shù)淖止?jié)數(shù)為 =3750000=3750000，所以一分鐘能傳輸?shù)男旁獢?shù)，所以一分鐘能傳輸?shù)男旁獢?shù)為為

37、。3750000707545350060841電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.38.3函數(shù)的運算函數(shù)的運算8.3.18.3.1函數(shù)的復合運算函數(shù)的復合運算定義定義8.3.1 8.3.1 考慮考慮f f：ABAB，g g：BCBC是兩個函數(shù)，是兩個函數(shù)，則則f f與與g g的復合運算的復合運算R RS S|xAzC|xAzC( (y)(yBxRyySz)y)(yBxRyySz)是從是從A A到到C C的函數(shù)，記為的函數(shù)，記為f fg g：AC AC ，稱為函數(shù)，稱為函數(shù)f f與與g g的復合函數(shù)。的復合函數(shù)。42電子

38、科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7注意注意（1 1）函數(shù)）函數(shù)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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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, 函數(shù)函數(shù)f:ABf:AB，g:BCg:BC定義如下：定義如下：f=,f=,；g=,g=,。求求fogfog。解解 fog=, fog=,44電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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 （續(xù)）（續(xù)）46電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7設設f f和和g g分別是分別是A A到到B B和從和從B B到到C C的函數(shù)，則：的函數(shù)，則：如如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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程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(續(xù)續(xù)) ) 48電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7定理定理8.3.28.3.2設設f f和和g g分別是從分別是從A A到到B B和從和從B B到到C C的函數(shù)，則的函數(shù)，則（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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.3.28.3.2函數(shù)的逆運算函數(shù)的逆運算定義定義8.3.28.3.2設設f:ABf:AB的函數(shù)。如果的函數(shù)。如果f-1f-1|xAyBf|xAyBf是從是從B B到到A A的函數(shù)，則稱的函數(shù)，則稱f-1f-1：BABA的逆函數(shù)。

45、的逆函數(shù)。由定義由定義8.3.28.3.2可以看出，一個函數(shù)的逆運算也是函可以看出，一個函數(shù)的逆運算也是函數(shù)。即逆函數(shù)數(shù)。即逆函數(shù)f-1f-1存在當且僅當存在當且僅當f f是雙射。是雙射。50電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.3.38.3.3試求出下列函數(shù)的逆函數(shù)。試求出下列函數(shù)的逆函數(shù)。（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電子科技大學離散數(shù)學課程組電子科

46、技大學離散數(shù)學課程組國家精品課程國家精品課程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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7定理定理8.3.3 8.3.3 設設f f是是A A到到B B的雙射函數(shù)，則：的雙射函數(shù)，則：f-1f-1f fIBIB|bB|bB；f ff-1f-1IAIA|aA|aA；

47、IAIAf ff fIBIBf f。53電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7定理定理8.3.48.3.4若若f f是是A A到到B B的雙射，則的雙射，則f f的逆函數(shù)的逆函數(shù)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是函數(shù)矛盾，因此是函數(shù)矛盾，因此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電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.3.48.3.4函數(shù)運算的應用函數(shù)運算的應用55電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程

49、2022-3-72022-3-78.3.48.3.4函數(shù)運算的應用函數(shù)運算的應用解由表解由表8.3.18.3.1知，知，f-1f-1如如下表所示。如如下表所示。將密文將密文“QAIQORSFDOOBUIPQKJBYAQ”“QAIQORSFDOOBUIPQKJBYAQ”中的每一個字中的每一個字母在母在f-1f-1中找出其對應的象就可得出對應的明文：中找出其對應的象就可得出對應的明文：“THETRUCKARRIVESGONIGHT”“THETRUCKARRIVESGONIGHT”。56電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8

50、.3.58.3.5設按順序排列的設按順序排列的1313張紅心紙牌，張紅心紙牌，A2345678910JQKA2345678910JQK經(jīng)過經(jīng)過1 1次洗牌后牌的順序變?yōu)榇蜗磁坪笈频捻樞蜃優(yōu)?8KA410QJ5762938KA410QJ57629再經(jīng)兩次同樣方式的洗牌后牌的順序是怎樣的？再經(jīng)兩次同樣方式的洗牌后牌的順序是怎樣的？57電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-7例例8.3.5 8.3.5 解解對應結果見下表。對應結果見下表。58電子科技大學離散數(shù)學課程組電子科技大學離散數(shù)學課程組國家精品課程國家精品課程2022-3-72022-3-78.48.4置換函數(shù)置換函數(shù)當當A A是有限集合時，這種情況具有特殊重要性。有是有限集合時，這種情況具有特殊重要性。有限集合上的雙射函數(shù)在數(shù)學、計算機科學和物理學限集合上的雙射函數(shù)在數(shù)學、計算機科學和物理學中有著非常廣泛的應用。中有著非常廣泛的應用。8.4.18.4.1基本概念基本概念定義定義8.4.1 8.4.1 設設A=a1,a2,anA=a1,a2,an是有限集合。從是有限集合。從A A到到A A的雙射函數(shù)稱為的雙射函數(shù)稱為A A上的置換或排列上的置換或排列(Permutation)(Permut