離散數(shù)學,二元關系與運算.ppt

1、二元關系和運算,第四章,1. 二元有序組：由兩個元素x和y按一定順序排成二元組，記作： 。,4.1 二元關系的概念,如： 平面直角坐標系中點的坐標,一、二元關系的概念,二元有序組的性質(zhì),(1) 當x y時， ,(2) = ，當且僅當x = u，y = v,(1)、(2)說明有序組區(qū)別于集合,n元有序組：由n個元素x1，x2，xn，按一定順序排成的n元組，記作：(x1，x2，xn) 。,2. 一種新的集合運算 積運算 ：,設A、B為兩集合，用A中元素為第一元素，B中元素作為第二元素構(gòu)成的二元有序組的全體叫做A和B的笛卡兒積。,記作：A B,符號化：A B = | xA y B,例4.1 設A=a

2、,b，B=0,1,2 ，求AB，BA,解：根據(jù)笛卡兒積的定義知,A B = , , , ,B A = , , ,一般地：如果|A|=m，|B|=n，則 |AB|=|BA|=m n, , , , ,積運算的性質(zhì),(1) 若A，B中有一個空集，則笛卡兒積是空集，即： B = A = ,(2) 當AB，且A，B都不是空集時，有ABBA,(3) 當A，B，C都不是空集時，有(AB)C A(BC),因為(AB)C中的元素, z，而A(BC)中的元素為 。,(4) A(BC) = (AB)(AC) (對的分配律),(BC)A = (BA)(CA),A(BC) = (AB)(AC),(BC)A = (BA)

3、(C A),我們證明：,A(BC) = (AB)(AC),( ? ),( ? ),( ? ),證明思想,要證明兩個集合相等，通常有兩種方法：一是證兩個集合相互包含；,二是利用已有的集合運算的性質(zhì)(算律和已證明過的公式)，仿照代數(shù)恒等式的證明方法，一步步從左(右)邊推出右(左)邊，或從左、右邊分別推出同一個集合式子。,一般說來，最基本的集合相等關系要用第一種證法，比較復雜的集合相等關系用第二種方法更好，但第二種方法的使用取決于我們對算律和常用公式的熟練程度。,證明： 用第一種方法,對于任意的 A ( BC ), xAy(BC), xA(yByC ), (xAyB)(xAyC), ABAC, (A

4、B)(AC), A(BC)=(AB)(AC),例4.2 設A=1,2，求P(A)A,解： P(A)A,= ，1，2，1,2,= ，,n階笛卡兒積：,= (x1,x2, xn) | x1A1x2A2 xnAn,A1 A2 An,1,2,，,，,，,二元關系：如果一個集合的元素都是二元有序組，則這個集合稱為一個二元關系，記作：R 。,如果 R ，記作 x R y,3、二元關系的數(shù)學定義,從A到B的二元關系：設A，B為集合，A B的任何子集所定義的二元關系叫做從A到B的二元關系。,若A=B，叫做 A上的二元關系；,若|A|n，則|AA|n2。,就是說，A上有 個不同的二元關系，其中包括空關系、全域關

5、系UA和恒等關系IA。,AA的所有子集有 個。,例4.3 設A = a,b，寫出P(A)上的包含關系R ：,解： P(A) = ,a,ba,b,R = , , , ,A上關系的表示法,1. 關系矩陣：,設A=x1, x2, , xn)，R是A上的關系，,則 (rij)nxn =,是R的關系矩陣,令：,二、二元關系的表示方法,2. 關系圖：,以E = | xiAxjAxiRxj為有向邊集組成的有向圖G = ,以V=A=x1, x2, xn 為頂點集，,例4.4 設A=1,2,3,4，R=,是A上的關系，試寫出R的關系矩陣并畫出關系圖：,解： 關系矩陣 ：,0 0 1 1,0 0 0 0,0 1

6、0 0,關系圖 ：,4.2 關系的運算,關系R的定義域： domR = x | (y)R (即R中有序組的第一個元素構(gòu)成的集合),關系R的值域： ranR =y | (x)R (即R中有序組的第二個元素構(gòu)成的集合),一、關系的定義域與值域,例4.5 下列關系都是整數(shù)集Z上的關系，分別求出它們的定義域和值域：,(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1,(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,解： domR1 = ranR1 = Z,解： R2 = , ,domR2 = ( ? ),ranR2

7、 = ( ? ),(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1, ,解： domR3 = Z， ranR3 = 偶數(shù),解： domR4 = ranR4 = ( ? ),(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,二、關系的常用運算,F是任意關系，F(xiàn)的逆F1= | yFx,F、G是任意兩個關系，F(xiàn)與G的合成記作：F G= | (z)(xGzzFy),關系F在集A上的限制，記作：F | A= | xFyxA,集A在關系F下的象FA = ran(F | A),(1) 逆：,(2) 合成：,(3) 限制：

8、,(4) 象：,例4.6 設F，G是N上的關系，其定義為：,F = | x, yNy = x2,G = | x,yNy = x+1,求 G1，F(xiàn) G，G F，F(xiàn) |1,2，F(xiàn)1,2,解：由定義知：,G1 = | y, xNy = x+1,列出G1 中的元素就是,G1 = ,為了求F G，可以先直觀表示如下：,對任何xN,即 y = (x+1)2,因此 F G = | x,yNy = (x+1)2,同理可求 G F = | (?) (自己做！),發(fā)現(xiàn) F G G F,F |1,2 = ,F 1,2 = ran(F |1,2) = 1,4,關系運算的性質(zhì)：設F、G、H、為任意關系，則有：,(1)

9、(F1)1 = F,(2) domF1 = ranF，ranF1 = domF,(3) (F G) H = F (G H),(4) (F G)1 = G1 F1,(5) F (GH) = F GF H (對的分配律),(6) F (GH) F GF H (對的半分配律),(7) (GH) F = G FH F,(8) (GH) F G FH F,( ? ),( ? ),任取, (F G)1, F G, (z)( G F), (z)( G1 F1), G1 F1,(4) (F G)1 = G1 F1的證明：,任取,F (GH), (z)(GH)F), (z)(GH)F) (注意對括號的順序),

10、(z)(GF(HF), F GF H, F (GH) = F GF H,(5) F (GH) = F GF H的證明：,4.3 關系的性質(zhì),R的關系矩陣：主對角線元素全是1,R的關系圖：每個頂點都有環(huán),自反性： x A 有R (R是A上的關系),關系矩陣：主對角線元素全是0,關系圖： 每個頂點都沒有環(huán),反自反性：x A R,對稱性：若 R，則 R,關系矩陣：對稱陣,關 系 圖：如果兩個頂點之間有邊，一定是一對方向相反的邊。,反對稱性：若 R且xy，則 R,關系矩陣：如果rij = 1，且 i j，則rji = 0,關系圖： 如果兩個頂點之間有邊，一定是只有一條有向邊。,傳遞性：若 R且 R，則

11、 R,關系圖：如果頂點xi到xj有邊， xj到xk有邊，則從xi到xk有邊,例4.7 設A=1,2,10，對于A上的關系R= | (xy)/3I,I為整數(shù)集，問R有哪些性質(zhì)？,解：逐條性質(zhì)加以驗證R= | (xy)/3I,任取A中元素x，由于(xx)/3=0，所以R是自反的；,又設A中任意兩個元素x,y，如果 xRy，即xy可被3整除，則yx也一定可被3整除，即yRx，從而R是對稱的；,如果A中三 個元素x，y，z滿足xRy， yRz，則x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，從而xRz即R具有傳遞性。,4.4 關系的閉包運算,閉包：設RAA，,自反閉包 記作 r

12、(R),對稱閉包 記作 s(R),傳遞閉包 記作 t(R),由A求r(R)，s(R)，t(R)的過程叫閉包運算。,那么，包含R而使之具有自反性質(zhì)的最小關系，稱之為R的自反閉包；,包含R而使之具有對稱性質(zhì)(傳遞性質(zhì))的最小關系，稱之為R的對稱(傳遞)閉包。,一、定義,冪運算：設RAA，kN，約定,(1) R0 = IA = | xA,(2) R1 = R,(3) Rk+1 = Rk R,顯然 Rm Rn = Rm+n (Rm)n = Rmn,二、計算方法,為了有效地計算關系R的各種閉包，先引進關系的冪運算概念。,閉包運算的方法：設R是A上的任一關系，則,(1) r (R) = RIA,(2) s

13、 (R) = RR,(3) t (R) = RR2R3 Rn,矩陣形式：(M為R的關系矩陣),(1) Mr = M + E,(2) Ms = M + M (M 是M的轉(zhuǎn)置),(3) Mt = M+M2+M3,其中“ +” 均表示“ 邏輯加”,例4.8 設A=a,b,c,d，A上的關系,求 r (R)，s (R) 和 t (R),解： r(R) = RIA,=, , , , , , ,R=, ,= R,三、實例,s(R) = RR,=,t(R) = RR2R3,= R,而R2 = R R,R3 = R2 R,R4 = R3 R,= ,= ,= , , , ,實際上，看到當k 4時，已有R4 RR

14、2R3,故 t(R) = RR2R3,=, ,四、閉包運算的性質(zhì),設A是有限集且|A| = n，RAA，則：,4.6 等價關系和偏序關系,等價關系：集A上的關系R是自反的, 對稱的和傳遞的。,等價類： R是集A上的等價關系，對于任一aA，,aR=x | aRx, xA,被稱為a的等價類。,即A中所有和a有R關系的元素的集合。,一、等價關系及用途,等價類的性質(zhì)：R是非空集合，對任意的x，yA，下面的結(jié)論成立：,(1) x且xA (等價類為A的子集),(2) 若xRy，則x = y,(3) 若xRy，則xy = ,集A在等價關系R下的商集：設R為非空集A上的等價關系，以R的不交的等價類為元素的集合

15、叫做A在R下的商集，記作A/R.,即：,A/R = xR | xA,集A的劃分：設A是非空集合，,(1) ,(2) 中任意兩個元素不交,(3) 中所有元素的并集為A,則 為A的劃分。,如果存在一個A的子集族， P(A)滿足以下條件：,由等價類的性質(zhì)和商集的定義可知，商集A/R是A的劃分，稱之為由R誘導的劃分。,反過來，給定A的任一劃分 ，則A被分割成若干個劃分塊。,若定義A上的二元關系R：x，yA且x,y屬 的同一塊，則xRy，那么R是A上的等價關系，稱之為由 誘導的等價關系。,集A上的等價關系與劃分是一一對應的。,例4.9 設A=1,2,3，求出A上所有的等價關系：,解：先求A的各種劃分：只

16、有1個劃分塊的劃分1，具有兩個劃分塊的劃分2， 3，和4，具有3個劃分塊5。,1 = A,2 = 1,2,3，,4 = 3,1,2，,3 = 2,1,3，,5 = 1,2,3,設對應于劃分i 的等價關系 Ri，i = 1,2,5，則有,R5 = ，,R1 = ，,R2 = ，,R3 = ，,R4 = ，,，,，,，,，,，,，,，,，,偏序關系：集A上的關系R是自反的，反對稱的和傳遞的，記作“ ”，且稱A, )為偏序集。,二、偏序關系及用途,例4.10 設A=2,4,6,8，A上關系R是通常意義下的小于或等于關系，試寫出R并驗證它是偏序關系。,解：R=, , , ,(1)自反性：,(2)反對稱

17、性：,(3)傳遞性：, , , ,均屬于R,對任意的R， 必有xy，當xy時， yx，從而R,對任意的R， R,由于 xyyz ，所以xz，從而R。,例4.11 設C=a,b,a,b,，C上關系T是集合的“ 包含于”，試寫出T，并驗證它是偏序關系。,解： 同例4.10類似，自己做！,偏序集的哈斯圖,(1) 用小圓圈表示偏序集的元素 (稱為結(jié)點)；,(2) 按每個元素在偏序中的次序從底向上列結(jié)點位置；,(3) 對于偏序集中任意兩個元素x和y，如果xy且不存在另一個元素a，使xaay，則在x與y兩結(jié)點之間劃上一杠，即“ | ” (x在下，y在上),全序關系：設是偏序集，,(x)(y)(xAyA(x

18、yyx),成立，則稱A,)為全序集，這時的偏序關系叫全序關系。,全序集A,)中全部元素可以排序，它的哈斯圖為一條直線。,如果,偏序集中的一些特殊元素,設是偏序集，BA,(1) 如果yB，使得(x)(xByx)為真，則y是B的最小元 (“ 小于” B中所有元 ),(2) 如果yB，使得(x)(xB xy)為真，則y是B的最大元 (“ 大于” B中所有元 ),(4) 若yB，使得 (x)(xBxy)，則稱y是B的極大元 (B中沒有比y大的其他元),(5) 若yA，使得(x)(xB xy)為真，則稱y是B的上界,(3) 若yB，使得 (x)(xBxy)，則稱y是B的極小元 (B中找不到x小于y ),(6) 若yA，使得(x)(xB yx)為真，則稱y是B