【正文】 Rx) 從關(guān)系有向圖看對稱性 :在兩個不同的結(jié)點 之間，若有邊的話，則有方向相反的兩條邊。 鄰居關(guān)系是對稱關(guān)系，朋友關(guān)系是對稱關(guān)系。 1。 。 2。 1。 。 2。 3 3 3 3 1。 。 2。 1。 。 2。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 四 .反對稱性 定義 :設(shè) R為集合 A中關(guān)系 ,若對任何 x, y∈ A,如果有 xRy,和 yRx,就 有 x=y,則稱 R為 A中反對稱關(guān)系 。 從關(guān)系矩陣看反對稱性： 以主對角線為對稱的 兩個元素中最多有一個 1。 R 下邊 R R R R R8均是反對稱關(guān)系。 1。 。 2。 1。 。 2。 3 3 3 3 1。 。 2。 1。 。 2。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 五 . 傳遞性 定義 :R是 A中關(guān)系，對任何 x,y,z∈ A,如果有 xRy,和 yRz,就 有 xRz,則稱 R為 A中傳遞關(guān)系。 從關(guān)系關(guān)系圖和關(guān)系矩陣中不易看清是否有傳遞性。 檢查時要特別注意使得傳遞定義表達式的前件為 F的時候 此表達式為 T，即是傳遞的。 例如 A={1,2},下面 A中關(guān)系 R是傳遞的 . 通過帶量詞的公式在論域展開式說明 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) ??x?y?z((xRy?yRz)?xRz) (為了簡單做些刪改 ) ? ?y?z((1Ry?yRz)?1Rz)??y?z((2Ry?yRz)?2Rz) ? (?z((1R1?1Rz)?1Rz)??z((1R2?2Rz)?1Rz) ?(?z((2R1?1Rz)?2Rz) ?(?z((2R2?2Rz)?2Rz)) ?(((1R1?1R1)?1R1)?((1R1?1R2)?1R2)) ? (((1R2?2R1)?1R1)?((1R2?2R2)?1R2)) ? (((2R1?1R1)?2R1)? ((2R1?1R2)?2R2)) ? (((2R2?2R1)?2R1)) ? ((2R2?2R2)?2R2)) ? (((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))? (((F?F)?F)? ((F?T)?F))?(((F?F)?F))?((F?F)?F))?T 1? ?2 下邊 R R R R R8均是傳遞的關(guān)系 。 2。 1。 。 2。 1。 。 2。 1。 。 2。 1。 。 。 (自反和反自反性除外 ) R 自反性 反自反性 對稱性 傳遞性 反對稱性 每個結(jié)點都有環(huán) 主對角線全是 1 每個結(jié)點都無環(huán) 主對角線全是 0 不同結(jié)點間如果有邊 ,則有方向相反的兩條邊 . 是以對角線為對稱 的矩陣 不同結(jié)點間 ,最多有一條邊 . 以主對角線為對稱的位置不會同時為 1 如果有邊 a,b,b,c,則也有邊 a,c. 或者定義的前件為假 . 如果 aij=1,且 ajk=1,則 aik=1 從關(guān)系的矩 陣 從關(guān)系的有向 圖 性 質(zhì) 判定 : 下面歸納這八個關(guān)系的性質(zhì)： Y有 N無 1。 。 2。 1。 。 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。 1。 。 2。 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是自反、對稱和傳遞的。 ⑵證對稱性 ：任取 x,y∈ I,設(shè) x,y∈ R, (要證出 y,x?R ) 由 R定義得 xy可被 3整除 , 即 xy=3n(n∈ I)， yx=(xy)=3n=3(n), 因 n∈ I, ∴ y,x∈ R, 所以 R對稱。 證畢 練習 2： 設(shè) R是集合 A上的一個自反關(guān)系 ,求證： R是對稱和傳遞的，當且僅當 a,b和 a,c在 R中 ,則有 b,c也在 R中。 設(shè) a,b?R 又 a,c?R， (要證出 b,c?R ) 因 R對稱的故 b,a?R,又已知 a,c?R 由傳遞性 得 b,c?R。 充分性 : 已知任意 a,b,c?A， 如 a,b和 a,c在 R中 ,則有 b,c也在 R中。 再證 R傳遞 ：任取 a,b,c?A 設(shè) a,b?R， b,c?R。 作業(yè) 第 113頁 ⑴、⑶、⑷ 44 關(guān)系的復合 二元關(guān)系除了可進行集合并、交、補等運算外， 還可以進行一些新的運算，先介紹由兩個關(guān)系生 成一種新的關(guān)系，即關(guān)系的復合運算。 b是 c的母親， c是 b的兒子。 SR?a b c R S :設(shè)是 R從 X到 Y的關(guān)系， S是從 Y到 Z的關(guān)系，則 R和 S的復合關(guān)系記作 R?S 。 (俗稱過河拆橋法 ) A={1,2,3} B={1,2,} C={1,2,3,4,5} R?A B S?B C ⑴ 枚舉法 R={1,2,2,3,2,4,3,1} S={1,2,2,1,2,3,3,4,4,2,4,5} 則 R?S={1,1,1,3,2,4,2,2,2,5,3,2} ⑵有向圖法 ⑶關(guān)系矩陣法 令 A={a1, a2,…, a m} B={b1, b2,…, b n} C={c1, c2,…, c t} R?A B S?B C 。 。 C 1 2 3 。 2。 A 1。 3。 。 B 1 2 3 。 。 。 4 5 SR? c11=(a11∧ b11)∨ (a12∧ b21)∨ ...∨ (a1n∧ bn1) = (a1k∧ bk1) (其中 ∧ 是邏輯乘 ,∨ 是邏輯加 ) cij=(ai1∧ b1j)∨ (ai2∧ b2j)∨ ...∨ (ain∧ bnj) = (aik∧ bkj) (1≤i≤m, 1≤j≤t) MS MR a1,b1a1,b2...al,bn a2,b1a2,b2...a2,bn ... ... am,b1am,b2...am,bn (aij) b1,c1b1,c2...bl,ct b2,c1b2,c2...b2,ct ... ... bn,c1bn,c2...bn,ct (bij) a1,c1...al,ct a2,c1...a2,ct ... ... am,c1...am,ct M SR?(cij) 0 1 0 0 0 0 1 1 1 0 0 0 3 4 。下面列舉一例 來驗證。 1。 3。 。 B a b c 。 2。 A R IB 。 。 d 。 。 d 1。 3。即 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。 ...如果 x,y?Rk,表明在 R圖上有從 x到 y有 k條邊 (長為 k)的路徑 。 一 .定義 R是從 A到 B的關(guān)系，如果將 R中的所有序偶的 兩個元素的位置互換，得到一個從 B到 A的關(guān)系， 稱之為 R的逆關(guān)系，記作 RC，或 R1。 3. RC的矩陣 M =(MR)T 即為 R矩陣的轉(zhuǎn)置。 3. (R∩S)C = RC∩SC 。 RC 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 MR= 3 4 0 0 0 1 0 1 0 1 1 MR = c 4 3 證明 1.：任取 y,x?(R∪ S)C，則 y,x?(R∪ S)C ? x,y?R∪ S ? x,y?R∨ x, y?S ? y,x?RC∨ y,x?SC ?y,x? RC∪ SC 所以 (R∪ S)C = RC∪ SC ，其它類似可證。 證明 ： 充分性 ，已知 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 。 證明 ：⑴ 充分性，已知 RC =R (證出 R對稱 ) 任取 x,y?A 設(shè) x,y?R,則 y,x?RC,而 RC =R 所以有 y,x?R ，所以 R對稱。 再證 R? RC， 任取 x,y?R, 因 R對稱，所以有 y,x∈ R，則 x,y∈ RC, 所以 R?RC。 證明⑵ 充分性，已知 R∩RC ?IA， (證出 R反對稱 ) 任取 x,y?A 設(shè) x,y?R 且 y,x∈ R， x,y?R∧ y,x∈ R?x,y?R∧ x,y∈ RC， ? x,y?R∩RC ? x,y? IA (因 R∩RC ?IA ) ?x=y 所以 R反對稱。 第 43和 44節(jié)的 要求 ： 熟練掌握求復合關(guān)系和逆關(guān)系的計算方法 及性質(zhì)。關(guān)系的閉包是通過關(guān)系的復合和求逆構(gòu)成的 一個新的關(guān)系。 一 .例子 給定 A中關(guān)系 R，如圖所示， 分別求 A上另一個關(guān)系 R’，使 得它是包含 R的“最小的” (序偶 盡量少 )分別具有自反 (對稱、傳遞 )性的關(guān)系。 1。 。 二 .