【文章內(nèi)容簡(jiǎn)介】 yRz, (要證出 xRz) 由 R定義得 xy=3m, yz=3n (∈ I) xz= (xy)+(yz)=3m+3n=3(m+n), 因 m+n∈ I, 所以 xRz, 所以 R傳遞。 證畢 練習(xí) 2： 設(shè) R是集合 A上的一個(gè)自反關(guān)系 ,求證： R是對(duì)稱和傳遞的，當(dāng)且僅當(dāng) a,b和 a,c在 R中 ,則有 b,c也在 R中。 證明 ： 必要性 : 已知 R是對(duì)稱和傳遞的。 設(shè) a,b?R 又 a,c?R， (要證出 b,c?R ) 因 R對(duì)稱的故 b,a?R,又已知 a,c?R 由傳遞性 得 b,c?R。所以有如果 a,b和 a,c在 R中 ,則有 b,c也在 R中。 充分性 : 已知任意 a,b,c?A， 如 a,b和 a,c在 R中 ,則有 b,c也在 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ì)稱的。 再證 R傳遞 ：任取 a,b,c?A 設(shè) a,b?R， b,c?R。 (要證出 a,c?R ) 由 R是對(duì)稱的 ,得 b,a?R ，由 b,a?R且 b,c?R，根據(jù)已知條件得 a,c?R ， 所以 R是傳遞的。 作業(yè) 第 113頁(yè) ⑴、⑶、⑷ 44 關(guān)系的復(fù)合 二元關(guān)系除了可進(jìn)行集合并、交、補(bǔ)等運(yùn)算外， 還可以進(jìn)行一些新的運(yùn)算，先介紹由兩個(gè)關(guān)系生 成一種新的關(guān)系，即關(guān)系的復(fù)合運(yù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的妹妹 。 b是 c的母親， c是 b的兒子。 則 a和 c間就是 舅舅和外甥 的關(guān)系 ,記作 R?S, 稱它是 R和 S的復(fù)合關(guān)系 。 SR?a b c R S :設(shè)是 R從 X到 Y的關(guān)系， S是從 Y到 Z的關(guān)系，則 R和 S的復(fù)合關(guān)系記作 R?S 。定義為： R?S ={x,z|x?X?z?Z??y(y?Y ?x,y?R?y,z?S)} 顯然， R?S 是從 X到 Z的關(guān)系。 (俗稱過(guò)河拆橋法 ) 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 。 4 1。 2。 3。 A 1。 2。 3。 A 。 。 。 B 1 2 3 。 4 R S 5 。 。 。 。 C 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 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 此式的證明很容易，從略。下面列舉一例 來(lái)驗(yàn)證。 令 A={1,2,3}, B={a,b,c,d} 從這兩個(gè)圖看出它們的復(fù)合都等于 R。 1。 2。 3。 A IA 。 。 。 B a b c 。 d R 1。 2。 3。 A R IB 。 。 。 a b c 。 d 。 。 。 B a b c 。 d 1。 2。 3。 A B 4. 關(guān)系的乘冪 令 R是 A上關(guān)系，由于復(fù)合運(yùn)算可結(jié)合，所以 關(guān)系的復(fù)合可以寫(xiě)成乘冪形式。即 R R=R2， R2 R=R R2 =R3， … 一般地 R0 =IA， Rm Rn = Rm+n (Rm)n =Rmn (m,n為非負(fù)整數(shù) ) 例如 R是 A上關(guān)系，如上圖所示 ,可見(jiàn) a,c?R2,表明在 R圖上有從 a到 c有兩條邊的路徑 : a b c。a,d?R3,表明在 R圖上有從 a到 d有三條 邊的路徑 :a b c d。 ...如果 x,y?Rk,表明在 R圖上有從 x到 y有 k條邊 (長(zhǎng)為 k)的路徑 。 (x,y?A) a d b c R: 45 逆關(guān)系 逆關(guān)系 (反關(guān)系 )也是我們經(jīng)常遇到的概念，例 如 ≤與 ≥就是互為逆關(guān)系。 一 .定義 R是從 A到 B的關(guān)系，如果將 R中的所有序偶的 兩個(gè)元素的位置互換，得到一個(gè)從 B到 A的關(guān)系， 稱之為 R的逆關(guān)系，記作 RC，或 R1。 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的有向圖的所有邊的方向顛倒一下即可。 3. RC的矩陣 M =(MR)T 即為 R矩陣的轉(zhuǎn)置。如 三 .性質(zhì) 令 R、 S都是從 X到 Y的關(guān)系，則 1. (RC)C = R 2. (R∪ S)C = RC∪ SC 。 3. (R∩S)C = RC∩SC 。 4. (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 ，其它類似可證。 5. R?S ? 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 SC ) 證明 ： 任取 z,x∈ (R S)C ?x,z?R S ??y(y∈ Y∧ x,y∈ R∧ y,z∈ S) ? ?y(y∈ Y∧ z,y∈ SC∧ y,x∈ RC) ?z,x?SC RC 所以 (R S)C= SC RC 8. R是 A上關(guān)系，則 ⑴ R是對(duì)稱的，當(dāng)且僅當(dāng) RC =R ⑵ R是反對(duì)稱的，當(dāng)且僅當(dāng) R∩RC ?IA。 證明 ：⑴ 充分性，已知 RC =R (證出 R對(duì)稱 ) 任取 x,y?A 設(shè) x,y?R,則 y,x?RC,而 RC =R 所以有 y,x?R ，所以 R對(duì)稱。 必要性，已知 R 對(duì)稱， (證出 RC =R) 先證 RC?R， 任取 y,x∈ RC,則 x,y?R,因 R對(duì)稱 所以有 y,x∈ R，所以 RC?R。 再證 R? RC， 任取 x,y?R, 因 R對(duì)稱，所以有 y,x∈ R，則 x,y∈ RC, 所以 R?RC。 最后得 RC =R 。 證明⑵ 充分性，已知 R∩RC ?IA， (證出 R反對(duì)稱