【正文】 路徑 :a b c d。 RC={y,x|x,y?R} y,x∈ RC ?x,y?R 二 . 計(jì)算方法 1. R={1,2,2,3,3,4,4,5} RC ={2,1,3,2,4,3,5,4} 2. RC的有向圖：是將 R的有向圖的所有邊的方向顛倒一下即可。 4. (R－ S)C = RC－ SC 。 (注意 ≠RC SC ) 證明 ： 任取 z,x∈ (R S)C ?x,z?R S ??y(y∈ Y∧ x,y∈ R∧ y,z∈ S) ? ?y(y∈ Y∧ z,y∈ SC∧ y,x∈ RC) ?z,x?SC RC 所以 (R S)C= SC RC 8. R是 A上關(guān)系，則 ⑴ R是對(duì)稱(chēng)的，當(dāng)且僅當(dāng) RC =R ⑵ R是反對(duì)稱(chēng)的，當(dāng)且僅當(dāng) R∩RC ?IA。 最后得 RC =R 。 作業(yè) ：第 118頁(yè)⑴、⑵ a)b)、⑶、⑸ 46 關(guān)系的閉包運(yùn)算 關(guān)系的閉包是個(gè)很有用的概念，特別是傳遞閉 包。 這 個(gè) R’就分別是 R的 自反 (對(duì)稱(chēng)、傳遞 )閉包。 3 這三個(gè)關(guān)系圖分別是 R的 自反、對(duì)稱(chēng)、傳遞閉包。 2。 。 3 實(shí)際上 r(R)、 (s(R) 、 t(R)) 就是包含 R的“最小” 的 自反 (對(duì)稱(chēng)、傳遞 )關(guān)系。即 r(R)=R∪ IA 。 證明：令 R’= R∪ R2∪ R3∪ ..., ⑴ 顯然有 R?R’ ； ⑵證 R’是傳遞的：任取 x,y,z?A,設(shè)有 x,y?R’ y,z?R’, 由 R’定義得必存在整數(shù) i,j使得 x,y?Ri , y,z?Rj ,根據(jù)關(guān)系的復(fù)合得 x,z?Ri+j, 又因 Ri+j ?R’,所以 x,z?R’, ∴ R’傳遞 。 ∴ R’?R”。下面證明 R’?R”： 任取 x,y?R’,由 R’定義得必存在 最小的 正整數(shù) i 使 得 x,y?Ri , (下面證明 i≤n)如果 i＞ n, 根據(jù)關(guān)系的復(fù)合得 A中必存在 i1個(gè)元素 e1, e2,...,ei1， 使得 x,e1?R∧ e1,e2?R∧ ...∧ ei1,y?R。 。 。 x e1 ej1 ej =ek ej+1 。 。 /*第 j行 +第 i行 ,送回第 j行 */ ⑷ i加 1。 2。 定理 6. R是 A上關(guān)系，則 ⑴ R是自反的，則 s(R)和 t(R)也自反。 證明 ⑵ . 證明 t(R)對(duì)稱(chēng) : (t(R))C=(R∪ R2∪ ...∪ Rn∪ ...)C = RC∪ (R2)C ∪ ...∪ (Rn)C∪ ... = RC∪ (RC)2 ∪ ...∪ (RC)n∪ ... =R∪ R2∪ ...∪ Rn∪ ... (∵ R對(duì)稱(chēng)， ∴ RC =R) =t(R) 所以 t(R)也對(duì)稱(chēng)。 。 ⑶ 因 R?s(R) 由定理 7得 t(R)?ts(R) st(R)?sts(R) 因 s(R)對(duì)稱(chēng)，有定理 6得 ts(R) 也對(duì)稱(chēng)，由定理 5得 sts(R)=ts(R) 所以有 st(R)?ts(R) 。 2。 2。 2。 2。 2。 2。 2。 2。 2。 2。 作業(yè) 第 127頁(yè) ⑴、⑸、⑺、⑻ 47 集合的劃分與覆蓋 圖書(shū)館的圖書(shū)，要分成許多類(lèi)存放，學(xué)校的學(xué)生 要按照專(zhuān)業(yè)分成許多班， … 即對(duì)集合的元素劃分 一 .定義 設(shè) X是一個(gè)非空集合 ,A={A1, A2,... ,An}, Ai?Φ Ai?X (i=1,2,...,n),如果滿(mǎn)足 A1∪ A2∪ ...∪ An =X (i=1,2,..., n) 則稱(chēng) A為集合 X的 覆蓋 。 A1, A2 ,A3也是劃分。如 A1 。 A1,A2,A3是一種劃分 ,其中 A1是最小劃分 ,A2是最 大劃分。若 a,b?A，且 aRb，則稱(chēng) a與 b等價(jià)。 1。 A={1} A={1,2} A={1,2,3} : 上邊 的模 3同余關(guān)系 R的圖： 從關(guān)系圖可看 出， R是自反、 對(duì)稱(chēng)、傳遞的 關(guān)系，所以 R是等價(jià)關(guān)系。 5。 3。 。 3 3 1。 2。 。 3 3 3 3 R2 R1 R5 R6 1。 2。 b)二個(gè)獨(dú)立子圖的情形，則 ( )個(gè)等價(jià)關(guān)系 。 ： R是 A上的等價(jià)關(guān)系， a∈A, 由 a確定的集合 [a]R: [a]R={x|x∈A∧a,x∈R} 稱(chēng)集合 [a]R為由 a形成的 R等價(jià)類(lèi)。 上述三個(gè)等價(jià)關(guān)系各有幾個(gè)等價(jià)類(lèi)？說(shuō)出對(duì)應(yīng)的 各個(gè)等價(jià)類(lèi)。 3 R2 1。 R3 。 ⑵ [a]R∩[b]R=Φ， 當(dāng)且 僅當(dāng) a,b?R。 證明：若 a,b∈ R，則任何 x∈ [a]R， 有 a,x∈R ， 由對(duì) 稱(chēng)性得 b,a∈R ， 再由傳遞性得 b,x∈R,∴x∈ [b]R， 所以 [a]R?[b]R。 證明： A中任何元素 a,由于有 aRa,所以 a∈ [a]R ， 如果 a∈ [b]R ， 所以有 a,b∈ ⑶得 [a]R=[b]R 。 (由性質(zhì)⑷⑸即得。 X/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}} X/R2={[1]R2 ,[2]R2}={{1},{2,3}} X/R1={[1]R3}={{1,2,3}}
。記作 A/R。 (因?yàn)橐?a,b∈ R， 要么 a,b?R。 ∴ [a]R=[b]R。 若 [a]R∩[b]R=Φ,而 a,b∈ R,由等價(jià)類(lèi)定義得 b∈ [a]R, 又因?yàn)?bRb,所以 b∈ [b]R， 所以 b∈ [a]R∩[b]R，產(chǎn)生矛盾。 1 2 3 從上述模 3同余關(guān)系例子中，可以歸納出等價(jià)類(lèi)的性質(zhì)：任 何兩個(gè)等價(jià)類(lèi)要么相等，要么不相交；那么在什么情況下相 等？那么在什么情況下不相交？ R是 A上等價(jià)關(guān)系，任意 a,b,c∈ A ⑴ 同一個(gè)等價(jià)類(lèi)中的元素，彼此有等價(jià)關(guān)系 R。 。 2。 可見(jiàn) x∈[a] R ?a,x∈ R 上例， A={1,2,3,4,5,6,7}, R是 A上的模 3同余關(guān)系， [1]R={1,4,7}= [4]R = [7]R 余數(shù)為 1的等價(jià)類(lèi) [2]R={2,5}= [5]R 余數(shù)為 2的等價(jià)類(lèi) [3]R={3,6}= [6]R 余數(shù)為 0的等價(jià)類(lèi) 思考題： 此例為什么只有三個(gè)等價(jià)類(lèi)？ 2. 由等價(jià)關(guān)系圖求等價(jià)類(lèi) ： R圖中每個(gè)獨(dú)立子圖上的結(jié)點(diǎn)， 構(gòu)成一個(gè)等價(jià)類(lèi)。 一共有 ( )個(gè) 中不同的等價(jià)關(guān)系。 3 3 R3 R4 R7 R8 思考題 ： A={1,2,3},可構(gòu)造多少個(gè) A中不同的等價(jià) 關(guān)系？可以根據(jù)等價(jià)關(guān)系有向圖的特點(diǎn)來(lái)考慮。 。 2。 1。 。 2。 A={1,2,3}下面是 A中關(guān)系： 1。 4。 上述關(guān)系 R圖就是由三個(gè)獨(dú)立的完全圖構(gòu)成的。 3。 1。 M W L N L∩M L∩W N∩M N∩W 遼寧男生 遼寧女生 非遼寧男生 非遼寧女生 定義： 若 A={A1, A2,... ,Am}與 B={B1,B2,...,Bn}都是集合 X的劃分 ,則其中所有的 Ai?Bj,組成的集合 C,稱(chēng)為 C是 A與B兩種劃分的交叉劃分 . (此定理的證明不講 ) 證明 :{ A1,A2,... ,Am}與 {B1,B2,...,Bn}的交叉劃分是 C={A1?B1,A1?B2,...,A1?Bn, A2?B1,A2?B2,...,A2?Bn ,..., Am?B1,Am?B2,...,Am?Bn} 在 C中任取元素 , Ai?Bh?X (∵ Ai?X,Bj?X) (A1?B1)∪ (A1?B2)∪ ...∪ (A1?Bs)∪ (A2?B1)∪ … ∪ (A2?Bs)∪ ... ∪ (Ar?B1)∪ (Ar?B2)∪ ...∪ (Ar?Bs) =(A1?( B1∪ B2∪ B3∪ ...Bs))∪ (A2?( B1∪ B2∪ B3∪ ... ∪ Bs))∪ ... ∪ (Ar?( B1∪ B2∪ B3∪ ... ∪ Bs)) = (A1∪ A2∪ A3∪ ...∪ Ar) ?( B1∪ B2∪ B3∪ ... ∪ Bs) =X?X=X 再驗(yàn)證 C中任意兩個(gè)元素不相交： 在 C中任取兩個(gè)不同元素 Ai?Bh和 Aj?Bk,考察 (Ai?Bh) ? (Aj?Bk) (i=j和 h=k不同時(shí)成立 ) = (Ai?Aj)?(Bh?Bk) i＝ j ,h≠k (Ai?Aj)?(Bh?Bk) =Ai??=? i≠j ,h≠k (Ai?Aj)?(Bh?Bk)=???=? i≠j, h=k (Ai?Aj)?(Bh?Bk)=?? Bh =? 綜上所述， C是 X的劃分。即每個(gè)劃分塊里 只有一個(gè)元素的劃分。 二 .最小劃分與最大劃分 最小劃分 ：劃分塊最少的劃分。 每個(gè) Ai均稱(chēng)為這 個(gè)劃分的一個(gè)劃分 (類(lèi) )。 。 。 。 。 。 。 。 。 。 。 通常將 t(R) 記成 R+， tr(R)記成 R*， 即 t(R)= R+=R∪ R2∪ ...∪ Rn∪ …= tr(R)=rt(R) =R*= R0∪ R∪ R2∪ ...∪ Rn∪ …= 練習(xí) ：給定 A中關(guān)系 R 如圖所示：分別畫(huà)出 r(R)、 s(R) 、 t(R)、 sr(R)、 rs(R)、 tr(R)、 rt(R)、 st(R) 、 ts(R) 的圖。 定理 7：設(shè) R R2是 A上關(guān)系，如果 R1?R2 ，則 ⑴ r(R1)? r(R2) ⑵ s(R1)? s(R2) ⑶ t(R1)?t(R2) 證明⑴ r(R1)=IA∪ R1?IA∪ R2= r(R2) ⑵ ，⑶類(lèi)似可證。 證明 ⑶ . 證明 r(R)傳遞 :先用歸納法證明下面結(jié)論 : (R∪ IA)i= IA∪ R∪ R2∪ ...∪ Ri ① i=1時(shí) R∪ IA= IA∪ R 結(jié)論成立。 ⑶ R是傳遞的，則 r(R)也傳遞。 。 下面舉例，令 X={1,2,3,4}, X中關(guān)系 R圖如右圖所示。 ⑵ 置 i=1。 。 。 。 所以 i≤n, 所以 x,y∈ R”, 于是 R’?R”。其實(shí)則不然，請(qǐng)看下例 : A={1,2,3} A中關(guān)系 R1,R2,R3,如下： R1={1,2,3,2} R2 ={1,2,3,1} R3 ={1,2,3,3} ={1,2} = =Φ 所以 t(R1)= ∪ ∪ = R1 ={1,3,2,1,3,2} ={1,1,2,2,3,3} =IA, = R2 ... t(R2)= R2∪ ∪ ={1,3,2,3,3,3} = t(R3)= R2∪ 2 R1 3 R1 4 R1 1 R1 2 R1 3 R1 2 R2 3 R2 4 R2 3 R2 2 R2 3 R2 3 R3 2 R3 2 R3 2 R3 定理 A中關(guān)系 R,如果 A是有限集合， |A|=n 則 t(R)=R∪ R2∪ ...∪ Rn 。因 R?R”, ∴ 有 x, e1?R”∧ e1,e2?R”∧ ...∧ ei1,y?R”。 證明方法與 。 證明：令 R’=R∪ IA,顯然 R’是自反的和 R?R’，下 面證明 R’是“最小的”：如果有 A上自反關(guān)系 R”且 R?R”,又 IA?R”,所以 R∪ IA?R”,即 R’?R”。 2。 3 1。 則稱(chēng) R’是 R的 自反 (對(duì)稱(chēng)、傳遞 )閉包。 2。這里要介紹關(guān)系的自反閉包、對(duì) 稱(chēng)閉包和傳