電子科技大學(xué)離散數(shù)學(xué)-函數(shù)課件

1、離 散 數(shù) 學(xué)25 七月 2022電子科技大學(xué)2022/7/25第8章 函數(shù)函數(shù)的復(fù)合運(yùn)算3函數(shù)的逆運(yùn)算4函數(shù)的概念1特殊函數(shù)2函數(shù)的運(yùn)算定理5內(nèi)容提要2022/7/258.1 本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11 函數(shù)的概念2 單射、滿射和雙射函數(shù)的概念3 函數(shù)的復(fù)合運(yùn)算和逆運(yùn)算31 置換的計算21 單射、滿射和雙射函數(shù)的證明2 置換的定義 2022/7/258.2 函數(shù) 函數(shù)也叫映射、變換或?qū)?yīng)。 函數(shù)是數(shù)學(xué)的一個基本概念。這里將高等數(shù)學(xué)中連續(xù)函數(shù)的概念推廣到對離散量的討論，即將函數(shù)看作是一種特殊的二元關(guān)系。 函數(shù)的概念在日常生活和計算機(jī)科學(xué)中非常重要。如各種高級程序語言中使用了大量的函數(shù)

2、。實際上，計算機(jī)的任何輸出都可看成是某些輸入的函數(shù)。2022/7/258.2.1函數(shù)的定義定義8.2.1 設(shè)f是集合A到B的關(guān)系，如果對每個xA，都存在惟一的yB，使得f，則稱關(guān)系f為A到B的函數(shù)(Function)(或映射(Mapping)、變換(Transform)，記為f:AB。 A為函數(shù)f的定義域，記為domf=A； f(A)為函數(shù)f的值域，記為ranf。 當(dāng)f時，通常記為y=f(x)，這時稱x為函數(shù)f的自變量，y為x在f下的函數(shù)值(或象)， 也稱x為y在f下的原象 。 2022/7/25結(jié)論如果關(guān)系f是函數(shù)，那么f y=f(x)；f f y=z；|f|=|A|；f(x)表示一個變值，

3、f代表一個集合，因此ff(x)。如果關(guān)系f具備下列兩種情況之一，那么f就不是函數(shù)：存在元素aA，在B中沒有象；存在元素aA，有兩個及兩個以上的象。2022/7/25例8.2.1設(shè)A=1,2,3,4，B=a,b,c,d，試判斷下列關(guān)系哪些是函數(shù)。如果是函數(shù)，請寫出它的值域。（1）f1,其中A1,2,3,Ba,b, c；（2）f2,其中Aa,b,c,Bb,c；（3）f3|yx1,x,yR,其中ABR（4）f4|yx1,x,yZ,其中ABZ2022/7/25例8.2.1 解（1）在f1中,因為元素1有兩個元素a,b與它對應(yīng),所以f1不是A到B函數(shù)；（2）在f2中,每個元素都有惟一的象和它對應(yīng),所以f

4、2是A到B函數(shù)。Ranf2b,c；（3）在f3中,因為每個元素都有惟一的象和它對應(yīng),所以f3是A到B函數(shù),且ranf3R；（4）在f4中,因為每個元素都有惟一的象和它對應(yīng),所以f4是A到B函數(shù),且ranf42,3,4,。2022/7/25例8.2.2設(shè)P是接受一個整數(shù)作為輸入并產(chǎn)生一個整數(shù)作為輸出的計算機(jī)程序。令A(yù)=B=Z，則由P確定的關(guān)系fp定義如下：如果fp當(dāng)且僅當(dāng)輸入m時，由程序P所產(chǎn)生的輸出是n。請判斷fp是否為函數(shù)。2022/7/25例8.2.2 解顯然，fp是一個函數(shù)。因為，任意一個特殊的輸入對應(yīng)唯一的輸出?？捎萌我庖粋€可能的輸入集合A對應(yīng)輸出集合B而推廣到一般情形的程序。所以，通

5、常把函數(shù)看做輸入輸出的關(guān)系。2022/7/25例8.2.3設(shè)A=a,b，B=1,2，請分別寫出A到B的不同關(guān)系和不同函數(shù)。解 因為|A|=2，|B|=2，所以|AB|=|A|B|=4，即AB=,，,，此時從A到B的不同的關(guān)系有24=16個。2022/7/25A到B不同的關(guān)系R0=；R1=；R2=；R3=；R4=；R5=,；R6=,；R7=,；R8=,；R9=,；R10=,；R11=,；R12=,；R13=,；R14=,；R15=,。2022/7/25A到B不同的函數(shù)從A到B的不同的函數(shù)僅有22=4個。分別如下： f1=, f2=,， f3=, f4=,。2022/7/25函數(shù)與關(guān)系的差別函數(shù)是

6、一種特殊的關(guān)系，它與一般關(guān)系比較具備如下差別：從A到B的不同的關(guān)系有2|A|B|個；但從A到B的不同的函數(shù)卻僅有|B|A|個。 (個數(shù)差別)關(guān)系的第一個元素可以相同；函數(shù)的第一元素一定是互不相同的。 (集合元素的第一個元素存在差別)每一個函數(shù)的基數(shù)都為|A|個(|f|=|A|)，但關(guān)系的基數(shù)卻為從零一直到|A|B|。 (集合基數(shù)的差別)2022/7/25定義8.2.2 設(shè)f是從A到B的函數(shù)，對任意x1,x2A，如果x1x2，有f(x1)f(x2)，則稱f為從A到B的單射（不同的x對應(yīng)不同的y)；如果ranfB，則稱f為從A到B的滿射；若f是滿射且是單射，則稱f為從A到B的雙射。若AB，則稱f為

7、A上的函數(shù)；當(dāng)A上的函數(shù)f是雙射時，稱f為一個變換。8.2.2函數(shù)的類型2022/7/25將定義8.2.2的描述數(shù)學(xué)化為f:AB是單射當(dāng)且僅當(dāng)對任意x1,x2A，若x1x2，則f(x1)f(x2)；f:AB是滿射當(dāng)且僅當(dāng)對任意yB，一定存在xB，使得f(x)=y；f:AB是雙射當(dāng)且僅當(dāng)f既是單射，又是滿射；f:AB是變換當(dāng)且僅當(dāng)f是雙射且A=B。2022/7/25例8.2.4確定下列函數(shù)的類型。設(shè)A=1,2,3,4,5，B=a,b,c,d。f:AB定義為：,；設(shè)A=1,2,3，B=a,b,c,d。f:AB定義為：f=,；設(shè)A=1,2,3，B=1,2,3。f:AB定義為f=,；2022/7/25

8、例8.2.4 解因為對任意yB，都存在xB，使得f，所以f是滿射函數(shù)；因為A中不同的元素對應(yīng)不同的象，所以f是單射函數(shù)；因為f既是單射函數(shù)，又是滿射函數(shù)，所以f是雙射函數(shù)。又因為A=B，所以f還是變換。2022/7/25設(shè)A，B為有限集合，f是從A到B的函數(shù)，則：f是單射的必要條件為|A|B|；f是滿射的必要條件為|B|A|；f是雙射的必要條件為|A|B|。結(jié)論A BA123456abcdeBf3A12345eabcdfBf4A123456abcdeBf5A12345abcdeBf62022/7/25定理8.2.1設(shè)A，B是有限集合，且|A|=|B|，f是A到B的函數(shù)，則f是單射當(dāng)且僅當(dāng)f是滿

9、射。證明 必要性()：設(shè)f是單射。顯然，f是A到f(A)的滿射，故f是A到f(A)的雙射，因此|A|=|f(A)|。由|f(A)|=|B|，且f(A)B，得f(A)=B，故f是A到B的滿射。2022/7/25定理8.2.1（續(xù)）充分性()：設(shè)f是滿射。任取x1,x2A，x1x2，假設(shè)f(x1)=f(x2)，由于f是A到B的滿射，所以f也是A-x1到B的滿射，故|A-x1|B|，即|A|-1|B|，這與|A|=|B|矛盾。因此f(x1)f(x2)，故f是A到B的單射。2022/7/25例8.2.5設(shè)X=0,1,2,，Y=1,1/2,1/3,，f:XY的定義如下：f1=,f2=,f3=,。試判斷它

10、們的類型。2022/7/25例8.2.5 解由已知得，根據(jù)函數(shù)f1(n)的表達(dá)式和單射函數(shù)的定義知，f1是單射函數(shù)；但是，Y中元素1沒有原象，所以f1不是滿射函數(shù)；由已知得，顯然f2是滿射函數(shù)。但是，X中元素0和1有相同的象1，所以f2不是單射函數(shù)；2022/7/25例8.2.5 解由已知得，顯然，f是雙射函數(shù)。2022/7/25例8.2.6設(shè)A=B=R(實數(shù)集)。試判斷下列函數(shù)的類型。（1）f1=|xR；（2）f2=|xR；（3）f3=|xR；解（1）f1僅是一般函數(shù)；（2）f2是雙射函數(shù)；（3）f3是單射函數(shù)。2022/7/25典型(自然)映射。設(shè)R是集合A上的一個等價關(guān)系，g：AA/R稱

11、為A對商集A/R的典型(自然)映射，其定義為g(a)aR，aA.證明：典型映射是一個滿射。例8.2.7分析：由等價類的定義，對任意aRA/R，aaR，即任意A/R中的元素都有原象，所以典型映射是滿射。證明過程留給讀者。2022/7/25設(shè)是偏序集，對任意aA，令：f(a)x|(xA)(xa)證明：f是一個從A到P(A)的一個單射函數(shù)，并且f保持與的偏序關(guān)系，即：對任意a,bA，若ab，則f(a)f(b)。例8.2.8 證明：1) f是映射。任取aA，由于f(a)x|(xA)(xa)A，所以f(a)P(A)，即f是從A到P(A)的映射。2022/7/252)f是單射。對任意a,bA，ab 若a,

12、b存在偏序關(guān)系，不妨設(shè)ab(或ba)，由于“”是反對稱的，所以ba(或ab)，從而bf(a)x|(xA)xa（或af(b)， 而“”是自反的，所以bb(或aa)，即bf(b)(或af(a)，所以f(a)f(b)。若a,b不存在偏序關(guān)系，則有：ab，從而af(b)x|(xA)xb，而“”是自反的，所以aa，即af(a)，即f(a)f(b)。例8.2.8(續(xù))2022/7/25例8.2.8(續(xù))2) 對任意a,bA，若ab，則：任取yf(a)，則ya，由ab，根據(jù)“”的傳遞性，有yb，從而yf(b)，所以f(a)f(b)。2022/7/25設(shè)A1,2,3,n，f是A到A的滿射，并且具有性質(zhì)：f(x

13、i)yi，i1,2,3,k，kn，xi,yiA。求f的個數(shù)。例8.2.9解：f是有限集A到A的滿射，由定理8.2.1知f是A到A的雙射。由于f已確定A中的某k個元素與另外k個元素的對應(yīng)所以只需考慮對剩下n-k個元素的對應(yīng)，為此，令BA-xi|i1,2,3,k;CA-yi|i1,2,3,k則從B到C的滿射個數(shù)(即是雙射個數(shù))就是f的個數(shù)。根據(jù)推論2.3.1有，從A到A的滿足題目條件的不同滿射個數(shù)共有(n-k)!。2022/7/258.2.3常用函數(shù)定義8.2.3（1）如果A=B，且對任意xA，都有f(x)=x，則稱f為A上的恒等函數(shù)，記為IA。（2）如果bB，且對任意xA，都有f(x)=b，則稱

14、f為常值函數(shù)。（3）設(shè)A是全集U=u1,u2,un的一個子集，則子集A的特征函數(shù)定義為從U到0,1的一個函數(shù)，且2022/7/25定義8.2.3（續(xù)）（4）對有理數(shù)x，f(x)為大于等于x的最小的整數(shù)，則稱f(x)為上取整函數(shù)(強(qiáng)取整函數(shù))，記為f(x)= ；（5）對有理數(shù)x，f(x)為小于等于x的最大的整數(shù)，則稱f(x)為下取整函數(shù)(弱取整函數(shù))，記為f(x)= ；2022/7/25例8.2.10設(shè)A=B=R(實數(shù)集)。試指出下列函數(shù)的類型。（1）f1=|xR；（2）f2=|xR,aR；（3）f3=|xR；（4）f4=|xR。解（1）f1是恒等函數(shù)，（2）f2是常值函數(shù)，（3）f3是上取整函

15、數(shù)，（4）f4是下取整函數(shù)。 2022/7/258.2.5函數(shù)的應(yīng)用解 P(An)到Bn可以按照如下的方式建立關(guān)系：對任意SP(An)，令f(S)b1b2b3bn，其中：例8.2.11 設(shè)Ana1,a2,a3,an是n個元素的有限集，Bnb1 b2b3bn|bi0,1，試建立P(An)到Bn的一個雙射。2022/7/25（2）證明f是雙射。 1)證f是映射。顯然，f是P(An)到Bn的映射。 2)證f是單射。任取S1,S2P(An)，S1S2，則存在元素aj(1jn)，使得ajS1，ajS2或ajS2，ajS1。從而f(S1)b1b2b3bn中必有bj1，f(S2)c1c2c3cn必有cj0或

16、f(S1)b1b2b3bn中必有bj0，f(S2)c1c2c3cn必有cj1。所以f(S1)f(S2)，即f是單射。例8.2.11(續(xù))2022/7/25例8.2.11(續(xù))3) 證f是滿射。任取二進(jìn)制數(shù)b1b2b3bnBn，對每一個二進(jìn)制數(shù)b1b2b3bn，建立對應(yīng)的集合SAn，Sai|若bi1(即若bi1，令aiS，否則aiS)，則SP(An)，從而f(S)b1b2b3bn，故f是滿射。由1)、2)和3)知，f是雙射。例如A3=a1,a2,a3，則有：000, a1110, a2010,a3001, a1,a2110, a1,a3101,a2,a3011, a1,a2,a3111。2022

17、/7/25例8.2.12 Hash函數(shù) 假設(shè)在計算機(jī)內(nèi)存中有編號從0到10的存儲單元，見圖8.2.2。圖8.2.2表示了在初始時刻全為空的單元中，按次序15、558、32、132、102和5存入后的情形?，F(xiàn)希望能在這些存儲單元中存儲任意的非負(fù)整數(shù)并能進(jìn)行檢索，試用Hash函數(shù)方法完成257的存儲和558的檢索。132 0 1 2 3 4 5 6 7 8 9 10 0 圖8.2.2102155259558322022/7/25解因為h(259)=259 mod11=6，所以257應(yīng)該存放在位置6；又因為h(558)=8，所以檢查位置8，558恰好在位置8。對于一個Hash函數(shù)H，如果H(x)=H

18、(y)，但xy，便稱沖突發(fā)生了。為了解決沖突，需要沖突消解策略。 2022/7/25例8.2.13存在計算機(jī)磁盤上的數(shù)據(jù)或數(shù)據(jù)網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)通常表示為字節(jié)串。每個字節(jié)由8個字組成，要表示100字位的數(shù)據(jù)需要多少字節(jié)。解 因為s= ，所以表示100字位的數(shù)據(jù)需要13字節(jié)。2022/7/25例8.2.14在異步傳輸模式(ATM)下，數(shù)據(jù)按53字節(jié)分組，每組稱為一個信元。以速率每秒500千字位傳輸數(shù)據(jù)的連接上一分鐘能傳輸多少個ATM信元。解因為一分鐘能夠傳輸?shù)淖止?jié)數(shù)為 =3750000，所以一分鐘能傳輸?shù)男旁獢?shù)為 。2022/7/258.3函數(shù)的運(yùn)算8.3.1函數(shù)的復(fù)合運(yùn)算定義8.3.1 考慮f：

19、AB，g：BC是兩個函數(shù)，則f與g的復(fù)合運(yùn)算RS|xAzC(y)(yBxRyySz)是從A到C的函數(shù)，記為fg：AC ，稱為函數(shù)f與g的復(fù)合函數(shù)。函數(shù)的復(fù)合，從本質(zhì)上講，就是關(guān)系的復(fù)合，滿足關(guān)系復(fù)合的性質(zhì)，不滿足交換律，但滿足結(jié)合律。2022/7/25注意函數(shù)f和g可以復(fù)合 ranfdomg；dom(fog)=domf，ran(fog)rang；對任意xA，有fog(x)=g(f(x)。2022/7/25例8.3.1設(shè)A=1,2,3,4,5，B=a,b,c,d，C=1,2,3,4,5， 函數(shù)f:AB，g:BC定義如下：f=,；g=,。求fog。解 fog=,2022/7/25例8.3.2設(shè)f:

20、RR，g:RR，h:RR，滿足f(x)=2x，g(x)(x+1)2，h(x)x/2。計算：（1）fg，gf；（2）(fg)h，f(gh)；（3）fh，hf。解（1）fg(x)g(f(x)g(2x)(2x+1)2； gf(x)f(g(x)f(x+1)2)2(x+1)2；2022/7/25（2）(fg)h)(x)h(fg)(x)h(g(f(x) h(g(2x)h(2x+1)2)(2x+1)2/2； (f(gh)(x)=(gh)(f(x)h(g(f(x) h(g(2x)h(2x+1)2)(2x+1)2/2 ；（3）fh(x)h(f(x)h(2x)x； hf(x)f(h(x)f(x/2)x；例8.3.

21、2 （續(xù)）2022/7/25設(shè)f和g分別是A到B和從B到C的函數(shù)，則：如f,g是滿射，則fg也是從A到C滿射；如f,g是單射，則fg也是從A到C單射；如f,g是雙射，則fg也是從A到C雙射。定理8.3.1 證明：1) 對任意cC，由于g是滿射，所以存在bB，使得g(b)c。對于bB，又因f是滿射，所以存在aA，使得f(a)b。從而有 fg(a)g(f(a)g(b)c。即存在aA，使得：fg(a)c，所以fg是滿射。2022/7/252) 對任意a1,a2A，a1a2，由于f是單射，所以f(a1)f(a2)。令b1f(a1)，b2f(a2)，由于g是單射，所以g(b1)g(b2)，即g(f(a1

22、)g(f(a2)。從而有fg(a1)fg(a2)，所以fg是單射。3) 是1)、2)的直接結(jié)果。定理8.3.1(續(xù)) 2022/7/25定理8.3.2設(shè)f和g分別是A到B和B到C的函數(shù)，則如fog是A到C的滿射，則g是B到C 的滿射；如fog是A到C的單射，則f是A到B的單射；如fog是A到C的雙射，則f是A到B的單射，g是B到C的滿射。2022/7/25證明 （1）對任意cC,由于fog是從A到C的滿射,所以存在aA,使得fog(a)c,即g(f(a)c。又因為f是從A到B的函數(shù),所以存在bB,使得f(a)b。即對任意cC,存在bB使得g(b)c。根據(jù)滿射的定義,g是從B到C的滿射。2022

23、/7/25（2）對任意a1,a2A,a1a2。由于fog是從A到C的單射,所以fog(a1)fog(a2),即g(f(a1)g(f(a2)。又因為g是從B到C的函數(shù),所以f(a1)f(a2),即f是從A到B的單射。（3）由(1)和(2)直接得到。2022/7/258.3.2函數(shù)的逆運(yùn)算定義8.3.2 設(shè)f:AB的函數(shù)。如果f-1|xAyBf是從B到A的函數(shù)，則稱f-1：BA的逆函數(shù)。由定義8.3.2可以看出，一個函數(shù)的逆運(yùn)算也是函數(shù)。即逆函數(shù)f-1存在當(dāng)且僅當(dāng)f是雙射。A123456abcdeBf3A12345eabcdfBf4A123456abcdeBf5A12345abcdeBf62022

24、/7/25例8.3.3試求出下列函數(shù)的逆函數(shù)。（1）設(shè)A=1,2,3，B=1,2,3。f1:AB定義為 f1=,；（2）f2=,（3）f3=|xR。2022/7/25解(1)因f1=,，所以 f1-1=,；(2)因f2=,，所以f2-1=,；（3）因為f3=|xR，所以 f3-1=|xR =|xR 。2022/7/25定理8.3.3 設(shè)f是A到B的雙射函數(shù)，則：f-1fIB|bB；ff-1IA|aA；IAffIBf。2022/7/25定理8.3.4若f是A到B的雙射，則f的逆函數(shù)f-1也是B到A的雙射。證明（1）證明f是滿射。因為ranf-1=domf=A，所以f-1是B到A的滿射。（2）說明

25、f是單射。對任意b1,b2B，b1b2，假設(shè)f-1(b1)= f-1(b2)，即存在aA，使得f-1， f-1 ，即f，f，這與f是函數(shù)矛盾，因此f-1(b1) f-1(b2)，故f-1是B到A的單射。綜上，f-1是B到A的雙射。2022/7/258.3.4函數(shù)運(yùn)算的應(yīng)用例8.3.4 假設(shè)f是的定義如下表。即f(A)=D，f(B)=E，f(C)=S，等等。試找出給定密文“QAIQORSFDOOBUIPQKJBYAQ”對應(yīng)的明文。ABCDEFGHIJKLMDESTINYABCFGHNOPQRSTUVWXYZJKLMOPQRUVWXZ2022/7/258.3.4函數(shù)運(yùn)算的應(yīng)用解 由上表知，f-1如下表所示。將密文“QAIQORSFDOOBUIPQKJBYAQ”中的每一個字母在f-1中找出其對應(yīng)的象就可得出對應(yīng)的明文：“THETRUCKARRIVESGONIGHT”。ABCDEFGHIJKLMHIJABKLMENOPQNOPQRSTUVWXYZFRSTUCDVWXYGZ2022/7/25例8.3.5設(shè)按順序排列的13張紅心紙牌，A2345678910JQK經(jīng)過1次洗牌后牌的順序變?yōu)?8KA410QJ57629再經(jīng)兩次同樣方式的洗牌后牌的順序是怎樣的？2022/7/25例8.