【正文】 當(dāng)且僅當(dāng) R∩RC ?IA。 5. R?S ? RC? SC 。 4. (R－ S)C = RC－ SC 。如 三 .性質(zhì) 令 R、 S都是從 X到 Y的關(guān)系，則 1. (RC)C = R 2. (R∪ S)C = RC∪ SC 。 RC={y,x|x,y?R} y,x∈ RC ?x,y?R 二 . 計(jì)算方法 1. R={1,2,2,3,3,4,4,5} RC ={2,1,3,2,4,3,5,4} 2. RC的有向圖：是將 R的有向圖的所有邊的方向顛倒一下即可。 (x,y?A) a d b c R: 45 逆關(guān)系 逆關(guān)系 (反關(guān)系 )也是我們經(jīng)常遇到的概念，例 如 ≤與 ≥就是互為逆關(guān)系。a,d?R3,表明在 R圖上有從 a到 d有三條 邊的路徑 :a b c d。 A B 4. 關(guān)系的乘冪 令 R是 A上關(guān)系，由于復(fù)合運(yùn)算可結(jié)合，所以 關(guān)系的復(fù)合可以寫成乘冪形式。 2。 B a b c 。 。 a b c 。 。 3。 d R 1。 。 A IA 。 2。 令 A={1,2,3}, B={a,b,c,d} 從這兩個(gè)圖看出它們的復(fù)合都等于 R。 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 = 4 5 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 3 5 k=1 n ∨ k=1 n ∨ ⑷ 謂詞公式法 設(shè) I是實(shí)數(shù)集合， R和 S都是 I上的關(guān)系，定義如下： R={x,y| y=x2+3x} S={x,y| y=2x+3} 所以 R?S ={x,y| y=2x2+6x+3} 三 .性質(zhì) 關(guān)系復(fù)合運(yùn)算不滿足交換律，但是 : R?A B S?B C T?C D 則 TS)(RT)S(R ???? ?x x2+3x 2(x2+3x)+3 = 2x2+6x+3 R S 證明：任取 a,d∈ R (S T) ??b(b∈ B∧ a,b∈ R∧ b,d∈ S T) ??b(b∈ B∧ a,b∈ R∧ ?c(c∈ C∧ b,c∈ S∧ c,d∈ T)) ??b?c(b∈ B∧ a,b∈ R∧ (c∈ C∧ b,c∈ S∧ c,d∈ T)) ??c?b(c∈ C∧ (b∈ B∧ a,b∈ R∧ b,c∈ S∧ c,d∈ T)) ??c (c∈ C∧ ?b(b∈ B∧ a,b∈ R∧ b,c∈ S)∧ c,d∈ T) ??c (c∈ C∧ a,c∈ R S)∧ c,d∈ T) ?a,d∈ (R S) T TS)(RT)S(R ???? ?A B C D R T 所以 可以用下圖形象表示 : 2. R?A B S?B C T?B C ⑴ R (S∪ T)=(R S)∪ (R T) ⑵ R (S∩T)?(R S)∩(R T) 證明 ⑴ 任取 a,c∈ R (S∪ T) ? ?b(b∈ B∧ a,b∈ R∧ b,c∈ S∪ T) ??b(b∈ B∧ a,b∈ R∧ (b,c∈ S∨ b,c∈ T)) ??b((b∈ B∧ a,b∈ R∧ b,c∈ S)∨ (b∈ B∧ a,b∈ R∧ b,c∈ T)) ??b(b∈ B∧ a,b∈ R∧ b,c∈ S)∨ ?b(b∈ B∧ a,b∈ R∧ b,c∈ T) ?a,c∈ R S∨ a,c∈ R T ?a,c∈ (R S)∪ (R T) 所以 R (S∪ T)=(R S)∪ (R T) 證明⑵ 任取 a,c∈ R (S∩T) ? ?b(b∈ B∧ a,b∈ R∧ b,c∈ S∩T) ??b(b∈ B∧ a,b∈ R∧ (b,c∈ S∧ b,c∈ T)) ??b((b∈ B∧ a,b∈ R∧ b,c∈ S) ∧ (b∈ B∧ a,b∈ R∧ b,c∈ T)) ??b(b∈ B∧ a,b∈ R∧ b,c∈ S)∨ ?b(b∈ B∧ a,b∈ R∧ b,c∈ T) ?a,c∈ R S ∧ a,c∈ R T ?a,c∈ (R S)∩(R T) 所以 R (S∩T)?(R S)∩(R T) ?x(A(x)∧ B(x)) ??xA(x)∧ ?xB(x) 3. R是從 A到 B的關(guān)系，則 R IB=IA R=R 此式的證明很容易，從略。 C 1 2 3 。 。 4 R S 5 。 。 A 。 2。 3。 4 1。 。 。定義為： R?S ={x,z|x?X?z?Z??y(y?Y ?x,y?R?y,z?S)} 顯然， R?S 是從 X到 Z的關(guān)系。 則 a和 c間就是 舅舅和外甥 的關(guān)系 ,記作 R?S, 稱它是 R和 S的復(fù)合關(guān)系 。 例如，有 3個(gè)人 a,b,c， A={a,b,c}， R是 A上 兄妹 關(guān)系， S是 A上 母子 關(guān)系， a,b∈ R∧ b,c∈ S 即 a是 b的哥哥 , b是 a的妹妹 。 (要證出 a,c?R ) 由 R是對(duì)稱的 ,得 b,a?R ，由 b,a?R且 b,c?R，根據(jù)已知條件得 a,c?R ， 所以 R是傳遞的。 先證 R對(duì)稱 ：任取 a,b?A 設(shè) a,b?R， (要證出 b,a?R ) 因 R是自反的 ,所以 a,a?R，由 a,b?R且 a,a?R，根據(jù)已知條件得 b,a?R ， 所以 R是對(duì)稱的。所以有如果 a,b和 a,c在 R中 ,則有 b,c也在 R中。 證明 ： 必要性 : 已知 R是對(duì)稱和傳遞的。 ⑶ 證傳遞性 :任取 x,y,z∈ I,設(shè) xRy, yRz, (要證出 xRz) 由 R定義得 xy=3m, yz=3n (∈ I) xz= (xy)+(yz)=3m+3n=3(m+n), 因 m+n∈ I, 所以 xRz, 所以 R傳遞。 證明 ： ⑴證自反性 ：任取 x∈ I, (要證出 x,x?R ) 因 xx=0, 0可被 3整除 ,所以有 x,x∈ R, 故 R自反。 。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 R是 A中 自反 的 ??x(x?A?xRx) R是 A中 反自反 的 ??x(x?A?x,x?R) R是 A上 對(duì)稱 的 ??x?y((x?A?y?A?xRy) ?yRx) R是 A上 反對(duì)稱 的 ??x?y((x?A?y?A?xRy?yRx) ?x=y) ??x?y((x?A?y?A?x?y?xRy)?y x) R在 A上 傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 上述定義表達(dá)式都是 蘊(yùn)涵式 ,所以判斷關(guān)系 R性質(zhì)時(shí)要特 別注意使得性質(zhì)定義表達(dá)式的前件為 F的時(shí)候此表達(dá)式 為 T，即 R是滿足此性質(zhì)的。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 本節(jié)要求 ： 。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 即若 x,y∈ R與 y,z∈ R有一個(gè)是 F時(shí) (即定義的前件為 假 )， R是傳遞的。有 時(shí)，必須直接根據(jù)傳遞的定義來檢查。 即 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 實(shí)數(shù)集中的 ≤、＜，集合 ?、 ?是傳遞的。 。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 R R8既是對(duì)稱也是反對(duì)稱的。 另外對(duì)稱與反對(duì)稱不是完全對(duì)立的， 有些關(guān)系 它既是對(duì)稱也是反對(duì)稱的 ，如空關(guān)系和恒等關(guān)系。 R是 A上反對(duì)稱的 ??x?y((x?A?y?A?xRy?yRx) ?x=y) ??x?y((x?A?y?A?x?y?xRy)?y x) (P112) 由 R的關(guān)系圖看反對(duì)稱性： 兩個(gè)不同的結(jié)點(diǎn)之間 最多有一條邊。 。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 下邊 R R R6 、 R8均是對(duì)稱關(guān)系。 從關(guān)系矩陣看對(duì)稱性：以主對(duì)角線為對(duì)稱 的矩陣。 3 3 3 3 R2 R1 R3 R4 R5 R6 R7 R8 三 .對(duì)稱性 定義 :R是集合 A中關(guān)系 ,若對(duì)任何 x, y∈ A,如 果有 xRy,必有 yRx,則稱 R為 A中的對(duì)稱關(guān)系。 2。 。 1。 2。 。 3 3 3 3 1。 2。 。 1。 2。 。 1。 注意 ：一個(gè)不是自反的關(guān)系，不一定就是反 自反的，如前邊 R R7非自反 ,也非反自反。 從關(guān)系矩陣看反自反性：主對(duì)角線都為 0。 二 .反自反性 定義 ： 設(shè) R是集合 A中的關(guān)系，如果對(duì)于任 意的 x∈ A都有 x,x?R ，則稱 R為 A中的反 自反關(guān)系。 。 1。 2。 。 1。 2。 。 1。 2。 。 1。 2。 從關(guān)系矩陣看自反性：主對(duì)角線都為 1。 一 .自反性 定義 :設(shè) R是集合 A中的關(guān)系 ， 如果對(duì)于任意 x∈ A都有 x,x∈ R (xRx)， 則稱 R是 A中自反關(guān)系 。 本節(jié)中所討論的關(guān)系都是集合 A中的關(guān)系 。 例如， A是學(xué)生集合， R是 A上的同鄉(xiāng)關(guān)系， S是 A上的同姓關(guān)系，則 R∪ S：或同鄉(xiāng)或同姓關(guān)系 R∩S：既同鄉(xiāng)又同姓關(guān)系 RS ：同鄉(xiāng)而不同姓關(guān)系 R?S：同鄉(xiāng)而不同姓 ,或同姓而不同鄉(xiāng)關(guān)系 ~R：不是同鄉(xiāng)關(guān)系 , 這里 ~R=(A A)R 作業(yè) 第 109頁 ⑵、⑸ c)d) 43 關(guān)系的性質(zhì) 本節(jié)將研究關(guān)系的一些性質(zhì) ， 它們?cè)陉P(guān)系的研究 中起著重要的作用 。 2。 3 1 1 1 1 1 1 1 1 1 3 3 1。 2。 。 例如 A={1,2,3}, 則 IA ={1,1,2,2,3,3} A上的 Φ、完全關(guān)系及 IA的關(guān)系圖及矩陣如 下： MIA = 1 0 0 0 1 0 0 0 1 3 3 1。它的矩陣中全是 1。 (全域關(guān)系 ) ： A B(或 A A)本身也是一個(gè)從 A到 B(或 A上 ) 的關(guān)系，稱之為完全關(guān)系。 設(shè) A={a1, a2, ? , am}， B={b1, b2, ? , bn}是個(gè)有限集， R?A B，定義 R的 m n階 矩陣 MR=(rij)m n，其中 rij= R3={ 1,a,1,c,2,b,3,a,4,c} R4={ 1,1,1,4,2,3,3,1,3,4,4,1,4,2} 上例中 MR = MR4= 1 若 ai,bj∈ R 0 若 ai,bj∈ R (1≤i≤m,1≤j≤n) 3 1 0 1 0 1 0 1 0 0 0 0 1 4 3 1 2 3 4 a b c 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 4 4 1 2 3 4 1 2 3 4 四 .三個(gè)特殊關(guān)系 Φ： 因?yàn)?Φ?A B， (或 Φ?A A)，所以 Φ也 是一個(gè)從 A到 B(或 A上 )的關(guān)系，稱之為 空 關(guān)系 。 。 。 。 。 3。 1。 如 R?A A,即 R是集合 A中關(guān)系時(shí) ,可能有 x,x?R,則從 x到 x畫一條有向環(huán) (自回路 )。例如 R={x,y|xy} ： R?A B,用兩組小圓圈 (稱為 結(jié)點(diǎn) )分別表示 A和 B的元素，當(dāng) x,y?R時(shí)，從 x到 y引一條有向弧 (邊 )。如前的 R2 ={