【正文】 37/57 等價關(guān)系與劃分 考察關(guān)系 R和集合 Z； R將 Z分成了如下 m個子集： 這 m個子集特點是：同一個子集中的元素之間都有關(guān)系 R，不同子集的元素之間無關(guān)系 R，每兩個子集無公共元素，而所有子集的并正好為 Z，構(gòu)成了 Z的一個劃分。若 ，稱 x等價于 y,記作 x~y。 ?定理 ： 設(shè) R是集合 A上的關(guān)系，則 )()().3(),()().2(),()().1( RtsRstRtrRrtRsrRrs ???34/57 等價關(guān)系與劃分 ?：集合和劃分 ?定義 ： 設(shè) A是一個非空集合， 是 A的任意 n個非空子集，如果 滿足： 則稱集合 為集合 A的一個劃分(Partition)，而 叫做這個劃分的塊或類。 )(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??????是傳遞的是對稱的是自反的.)(:)3(,)(),(:)2(,)(),(:)1(傳遞傳遞對稱對稱自反自反RrRRtRrRRtRsR???33/57 關(guān)系的閉包 ?定義 ： (1)集合 A上的關(guān)系 R的自反對稱閉包定義為 rs(R)=r(s(R))。 解： r(R)={a, b,b, b,b, c,a, a,c, c}。 ?定義 ： 設(shè) R是定義在 A上的二元關(guān)系，若存在滿足 ： (1) 是自反的 (對稱的或傳遞的 )； (2). ； (3)對 R的任何擴充 是自反的 (對稱的或傳遞的 )，則 。傳遞反對稱；反對稱對稱；對稱反自反；反自反自反；自反SRRSRSRSRRSRSRSRSRRSRSRSRSRRSRSRSRSRRSR?????????,)5(,)4(,)3(,)2(,)1(11111?????????????28/57 關(guān)系的性質(zhì) 顯然 R， S是反自反的，反對稱的，傳遞的，則 也是反自反的，反對稱的，傳遞的； 也具備上述的一切性質(zhì)； (3)R∪S={a, b,b, c,a, c, b, a,c, b,c, a}僅是對稱的和反自反的； 則是傳遞的和對稱的。)3(。 ?例 49： 設(shè) A={a, b, c, d} 不是傳遞的。 解 (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ì) 我們在研究關(guān)系的性質(zhì)時，可以假定關(guān)系是某一非空集合上的二元關(guān)系，這一假設(shè)不失一般性。 例： R={a, b， a,{a}， {a},{a,{a}}}，則： RΓ {a}={a, b， a,{a}}；RΓ {{a}}={{a},{a,{a}}} 。 ?定理 ： 設(shè)集合 A的基數(shù)為 n， R是 A上的二元關(guān)系，那么存在自然數(shù) i， j使得 證明：我們知道，當(dāng) |A|=n時， A上的二元關(guān)系共計 個，令 k= ，因此在 這 k+1個關(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)系的運算 系中，至少有兩個是相同的 (鴿巢原理 )，即有 ?定理 ： 設(shè) A是有限集合，且 |A|=n， R是 A上的二元關(guān)系，則 證明：顯然 ，下面證： 。)) . (1(1111111111111111111ABBAd o m Rr a n Rr a n Rd o m RSRSRSRSRSRSRSRSRRRRR???????????????????????????????????????????14/57 關(guān)系的運算 ? ?定義 ： 設(shè) R， S為二元關(guān)系，則 R與 S的復(fù)合關(guān)系 定義為： ，其中“ ”為復(fù)合運算， 也記為 。,).5(。 ?3. 關(guān)系矩陣 ?定義 ： 設(shè) ，那么 R的關(guān)系矩陣 為一 m n矩陣，它的第 i， j分量 只取 0或 1，且 },{},{, 2121 nm bbbBaaaABAR ?? ????RMijr???????jijiij bRaRbar當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)0110/57 關(guān)系的運算 ?，并，補，差運算 ?定義 ： 設(shè) R和 S為 A到 B的二元關(guān)系，其并，交，補，差運算定義如下： ?例 43： 設(shè) A={1,2,3,4}，若 R={x, y|(xy)/2是整數(shù)， x, y A}， S={x, y|(xy)/3是正整數(shù)，x, y A}，求 R∪S ， R∩S ， SR， ~R， R S。 ?例 41： 設(shè) A={1,2,3,4,5,6}， B={a, b, c, d}，則 R={2, a， 2, b， 3, b， 4, c， 6, c}，那么 domR={2,3,4,6}， ranR={a, b, c}。 例： A={a, b}， B={c}，則 A B的子集有 ，{a, c}， {b, c}， {a, c, b, c}， Fyx ??? , xFyyFx? ????6/57 二元關(guān)系及其表示法 A到 B上的全部二元關(guān)系；而 ， {c, c}為 B上的二元關(guān)系。 ?定義 ： 設(shè) 為 n個集合 (n ≥2) ，稱集合 為 n維卡氏積或 n階笛卡爾積，記作 ， 當(dāng) 時簡記為 。 例：設(shè) A={1,2}； B={a, b}則 A B={1,a， 1,b，2,a， 2,b}； B A={a, 1， a, 2， b, 1， b, 2}。1/57 第四章 二元關(guān)系 二元關(guān)系及其表示法 序偶與笛卡爾積 ?定義 ： 由兩個元素 x和 y按一定的次序組成的二元組稱為有序?qū)蛐蚺?(Ordered)，記作 x, y，其中 x是它的第一元素， y是它的第二元素。 ?2/57 二元關(guān)系及其表示法 ?定義 ： 設(shè) A， B是兩個集合，稱集合 為集合 A與 B的笛卡爾積 (Descartes Product)。(CA)(BAC)(BC ) ,(AB)(AC)(BA ) ,(CA)(BAC)(BC ) ,(AB)(AC)(B????????????????????????AA)()(,)(,)(,)()()()(,CABAyxCAyxBAyxCyAxByAxCyByAxCByAxCBAyx?????????????????????????????????????????DCBADBCA