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

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

2、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, , , , , (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, 。(4) A (BC) = (A B)(A C) ( 對(duì)的分配律)(BC) A = (B A)(C A)A (BC) = (A B)(A C)

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

4、A B A C (A B)(A C) A (BC)=(A B)(A C)例例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， ，二元關(guān)系：二元關(guān)系：如果一個(gè)集合的元素都是二元有如果一個(gè)集合的元素都是二元有序組，則這個(gè)集合稱(chēng)為一個(gè)二元序組，則這個(gè)集合稱(chēng)為一個(gè)二元關(guān)系，記作：關(guān)系，記作：R 。如果 R ，記作 x R y如果 R ，記作 x R y3、二元關(guān)系的數(shù)學(xué)定義、二元關(guān)系的數(shù)學(xué)定義從從A到到B的二元關(guān)系：的二元關(guān)系：設(shè)設(shè)A，B為集合，為集合，A B的任的任

5、何子集所定義的二元關(guān)系叫做從何子集所定義的二元關(guān)系叫做從A到到B的二元關(guān)系。的二元關(guān)系。若A=B，叫做 A上的二元關(guān)系；若|A|n，則|A A|n2。2n2就是說(shuō)，A上有 個(gè)不同的二元關(guān)系，其中包括空關(guān)系、全域關(guān)系UA和恒等關(guān)系IA。2n2A A的所有子集有 個(gè)。例例4.3 設(shè)A = a,b，寫(xiě)出P(A)上的包含關(guān)系R ：解：解： P(A) = ,a,ba,bR = , , , , , 1. 關(guān)系矩陣：設(shè)A=x1, x2, , xn)，R是A上的關(guān)系，rij =1 若xi R xj0 若xi R xj(i, j = 1,2, n)則 (rij)nxn =是R的關(guān)系矩陣令：nnnnnnrrrrr

6、rrrr212222111211二、二元關(guān)系的表示方法2. 關(guān)系圖：以E = | xiA xjA xiRxj為有向邊集組成的有向圖G = 以V=A=x1, x2, xn 為頂點(diǎn)集，例例4.4 設(shè)A=1,2,3,4，R=,是A上的關(guān)系，試寫(xiě)出R的關(guān)系矩陣并畫(huà)出關(guān)系圖：解：解： 關(guān)系矩陣 ：0 0 1 10 0 0 00 1 0 01 1 0 0關(guān)系圖 ：134 2關(guān)系關(guān)系R的定義域：的定義域： domR = x | ( y) R (即即R中有序組的第一個(gè)元中有序組的第一個(gè)元素構(gòu)成的集合素構(gòu)成的集合)關(guān)系關(guān)系R的值域：的值域： ranR =y | ( x) R (即即R中有序組的第二個(gè)元中有序組的

7、第二個(gè)元素構(gòu)成的集合素構(gòu)成的集合)一、關(guān)系的定義域與值域例例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 解：解： domR1 = ranR1 = Z解：解： R2 = , , domR2 = ( ? )ranR2 = ( ? )(1) R1= | x, y Z xy (2) R2= | x, y Z x2+y2=1 , 解：解： domR3 = Z， ranR3 = 偶數(shù) 解：解： do

8、mR4 = ranR4 = ( ? )(3) R3= | x, y Z y=2x (4) R4= | x, y Z |x|=|y|=3 二、關(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 xA集A在關(guān)系F下的象FA = ran(F | A)(1) 逆：(2) 合成：(3) 限制：(4) 象：例例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解：解

9、：由定義知：G1 = | y, xN y = x+1列出G1 中的元素就是G1 = ,為了求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,2 = ,F 1,2 = ran(F |1,2) = 1,4F Z Z2 = y關(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

10、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( ? )( ? )任取 (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) (注意對(duì)括號(hào)的順序) (z)(G F(H F) F GF H F (GH) = F GF H(5) F (GH) = F GF H的證明：R的關(guān)系矩陣：主對(duì)角線元素全是1R的關(guān)系圖：每個(gè)頂點(diǎn)都有環(huán)自反性： x

11、 A 有R (R是A上的關(guān)系) 關(guān)系矩陣：主對(duì)角線元素全是0關(guān)系圖： 每個(gè)頂點(diǎn)都沒(méi)有環(huán)反自反性：x A R對(duì)稱(chēng)性：若 R，則 R 關(guān)系矩陣：對(duì)稱(chēng)陣關(guān) 系 圖：如果兩個(gè)頂點(diǎn)之間有邊，一定是一對(duì)方向相反的邊。反對(duì)稱(chēng)性：反對(duì)稱(chēng)性：若 R且xy，則 R 關(guān)系矩陣：如果rij = 1，且 i j，則rji = 0 關(guān)系圖： 如果兩個(gè)頂點(diǎn)之間有邊，一定是只有一條有向邊。傳遞性：傳遞性：若 R且 R，則 R 關(guān)系圖：如果頂點(diǎn)xi到xj有邊， xj到xk有邊，則從xi到xk有邊例例4.7 設(shè)A=1,2,10，對(duì)于A上的關(guān)系R= | (xy)/3II為整數(shù)集，問(wèn)R有哪些性質(zhì)？解：解：逐條性質(zhì)加以驗(yàn)證R= | (

12、xy)/3I 任取A中元素x，由于(xx)/3=0，所以R是自反的自反的；又設(shè)A中任意兩個(gè)元素x,y，如果 xRy，即xy可被3整除，則yx也一定可被3整除，即yRx，從而R是對(duì)稱(chēng)的對(duì)稱(chēng)的；如果A中三 個(gè)元素x，y，z滿足xRy， yRz，則x y，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，從而xRz即R具有傳遞性傳遞性。 閉包：設(shè)RAA，自反閉包 記作 r(R)對(duì)稱(chēng)閉包 記作 s(R)傳遞閉包 記作 t(R)由A求r(R)，s(R)，t(R)的過(guò)程叫閉包運(yùn)算。那么，包含R而使之具有自反性質(zhì)的最小關(guān)系，稱(chēng)之為R的自反閉包自反閉包；包含R而使之具有對(duì)稱(chēng)性質(zhì)(傳遞性質(zhì))的最小關(guān)

13、系，稱(chēng)之為R的對(duì)稱(chēng)(傳遞傳遞)閉包閉包。一、定義冪運(yùn)算：設(shè)RAA，kN，約定(1) R0 = IA = | xA(2) R1 = R(3) Rk+1 = Rk R顯然 Rm Rn = Rm+n (Rm)n = Rmn二、計(jì)算方法為了有效地計(jì)算關(guān)系R的各種閉包，先引進(jìn)關(guān)系的冪運(yùn)算概念。閉包運(yùn)算的方法：閉包運(yùn)算的方法：設(shè)R是A上的任一關(guān)系，則(1) r (R) = RIA(2) s (R) = RR(3) t (R) = RR2R3 Rn矩陣形式矩陣形式：(M為R的關(guān)系矩陣)(1) Mr = M + E(2) Ms = M + M (M 是M的轉(zhuǎn)置)(3) Mt = M+M2+M3其中“ +” 均

14、表示“ 邏輯加”例例4.8 設(shè)A=a,b,c,d，A上的關(guān)系求 r (R)，s (R) 和 t (R)解：解： r(R) = RIA=, , , , , , R=, = R,三、實(shí)例s(R) = RR=,t(R) = RR2R3= R,而R2 = R RR3 = R2 RR4 = R3 R= ,= ,= , , , 實(shí)際上，看到當(dāng)k 4時(shí)，已有R4 RR2R3故 t(R) = RR2R3=, ,四、閉包運(yùn)算的性質(zhì)設(shè)A是有限集且|A| = n，R A A，則：ikiRRtnk1)()1(，使有)()()2(RsrRrs)()()3(RtrRrt)( )()4(RtsRst 等價(jià)關(guān)系：集A上的關(guān)系

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

16、集為A則 為A的劃分。如果存在一個(gè)A的子集族， P(A)滿足以下條件： 由等價(jià)類(lèi)的性質(zhì)和商集的定義可知，商集A/R是A的劃分，稱(chēng)之為由R誘導(dǎo)的劃分。反過(guò)來(lái)，給定A的任一劃分 ，則A被分割成若干個(gè)劃分塊。 若定義A上的二元關(guān)系R：x，yA且x,y屬 的同一塊，則xRy，那么R是A上的等價(jià)關(guān)系，稱(chēng)之為由 誘導(dǎo)的等價(jià)關(guān)系。集A上的等價(jià)關(guān)系與劃分是一一對(duì)應(yīng)的。例例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,1,3，5 = 1,2,3

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

18、.11 設(shè)C=a,b,a,b,，C上關(guān)系T是集合的“ 包含于”，試寫(xiě)出T，并驗(yàn)證它是偏序關(guān)系。解：解： 同例4.10類(lèi)似，自己做！(1) 用小圓圈表示偏序集的元素 (稱(chēng)為結(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在上)全序關(guān)系：設(shè)是偏序集，(x)(y)(xA yA (xy yx)成立，則稱(chēng)A,)為全序集，這時(shí)的偏序關(guān)系叫全序關(guān)系。全序集A,)中全部元素可以排序，它的哈斯圖為一條直線。如果設(shè)是偏序集，B A(1) 如果yB，使得(x)(xByx)為真，則y是B的最小元 (“ 小于” B中所有元 )(2) 如果yB，使得(x)(xB xy)為真，則y是B的最大元 (“ 大于” B中所有元 )(4) 若yB，使得 (x)(xB xy)，則稱(chēng)y是B的極大元 (B中沒(méi)有比y大的其他元)(5) 若yA，