離散數(shù)學(xué)-函數(shù)

《離散數(shù)學(xué)-函數(shù)》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-函數(shù)（36頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、1 第6章 函數(shù) 2 主要內(nèi)容n6.1 函 數(shù) 的 概 念 n6.2 復(fù) 合 函 數(shù) 與 逆 函 數(shù)n6.3 基 數(shù) 的 概 念n6.4 基 數(shù) 的 比 較 3 6.1 函數(shù)的概念 n 定 義 6.1.1 函 數(shù)一 種 特 殊 的 關(guān) 系亦 稱 映 射 或 變 換設(shè) A和 B是 非 空 集 合 , f是 一 個(gè) 從 A到 B的關(guān) 系 ， 如 果 對 于 每 一 個(gè) a A ， 均 存 在 唯 一 的b B ， 使 得 f ， 則 稱 關(guān) 系 f是 由 A到 B的一 個(gè) 函 數(shù) 。 記 作 f : AB。 特 殊 地 ， 當(dāng) A = B時(shí) ，稱 f是 A上 的 函 數(shù) f通 常 記 作 f(x)

2、=y 4 例：判斷以下關(guān)系是否為函數(shù) 5 例n 例 6.1.3 設(shè) E是 全 集 ， A E ， 那 么 A的 特 征函 數(shù) A是 E到 0,1的 函 數(shù) ：a E ， Aa Aaa A 10)(n例 設(shè) E= a, b, c, d , A= b, dA:E 0, 1A=, 6 n 設(shè) A和 B是 全 集 E的 任 意 兩 個(gè) 子 集 , 對 所 有x E, 下 列 關(guān) 系 式 成 立(a) x(A(x)=0) A=(b) x(A(x)=1) A=E(c) x(A(x)B(x)AB(d) x(A(x)=B(x)A=B(e) A(x)=1 A(x) (f) AB(x)=A(x)B(x) (g)

3、A B(x)=A(x)+B(x) AB(x)(h) A B(x)=AB (x)=A(x) AB(x) 7 函數(shù)的定義域和值域n 設(shè) f : XYXf的 前 域 (定 義 域 dom f)Y f的 陪 域 (值 域 ran f Y )f (x)=ynx函 數(shù) 的 自 變 元ny自 變 元 x的 函 數(shù) 值 ， 也 稱 為 x的 像dom f= Xran f= f (X)如 果 f(x)=y 1和 f(x)=y2,那 么 y1=y2 8 n 設(shè) f : XYX Xf(X)=y| x(x X f(x)=y) Yn 稱 f(X)為 X的 象n 稱 X為 f(X)的 原 象n 例 f:NN, f(x)=

4、2x.A=N偶 =0,2,4,6,=2k|k N,f(A)=0,4,8,12,=4k|k NB=2+4k|k N=2,6,10,14,B的 原 象 =1+2k|k N =1,3,5,7,=N 奇 象(im age)與原象(preim age) 9 例假 定 f: a,b,c,d 1,2,3,4f ( a )= 1 ; f ( a,b )= 1,3 ; f ( a,b,c )= 1,3 ; ranf=f ( a,b,c,d )= 1,3,4 ; 10 n 定 義 6.1.2 設(shè) f:XY,g:WZ,如 果 X=W,Y=Z,且 對 每 一 x X有f(x)=g(x)則 稱 f=g.函 數(shù) 相 等

5、的 定 義 和 關(guān) 系 相 等 的 定 義 一 致必 須 有 相 同 的 前 域 與 陪 域 和 相 等 的 序 偶 集 合例 nf:II, f(x)=x2ng: 1,2,3 I, g(x)=x2 n 是 兩 個(gè) 不 同 的 函 數(shù) 11 n 通 常 用 BA表 示 從 集 合 A到 集 合 B的 所 有 函 數(shù) 的 集 合 ,讀 作 B上 A BA = f | f: AB設(shè) A =m , B =n ， 共 有 多 少 個(gè) A到 B的 函 數(shù) ？ BA =nm例 ： 設(shè) A a,b,c， B 0,1。 則 共 有 個(gè) A到 B的 函數(shù) (它 們 分 別 是 A的 個(gè) 子 集 的 特 征 函 數(shù)

6、 )， 它 們 是 f1 , f2 ,f3 , f4 ,f 5 , f6 ,f7 , f8 , 12 n 函 數(shù) 是 特 殊 的 關(guān) 系 ， 故 也 可 用 關(guān) 系 圖 或 關(guān) 系矩 陣 來 表 示 函 數(shù) 例 ： 集 合 A 1,2,3,4上 的 函 數(shù) f, 0001 1000 0100 0010 1432 4321 13 特殊函數(shù)類n 滿 射 、 入 射 和 雙 射n 定 義 6.1.3 設(shè) f 是 從 X到 Y的 函 數(shù)(a) 如 果 xx蘊(yùn) 含 著 f (x)f (x) (即 f (x)=f (x), 那 么x=x), 那 么 f 是 入 射 (injection, 單 射 ， 一

7、對 一 的 ，1-1)(b) 如 果 f (X)=Y, 那 么 f 是 滿 射 (surjection, 映 上 的 , onto)(c) 如 果 f 既 是 滿 射 又 是 入 射 , 那 么 f 是 雙 射(bijection, 1-1, onto) 雙 射 常 稱 作 一 一 對 應(yīng) ， 又 稱 集 合 同 構(gòu) (set isomorphism) 14 n 例 6.1.9 設(shè) A和 B是 兩 個(gè) 集 合 ， 若 存 在 b B使 得 對任 意 a A皆 有 f(a) b， 則 稱 f是 常 函 數(shù)一 般 說 來 ， 常 函 數(shù) 不 是 入 射 ， 也 不 是 滿 射 (除 非 B是 一

8、個(gè)一 元 集 合 )。n 例 6.1.10 設(shè) R是 一 集 合 X上 的 等 價(jià) 關(guān) 系 , 函 數(shù) g:XX R, g(x)= x R 叫 做 從 X到 商 集 X R的 規(guī) 范 映 射 .例 設(shè) X= a, b, c, d , Y= 0, 1, 2, 3, 4 , n f :XY, f (a)=1, f (b)=0, f (c)=1, f (d)=3n f 誘 導(dǎo) 的 X上 的 等 價(jià) 關(guān) 系 R有 等 價(jià) 類 a, c , b ， dn 從 X到 X R的 規(guī) 范 映 射 g: a, b, c, d a, c , b , d g(a)= a, c , g(b)= b g(c)= a,

9、c , g(d)= d 15 n 定 理 6.1.1 若 f是 到 的 函 數(shù) ， 其 中 和 都 是 非 空 有 限 集 ， 且 # # ， 那 么 ： f是一 個(gè) 入 射 iff f是 一 個(gè) 滿 射 。證 明 必 要 性若 f是 一 個(gè) 入 射 ， 則 # #f( )， 故 #f( ) # ，而 是 有 限 集 ， 故 f( ) ， 因 此 ， f是 一 個(gè) 滿射 。 充 分 性若 f是 一 個(gè) 滿 射 ， 則 f( ) ， 于 是 # # #f( )， 因 為 是 有 限 集 ， 故 f是 一 個(gè) 入 射 。定 理 的 結(jié) 論 只 在 有 限 集 的 情 況 下 才 有 效 16 例A

10、到 B存 在 入射 ， |A| |B| A到 B存 在 滿射 ， |A| |B| A到 B存 在 雙射 ， |A|= |B|，稱 A和 B等 勢 17 6.2 復(fù)合函數(shù)與逆函數(shù)n 定 理 6.2.1 設(shè) g:XY和 f:YZ是 函 數(shù) , 那么 從 X到 Z的 復(fù) 合 關(guān) 系 是 一 個(gè) X到 Z的 函 數(shù) ， 記 為 fg，定 義 為 對 一 切 x X, (fg)(x)=f(g(x).復(fù) 合 函 數(shù) gf就 是 復(fù) 合 關(guān) 系 fg 。 要 注 意的 是 為 了 方 便 ， 當(dāng) 將 其 看 作 復(fù) 合 函 數(shù) 時(shí) ， 在 其表 示 記 號 中 顛 倒 f和 g的 位 置 而 寫 成 gf

11、n 定 理 6.2.2 若 f是 到 的 函 數(shù) ， 則 fIA IBf f 18 n 設(shè) 集 合 A=a1,a2,a3,a4, B=b1,b2,b3,b4,b5, Cc1,c2,c3,c4 函 數(shù) f:AB和 g:BC， 分 別 定 義 為f=, , , , g=, , , , 例g f =, 19 n 定 理 6.2.3 函 數(shù) 復(fù) 合 是 可 結(jié) 合 的 . 即 f , g和 h都是 函 數(shù) , 那 么 (f g)h=f (gh).n 定 義 6.2.1如 果 對 某 集 合 X, f :XX, 那 么 函 數(shù) f 能 同 自 身 復(fù)合 任 意 次 . f 的 n次 復(fù) 合 定 義 如

12、下 :(1) f 0(x)=x(2) f n+1(x)=f (f n(x), n N 20 n 定 理 6.2.4 設(shè) g:XY和 f :YZ是 函 數(shù) , f g是復(fù) 合 函 數(shù)(a) 如 果 f 和 g是 滿 射 , 那 么 f g是 滿 射(b) 如 果 f 和 g是 入 射 , 那 么 f g是 入 射(c) 如 果 f 和 g是 雙 射 , 那 么 f g是 雙 射證 明 (a):z Z, 因 為 f 是 滿 射 , 存 在 y Y, 使 得 f (y)=z又 g是 滿 射 , 存 在 x X, 使 g(x)=y于 是 f g(x)=f (g(x)=f (y)=z, 即 對 Z中 任

13、 一 元 素 都 能 找 到 其 原 像 f g是 滿 射 21 證 明 (b):設(shè) x1, x2X， x1x2 g是 入 射 g(x1)g(x2)又 f 是 入 射 , 且 g(x1)g(x2) f g(x1)f g(x2)即 f g是 入 射證 明 (c):因 為 f 和 g是 雙 射 , 由 (a)和 (b)得 f g是 滿 射 和 入 射 , 所 以 f g是 雙 射 22 例(a) 設(shè) E是 偶 整 數(shù) 集 合 , M是 奇 整 數(shù) 集 合 . 雙 射 函 數(shù) f 和g定 義 如 下 : g: IE, g(x)=2x； f :EM, f (x)=x+1 f g:IM, f g(x)=

14、2x+1(b) g:0,1 0,1/2 , g(x)=x/2 f:0, 1/2 (0,1) , f(x)=x+1/4 f g: 0,1 (0,1) , f g(x)=x/2+1/4 23 n定 理 6.2.4的 逆 命 題 并 不 成 立 24 n 定 理 6.2.5 設(shè) g:XY和 f :YZ是 函 數(shù) ， f g是復(fù) 合 函 數(shù)(a) 如 果 f g是 滿 射 , 那 么 f 是 滿 射(b) 如 果 f g是 入 射 , 那 么 g是 入 射(c) 如 果 f g是 雙 射 , 那 么 f 是 滿 射 而 g是 入 射 證 明 (a): zZ (只 需 證 明 z有 原 像 ) f g是

15、 X到 Z的 滿 射 ， xX, f g(x)= z記 y=g(x)， 顯 然 yY， 且 f (y)=z，說 明 f 是 滿 射證 明 (b):假 若 不 然 ，存 在 x 1, x2X， x1x2， 但 g(x1)=g(x2)則 必 有 fg(x1)=fg(x2)， 與 f g是 入 射 矛 盾 25 逆函數(shù)n 函 數(shù) 的 逆 關(guān) 系 不 一 定 是 函 數(shù)n 例 X= 1, 2, 3 , Y= a, b, c f = , , 是 函 數(shù) f-1 = , , 不 是 函 數(shù)n 定 理 6.2.6 設(shè) f :XY是 一 雙 射 函 數(shù) , 那 么 f 的逆 關(guān) 系 f-1是 一 雙 射 函

16、數(shù) , f-1 :YX 26 n 定 理 6.2.7 若 f是 到 的 雙 射 ， 則 f -1f =IA, f f-1=IB證 明 ： x A, 若 f (x)=y, 則 f -1(y)=x 則 f -1f (x)=f -1(f (x)=f -1(y)=x 所 以 , f -1f = IA 類 似 可 證 f f-1=IB 27 n 定 理 6.2.8 若 f是 到 的 函 數(shù) ， g是 到 的 函 數(shù) ， 且 gf =IA, f g=IB， 則 g f -1， f g-1。證 明 我 們 只 證 明 g f -1， f g-1同 理 可 得因 為 IA和 IB都 是 雙 射 ， 這 樣 從

17、 gf =IA可 知 f是 入 射 ，g是 滿 射 ；又 從 f g=IB可 知 g是 入 射 ， f是 滿 射 。 也 即 g和 f皆是 雙 射 。 從 而 ：g gIB g (f f-1) ( g f )f-1 IA f-1 f-1 28 練習(xí)n 設(shè) A=a, b, c, d,B=1, 2, 3, 4, , 和 均是 由 到 的 函 數(shù) ,這 些 函 數(shù) 的 值 域 分 別 為 f( )=1,2,4, ( )=1,3,h( )= 這 三 個(gè)函 數(shù) 中 , 有 逆 函 數(shù) 。n 判 斷 以 下 函 數(shù) 是 否 有 逆 函 數(shù)(1) f:I , f(i)=3i ( ) (2) g:RR , f

18、(r)=3r ( )h NY 29 n 定 義 6.2.2設(shè) f是 到 的 函 數(shù) ， 若 存 在 到 的 函 數(shù) g使 得gf =IA， 則 稱 f是 左 可 逆 的 ， 并 稱 g是 f的 左 逆 ； 類似 地 ， 若 存 在 到 的 函 數(shù) h使 得 f h =IB ， 則 稱f是 右 可 逆 的 ， 并 稱 h是 f的 右 逆 ； 若 f既 是 左 可 逆的 ， 又 是 右 可 逆 的 ， 則 稱 f是 可 逆 的 。例 ： 設(shè) f1、 f2 、 g1、 g2是 四 個(gè) 上 的 函 數(shù) ， 其 中 22 100 1 xx xxf 若 或若 22 1012 xx xxf 若 或若 ,21

19、 xxg 12 002 xx xxg 若若 左 逆 (右 逆 、 逆 )不 一 定 存 在 ； 也 不 一 定 唯 一 30 例abc 1234 abcA B Af g abc 1234 abcA B Af gabc 1234 abcA B Ah fabc 1234 abcA B Ah f 31 n 定 理 6.2.9(a) f 有 左 逆 元 當(dāng) 且 僅 當(dāng) f 是 入 射(b) f 有 右 逆 元 當(dāng) 且 僅 當(dāng) f 是 滿 射(c) f 有 左 逆 元 和 右 逆 元 當(dāng) 且 僅 當(dāng) f 是 雙 射(d) 如 果 f有 左 逆 g且 有 右 逆 h , 那 么 g = h = f -1證

20、 明 (a)： 必 要 性 ： 假 設(shè) g是 f 的 左 逆 元 , gf = IA , IA是 雙 射 , f 是 入 射充 分 性 ： 用 構(gòu) 造 性 證 明 . f 是 入 射 ， y f(X), 必 存 在 唯 一 的 x X使 f(x)=y 選 取 任 意 元 素 x 0 X, 定 義 Y到 X的 函 數(shù) g如 下 : )(, )(),(,)( 0 Xfyx yxfXfyxygg是 f 的 左 逆 元 32 abc 1234 abcA B Af habc 1234 abcA B Af g 33 證 明 (b)： 必 要 性 ： 假 設(shè) h是 f 的 右 逆 元 , fh = IB ,

21、 IB是 雙 射 , f 是 滿 射充 分 性 ： 用 構(gòu) 造 性 證 明 . f 是 滿 射 ， 構(gòu) 造 Y到 X的 函 數(shù) h如 下 :h(y)=x, 其 中 x X且 f(x)=y( 若 X中 有 多 個(gè) 元 素 在 f作 用 下 的 象 為 y， 則 可 從 中 任 取 一個(gè) 作 為 y在 h作 用 下 的 象 ) abc 123 4 abcA B Ah fabc 1234 abcA B Ah f 34 證 明 (d)： 因 為 gf = IA和 f h= IB則 g=g IB =g (f f-1)=( g f ) f-1= IA f-1 =f-1 h= IA h= (f-1f) h=

22、 f-1 ( f h ) = f-1 IB =f-1n 以 上 定 理 實(shí) 質(zhì) 上 指 出 了 逆 函 數(shù) 的 存 在 性 、唯 一 性 與 相 互 性唯 有 雙 射 是 可 逆 的 ， 且 其 逆 關(guān) 系 即 是 它 的 左 逆兼 右 逆 (稱 為 逆 函 數(shù) 或 反 函 數(shù) )每 個(gè) 雙 射 的 逆 函 數(shù) 是 唯 一 的 (即 是 它 的 逆 關(guān) 系 )。逆 函 數(shù) 是 相 互 的 ， 即 (f -1 ) -1 f 35 n 定 理 6.2.10 若 f是 到 的 雙 射 ， g是 到 的 雙 射 。 那 么 (gf ) -1 = f -1 g -1 由 條 件 證 明 可 得 ， gf是 到 的 雙 射 。 此 外 ，由 于(gf ) (f -1 g -1)= g(f f -1 ) g -1= g IB g -1 = g g -1 = IC和(f -1 g -1) (gf ) = f -1 (g -1 g) f = f -1 IC f = f -1 f = IA可 得 (gf ) -1 = f -1 g -1 36 n 推 論 若 f是 集 合 上 的 雙 射 ， n ， 則(f -1 )n (f n )-1這 樣 ， 我 們 可 定 義 集 合 上 的 雙 射 的 負(fù) 次 方 冪 為f -n (f -1 )n (f n )-1 ， 其 中 n