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

1、關(guān)于離散數(shù)學(xué)二元關(guān)系和函數(shù)第一張，PPT共三十六頁，創(chuàng)作于2022年6月 在高等數(shù)學(xué)中，函數(shù)是在實(shí)數(shù)集合上進(jìn)行討論的，其定義域是連續(xù)的。 本章把函數(shù)概念予以推廣 定義域?yàn)橐话愕募?，支持離散應(yīng)用。 把函數(shù)看作是一種特殊的關(guān)系：單值二元關(guān)系。4.6函數(shù)的定義與性質(zhì)第二張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)定義定義 設(shè) F 為二元關(guān)系, 若 xdomF 都存在唯一的yranF 使 xFy 成立, 則稱 F 為函數(shù). 對于函數(shù)F, 如果有 xFy, 則記作 y=F(x), 并稱 y 為 F 在 x 的函數(shù)值. 例1 F1=, F2=, F1是函數(shù), F2不是函數(shù) 4.6函數(shù)的定義與性質(zhì)第三張

2、，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)與關(guān)系的區(qū)別從A到B的函數(shù)f與一般從A到B的二元關(guān)系R有如下區(qū)別：A的每一元素都必須是f的序偶的第一坐標(biāo)，即dom(f)=A；但dom(R)R若f(x)=y，則函數(shù)f在x處的值是惟一的，即(f(x)=y)(f(x)=z)(y=z)，；但(xRy)(xRz)得不到y(tǒng)=z4.6函數(shù)的定義與性質(zhì)第四張，PPT共三十六頁，創(chuàng)作于2022年6月例1 設(shè)A=1,2,3,4,5，B=6,7,8,9,10，分別確定下列各式中的f是否為由A到B的函數(shù)。(1)f=(1,8),(3,9),(4,10),(2,6),(5,9)(2)f=(1,9),(3,10),(2,6),

3、(4,9)(3)f=(1,7),(2,6),(4,5),(1,9),(5,10),(3,9)解 （1）能構(gòu)成函數(shù)，因?yàn)榉虾瘮?shù)的定義條件。 （2）不能構(gòu)成函數(shù)，因?yàn)锳中的元素5沒有像，不滿足像的存在性。 （3）不能構(gòu)成函數(shù)，因?yàn)锳中的元素1有兩個(gè)像7和9，不滿足像的惟一性。 4.6函數(shù)的定義與性質(zhì)第五張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)相等定義 設(shè)F, G為函數(shù), 則 F = G FGGF 一般使用下面兩個(gè)條件： (1) domF = domG (2) xdomF = domG 都有 F(x) = G(x) 實(shí)例 函數(shù) F(x)=(x21)/(x+1), G(x)=x1不相等, 因?yàn)?/p>

4、 domFdomG. 4.6函數(shù)的定義與性質(zhì)第六張，PPT共三十六頁，創(chuàng)作于2022年6月從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ù) 4.6函數(shù)的定義與性質(zhì)第七張，PPT共三十六頁，創(chuàng)作于2022年6月B上A定義 所有從 A 到 B 的函數(shù)的集合記作 BA, 讀作“B上A”，符號化表示為 BA = f | f：AB 計(jì)數(shù)： |A|=m, |B|=n, 且m, n0, |BA|=nm. A=

5、, 則 BA=B=. A且B=, 則 BA=A= .4.6函數(shù)的定義與性質(zhì)第八張，PPT共三十六頁，創(chuàng)作于2022年6月實(shí)例例2 設(shè) A = 1, 2, 3, B = a, b, 求BA. 解 BA = f0, f1, , f7, 其中 f0=, f1=, f2=,，f3=, f4=,，f5=, f6=, f7=, 4.6函數(shù)的定義與性質(zhì)第九張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)的像定義 設(shè)函數(shù) f：AB, A1A. A1 在 f 下的像： f(A1) = f(x) | xA1 函數(shù)的像 f(A) = ranf 注意： 函數(shù)值 f(x)B, 而像 f(A1)B. 例3 設(shè) f：NN,

6、且 令A(yù)=0,1, B=2, 那么有 f(A) = f(0,1) = f(0), f(1) = 0, 24.6函數(shù)的定義與性質(zhì)第十張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)的性質(zhì)定義 設(shè) f：AB,（1）若ranf = B, 則稱 f：AB是滿射的.（2）若任意x1， x2 A 而且不相等，都有f(x1)與 f(x2)不相等, 則稱 f：AB是單射的.（3）若 f：AB既是滿射又是單射的, 則稱 f： AB是雙射的f 滿射意味著：y B, 都存在 x使得 f(x) = y. f 單射意味著：f(x1) = f(x2) x1= x2 4.6函數(shù)的定義與性質(zhì)第十一張，PPT共三十六頁，創(chuàng)作于2

7、022年6月注意：由單射的定義可知，設(shè)X和Y是有限集合，若存在單射函數(shù)f:XY，則|X|Y|。由滿射的定義可知，設(shè)X和Y是有限集合，若存在滿射函數(shù)f:XY，則|X|Y|。由雙射的定義可知，設(shè)X和Y是有限集合，若存在雙射函數(shù)f:XY，則|X|=|Y|。4.6函數(shù)的定義與性質(zhì)第十二張，PPT共三十六頁，創(chuàng)作于2022年6月實(shí)例例4 判斷下面函數(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+,

8、f(x)=(x2+1)/x, 其中R+為正實(shí)數(shù)集.4.6函數(shù)的定義與性質(zhì)第十三張，PPT共三十六頁，創(chuàng)作于2022年6月解 (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)=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ù)既不單射

9、也不滿射. 實(shí)例（續(xù)）4.6函數(shù)的定義與性質(zhì)第十四張，PPT共三十六頁，創(chuàng)作于2022年6月構(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)=f3, f(1,2)=f4, f(1,3)=f5, f(2,3)=f6, f(1,2,3)=f74.6函數(shù)的定義與性質(zhì)第十五張，PPT共三十六頁，創(chuàng)作于2022

10、年6月實(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 4.6函數(shù)的定義與性質(zhì)第十六張，PPT共三十六頁，創(chuàng)作于2022年6月構(gòu)造從A到B的雙射函數(shù)（續(xù)）A 與自然數(shù)集合之間構(gòu)造雙射方法：將A中元素排成有序圖形，然后從第一個(gè)元素開始 按照次序與自然數(shù)對應(yīng)例7 A=Z, B=N，構(gòu)造雙射 f：AB將Z中元素以下列順序排列并與N中元素對應(yīng)：Z：011 2233 N：0 1 2 3 4 5 6 則這種對應(yīng)所表示的函數(shù)是：4.6函數(shù)的定義與性質(zhì)第十七張，PPT共三十六頁，

11、創(chuàng)作于2022年6月常函數(shù)、恒等函數(shù)、單調(diào)函數(shù) 1. 設(shè)f：AB, 若存在 cB 使得 xA 都有 f(x)=c, 則稱 f：AB是常函數(shù). 2. 稱 A 上的恒等關(guān)系 IA為 A 上的恒等函數(shù), 對所有 的 xA 都有 IA(x)=x. 3. 設(shè) f：RR，如果對任意的 x1, x2R，x1x2, 就 有 f(x1) f(x2), 則稱 f 為單調(diào)遞增的；如果對任意 的 x1, x2A, x1 x2, 就有 f(x1) f(x2), 則稱 f 為 嚴(yán) 格單調(diào)遞增 的. 類似可以定義單調(diào)遞減 和嚴(yán)格單調(diào)遞減 的函數(shù).4.6函數(shù)的定義與性質(zhì)第十八張，PPT共三十六頁，創(chuàng)作于2022年6月集合的特

12、征函數(shù)設(shè) A 為集合, A A, A 的 特征函數(shù) A：A0,1 定義為實(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 4.6函數(shù)的定義與性質(zhì)第十九張，PPT共三十六頁，創(chuàng)作于2022年6月5. 設(shè) R 是 A 上的等價(jià)關(guān)系, 令g：AA/Rg(a) = a, aA稱 g 是從 A 到商集 A/R 的自然映射. 自然映射 4.6函數(shù)的定義與性質(zhì)第二十張，PPT共三十六頁，創(chuàng)作于2022年6月實(shí)例例8 (1) A的每一個(gè)子集A都對應(yīng)于

13、一個(gè)特征函數(shù), 不同的子集對應(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) = 34.6函數(shù)的定義與性質(zhì)第二十一張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)復(fù)合的定理定理 設(shè)F, G是函數(shù), 則F G也是函數(shù), 且滿足 (1) dom( FG)= x | xdomG G(x)domF (2) xdom(F G) 有FG(x) =

14、F (G(x)推論1 設(shè)F, G, H為函數(shù), 則 (FG)H 和 F(GH) 都是函數(shù), 且 (FG)H = F(GH)推論2 設(shè) f： BC, g： AB, 則 fg：AC, 且 xA 都有 fg(x) = f (g(x). 4.7函數(shù)復(fù)合和反函數(shù)第二十二張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)復(fù)合運(yùn)算的性質(zhì)定理 設(shè)g ：AB, f ：BC. (1) 如果f,g都是滿射, 則 fg：AC也是滿射. (2) 如果 g, f 都是單射, 則f g:AC也是單射. (3) 如果 g, f 都是雙射, 則 fg：AC也是雙射.證 (1) cC, 由 f：BC 的滿射性, bB 使得 f(b)

15、=c. 對這個(gè)b, 由 g：AB 的滿射性，aA 使得 f(a)=b. 由合成定理 fg(a)= f ( g(a)=f(b)=c 從而證明了 fg：AC是滿射的. 第二十三張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)復(fù)合運(yùn)算的性質(zhì) (2) 假設(shè)存在 x1, x2A使得 fg(x1) = f g(x2) 由合成定理有 f (g(x1)= f (g(x2). 因?yàn)?f：BC是單射的, 故 g(x1)=g(x2). 又由 于 g：AB也是單射的, 所以 x1=x2. 從而證 明 fg：AC是單射的. (3) 由 (1) 和 (2) 得證.定理 設(shè) f: AB，則 f = fIB = IAf 第二十

16、四張，PPT共三十六頁，創(chuàng)作于2022年6月定理 設(shè)f:XY，g:YZ，那么（1）若gf是單射，則f是單射。（2）若gf是滿射，則g是滿射。（3）若gf是雙射，則f是單射，g是滿射。函數(shù)復(fù)合運(yùn)算的性質(zhì)第二十五張，PPT共三十六頁，創(chuàng)作于2022年6月反函數(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 第二十六張，PPT共三十六

17、頁，創(chuàng)作于2022年6月反函數(shù)定理 設(shè) f：AB是雙射的, 則f 1：BA也是雙射函數(shù).證 因?yàn)?f 是函數(shù), 所以 f 1 是關(guān)系, 且 dom f 1 = ranf = B , ran f 1 = domf = A, 對于任意的 yB = dom f 1, 假設(shè)有x1, x2A使得f 1f 1成立, 則由逆的定義有ff根據(jù) f 的單射性可得 x1 = x2, 從而證明了f 1是函數(shù)，且是滿射的. 下面證明 f 1 的單射性. 若存在 y1, y2B 使得 f 1 (y1) = f 1 (y2) = x, 從而有f 1f 1 ff y1 = y2 第二十七張，PPT共三十六頁，創(chuàng)作于2022

18、年6月反函數(shù)的定義及性質(zhì)對于雙射函數(shù)f：AB, 稱 f 1：BA是它的反函數(shù). 反函數(shù)的性質(zhì)定理 設(shè) f：AB是雙射的, 則f 1f = IA, ff 1 = IB 對于雙射函數(shù) f：AA, 有f 1f = ff 1 = IA 第二十八張，PPT共三十六頁，創(chuàng)作于2022年6月定理 若f:XY是可逆的，那么 （l）(f-1)-1=f （2）f-1f=IX，ff-1=IY定理3.9 設(shè)X,Y,Z是集合，如果f:XY，g:YZ都是可逆的，那么gf也是可逆的，且(gf)-1=f-1g-1 。第二十九張，PPT共三十六頁，創(chuàng)作于2022年6月函數(shù)復(fù)合與反函數(shù)的計(jì)算例 設(shè) f：RR, g：RR 求 f

19、g, g f. 如果 f 和 g 存在反函數(shù), 求出它們的反函數(shù). 解 f：RR不是雙射的, 不存在反函數(shù). g：RR是雙射的, 它的反函數(shù)是 g1：RR, g1(x) = x2 第三十張，PPT共三十六頁，創(chuàng)作于2022年6月一、兩個(gè)有限集如何比較多少。 設(shè)兩個(gè)班級A 和B，要比較這兩個(gè)班級的學(xué)生哪班多，哪班少，可采取兩種方法。方法1：報(bào)數(shù)。報(bào)數(shù)后看誰的數(shù)目大，數(shù)目大的就表示這個(gè)班上學(xué)生人數(shù)多。但這個(gè)方法對無限集卻行不通。方法2：配對。將A 中的一個(gè)學(xué)生a1 和B 中的一個(gè)學(xué)生b1 配成一對，配好以后，不許他們再和別人配對了。然后再把A 中的另一個(gè)學(xué)生a2 和B 中的一個(gè)學(xué)生b2 配成一對，同樣，配好以后也不準(zhǔn)他們再和其他人配對了。這樣一對一配下去，如果A中的人都配完了，而B還剩下一些人，則說B中的學(xué)生比A多；如果B 中的人都配完了，而A 剩下一些人，則說A中的學(xué)生比B多；如果A和B中的學(xué)生正好都能一對一地搭配起來，則說A和B的學(xué)生人數(shù)一樣多。這種“配對”的辦法可以應(yīng)用到無限集中去。第三十一張，PPT共三十六頁，創(chuàng)作于2022年6月定義一 設(shè)A與B為集合，若存在從A到B的雙射，則稱A和B為等勢，記為AB。例6.13 (-1,1)(-,+)。證明 因存在著雙射 ，x(-1,1)，所以(-1,1)(-,+)。 等勢關(guān)系具有如下性質(zhì) AA。 若AB，則BA。