【文章內(nèi)容簡介】 }]={1,2} ],[][)][().4(,)().3(],[][)][().2(,)().1(BFAFBAFBFAFBAFBFAFBAFBFAFBAF??????????????????|}|,|,{ xyZyxyxR ????????22/57 關系的性質(zhì) 我們在研究關系的性質(zhì)時，可以假定關系是某一非空集合上的二元關系，這一假設不失一般性。因此任一 A到 B上的關系 R，即 ，而 ，所以關系 R總可以看成是A∪ B 上的關系，它與原關系 R具有完全相同的序偶，對它的討論代替對 R的討論無損于問題的本質(zhì) ? ?定義 ： 設 R是 A上的二元關系，即 ，則 (1)若 ，則稱 R是自反的(Reflexive)； (2)若 ，則稱 R是反自反的(Irreflexive)； BAR ??)()( BABABA ?? ???AAR ??),( RxxAxx ??????),( RxxAxx ??????23/57 關系的性質(zhì) (3)若 ，則稱 R是對稱的(Symmetric) (4)若 ，則稱 R是反對稱的 (Antisymmetric) (5)若 ，則稱 R是傳遞的 (Transitive) ?例 47： 設 A={a, b, c, d} (1):R={a, a， a, d， b, b， b, d， c, c， d, d}是自反的； S={a, b， a, d， b, c， b, d， c, a，d, c}是反自反的； T={a, a,a, b,a, c,b, d,c, a,c, c,d, c}既不是自反的也不是反自反的； ),( y R xx R yAyxyx ?????),( yxy R xx R yAyxyx ???????),( x R zy R zx R yAzyxzyx ???????24/57 關系的性質(zhì) ?在關系圖上：關系 R是自反的，當且僅當其關系圖中的每個節(jié)點都有環(huán)，關系 R是反自反的，當且僅當其關系圖中的每個節(jié)點上都無環(huán)； ?在關系矩陣上：關系 R是自反的，當且僅當其關系矩陣的主對角線上全為 1，關系 R是反自反的，當且僅當其關系矩陣的主對角線上全為 0。 ?例 48： 設 A={a, b, c} 稱的。既是對稱的，也是反對反對稱的；既不是對稱的，也不是是反對稱的；是對稱的；},{)4(},,{)3(},{)2(},,{)1(4321??????????????????????????ccaaRaccabaaaRcaaaRaccaaaR25/57 關系的性質(zhì) ?關系圖上：關系 R是對稱的當且僅當其關系圖中，任何一對節(jié)點之間，要么有方向相反的兩條邊，要么無任何邊；關系 R是反對稱的當且僅當其關系圖中，任何一對節(jié)點之間，至多有一條邊； ?關系矩陣上：關系 R是對稱的當且僅當其關系矩陣是對稱矩陣；關系 R是反對稱的當且僅當其關系矩陣為反對稱矩陣。 ?例 49： 設 A={a, b, c, d} 不是傳遞的。不是傳遞的；是傳遞的；是傳遞的；},,{)4(},,{)3(},{)2(},,{)1(4321????????????????????????????dccacbbaRcbbaaaRbaRcacbbaaaR26/57 關系的性質(zhì) ?關系圖上：關系 R是傳遞的當且僅當其關系圖中，任何三個節(jié)點 x, y, z(可相同 )之間，若從 x到 y，y到 z均有一條邊，則從 x到 z一定有一條邊存在； ?關系矩陣上：關系 R是傳遞當且僅當其關系矩陣中，對任意 ? ?定理 ： 設 R是集合 A上的二元關系，則 。則必有若 1,1,1],1[, ???? ikjkij rrrnkji.)5(。)4(。)3(。)2(。)1(11RRRRIRRRRRRIRRRIRAAA?????????????????傳遞的是反對稱的是對稱的是反自反的是自反的27/57 關系的性質(zhì) ? ?定理 ： 設 R， S是 A上的二元關系，則 ?例 410： 設 R={a, b， b, c， a, c}， S={b, a， c, b， c, a}是定義在 A={a, b, c}上的兩個二元關系。 傳遞。傳遞反對稱；反對稱對稱；對稱反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR?????????,)5(,)4(,)3(,)2(,)1(11111?????????????28/57 關系的性質(zhì) 顯然 R， S是反自反的，反對稱的，傳遞的，則 也是反自反的，反對稱的，傳遞的； 也具備上述的一切性質(zhì)； (3)R∪S={a, b,b, c,a, c, b, a,c, b,c, a}僅是對稱的和反自反的； 則是傳遞的和對稱的。 111 ,).1( ??? ?? SRSR???SR ?)2(},,{)4( ????????? abbabbaaSR ?29/57 關系的閉包 關系的限制與擴充：對于任何一個具備某種性質(zhì) (如自反、對稱、傳遞 )的關系來說，在理論研究與應用上都十分重要，但遺憾的是，許多我們要研究的關系并不具有我們所希望的良好性質(zhì)。因此，我們往往要在給定的關系中刪去一些或添加一些元素，以改變原有關系的性質(zhì)，即所謂的關系的限制與擴充。 關系的閉包則是關系的擴充。 ?定義 ： 設 R是定義在 A上的二元關系，若存在滿足 ： (1) 是自反的 (對稱的或傳遞的 )； (2). ； (3)對 R的任何擴充 是自反的 (對稱的或傳遞的 )，則 。一般將 R的自反、對稱、傳遞閉包記作 r(R)， s(R)， t(R)。 R?R?RR ?? R?RR ????30/57 關系的閉包 例：定義在 N上的“ ”關系的自反閉包 r(R)為“ ≤ ”，對稱閉包 s(R)為“ ≠ ”，傳遞閉包 t(R)為“ ”； 定義在 N上的“ =”關系的自反閉包 r(R)為“ =”，對稱閉包 s(R)為“ =”，傳遞閉包 t(R)為“ =”。 ?例 411： 設集合 A={a, b, c}， R={a, b， b, b，b, c}是定義在 A上的二元關系，求 r(R)， s(R)，t(R)并畫出 R， r(R)， s(R)， t(R)的關系圖，關系矩陣。 解： r(R)={a, b,b, b,b, c,a, a,c, c}。 s(R)={a, b,b, b,b, c,b, a,c, b}。 t(R)={a, b,b, b,b, c,a, c}。 31/57 關系的閉包 ?利用關系圖，關系矩陣求閉包的方法： (1).求一個關系的自反閉包，即將圖中所有的無環(huán)節(jié)點加上環(huán)，矩陣中的對角線上的值全定義為 1； (2).求一個關系的對稱閉包，則在圖中，任何一對節(jié)點之間，若僅存在一條邊，則加一條反方向的邊；矩陣中則為：若 ，則令 ，即 ； (3).求一個關系的傳遞閉包，則在圖中，對任意節(jié)點 a， b， c，若 a到 b有一條邊，同時 b到 c也有一條邊，則從 a到 c必增加一條邊 (當 a到 c無邊時 )，在矩陣中，若 。 )(1 jirij ?? )1(1 ??jiji rr 若1)( ??? RRRs MMM）（若則令 111,1 ???? ikikjkij rrrr32/57 關系的閉包 ?定理 ： 設 R是 A上的二元關系，則 ?定理 ： 設 R是集合 A上的關系，則 ?定理 ： 設 R是集合 A上的關系，則 iniiiARRtnARRtRRRsIRRRRr1110)(||,)(:)3(,)(:)2(,)(:)1(???????????????則若.)(:)3(,)(:)2(,)(:)1(RRtRRRsRRRrR??????是傳遞的是對稱的是自反的.)(:)3(,)(),(:)2(,)(),(:)1(傳遞傳遞對稱對稱自反自反RrRRtRrRRtRsR???33/57 關系的閉包 ?定義 ： (1)集合