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

1、精選ppt1精選ppt21：由兩個(gè)元素：由兩個(gè)元素x和和y按一定順序按一定順序排成二元組，記作：排成二元組，記作： 。如： 平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)一、二元關(guān)系的概念精選ppt3(1) 當(dāng)x y時(shí)， (2) = ，當(dāng)且僅當(dāng)x = u，y = v(1)、(2)說明有序組區(qū)別于集合n元有序組：由由n個(gè)元素個(gè)元素x1，x2，xn，按按一定順序排成的一定順序排成的n元組，記作：元組，記作：(x1，x2，xn) 。精選ppt42. 一種新的集合運(yùn)算一種新的集合運(yùn)算 積運(yùn)算積運(yùn)算 ： 設(shè)A、B為兩集合，用A中元素為第一元素，B中元素作為第二元素構(gòu)成的二元有序組的全體叫做A和B的笛卡兒積。記作：A B符號(hào)化

2、：A B = | xA y B精選ppt5例例4.1 設(shè)A=a,b，B=0,1,2 ，求A B，B A解：解：根據(jù)笛卡兒積的定義知A B = , , , B A = , , 一般地：如果|A|=m，|B|=n，則 |A B|=|B A|=m n, , , , , 精選ppt6(1) 若A，B中有一個(gè)空集，則笛卡兒積是空集，即： B = A = (2) 當(dāng)AB，且A，B都不是空集時(shí)，有ABBA (3) 當(dāng)A，B，C都不是空集時(shí)，有(A B) C A (B C)因?yàn)?A B)C中的元素 , z，而A (B C)中的元素為 x, 。精選ppt7(4) A (BC) = (A B)(A C) ( 對(duì)的

3、分配律)(BC) A = (B A)(C A)A (BC) = (A B)(A C)(BC) A = (B A)(C A)我們證明：A (BC) = (A B)(A C)( ? )( ? )( ? )精選ppt8 要證明兩個(gè)集合相等，通常有兩種方法：一是證兩個(gè)集合相互包含；二是利用已有的集合運(yùn)算的性質(zhì)(算律和已證明過的公式)，仿照代數(shù)恒等式的證明方法，一步步從左(右)邊推出右(左)邊，或從左、右邊分別推出同一個(gè)集合式子。一般說來，最基本的集合相等關(guān)系要用第一種證法，比較復(fù)雜的集合相等關(guān)系用第二種方法更好，但第二種方法的使用取決于我們對(duì)算律和常用公式的熟練程度。精選ppt9證明：證明： 用第一種

4、方法對(duì)于任意的 A ( BC ) xA y(BC) xA (yB yC ) (xA yB) (xA yC) A B A C (A B)(A C) A (BC)=(A B)(A C)精選ppt10例例4.2 設(shè)A=1,2，求P(A) A解：解： P(A) A= ，1，2，1,2 = ，n階笛卡兒積：= (x1,x2, xn) | x1A1 x2A2 xnAnA1 A2 An1,2， ，精選ppt11二元關(guān)系：二元關(guān)系：如果一個(gè)集合的元素都是二元有如果一個(gè)集合的元素都是二元有序組，則這個(gè)集合稱為一個(gè)二元序組，則這個(gè)集合稱為一個(gè)二元關(guān)系，記作：關(guān)系，記作：R 。如果 R ，記作 x R y如果 R

5、，記作 x R y3、二元關(guān)系的數(shù)學(xué)定義、二元關(guān)系的數(shù)學(xué)定義精選ppt12從從A到到B的二元關(guān)系：的二元關(guān)系：設(shè)設(shè)A，B為集合，為集合，A B的任的任何子集所定義的二元關(guān)系叫做從何子集所定義的二元關(guān)系叫做從A到到B的二元關(guān)系。的二元關(guān)系。若A=B，叫做 A上的二元關(guān)系；若|A|n，則|A A|n2。2n2就是說，A上有 個(gè)不同的二元關(guān)系，其中包括空關(guān)系、全域關(guān)系UA和恒等關(guān)系IA。2n2A A的所有子集有 個(gè)。精選ppt13例例4.3 設(shè)A = a,b，寫出P(A)上的包含關(guān)系R ：解：解： P(A) = ,a,ba,bR = , , , , , 精選ppt141. 關(guān)系矩陣：設(shè)A=x1, x

6、2, , xn)，R是A上的關(guān)系，rij =1 若xi R xj0 若xi R xj(i, j = 1,2, n)則 (rij)nxn =是R的關(guān)系矩陣令：nnnnnnrrrrrrrrr212222111211二、二元關(guān)系的表示方法精選ppt152. 關(guān)系圖：以E = | xiA xjA xiRxj為有向邊集組成的有向圖G = 以V=A=x1, x2, xn 為頂點(diǎn)集，精選ppt16例例4.4 設(shè)A=1,2,3,4，R=,是A上的關(guān)系，試寫出R的關(guān)系矩陣并畫出關(guān)系圖：解：解： 關(guān)系矩陣 ：0 0 1 10 0 0 00 1 0 01 1 0 0關(guān)系圖 ：134 2精選ppt17關(guān)系關(guān)系R的定義

7、域：的定義域： domR = x | ( y) R (即即R中有序組的第一個(gè)元中有序組的第一個(gè)元素構(gòu)成的集合素構(gòu)成的集合)關(guān)系關(guān)系R的值域：的值域： ranR =y | ( x) R (即即R中有序組的第二個(gè)元中有序組的第二個(gè)元素構(gòu)成的集合素構(gòu)成的集合)一、關(guān)系的定義域與值域精選ppt18例例4.5 下列關(guān)系都是整數(shù)集Z上的關(guān)系，分別求出它們的定義域和值域：(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 精選ppt19解：解： domR1 = ranR1

8、= Z解：解： R2 = , , domR2 = ( ? )ranR2 = ( ? )(1) R1= | x, y Z xy (2) R2= | x, y Z x2+y2=1 , 精選ppt20解：解： domR3 = Z， ranR3 = 偶數(shù) 解：解： domR4 = ranR4 = ( ? )(3) R3= | x, y Z y=2x (4) R4= | x, y Z |x|=|y|=3 精選ppt21二、關(guān)系的常用運(yùn)算F是任意關(guān)系，F(xiàn)的逆F1= | yFx F、G是任意兩個(gè)關(guān)系，F(xiàn)與G的合成記作：F G= | (z)(xGz zFy)關(guān)系F在集A上的限制，記作：F | A= | xFy

9、 xA集A在關(guān)系F下的象FA = ran(F | A)(1) 逆：(2) 合成：(3) 限制：(4) 象：精選ppt22例例4.6 設(shè)F，G是N上的關(guān)系，其定義為：F = | x, yN y = x2G = | x,yN y = x+1求 G1，F(xiàn) G，G F，F(xiàn) |1,2，F(xiàn)1,2解：解：由定義知：G1 = | y, xN y = x+1列出G1 中的元素就是G1 = ,精選ppt23為了求F G，可以先直觀表示如下：對(duì)任何xNx x+1=G即 y = (x+1)2因此 F G = | x,yN y = (x+1)2 同理可求 G F = | (?) (自己做！)發(fā)現(xiàn) F G G FF |1

10、,2 = ,F 1,2 = ran(F |1,2) = 1,4F Z Z2 = y精選ppt24關(guān)系運(yùn)算的性質(zhì)：關(guān)系運(yùn)算的性質(zhì)：設(shè)F、G、H、為任意關(guān)系，則有：(1) (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 ( 對(duì)的分配律)(6) F (GH) F GF H ( 對(duì)的半分配律)(7) (GH) F = G FH F(8) (GH) F G FH F( ? )( ? )精選ppt25任取 (F G)1 F G (z)( G F) (z)( G1

11、 F1) G1 F1(4) (F G)1 = G1 F1的證明：精選ppt26任取F (GH) (z)(GH)F) (z)(GH) F) (注意對(duì)括號(hào)的順序) (z)(G F(H F) F GF H F (GH) = F GF H(5) F (GH) = F GF H的證明：精選ppt27R的關(guān)系矩陣：主對(duì)角線元素全是1R的關(guān)系圖：每個(gè)頂點(diǎn)都有環(huán)自反性： x A 有R (R是A上的關(guān)系) 關(guān)系矩陣：主對(duì)角線元素全是0關(guān)系圖： 每個(gè)頂點(diǎn)都沒有環(huán)反自反性：x A R精選ppt28對(duì)稱性：若 R，則 R 關(guān)系矩陣：對(duì)稱陣關(guān) 系 圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊。精選ppt29反對(duì)稱性

12、：反對(duì)稱性：若 R且xy，則 R 關(guān)系矩陣：如果rij = 1，且 i j，則rji = 0 關(guān)系圖： 如果兩個(gè)頂點(diǎn)之間有邊，一定是只有一條有向邊。精選ppt30傳遞性：傳遞性：若 R且 R，則 R 關(guān)系圖：如果頂點(diǎn)xi到xj有邊， xj到xk有邊，則從xi到xk有邊精選ppt31例例4.7 設(shè)A=1,2,10，對(duì)于A上的關(guān)系R= | (xy)/3II為整數(shù)集，問R有哪些性質(zhì)？精選ppt32解：解：逐條性質(zhì)加以驗(yàn)證R= | (xy)/3I 任取A中元素x，由于(xx)/3=0，所以R是自反的自反的；又設(shè)A中任意兩個(gè)元素x,y，如果 xRy，即xy可被3整除，則yx也一定可被3整除，即yRx，從

13、而R是對(duì)稱的對(duì)稱的；如果A中三 個(gè)元素x，y，z滿足xRy， yRz，則x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，從而xRz即R具有傳遞性傳遞性。 精選ppt33閉包：設(shè)RAA，自反閉包 記作 r(R)對(duì)稱閉包 記作 s(R)傳遞閉包 記作 t(R)由A求r(R)，s(R)，t(R)的過程叫閉包運(yùn)算。那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱之為R的自反閉包自反閉包；包含R而使之具有對(duì)稱性質(zhì)(傳遞性質(zhì))的最小關(guān)系，稱之為R的對(duì)稱(傳遞傳遞)閉包閉包。一、定義精選ppt34冪運(yùn)算：設(shè)RAA，kN，約定(1) R0 = IA = | xA(2) R1 = R(3) R

14、k+1 = Rk R顯然 Rm Rn = Rm+n (Rm)n = Rmn二、計(jì)算方法為了有效地計(jì)算關(guān)系R的各種閉包，先引進(jìn)關(guān)系的冪運(yùn)算概念。精選ppt35閉包運(yùn)算的方法：閉包運(yùn)算的方法：設(shè)R是A上的任一關(guān)系，則(1) r (R) = RIA(2) s (R) = RR(3) t (R) = RR2R3 Rn精選ppt36矩陣形式矩陣形式：(M為R的關(guān)系矩陣)(1) Mr = M + E(2) Ms = M + M (M 是M的轉(zhuǎn)置)(3) Mt = M+M2+M3其中“ +” 均表示“ 邏輯加”精選ppt37例例4.8 設(shè)A=a,b,c,d，A上的關(guān)系求 r (R)，s (R) 和 t (R

15、)解：解： r(R) = RIA=, , , , , , R=, = R,三、實(shí)例精選ppt38s(R) = RR=,t(R) = RR2R3= R,精選ppt39而R2 = R RR3 = R2 RR4 = R3 R= ,= ,= , , , 實(shí)際上，看到當(dāng)k 4時(shí)，已有R4 RR2R3故 t(R) = RR2R3=, ,精選ppt40四、閉包運(yùn)算的性質(zhì)設(shè)A是有限集且|A| = n，R A A，則：ikiRRtnk1)()1(，使有)()()2(RsrRrs)()()3(RtrRrt)( )()4(RtsRst 精選ppt41等價(jià)關(guān)系：集A上的關(guān)系R是自反的, 對(duì)稱的和傳遞的。等價(jià)類： R是

16、集A上的等價(jià)關(guān)系，對(duì)于任一aA，aR=x | aRx, xA被稱為a的等價(jià)類。即A中所有和a有R關(guān)系的元素的集合。一、等價(jià)關(guān)系及用途精選ppt42等價(jià)類的性質(zhì)：等價(jià)類的性質(zhì)：R是非空集合，對(duì)任意的x，yA，下面的結(jié)論成立：(1) x且x A (等價(jià)類為A的子集)(2) 若xRy，則x = y(3) 若xRy，則xy = AxAx)4(精選ppt43集A在等價(jià)關(guān)系R下的商集：設(shè)R為非空集A上的等價(jià)關(guān)系，以R的不交的等價(jià)類為元素的集合叫做A在R下的商集，記作A/R.即：A/R = xR | x A精選ppt44集A的劃分：設(shè)A是非空集合，(1) (2) 中任意兩個(gè)元素不交 (3) 中所有元素的并集

17、為A則 為A的劃分。如果存在一個(gè)A的子集族， P(A)滿足以下條件：精選ppt45 由等價(jià)類的性質(zhì)和商集的定義可知，商集A/R是A的劃分，稱之為由R誘導(dǎo)的劃分。反過來，給定A的任一劃分 ，則A被分割成若干個(gè)劃分塊。 若定義A上的二元關(guān)系R：x，yA且x,y屬 的同一塊，則xRy，那么R是A上的等價(jià)關(guān)系，稱之為由 誘導(dǎo)的等價(jià)關(guān)系。集A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的。精選ppt46例例4.9 設(shè)A=1,2,3，求出A上所有的等價(jià)關(guān)系：解：解：先求A的各種劃分：只有1個(gè)劃分塊的劃分1，具有兩個(gè)劃分塊的劃分2， 3，和4，具有3個(gè)劃分塊5。1 = A2 = 1,2,3，4 = 3,1,2，3 = 2,

18、1,3，5 = 1,2,3精選ppt47設(shè)對(duì)應(yīng)于劃分i 的等價(jià)關(guān)系 Ri，i = 1,2,5，則有R5 = ，R1 = ，R2 = ，R3 = ，R4 = ，精選ppt48偏序關(guān)系：偏序關(guān)系：集集A上的關(guān)系上的關(guān)系R是自反的，反對(duì)是自反的，反對(duì)稱的和傳遞的，記作稱的和傳遞的，記作“ ”，且，且稱稱A, )為偏序集。為偏序集。二、偏序關(guān)系及用途精選ppt49例例4.10 設(shè)A=2,4,6,8，A上關(guān)系R是通常意義下的小于或等于關(guān)系，試寫出R并驗(yàn)證它是偏序關(guān)系。解：解：R=, , , , (1)自反性：(2)反對(duì)稱性：(3)傳遞性：, , , , ,均屬于R對(duì)任意的R， 必有xy，當(dāng)xy時(shí)， yx

19、，從而R對(duì)任意的R， R,由于 xy yz ，所以xz，從而R。精選ppt50例例4.11 設(shè)C=a,b,a,b,，C上關(guān)系T是集合的“ 包含于”，試寫出T，并驗(yàn)證它是偏序關(guān)系。解：解： 同例4.10類似，自己做！精選ppt51(1) 用小圓圈表示偏序集的元素 (稱為結(jié)點(diǎn))；(2) 按每個(gè)元素在偏序中的次序從底向上列結(jié)點(diǎn)位置；(3) 對(duì)于偏序集中任意兩個(gè)元素x和y，如果xy且不存在另一個(gè)元素a，使xa ay，則在x與y兩結(jié)點(diǎn)之間劃上一杠，即“ | ” (x在下，y在上)精選ppt52全序關(guān)系：設(shè)是偏序集，(x)(y)(xA yA (xy yx)成立，則稱A,)為全序集，這時(shí)的偏序關(guān)系叫全序關(guān)系。全序集A,)中全部元素可以排序，它的哈斯圖為一條直線。如果精選ppt53設(shè)是偏序集，B A(1) 如果yB，使得(x)(xByx)為真，則y是B的最小元 (“ 小于” B中所有元 )(2) 如果yB，使得(x)(xB xy)為真，則y是B的最大元 (“ 大于” B中所有元 )精選ppt54(4) 若yB，使得 (x)(xB xy)，則稱y是B的極大元 (B中沒有比y大的其他元)(5) 若yA，使得(x)(xB xy)為真，則稱y是B的上界(3) 若yB，使得 (x)