離散數學-第8章-函數

1、離 散 數 學,2024年3月19日星期二,電子科技大學計算機科學與工程學院,2024/3/19,第8章 函數,,2024/3/19,8.1 本章學習要求,,,2024/3/19,8.2 函數,函數也叫映射、變換或對應。 函數是數學的一個基本概念。這里將高等數學中連續(xù)函數的概念推廣到對離散量的討論，即將函數看作是一種特殊的二元關系。 函數的概念在日常生活和計算機科學中非常重要。如各種高級程序語言中使用了大量的函數。實際上

2、，計算機的任何輸出都可看成是某些輸入的函數。,2024/3/19,8.2.1函數的定義,定義8.2.1 設f是集合A到B的關系，如果對每個x∈A，都存在惟一的y∈B，使得∈f，則稱關系f為A到B的函數(Function)(或映射(Mapping)、變換(Transform))，記為f:A→B。 A為函數f的定義域，記為domf=A； f(A)為函數f的值域，記為ranf。 當∈f時，通常記為y=f(x)，這時稱x

3、為函數f的自變量，y為x在f下的函數值(或象)， 也稱x為y在f下的原象 。,2024/3/19,結論,如果關系f是函數，那么∈f ? y=f(x)；∈f ∧ ∈f ? y=z；|f|=|A|；f(x)表示一個變值，f代表一個集合，因此f≠f(x)。如果關系f具備下列兩種情況之一，那么f就不是函數：存在元素a∈A，在B中沒有象；存在元素a∈A，有兩個及兩個以上的象。,2024/3/19,例8.2.1,設A={1,2,3,4

4、}，B={a,b,c,d}，試判斷下列關系哪些是函數。如果是函數，請寫出它的值域。（1）f1={,,,}；（2）f2={,,,}；（3）f3={,,,}；（4）f4={,,}。,2024/3/19,例8.2.1 解,（1）在f1中，因為A中每個元素都有唯一的象和它對應，所以f1是函數。其值域是A中每個元素的象的集合，即ranf1={a,c,d}；（2）在f2中，因為元素2有兩個不同的象a和d，與象的唯一性矛盾，所以f2不是函數

5、；（3）在f3中，因為A中每個元素都有唯一的象和它對應，所以f3是函數。其值域是A中每個元素的象的集合，即ranf3={a,b,c,d}；（4）在f4中，因為元素1沒有象，所以f4不是函數。,2024/3/19,例,判斷下圖所示的幾個關系是否是函數：,f1不是函數。因f1中A的元素5沒出現在序偶的第一元素中,f2不是函數。f2中A的元素4出現在兩個不同序偶的第一元素中。,f3是函數,f4是函數。,f5是函數,f6是函數,2024/3

6、/19,例8.2.2,設P是接受一個整數作為輸入并產生一個整數作為輸出的計算機程序。令A=B=Z，則由P確定的關系fp定義如下：如果∈fp當且僅當輸入m時，由程序P所產生的輸出是n。請判斷fp是否為函數。,2024/3/19,例8.2.2 解,顯然，fp是一個函數。因為，任意一個特殊的輸入對應唯一的輸出?？捎萌我庖粋€可能的輸入集合A對應輸出集合B而推廣到一般情形的程序。所以，通常把函數看做輸入－輸出的關系。,2024/3/19,例

7、8.2.3,設A={a,b}，B={1,2}，請分別寫出A到B的不同關系和不同函數。解 因為|A|=2，|B|=2，所以|A×B|=|A|×|B|=4，即A×B={,，,}，此時從A到B的不同的關系有24=16個。,2024/3/19,A到B不同的關系,R0=Φ；R1={}；R2={}；R3={}；R4={}；R5={,}；R6={,}；R7={,}；R8={,}；R9={,}；R10={,}；R

8、11={,,}；R12={,,}；R13={,,}；R14={,,}；R15={,,,}。,2024/3/19,A到B不同的函數,從A到B的不同的函數僅有22=4個。分別如下： f1={,}, f2={,}， f3={,}, f4={,}。,2024/3/19,函數與關系的差別,函數是一種特殊的關系，它與一般關系比較具備如下差別：從A到B的不同的關系有2|A|?|B|個；但從A到B的不同的函數卻僅有|B||A|個。

9、 (個數差別)關系的第一個元素可以相同；函數的第一元素一定是互不相同的。 (集合元素的第一個元素存在差別)每一個函數的基數都為|A|個(|f|=|A|)，但關系的基數卻為從零一直到|A|×|B|。 (集合基數的差別),2024/3/19,定義8.2.2 設f是從A到B的函數，對任意x1,x2∈A，如果x1≠x2，有f(x1)≠f(x2)，則稱f為從

10、A到B的單射（不同的x對應不同的y)；如果ranf＝B，則稱f為從A到B的滿射；若f是滿射且是單射，則稱f為從A到B的雙射。若A＝B，則稱f為A上的函數；當A上的函數f是雙射時，稱f為一個變換。,8.2.2函數的類型,2024/3/19,將定義8.2.2的描述數學化為,f:A→B是單射當且僅當對任意x1,x2∈A，若x1≠x2，則f(x1)≠f(x2)；f:A→B是滿射當且僅當對任意y∈B，一定存在x∈B，使得f(x)=y；f

11、:A→B是雙射當且僅當f既是單射，又是滿射；f:A→B是變換當且僅當f是雙射且A=B。,2024/3/19,例8.2.4,確定下列函數的類型。設A={1,2,3,4,5}，B={a,b,c,d}。f:A→B定義為：{,,,,}；設A={1,2,3}，B={a,b,c,d}。f:A→B定義為：f={,,}；設A={1,2,3}，B={1,2,3}。f:A→B定義為f={,,}；,2024/3/19,例8.2.4 解,因為對任意y∈

12、B，都存在x∈B，使得∈f，所以f是滿射函數；因為A中不同的元素對應不同的象，所以f是單射函數；因為f既是單射函數，又是滿射函數，所以f是雙射函數。又因為A=B，所以f還是變換。,2024/3/19,設A，B為有限集合，f是從A到B的函數，則：f是單射的必要條件為|A|≤|B|；f是滿射的必要條件為|B|≤|A|；f是雙射的必要條件為|A|＝|B|。,結論,,,,,,,A B,,,,,,,,,,,,

13、2024/3/19,定理8.2.1,設A，B是有限集合，且|A|=|B|，f是A到B的函數，則f是單射當且僅當f是滿射。證明 必要性(?)：設f是單射。顯然，f是A到f(A)的滿射，故f是A到f(A)的雙射，因此|A|=|f(A)|。由|f(A)|=|B|，且f(A)?B，得f(A)=B，故f是A到B的滿射。,2024/3/19,定理8.2.1（續(xù)）,充分性(?)：設f是滿射。任取x1,x2∈A，x1≠x2

14、，假設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的單射。,2024/3/19,例8.2.5,設X={0,1,2,…}，Y={1,1/2,1/3,…}，f:X→Y的定義如下：f1={,,…,,…}f2={,,,…,,…}f3={,,…,,…}。試判斷它

15、們的類型。,2024/3/19,例8.2.5 解,由已知得，根據函數f1(n)的表達式和單射函數的定義知，f1是單射函數；但是，Y中元素1沒有原象，所以f1不是滿射函數；由已知得，顯然f2是滿射函數。但是，X中元素0和1有相同的象1，所以f2不是單射函數；,,,,2024/3/19,例8.2.5 解,由已知得，顯然，f是雙射函數。,,,,2024/3/19,例8.2.6,設A=B=R(實數集)。試判斷下列函數的類型。（1）

16、f1={|x∈R}；（2）f2={|x∈R}；（3）f3={|x∈R}；解（1）f1僅是一般函數；（2）f2是雙射函數；（3）f3是單射函數。,2024/3/19,典型(自然)映射。設R是集合A上的一個等價關系，g：A→A/R稱為A對商集A/R的典型(自然)映射，其定義為g(a)＝[a]R，a∈A.證明：典型映射是一個滿射。,例8.2.7,分析：由等價類的定義，對任意[a]R∈A/R，a∈[a]R，即任意A/R中的元素都有原

17、象，所以典型映射是滿射。證明過程留給讀者。,2024/3/19,設是偏序集，對任意a∈A，令：f(a)＝{x|(x∈A)∧(x≤a)}證明：f是一個從A到P(A)的一個單射函數，并且f保持與的偏序關系，即：對任意a,b∈A，若a≤b，則f(a)?f(b)。,例8.2.8,證明：1) f是映射。任取a∈A，由于f(a)＝{x|(x∈A)∧(x≤a)}?A，所以f(a)∈P(A)，即f是從A到P(A)的映射。,2024/3/19,

18、2)f是單射。對任意a,b∈A，a≠b若a,b存在偏序關系，不妨設a≤b(或b≤a)，由于“≤”是反對稱的，所以b≤a(或a≤b)，從而,b?f(a)＝{x|(x∈A)∧x≤a}（或a?f(b))， 而“≤”是自反的，所以b≤b(或a≤a)，即b∈f(b)(或a∈f(a))，所以f(a)≠f(b)。若a,b不存在偏序關系，則有：a≤b，從而a?f(b)＝{x|(x∈A)∧x≤b}，而“≤”是自反的，所以a≤a，即a∈f(a)，

19、即f(a)≠f(b)。,例8.2.8(續(xù)),,,,2024/3/19,例8.2.8(續(xù)),2) 對任意a,b∈A，若a≤b，則：任取y∈f(a)，則y≤a，由a≤b，根據“≤”的傳遞性，有y≤b，從而y∈f(b)，所以f(a)?f(b)。,2024/3/19,設A＝{1,2,3,…,n}，f是A到A的滿射，并且具有性質：f(xi)＝y(tǒng)i，i＝1,2,3,…,k，k≤n，xi,yi∈A。求f的個數。,例8.2.9,解：f是有限集

20、A到A的滿射，由定理8.2.1知f是A到A的雙射。由于f已確定A中的某k個元素與另外k個元素的對應所以只需考慮對剩下n-k個元素的對應，為此，令,B＝A-{xi|i＝1,2,3,…,k};C＝A-{yi|i＝1,2,3,…,k},則從B到C的滿射個數(即是雙射個數)就是f的個數。根據推論2.3.1有，從A到A的滿足題目條件的不同滿射個數共有(n-k)!。,2024/3/19,8.2.3常用函數,定義8.2.3（1）如果A=B，且對任

21、意x∈A，都有f(x)=x，則稱f為A上的恒等函數，記為IA。（2）如果?b∈B，且對任意x∈A，都有f(x)=b，則稱f為常值函數。（3）設A是全集U={u1,u2,…,un}的一個子集，則子集A的特征函數定義為從U到{0,1}的一個函數，且,,2024/3/19,定義8.2.3（續(xù)）,（4）對有理數x，f(x)為大于等于x的最小的整數，則稱f(x)為上取整函數(強取整函數)，記為f(x)= ；（5）對有理數x，f(x)為

22、小于等于x的最大的整數，則稱f(x)為下取整函數(弱取整函數)，記為f(x)= ；,,,,2024/3/19,例8.2.10,設A=B=R(實數集)。試指出下列函數的類型。（1）f1={|x∈R}；（2）f2={|x∈R,a∈R}；（3）f3={|x∈R}；（4）f4={|x∈R}。解（1）f1是恒等函數，（2）f2是常值函數，（3）f3是上取整函數，（4）f4是下取整函數。,2024/3/19,8.2.5函數的應

23、用,解 P(An)到Bn可以按照如下的方式建立關系：對任意S∈P(An)，令f(S)＝b1b2b3…bn，其中：,例8.2.11 設An＝{a1,a2,a3,…,an}是n個元素的有限集，Bn＝{b1 b2b3…bn|bi∈{0,1}}，試建立P(An)到Bn的一個雙射。,2024/3/19,（2）證明f是雙射。 1)證f是映射。顯然，f是P(An)到Bn的映射。 2)證f是單射。任取S1,S2∈P(An)，S1≠S2，則

24、存在元素aj(1≤j≤n)，使得aj∈S1，aj?S2或aj∈S2，aj?S1。從而f(S1)＝b1b2b3…bn中必有bj＝1，f(S2)＝c1c2c3…cn必有cj＝0或f(S1)＝b1b2b3…bn中必有bj＝0，f(S2)＝c1c2c3…cn必有cj＝1。所以f(S1)≠f(S2)，即f是單射。,例8.2.11(續(xù)),2024/3/19,例8.2.11(續(xù)),3) 證f是滿射。任取二進制數b1b2b3…bn∈Bn，對每一個二

25、進制數b1b2b3…bn，建立對應的集合S?An，S＝{ai|若bi＝1}(即若bi＝1，令ai∈S，否則ai?S)，則S∈P(An)，從而f(S)＝b1b2b3…bn，故f是滿射。由1)、2)和3)知，f是雙射。,例如A3={a1,a2,a3}，則有：Ф├→000, {a1}├→110, {a2}├→010,{a3}├→001, {a1,a2}├→110, {a1,a3}├→101,{a2,a3}├→

26、011, {a1,a2,a3}├→111。,2024/3/19,例8.2.12 Hash函數,假設在計算機內存中有編號從0到10的存儲單元，見圖8.2.2。圖8.2.2表示了在初始時刻全為空的單元中，按次序15、558、32、132、102和5存入后的情形?，F希望能在這些存儲單元中存儲任意的非負整數并能進行檢索，試用Hash函數方法完成257的存儲和558的檢索。,2024/3/19,解,因為h(259)=259 mod11=6，所以2

27、57應該存放在位置6；又因為h(558)=8，所以檢查位置8，558恰好在位置8。對于一個Hash函數H，如果H(x)=H(y)，但x≠y，便稱沖突發(fā)生了。為了解決沖突，需要沖突消解策略。,2024/3/19,例8.2.13,存在計算機磁盤上的數據或數據網絡上傳輸的數據通常表示為字節(jié)串。每個字節(jié)由8個字組成，要表示100字位的數據需要多少字節(jié)。解 因為s= ，所以表示100字位的數據需要13字節(jié)。,,,,2024/

28、3/19,例8.2.14,在異步傳輸模式(ATM)下，數據按53字節(jié)分組，每組稱為一個信元。以速率每秒500千字位傳輸數據的連接上一分鐘能傳輸多少個ATM信元。解因為一分鐘能夠傳輸的字節(jié)數為 =3750000，所以一分鐘能傳輸的信元數為 。,,,,2024/3/19,8.3函數的運算,8.3.1函數的復合運算定義8.3.1 考慮f：A→B，g：B→C是兩個函數，則f與g的復合運算R?S＝{|x

29、∈A∧z∈C∧(?y)(y∈B∧xRy∧ySz)}是從A到C的函數，記為f?g：A→C ，稱為函數f與g的復合函數。函數的復合，從本質上講，就是關系的復合，滿足關系復合的性質，不滿足交換律，但滿足結合律。,2024/3/19,注意,函數f和g可以復合 ? ranf=domg；dom(fog)=domf，ran(fog)=rang；對任意x∈A，有fog(x)=g(f(x))。,2024/3/19,例8.3.1,設A={1

30、,2,3,4,5}，B={a,b,c,d}，C={1,2,3,4,5}， 函數f:A→B，g:B→C定義如下：f={,,,,}；g={,,,}。求fog。解 fog={,,,,},2024/3/19,,例8.3.2,設f:R→R，g:R→R，h:R→R，滿足f(x)=2x，g(x)＝(x+1)2，h(x)＝x/2。計算：（1）f?g，g?f；（2）(f?g)?h，f?(g?h)；（3）f?h，h?f。,解（1）f?

31、g(x)＝g(f(x))＝g(2x)＝(2x+1)2； g?f(x)＝f(g(x))＝f((x+1)2)＝2(x+1)2；,2024/3/19,（2）((f?g)?h)(x)＝h((f?g)(x))＝h(g(f(x))) ＝h(g(2x))＝h((2x+1)2)＝(2x+1)2/2； (f?(g?h))(x)=(g?h)(f(x))＝h(g(f(x))) ＝h(g(2x))＝h((2x+1)2)＝(2x

32、+1)2/2 ；（3）f?h(x)＝h(f(x))＝h(2x)＝x； h?f(x)＝f(h(x))＝f(x/2)＝x；,例8.3.2 （續(xù)）,2024/3/19,設f和g分別是A到B和從B到C的函數，則：如f,g是滿射，則f?g也是從A到C滿射；如f,g是單射，則f?g也是從A到C單射；如f,g是雙射，則f?g也是從A到C雙射。,定理8.3.1,證明：1) 對任意c∈C，由于g是滿射，所以存在b∈B，使得g(b)＝c。

33、對于b∈B，又因f是滿射，所以存在a∈A，使得f(a)＝b。從而有 f?g(a)＝g(f(a))＝g(b)＝c。即存在a∈A，使得：f?g(a)＝c，所以f?g是滿射。,2024/3/19,2) 對任意a1,a2∈A，a1≠a2，由于f是單射，所以f(a1)≠f(a2)。令b1＝f(a1)，b2＝f(a2)，由于g是單射，所以g(b1)≠g(b2)，即g(f(a1))≠g(f(a2))。從而有f?g(a1)≠f?g(a2)，

34、所以f?g是單射。3) 是1)、2)的直接結果。,定理8.3.1(續(xù)),2024/3/19,定理8.3.2,設f和g分別是A到B和B到C的函數，則如fog是A到C的滿射，則g是B到C 的滿射；如fog是A到C的單射，則f是A到B的單射；如fog是A到C的雙射，則f是A到B的單射，g是B到C的滿射。,2024/3/19,8.3.2函數的逆運算,定義8.3.2 設f:A→B的函數。如果f-1＝{|x∈A∧y∈B∧∈f}是從B到

35、A的函數，則稱f-1：B→A的逆函數。由定義8.3.2可以看出，一個函數的逆運算也是函數。即逆函數f-1存在當且僅當f是雙射。,2024/3/19,例8.3.3,試求出下列函數的逆函數。（1）設A={1,2,3}，B={1,2,3}。f1:A→B定義為 f1={,,}；（2）f2={,,…,,…}（3）f3={|x∈R}。,2024/3/19,解,(1)因f1={,,}，所以 f1-1={,,}；(2)因

36、f2={,,…,,…}，所以f2-1={,,…,,…}；（3）因為f3={|x∈R}，所以 f3-1={|x∈R} ={|x∈R} 。,2024/3/19,定理8.3.3,設f是A到B的雙射函數，則：f-1?f＝IB＝{|b∈B}；f?f-1＝IA＝{|a∈A}；IA?f＝f?IB＝f。,2024/3/19,定理8.3.4,若f是A到B的雙射，則f的逆函數f-1也是B到A的雙射。證明（1）

37、證明f是滿射。因為ranf-1=domf=A，所以f-1是B到A的滿射。（2）說明f是單射。對任意b1,b2∈B，b1≠b2，假設f-1(b1)= f-1(b2)，即存在a∈A，使得∈f-1，∈ f-1 ，即∈f，∈f，這與f是函數矛盾，因此f-1(b1)≠ f-1(b2)，故f-1是B到A的單射。綜上，f-1是B到A的雙射。,2024/3/19,8.3.4函數運算的應用,例8.3.4 假設f是的定義如下表。即f(A

38、)=D，f(B)=E，f(C)=S，…等等。試找出給定密文“QAIQORSFDOOBUIPQKJBYAQ”對應的明文。,2024/3/19,8.3.4函數運算的應用,解 由上表知，f-1如下表所示。將密文“QAIQORSFDOOBUIPQKJBYAQ”中的每一個字母在f-1中找出其對應的象就可得出對應的明文：“THETRUCKARRIVESGONIGHT”。,2024/3/19,例8.3.5,設按順序排列的13張紅心紙牌，

39、A2345678910JQK經過1次洗牌后牌的順序變?yōu)?8KA410QJ57629再經兩次同樣方式的洗牌后牌的順序是怎樣的？,2024/3/19,例8.3.5 解,對應結果見下表。,2024/3/19,8.4置換函數,當A是有限集合時，這種情況具有特殊重要性。有限集合上的雙射函數在數學、計算機科學和物理學中有著非常廣泛的應用。8.4.1基本概念定義8.4.1 設A={a1,a2,…,an}是有限集合。從A到A的雙射函數稱為A

40、上的置換或排列(Permutation)，記為P:A→A，n稱為置換的階(Order)。,2024/3/19,,n階置換P:A→A常表示為：第一行是集合A的元素按順序列出，第二行是A中元素對應的函數值。顯然序列P(a1),P(a2),…,P(an)恰好是A中元素的重排，在2.3.1節(jié)的意義下它恰好對應N的一個排列。,,2024/3/19,例8.4.1,解 A上的所有置換P如下：,,,,,,,2024/3/19,例8.4.2,

41、試求出例8.4.1中的置換P2,P4的逆置換，并計算P2,P4的復合運算以及它們的逆的復合運算。解 根據已知有P2={,,}， P4={,,}。（1）P2-1={,,}， P4-1={,,}；（2）P2oP4={,,}， P2-1oP4-1={,,}。,2024/3/19,8.4.3置換函數的應用,例8.4.3 等邊三角形如圖8.4.1所示。求經過旋轉和翻轉能使之重合的所有置換

42、函數。,解 能使三角形重合的置換有6個：（1）三角形繞中心A反時針旋轉120°、240°和360°對應的置換分別為:,,,,（2）繞中線1A,2A,3A翻轉對應的置換分別為：,,,2024/3/19,8.5 本章總結,函數的概念。注意函數與關系的區(qū)別和聯(lián)系；單射、滿射和雙射函數的概念，數學描述形式；特殊函數的基本概念；函數的復合運算，逆運算及運算性質。,2024/3/19,習題類型,基本概念題：涉