【正文】 則 R的 等價類之 集 ?R = { ?a?R : a?A } 是 A上的一個劃分；等價類就是 劃分塊 。 定理 4 。則 A的 (1)覆蓋是一集合之集 ?={A? : ????A?≠?}，滿足條件： 74 離散數(shù)學 A ? ； (2)劃分是一集合之集 ?={A? : ????A?≠?}，滿足條件： (a) A = ； (b)?1≠?2?A?1∩A?2 = ? ； 其中 A?稱為 劃分 ?的劃分塊 (block of partition)。 2176。 ?由 定理 3知，等價關(guān)系與等價類集合一一對應(yīng)。 [證 ].(采用邏輯法 ) R=S ?R?S?S?R ? (?a?A)(?a?R ? ?a?S)?(?a?A)(?a?S ? ?a?R) (定理 2) ? (?a?A)(?a?R ? ?a?S??a?S ? ?a?R) (?量詞 對 ?的分配律 ： 73 離散數(shù)學 ?x(A(x)??xB(x) ? ?x(A(x)?B(x)) ) ?(?a?A)(?a?R = ?a?S) 。 定理 R和 S是非空集合 A上的兩個等價關(guān)系。則 R?S?(?a?A)(?a?R? ?a?S) 。 則 (1)A上最細的 等價 關(guān)系是幺關(guān)系；即 R細 =IA ， A/R細 ={{a} : a?A} ； (2)A上最粗的 等價 關(guān)系是全關(guān)系；即， R粗 =A A ， A/R粗 ={A} 。若R?S ，則我們稱 R細于 S ， 或 S粗于 R 。否則若 ?a?R∩?b?R≠? ? ?a?R = ?b?R (本定理的 ()) ?aRb (本定理的 (2)) ?(a,b)?R 這就與已知條件： (a,b)?R 矛盾； (4)對任何序偶 (a,b) (a,b)?A A ?(a,b)?R?(a,b)?R (二分法，互斥 ) ?(?a?R = ?b?R)?(?a?R∩ ?b?R = ?) (本定理的 ()和 ()，互斥 ) 。對任意的 a,b?A，有 (1)a??a?R (故 ?a?R ≠?) ； (2)aRb (即 (a,b)?R) ? ?a?R = ?b?R ； (3)() ?a?R∩ ?b?R≠? ? ?a?R = ?b?R (? aRb，即 (a,b)?R) ； () (a,b)?R ? ?a?R∩ ?b?R = ? ； (4)兩個等價類 ?a?R和 ?b?R ，要么完全重合 (即 ?a?R = ?b?R )，要么不交 (即 ?a?R∩ ?b?R = ? )；二者必居其一，也只居其一 。 例 8中 等價關(guān)系 R的 等價類為 ?a?R = {a}, ?b?R = ?c?R = {b,c} ； 其商集為 A/R= ?R = {?a?R , ?b?R }={{a},{b,c}}； 故其秩為 2。 R是 N上的模 m同余關(guān)系，即 R={(a,b) : a? N ? b? N ? a ? b (mod m)} 。稱 A/R中元素的個數(shù)為 R的秩。我們定義 集合 ? R = {?a?R : a?A} (注意：應(yīng)去掉重復的類！ ) 為集合 A關(guān)于等價關(guān)系 R的商集。同時稱 a為等價類 ?a?R的代表元。 定義 類 (塊 )(equivalence classes(block)) 設(shè) R是非空集合 A上的等價關(guān)系。 例 二元關(guān)系 R? A A,這里 A={a,b,c} , R={(a,a), (b,b), (c,c), (b,c),(c,b)} 則 R是 A上的等價關(guān)系。 例 A上的幺關(guān)系、全關(guān)系都是等價關(guān)系。 61 離散數(shù)學 例 4 .平面幾何中的直線間的平行關(guān)系是等價關(guān)系。 例 2 .平面幾何中的三角形間的相似關(guān)系是等價關(guān)系。 R是 A上的等價關(guān)系 ?R是自反的、對稱的、傳遞的。 等價關(guān)系和等價類 定義 (equivalence relation) 設(shè)二元關(guān)系 R? A A。 60 離散數(shù)學 167。則 (1)若 m?N，則 Rm ? R* ；特別地 I? R* ， R ? R* ； (2) R*是自反傳遞關(guān)系：即，對任何元素 a?A ， aR*a ； 58 離散數(shù)學 對任何元素 a， b， c ? A ， aR*b?bR*c?aR*c ； (3) R*是包含 R的最小自反傳遞關(guān)系：即，對任何二元關(guān)系 S?A A，若 R?S且 S也是自反傳遞關(guān)系，那么 R*?S ； (4)若 |A|=n ， 則 R* = Rk ；這時 a R*b ? (?k?N)(0?k?n)(aRkb) ? (a=b)?(?k?N)(1?k?n)(aRkb) ； (5)若 R是自反傳遞關(guān)系 , 則 R* = R 。 [證 ].只證 (2)(采用邏輯法 ) (2)對任何元素 a， b， c ? A ，有 aR＋ b?bR＋ c ?(?k)(aRkb)?(?l)(bRlc) (這里 k ?1, l ?1) ?(?x1)(?x2) ? (?xk1)(aRx1 ? x1Rx2 ? ? ? xk1Rb) ? (?y1)(?y2) ? (?yl1)(bRy1 ? y1Ry2 ? ? ? yl1Rc) ?(?x1)(?x2) ? (?xk1)(aRx1 ? x1Rx2 ? ? ? xk1Rb ? (?y1)(?y2) ? (?yl1)(bRy1 ? y1Ry2 ? ? ? yl1Rc)) (量詞前移： ?xA(x)?p??x(A(x)?p) ) ?(?x1)(?x2) ? (?xk1)(?y1)(?y2) ? (?yl1)(aRx1 ? x1Rx2 ? ? ? xk1Rb? bRy1 ? y1Ry2 ? ? ? yl1Rc) 57 離散數(shù)學 (量詞前移： p??xA(x)??x(p?A(x)) ) ?(?x1)(?x2) ? (?xk1)(?xk)(?xk+1)(?xk+2) ? (?xk+l1)(aRx1 ?x1Rx2? ? ?xk1Rxk?xkRxk+1?xk+1Rxk+2 ? ? ?xk+l1Rc) (這里，我們令： xk=b , xk+1=y1, xk+2 =y2 , ? , xk+l1= yl1) ?(?n)(aRnc) (這里，我們令： n=k+l ?1+1 ?1 ) ? aR＋ c 所以， R＋ 是傳遞的。 定理 設(shè)二元關(guān)系 R? A A， R?? 。 我們定義： (1)傳遞閉包 (transitive closure)： R＋ = Rk =R∪ R２ ∪ R3 ∪ ? ∪ Rk ∪ ? ； (2)自反傳遞閉包 (reflexive and transitive closure)： R? = Rk =I∪ R∪ R２ ∪ R3 ∪ ? ∪ Rk ∪ ? 。 RR RRRR R54 離散數(shù)學 定義 (closure operation) 設(shè)二元關(guān)系 R ?A A 。 注： ? 這個例子說明一般情況下 逆 關(guān)系不 是 關(guān)系合成運算的逆元； ? 由定理 2的 (1)有： ? o R = R o ? = ? ， 這說明 空集是 合成運算的零元 。 例 二元關(guān)系 R? A A,這里 A={a,b,c} ,R={(a,b),(c,b)}。 歸納變量選取 n（讓 m固定） n=0時， RmoR0 = RmoI (定義 3的 (1)： R0 =I) = Rm n=1時， RmoR1 = RmoR (定義 3的 (2)： R1 =R) = Rm+1 (定義 3的 (3)) 結(jié)論成立； n=k時，假設(shè) 結(jié)論成立。則 (1)交換律： RmoRn = RnoRm= Rm+n ； 特別地： IoR = RoI= R (幺關(guān)系是合成運算的幺元 )； (2)交換律： (Rm)n = (Rn)m= Rm?n 。 定理 設(shè)二元關(guān)系 R? A A， m ,n?N 。這里 A 是一個非空的集合， N 是自然數(shù)集。 1lk??51 離散數(shù)學 4176。 ) ? (xi1 ? y1j ) ? (xi2 ? y2j ) ? ?? (xil ? ylj ) =1 (這里： ?是 布爾乘 ； ?是 布爾加 。則關(guān)系 R={(a,b),(c,d),(b,b)}， S={(b,e),(c,a),(a,c),(d,b)} 的 合成 關(guān)系 R o S= {(a,e),(b,e),(c,b)} 其關(guān)系矩陣分別為 MR = MS= MR o S = 0 1 0 0 00 1 0 0 00 0 0 1 00000000000??????????0 0 1 0 00 0 0 0 11 0 0 0 00 1 0 0 000000??????????0 0 0 0 10 0 0 0 10 1 0 0 00000000000??????????49 離散數(shù)學 現(xiàn)在我們計算 MR o MS = = 其中： t25= (x2k ? yk5) =(x21?y15)?(x22?y25)?(x23?y35)?(x24?y45)?(x25?y55) =(0 ?0)? (1?1)? (0 ?0)? (0 ?0)? (0 ?0) =0 ? 1 ? 0? 0 ? 0 =1 這說明 MR o S = MR o MS 。值得注意的是：這里的布爾加 1 ? 1=1（不進位），而非 1 ? 1=0（進位）。 并設(shè)它們的關(guān)系矩陣分別為 MR=(xij)m l ， MS=(yij)l n ， MR o S =(uij)m n 則我們有： ? MR o S = MR o MS 其中：我們令 MR o MS = (tij)m n tij = (xik ? ykj) (1?i ? m,1 ? j ? n) 1lk??1lk??48 離散數(shù)學 注：這里關(guān)系矩陣的合成運算與 《 線性代數(shù) 》 中的一般矩陣的乘法運算頗為相似。 關(guān)系矩陣的合成運算 設(shè) R? A B ， S?B C 是兩個二元關(guān)系，其 合成關(guān)系為 R o S。則關(guān)系 R={(a,b),(c,d),(b,b)}， S=