離散數(shù)學(xué)課件第4章

1、第4章 函數(shù)4.1 函數(shù)的基本概念函數(shù)的基本概念 4.2 特殊函數(shù)類特殊函數(shù)類4.3 逆函數(shù)逆函數(shù)第第4章章 函函 數(shù)數(shù)第4章 函數(shù)4.1 函數(shù)的基本概念函數(shù)的基本概念 4.1.1 函數(shù)的定義函數(shù)的定義 函數(shù)亦稱映射或變換,其定義如下: 定義定義4.11 設(shè)X和Y是集合,一個從X到Y(jié)的函數(shù)f記為f:XY,是一個滿足以下條件的關(guān)系:對每一xX,都存在唯一的yY,使x,yf。 x,yf通常記作f(x)=y,X叫做函數(shù)f的前域,Y叫做f的陪域.在表達(dá)式f (x)=y中,x叫做函數(shù)的自變元,y叫做對應(yīng)于自變元x的函數(shù)值. .第4章 函數(shù)從定義可看出,X到Y(jié)的函數(shù)f和一般X到Y(jié)的二元關(guān)系的不同有以下兩點

2、: (1)X的每一元素都必須作為f的序偶的第一個成分出現(xiàn). (2) 如果f(x)=y1和f(x)=y2,那么y1=y2.第4章 函數(shù) 通常我們也把函數(shù)f看作是一個映射(變換)規(guī)則,它把X的每一元素映射到(變換為)Y的一個元素,因而f(x)又叫做x的映象映象. 在定義一個函數(shù)時,我們必須指定前域,陪域和變換規(guī)則,變換規(guī)則必須覆蓋所有可能的自變元的值.例如例如 f:II,f(x)0,如果x0;f(x)=x1,如果x0 定義了一個函數(shù).第4章 函數(shù) 如果函數(shù)的前域是有限的,那么可以通過列表或畫有向圖表述變換規(guī)則.例如 g:a,b,c,d1,2,3 g(a)=1 g(b)=2 g(c)=2 g(d)=

3、1 定義了一函數(shù).或x g (x)a 1a 2c 2d 1第4章 函數(shù)圖 4.11第4章 函數(shù)定義 4.12 設(shè)f:XY,g:WZ,如果X=W,Y=Z,且對每一xX有f(x)=g(x)則稱f=g. 函數(shù)相等的定義和關(guān)系相等的定義是一致的,它們必須有相同的前域與陪域和相等的序偶集合.例如 函數(shù)f:II,f(x)=x2和 函數(shù)f:1,2,3I,f(x)=x2 是兩個不同的函數(shù).第4章 函數(shù) 圖 4.12 第4章 函數(shù) 定義4.13 設(shè)f是從X到Y(jié)的函數(shù),X是前域X的子集,那么f(X)表示Y的子集, f(X)=yx(xXy=f(x)叫做函數(shù)f下X的映象.整個前域的映象f(X)叫做函數(shù)f的映象(或叫f

4、的值域).對任何函數(shù)f: XY，定義4.1-3含蓄地指定了另一函數(shù)F，F(xiàn): (X)(Y)，對任一X X，F(xiàn)(X)=y x(xXy=f(x)。f和F顯然不是相同的函數(shù)，f的前域和陪域是集合X和Y，f映射X的元素到Y(jié)的元素; F的前域和陪域是集合(X)和(Y)， F映射X的子集到Y(jié)的子集，如圖4.1-2所示。第4章 函數(shù)圖 4.1-3 第4章 函數(shù) 例例4.1-1 (1)假定f:a,b,c,d1,2,3,4用圖4.13定義. 那么f (a)=1; f (a,b)=1,3; f (a,b,c)=1,3; f (a,b,c,d)=1,3,4; f ( )=第4章 函數(shù)圖 4.14第4章 函數(shù) (2)

5、設(shè)f:II,x0時f (x)=0,x0時f (x)=x1,那么: f (1)=0, f (1)=0 f (0)=0, f (0)=0 f (1)=0, f (1)=0 f (2)=1, f (1,2,3,)=N f (3)=2, f (2,4,6,8)=1,3,5,7 f (4)=3, f (0.1,2,)=0 第4章 函數(shù) 通常用YX表示從集合X到集合Y的所有函數(shù)的集合,應(yīng)用這樣的符號有其方便之處,因為如果X和Y都是有限集合時,設(shè)X=m ,Y=N ,則YX=Nm = YX.這是因為對每個自變元,它的函數(shù)值都有N 種取法,故共有nm 種從X到Y(jié)的函數(shù). 函數(shù)的前域X時常是某個集合叉積.具有前域

6、 1niiXX 的函數(shù)f叫做n個變元的函數(shù),在x1,x2,xn 上的f值用f (x1,x2,xn )表示,這里xiXi.算術(shù)運算,諸如加,減,乘等都是二元函數(shù)的例子.這些函數(shù)通常用固定的符號表示.例如加法可表示為+(x,y),或x+y.第4章 函數(shù) 例4.1-2 (a)設(shè)X=a,b,z,Y=01,02,26,f:XY. f (a)=01,f (b)=02,f (z)=26.f是一個簡單的編碼函數(shù). (b)S :N N ,S (N )=N +1.S 叫皮亞諾后繼函數(shù). (c)X和Y是非空集合,P:XYX,P(x,y)=x.P稱為投影函數(shù). (d)X和Y是非空集合,f:X(XY),f (x)=xY

7、.函數(shù)值xY代表XY在x處的截痕,f叫截痕函數(shù).(e) 如果X=,Y是任意集合,那么空關(guān)系是從X到Y(jié)的無義的函數(shù),叫空函數(shù).如果X而Y=,那么從X到Y(jié)的唯一關(guān)系是空關(guān)系,但這空關(guān)系不是從X到Y(jié)的函數(shù).沒有一個函數(shù),它有非空的前域和空的陪域.第4章 函數(shù) 4.1.2 合成函數(shù)合成函數(shù) 關(guān)系可以合成.函數(shù)是關(guān)系,也可以合成,下述定理將證明由合成所得的關(guān)系確是一個函數(shù).合成是獲得新函數(shù)的常用方法之一,因為直接去定義一個具有一定性質(zhì)的函數(shù),有時不如利用兩個具有一定性質(zhì)的已知函數(shù)合成得出來得方便. 第4章 函數(shù) 定理定理 4.11 設(shè)g:XY和 f:YZ是函數(shù), 那么合成函數(shù)fg是從X到Z的函數(shù) g:X

8、Y和f:WZ且YW時, 如果需要也可定義合成函數(shù)fg, 不一定要求Y=W., 對一切xX, (fg)(x)=f(g(x). 證證 因為f和g都是關(guān)系, fg是從X到Z的關(guān)系. 所以我們只須證明對每一xX, 有一個唯一的zZ使x, zfg, 那么fg就是函數(shù)了. 因為g是函數(shù)，對每一xX，有一yY使g(x)=y。因為f是函數(shù)，對每一yY，有一zZ使f(y)=z。因為x，yg，y，zf，這得出x，zfg。再者，由于g和f都是函數(shù)，x唯一地確定y，y唯一地確定z，于是x唯一地確定z。所以，x，z是以x為第一分量的合成關(guān)系fg的唯一序偶。這樣，fg是一函數(shù)，而(fg)(x)=z=f(y)=f(g(x)

9、。 證畢。 第4章 函數(shù) 例例4.1-3 (1) 設(shè)g:a, b, cA, B, C, D和 f :A, B, C, D1, 2, 3, 用圖4.14定義, 那么f g:a, b, c1, 2, 3如圖4.15所示. (2) 設(shè)g:0, 1, 2N定義為g(x)=x+1, f :NN定義為f (x)=3x+2, 則合成函數(shù)gf 沒有定義, 因為g的前域不等于f 的陪域. 然而, 合成函數(shù)f g是有定義的: f g:0, 1, 2N, f g(x)=3x+5第4章 函數(shù)圖 4.15 第4章 函數(shù)圖 4.16第4章 函數(shù) 定理定理 4.12 函數(shù)合成是可結(jié)合的. 即f , g和h都是函數(shù), 那么(

10、f g)h=f (gh). 本定理是定理3.22的一個特殊情況. 另外附帶指出, 今后討論一個合成函數(shù)時, 我們總是假定它是有定義的, 對此不再說明. 如果對某集合X, f :XX, 那么函數(shù)f 能同自身合成任意次. f 的n次合成定義如下: (1) f 0(x)=x, (2) f n+1(x)=f (f n(x), nN. 第4章 函數(shù) 4.1.3 歸納定義的函數(shù)歸納定義的函數(shù) 當(dāng)函數(shù)的前域是用歸納定義的集合時, 歸納法也是指定函數(shù)的方便和有效方法. 函數(shù)的定義隨著前域的定義自然地得出. 例例 4.1-4 (a) 階乘n! 的歸納定義如下: f :NN (1) (基礎(chǔ))f (0)=1. (2

11、) (歸納)f (n+1)=(n+1)f (n). 注意這里極小性條款是不必需的, 函數(shù)已經(jīng)隨著N的歸納定義而在整個前域上定義.第4章 函數(shù) (b) N上的算術(shù)運算能利用后繼函數(shù)歸納地定義. 例如加法運算可如下定義. +: NNN (1) (基礎(chǔ))+(m, 0)=m, 對任一mN. (2) (歸納)+(m, S(n)=S(+(m,n), 或?qū)懗?(m, n+1)=+(m, n)+1, m, nN. (c) 斐波那奇(F IbonaccI)序列 0, 1, 1, 2, 3, 5, 8, 13, 21, 第4章 函數(shù) 它具有如下性質(zhì), 即第二項之后的每一項都是前兩項之和. 它能作為N上的函數(shù)F 歸

12、納地定義. F :NN (1) (基礎(chǔ)) F (0)=0, F (1)=1. (2) (歸納) F (n+2)=F (n+1)+F (n), 對所有nN. 以上都是歸納定義的例子，例子的歸納步驟中函數(shù)值都用較“早”變元的函數(shù)值指定。對kn，f(n)用f(k)表達(dá)的式子叫遞歸公式，用遞歸公式定義叫遞歸定義。遞歸定義時k不一定都小于n。例如以下著名的麥克卡茜(McCarthy)“91函數(shù)”是遞歸地(但不是歸納地)定義的。 第4章 函數(shù) 例4.1-5 f :NN f (x)=x10, 對x100 f (x)=f (f (x+11), 對x100 這個函數(shù)有如下特性, 對所有0 x100, f (x)

13、=91, 其它情況f (x)=x10. 在歸納定義的集合上用遞歸(包括歸納)方法定義一函數(shù), 所得未必是函數(shù). 特別, 當(dāng)前域的歸納定義允許某些元素能用多種方法構(gòu)造時, 更易出現(xiàn)這一情況. 如果定義得滿足函數(shù)定義, 我們說這函數(shù)是良定的. 當(dāng)一函數(shù)是遞歸定義時, 常需證明它是良定的. 第4章 函數(shù) 例例4.1-6 設(shè)=a, b, c, +定義如下: (1) (基礎(chǔ)) a+, b+, c+; (2) (歸納) 如果x+和y+, 那么xy+; (3) (極小性) +是滿足條款1和2的最小集合. 上述+的定義允許用多于一種方法構(gòu)造某些元素, 例如abc, 在歸納步驟中, 可以讓x是a, y是bc,

14、再形成abc; 也可以讓x是ab, y是c, 再形成abc. 第4章 函數(shù) 現(xiàn)在+上如下地定義一函數(shù)f : f :+N (i) (基礎(chǔ)) f (a)=1, f (b)=2, f (c)=3; (ii) (歸納) 如果x+和y+, 那么f (xy)=f (x)f (y). 這個函數(shù)不是良定的, 例如: f (bac)=f (b)f (ac)= = =2 f (bac)=f (ba)f (c)=(f (b)f (a)f (c)=(21)3=8 如果+ 像2.3節(jié)那樣定義, 那么以上這樣地定義的函數(shù)就是良定的了. 遞歸定義的函數(shù)常能寫出計算程序. ( )( )2fcf a312第4章 函數(shù) 4.1.

15、4 偏函數(shù)偏函數(shù) 有時函數(shù)f :XY的前域X沒有明晰指定, 但 X X和X卻是明確的. 對于這種情況, 有以下定義. 定義4.14 X和Y是集合, X X, 從X到Y(jié)的任一函數(shù)f 稱為具有前域X, 陪域Y的偏函數(shù). 而對任一 xXX, 說f (x)無定義. X=X時, 也符合以上定義, 故函數(shù)也可看作偏函數(shù). 有時為了強(qiáng)調(diào)此種情況而稱為全函數(shù). 但通常仍稱全函數(shù)為函數(shù), 僅當(dāng)X X時稱為偏函數(shù). 第4章 函數(shù)例4.1-7 (a) 求實數(shù)方根的運算是從R到R的偏函數(shù) , 對x0無定義. (b) 從R到R的偏函數(shù) , 對自變元x=0和x=1無定義. (c) 計算機(jī)程序是偏函數(shù), 此偏函數(shù)的自變元是

16、程序的輸入, 偏函數(shù)的值是程序的輸出, 如果輸入使程序不終止或不正常終止, 則對這樣的輸入偏函數(shù)無定義. x1( )(1)f xx x第4章 函數(shù) 4.1.5 函數(shù)前域的擴(kuò)大和縮小函數(shù)前域的擴(kuò)大和縮小 有時我們需要縮小所給函數(shù)的前域, 或擴(kuò)大所給函數(shù)的前域以創(chuàng)建新的函數(shù). 為此有以下定義. 定義4.15 設(shè)f :XY, X X, f 到X的限制是一函數(shù), 記為f x, 定義如下: | :| ( )( )xxfXYfxf x第4章 函數(shù) 定義定義4.16 設(shè)f :XY, g:XY而XX. 如果gx=f , 那么, g是f 到前域X的開拓. 例4.1-8 設(shè)f :NN, f (x)=2x, g:I

17、N, 那么, f 是g到N的限制, 即f =gN; g是f 到I的開拓. 20( )10 xxg xx時時第4章 函數(shù) 本節(jié)介紹具有一定性質(zhì)的函數(shù), 因為今后應(yīng)用中遇到最多的正是它們. 定義4.21 設(shè)f 是從X到Y(jié)的函數(shù). (a) 如果f (X)=Y, 那么f 是滿射的(映到的). (b) 如果xx蘊(yùn)含著f (x)f (x) (即f (x)=f (x), 那么x=x), 那么f 是單射的(一對一的). (c) 如果f 是滿射的且是單射的(一對一和映到的), 那么f 是雙射的. 具有這些性質(zhì)的函數(shù)分別叫做滿射函數(shù), 單射函數(shù)和雙射函數(shù). 4.2 特殊函數(shù)類特殊函數(shù)類第4章 函數(shù) 如果f :XY

18、是滿射的, 那么每一元素yY是在f 的象中. 如果f 是單射的, 那么前域不同的元素映射到陪域不同的元素. 如果f 是雙射的, 那么Y的每一元素y是且僅是X的某個元素x的映象, 常稱雙射為一一對應(yīng). 圖 4.21用以說明定義4.21中各類函數(shù)的概念, 函數(shù)的前域和陪域分別用左邊的和右邊的一列小圓點表示. (a)是單射的但不滿射, (b)是滿射的但不單射, (c)是雙射的. 顯然, 如果f 是滿射的, 那么至少有一條弧終止于陪域的每一個元素. 如果f 是單射的, 那么終止于陪域的每一元素的弧不多于一條. 如果f 是雙射的, 那么有且只有一條弧終止于陪域的每一元素.第4章 函數(shù) 圖 4.21第4章

19、 函數(shù) 例4.2-1 (a) 皮亞諾函數(shù)S:NN, S(n)=n+1是單射函數(shù)但不滿射, S的映象是N的真子集1, 2, . (b) g:0, 1a, b, 這里ab, g(x)=(ba)x+a是雙射函數(shù). (c) h:RR, f (x)=x3+2x2是滿射函數(shù)但不單射. 因為每一水平線橫截圖形至少一次, 而有些地方多于一次(參看圖4.22). 第4章 函數(shù) 圖 4.22 第4章 函數(shù) 定理定理4.21 設(shè)g:XY和f :YZ是函數(shù), f g是合成函數(shù). (a) 如果f 和g是滿射的, 那么f g是滿射的. (b) 如果f 和g是單射的, 那么f g是單射的. (c) 如果f 和g是雙射的,

20、那么f g是雙射的. 證證 (1) 任取zZ, 因f 是滿射的, 存在yY, 使f (y)=z; 又因g是滿射的, 存在xX, 使g(x)=y. 于是f g(x)=f (g(x)=f (y)=z, 所以zf g(X). 因為z是任意的, 這就證明了(a)部分. 第4章 函數(shù) (2) 設(shè)x1, x2是X的兩個不同的元素, 因為g是單射的, 推得g(x1)g(x2); 又因f 是單射的且g(x1)g(x2), 推得f g(x1)f g(x2). 所以, x1x2蘊(yùn)含著f g(x1)f g(x2). 這證明了(b)部分. (3) 因為f 和g是雙射的, 它們都是滿射和單射的. 從(a)和(b)得f

21、g是滿射和單射的, 所以是雙射的. 證畢. 第4章 函數(shù) 例4.2-2 (a) 設(shè)E是偶整數(shù)集合, M是奇整數(shù)集合. 雙射函數(shù)f 和g定義如下: g:IE, g(x)=2x f :EM, f (x)=x+1 因為f 和g都是雙射函數(shù), 故合成函數(shù) f g:IM, f g(x)=2x+1. 也是雙射函數(shù). 第4章 函數(shù) (b) 設(shè) 1:0,10, , ( )2211:0, (0,1),( )24xgg xff xx則g, f 都是單射函數(shù), 于是 1:0,1(0,1),( )24xfgfg x第4章 函數(shù) 定理4.21的每一部分的逆定理都不真, 但有下述“部分逆定理”. 定理4.22 設(shè)f g是

22、合成函數(shù), (a) 如果f g是滿射的, 那么f 是滿射的. (b) 如果f g是單射的, 那么g是單射的. (c) 如果f g是雙射的, 那么f 是滿射的而g是單射的. 第4章 函數(shù) 定義4.22 對函數(shù)f :XY, 如果存在yY使對每一xX有f (x)=y, 即f (X)=y, 那么f 稱為常函數(shù). 定義4.23 如果函數(shù)f :XX對一切xX有f (x)=x, 則稱f 為X上的恒等函數(shù), 通常記為1x. 恒等函數(shù)是雙射函數(shù). 定理4.23 設(shè)f :XY是函數(shù), 那么, f =f 1x =1Yf . 第4章 函數(shù) 定義4.24 X上的雙射函數(shù)稱為X上的置換或排列. 例3 (a) 一集合X上的

23、恒等函數(shù)是一個置換, 并被稱作么置換, 或恒等置換. (b) 函數(shù)f :1, 2, 31, 2, 3, 這里f (1)=2, f (2)=1, f (3)=3是一置換. (c) 函數(shù)f :II, f (x)=x+5, 是整數(shù)集合上的一個置換. 第4章 函數(shù) 當(dāng)集合X是無限集時, X上的置換稱為無限次的, 當(dāng)集合X是有限集時, 若X=n; 則X上的置換稱為n次的. n次置換常寫成1212()()()nnxxxPP xP xp x的形式(可以任意交換列的次序). 如例3(b)可寫成123213P第4章 函數(shù) 定理定理4.24 在n個元素的集合中, 不同的n次置換有n! 個. 證 用歸納法. 為了敘

24、述方便, 我們把P:XX記成P:XY. 當(dāng)n=1時, X=x1, Y=y1, 于是XY的雙射函數(shù)的數(shù)目等于1! =1. 設(shè)從n個元素的集合到n個元素的集合的雙射函數(shù)的數(shù)目等于n! 個. 現(xiàn)在考察 X=x1, x2, , xn, xn+1, Y=y1, y2, , yn, yn+1, 我們可以把從X到Y(jié)的所有雙射函數(shù)分割成如下n+1個不相交的集合. 第4章 函數(shù) 例4 設(shè)A=1, 2, 3, 則A上的所有置換為:123456123123123,123132213123123123,321231312PPPPPP 因為置換是雙射函數(shù), 而雙射函數(shù)的合成是雙射函數(shù), 所以置換的合成是置換. 換言之,

25、 置換在合成運算下封閉. 例如2351231231232132113231PPP第4章 函數(shù) 定義4.25 設(shè) U是全集合(論述域), 對每一AU, 函數(shù)A:U0, 1定義為A(x)= 1 如果 xA 0 如果 xA 稱它是集合A的特征函數(shù). 特征函數(shù)A(x)的前域U一般隱含在討論的問題中, 不明確指定. 第4章 函數(shù)例4.2-5 (a) 設(shè)U=a, b, c, d, A=b, d, A:U0, 1則 A(a)=0, A(b)=1, A(c)=0, A(d)=1. (b) 設(shè)U=0, 1, A= ,1 , A:U0, 112則 A(x)= 1 當(dāng) x1時 12 0 當(dāng)0 x 時12第4章 函數(shù)

26、 圖 4.23第4章 函數(shù) 定理定理4.25 設(shè)A和B是全集合U的任意兩個子集, 于是, 對所有xU, 下列關(guān)系式成立. (a) x(A(x)=0) A= (b) x(A(x)=1) A=U (c) x(A(x)B(x)A B (d) x(A(x)=B(x)A=B (E) (x)=1A(x) (f ) AB(x)=A(x)B(x) (g) AB(x)=A(x)+B(x)AB(x) (h) AB(x)=A (x)=A(x)AB(x)AB第4章 函數(shù)證證 只證(f ), 其它留作練習(xí). 當(dāng)xAB時, xA且xB, 所以AB(x)=1, A(x)=1, B(x)=1, 公式成立. 當(dāng)xAB時, x

27、A或 x B, 所以AB(x)=0, A(x)=0或B(x)=0, 公式也成立. 證畢. 第4章 函數(shù)例4.2-6(a) 利用特征函數(shù)證明集合上的命題. (I)證明 =A. 證 (x)=1 (x)=1(1A(x) =A(x), 所以, =A. (II) 證明A(BC)=ABAC. AAAA第4章 函數(shù)證 A(BC)(x) =A(x)BC(x) =A(x)(B(x)+c(x)B(x)c(x) =A(x)()B(x)+A(x)C(x)A(x)B(x)C(x) =AB(x)+AC(x)ABC(x) =AB(x)+AC(x)(AB)(AC)(x) =ABAC (x)所以, A(BC)=ABAC 第4章

28、 函數(shù) (b) 若f (x)只有有窮個值, 則稱f (x)是簡單函數(shù), 可用特征函數(shù)表達(dá)簡單函數(shù). 設(shè) f :AB是函數(shù), 而B=b1, b2, , bn, b1, b2, , bn互不相同. 定義Ai=xf (x)=bi, 1in. 顯然 而ij時AiAj= . 這樣f (x)可表示為 1niiAA1( )( )iniAif xbx第4章 函數(shù)4.3 逆函數(shù)逆函數(shù) 4.3.1 逆函數(shù)逆函數(shù) 給定一個關(guān)系R, 顛倒R的所有序偶, 得到逆關(guān)系 . 給定一個函數(shù)f , 顛崐倒f 的所有序偶, 得到的關(guān)系 卻未必是函數(shù). 例如, X=1, 2, 3, Y= a, b, c, f =1, a, 2,

29、a, 3, c是一函數(shù).而 =a, 1, a, 2, c, 3不是從Y到X 的函數(shù). 但如果f 是從X到Y(jié)的雙射函數(shù), 則定理4.31說明 是Y到X的雙射函數(shù). Rfff第4章 函數(shù) 定理4.31 設(shè)f :XY是一雙射函數(shù), 那么f 的逆關(guān)系 是一雙射函數(shù), :YX. 證證 考慮對應(yīng)于f 和 的序偶集合fff,|( ),|,fx yxXyYf xyfx yx yf 第4章 函數(shù) 定義4.31 設(shè)f :XY是雙射 函數(shù), 稱逆關(guān)系 為f 的逆函數(shù) 。記為f -1, 稱f 是可逆的. 注意僅當(dāng)f 是雙射函數(shù)時逆函數(shù)才有定義. 定理4.32 設(shè)f :XY是可逆的, 則f -1f =1X, f f-1

30、=1Y. 證 設(shè)x的X的任一元素, 如果f (x)=y, 則f -1(y)=x. f -1f (x)=f -1(f (x)=f -1(y)=x 所以, f -1f =1X. 類似地, 設(shè)y是Y的任一元素, 如果f -1(y)=x, 則f (x)=y. f f -1(y)=f (f -1(y)=f (x)=y 所以, f f -1 =1Y. 定理4.33 如果f 是可逆的, 那么(f 1)f第4章 函數(shù) 4.3.2 規(guī)范映射規(guī)范映射 設(shè)f :XY是一函數(shù), X X, Y Y. 前已介紹過f (X)的意義, 現(xiàn)在建立f 1(Y)的意義. 定義4.32 設(shè)f :XY是函數(shù)且Y Y, 那么 1() |

31、( )fYx f xY表示X的子集, 叫做f 下Y的逆象或前象. 第4章 函數(shù) 例例1 (a) 考慮圖4.31表示的函數(shù), 那么f 1(0)=b, f 1(0, 1)=a, b, c, f 1(2, 3)=d, f 1(2, 4)= . 注意f 沒有逆函數(shù). (b) 假定f :XY, 這里X=0, 1, Y=, , f (0)=, f (1)=, 那么f 1用作雙射函數(shù)f 的逆函數(shù)時 f 1()=1 但是用作誘導(dǎo)出的從(Y)到(X)的函數(shù)時 f 1()=0第4章 函數(shù)圖 4.31第4章 函數(shù) 如果函數(shù)f :XY的前域X非空, 那末集合族 f 1(y)yYf 1(y) 形成X的一個劃分, 與此劃

32、分相關(guān)聯(lián)的等價關(guān)系R可如下定義: x1Rx2 f (x1)=f (x2) 容易證明R符合等價條件. 我們稱R為f 誘導(dǎo)的等價關(guān)系. 第4章 函數(shù) 定義定義4.33 設(shè)R是一集合X上的等價關(guān)系, 函數(shù) g:XXR, g(x)=xR 叫做從X到商集XR的規(guī)范映射. 例4.3-2 設(shè)X=a, b, c, d, Y=0, 1, 2, 3, 4, f :XY, f (a)=1, f (b)=0, f (c)=1, f (d)=3, 那么f 誘導(dǎo)的X上的等價關(guān)系R有等價類a, c, b和d. (參看圖4.31). 第4章 函數(shù) 從X到XR的規(guī)范映射是函數(shù)g. g:a, b, c, da, c,b,d g(a)=a, c, g(b)=b, g(c)=a, c, g(d)=d. 從這個例子可以看出, 給定一個函數(shù)f :XY, 可以在f 自身前域X上誘導(dǎo)出一個等價關(guān)系, 對此等價關(guān)系可以定義一個規(guī)范映射. 在計算機(jī)科學(xué)上這些概念有許多應(yīng)用. 第4章 函數(shù) 4.3.3 單側(cè)逆函數(shù)單側(cè)逆函數(shù) 定義定義4.34 設(shè)h:XY和k:YX, 如果kh=1X, 那么k是h的左逆元(或左逆函數(shù)), h是k的右逆元(或右逆函數(shù)). 業(yè)已證明:如果f :XY是雙射函數(shù), 那么函數(shù)f 1存在且f 1f =1X和f f 1=1Y. 因此, f 1既