【正文】 中的元素之間都有關(guān)系 R，不同子集的元素之間無(wú)關(guān)系 R，每?jī)蓚€(gè)子集無(wú)公共元素，而所有子集的并正好為 Z，構(gòu)成了 Z的一個(gè)劃分。 Ryx ??? ,AAI A ?,?36/57 等價(jià)關(guān)系與劃分 ?例 412： 設(shè) m為正整數(shù)，整數(shù)集合上的關(guān)系 證明關(guān)系 R是等價(jià)關(guān)系。若 ，稱 x等價(jià)于 y,記作 x~y。 nAAA , 21 ?nAAA , 21 ?AAnjijiAA iniji??????? 1).2(。 ?定理 ： 設(shè) R是集合 A上的關(guān)系，則 )()().3(),()().2(),()().1( RtsRstRtrRrtRsrRrs ???34/57 等價(jià)關(guān)系與劃分 ?：集合和劃分 ?定義 ： 設(shè) A是一個(gè)非空集合， 是 A的任意 n個(gè)非空子集，如果 滿足： 則稱集合 為集合 A的一個(gè)劃分(Partition)，而 叫做這個(gè)劃分的塊或類。 (3)集合 A上的關(guān)系 R的對(duì)稱傳遞閉包定義為 st(R)=s(t(R))。 )(1 jirij ?? )1(1 ??jiji rr 若1)( ??? RRRs MMM）（若則令 111,1 ???? ikikjkij rrrr32/57 關(guān)系的閉包 ?定理 ： 設(shè) R是 A上的二元關(guān)系，則 ?定理 ： 設(shè) R是集合 A上的關(guān)系，則 ?定理 ： 設(shè) R是集合 A上的關(guān)系，則 iniiiARRtnARRtRRRsIRRRRr1110)(||,)(:)3(,)(:)2(,)(:)1(???????????????則若.)(:)3(,)(:)2(,)(:)1(RRtRRRsRRRrR??????是傳遞的是對(duì)稱的是自反的.)(:)3(,)(),(:)2(,)(),(:)1(傳遞傳遞對(duì)稱對(duì)稱自反自反RrRRtRrRRtRsR???33/57 關(guān)系的閉包 ?定義 ： (1)集合 A上的關(guān)系 R的自反對(duì)稱閉包定義為 rs(R)=r(s(R))。 t(R)={a, b,b, b,b, c,a, c}。 解： r(R)={a, b,b, b,b, c,a, a,c, c}。 R?R?RR ?? R?RR ????30/57 關(guān)系的閉包 例：定義在 N上的“ ”關(guān)系的自反閉包 r(R)為“ ≤ ”，對(duì)稱閉包 s(R)為“ ≠ ”，傳遞閉包 t(R)為“ ”； 定義在 N上的“ =”關(guān)系的自反閉包 r(R)為“ =”，對(duì)稱閉包 s(R)為“ =”，傳遞閉包 t(R)為“ =”。 ?定義 ： 設(shè) R是定義在 A上的二元關(guān)系，若存在滿足 ： (1) 是自反的 (對(duì)稱的或傳遞的 )； (2). ； (3)對(duì) R的任何擴(kuò)充 是自反的 (對(duì)稱的或傳遞的 )，則 。因此，我們往往要在給定的關(guān)系中刪去一些或添加一些元素，以改變?cè)嘘P(guān)系的性質(zhì)，即所謂的關(guān)系的限制與擴(kuò)充。傳遞反對(duì)稱；反對(duì)稱對(duì)稱；對(duì)稱反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR?????????,)5(,)4(,)3(,)2(,)1(11111?????????????28/57 關(guān)系的性質(zhì) 顯然 R， S是反自反的，反對(duì)稱的，傳遞的，則 也是反自反的，反對(duì)稱的，傳遞的； 也具備上述的一切性質(zhì)； (3)R∪S={a, b,b, c,a, c, b, a,c, b,c, a}僅是對(duì)稱的和反自反的； 則是傳遞的和對(duì)稱的。)1(11RRRRIRRRRRRIRRRIRAAA?????????????????傳遞的是反對(duì)稱的是對(duì)稱的是反自反的是自反的27/57 關(guān)系的性質(zhì) ? ?定理 ： 設(shè) R， S是 A上的二元關(guān)系，則 ?例 410： 設(shè) R={a, b， b, c， a, c}， S={b, a， c, b， c, a}是定義在 A={a, b, c}上的兩個(gè)二元關(guān)系。)3(。則必有若 1,1,1],1[, ???? ikjkij rrrnkji.)5(。 ?例 49： 設(shè) A={a, b, c, d} 不是傳遞的。 ?例 48： 設(shè) A={a, b, c} 稱的。 解 (1)： R[A∩B]=R[{0}]={0} ； R[A]∩R[B] ={0,1,2}∩{0,1,2} ={0,1,2} ； (2)： R[A]R[B] ={0,1,2} {0,1,2}= ； R[AB]=R[{1,2}]={1,2} ],[][)][().4(,)().3(],[][)][().2(,)().1(BFAFBAFBFAFBAFBFAFBAFBFAFBAF??????????????????|}|,|,{ xyZyxyxR ????????22/57 關(guān)系的性質(zhì) 我們?cè)谘芯筷P(guān)系的性質(zhì)時(shí)，可以假定關(guān)系是某一非空集合上的二元關(guān)系，這一假設(shè)不失一般性。}][{ 11 aaRaR ???? ??21/57 關(guān)系的運(yùn)算 ?定理 ： 設(shè) F為關(guān)系， A， B為集合，則 ?例 46： 設(shè) ， A={0,1,2}， B={0,1,2}。 例： R={a, b， a,{a}， {a},{a,{a}}}，則： RΓ {a}={a, b， a,{a}}；RΓ {{a}}={{a},{a,{a}}} 。對(duì)任意的 ，則由“” 的定義知：存在 ，使得： .),20(, 2 jin RRjiji ???? 使iniiiRR11 ???? ??iiiniRR ????11?? iniiiRR11 ???? ??iniiniiiRRR ???????111????inik RR1?? ?kRba ??? , ?Aaaa k ?? 121 , ?),(, 012110 baaaRaaRaaRaa kkk ??????????? ? 令?19/57 關(guān)系的運(yùn)算 由于 |A|=n，所以由鴿巢原理； k+1個(gè)元素 中至少有兩個(gè)元素相同，不妨設(shè)為 ，則可 在 中刪去 后仍有 由關(guān)系的復(fù)合運(yùn)算得： ，其中 ，此時(shí)：若 ，則 ；若 ，則重復(fù)上述做法，最終總能找到 ，使 得 ，即有 ，由此 有 ，由 k的任意性 ， ∴ kaa ,0 ?)( jiaa ji ??RaaRaaRaa kk ????????? ? , 12110 ?RaaRaaRaa jjiiii ????????? ???? , 1211 ?RaaRaaRaaRaaRaa kkjjii ??????????????? ??? , 1112110 ?39。 ?定理 ： 設(shè)集合 A的基數(shù)為 n， R是 A上的二元關(guān)系，那么存在自然數(shù) i， j使得 證明：我們知道，當(dāng) |A|=n時(shí)， A上的二元關(guān)系共計(jì) 個(gè)，令 k= ，因此在 這 k+1個(gè)關(guān) 11).1( ??? ??? mnmnnn RRRRRRR ???.)()) . (4(,)) . (3(,).2( 11 ??? ??? nnmnnmnmnm RRRRRRR ?AAnA IIRIR ??? ??? 1101 )()(,)(11 )()( ?? ? kk RR111111111 )()()()()()( ????????? ???? kkkkk RRRRRRRR ???)20( 2nji jiRR ????22n 22n 1210 , ?kRRRR ?18/57 關(guān)系的運(yùn)算 系中，至少有兩個(gè)是相同的 (鴿巢原理 )，即有 ?定理 ： 設(shè) A是有限集合，且 |A|=n， R是 A上的二元關(guān)系，則 證明：顯然 ，下面證： 。 ?例 4