離散數(shù)學(xué)-二元關(guān)系和函數(shù)

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

1、1 4.6 函數(shù)的定義與性質(zhì) 函數(shù)的定義 函數(shù)定義 從 A到 B的函數(shù) 函數(shù)的像 函數(shù)的性質(zhì) 函數(shù)的單射、滿射、雙射性 構(gòu)造雙射函數(shù) 應(yīng)用實(shí)例：問題描述 2 函數(shù)定義 定義 設(shè) F 為二元關(guān)系 , 若 x domF 都存在 唯一的 y ranF 使 xFy 成立 , 則稱 F 為 函數(shù) . 對(duì)于函數(shù) F, 如果有 xFy, 則記作 y=F(x), 并稱 y 為 F 在 x 的 值 . 例 1 F1=, F2=, F1是函數(shù) , F2不是函數(shù) 3 函數(shù)相等 定義 設(shè) F, G為函數(shù) , 則 F = G FG GF 如果兩個(gè)函數(shù) F 和 G 相等 , 一定滿足下面兩個(gè)條件： (1) domF =

2、domG (2) x domF = domG 都有 F(x) = G(x) 實(shí)例 函數(shù) F(x)=(x21)/(x+1), G(x)=x1 不相等 , 因?yàn)?domFdomG. 4 從 A 到 B 的函數(shù) 定義 設(shè) A, B為集合 , 如果 f 為函數(shù) domf = A ranf B, 則稱 f 為 從 A到 B的函數(shù) , 記作 f： AB. 實(shí)例 f： NN, f(x)=2x 是從 N 到 N 的函數(shù) g： NN, g(x)=2也是從 N 到 N 的函數(shù) 5 B上 A 定義 所有從 A 到 B 的函數(shù)的集合記作 BA, 讀作“ B上 A”，符號(hào)化表示為 BA = f | f： AB 計(jì)數(shù)：

3、|A|=m, |B|=n, 且 m, n0, |BA|=nm. A=, 則 BA=B=. A且 B=, 則 BA=A= . 6 實(shí)例 例 2 設(shè) A = 1, 2, 3, B = a, b, 求 BA. 解 BA = f0, f1, , f7, 其中 f0=, f1=, f2=,， f3=, f4=,， f5=, f6=, f7=, 7 函數(shù)的像 定義 設(shè)函數(shù) f： AB, A1A. A1 在 f 下的像 ： f(A1) = f(x) | x A1 函數(shù)的像 f(A) 注意：函數(shù)值 f(x) B, 而像 f(A1)B. 例 3 設(shè) f： NN, 且 令 A=0,1, B=2, 那么有 f(A)

4、 = f(0,1) = f(0), f(1) = 0, 2 為奇數(shù)若 為偶數(shù)若 xx xxxf 1 2/)( 8 函數(shù)的性質(zhì) 定義 設(shè) f： AB, （ 1）若 ranf = B, 則稱 f： AB是 滿射 的 . （ 2）若 y ranf 都存在唯一的 x A使得 f(x)=y, 則稱 f： AB是 單射 的 . （ 3）若 f： AB既是滿射又是單射的 , 則稱 f： AB是 雙射 的 f 滿射意味著： y B, 都存在 xA 使得 f(x) = y. f 單射意味著： f(x1) = f(x2) x1= x2 9 實(shí)例 例 4 判斷下面函數(shù)是否為單射 , 滿射 , 雙射的 , 為什么 ?

5、 (1) f： RR, f(x) = x2+2x1 (2) f： Z+R, f(x) = lnx, Z+為正整數(shù)集 (3) f： RZ, f(x) = x (4) f： RR, f(x) = 2x+1 (5) f： R+R+, f(x)=(x2+1)/x, 其中 R+為正實(shí)數(shù)集 . 10 解 (1) f： RR, f(x)=x2+2x1 在 x=1取得極大值 0. 既不單射也不滿射 . (2) f： Z+R, f(x)=lnx 單調(diào)上升 , 是單射 . 但不滿射 , ranf=ln1, ln2, . (3) f： RZ, f(x)= x 滿射 , 但不單射 , 例如 f(1.5)=f(1.2)

6、=1. (4) f： RR, f(x)=2x+1 滿射、單射、雙射 , 因?yàn)樗菃握{(diào)的并且 ranf=R. (5) f： R+R+, f(x)=(x2+1)/x 有極小值 f(1)=2. 該函數(shù)既不單射也不滿射 . 實(shí)例（續(xù)） 11 構(gòu)造從 A到 B的雙射函數(shù) 有窮集之間的構(gòu)造 例 5 A=P(1,2,3), B=0,11,2,3 解 A=,1,2,3,1,2,1,3,2,3,1,2,3. B= f0, f1, , f7 , 其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=,. 令 f： AB, f()=f0, f(1)=f1, f(2)=f2, f(3)=f

7、3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f7 12 實(shí)數(shù)區(qū)間之間構(gòu)造雙射 構(gòu)造方法：直線方程 例 6 A=0,1 B=1/4,1/2 構(gòu)造雙射 f :AB 構(gòu)造從 A到 B的雙射函數(shù)（續(xù)） 解 令 f： 0,11/4,1/2 f(x)=(x+1)/4 13 構(gòu)造從 A到 B的雙射函數(shù)（續(xù)） A 與自然數(shù)集合之間構(gòu)造雙射 方法：將 A中元素排成有序圖形，然后從第一個(gè)元素開始 按照次序與自然數(shù)對(duì)應(yīng) 例 7 A=Z, B=N，構(gòu)造雙射 f： AB 將 Z中元素以下列順序排列并與 N中元素對(duì)應(yīng)： Z： 0 1 1 2 2 3 3 N： 0 1 2 3

8、4 5 6 012 02)(,NZ xx xxff ： 14 常函數(shù)、恒等函數(shù)、單調(diào)函數(shù) 1. 設(shè) f： AB, 若存在 c B 使得 x A 都有 f(x)=c, 則稱 f： AB是 常函數(shù) . 2. 稱 A 上的恒等關(guān)系 IA為 A 上的 恒等函數(shù) , 對(duì)所有 的 x A 都有 IA(x)=x. 3. 設(shè) f： RR，如果對(duì)任意的 x1, x2 R， x1x2, 就 有 f(x1) f(x2), 則稱 f 為 單調(diào)遞增 的；如果對(duì)任意 的 x1, x2 A, x1 x2, 就有 f(x1) f(x2), 則稱 f 為 嚴(yán) 格單調(diào)遞增 的 . 類似可以定義 單調(diào)遞減 和 嚴(yán)格單調(diào)遞減 的函數(shù)

9、 . 15 集合的特征函數(shù) 4.設(shè) A 為集合 , A A, A 的 特征函數(shù) A： A0,1 定義為 ,0 ,1)( AAa Aaa A 實(shí)例 集合： X = A, B, C, D, E, F, G, H , 子集： T = A, C, F, G, H T 的特征函數(shù) T ： x A B C D E F G H T(x) 1 0 1 0 0 1 1 1 16 5. 設(shè) R 是 A 上的等價(jià)關(guān)系 , 令 g： AA/R g(a) = a, a A 稱 g 是從 A 到商集 A/R 的 自然映射 . 自然映射 17 實(shí)例 例 8 (1) A的每一個(gè)子集 A都對(duì)應(yīng)于一個(gè)特征函 數(shù) , 不同的子集對(duì)

10、應(yīng)于不同的特征函數(shù) . 例如 A=a, b, c, 則有 = , , ， a,b = , , (2) 給定集合 A， A 上不同的等價(jià)關(guān)系確定不同 的自然映射 , 其中恒等關(guān)系確定的自然映射是雙 射 , 其他的自然映射一般來說是滿射 . 例如 A=1, 2, 3, R=, IA g(1) = g(2) = 1,2, g(3) = 3 18 4.7 函數(shù)的復(fù)合與反函數(shù) 函數(shù)的復(fù)合 函數(shù)復(fù)合的定理 函數(shù)復(fù)合的性質(zhì) 反函數(shù) 反函數(shù)存在的條件 反函數(shù)的性質(zhì) 19 函數(shù)復(fù)合的定理 定理 設(shè) F, G是函數(shù) , 則 FG也是函數(shù) , 且滿足 (1) dom(FG)= x | x domF F(x) dom

11、G (2) x dom(FG) 有 FG(x) = G(F(x) 推論 1 設(shè) F, G, H為函數(shù) , 則 (FG)H 和 F(GH) 都是函數(shù) , 且 (FG)H = F(GH) 推論 2 設(shè) f： AB, g： BC, 則 fg： AC, 且 x A 都有 fg(x) = g(f(x). 20 函數(shù)復(fù)合運(yùn)算的性質(zhì) 定理 設(shè) f： AB, g： BC. (1) 如果 f： AB, g： BC 都是滿射的 , 則 fg： AC也是滿射的 . (2) 如果 f： AB, g： BC 都是單射的 , 則 fg： AC也是單射的 . (3) 如果 f： AB, g： BC 都是雙射的 , 則 fg

12、： AC也是雙射的 . 證 (1) c C, 由 g： BC 的滿射性 , b B 使得 g(b)=c. 對(duì)這個(gè) b, 由 f： AB 的滿射性， a A 使得 f(a)=b. 由合成定理有 fg(a)=g(f(a)=g(b)=c 從而證明了 fg： AC是滿射的 . 21 函數(shù)復(fù)合運(yùn)算的性質(zhì) (2) 假設(shè)存在 x1, x2 A使得 fg(x1) = fg(x2) 由合成定理有 g(f(x1)=g(f(x2). 因?yàn)?g： BC是單射的 , 故 f(x1)=f(x2). 又由 于 f： AB也是單射的 , 所以 x1=x2. 從而證 明 fg： AC是單射的 . (3) 由 (1) 和 (2)

13、 得證 . 定理 設(shè) f: AB，則 f = fIB = IAf 22 反函數(shù)存在的條件 任給函數(shù) F, 它的逆 F 1不一定是函數(shù) , 是二元關(guān)系 . 實(shí)例： F=,， F 1=, 任給單射函數(shù) f： AB, 則 f 1是函數(shù) , 且是從 ranf 到 A的雙射函數(shù) , 但不一定是從 B 到 A 的雙射函 數(shù) . 實(shí)例： f : N N, f(x) = 2x, f 1 : ranf N, f 1 (x) = x/2 23 反函數(shù) 定理 設(shè) f： AB是雙射的 , 則 f 1： BA也是雙射的 . 證 因?yàn)?f 是函數(shù) , 所以 f 1 是關(guān)系 , 且 dom f 1 = ranf = B ,

14、 ran f 1 = domf = A, 對(duì)于任意的 y B = dom f 1, 假設(shè)有 x1, x2 A使得 f 1 f 1 成立 , 則由逆的定義有 f f 根據(jù) f 的單射性可得 x1 = x2, 從而證明了 f 1是函數(shù)，且是 滿射的 . 下面證明 f 1 的單射性 . 若存在 y1, y2 B 使得 f 1 (y1) = f 1 (y2) = x, 從而有 f 1 f 1 f f y1 = y2 24 反函數(shù)的定義及性質(zhì) 對(duì)于雙射函數(shù) f： AB, 稱 f 1： BA是它的 反 函數(shù) . 反函數(shù)的性質(zhì) 定理 設(shè) f： AB是雙射的 , 則 f 1f = IB, ff 1 = IA

15、對(duì)于雙射函數(shù) f： AA, 有 f 1f = ff 1 = IA 25 函數(shù)復(fù)合與反函數(shù)的計(jì)算 例 設(shè) f： RR, g： RR 求 f g, g f. 如果 f 和 g 存在反函數(shù) , 求出它們的反函數(shù) . 2)( 32 3)( 2 xxg x xxxf f： RR不是雙射的 , 不存在反函數(shù) . g： RR是雙射的 , 它 的反函數(shù)是 g1： RR, g1(x) = x2 12 1)2( )( 30 32 )( RR:RR: 22 x xx xfg x xx xgf fggf 26 問題： 有 2臺(tái)機(jī)器 c1, c2； 6項(xiàng)任務(wù) t1, t2, , t6. 每項(xiàng)任務(wù)的加工時(shí)間分別為： l(

16、t1)=l(t3)=l(t5)=l(t6)=1, l(t2)=l(t4)=2 任務(wù)之間的順序約束是： 任務(wù) t3只有在 t6和 t5完成之后才能開始加工； 任務(wù) t2只有在 t6, t5和 t4都完成后才能開始加工； 任務(wù) t1只有在 t3和 t2完成之后才能開始加工 . 調(diào)度：任務(wù)安排在機(jī)器上加工的方案 截止時(shí)間：開始時(shí)刻 0，最后停止加工機(jī)器的停機(jī)時(shí)刻 問題描述 多機(jī)調(diào)度 27 兩個(gè)調(diào)度方案 D=6 t1 t2 t3 t4 t5 t6 D=5 t1 t3 t5 t2 t6 t4 t5 t6 t4 t3 t2 t1 28 集合 任務(wù)集 T=t1, t2, . , tn, nZ+ 機(jī)器集 M=

17、c1, c2, . , cm， mZ+ 時(shí)間集 N 函數(shù) 和關(guān)系 加工時(shí)間 函數(shù) l:TZ+. 順序約束 R T上的 偏序關(guān)系 ，定義為 R=| ti, tjT, i=j 或 ti完成后 tj 才可以開始加工 問題描述 29 問題描述（續(xù)） 可行調(diào)度 分配到機(jī)器： T 的 劃分 =T1, T2, . , Tm，劃分塊 Tj 是 T 的非空子集， 由安排在機(jī)器 cj上加工的所有任務(wù)組成 . 每個(gè)機(jī)器上的任務(wù)開始時(shí)間 Tj，存在 調(diào)度函數(shù) j:TjN， 滿足以下條件： (1) 任意時(shí)刻 i，每臺(tái)機(jī)器上正在加工至多 1個(gè)任務(wù) i, 0 iD, | tk | tkTj, j(tk)ij(tk)+l(tk) | 1, j=1, 2, , m (2) 任務(wù)的安排滿足偏序約束 tiTi, tjTj, R i(ti)+l(ti)j(tj) i, j=1, 2, , m 30 問題描述（續(xù)） 機(jī)器 j 的停止時(shí)間 Dj=maxj(tk)| tkTj+l(tk) 所有任務(wù)的截止時(shí)間 D=maxDj | j=1,2,.,m. 我們的問題就是確定使得 D達(dá)到最小的可行調(diào)度 .