《《離散數(shù)學》二元關系和函數(shù).ppt》由會員分享，可在線閱讀，更多相關《《離散數(shù)學》二元關系和函數(shù).ppt（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、第4章 二元關系和函數(shù),Relation,在高等數(shù)學中，函數(shù)是在實數(shù)集合上進行討論的，其定義域是連續(xù)的。 本章把函數(shù)概念予以推廣 定義域為一般的集合，支持離散應用。 把函數(shù)看作是一種特殊的關系：單值二元關系。,4.6函數(shù)的定義與性質,函數(shù)定義,定義 設 F 為二元關系, 若 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ù)的定義與性質,函數(shù)與關系的區(qū)別,從A到B的函數(shù)f與一般從A到B的二元關系R有如下
2、區(qū)別： A的每一元素都必須是f的序偶的第一坐標，即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ù)的定義與性質,例1 設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）能構成函數(shù)，因為符合函數(shù)的定義條
3、件。 （2）不能構成函數(shù)，因為A中的元素5沒有像，不滿足像的存在性。 （3）不能構成函數(shù)，因為A中的元素1有兩個像7和9，不滿足像的惟一性。,4.6函數(shù)的定義與性質,函數(shù)相等,定義 設F, G為函數(shù), 則 F = G FGGF 一般使用下面兩個條件： (1) domF = domG (2) xdomF = domG 都有 F(x) = G(x) 實例 函數(shù) F(x)=(x21)/(x+1), G(x)=x1 不相等, 因為 domFdomG.,4.6函數(shù)的定義與性質,從A到B的函數(shù),定義 設A, B為集合, 如果 f 為函數(shù) domf = A ranf B, 則稱 f
4、為從A到B的函數(shù), 記作 f：AB. 實例 f：NN, f(x)=2x 是從 N 到 N 的函數(shù) g：NN, g(x)=2也是從 N 到 N 的函數(shù),4.6函數(shù)的定義與性質,B上A,定義 所有從 A 到 B 的函數(shù)的集合記作 BA, 讀作“B上A”，符號化表示為 BA = f | f：AB 計數(shù)： |A|=m, |B|=n, 且m, n0, |BA|=nm. A=, 則 BA=B=. A且B=, 則 BA=A= .,4.6函數(shù)的定義與性質,實例,例2 設 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ù)的定義與性質,函數(shù)的像,,定義 設函數(shù) f：AB, A1A. A1 在 f 下的像： f(A1) = f(x) | xA1 函數(shù)的像 f(A) = ranf 注意： 函數(shù)值 f(x)B, 而像 f(A1)B. 例3 設 f：NN, 且 令A=0,1, B=2, 那么有 f(A) = f(0,1) = f(0), f(1) = 0, 2,4.6函數(shù)的定義與性質,函數(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ù)的定義與性質,注意： 由單射的定義可知，設X和Y是有限集合，若存在單射函數(shù)f:XY，則|X||Y|。 由滿射的定義可知，設X和Y是有限集合，若存在滿射函數(shù)f:XY，則|X||Y|。 由雙射的定義可知，設X和Y是有限集合，若存在雙射函數(shù)f:XY，則|X|=|Y|。,4.6函數(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ù)集.,4.6函數(shù)的定義與性質,解 (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 滿射、單射、雙射, 因為它是單調(diào)的并且ranf=R. (5) f：R+R+, f(x)=(x2+1)/x 有極小值f(1)=2. 該函數(shù)既不單射也不滿射.,實例（續(xù)）,4.6函數(shù)的定義與性質,構造從A到B的雙射函數(shù),有窮集之間的構造 例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ù)的定義與性質,實數(shù)區(qū)間之間構造雙射 構造方法：直線方程 例6 A=0,1 B=1/4,1/2構造雙射 f :AB,構造從A到B的雙射函數(shù)（續(xù)）,解 令 f：0,11/4,1/2 f(x)=(x+1)/4,4.6函數(shù)的定義與性質,構造從A到B的雙射函數(shù)（續(xù)）,A 與自然數(shù)集合之間構造雙射 方法：將A中元素排成有序圖形，然后從第一個元素開始 按照次序與自然數(shù)對應 例7 A=Z, B=N，構造雙射 f：AB 將Z中元素以下列
10、順序排列并與N中元素對應：Z：011 2233 N：0 1 2 3 4 5 6 則這種對應所表示的函數(shù)是：,4.6函數(shù)的定義與性質,常函數(shù)、恒等函數(shù)、單調(diào)函數(shù),1. 設f：AB, 若存在 cB 使得 xA 都有 f(x)=c, 則稱 f：AB是常函數(shù). 2. 稱 A 上的恒等關系 IA為 A 上的恒等函數(shù), 對所有 的 xA 都有 IA(x)=x. 3. 設 f：RR，如果對任意的 x1, x2R，x1
11、 嚴 格單調(diào)遞增 的. 類似可以定義單調(diào)遞減 和嚴格單調(diào)遞減 的函數(shù).,4.6函數(shù)的定義與性質,集合的特征函數(shù),設 A 為集合, A A, A 的 特征函數(shù) A：A0,1 定義為,實例 集合：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ù)的定義與性質,5. 設 R 是 A 上的等價關系, 令g：AA/Rg(a) = a, aA稱 g 是從 A 到商集 A/R 的自然映射
12、.,自然映射,4.6函數(shù)的定義與性質,實例,例8 (1) A的每一個子集A都對應于一個特征函數(shù), 不同的子集對應于不同的特征函數(shù). 例如 A=a, b, c, 則有 = , , ， a,b = , , (2) 給定集合 A， A 上不同的等價關系確定不同的自然映射, 其中恒等關系確定的自然映射是雙射, 其他的自然映射一般來說是滿射. 例如 A=1, 2, 3, R=,IA g(1) = g(2) = 1,2, g(3) = 3,4.6函數(shù)的定義與性質,函數(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 設F, G, H為函數(shù), 則 (FG)H 和 F(GH) 都是函數(shù), 且 (FG)H = F(GH) 推論2 設 f： BC, g： AB, 則 fg：AC, 且 xA 都有 fg(x) = f (g(x)).,4.7函數(shù)復合和反函數(shù),函數(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. 對這個b, 由 g：AB 的滿射性，aA 使得 f(a)=b. 由合成定理 fg(a)= f ( g(a))=f(b)=c 從而證明了 fg：AC是滿射的.,函數(shù)復合運算的性質,(2) 假設存在 x1, x2A使得 fg(x1) = f g(x2) 由合成定理有 f (g(x1))= f (g(x2)). 因為 f：BC是單射的, 故 g(x1)=g(x2). 又由 于 g：AB也是單射的, 所以 x1=x2. 從而證 明 fg：AC是單射的. (3) 由 (1) 和 (2) 得證. 定理 設 f: AB，則 f = fIB = IAf,
15、定理 設f:XY，g:YZ，那么 （1）若gf是單射，則f是單射。 （2）若gf是滿射，則g是滿射。 （3）若gf是雙射，則f是單射，g是滿射。,函數(shù)復合運算的性質,反函數(shù)存在的條件,任給函數(shù) F, 它的逆F 1不一定是函數(shù), 是二元關系. 實例：F=,， F 1=, 任給單射函數(shù) f：AB, 則 f 1是函數(shù), 且是從 ranf 到 A的雙射函數(shù), 但不一定是從 B 到 A 的雙射函數(shù). 實例：f : N N, f(x) = 2x, f 1 : ranf N, f 1 (x) = x/2,反函數(shù),定理 設 f：AB是雙射的, 則f 1：BA也是雙射函數(shù).證 因為 f 是函數(shù), 所以 f
16、 1 是關系, 且 dom f 1 = ranf = B , ran f 1 = domf = A, 對于任意的 yB = dom f 1, 假設有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ù)的定義及性質,對于雙射函數(shù)f：AB, 稱 f 1：BA是它的反 函數(shù). 反函數(shù)的性質 定理 設 f：AB是雙射的, 則f 1f = IA, ff 1 =
17、 IB 對于雙射函數(shù) f：AA, 有f 1f = ff 1 = IA,定理 若f:XY是可逆的，那么 （l）(f-1)-1=f （2）f-1f=IX，ff-1=IY 定理3.9 設X,Y,Z是集合，如果f:XY，g:YZ都是可逆的，那么gf也是可逆的，且(gf)-1=f-1g-1 。,函數(shù)復合與反函數(shù)的計算,,例 設 f：RR, g：RR 求 f g, g f. 如果 f 和 g 存在反函數(shù), 求出它們的反函數(shù).,,解 f：RR不是雙射的, 不存在反函數(shù). g：RR是雙射的, 它 的反函數(shù)是 g1：RR, g1(x) = x2,一、兩個有限集如何比較多少。 設兩個班級A 和B，要比
18、較這兩個班級的學生哪班多，哪班少，可采取兩種方法。 方法1：報數(shù)。報數(shù)后看誰的數(shù)目大，數(shù)目大的就表示這個班上學生人數(shù)多。但這個方法對無限集卻行不通。 方法2：配對。將A 中的一個學生a1 和B 中的一個學生b1 配成一對，配好以后，不許他們再和別人配對了。然后再把A 中的另一個學生a2 和B 中的一個學生b2 配成一對，同樣，配好以后也不準他們再和其他人配對了。這樣一對一配下去，如果A中的人都配完了，而B還剩下一些人，則說B中的學生比A多；如果B 中的人都配完了，而A 剩下一些人，則說A中的學生比B多；如果A和B中的學生正好都能一對一地搭配起來，則說A和B的學生人數(shù)一樣多。這種“配對”的辦法可
19、以應用到無限集中去。,定義一 設A與B為集合，若存在從A到B的雙射，則稱A和B為等勢，記為AB。 例6.13 (-1,1)(-,+)。 證明 因存在著雙射 ，x(-1,1)，所以(-1,1)(-,+)。 等勢關系具有如下性質 AA。 若AB，則BA。 若AB，BC，則AC。 所以等勢關系是等價關系。,定義二 設Nn=0,1,2,,n-1，A 為任一集合。若A=或A 與某個Nn等勢，則稱A為有限集；否則稱A 為無限集。 定理一 自然數(shù)集N為無限集。 證明 任取nN，f 是從Nn 到N 的任意一個函數(shù)。令k=1+maxf(0),f(1),,f(n-1)，則kN。但對每個xNn，都有f
20、(x)k，因此f不是滿射，從而f 不是雙射。由n和f的任意性得知N 是無限的。,定義三 （1）對于有限集合A，有唯一的Nn與其等勢，對應的n稱為A的基數(shù)，記為|A| （2）自然數(shù)集N 的基數(shù)記為0（讀作阿列夫零）。 （3）實數(shù)集R 的基數(shù)記為（讀作阿列夫）。 由定義可知，有限集合的基數(shù)就是其所含元素的個數(shù)。兩個有限集合等勢當且僅當A和B 的元素個數(shù)相同。,定義四 與自然數(shù)集N 等勢的集合叫做可數(shù)集或可列集，其基數(shù)記為0。與自然數(shù)集N不等勢的無限集叫做不可數(shù)集或不可列集。 下面介紹可數(shù)集的一些性質。 定理五 集合A 為可數(shù)集的充要條件是A 的元素可以排列成無限序列的形式（即 A=a0,a1,,an,）。 定理二 任一無限集必含有可數(shù)子集。 定理三 任一無限集必與其某一真子集等勢。 定理四 可數(shù)集的任何無限子集是可數(shù)的。 定理五 兩個可數(shù)集的并集仍是可數(shù)集。,
《離散數(shù)學》二元關系和函數(shù).ppt
