復(fù)合關(guān)系逆關(guān)系及閉包

1、3-7 復(fù)合關(guān)系和逆關(guān)系3-7.1復(fù)合關(guān)系復(fù)合關(guān)系定義定義1復(fù)合復(fù)合 (合成合成)(composite)關(guān)系關(guān)系:設(shè)設(shè)R為為X到到Y(jié)的關(guān)系，的關(guān)系，S為從為從Y到到Z上的關(guān)系，上的關(guān)系，則則RS稱為稱為R和和S的復(fù)合關(guān)系，表示為：的復(fù)合關(guān)系，表示為：RS= |xXzZ(y)(yYRS).3-7.23-7.2逆關(guān)系逆關(guān)系定義定義2逆逆(inverse)關(guān)系關(guān)系 : 設(shè)R是X到Y(jié)的二元關(guān)系，則從Y到X的二元關(guān)系Rc定義為： Rc = |R.整數(shù)集合上的“”關(guān)系的逆關(guān)系是“”關(guān)系。人群中的父子關(guān)系的逆關(guān)系是子父關(guān)系。容易看出(Rc) c=R例1: 設(shè) R= , , S= , .求: (1)Rc ，S

2、c. (2) RS, SR解: (1) Rc = , Sc = ,. (2) RS= , SR=.例2:（書上的例題2，第115頁）定理1: 設(shè)R1,R2,R3為關(guān)系， R1 是X到Y(jié)的關(guān)系， R2是Y到Z的關(guān)系， R3是Z到W的關(guān)系則(R1R2)R3 = R1 (R2 R3)證明: , (R1 R2) R3 z(zZ x (R1R2)z zR3w ) z(zZ y(yY xR1y yR2z ) zR3w) zy(zZ yY xR1y yR2z zR3w) ytz(zZ yY xR1y (yR2z zR3w) ) y(yY xR1y z(zZ yR2z zR3w) y(yY xR1y y(R2

3、R3)w ) xR1(R2R3)w R1(R2R3) (R1R2) R3 = R1(R2 R3). #說明: 本定理說明復(fù)合運(yùn)算滿足結(jié)合律. 由復(fù)合關(guān)系滿足結(jié)合律，可以把關(guān)系R本身所組成的復(fù)合關(guān)系寫成：RR， RRR， RRR(m個(gè))，分別記作 R(2)， R(3)， ， R(m)?？梢宰C明復(fù)合關(guān)系不滿足交換律。R1R2 R2R17-3.3關(guān)系矩陣的性質(zhì)：(1) MRc = (MR)T. ( T表示矩陣轉(zhuǎn)置)(2) MR1 R2 = MR1MR2 (表示布爾乘法, 其中加法使用邏輯, 乘法使用邏輯 )3-7.4逆關(guān)系關(guān)系圖的性質(zhì)：關(guān)系 Rc 的圖形是將關(guān)系R圖形中弧的箭頭方向反置。定理定理2:

4、 設(shè)設(shè)R、 R1 、 R2都是從都是從A到到B的二元關(guān)系，則的二元關(guān)系，則有有(1)( R1 R2) c= R1 c R2 c (2) ( R1 R2) c= R1 c R2 c(3)(AB) c= B A(4)(R) c = Rc, 這里這里R AB-R(5) ( R1-R2) c = R1 c - R2 c 注：證明注：證明(1)(4)(5)見書見書117頁。頁。定理3: 設(shè)設(shè)R,S為二元關(guān)系為二元關(guān)系, 則則(RS)c =S c Rc.證明證明: , (RS)c (RS) z( yRz zSx ) z( zRcy xScz ) z( xScz zRcy) Sc Rc. 定理4:設(shè)設(shè)R為為

5、X上的二元關(guān)系，則上的二元關(guān)系，則(1) R是對稱的是對稱的R=Rc（證明見書（證明見書118頁）頁）(2) 是反對稱的是反對稱的R Rc IX定理定理5:P119 (2)設(shè)設(shè)R為為X上的二元關(guān)系，上的二元關(guān)系，則則(1) R是傳遞的是傳遞的 (RR) R(2) R是自反的是自反的 IX R例題: 設(shè) A=a,b,c, R1=, R2=, 用MR1, MR2確定MR1c , MR2c, MR1R1, MR1R2, MR2R1, 從而求出它們的集合表達(dá)式. 1 1 0 1 1 0MR1= 1 0 1 MR1c= 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0MR2= 0 0 1 MR

6、2c= 1 0 0 0 0 0 1 1 0 0 1 1MR1R2 =MR1 MR2= 0 1 1 0 0 0R1R2 = ,. 1 1 0 1 1 0 1 1 1 MR1R1 =MR1 MR1= 1 0 1 1 0 1 = 1 1 0 0 0 0 0 0 0 0 0 0R1R1 = ,. 0 1 1 1 1 0 1 0 1 MR2R1 =MR2 MR1= 0 0 1 1 0 1 = 0 0 0 0 0 0 0 0 0 0 0 0R2R1 = ,.解: R1c = , R2c = , R1R1 = ,. R1R2 = ,. R2R1 = ,.作業(yè)(3-7)：P118 (1) (5)3-8 關(guān)系的

7、閉包運(yùn)算自反閉包r(R) (reflexivity closure)對稱閉包s(R) (symmetry closure)傳遞閉包t(R) (transitivity closure)閉包的性質(zhì), 求法, 相互關(guān)系3-8.1自反閉包(reflexive closure)定義定義1自反閉包自反閉包: 包含給定關(guān)系包含給定關(guān)系R的最小自反關(guān)系的最小自反關(guān)系, 稱為稱為R的的自反閉包自反閉包, 記作記作r( R ). (1) r( R )是自反的是自反的; (2) R r( R ); (3)( S)( (R S S自反自反) r(R) S).3-8.2對稱閉包(symmetric closure)定

8、義定義2對稱閉包對稱閉包: 包含給定關(guān)系包含給定關(guān)系R的最小的最小對稱關(guān)系對稱關(guān)系, 稱為稱為R的對稱閉包的對稱閉包, 記記作作s( R ). (1) s(R)是對稱的是對稱的; (2) R s(R); (3) ( S)( (R S S對稱對稱) s(R) S ).3-8.3傳遞閉包(transitive closure)定義定義3傳遞閉包傳遞閉包: 包含給定關(guān)系包含給定關(guān)系R的最小的最小傳遞關(guān)系傳遞關(guān)系, 稱為稱為R的傳遞閉包的傳遞閉包, 記作記作t(R). (1) t(R)是傳遞的是傳遞的; (2) R t(R); (3) ( S)( (R S S傳遞傳遞) t(R) S ).定理1: 設(shè)

9、設(shè)R A A且且A,則則 (1) R自反自反 r(R) = R; (2) R對稱對稱 s(R) = R; (3) R傳遞傳遞 t(R) = R;證明證明: (1) R R R自反自反 r(R) R 又又 R r(R), r(R) = R. (2)(3) 完全類似完全類似. *（補(bǔ)充）定理（補(bǔ)充）定理1:設(shè)設(shè) R1 R2 A A 且且 A, 則則 (1) r(R1) r(R2); (2) s(R1) s(R2); (3) t(R1) t(R2);證明證明: (1) R1 R2 r(R2)自反自反, r(R1) r(R2) (2)(3) 類似可證類似可證. *（補(bǔ)充）定理（補(bǔ)充）定理2:設(shè)設(shè) R1

10、,R2 A A 且且 A, 則則 (1) r(R1 R2) = r( R1 ) r( R2 ); (2) s(R1 R2) = s( R1 ) s( R2 ); (3) t(R1 R2) t( R1 ) t( R2 ).證明證明: (1) 利用定理利用定理20, r(R1 R2) r(R1) r(R2). r(R1) r(R2)自反且包含自反且包含R1 R2,所以所以 r(R1 R2) r(R1) r(R2). r( R1 R2) = r( R1 ) r( R2 )證明證明(2): 利用定理利用定理20, s(R1 R2) s(R1) s(R2). s(R1) s(R2)對稱且包含對稱且包含R

11、1 R2,所以所以 s(R1 R2) s(R1) s(R2). s( R1 R2) = s( R1 ) s( R2 )證明證明(3): 利用定理利用定理20, t(R1 R2) t(R1) t(R2). 反例反例: t(R1 R2) t(R1) t(R2) . 定理定理2: 設(shè)設(shè) R A A 且且 A, 則則 (1) r( R ) = R IA; (2) s( R ) = R Rc; (3) t( R ) = R R2 R3 .對比對比: R自反自反 IA R R對稱對稱 R=Rc R傳遞傳遞 R2 R證明證明: (1) r( R ) = R IA;i) R R IA;ii)IA R IA R

12、 IA自反自反 r( R ) R IA;iii)R r(R) r(R)自反自反 R r(R) IA r(R) R IA r( R ) r( R ) = R IA.證明證明: (2) s(R) = R Rc;i) R R Rc; ii) (R Rc)c=R Rc R Rc 對稱對稱 s(R) R Rc;iii)R s(R) s(R)對稱對稱R s(R) Rc s(R) R Rc s(R) s( R ) = R Rc.證明(3)之前，說明以下事實(shí)：復(fù)合運(yùn)算對并運(yùn)算滿足分配律(1)R1 (R2 R3)=(R1 R2 ) (R1 R3)(2)(R1R2) R3 =(R1 R3 ) (R2 R3)復(fù)合運(yùn)

13、算對交運(yùn)算滿足弱弱分配律(1)R1 (R2R3) (R1 R2 ) (R1 R3)(2)(R1R2) R3 (R1 R2 ) (R1 R3)證明證明: (3) t(R) = R R2 R3 .證明證明:i) 先證先證t(R) R R2 R3 ; R R R2 R3 ; (R R2 R3 )2 = R2 R3 R R2 R3 R R2 R3 傳遞傳遞 t(R) R R2 R3 ; ii)再證再證R R2 R3 t(R) R t(R) t(R)傳遞傳遞 R t(R) R2 t(R) R3 t(R) R R2 R3 t(R) t(R) = R R2 R3 . #定理定理3：設(shè)設(shè)X是含有是含有n個(gè)元素

14、的集合，個(gè)元素的集合，R是是X上的二元關(guān)系，則存在一個(gè)正整數(shù)上的二元關(guān)系，則存在一個(gè)正整數(shù)k n，使得使得t( R ) = R R2 R3 Rk證明：見證明：見P122。例題例題1: 設(shè)設(shè) A = a,b,c,d , R = , . 求求 r(R), s(R), t(R).解解: r(R)=R IA =, , s(R)=R Rc= , t(R)= R R2 R3 R4 =, ,見見P123求傳遞閉包的另一種方法：當(dāng)有限集X的元素較多時(shí)，矩陣運(yùn)算很繁瑣，Warshall 在1962年提出了R+的一個(gè)有效算法如下：（1）置新矩陣A=M（2）置i=1（3）對所有j如果Aj, i =1，則對k=1,2

15、,nAj,k=Aj,k+Ai,k（4） i= i+1（5）如果 i n,則轉(zhuǎn)到步驟（3）,否則停止。引出下面定理：引出下面定理：閉包運(yùn)算是否可以交換順序閉包運(yùn)算是否可以交換順序?即：即：(1) rs( R ) = sr( R ) ?(2) rt( R ) = tr( R ) ?(3) st( R ) = ts( R ) ?定理定理4：設(shè)設(shè) R A A 且且 A, 則則 (1) rs(R) = sr(R); (2) rt(R) = tr(R); (3) st(R) ts(R);證明：證明： (1) rs(R) = r(s(R) = r(R Rc) = IA (R Rc) = (IA R) (IAc Rc) = (IA R) (IA R)c = r(R) r(R)c = s(r(R) = sr(R). rs(R) = sr(R). (2)證明證明: rt(R) = r(t(R) = r(R R2 R3 ) = IA (R R2 R3 ) = (IA R) (IA R R2) (IA R R2 R3) = (IA R) (I