【正文】 即 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={1,2,3},X上關(guān)系 R R2 、 R3， 如上圖所示。 ) ⑹ R的所有等價類構(gòu)成的集合是 A的一個劃分。 如果 [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,b∈ R。 即任意 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。 3 R1 。 。不同的等價類個數(shù) =獨立子圖個數(shù)。 二 . 等價類 我們經(jīng)常用等價關(guān)系對集合進行劃分，得到的劃分塊 稱之為等價類。 如果等價關(guān)系 R中有 a)三個獨立子圖的情形，則 ( )個等價關(guān)系 。 1。 。 2。 1。 。 2。 7。 下面給出八個關(guān)系如圖所示，根據(jù)等價關(guān)系有向圖的 特點，判斷哪些是等價關(guān)系， 2。 1。 2。 作業(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)系。如 A2 。即只有一個劃分 塊的劃分，這個劃分塊就是 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 是覆蓋。 4 3 r(R) s(R) t(R) sr(R) rs(R) tr(R) rt(R) st(R) ts(R) 本節(jié)重點掌握閉包的定義、計算方法和性 質(zhì)。 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 ∪ Ri i=1 ∞ ∪ Ri i=0 ∞ 1。 1。 定理 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 很容易證明，這里從略。 ②假設(shè) i≤k 時結(jié)論成立，即 (R∪ IA)k= IA∪ R∪ R2∪ ...∪ Rk (R2)c=(R R)c =Rc Rc =(Rc)2 ③ 當 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)也傳遞。 證明 : ⑴ 因為 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)也自反。 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是自反的，當且僅當 r(R)=R. ⑵ R是對稱的，當且僅當 s(R)=R. ⑶ R是傳遞的，當且僅當 t(R)=R. 證明略，因為由閉包定義即可得。 運行該算法 求 t(R)的矩陣 ： 1。 ⑶ 對所有 j ,如果 A[j,i] =1 ,則對 k=1,2,…,n A[j,k]:=A[j,k]+A[i,k]。 。 。 。 最后得 R’=R”，所以 t(R)=R∪ R2∪ ...∪ Rn 定理證畢。 證明：令 R’=R∪ R2∪ R3∪ ..., R”=R∪ R2∪ ...∪ Rn 下面證明 R’=R” ， 顯然有 R”?R’。 由于 R”傳遞，所以有 x,y?R”。 定理 A中關(guān)系 R,則 t(R)=R∪ R2∪ R3∪ ... 。 所以 R’就是 R的自反閉包。 。 2。記作 r(R)、 (s(R) 、 t(R)) (reflexive、 symmetric、 transitive) 1。 。 一 .例子 給定 A中關(guān)系 R，如圖所示， 分別求 A上另一個關(guān)系 R’，使 得它是包含 R的“最小的” (序偶 盡量少 )分別具有自反 (對稱、傳遞 )性的關(guān)系。 第 43和 44節(jié)的 要求 ： 熟練掌握求復合關(guān)系和逆關(guān)系的計算方法 及性質(zhì)。 再證 R? RC， 任取 x,y?R, 因 R對稱，所以有 y,x∈ R，則 x,y∈ RC, 所以 R?RC。 證明 ： 充分性 ，已知 RC? SC ，則任取 x,y∈ R ?y, x?RC? y, x?SC ? x,y?S ∴ R?S 必要性 ，已知 R? S，則任取 y,x∈ RC ? x,y?R?x,y?S ?y,x?SC ∴ RC?SC 6.(~R)C=~RC 證明 :任取 y,x∈ (~R)C ?x,y∈ ~R?x,y?R ?y,x?RC ?y,x∈ ~RC ∴ .(~R)C=~RC R是從 X到 Y的關(guān)系， S是 Y到 Z的關(guān)系，則 (R S)C= SC RC 。 3. (R∩S)C = RC∩SC 。 一 .定義 R是從 A到 B的關(guān)系，如果將 R中的所有序偶的 兩個元素的位置互換，得到一個從 B到 A的關(guān)系， 稱之為 R的逆關(guān)系，記作 RC，或 R1。即 R R=R2， R2 R=R R2 =R3， … 一般地 R0 =IA， Rm Rn = Rm+n (Rm)n =Rmn (m,n為非負整數(shù) ) 例如 R是 A上關(guān)系，如上圖所示 ,可見 a,c?R2,表明在 R圖上有從 a到 c有兩條邊的路徑 : a b c。 d 1。 d 。 A R IB 。 B a b c 。 3。下面列舉一例 來驗證。 。 B 1 2 3 。 3。 2。 。 SR?a b c R S :設(shè)是 R從 X到 Y的關(guān)系， S是從 Y到 Z的關(guān)系，則 R和 S的復合關(guān)系記作 R?S 。 作業(yè) 第 113頁 ⑴、⑶、⑷ 44 關(guān)系的復合 二元關(guān)系除了可進行集合并、交、補等運算外， 還可以進行一些新的運算，先介紹由兩個關(guān)系生 成一種新的關(guān)系，即關(guān)系的復合運算。 充分性 : 已知任意 a,b,c?A， 如 a,b和 a,c在 R中 ,則有 b,c也在 R中。 證畢 練習 2： 設(shè) R是集合 A上的一個自反關(guān)系 ,求證： R是對稱和傳遞的，當且僅當 a,b和 a,c在 R中 ,則有 b,c也在 R中。 3 3 3 3 R5 R6 R7 R8 自反性 反自反性 對稱性 反對稱性 傳遞性 R5 N Y N Y Y R6 N N Y N N R7 N N N N N R8 N Y Y Y Y 練習 1:令 I是整數(shù)集合， I上關(guān)系 R定義為： R={x,y|xy可被 3整除 }，求證 R是自反、對稱和傳遞的。 。 2。 3 3 3 3 R2 R1 R3 R4 自反性 反自反性 對稱性 反對稱性 傳遞性 R1 Y N N Y Y R2 N Y N Y N R3 Y N Y N Y R4 Y N Y Y Y 1。 。 2。 (自反和反自反性除外 ) R