【正文】 b?R ； (3)() ?a?R∩ ?b?R≠? ? ?a?R = ?b?R (? aRb，即 (a,b)?R) ； () (a,b)?R ? ?a?R∩ ?b?R = ? ； (4)兩個(gè)等價(jià)類 ?a?R和 ?b?R ，要么完全重合 (即 ?a?R = ?b?R )，要么不交 (即 ?a?R∩ ?b?R = ? )；二者必居其一，也只居其一 。 R是 N上的模 m同余關(guān)系，即 R={(a,b) : a? N ? b? N ? a ? b (mod m)} 。我們定義 集合 ? R = {?a?R : a?A} (注意：應(yīng)去掉重復(fù)的類！ ) 為集合 A關(guān)于等價(jià)關(guān)系 R的商集。 定義 類 (塊 )(equivalence classes(block)) 設(shè) R是非空集合 A上的等價(jià)關(guān)系。 例 A上的幺關(guān)系、全關(guān)系都是等價(jià)關(guān)系。 例 2 .平面幾何中的三角形間的相似關(guān)系是等價(jià)關(guān)系。 等價(jià)關(guān)系和等價(jià)類 定義 (equivalence relation) 設(shè)二元關(guān)系 R? A A。則 (1)若 m?N，則 Rm ? R* ；特別地 I? R* ， R ? R* ； (2) R*是自反傳遞關(guān)系：即，對(duì)任何元素 a?A ， aR*a ； 58 離散數(shù)學(xué) 對(duì)任何元素 a， b， c ? A ， aR*b?bR*c?aR*c ； (3) R*是包含 R的最小自反傳遞關(guān)系：即，對(duì)任何二元關(guān)系 S?A A，若 R?S且 S也是自反傳遞關(guān)系，那么 R*?S ； (4)若 |A|=n ， 則 R* = Rk ；這時(shí) a R*b ? (?k?N)(0?k?n)(aRkb) ? (a=b)?(?k?N)(1?k?n)(aRkb) ； (5)若 R是自反傳遞關(guān)系 , 則 R* = R 。 定理 設(shè)二元關(guān)系 R? A A， R?? 。 RR RRRR R54 離散數(shù)學(xué) 定義 (closure operation) 設(shè)二元關(guān)系 R ?A A 。 例 二元關(guān)系 R? A A,這里 A={a,b,c} ,R={(a,b),(c,b)}。則 (1)交換律： RmoRn = RnoRm= Rm+n ； 特別地： IoR = RoI= R (幺關(guān)系是合成運(yùn)算的幺元 )； (2)交換律： (Rm)n = (Rn)m= Rm?n 。這里 A 是一個(gè)非空的集合， N 是自然數(shù)集。 ) ? (xi1 ? y1j ) ? (xi2 ? y2j ) ? ?? (xil ? ylj ) =1 (這里： ?是 布爾乘 ； ?是 布爾加 。值得注意的是：這里的布爾加 1 ? 1=1（不進(jìn)位），而非 1 ? 1=0（進(jìn)位）。 關(guān)系矩陣的合成運(yùn)算 設(shè) R? A B ， S?B C 是兩個(gè)二元關(guān)系，其 合成關(guān)系為 R o S。 ?但是合成運(yùn)算不滿足交換律。 R是 由 A到 B的父子關(guān)系， R? A B b1 b2 B a1 a2 a3 A c1 c2 c3 c4 C R S RoS 43 離散數(shù)學(xué) S 是由 B到 C的父子關(guān)系， S?B C 則復(fù)合關(guān)系 R o S是 A到 C的祖孫關(guān)系。 關(guān)系的合成運(yùn)算 定義 (position operation) 設(shè) A， B是兩個(gè)非空的集合。則有 (1)反身律： =R ； (2)保序性： R?S ? ? ； R=S ? = ； (3)分配律： R?S= ? （逆對(duì)并的）； (4)分配律： R?S= ? （逆對(duì)交的）； (5)X Y=Y X ； RRRSRSR SR S39 離散數(shù)學(xué) (6) =? ； (7)交換律： (R?)=( )? （逆與余的）； (8)分配律： R\S= \ （逆對(duì)差的）； [證 ].只證 (1)， (4)， (7) （采用邏輯法） (1)對(duì)任何 (a,b)?A B ，有 (a,b)? ? (b,a)? ? (a,b)?R 所以 =R 。 顯然，對(duì)任何 (b,a)? B A， b a ?aRb ；并且 。 37 離散數(shù)學(xué) 167。 例 11. ?相等關(guān)系是自反的、對(duì)稱的、 反對(duì)稱的、 傳遞關(guān)系。 由傳遞關(guān)系的定義知 R是 X上的傳遞關(guān)系。 注： ?傳遞性和反傳遞性是關(guān)系的兩個(gè)極端性質(zhì)；因此，傳遞關(guān)系和反傳遞關(guān)系是兩種極端關(guān)系； ?概念 反傳遞性和反傳遞關(guān)系一般不甚用，所以不加討論； 例 8. 設(shè) X={a,b,c,d} 。 33 離散數(shù)學(xué) 例 X={a,b,c}。 反對(duì)稱關(guān)系 (antisymmetric relation)：當(dāng)且僅當(dāng) R滿足 反對(duì)稱性： (?x?X)(?y?X)(xRy?yRx?x = y) ； ?常見(jiàn)的 對(duì)稱關(guān)系有相等關(guān)系 (=)，不相等關(guān)系 (?)，同余關(guān)系，朋友關(guān)系，同學(xué)關(guān)系，同鄉(xiāng)關(guān)系等； 而小于等于關(guān)系 (?)，包含關(guān)系 (?)，上下級(jí)關(guān)系，父子關(guān)系等都不是對(duì)稱關(guān)系，它們都是反對(duì)稱關(guān)系。則關(guān)系 R1={(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)} 是 X上的自反關(guān)系 ,但不是 X上的幺關(guān)系 ,因 (a,b), (c,d)?R1；而關(guān)系 R2 ={(a,a),(b,b),(c,c),(d,d)} 是 X上的自反關(guān)系 ,同時(shí)也是 X上的幺關(guān)系； R3={(a,b),(a,c),(a,d),(c,d)} 31 離散數(shù)學(xué) 是 X上的反自反關(guān)系。 自反關(guān)系 (reflexive relation)：當(dāng)且僅當(dāng) R滿足 自反性： (?x?X)(xRx) ； 顯然，對(duì)于 自反關(guān)系 R， ? (R) = ? (R) = X 。 注： ?圖中各結(jié)點(diǎn)所帶的小圓圈稱為自反圈；一對(duì)結(jié)點(diǎn)間的來(lái)回邊稱為雙向?。环駝t，一對(duì)結(jié)點(diǎn)間只有一條邊，則此邊稱為單向弧。 ?所有有向弧的始端結(jié)點(diǎn)構(gòu)成 ? (R)；所有有向弧的終端結(jié)點(diǎn)構(gòu)成 ? (R)。 關(guān)系的圖形表示法 設(shè)關(guān)系 R?A B ， 這里 A,B是兩個(gè)非空的有限集合， A={ a1,a2,a3,? ,am } ， B={ b1,b2,b3,? ,bn } 。 關(guān)系的矩陣表示法 設(shè)關(guān)系 R?A B ， 這里 A,B是兩個(gè)非空的有限集合， A={ a1,a2,a3,…,a m } ， B={ b1,b2,b3,…,b n } 。 例 .設(shè) A={a,b,c,d}，并且設(shè) R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。 于是，類似于定理 1(2)，定理 2(2)(4)，我們有 定理 .設(shè) R? A B是一個(gè)二元關(guān)系， A1 ,A2? A 。 且看下面的反例 。 ?次證： ? (R1 ∪ R2) ? ? (R1)∪ ? (R2) (采用元素 離散數(shù)學(xué) 20 離散數(shù)學(xué) 法 ) 對(duì)任何元素 a ?A ， 若 a ? ? (R1∪ R2)， 則存在 b?B ， 使得 a R1 ∪ R2 b 因此 (a,b)?R1 ∪ R2 ， 從而有 (a,b)?R1 或者 (a,b)?R2 即 aR1b 或者 aR2b 于是 a ? ? (R１ ) 或者 a ? ? (R2 ) 故此 a ? ? (R1)∪ ? (R2) 21 離散數(shù)學(xué) 所以 ? (R1 ∪ R2) ? ? (R1)∪ ? (R2) 。若 R1 ? R2 ，則 (1)保序性： ? (R1) ? ? (R2) ； (2)保序性： ? (R1) ? ? (R2) ； [證 ].只證 (1) （采用邏輯法）對(duì)任何元素 a ?A， a ? ? (R1 ) ? a?A?(?b?B)(a R1 b) ? a?A?(?b?B)((a,b)?R1) ? a?A?(?b?B)((a,b)?R2) (條件： R1 ? R2 ) ? a?A?(?b?B)(a R2 b) ? a ? ? (R2 ) 所以 ? (R1) ? ? (R2) 。 例 9 .設(shè) A={1,2,3,4} ， B={2,4,6,8,10} 。 5176。 空關(guān)系 (empty relation)： 關(guān)系 R= ?稱為空關(guān)系； ?空關(guān)系和全關(guān)系都是平凡關(guān)系； 3176。 R= { (a,b) : a?A?b?B?a調(diào)用 (call)b }?A?A 則 R就是程序塊集合上的 調(diào)用 關(guān)系。 13 離散數(shù)學(xué) R= { (a,b) : a?N?b?N?a|b }? N N 則 R就是自然數(shù)集合上的整除關(guān)系。 aRbaRb aRb12 離散數(shù)學(xué) R={(a,b) : a?A?b?A?a與 b是同鄉(xiāng) }?A A 于是， R是西安交通大學(xué)同學(xué)之間的同鄉(xiāng)關(guān)系。 2 .關(guān)系 一 .關(guān)系的基本概念 定義 1 .二元關(guān)系 (binary relation) 設(shè) A,B是兩個(gè)非空的集合。 定理 2 . 設(shè) A,B,C是三個(gè)集合。 定理 A,B,C,D是四個(gè)非空的集合。 定義 2. ? 二個(gè)集合 A， B的 (二維或二重 )叉積定義為 A B ={(a, b): a? A ?b?B} ； ?其元素 —— 二元組 (a, b)通常稱為序偶或偶對(duì) (ordered pair) ； ?二元組 (a, b)的 第一分量上的元素 a稱為前者； 第二分量上的元素 b稱為后者； ?二重叉積的 A? B第一 集合 A稱為前集； 第二 集合 B稱為后集。 6. 半序關(guān)系 4 離散數(shù)學(xué) 167。 2 .關(guān)系 167。 1 . 集合的叉積 n元組 167。 5. 等價(jià)關(guān)系 167。這里是其概念的推廣。 即 A ? = ? = ? A 由于若偶對(duì)的第一分量或第二分量不存在就沒(méi)有偶對(duì)存在，故規(guī)定它們的叉積集合為空集是合理的。 ?)： （采用邏輯法） 對(duì)任何的元素 a,b a?A?b?B ?(a,b)?A B ?(a,b)?C D (條件： A B = C D ） ? a?C?b?D 所以 A = C ? B = D 。 11 離散數(shù)學(xué) 167。 例 1 . 設(shè) A是西安交通大學(xué)全體同學(xué)組成的集合 。 例 3 . 設(shè) N是自然數(shù)集合。 例 5 . 設(shè) A是某一大型 FORTRAN程序中諸程序塊的集合。 全關(guān)系 (full relation)： 關(guān)系 R=A?B稱為全關(guān)系； 2176。 R=小于關(guān)系 ={(m,n) : m?N?n?N?m?n}?N?N S=整除關(guān)系 ={(m,n) : m?N?n?N?m|n}?N ?N 則 R? =大于等于關(guān)系 (?)； R?S=小于等于關(guān)系 (?) ； 16 離散數(shù)學(xué) R?S=不相等的 整除關(guān)系 (???)； R\S=小于又 不 整除關(guān)系 (? ??)； S\R=相等 關(guān)系 (=