離散數(shù)學(xué)課件第五章函數(shù)-1st zhou

1、1/44第五章 函數(shù)2/44主要內(nèi)容函數(shù)的基本概念函數(shù)的性質(zhì)函數(shù)的合成、合成函數(shù)的性質(zhì)特殊函數(shù)反函數(shù)、特征函數(shù)基數(shù)二元運(yùn)算3/44回顧4/445.1函數(shù)的基本概念和性質(zhì) 函數(shù)（或稱映射）是滿足某些條件的關(guān)系，關(guān)系又是笛卡爾乘積的子集。 定義：設(shè)X和Y是兩個(gè)任意的集合，并且f是從X到Y(jié)的一種關(guān)系。如果對(duì)于每一個(gè)xX，都存在唯一的y Y，使得f，則稱關(guān)系f為函數(shù)或映射，并記作 f: XY。 對(duì)于函數(shù)來(lái)說(shuō)f:XY，如果有f ，則稱x是自變量；與x相對(duì)應(yīng)的y，稱為在f作用下x的象點(diǎn)，或稱y是函數(shù)f在x處的值。通常用y=f(x)表示f 。 5/44函數(shù)的基本概念從X到Y(jié)的函數(shù)f，是具有下列性質(zhì)的從X到Y(jié)

2、的二元關(guān)系： 每一個(gè)元素xX ，都必須關(guān)系到某一個(gè)yY ；也就是說(shuō)，關(guān)系f的域是集合X本身，而不是X的真子集。就是說(shuō)X中每個(gè)元素都得用上如果有f ，則函數(shù)f在x處的值y是唯一的，亦即 不能一個(gè)X對(duì)應(yīng)多個(gè)Y任意性唯一性6/44函數(shù)的基本概念例：設(shè)A1, 2, 3, 4,B=2, 3, 4, 5, 6,A到B的關(guān)系 =,是否是由A到B的函數(shù)？若調(diào)整為f, 或g=, 呢？7/44函數(shù)的定義域和值域設(shè)f是從X到Y(jié)的函數(shù)，函數(shù)的定義域Df=X,而不會(huì)是X的真子集。 函數(shù)的值域滿足Rf Y. 對(duì)于函數(shù)f,常用f(X)表示Rf。集合Y稱作f的陪域。也稱f(x)是函數(shù)f的象點(diǎn)注意：函數(shù)f的象點(diǎn)與自變量x的象點(diǎn)

3、是不同的。我們這里給出的函數(shù)的定義是全函數(shù)的定義，所以Df=X. 8/44函數(shù)的基本概念和性質(zhì)例：設(shè)E是全集，(E)是E的冪集。對(duì)任何兩個(gè)集合X,Y(E)，它們的并運(yùn)算和相交運(yùn)算都是從(E) (E)到(E)的映射；對(duì)任何集合X(E)的求補(bǔ)運(yùn)算，則是從(E)到(E)的映射。 例：試說(shuō)明下列二元關(guān)系是否是函數(shù)？(1)是函數(shù)，(2)不是函數(shù)9/44函數(shù)的基本概念和性質(zhì)例：設(shè)N是自然數(shù)集合，函數(shù)S: NN定義成S(n)=n+1。顯然，S(0)=1，S(1)=2，S(2)=3。這樣的函數(shù)，通常稱為皮亞諾后繼函數(shù)。 注意：有時(shí)為了某種需要，要特別強(qiáng)調(diào)函數(shù)的任意性和唯一性性質(zhì)：函數(shù)f的域Df中的每一個(gè)x，在

4、值域Rf中都恰有一個(gè)象點(diǎn)y，這種性質(zhì)通常被稱為函數(shù)的良定性。 10/44函數(shù)的相等定義： 給定函數(shù)f: XY和g: ZW。如果f和g具有同樣的域和陪域，亦即X=Z和Y=W，并且對(duì)于所有的x X或xZ都有f(x)=g(x)，則稱函數(shù)f和g是相等的，記作f=g。 求/證明函數(shù)相等的方法？11/44函數(shù)的擴(kuò)大和縮小定義：給定函數(shù)f: XY，且有A X。 試構(gòu)成一個(gè)從A到Y(jié)的函數(shù) 通常稱g是函數(shù)f的縮小，并記作f/A。(2)如果g是f的縮小，則稱f是g的擴(kuò)大。 從定義可以看出，函數(shù)f/A: AY的域是集合A，而函數(shù)f的域則是集合X。f/A和f的陪域均是集合Y。于是若g是f的縮小，則應(yīng)有 Dg Df和g

5、 f并且對(duì)于任何xDg都有g(shù)(x)=(f/A)(x)=f(x)。 12/44函數(shù)的擴(kuò)大和縮小例：令X1=0,1,X2=0,1,2,Y=a,b,c,d。定義從X12到Y(jié)的函數(shù)f為：f=,。g=f ,是從X12 ,到Y(jié)的函數(shù)。于是f=g/X12，因此f是g在X12上的縮?。ɑ蚍Q限制），g是f到X12 ,上的擴(kuò)大（或稱延拓）。 13/44函數(shù)的表示因?yàn)楹瘮?shù)是二元關(guān)系，所以可以用關(guān)系圖和關(guān)系矩陣來(lái)表達(dá)函數(shù)。 函數(shù)f: XY的圖解14/44函數(shù)的表示例： 設(shè)集合X=a,b,c,d和Y=1,2,3,4,5，并且有 f=,試求出Df，Rf 和f的矩陣表達(dá)式。 解：Df=a,b,c,d Rf=1,3,415/

6、44函數(shù)的表示由函數(shù)的定義可知，在關(guān)系矩陣的每一個(gè)行上，都有且僅有一個(gè)元素的值是1，而此行上的其他元素都必定為0。因此，可以用一個(gè)單獨(dú)的列來(lái)代替關(guān)系矩陣。在這個(gè)單獨(dú)的列上，應(yīng)標(biāo)明所對(duì)應(yīng)的給定函數(shù)的各個(gè)值。這樣，該列上的各元素也說(shuō)明了自變量與其函數(shù)值之間的對(duì)應(yīng)關(guān)系。 上例中f的簡(jiǎn)化關(guān)系矩陣為： 16/44函數(shù)的構(gòu)成設(shè)X和Y是任意的兩個(gè)集合。在XY的所有子集中，并不全都是從X到Y(jié)的函數(shù)，僅有一些子集可以用來(lái)定義函數(shù)。 定義：設(shè)A和B是任意兩個(gè)集合，記 BA=f|f: AB17/44函數(shù)的構(gòu)成例：設(shè)集合X=a,b,c和集合Y=0,1。試求出所有可能的函數(shù)f: XY。 解：首先求出的XY所有序偶，于是

7、應(yīng)有 于是，有26 個(gè)可能的子集，但其中僅有下列23個(gè)子集可以用來(lái)定義函數(shù)： 18/44函數(shù)的構(gòu)成設(shè)A和B都是有限集合，且|A|=m和|B|=n，因?yàn)槿魏魏瘮?shù)f: AB的域都是集合A， 所以每個(gè)函數(shù)中都恰有m個(gè)序偶。而且，任何元素x A，都可以在B的n個(gè)元素中任選其一作為自己的象點(diǎn)。因此，應(yīng)有nm 個(gè)可能的不同函數(shù)，亦即 |BA|=|B|A|=nm例：設(shè)A為任意集合，B為任意非空集合。（1）因?yàn)榇嬖谖ㄒ坏囊粋€(gè)從到A的函數(shù)，所以A=。（2）因?yàn)椴淮嬖趶腂到的函數(shù)，所以B=。 19/445.2函數(shù)的合成和合成函數(shù)的性質(zhì) 定義：設(shè)f: XY和g: YZ是兩個(gè)函數(shù)。于是，合成關(guān)系fg為f與g的合成函數(shù)

8、，并用gf表示。即 注意：合成函數(shù)gf與合成關(guān)系fg實(shí)際上表示同一個(gè)集合。這種表示方法的不同有其方便之處：對(duì)合成函數(shù)gf，當(dāng)z=(gf)(x)時(shí)，必有z=g(f(x) gf與g(f(x) 的次序是理想的。20/44函數(shù)的合成和合成函數(shù)的性質(zhì)函數(shù)f的值域是函數(shù)g的域Y的子集，亦即Rf Dg 。條件Rf Dg能確保合成函數(shù)gf是非空的。否則，合成函數(shù)gf是空集。如果gf非空，則能保證gf是從X到Z的函數(shù)。 定理：設(shè)f: XY和g: YZ是兩個(gè)函數(shù)：（1）合成函數(shù)gf是從XZ的函數(shù)，并且對(duì)于每一個(gè)xX，都有(gf)(x)=g(f(x)（2）Dgf =f-1Dg, Rgf=gRf其中f-1Dg表示g的

9、域在下的原象集，gRf表示f的值域在g下的象點(diǎn)集。 21/44函數(shù)的合成和合成函數(shù)的性質(zhì)證明: (1)假設(shè)xX和z1,z2Z，再假設(shè)gf和gf。這個(gè)假設(shè)要求存在yY，能使y=f(x)，z1=g(y)以及z2=g(y)。因?yàn)間是一個(gè)函數(shù)，所以由函數(shù)值的唯一性可知，除非z1=z2，否則不可能有z1=g(y)和z2=g(y)。也就是說(shuō)，僅能有z1=z2=z和 gf。 因此gf是一個(gè)從X到Z的函數(shù)，且 (gf)(x)=z=g(y)=g(f(x)22/44函數(shù)的合成和合成函數(shù)的性質(zhì)證明： (2)若 xDgf，則存在zZ使 gf。因此，必有yY使f且 g。但由 g知 yDg，再由 f，即得xf-1Dg。另

10、一方面，若xf-1Dg ，則有yDg使f。但由y Dg知，有zZ使g，所以 gf，這表明xDgf。同理可證Rgf=gRf。 23/44函數(shù)的合成和合成函數(shù)的性質(zhì)例：設(shè)集合X=x1,x2,x3,x4, Y=y1,y2,y3,y4,y5，Z=z1,z2,z3。函數(shù)f: XY和g: YZ分別是試求出函數(shù)gf=XZ，并給出它的圖解。 解：24/44函數(shù)的合成和合成函數(shù)的性質(zhì)定理：函數(shù)的合成運(yùn)算是可結(jié)合的，即如果f,g,h都是函數(shù)，則應(yīng)有25/44函數(shù)的合成和合成函數(shù)的性質(zhì)因?yàn)楹瘮?shù)的合成運(yùn)算是可結(jié)合的，所以在表達(dá)合成函數(shù)時(shí)，可以略去圓括號(hào)，即 推廣：設(shè)有n個(gè)函數(shù)：f1: X1 X2，f2: X2X3，

11、，fn: XnXn+1，于是無(wú)括號(hào)表達(dá)式唯一地表達(dá)了從X1到Xn+1的函數(shù)。如果X1=X2=Xn=Xn+1=X和f1=f2=fn=f，則可用fn表示從X到X的合成函數(shù) fnfn-1f1。 26/44函數(shù)的合成和合成函數(shù)的性質(zhì)例：設(shè)I是整數(shù)集合，并且函數(shù)f: II給定成f(i)=2i+1。試求出合成函數(shù)f3(i)。 解：合成函數(shù)f3(i)是一個(gè)由I到I的函數(shù)，于是有27/44等冪函數(shù)定義：給定函數(shù)f: XX，如果有f2=f，則稱f是個(gè)等冪函數(shù)。 例：設(shè)I是整數(shù)集合和Nm=0,1,2,m-1，并且函數(shù)f: INm是f(i)=i(mod m)。試證明，對(duì)于n1都有fn=f。 證明： （歸納證法）當(dāng)n

12、=2時(shí)假設(shè)當(dāng)n=k時(shí)，滿足fk=f;那么當(dāng)n=k+1時(shí)，fk+1=fkf=ff=f得證。對(duì)于所有的n1，都有fn=f28/445.3特殊函數(shù)定義：給定函數(shù)f: XY。（a）如果函數(shù)f的值域Rf=Y，則稱f為映上的映射，或稱滿射函數(shù)。（b）如果函數(shù)f的值域Rf Y，則稱f為映入的映射或內(nèi)射。 定義： 給定函數(shù)f: XY,對(duì)于x1,x2 X來(lái)說(shuō)，如果有 或者是則稱f為一對(duì)一的映射，或稱f為單射函數(shù)。定義：給定函數(shù)f: XY。如果f既是滿射的又是單射的，則稱f為一對(duì)一映滿的映射，或稱f為雙射。 29/445.3特殊函數(shù)例：（a）內(nèi)射，單射；（b）滿射；（c）內(nèi)射；（d）雙射，單射，滿射30/44補(bǔ)充

13、函數(shù)f: XY是雙射函數(shù)，必須要求X和Y含有的元素?cái)?shù)目相等，也就是基數(shù)相等，設(shè)為n。思考：從X到Y(jié)上存在多少個(gè)雙射函數(shù)？n！定理：假設(shè)m和n是正整數(shù)并且滿足nm，那么從m元素集合到n元素集合的單射函數(shù)的個(gè)數(shù)為：排列組合31/44補(bǔ)充函數(shù)f: XY是滿射函數(shù)，X中的元素個(gè)數(shù)是m，Y中的元素個(gè)數(shù)是n，mn，問(wèn)可以定義多少個(gè)這樣的滿射函數(shù)？例：X=1,2,3,4，Y=a,b，可以定義多少個(gè)XY的滿射函數(shù)？24-2=1432/44補(bǔ)充例：X=1,2,3,4,5,6，Y=a,b,c，可以定義多少個(gè)XY的滿射函數(shù)？解：設(shè)P1,P2,P3為a,b,c分別不在函數(shù)值域內(nèi)的情況。一個(gè)函數(shù)是滿射的，當(dāng)且僅當(dāng)滿足函

14、數(shù)概念并且不是P1,P2,P3三種情況時(shí)。設(shè)所有的函數(shù)為全集，P1,P2,P3是在全集上的集合，表征意義如上，那么滿射函數(shù)必須滿足用N(A)表示滿足情況A的集合的基數(shù)，N表示全集的基數(shù)，也就是從6元素集合到3元素集合的函數(shù)總數(shù)，根據(jù)包含排斥原理，有33/44補(bǔ)充34/44補(bǔ)充定理：假設(shè)m和n是正整數(shù)并且滿足mn，那么從m元素集合到n元素集合的滿射函數(shù)的個(gè)數(shù)為：35/44特殊函數(shù)定理：給定函數(shù)f和g，并且有合成函數(shù)gf。于是（a）如果f和g都是滿射函數(shù)，則合成函數(shù)gf也是個(gè)滿射函數(shù)。（b）如果f和g都是單射函數(shù)，則合成函數(shù)gf也是個(gè)單射函數(shù)。（c）如果f和g都是雙射函數(shù)，則合成函數(shù)gf也是個(gè)雙射

15、函數(shù)。 證明：給定集合X，Y和Z，并且有函數(shù)f: XY和g: YZ。 36/44特殊函數(shù)證明： (a)設(shè)任意的元素zZ,由于g是個(gè)滿射函數(shù)，因而存在某一個(gè)元素yY，能使g(y)=z。另外，因?yàn)閒是個(gè)滿射函數(shù)，所以存在某一個(gè)元素xX，能使f(x)=y，于是有(gf)(x)=g(f(x)=g(y)=z即z(gf)(X)。由元素zZ的任意性，知命題（a）為真。 37/44特殊函數(shù)證明：（b）設(shè)任意的元素xi,xj X且有xixj,因?yàn)閒是單射的，所以必定有f(xi)f(xj)。由于g是單射的和f(xi)f(xj)可推出g(f(xi)g(f(xj)，即如果xixj，則有(gf)(xi)(gf)(xj)

16、。于是命題（b）的真值為真。 由命題（a）和命題（b）可直接推出命題（c） 注意：以上定理各部分的逆定理均不成立。 實(shí)例考慮集合A=a1,a2,a3, B=b1,b2,b3,b4, C=c1,c2,c3. 令f=,g=,g f =,那么 f:AB和g f :AC是單射的, 但g:BC不是單射的. 考慮集合A=a1,a2,a3, B=b1,b2,b3, C=c1,c2. 令f=,g=, g f =,那么g:BC 和 g f :AC是滿射的, 但 f:AB不是滿射的.39/44特殊函數(shù)定理： 給定函數(shù)f和g，并且有合成函數(shù)gf,于是（1）如果gf是滿射函數(shù)，則g必定是滿射的。（2）如果gf是個(gè)單射

17、函數(shù)，則f必定是個(gè)單射函數(shù)。（3）如果gf是個(gè)雙射函數(shù)，則g必定是滿射的，f是單射的。 證明：給定集合X，Y和Z，并且有函數(shù)f: XY和g: YZ。 (1)合成函數(shù)gf: XZ。因?yàn)間f是個(gè)滿射函數(shù)，所以gf的值域Rgf=Z。設(shè)任意的元素xX，某些yY和zZ，于是應(yīng)有 (gf)(x)=z=g(f(x)=g(y)可見，Rg=Rgf=Z，即g是滿射的，得證。40/44特殊函數(shù)（1）反證法證明。設(shè)f：XY，g：YZ，因?yàn)間f是滿射函數(shù)，若g不是滿射函數(shù)，則必存在Z中的元素z0，使得對(duì)于任意的Y中的元素y，g(y)z0，這樣，對(duì)于X中的任意元素x，gf(x)=g(f(x)=g(y)z0 ,故gf不是滿射函數(shù)，與假設(shè)矛盾，因此，g一定是滿射函數(shù)。41/44特殊函數(shù)（2）合成函數(shù)gf: XZ。設(shè)xi,xjX和xixj。因?yàn)間f是單射的，所以應(yīng)有 因?yàn)間是函數(shù)，所以象點(diǎn)不同時(shí)，原象一定不相同，即 根據(jù)永真蘊(yùn)含關(guān)系的可傳遞性，應(yīng)有 得證。由（1）和（2）可知（3）成立。 42/44特殊函數(shù)（2）反證法證明。設(shè)f：XY，g：YZ，因?yàn)間f是單射函數(shù)，若f不是單射函數(shù)，則必存