【正文】 ) (這個(gè)劃分稱之為 商集 ) 三 . 商集 商”和除法有關(guān)，比如把 一塊蛋糕 平均分成四份，從 兩種不同的角度看這件事： 從算術(shù)角度看 ： 1用 4除 ,每份 1/4,這就是“商” ,于是 : 1=1/4+1/4+1/4+1/4 從集合角度看 ： 集合 A用模 3同余關(guān)系 R劃分，得到三個(gè)等價(jià)類，所以 A {{1,4,7},{2,5},{3,6}}={[1]R,[2]R,[3]R}商集 定義 ： R是 A上等價(jià)關(guān)系，由 R的所有等價(jià)類構(gòu)成的集合 稱之為 A關(guān)于 R的商集。 類似可證 [b]R?[a]R。 。 1。 c)一個(gè)獨(dú)立子圖的情形，則 ( )個(gè)等價(jià)關(guān)系 。 2。 。 1。 1。 2。 三 .交叉劃分 例 X是東大學(xué)生集合 , A和 B都是 X的劃分： A={M,W},M?X, W?X, M={男生 },W={女生 } B={L,N},L?X, N?X, L={遼寧人 },N={非 遼寧人 } C={L∩M , L∩W , N∩M , N∩W } 稱 C是 X的交叉劃分。 劃分 ,一定是覆蓋；但覆蓋 , 不一定是劃分 。 。 。 。 。 。 證明完畢。 類似可以證明 r(R)也對稱。 。 ej+2 ek1 ek2 ek+1 ek+2 …... …... ei1 y 求 t(R)的矩陣 Warshall算法： |X|=n, R?X X, 令 MR=A R2的矩陣為 A2， … R k的矩陣為 Ak .于是 t(R)的 矩陣記作 MR+=A+A2+…+A k +… (+是邏輯加 ) ⑴ 置新矩陣 A :=MR 。 。 上述元素序列 : x=e0, e1, e2,...,ei1,y=ei中共有 i+1個(gè)元 素， i+1n , 而 A 中只有 n個(gè)元素，所以上述元素中 至少有兩個(gè)相同，設(shè) ej=ek (jk)， 于是 R的關(guān)系圖中 會(huì)有下面這些邊： 從此圖中刪去回路中 kj(kj≥1)條邊后得x,y∈ Ri(kj)， i(kj)i, 與 i是 最小的 矛盾。 ⑶ 證 R’是“最小的”：如果有 A上傳遞關(guān)系 R”且 R?R”,（ 證出 R’?R”）任取 x,y?R’,則由 R’定義 得必存在整數(shù) i,使得 x,y?Ri ,根據(jù)關(guān)系的復(fù)合得 A中必存在 i1個(gè)元素 e1, e2,...,ei1， 使得 (見 49頁 ) x, e1?R∧ e1,e2?R∧ ...∧ ei1,y?R。 三 .計(jì)算方法 定理 A中關(guān)系 R,則 r(R)=R∪ IA。 。 1。 證明⑵ 充分性，已知 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反對稱。 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 ，其它類似可證。 ...如果 x,y?Rk,表明在 R圖上有從 x到 y有 k條邊 (長為 k)的路徑 。 。 2。 1。 。 A 1。 (俗稱過河拆橋法 ) 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 。 再證 R傳遞 ：任取 a,b,c?A 設(shè) a,b?R， b,c?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對稱。 1。 2。 。 1。 2。 。 檢查時(shí)要特別注意使得傳遞定義表達(dá)式的前件為 F的時(shí)候 此表達(dá)式為 T，即是傳遞的。 。 3 3 3 3 1。 2。 從關(guān)系矩陣看反對稱性： 以主對角線為對稱的 兩個(gè)元素中最多有一個(gè) 1。 1。 2。 。 。 1。 2。 下面 R R R均是反自反關(guān)系 。 2。 。 1。 即 R是 A中自反的 ??x(x?A?xRx) 例如在實(shí)數(shù)集合中 ,“?”是自反關(guān)系 ， 因?yàn)?， 對任意實(shí)數(shù) x， 有 x ? x. 從關(guān)系有向圖看自反性 :每個(gè)結(jié)點(diǎn)都有環(huán)。 。 3. A上的 恒等關(guān)系 IA： IA?A A，且 IA ={x,x|x∈ A}稱之為 A 上的恒等關(guān)系。 4。 2。 x2+y2=4 ≤ ≥ = x y 定義域 (domain) ： 設(shè) R?A B，由所有 x,y?R的第一個(gè)元素組成的集合，稱為 R的定義域，記作 dom R，即 dom R={x|?y(x,y?R)} 值域 (range) ： 設(shè) R?A B，由所有 x,y?R的第二個(gè)元素組成的集合，稱為 R的值域， 記作 ran R，即 ran R={y|?x(x,y?R)} 上述 R2={ 1,1,1,2,1,3,1,4,2,2,2,3, 2,4, 3,3, 3,4,4,4} dom R2 ={1,2,3,4} ran R2 ={1,2,3,4} 三 . 關(guān)系的表示方法 1. 枚舉法 : 即將關(guān)系中所有序偶一一列舉出，寫在大括號(hào) 內(nèi)。下面討論如何從中抽象出關(guān)系的定義 和如何表示關(guān)系。 1) 如果 A、 B都是有限集，且 |A|=m, |B|=n，則 |A?B |=mn. 證明：由笛卡爾積的定義及排列組合中的乘法原 理，直接推得此定理。 :有序 n元組是一個(gè)序偶 ,其第一個(gè)元素本身是個(gè)有序 n1元組 ,記作 x1 , x2 ,? , xn1, xn。 41 序偶與集合的笛卡爾積 實(shí)際上“序偶”概念以前已經(jīng)用過。 ：設(shè) x,y， u,v是兩個(gè)序偶，如果 x=u和 y=v，則稱 x,y和 u,v相等， 記作 x,y=u,v. 3 .定義 :有序 3元組是一個(gè)序偶 ,其第一個(gè)元素也是個(gè)序偶。 解： A?B={0,a,0,b,1,a,1,b} B?A={a,0 ,b,0,a,1,b,1} A?A={0,0,0,1,1,0,1,1} 可見 A B≠B A 所以，集合的笛卡爾積運(yùn)算不滿足交換律。 1)令 A1={x|x是 學(xué)號(hào) } A2={x|x是 姓名 } A3={男 ,女 } A4={x|x是 出生日期 } A5={x|x是 班級(jí) } A6 ={x|x是 籍貫 } 則 A1?A2?A3 ?A4?A5 ?A6中一個(gè)元素： 001， 王強(qiáng)，男， 1981:02:16，計(jì) 20221，遼寧 這就是學(xué)生檔案數(shù)據(jù)庫的一條信息，所以學(xué)生 的檔案就是 A1?A2?A3 ?A4?A5 ?A6的一個(gè)子集。如 :R={1,a,書 ,車 ,人 , 樹 } x,y?R ?xRy 也稱之為 x與 y有Ｒ關(guān)系。 如 R?A A,即 R是集合 A中關(guān)系時(shí) ,可能有 x,x?R,則從 x到 x畫一條有向環(huán) (自回路 )。 。 (全域關(guān)系 ) ： A B(或 A A)本身也是一個(gè)從 A到 B(或 A上 ) 的關(guān)系，稱之為完全關(guān)系。 2。 本節(jié)中所討論的關(guān)系都是集合 A中的關(guān)系 。 1。 。 2。 從關(guān)系矩陣看反自反性：主對角線都為 0。 2。 3 3 3 3 1。 。 下邊 R R R6 、 R8均是對稱關(guān)系。 2。 1。 。 2。 1。 。 即 R在 A上傳遞 ??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz) 實(shí)數(shù)集中的 ≤、＜，集合 ?、 ?是傳遞的。 。 2。 1。 R是 A中 自反 的 ??x(x?A?xRx) R是 A中 反自反 的 ??x(x?A?x,x?R) R是 A上 對稱 的 ??x?y((x?A?y?A?xRy) ?yRx) R是 A上 反對稱 的 ??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ì)的。 2。 1。 。所以有如果 a,b和 a,c在 R中 ,則有 b,c也在 R中。 則 a和 c間就是 舅舅和外甥 的關(guān)系 ,記作 R?S, 稱它是 R和 S的復(fù)合關(guān)系 。 4 1。 。 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