【正文】 {(b,e),(c,a),(a,c),(d,b)} 的 合成關系為 47 離散數學 R o S= {(a,e),(b,e),(c,b)}， So R ={(a,d),(c,b),(d,b)} 所以 R o S?S o R 。 ?但是合成運算不滿足交換律。則 (1)R o ? = ? o S = ?； (2)?( R o S ) ??( R )； ?( R o S ) ??(S )； (3)保序性： R1 ?R2 ? S1 ? S2 ? R1 o S1 ?R2 o S2 ； (4)結合律： R o (S o T) = (R o S) o T； (5)左分配律： R o (S1∪ S2) = (R o S1) ∪ (R o S2) ； (合成運算對并的 ) 右分配律： (S1∪ S2) o T = (S1 o T) ∪ (S2 o T)； (合成運算對并的 ) (6)左分配不等式： R o (S1∩S2) ?(R o S1)∩(R o S2)； 44 離散數學 (合成運算對交的 ) 右分配不等式： (S1∩ S2) o T ?(S1 o T)∩(S2 o T)； (合成運算對交的 ) (7) 鞋襪律： (R o S) = S o R 。 R是 由 A到 B的父子關系， R? A B b1 b2 B a1 a2 a3 A c1 c2 c3 c4 C R S RoS 43 離散數學 S 是由 B到 C的父子關系， S?B C 則復合關系 R o S是 A到 C的祖孫關系。 顯然，對任何 (a,c)?A C， aRoSc?(?b?B)(aRb?bSc) 。 關系的合成運算 定義 (position operation) 設 A， B是兩個非空的集合。 (7)對任何 (a,b)?B A ，有 (a,b)?(R?) ? (b,a)?R? ? (b,a)?R ? (a,b)? ? (a,b)?( )? 所以 (R?)= ( )? 。則有 (1)反身律： =R ； (2)保序性： R?S ? ? ； R=S ? = ； (3)分配律： R?S= ? （逆對并的）； (4)分配律： R?S= ? （逆對交的）； (5)X Y=Y X ； RRRSRSR SR S39 離散數學 (6) =? ； (7)交換律： (R?)=( )? （逆與余的）； (8)分配律： R\S= \ （逆對差的）； [證 ].只證 (1)， (4)， (7) （采用邏輯法） (1)對任何 (a,b)?A B ，有 (a,b)? ? (b,a)? ? (a,b)?R 所以 =R 。則關系 R={(a,1),(a,2),(b,2),(c,1)} 的逆關系 ={(1,a),(2,a),(2,b),(1,c)} 。 顯然，對任何 (b,a)? B A， b a ?aRb ；并且 。 關系的逆運算 定義 (converse operation) 設 A， B是兩個非空的集合。 37 離散數學 167。 ?幺關系 I 是自反的、對稱的、反對稱的、傳遞的。 例 11. ?相等關系是自反的、對稱的、 反對稱的、 傳遞關系。相似 關系 R={(x, y) : x?X ? y?X ? x∽ y} 由平面幾何的知識知 :若 x∽ y 且 y∽ z ，則 x∽ z 。 由傳遞關系的定義知 R是 X上的傳遞關系。 35 離散數學 例 9. 設 X是平面上直線的集合 。 注： ?傳遞性和反傳遞性是關系的兩個極端性質；因此，傳遞關系和反傳遞關系是兩種極端關系； ?概念 反傳遞性和反傳遞關系一般不甚用，所以不加討論； 例 8. 設 X={a,b,c,d} 。 4176。 33 離散數學 例 X={a,b,c}。即 xij = xji (1?i,j ? n)； 反 對稱 關系的 關系矩陣滿足如下性質 xij = 1 ? xji = 0 (1?i,j ? n) ； ?從 關系圖來看： 對稱關系 關系圖的結點間若有弧則都是雙向?。环磳ΨQ關系 關系圖的結點間若有弧則都是單向??； 例 X={a,b,c}。 反對稱關系 (antisymmetric relation)：當且僅當 R滿足 反對稱性： (?x?X)(?y?X)(xRy?yRx?x = y) ； ?常見的 對稱關系有相等關系 (=)，不相等關系 (?)，同余關系，朋友關系，同學關系，同鄉(xiāng)關系等； 而小于等于關系 (?)，包含關系 (?)，上下級關系，父子關系等都不是對稱關系，它們都是反對稱關系。 2176。則關系 R1={(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)} 是 X上的自反關系 ,但不是 X上的幺關系 ,因 (a,b), (c,d)?R1；而關系 R2 ={(a,a),(b,b),(c,c),(d,d)} 是 X上的自反關系 ,同時也是 X上的幺關系； R3={(a,b),(a,c),(a,d),(c,d)} 31 離散數學 是 X上的反自反關系。 xRx30 離散數學 注： ?自反性和反自反性是關系的兩個極端性質；因此，自反關系和反自反關系是兩種極端關系； ?從 關系矩陣來看： 自反關系 關系矩陣的對角線上元素全是 1；反自反關系 關系矩陣的對角線上元素全是 0； ?從 關系圖來看： 自反關系 關系圖的各結點上全都有自反圈；反自反關系 關系圖的各結點上全都沒有自反圈。 自反關系 (reflexive relation)：當且僅當 R滿足 自反性： (?x?X)(xRx) ； 顯然，對于 自反關系 R， ? (R) = ? (R) = X 。 a1 a2 a3 a4 b1 b2 b3 R A B GR a1 a2 a3 GS 29 離散數學 二 .關系的性質 設二元關系 R?X X(或者說 R?X2)，這里 X??是一集合。 注： ?圖中各結點所帶的小圓圈稱為自反圈；一對結點間的來回邊稱為雙向??；否則，一對結點間只有一條邊，則此邊稱為單向弧。 例 3 .設關系 R?A B， A={ a1,a2,a3,a4 }， B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)} 于是，我們得到 R的關系圖 GR為下面左圖。 ?所有有向弧的始端結點構成 ? (R)；所有有向弧的終端結點構成 ? (R)。 ? VR =A?B， ER =R； ? VR中的元素稱為結點，用小圓點表示；表示 A中元素的結點放在左邊一塊；表示 B中元素的結點放在右邊一塊； ? ER中的元素稱為邊，用有向弧表示；若 aRb(即(a,b)?R)，則在表示 a的結點和表示 b的結點之間連一條有向弧。 關系的圖形表示法 設關系 R?A B ， 這里 A,B是兩個非空的有限集合， A={ a1,a2,a3,? ,am } ， B={ b1,b2,b3,? ,bn } 。 MR=(xij)m n ，其中 1 當（ ai,bj) ? R時 xij = ( i=1,…,m ； j=1,…,n) 0 當（ ai,bj) ? R時 25 離散數學 例 1 .設關系 R?A B ， A={ a1,a2,a3,a4 } ， B={b1,b2,b3} R ={ (a1, b2),(a1, b3),(a2, b3),(a3, b1),(a4, b2)}。 關系的矩陣表示法 設關系 R?A B ， 這里 A,B是兩個非空的有限集合， A={ a1,a2,a3,…,a m } ， B={ b1,b2,b3,…,b n } 。 24 離散數學 167。 例 .設 A={a,b,c,d}，并且設 R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。 ?23 離散數學 [證 ].仿定理 1(2)，定理 2(2)(4)可證。 于是，類似于定理 1(2)，定理 2(2)(4)，我們有 定理 .設 R? A B是一個二元關系， A1 ,A2? A 。 則，由于 R1 ∩ R2 = ? ，故 ? (R1 ∩ R2) = ? 但是， 由于 ? (R1) = {1,2 } ， ? (R2) = {1,2} 故 ? (R1)∩? (R2) = {1,2 } 22 離散數學 所以 ? (R1)∩? (R2) ? (R1 ∩ R2) 。 且看下面的反例 。 2定理 2的 (3?) ， 就可得 ? (R1 ∩ R2) ? ? (R1)∩? (R2) 。 ?次證： ? (R1 ∪ R2) ? ? (R1)∪ ? (R2) (采用元素 離散數學 20 離散數學 法 ) 對任何元素 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 離散數學 所以 ? (R1 ∪ R2) ? ? (R1)∪ ? (R2) 。則 (1)? (R1 ∪ R2) = ? (R1)∪ ? (R2) (2)? (R1 ∪ R2) = ? (R1)∪ ? (R2) (3)? (R1 ∩ R2) ? ?(R1)∩? (R2) (4)? (R1 ∩ R2) ? ? (R1)∩? (R2) [證 ].只證 (1)， (3) (1)?先證： ? (R1)∪ ? (R2) ? ? (R1 ∪ R2) (采用包含法 ) 由于 R1 ? R1 ∪ R2， R2 ? R1 ∪ R2 ， 依定理 1， 有 ? (R1) ? ? (R1∪ R2)， ? (R2) ? ? (R1∪ R2) 故根據第一章 167。若 R1 ? R2 ，則 (1)保序性： ? (R1) ? ? (R2) ； (2)保序性： ? (R1) ? ? (R2) ； [證 ].只證 (1) （采用邏輯法）對任何元素 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) 。 則 ? (R) = {1,2,3}?A ， ? (R) = {2,4,6}?B 。 例 9 .設 A={1,2,3,4} ， B={2,4,6,8,10} 。 n元關系： n元關系