《離散數(shù)學(xué)》二元關(guān)系和函數(shù).ppt

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

1、第4章 二元關(guān)系和函數(shù),Relation,在高等數(shù)學(xué)中，函數(shù)是在實(shí)數(shù)集合上進(jìn)行討論的，其定義域是連續(xù)的。 本章把函數(shù)概念予以推廣 定義域?yàn)橐话愕募希С蛛x散應(yīng)用。 把函數(shù)看作是一種特殊的關(guān)系：單值二元關(guān)系。,4.6函數(shù)的定義與性質(zhì),函數(shù)定義,定義 設(shè) F 為二元關(guān)系, 若 xdomF 都存在唯一的yranF 使 xFy 成立, 則稱 F 為函數(shù). 對(duì)于函數(shù)F, 如果有 xFy, 則記作 y=F(x), 并稱 y 為 F 在 x 的函數(shù)值. 例1 F1=,, F2=, F1是函數(shù), F2不是函數(shù) ,4.6函數(shù)的定義與性質(zhì),函數(shù)與關(guān)系的區(qū)別,從A到B的函數(shù)f與一般從A到B的二元關(guān)系R有如下

2、區(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)=z,4.6函數(shù)的定義與性質(zhì),例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),(4,9) (3)f=(1,7),(2,6),(4,5),(1,9),(5,10),(3,9) 解 （1）能構(gòu)成函數(shù)，因?yàn)榉虾瘮?shù)的定義條

3、件。 （2）不能構(gòu)成函數(shù)，因?yàn)锳中的元素5沒有像，不滿足像的存在性。 （3）不能構(gòu)成函數(shù)，因?yàn)锳中的元素1有兩個(gè)像7和9，不滿足像的惟一性。,4.6函數(shù)的定義與性質(zhì),函數(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)?domFdomG.,4.6函數(shù)的定義與性質(zhì),從A到B的函數(shù),定義 設(shè)A, B為集合, 如果 f 為函數(shù) domf = A ranf B, 則稱 f

4、為從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ì),B上A,定義 所有從 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= .,4.6函數(shù)的定義與性質(zhì),實(shí)例,例2 設(shè) A = 1, 2, 3, B = a, b, 求BA. 解 BA = f0, f1, , f7, 其中 f0=,,, f

5、1=,, f2=,,，f3=,, f4=,,，f5=,, f6=,,, f7=,, ,4.6函數(shù)的定義與性質(zhì),函數(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, 且 令A(yù)=0,1, B=2, 那么有 f(A) = f(0,1) = f(0), f(1) = 0, 2,4.6函數(shù)的定義與性質(zhì),函數(shù)的性質(zhì),定義 設(shè) f：AB,（1）若ranf = B, 則稱 f：AB是滿射的.（2）若任意x1， x2 A 而且不相等，都

6、有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ì),注意： 由單射的定義可知，設(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ì),實(shí)例,例4 判斷下面函數(shù)是否為單射, 滿射,

7、雙射的, 為什么? (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ù)集.,4.6函數(shù)的定義與性質(zhì),解 (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)=

8、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ù)既不單射也不滿射.,實(shí)例（續(xù)）,4.6函數(shù)的定義與性質(zhì),構(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()=

9、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,4.6函數(shù)的定義與性質(zhì),實(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ì),構(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中元素以下列

10、順序排列并與N中元素對(duì)應(yīng)：Z：011 2233 N：0 1 2 3 4 5 6 則這種對(duì)應(yīng)所表示的函數(shù)是：,4.6函數(shù)的定義與性質(zhì),常函數(shù)、恒等函數(shù)、單調(diào)函數(shù),1. 設(shè)f：AB, 若存在 cB 使得 xA 都有 f(x)=c, 則稱 f：AB是常函數(shù). 2. 稱 A 上的恒等關(guān)系 IA為 A 上的恒等函數(shù), 對(duì)所有 的 xA 都有 IA(x)=x. 3. 設(shè) f：RR，如果對(duì)任意的 x1, x2R，x1

11、 嚴(yán) 格單調(diào)遞增 的. 類似可以定義單調(diào)遞減 和嚴(yán)格單調(diào)遞減 的函數(shù).,4.6函數(shù)的定義與性質(zhì),集合的特征函數(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ì),5. 設(shè) R 是 A 上的等價(jià)關(guān)系, 令g：AA/Rg(a) = a, aA稱 g 是從 A 到商集 A/R 的自然映射

12、.,自然映射,4.6函數(shù)的定義與性質(zhì),實(shí)例,例8 (1) A的每一個(gè)子集A都對(duì)應(yīng)于一個(gè)特征函數(shù), 不同的子集對(duì)應(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,4.6函數(shù)的定義與性質(zhì),函數(shù)復(fù)合的定理,定理 設(shè)F, G是函數(shù), 則F G也是函數(shù), 且滿足 (1) dom( FG)= x | xdomG G(x)d

13、omF (2) xdom(F G) 有FG(x) = 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ù),函數(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 的

14、滿射性, bB 使得 f(b)=c. 對(duì)這個(gè)b, 由 g：AB 的滿射性，aA 使得 f(a)=b. 由合成定理 fg(a)= f ( g(a))=f(b)=c 從而證明了 fg：AC是滿射的.,函數(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,

15、定理 設(shè)f:XY，g:YZ，那么 （1）若gf是單射，則f是單射。 （2）若gf是滿射，則g是滿射。 （3）若gf是雙射，則f是單射，g是滿射。,函數(shù)復(fù)合運(yùn)算的性質(zhì),反函數(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,反函數(shù),定理 設(shè) f：AB是雙射的, 則f 1：BA也是雙射函數(shù).證 因?yàn)?f 是函數(shù), 所以 f

16、 1 是關(guān)系, 且 dom f 1 = ranf = B , ran f 1 = domf = A, 對(duì)于任意的 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 ,反函數(shù)的定義及性質(zhì),對(duì)于雙射函數(shù)f：AB, 稱 f 1：BA是它的反 函數(shù). 反函數(shù)的性質(zhì) 定理 設(shè) f：AB是雙射的, 則f 1f = IA, ff 1 =

17、 IB 對(duì)于雙射函數(shù) f：AA, 有f 1f = ff 1 = IA,定理 若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 。,函數(shù)復(fù)合與反函數(shù)的計(jì)算,,例 設(shè) f：RR, g：RR 求 f g, g f. 如果 f 和 g 存在反函數(shù), 求出它們的反函數(shù).,,解 f：RR不是雙射的, 不存在反函數(shù). g：RR是雙射的, 它 的反函數(shù)是 g1：RR, g1(x) = x2,一、兩個(gè)有限集如何比較多少。 設(shè)兩個(gè)班級(jí)A 和B，要比

18、較這兩個(gè)班級(jí)的學(xué)生哪班多，哪班少，可采取兩種方法。 方法1：報(bào)數(shù)。報(bào)數(shù)后看誰的數(shù)目大，數(shù)目大的就表示這個(gè)班上學(xué)生人數(shù)多。但這個(gè)方法對(duì)無限集卻行不通。 方法2：配對(duì)。將A 中的一個(gè)學(xué)生a1 和B 中的一個(gè)學(xué)生b1 配成一對(duì)，配好以后，不許他們?cè)俸蛣e人配對(duì)了。然后再把A 中的另一個(gè)學(xué)生a2 和B 中的一個(gè)學(xué)生b2 配成一對(duì)，同樣，配好以后也不準(zhǔn)他們?cè)俸推渌伺鋵?duì)了。這樣一對(duì)一配下去，如果A中的人都配完了，而B還剩下一些人，則說B中的學(xué)生比A多；如果B 中的人都配完了，而A 剩下一些人，則說A中的學(xué)生比B多；如果A和B中的學(xué)生正好都能一對(duì)一地搭配起來，則說A和B的學(xué)生人數(shù)一樣多。這種“配對(duì)”的辦法可

19、以應(yīng)用到無限集中去。,定義一 設(shè)A與B為集合，若存在從A到B的雙射，則稱A和B為等勢，記為AB。 例6.13 (-1,1)(-,+)。 證明 因存在著雙射 ，x(-1,1)，所以(-1,1)(-,+)。 等勢關(guān)系具有如下性質(zhì) AA。 若AB，則BA。 若AB，BC，則AC。 所以等勢關(guān)系是等價(jià)關(guān)系。,定義二 設(shè)Nn=0,1,2,,n-1，A 為任一集合。若A=或A 與某個(gè)Nn等勢，則稱A為有限集；否則稱A 為無限集。 定理一 自然數(shù)集N為無限集。 證明 任取nN，f 是從Nn 到N 的任意一個(gè)函數(shù)。令k=1+maxf(0),f(1),,f(n-1)，則kN。但對(duì)每個(gè)xNn，都有f

20、(x)k，因此f不是滿射，從而f 不是雙射。由n和f的任意性得知N 是無限的。,定義三 （1）對(duì)于有限集合A，有唯一的Nn與其等勢，對(duì)應(yīng)的n稱為A的基數(shù)，記為|A| （2）自然數(shù)集N 的基數(shù)記為0（讀作阿列夫零）。 （3）實(shí)數(shù)集R 的基數(shù)記為（讀作阿列夫）。 由定義可知，有限集合的基數(shù)就是其所含元素的個(gè)數(shù)。兩個(gè)有限集合等勢當(dāng)且僅當(dāng)A和B 的元素個(gè)數(shù)相同。,定義四 與自然數(shù)集N 等勢的集合叫做可數(shù)集或可列集，其基數(shù)記為0。與自然數(shù)集N不等勢的無限集叫做不可數(shù)集或不可列集。 下面介紹可數(shù)集的一些性質(zhì)。 定理五 集合A 為可數(shù)集的充要條件是A 的元素可以排列成無限序列的形式（即 A=a0,a1,,an,）。 定理二 任一無限集必含有可數(shù)子集。 定理三 任一無限集必與其某一真子集等勢。 定理四 可數(shù)集的任何無限子集是可數(shù)的。 定理五 兩個(gè)可數(shù)集的并集仍是可數(shù)集。,