《離散數(shù)學》課件1第3章 函數(shù)

1主要內(nèi)容：函數(shù)的基本概念特殊函數(shù)

復合函數(shù)與逆函數(shù)23.1函數(shù)的基本概念在離散數(shù)學中，任何對象，包括集合都可以做自變量或函數(shù)值，并且函數(shù)僅指單值函數(shù)，也沒對兩個集合的元素作任何特殊限制。3關(guān)系在現(xiàn)實世界和信息世界中的表示定義3.1

設(shè)f是集合A到B的關(guān)系，如果對每個xA，都存在唯一yB，使得(x,y)

f，則稱f關(guān)系為A到B的函數(shù)（或映射、變換），記為f:A

B。當(x,y)

f時，通常記為y=f(x)，這時稱x為函數(shù)的自變量，稱y為x在f下的函數(shù)值（或像）。4由函數(shù)的定義顯然有：（1）dom(f)=A，稱為函數(shù)f的定義域；（2）ran(f)B，稱為函數(shù)f的值域，B稱為函數(shù)f的陪域，ran(f)也可記為f(A)，并稱f(A)為A在f下的像；（3）(x,y)

f，(x,z)

f

y=z；（4）|f|=|A|。5例3.1設(shè)集合A={1,2,3}，集合B={a,b,c}，判斷下列各式是否是函數(shù)？(1)(2)(3)解:根據(jù)定義,(1)和(3)滿足條件,因此是函數(shù);(2)不是函數(shù),因為在(2)中,集合A的元素1對應集合B中的兩個元素a,b,故不是函數(shù)。6例3.2:判斷關(guān)系：(1)f1={(a,1),(b,1),(c,2)}。(2)f2={(a,1),(a,2),(b,1),(c,2)}。是否為函數(shù)。解:根據(jù)定義,有(1)對任意的x∈domf1,都存在唯一的y∈ranf1,使得(x,y)∈f1成立,因此f1是函數(shù)。(2)對a∈domf2,存在不同的1∈ranf2,2∈ranf2,使得(a,1)∈f2

與(a,2)∈f2

同時成立,因此f2是函數(shù)。7例3.3（1）任意集合A上的恒等關(guān)系IA是一個函數(shù)，常稱為恒等函數(shù)，并且IA(x)=x（對任意xA）。（2）自然數(shù)集合上的m倍關(guān)系是一個函數(shù)，若用f表示這一關(guān)系，那么f:NN，可表示為：y=f(x)=mx。8函數(shù)的表示方法：（1）列表法：由于函數(shù)具有“單值性”，即對任一自變量有唯一確定的函數(shù)值，因此可將其序偶排列成一個表，將自變量與函數(shù)值一一對應起來。列表法一般適用于定義域為有限集合的情況。（2）圖表法：用笛卡爾平面上點的集合表示函數(shù)。與列表法一樣，圖表法一般適用于定義域有限的情況。（3）解析法：用等式y(tǒng)=f(x)表示函數(shù)，這時可認為y=f(x)為函數(shù)的“命名式”，有別于“y是f在x處的值”。y=f(x)具有雙重意義，可依上下文加以區(qū)別。9定義3.2設(shè)函數(shù)f:AB與g:CD，如果A=C，B=D，并且對任意的aA或aC

，都有f(a)=g(a)，則稱函數(shù)f與g相等，記作f=g。10函數(shù)相等的條件：(1)dom(f)=dom(g);(2)xdom(f)=dom(g),都有f(x)=g(x).11定義3.3設(shè)A,B,C是3個非空集合，函數(shù)f:AB，AC，f在C-A上無定義，則稱f是C到B的偏函數(shù)。定義3.4設(shè)A,B,C是3個非空集合，函數(shù)f:AB

；g:B

C，如果CA

，且對于所有的aC，有f(a)=g(a)，則稱g是f的限制，f是g的擴充。如果g是A到B的偏函數(shù)，當對g無定義處規(guī)定一個值，即對g作一補充定義，即可構(gòu)造出g的一個擴充。12例3.4設(shè)Z是整數(shù)集，并定義函數(shù)f:ZZ

，設(shè)f={(x,2x+1)|xZ}，且N

Z為自然數(shù)集合，求f在Z上的限制。解:先寫出f的集合表示形式如下:f={…,(-1,-1),(0,1),(1,3),…}因此,f在自然數(shù)集N上的限制為g={(0,1),(1,3),…}

13定義3.5設(shè)A,B是非空集合，所有從A到B的函數(shù)記作BA，讀作“B上A”，符號化表示為：BA={f|f:AB}

。14定理3.1設(shè)A,B是非空有限集合，則從A到B共有|B||A|個不同的函數(shù)。證明設(shè)|A|=n，|B|=m。函數(shù)是f從A到B的任一函數(shù)，并且f由A中的n個元素的取值唯一確定，對于A中的任一元素，f在該元素處的取值都有m種可能，因此從A到B可以定義m·m·…m=|B||A|個不同的函數(shù)。例3.5設(shè)集合A={1,2,3},集合B={a,b},計算BA

。解:根據(jù)定義,有BA={f1,f2,f3,f4,f5,f6,f7,f8}。f1(1)=a,f1(2)=a,f1(3)=a;f2(1)=a,f2(2)=a,f2(3)=b;f3(1)=a,f3(2)=b,f3(3)=a;f4(1)=a,f4(2)=b,f4(3)=b;f5(1)=b,f5(2)=a,f5(3)=a;f6(1)=b,f6(2)=a,f6(3)=b;f7(1)=b,f7(2)=b,f7(3)=a;f8(1)=b,f8(2)=b,f8(3)=b。也可以表示成如下形式。f1={(1,a),(2,a),(3,a)};f2={(1,a),(2,a),(3,b)};f3={(1,a),(2,b),(3,a)};f4={(1,a),(2,b),(3,b)};f5={(1,b),(2,a),(3,a)};f6={(1,b),(2,a),(3,b)};f7={(1,b),(2,b),(3,a)};f8={(1,b),(2,b),(3,b)}。1516例3.6設(shè)集合A={1,2}，集合B={a,b,c}，計算BA。17定理3.2設(shè)A,B,X,Y是非空集合，f:XY且A

f(X)，B

f(X)

，則（1）（2）證明:(1)先證f(A∪B)?f(A)∪f(B)。對任意的y∈f(A∪B),存在x∈A∪B,使得y=f(x)即x∈A或x∈B時,有y=f(x),因此f(x)∈f(A)或f(x)∈f(B),即y∈f(A)∪f(B),則f(A∪B)?f(A)∪f(B)。再證f(A)∪f(B)?f(A∪B)。對任意的y∈f(A)∪f(B),有y∈f(A)或y∈f(B),因此在集合A,B中至少有一個集合里有一個x,使得y=f(x)即y=f(x)∈f(A∪B),則f(A)∪f(B)?f(A∪B)因此f(A∪B)=f(A)∪f(B)。(2)對任意的y∈f(A∩B),存在x∈A∩B,使得y=f(x)即x∈A且x∈B時,有y=f(x),因此f(x)∈f(A)且f(x)∈f(B),即y∈f(A)∩f(B),則f(A∩B)?f(A)∩f(B)一般地,f(A∩B)≠f(A)∩f(B)。1819例3.7設(shè)集合X={1,2,3}，集合Y={a,b,c}，A={1,2}，B={3}且f:X→Y,f(1)=a，f(2)=b，f(3)=b,有A∪B={1,2,3},則f(A∪B)={a,b}。因此,f(A)∪f(B)={a,b}∪={a,b},即f(A∪B)=f(A)∪f(B)成立。但是f(A∩B)=f(A)∩f(B)不一定成立。例3.8設(shè)集合X={1,2,3}，集合Y={a,b,c}，A={1,2}，B={3}且f:XY，f(1)=a，f(2)=b，f(3)=b。有A∩B=

，則f(A∩B)=

。但是f(A)∩f(B)={a,b}∩=，

，即f(A∩B)

f(A)∩f(B)成立。但是不滿足f(A∩B)=f(A)∩f(B)。20定義3.6設(shè)集合A=A1×A2×…×An

與集合B,則對任意x∈A,且x=(x1,x2,…,xn),其中,xi∈Ai,1≤i≤n,有y∈B,這時定義y=f(x)=f((x1,x2,…,xn)),則稱f為A到B的n元函數(shù)。例3.9設(shè)A,B是非空集合,f:A×B→A的函數(shù),若f(a,b)=a,則f是一個二元函數(shù),其中,a∈A,b∈B。21223.2特殊函數(shù)定義3.7設(shè)f:AB是一個函數(shù)，

（1）如果對任意的x1,x2A，當x1

x2時，有f(x1)

f(x2)，則稱f為A到B的單射函數(shù)或單射，或稱一對一的函數(shù)。（2）如果對任意的y

B，均有xA

，使y=f(x)，即，則稱f為A到B的滿射函數(shù)或滿射，或稱A到B映上的函數(shù)。（3）如果f既是A到B的單射，又是A到B的滿射，則稱f為A到B的雙射函數(shù)或雙射，或稱一一對應的函數(shù)。23由定義可知：當集合A,B為有限集時，有（1）f:AB是單射的必要條件為|A||B|；（2）f:AB是滿射的必要條件為|A||B|

；（3）f:AB是雙射的必要條件為|A|=|B|

。例3.10設(shè)集合A，B，定義函數(shù)f:AB，在圖3.1中給出了4種不同情形下的函數(shù)：24(a)單射,滿射(b)非單射,非滿射(c)非單射,滿射(d)單射,非滿射例3.11在實數(shù)集上也可以找到這樣的函數(shù)，例如：實數(shù)集上的函數(shù)y=5x

是單射而非滿射，多項式函數(shù)y=ax3+bx2+cx+d(a0)是滿射而非單射，一次函數(shù)y=ax+b(a0)是雙射，但二次函數(shù)y=ax2+bx+c(a0)

既非單射，又非滿射。25例3.12設(shè)集合A={1,2,3,4,5,6,7,8,9,10}，找出一個從A2到A的函數(shù)，能否找到一個從A2到A的滿射，能否找到一個從A2到A的單射？解對任意的x,yA

,設(shè)f((x,y))=max(x,y)則f是一個從A2到A的函數(shù)，該函數(shù)也是一個從A2到A的滿射，因為|A2|=|AA|=1010=100|A|=10因此|A2|>|A|,這是滿射函數(shù)存在的必要條件。但是找不到一個從A2到A的單射,因為A2到A,不滿足單射的必要條件。26例3.13設(shè)集合A=P({1,2,3}),集合B={1,2}{a,b,c},構(gòu)造雙射函數(shù)f:A→B。解:A={

,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}B={f1,f2,f3,f4,f5,f6,f7,f8},

f1={(a,1),(b,1),(c,1)},f2={(a,1),(b,1),(c,2)},f3={(a,1),(b,2),(c,1)},f4={(a,1),(b,2),(c,2)},f5={(a,2),(b,1),(c,1)},f6={(a,2),(b,1),(c,2)},f7={(a,2),(b,2),(c,1)},f8={(a,2),(b,2),(c,2)}。令f:A→B,使得f(?)=f1,f({1})=f2,f({2})=f3,f({3})=f4,f({1,2})=f5,f({1,3})=f6,f({2,3})=f7,f({1,2,3})=f8。2728定理3.3設(shè)A和B為有限集，若|A|=|B|，則f:AB是單射的充要條件是f:AB為滿射。證明:必要性:若f:A→B是單射,則|A|=|f(A)|,因為|A|=|B|,所以|f(A)|=|B|因此,B=f(A)。否則,若存在b∈B且b?f(A),又B是有限集,因此有|f(A)|<|B|=|A|與|f(A)|=|B|矛盾,因此f:A→B是單射。充分性:若f:A→B是滿射,根據(jù)定義有B=f(A),于是|A|=|B|=|f(A)|則f:A→B。否則,存在x1,x2∈A,盡管x1≠x2,但仍有f(x1)=f(x2),因此,|f(A)|<|A|=|B|與|A|=|B|=|f(A)|矛盾,所以f:A→B是單射。29定義3.8設(shè)函數(shù)f:AB

，給出幾個特殊函數(shù)的定義如下：若存在bB，使得對任意的aA都有f(a)=b，則稱f是從A到B的常值函數(shù)；2）集合A上的恒等關(guān)系IA稱為集合A上的恒等函數(shù)。即對任意的aA

，都有IA(a)=a。30定義3.9設(shè)U是全集，且AU，函數(shù)

A:U{0,1}定義為稱

A是集合A的特征函數(shù)。對于特征函數(shù)，滿足定理3.4的性質(zhì)。例3.14設(shè)U={a,b,c,d}，A={a,b}，則A的特征函數(shù)為

A:{a,b,c,d}{0,1}

A(a)=

A(b)=1

A(c)=

A(d)=031定理3.4設(shè)U是全集,且A?U,B?U,則對任意的x∈U,有

(1)?x(ψA(x)=0)?A=

(2)?x(ψA(x)=1)?A=U(3)?x(ψA(x)≤ψB(x))?A?B(4)?x(ψA(x)=ψB(x))?A=B(5)ψA'(x)=1-ψA(x)(6)ψA∩B(x)=ψA(x)·ψB(x)(7)ψA∪B(x)=ψA(x)+ψB(x)-ψA∩B(x)(8)ψA-B(x)=ψA∩B'(x)=ψA(x)-ψA(x)·ψB(x)3233例3.15利用特征函數(shù)證明A∪(B∩C)=(A∪B)∩(A∪C)。證明:對任意的x,有ψ(A∪B)∩(A∪C)(x)=ψA∪B(x)·ψA∪C(x)=(ψA(x)+ψB(x)-ψA∩B(x))·(ψA(x)+ψC(x)-ψA∩C(x))=(ψA(x)+ψB(x)-ψA(x)·ψB(x))·(ψA(x)+ψC(x)-ψA(x)·ψC(x))=ψA(x)+ψA(x)·ψC(x)-ψA(x)·ψC(x)+ψA(x)·ψB(x)+ψB(x)·ψC(x)-ψA(x)·ψB(x)·ψC(x)-ψA(x)·ψB(x)-ψA(x)·ψB(x)·ψC(x)+ψA(x)·ψB(x)·ψC(x)=ψA(x)+ψB(x)·ψC(x)-ψA(x)·ψB(x)·ψC(x)=ψA(x)+ψB∩C(x)-ψA∩B∩C(x)=ψA∪(B∩C)(x)因此A∪(B∩C)=(A∪B)∩(A∪C)。34定義3.10設(shè)R是定義在非空集合A上的等價關(guān)系,函數(shù)f:A→A/R,f(x)=[x]R,其中,[x]R

是x關(guān)于R的等價類,則稱f為從A到商集A/R的自然映射。例3.16設(shè)A={1,2,3},等價關(guān)系R={(1,1),(2,2),(3,3),(1,2),(2,1)},寫出從A到商集A/R的自然映射。解:從A到商集A/R的自然映射f:A→A/R,f(1)=f(2)={1,2},f(3)={3}。35363.3復合函數(shù)與逆函數(shù)定義3.11設(shè)A,B,C是集合，有函數(shù)f:AB和g:BC，則f與g的復合函數(shù)是一個由A到C的函數(shù)，記作gf，符號化表示為gf={(a,c)|aA,cC且存在bB,使得(a,b)f,(b,c)g}對于

aA,有(gf)(a)=g(f(a))

。37例3.17設(shè)f，g均為實數(shù)集上的函數(shù)，f(x)=x+1,g(x)=x2+1,則g

f(x)=g(f(x))=(x+1)2+1=x2+2x+2，

而f

g(x)=f(g(x))=(x2+1)+1=x2+2例3.18設(shè)集合A={a,b,c}上的兩個函數(shù):f={(a,c),(b,a),(c,c)}，g={(a,b),(b,a),(c,c)}，則f

g={(a,c),(b,c),(c,c)}g

f={(a,a),(b,c),(c,c)}38對于復合函數(shù)有如下定理:定理3.5設(shè)函數(shù)f:AB，g:BC，則（1）若f與g是滿射，則gf:AC是滿射；（2）若f與g是單射，則gf:AC是單射；（3）若f與g是雙射，則gf:AC是雙射。證明:(1)對于任意的c∈C,因為g是滿射,所以存在b∈B,使得c=g(b)。而對于b∈B,因為f是滿射,所以存在a∈A,使得b=f(a)。于是(g·f)(a)=g(f(a))=g(b)=c因此g·f是滿射。(2)對于任意的a,b∈A,如果a≠b,則f(a)≠f(b)。又因為g是單射,所以g(f(a))≠g(f(b)),因此g·f是單射。(3)因為f與g是雙射,即f與g既是單射又是滿射,由(1)和(2)可知,g·f也既是單射又是滿射,即g·f是雙射。3940定理3.6設(shè)函數(shù)f:AB，g:BC,則（1）若gf是滿射，則g是滿射；（2）若gf是單射，則f是單射；（3）若gf是雙射，則f是滿射且f是單射。證明:(1)對于任意的c∈C,因為g

f是滿射,所以存在a∈A,使得c=g

f(a),即c=g(f(a))。因此有b=f(a)∈B,使得c=g(b),因此g是滿射。(2)對于a,b∈A,如果f(a)=f(b),又因為g是函數(shù),所以g(f(a))=g(f(b)),即g

f(a)=g

f(b)。由于g

f是單射,所以a=b,即f是單射。(3)因為g

f是雙射,所以g

f既是滿射又是單射,由(1)和(2)可知,g是滿射且f是單射。4142例3.20設(shè)集合A、B、C,函數(shù)f:AB，g:BC

，舉例說明（1）gf是滿射，則f不是滿射；（2）gf是單射，則g不是單射。解:設(shè)A={a1,a2},B={b1,b2},C={c},定義函數(shù)f(a1)=f(a2)=b1,g(b1)=g(b2)=c,則g

f:A→C為g

f(a1)=g

f(