【正文】 ??SSSRSRSRSRSRSRSRMMMMMMMMMMMM????????? ,???12/57 關系的運算 ? 由于關系是序偶的集合，除了集合的一般運算外，還有一些特有的運算。 ?定義 ： 設 R是 A到 B的關系， R的逆關系或逆是 B到 A的關系，記為 ，定義為： ?顯然對任意 ，有 ； ? 為 R的關系矩陣，則 . 例： ； A={a, b, c, d}， B={1,2,3}， R={a, 1， c, 2， b, 2， d, 3}， ={1, a， 2, c， 2, b， 3, d}。 1?R }|,{1 xR yxyR ????ByAx ?? , xyRxR y 1??RM RR MM ???1?????? ?? 11 ,AA II1R?13/57 關系的運算 ?定理 ： 設 R和 S都是 A到 B上的二元關系，那么 .)(,).6(。,).5(。)) . (4(。)(,)(,)) . (3(。)) . (2(。)) . (1(1111111111111111111ABBAd o m Rr a n Rr a n Rd o m RSRSRSRSRSRSRSRSRRRRR???????????????????????????????????????????14/57 關系的運算 ? ?定義 ： 設 R， S為二元關系，則 R與 S的復合關系 定義為： ，其中“ ”為復合運算， 也記為 。 例：設 R表示父子關系，則 表示祖孫關系。 ?例 44： 設集合 A={0,1,2,3,4}， R， S均為 A上的二元關系，且 R={x, y|x+y=4}={0,4， 4,0，1,3， 3,1， 2,2}， S= ={x, y|yx=1}={0,1， 1,2， 2,3， 3,4}；求 ?一般地， SR? )}(|,{ t Syx R ttyxSR ??????? RR? 2R2RR)(SRR,S)(R, ???????? SSRRRSSRRSSR ?? ?15/57 關系的運算 ?定理 ： 設 F， G， H為任意二元關系，則 ?定理 ： 設 R為 A上的關系，則 ?定理 ： 設 F， G， H為任意二元關系，則 111)) . (2(),()) . (1( ??? ?? FGGFHGFHGF ??????????????? ???? RRRIIR AA ).2(,).1(.)) . (4(,)().3(,)) . (2(,)().1(FHFGFHGHFGFHGFFHFGFHGHFGFHGF????????????????????????16/57 關系的運算 ? ?定義 ： 設 R是集合 A上的二元關系，則 R的 n次冪 定義為： ?例 45： 設 A={0,1,2,3,4}， R={0,0， 0,1，1,3， 2,4， 3,1， 4,4}。 則 ={0,0， 0,1， 0,3， 1,1， 2,4，3,3， 4,4}； ={0,0， 0,1， 0,3， 1,3， 2,4，3,1， 4,4}； ={0,0， 0,1， 0,3， 1,1， 2,4，3,3， 4,4}= nRRRRAxxxIR nnA ??????? ? 10 ).2(},|,{).1(2R3R4R2R17/57 關系的運算 ?定理 ： 設 R為 A上的二元關系， m， n為自然數(shù)，則 證 (4)：若 n=0時，則有 假設 n=k時，有 ，則 n=k+1時，有 ∴ 命題成立。 ?定理 ： 設集合 A的基數(shù)為 n， R是 A上的二元關系，那么存在自然數(shù) i， j使得 證明：我們知道，當 |A|=n時， A上的二元關系共計 個，令 k= ，因此在 這 k+1個關 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 關系的運算 系中，至少有兩個是相同的 (鴿巢原理 )，即有 ?定理 ： 設 A是有限集合，且 |A|=n， R是 A上的二元關系，則 證明：顯然 ，下面證： 。 而 ，為此，只要證明對任意的 kn ，有 即可。對任意的 ，則由“” 的定義知：存在 ，使得： .),20(, 2 jin RRjiji ???? 使iniiiRR11 ???? ??iiiniRR ????11?? iniiiRR11 ???? ??iniiniiiRRR ???????111????inik RR1?? ?kRba ??? , ?Aaaa k ?? 121 , ?),(,, 012110 baaaRaaRaaRaa kkk ??????????? ? 令?19/57 關系的運算 由于 |A|=n，所以由鴿巢原理； k+1個元素 中至少有兩個元素相同，不妨設為 ，則可 在 中刪去 后仍有 由關系的復合運算得： ，其中 ，此時：若 ，則 ；若 ，則重復上述做法，最終總能找到 ，使 得 ，即有 ，由此 有 ，由 k的任意性 ， ∴ kaa ,0 ?)( jiaa ji ??RaaRaaRaa kk ????????? ? ,, 12110 ?RaaRaaRaa jjiiii ????????? ???? ,, 1211 ?RaaRaaRaaRaaRaa kkjjii ??????????????? ??? ,,, 1112110 ?39。,0 kk Raaba ??? ? ??)( ijkk ???? nk ?? iniRba1,???? ?nk ?? nk ???kk Raaba ????? ? ?? , 0 iniRba1,???? ?inik RR1?? ? iniiiRR11 ???? ?? iniiiRR11 ???? ??20/57 關系的運算 ?5：集合在關系下的像 ?定義 ： 設 R為二元關系， A是集合 (1)： R在 A上的限制 定義為： (2)： A在 R下的像 R[A]定義為 R[A]=ran( )。 例： R={a, b， a,{a}， {a},{a,{a}}}，則： RΓ {a}={a, b， a,{a}}；RΓ {{a}}={{a},{a,{a}}} 。 RΓ {a, {a}}=R； R[{a}]={b,{a}}； R[{a,{a}}]={b,{a},{a,{a}}}； }|,{ Axx R yyxAR ??????AR?AR?}},{{}}{{1 ????? aaaR}{}}][{{。}][{ 11 aaRaR ???? ??21/57 關系的運算 ?定理 ： 設 F為關系， A， B為集合，則 ?例 46： 設 ， A={0,1,2}， B={0,1,2}。 (1)求 R[A∩B] 和R[A]∩R[B] ； (2)求 R[A]R[B]和 R[AB]。 解 (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