【文章內(nèi)容簡(jiǎn)介】 3 。 33 離散數(shù)學(xué) 例 X={a,b,c}。則關(guān)系 R1={(a,a),(a,b) ,(a,c) ,(c,b) ,(c,c)} 是 X上的反對(duì)稱關(guān)系；而關(guān)系 R2={(a,a),(a,b) ,(a,c) ,(b,a) ,(c,b)} 不是 X上的反對(duì)稱關(guān)系；因 (a,b)? R2 且 (b,a)? R2 ,但a?b。 4176。 傳遞關(guān)系 (transitive relation)：當(dāng)且僅當(dāng) R滿足 傳遞性： (?x?X)(?y?X)(?z?X)(xRy ? yRz?xRz)； ?反傳遞關(guān)系 (antisymmetric relation)： 當(dāng)且僅當(dāng) R滿足 反傳遞性： (?x?X)(?y?X)(?z?X)(xRy ? yRz? ) ； ?常見(jiàn)的 傳遞關(guān)系有相等關(guān)系 (=)，小于等于關(guān)系 (?)，包含關(guān)系 (?)，整除關(guān)系，同余關(guān)系，上下級(jí) xRz34 離散數(shù)學(xué) 關(guān)系，同鄉(xiāng)關(guān)系，后裔關(guān)系等； 而不相等關(guān)系 (?)，父子關(guān)系，朋友關(guān)系，同學(xué)關(guān)系等都不是傳遞關(guān)系。 注： ?傳遞性和反傳遞性是關(guān)系的兩個(gè)極端性質(zhì)；因此，傳遞關(guān)系和反傳遞關(guān)系是兩種極端關(guān)系； ?概念 反傳遞性和反傳遞關(guān)系一般不甚用，所以不加討論； 例 8. 設(shè) X={a,b,c,d} 。則關(guān)系 R1={(a,b),(b,c),(a,c),(c,d),(a,d),(b,d)} 是 X上的傳遞關(guān)系； 而關(guān)系 R2={(a,b),(b,c),(a,c),(c,d),(a,d)} 不是 X上的傳遞關(guān)系；因 (b,c)? R2且 (c,d)?R2， 但(b,d)? R2 。 35 離散數(shù)學(xué) 例 9. 設(shè) X是平面上直線的集合 。平行 關(guān)系 R={(x,y) : x?X ? y?X ? x∥ y} 由平面幾何的知識(shí)知 :若 x∥ y且 y∥ z，則 x∥ z 。 由傳遞關(guān)系的定義知 R是 X上的傳遞關(guān)系。 例 10. 設(shè) X是平面上三角形的集合 。相似 關(guān)系 R={(x, y) : x?X ? y?X ? x∽ y} 由平面幾何的知識(shí)知 :若 x∽ y 且 y∽ z ，則 x∽ z 。 由傳遞關(guān)系的定義知 R是 X上的傳遞關(guān)系。 例 11. ?相等關(guān)系是自反的、對(duì)稱的、 反對(duì)稱的、 傳遞關(guān)系。 ?全關(guān)系 X2是自反的、對(duì)稱的、傳遞的。 ?幺關(guān)系 I 是自反的、對(duì)稱的、反對(duì)稱的、傳遞的。 36 離散數(shù)學(xué) ?空關(guān)系 ?是反自反的、對(duì)稱的、反對(duì)稱的、傳遞的。 37 離散數(shù)學(xué) 167。 4 .關(guān)系的運(yùn)算 1176。 關(guān)系的逆運(yùn)算 定義 (converse operation) 設(shè) A， B是兩個(gè)非空的集合。我們稱一元運(yùn)算 : 2A B? 2 B A 對(duì)任何二元關(guān)系 R?A B，使得 = {(b,a) : b?B?a?A?aRb}?B A 為關(guān)系的逆運(yùn)算； 稱 是 R的逆關(guān)系 (converse of relation)。 顯然，對(duì)任何 (b,a)? B A， b a ?aRb ；并且 。 RRRRTRRMM?? 38 離散數(shù)學(xué) 例 A={a,b,c} ， B={1,2}。則關(guān)系 R={(a,1),(a,2),(b,2),(c,1)} 的逆關(guān)系 ={(1,a),(2,a),(2,b),(1,c)} 。 定理 設(shè)兩個(gè)關(guān)系 R ? A B， S ?A B，這里 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 。 (4)對(duì)任何 (a,b)?B A ，有 (a,b)?R?S ? (b,a)?R?S R?R SRRR40 離散數(shù)學(xué) ? (b,a)?R?(b,a)? S ? (a,b)? ?(a,b)? ? (a,b)? ? 所以 R?S = ? 。 (7)對(duì)任何 (a,b)?B A ，有 (a,b)?(R?) ? (b,a)?R? ? (b,a)?R ? (a,b)? ? (a,b)?( )? 所以 (R?)= ( )? 。 R SRSRSRRR41 離散數(shù)學(xué) 2176。 關(guān)系的合成運(yùn)算 定義 (position operation) 設(shè) A， B是兩個(gè)非空的集合。我們稱二元運(yùn)算 o : 2A B 2B C ? 2 A C 對(duì)任何兩個(gè)二元關(guān)系 R ?A B ， S ?B C ，使得 RoS ={(a,c) : a?A?c?C?(?b?B)(aRb?bSc)}?A C 為關(guān)系的合成運(yùn)算； 稱 RoS是 R與 S的合成關(guān)系。 顯然，對(duì)任何 (a,c)?A C， aRoSc?(?b?B)(aRb?bSc) 。 例 2 .設(shè) A={ a1,a2,a3} ， B={b1,b2} ， C={c1, c2, c3, c4} 關(guān)系 R?A B ， S?B C R ={(a1, b1),(a2, b2),(a3, b1)} S ={(b1, c4),(b2, c2),(b2, c3)} 42 離散數(shù)學(xué) 于是，我們得到 R與 S的合成關(guān)系為 R o S ={(a1, c4),(a2, c2) ,(a2, c3),(a3, c4)} 其合成關(guān)系的關(guān)系圖為 例 A是老年男子的集合， B是中年男子的集合， C是青少年男子的集合。 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)系。 定理 設(shè) R,R1,R2 ? A B， S,S1,S2 ? B C， T ? C D ，這里 A,B,C,D是四個(gè)非空的集合。則 (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)結(jié)合律： R o (S o T) = (R o S) o T； (5)左分配律： R o (S1∪ S2) = (R o S1) ∪ (R o S2) ； (合成運(yùn)算對(duì)并的 ) 右分配律： (S1∪ S2) o T = (S1 o T) ∪ (S2 o T)； (合成運(yùn)算對(duì)并的 ) (6)左分配不等式： R o (S1∩S2) ?(R o S1)∩(R o S2)； 44 離散數(shù)學(xué) (合成運(yùn)算對(duì)交的 ) 右分配不等式： (S1∩ S2) o T ?(S1 o T)∩(S2 o T)； (合成運(yùn)算對(duì)交的 ) (7) 鞋襪律： (R o S) = S o R 。 [證 ].只證 (4)， (5) （采用邏輯法） (4)對(duì)任何元素 a?A,d?D ，有 a R o (S o T)d ?(?b?B)(aRb ?b(S o T)d) ?(?b?B)(aRb ?(?c?C)(bSc?cTd)) ?(?b?B)(?c?C)(aRb?(bSc?cTd)) (量詞前移： p??xA(x)? ?x(p?A(x)) ) ? (?c?C)(?b?B)(aRb?(bSc?cTd)) (量詞交換： ?x?yA(x,y)??y?xA(x,y) ) 45 離散數(shù)學(xué) ? (?c?C)(?b?B)((aRb?bSc)?cTd) (?的 結(jié)合律： p?(q ? r)?(p ? q )? r ) ? (?c?C)((?b?B)(aRb?bSc)?cTd) (量詞后移： ?x(p?A(x)) ? p??xA(x) ) ? (?c?C)(a(R o S)c?cTd) ? a(R o S) o Td 所以 R o (S o T) = (R o S) o T； (5)對(duì)任何元素 a?A,c?C ，有 a R o (S1∪ S2)c ?(?b?B)(aRb ?b(S1∪ S2)c) ?(?b?B)(aRb ?(bS1c?bS2c)) ?(?b?B)((aRb?bS1c)?(aRb?bS2c)) (?對(duì) ?的分配律： p?(q?r)?(p ? q ) ? (p ? r ) ) 46 離散數(shù)學(xué) ?(?b?B)(aRb?bS1c)?(?b?B)(aRb?bS2c) (?量詞 對(duì) ?的分配律 ： ?x(A(x)?B(x)) ??x(A(x)??xB(x) ) ?a(R o S1)c ?a (R o S2)c ? a(R o S1)∪ (R o S2)c 所以 R o (S1∪ S2) = (R o S1)∪ (R o S2) 。 ?但是合成運(yùn)算不滿足交換律。即，一般 R o S?S o R 例 A={a,b,c,d,e} 。則關(guān)系 R={(a,b),(c,d),(b,b)}， S={(b,e),(c,a),(a,c),(d,b)} 的 合成關(guān)系為 47 離散數(shù)學(xué) R o S= {(a,e),(b,e),(c,b)}， So R ={(a,d),(c,b),(d,b)} 所以 R o S?S o R 。 3176。 關(guān)系矩陣的合成運(yùn)算 設(shè) R? A B ， S?B C 是兩個(gè)二元關(guān)系，其 合成關(guān)系為 R o S。這里 A={ a1,a2,? ,am} ， B={b1,b2 , ? , bl} ，C={c1, c2, ? ,}。 并設(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ù)學(xué) 注：這里關(guān)系矩陣的合成運(yùn)算與 《 線性代數(shù) 》 中的一般矩陣的乘法運(yùn)算頗為相似。所不同的是：乘法現(xiàn)在換成布爾乘 (?)；加法現(xiàn)在換成布爾加 (?)。值得注意的是：這里的布爾加 1 ? 1=1（不進(jìn)位），而非 1 ? 1=0（進(jìn)位）。 例 A=