離散數(shù)學(xué)--5.1-2函數(shù).ppt

1,第5章 函數(shù),2,第5章 函數(shù),5.1 函數(shù)定義及其性質(zhì) 5.2 函數(shù)的復(fù)合與反函數(shù),3,5.1 函數(shù)定義及其性質(zhì),5.1.1 函數(shù)的定義 函數(shù)定義 從A到B的函數(shù) 5.1.2 函數(shù)的像與完全原像 5.1.3 函數(shù)的性質(zhì) 函數(shù)的單射、滿射、雙射性 構(gòu)造雙射函數(shù),4,函數(shù)定義,定義5.1 設(shè) f 為二元關(guān)系, 若 xdomf 都存在唯一的yranf 使 x f y 成立, 則稱 f為函數(shù). 對(duì)于函數(shù)f, 如果有 x f y, 則記作 y=f(x), 并稱 y 為 f 在 x 的值. 例如 f1=, f2=, f1是函數(shù), f2不是函數(shù) ,5,函數(shù)相等,定義5.2 設(shè)f, g為函數(shù), 則 f=g fggf 如果兩個(gè)函數(shù) f 和 g 相等, 一定滿足下面兩個(gè)條件： (1) domf = domg (2) xdomf = domg 都有 f(x) = g(x) 實(shí)例 函數(shù) f(x)=(x21)/(x+1), g(x)=x1 不相等, 因?yàn)?domfdomg.,6,從A到B的函數(shù),定義5.3 設(shè)A, B為集合, 如果 (1) f 為函數(shù) (2) domf = A (3) 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ù),7,B上A,定義5.4 所有從A到B的函數(shù)的集合記作BA, 讀作“B上A” 符號(hào)化表示為 BA = f | f : AB 計(jì)數(shù)： |A|=m, |B|=n, 且m, n0, |BA|=nm. A=, 則 BA=B=. A且B=, 則 BA=A= .,8,實(shí)例,解BA = f0, f1, , f7 , 其中 f0=, f1=, f2=, f3=, f4=, f5=, f6=, f7=, ,例1 設(shè)A = 1, 2, 3, B = a, b, 求BA.,9,重要函數(shù)的定義,定義5.5 (1) 設(shè)f：AB, 如果存在 cB 使得對(duì)所有的 xA 都有 f(x)=c, 則稱 f : AB是常函數(shù). (2) 稱 A 上的恒等關(guān)系 IA為 A 上的恒等函數(shù), 對(duì)所有的 xA 都有 IA(x)=x. (3) 設(shè), 為偏序集，f : AB，如果對(duì)任意的 x1, x2A, x1x2, 就有 f(x1) f(x2), 則稱 f 為單調(diào)遞增的； 如果對(duì)任意的 x1, x2A, x1x2, 就有 f(x1) f(x2), 則稱 f 為嚴(yán)格單調(diào)遞增的. 類似的也可以定義單調(diào)遞減和嚴(yán)格單調(diào)遞減的函數(shù).,10,重要函數(shù)的定義(續(xù)),(4) 設(shè) A 為集合, 對(duì)于任意的 A A, A 的特征函數(shù) A : A0,1 定義為,實(shí)例：設(shè)A=a,b,c, A的每一個(gè)子集 A都對(duì)應(yīng)于一個(gè)特征函數(shù), 不同的子集對(duì)應(yīng)于不同的特征函數(shù). 如 = ,， a,b = ,.,11,(5) 設(shè) R 是 A 上的等價(jià)關(guān)系, 令 g : AA/R g(a) = a, aA 稱 g 是從 A 到商集 A/R 的自然映射.,重要函數(shù)的定義(續(xù)),12,實(shí)例,給定集合 A 和 A 上的等價(jià)關(guān)系 R, 就可以確定一個(gè)自然映射 g : AA/R. 不同的等價(jià)關(guān)系確定不同的自然映射, 其中恒等關(guān)系所確定的自然映射是雙射, 而其他的自然映射一般來(lái)說(shuō)只是滿射. 例如： A=1, 2, 3, 等價(jià)關(guān)系: R1=,IA 自然映射：g1(1) = g1(2) = 1,2, g1(3) = 3 等價(jià)關(guān)系：IA 自然映射：g2(1)=1, g2(2)=2, g2(3)=3,13,重要函數(shù)的定義(續(xù)),W : Z+Z+作為算法的時(shí)間復(fù)雜度函數(shù) W(n)的含義：對(duì)于規(guī)模為 n 的輸入，該算法在最壞情況 下所執(zhí)行的基本運(yùn)算次數(shù)是W(n). 復(fù)雜度函數(shù) f(n) 的階的表示： f(n)=O(g(n) f(n)的階不超過(guò)g(n)的階 f(n)=(g(n) f(n)=O(g(n)且g(n)=O(f(n) 例如: f(n)=n2+n=(n2), g(n)=nlogn=O(n2) 其中 logn 是 log2n 的簡(jiǎn)寫 算法：二分搜索 W(n)=O(logn) 歸并排序 W(n)=O(nlogn),14,函數(shù)的像與完全原像,定義5.6 設(shè)函數(shù) f : AB, A1A, B1B,稱 f(A1) = f(x) | xA1 為A1 在 f 下的像，f(A) 稱為函數(shù)的像. f1(B1)= x | xA f(x)B1 為B1 在 f 下的完全原像 注意: 函數(shù)的像與值的區(qū)別：函數(shù)值 f(x)B, 像 f(A1)B. A1f1(f(A1)， f(f1(B1)B1. 實(shí)例 11,2=f1(a)= f1(f(1) f(f1(b,c)=f(3)=bb, c,15,實(shí)例,1. 設(shè) f : NN, 且 令A(yù)=0,1, B=2, 那么有 f(A) = f(0,1) = f(0), f(1) = 0, 2 f(B) = f(2) = 1 2. A=1, 2, 3, B=a, b, c, f=,，則 f1(a,b) =1,2,3, f1(b,c) =3,16,函數(shù)的性質(zhì),定義5.7 設(shè) f : AB, （1）若ranf = B, 則稱 f : AB是滿射的. （2）若 yranf 都存在唯一的 xA使得 f(x)=y, 則稱 f : AB是單射的. （3）若 f : AB既是滿射又是單射的, 則稱 f : AB是雙射的 f 滿射意味著：y B, 都存在 xA 使得 f(x)=y. f 單射意味著：f(x1)=f(x2) x1=x2,17,實(shí)例,例2 判斷下面函數(shù)是否為單射, 滿射, 雙射的, 為什么? （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ù)集.,18,解 (1) f : RR, f(x)= x2+2x1 (2) f : Z+R, f(x)=lnx (3) f : RZ, f(x)= x (4) f : RR, f(x)=2x+1 (5) f : R+R+, f(x)=(x2+1)/x,實(shí)例(續(xù)),在x=1取得極大值0. 既不是單射也不是滿射的.,單調(diào)上升, 是單射的. 但不滿射, ranf=ln1, ln2, .,是滿射的, 但不是單射的, 例如 f(1.5)=f(1.2)=1.,是滿射、單射、雙射的, 因?yàn)樗菃握{(diào)函數(shù)并且ranf=R.,有極小值f(1)=2. 該函數(shù)既不是單射的也不是滿射的.,19,構(gòu)造從A到B的雙射函數(shù),有窮集之間的構(gòu)造 例3 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)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f7,20,實(shí)數(shù)區(qū)間之間構(gòu)造雙射 構(gòu)造方法：直線方程 例4 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,21,A與自然數(shù)集合之間構(gòu)造雙射 方法：將A中元素排成有序圖形，然后從第一個(gè)元素開(kāi)始 按照次序與自然數(shù)對(duì)應(yīng),構(gòu)造從A到B的雙射函數(shù)(續(xù)),例5 A=Z, B=N，構(gòu)造雙射 f : AB,將Z中元素以下列順序排列并與N中元素對(duì)應(yīng)： Z：011 2233 N：0 1 2 3 4 5 6 則這種對(duì)應(yīng)所表示的函數(shù)是： ,22,5.2 函數(shù)的復(fù)合與反函數(shù),5.2.1 函數(shù)的復(fù)合 函數(shù)復(fù)合的基本定理及其推論 函數(shù)復(fù)合的性質(zhì) 5.2.2 反函數(shù) 反函數(shù)存在的條件 反函數(shù)的性質(zhì),23,函數(shù)復(fù)合的基本定理,定理5.1 設(shè)f, g是函數(shù), 則fg也是函數(shù), 且滿足 (1) dom(fg)= x | xdomf f(x)domg (2) xdom(fg) 有 fg(x) = g(f(x) 證 先證明 fg 是函數(shù). 因?yàn)?f, g 是關(guān)系, 所以 fg 也是關(guān)系. 若對(duì)某個(gè) xdom(fg)，xfgy1和 xfgy2, 則 fg fg t1(f g) t2(f g) t1t2 (t1=t2 g g) y1=y2 所以 fg 為函數(shù).,24,證明,再證明結(jié)論 (1) 和 (2) . 任取x, xdom(f g) t y (fg) t (xdomf t=f(x) tdomg) x x | xdomf f(x)domg 任取x, xdomf f(x)domg f g fg xdom(fg)fg(x)g(f(x) 所以(1) 和 (2) 得證.,25,推論,推論1 設(shè)f, g, h為函數(shù), 則(fg)h 和 f(gh)都是函數(shù), 且 (fg)h = f(gh) 證 由上述定理和關(guān)系合成運(yùn)算的可結(jié)合性得證. 推論2 設(shè)f : AB, g : BC, 則 fg : AC, 且xA都有 fg(x) = g(f(x). 證 由上述定理知 fg是函數(shù), 且 dom(fg) = x | xdomf f(x)domg = x | xA f(x)B = A ran(fg) rang C 因此 fg : AC, 且xA 有 fg(x) = g(f(x).,26,函數(shù)復(fù)合的性質(zhì),定理5.2 設(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 : AC也是雙射的.,27,證明,(1) 任取 cC, 由g : BC的滿射性, bB 使得 g(b)=c. 對(duì)于這個(gè)b, 由 f : AB 的滿射性，aA 使得 f(a)=b. 由 定理5.1 有 fg(a) = g(f(a) = g(b) = c 從而證明了fg : AC是滿射的. (2) 假設(shè)存在 x1, x2A使得 fg(x1) = fg(x2) 由合成定理有 g(f(x1)=g(f(x2) 因?yàn)?g : BC是單射的, 故 f(x1) = f(x2). 又由于 f : AB 也是單射的, 所以 x1=x2. 從而證明fg : AC是單射的.,28,函數(shù)復(fù)合的性質(zhì)(續(xù)),定理5.3 設(shè) f : AB，則 f = f IB=IAf 定理5.3 的證明可以采用集合相等的證明方法,29,反函數(shù)的存在條件及定義,定理5.4 設(shè) f : AB是雙射的, 則f1: BA也是雙射的. 證 因?yàn)?f 是函數(shù), 所以 f 1是關(guān)系, 且 dom f 1= ranf =B , ran f 1= domf =A, 對(duì)于任意的 xB, 假設(shè)有 y1, y2A 使得 f 1f 1 成立, 則由逆的定義有 f f. 根據(jù) f 的單射性可得 y1=y2, 從而證 明了f 1是函數(shù)，且是滿射的. 若存在 x1, x2B使得 f 1(x1) = f 1(x2)=y, 從而有 f 1f 1 f f x1=x2 因?yàn)?f 是函數(shù)） 從而證明了f 1的單射性. 對(duì)于雙射函數(shù)f : AB, 稱f 1: BA是它的反函數(shù).,30,實(shí)例,例1 設(shè) f : RR, g