【正文】 定義 ：給定 A中關(guān)系 R,若 A上另一個關(guān)系 R’， 滿足：⑴ R?R’； ⑵ R’是自反的 (對稱的、傳遞的 )； ⑶ R’是“ 最小的 ”，即對于任何 A上自反 (對稱、 傳遞 )的關(guān)系 R”, 如果 R?R”, 就有 R’?R”。記作 r(R)、 (s(R) 、 t(R)) (reflexive、 symmetric、 transitive) 1。 。 2。 3 1。 。 三 .計算方法 定理 A中關(guān)系 R,則 r(R)=R∪ IA。 所以 R’就是 R的自反閉包。 定理 A中關(guān)系 R,則 s(R)=R∪ RC 。 定理 A中關(guān)系 R,則 t(R)=R∪ R2∪ R3∪ ... 。 ⑶ 證 R’是“最小的”：如果有 A上傳遞關(guān)系 R”且 R?R”,（ 證出 R’?R”）任取 x,y?R’,則由 R’定義 得必存在整數(shù) i,使得 x,y?Ri ,根據(jù)關(guān)系的復(fù)合得 A中必存在 i1個元素 e1, e2,...,ei1， 使得 (見 49頁 ) x, e1?R∧ e1,e2?R∧ ...∧ ei1,y?R。 由于 R”傳遞，所以有 x,y?R”。 綜上所述， R’就是 R的傳遞閉包，即 t(R)=R∪ R2∪ R3∪ …= ∪ Ri i=1 ∞ 用上述 公式計算 t(R)， 要計算 R的無窮大次冪 ,好 象無法實現(xiàn)似的。 證明：令 R’=R∪ R2∪ R3∪ ..., R”=R∪ R2∪ ...∪ Rn 下面證明 R’=R” ， 顯然有 R”?R’。 上述元素序列 : x=e0, e1, e2,...,ei1,y=ei中共有 i+1個元 素， i+1n , 而 A 中只有 n個元素，所以上述元素中 至少有兩個相同，設(shè) ej=ek (jk)， 于是 R的關(guān)系圖中 會有下面這些邊： 從此圖中刪去回路中 kj(kj≥1)條邊后得x,y∈ Ri(kj)， i(kj)i, 與 i是 最小的 矛盾。 最后得 R’=R”，所以 t(R)=R∪ R2∪ ...∪ Rn 定理證畢。 。 。 。 。 。 。 ej+2 ek1 ek2 ek+1 ek+2 …... …... ei1 y 求 t(R)的矩陣 Warshall算法： |X|=n, R?X X, 令 MR=A R2的矩陣為 A2， … R k的矩陣為 Ak .于是 t(R)的 矩陣記作 MR+=A+A2+…+A k +… (+是邏輯加 ) ⑴ 置新矩陣 A :=MR 。 ⑶ 對所有 j ,如果 A[j,i] =1 ,則對 k=1,2,…,n A[j,k]:=A[j,k]+A[i,k]。 ⑸ 如果 i≤n, 則轉(zhuǎn)到步驟 ⑶，否則停止。 運(yùn)行該算法 求 t(R)的矩陣 ： 1。 。 4 3 i=1 (i列 , j行 ) A[4,1]=1 1行 +4行 →4 行 i=2 A[1,2]=1 ,1行 +2行 →1 行 A[2,2]=1 ,2行 +2行 →2 行 A不變 A[4,2]=1 ,4行 +2行 →4 行 ,4行全 1, A不變 i=3 A[1,3]=1,1行 +3行 →1 行 , 3行全 0, A不變 A[2,3]=1,2行 +3行 →2 行 , 3行全 0, A不變 A[4,3]=1,4行 +3行 →4 行 , 3行全 0, A不變 i=4 A[1,4]=1 ,1行 +4行 →1 行 A[4,4]=1 ,4行 +4行 →4 行 A不變 , 最后 A=Mt(R) ????????????1101000001101010A=MR= A= ????????????1111000001101010A的初值 : A= ????????????1111000001101110A= ????????????1111000001101111四 .性質(zhì) 定理 5. R是 A上關(guān)系，則 ⑴ R是自反的，當(dāng)且僅當(dāng) r(R)=R. ⑵ R是對稱的，當(dāng)且僅當(dāng) s(R)=R. ⑶ R是傳遞的，當(dāng)且僅當(dāng) t(R)=R. 證明略，因為由閉包定義即可得。 ⑵ R是對稱的，則 r(R)和 t(R)也對稱。 證明 : ⑴ 因為 R自反 ,由定理 5得 r(R)=R,即 R∪ IA=R, r(s(R))=s(R)∪ IA=(R∪ RC)∪ IA = (R∪ IA)∪ RC=r(R)∪ RC =R∪ RC =s(R)∴ s(R)自反 類似可以證明 t(R)也自反。 類似可以證明 r(R)也對稱。 ②假設(shè) i≤k 時結(jié)論成立，即 (R∪ IA)k= IA∪ R∪ R2∪ ...∪ Rk (R2)c=(R R)c =Rc Rc =(Rc)2 ③ 當(dāng) i=k+1時 (R∪ IA)k+1=(R∪ IA)k (R∪ IA) = (IA∪ R∪ R2∪ ...∪ Rk） (IA∪ R) = (IA∪ R∪ R2∪ ...∪ Rk)∪ (R∪ R2∪ ...∪ Rk+1) = IA∪ R∪ R2∪ ...∪ Rk∪ Rk+1 所以結(jié)論成立 . t(r(R))=t(R∪ IA) = (R∪ IA)∪ (R∪ IA)2∪ (R∪ IA)3∪ ... =(IA∪ R)∪ (IA∪ R∪ R2)∪ (IA∪ R∪ R2∪ R3)∪ ... = IA∪ R∪ R2∪ R3∪ ...= IA∪ t(R) = IA∪ R (R傳遞 t(R)=R) =r(R) 所以 r(R)也傳遞。 。 定理 8：設(shè) R是 A上關(guān)系，則 ⑴ sr(R)=rs(R) ⑵ tr(R)=rt(R) ⑶ st(R)?ts(R) 證明： ⑴ sr(R)=r(R)∪ (r(R)c=(R∪ IA)∪ (R∪ IA)c = (R∪ IA)∪ (Rc∪ IAc) =R∪ IA∪ Rc∪ IA = (R∪ Rc)∪ IA= s(R)∪ IA=rs(R) ⑵ 的證明用前邊證明的結(jié)論： (R∪ IA)k= IA∪ R∪ R2∪ ...∪ Rk 很容易證明，這里從略。 證明完畢。 1。 。 4 3 ∪ Ri i=1 ∞ ∪ Ri i=0 ∞ 1。 。 4 3 1。 。 4 3 1。 。 4 3 1。 。 4 3 1。 。 4 3 1。 。 4 3 1。 。 4 3 1。 。 4 3 1。 。 4 3 r(R) s(R) t(R) sr(R) rs(R) tr(R) rt(R) st(R) ts(R) 本節(jié)重點掌握閉包的定義、計算方法和性 質(zhì)。 設(shè) A={A1, A2,... ,An}是 X一個覆蓋 , 且 Ai?Aj=Φ (i?j,1≤i,j≤n)則稱 A是 X的 劃分。 例 X={1,2,3}, A1={{1,2,3}}, A2={{1},{2},{3}}, A3={{1,2},{3}}, A4={{1,2},{2,3}}, A5={{1},{3}} A1, A2 ,A3 ,A4 是覆蓋。 劃分 ,一定是覆蓋；但覆蓋 , 不一定是劃分 。即只有一個劃分 塊的劃分，這個劃分塊就是 X本身。 最大劃分 ：劃分塊最多的劃分。如 A2 。 三 .交叉劃分 例 X是東大學(xué)生集合 , A和 B都是 X的劃分： A={M,W},M?X, W?X, M={男生 },W={女生 } B={L,N},L?X, N?X, L={遼寧人 },N={非 遼寧人 } C={L∩M , L∩W , N∩M , N∩W } 稱 C是 X的交叉劃分。 作業(yè) ：第 130頁 (1) 48 等價關(guān)系與等價類 等價關(guān)系是很重要的關(guān)系，它是我們遇到最多的 關(guān)系，例如，數(shù)值相等關(guān)系 =、命題間的等價關(guān) 系 ? 、三角形相似 ∽ 和全等關(guān)系 ≌ ， ….. 一 .等價關(guān)系 :設(shè) R是 A上關(guān)系 ,若 R是自反的、對稱的和 傳遞的，則稱 R是 A中的等價關(guān)系。 例子，集合 A={1,2,3,4,5,6,7}, R是 A上的模 3同 余關(guān)系，即 R={x,y|xy可被 3整除 (或 x/3與 y/3的 余數(shù)相同 )} 即 x,y∈ R? x(mod 3)=y(mod3) 例如 4(mod 3)=7(mod3) 3(mod 3)=6(mod3) R={1,1,1,4, 1,7,2,2,2,5,3,3,3,6, 4,1, 4,4,4,7,5,2,6,3,6,6,7,1, 7,4,7,7} 1)完全關(guān)系 (全域關(guān)系 A A)圖，下面分別是當(dāng) A中只有 3個元素時的完全關(guān)系圖。 2。 2。 1。 等價關(guān)系 R的有向圖可能由若干個獨立子圖 (R圖的一部 分 )構(gòu)成的，每個獨立子圖都是完全關(guān)系圖 。 下面給出八個關(guān)系如圖所示，根據(jù)等價關(guān)系有向圖的 特點，判斷哪些是等價關(guān)系， 2。 1。 7。 6。 2。 1。 。 2。 1。 。 2。 1。 。 2。 1。 。 如果等價關(guān)系 R中有 a)三個獨立子圖的情形，則 ( )個等價關(guān)系 。 c)一個獨立子圖的情形，則 ( )個等價關(guān)系 。 二 . 等價類 我們經(jīng)常用等價關(guān)系對集合進(jìn)行劃分，得到的劃分塊 稱之為等價類。簡稱 a等價類。不同的等價類個數(shù) =獨立子圖個數(shù)。 1。 。 2。 3 R1 。 。 即任意 x,y∈ [a]R， 必有 x,y∈ R 證明： 任取 x,y∈ [a]R，由等價類定義得， a,x∈ R, a,y∈ R ,由 R對稱得， x,a∈ R， 又由 R傳遞得 x,y∈ R。 證明 :設(shè) a,b?R， 假設(shè) [a]R∩[b]R≠Φ,則存在 x∈ [a]R∩[b]R， ∴ x∈ [a]R∧ x∈ [b]R,∴ a,x∈ R ,b,x∈ R,由 R對稱得 x,b∈ R又由 R傳遞得 a,b∈ R,產(chǎn)生矛盾。 ⑶ [a]R=[b]R 當(dāng)且 僅當(dāng) a,b∈ R。 類似可證 [b]R?[a]R。 如果 [a]R=[b]R，由于有 aRa,所以 a∈ [a]R ， a∈ [b]R ， 所以有 b,a∈ R， 由對稱性得 a,b∈R. ⑷ .A中任何元素 a,a必屬于且僅屬于一個等價類。 ⑸ .任意兩個等價類 [a]R、 [b]R， 要么 [a]R=[b]R ，要么 [a]R∩[b]R=Φ 。 ) ⑹ R的所有等價類構(gòu)成的集合是 A的一個劃分。 ) (這個劃分稱之為 商集 ) 三 . 商集 商”和除法有關(guān)，比如把 一塊蛋糕 平均分成四份，從 兩種不同的角度看這件事： 從算術(shù)角度看 ： 1用 4除 ,每份 1/4,這就是“商” ,于是 : 1=1/4+1/4+1/4+1/4 從集合角度看 ： 集合 A用模 3同余關(guān)系 R劃分，得到三個等價類，所以 A {{1,4,7},{2,5},{3,6}}={[1]R,[2]R,[3]R}商集 定義 ： R是 A上等價關(guān)系，由 R的所有等價類構(gòu)成的集合 稱之為 A關(guān)于 R的商集。即 A/R={[a]R |a∈ A} 用刀分 } { 用 R分 生 日 日 快 快 樂 樂 生 例如 A={1,2,3,4,5,6,7} , R上模 3同余關(guān)系，則 A/R= {[1]R,[2]R,[3]R} ={{},{2,5},{3,6}} 練習(xí) X={1,2,3},X上關(guān)系 R R2 、 R3， 如上圖所示