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