【正文】 x,y?A?C ? x?A?y?C ? x?B?y?D ? x,y?B?D (2) 不一定 .反例如下： A={1}， B={2}, C = D = ?, 則 A?C = B?D但是 A ? B. 7 二元關(guān)系 定義 如果一個集合滿足以下條件之一： (1) 集合非空 , 且它的元素都是有序?qū)? (2) 集合是空集 則稱該集合為一個 二元關(guān)系 , 簡稱為關(guān)系，記作 R. 如果 x,y∈ R, 可記作 xRy；如果 x,y?R, 則記作 xRy 實(shí)例： R={1,2,a,b}, S={1,2,a,b}. R是二元關(guān)系 , 當(dāng) a, b不是有序?qū)r， S不是二元關(guān)系 根據(jù)上面的記法，可以寫 1R2, aRb, aSb等 . 8 A到 B的關(guān)系與 A上的關(guān)系 定義 設(shè) A,B為集合 , A B的任何子集所定義的二元關(guān)系叫做 從 A 到 B的二元關(guān)系 , 當(dāng) A=B時則叫做 A上的二元關(guān)系 . 例 3 A={0,1}, B={1,2,3}, 那么 R1={0,2}, R2=A B, R3=?, R4={0,1} R1, R2, R3, R4是從 A 到 B 的二元關(guān)系 , R3 和 R4 也是 A上的二元關(guān)系 . 計(jì)數(shù) : |A|=n, |A A|=n2, A A的子集有 個 .所以 A上有 個不同的二元關(guān)系 . 例如 |A| = 3, 則 A上有 =512個不同的二元關(guān)系 . 22n 22njump 9 A上重要關(guān)系的實(shí)例 定義 設(shè) A 為集合 , (1) ?是 A上的關(guān)系，稱為 空關(guān)系 (2) 全域關(guān)系 EA = {x,y| x∈ A∧ y∈ A} = A A 恒等關(guān)系 IA = {x,x| x∈ A} 小于等于關(guān)系 LA = {x,y| x,y∈ A∧ x≤y}, A為實(shí)數(shù)子集 整除關(guān)系 DB = {x,y| x,y∈ B∧ x整除 y}, A為非 0整數(shù)子集 包含關(guān)系 R? = {x,y| x,y∈ A∧ x?y}, A是集合族 . 10 實(shí)例 例如 , A={1, 2}, 則 EA = {1,1,1,2,2,1,2,2} IA = {1,1,2,2} 例如 A = {1, 2, 3}, B={a, b}, 則 LA = {1,1,1,2,1,3,2,2,2,3,3,3} DA = {1,1,1,2,1,3,2,2,3,3} 例如 A = P(B) = {?,{a},,{a,b}}, 則 A上的包含關(guān)系是 R? = {?,?,?,{a},?,,?,{a,b},{a},{a}, {a},{a,b},,,,{a,b},{a,b},{a,b}} 類似的還可以定義： 大于等于關(guān)系 , 小于關(guān)系 , 大于關(guān)系 , 真包含關(guān)系等 . 11 關(guān)系的表示 1. 關(guān)系矩陣 若 A={x1, x2, …, xm}， B={y1, y2, …, yn}， R是從 A到 B的 關(guān)系， R的關(guān)系矩陣是布爾矩陣 MR = [ rij ] m?n, 其中 rij = 1? xi, yj ?R. 2. 關(guān)系圖 若 A= {x1, x2, …, xm}， R是從 A上的關(guān)系， R的關(guān)系圖是GR=A, R, 其中 A為結(jié)點(diǎn)集， R為邊集 . 如果 xi,xj屬于 關(guān)系 R，在圖中就有一條從 xi 到 xj 的有向邊 . 注意： ? 關(guān)系矩陣適合表示從 A到 B的關(guān)系或 A上的關(guān)系（ A,B為有窮集） ? 關(guān)系圖適合表示有窮集 A上的關(guān)系 12 實(shí)例 例 4 A={1,2,3,4}, R={1,1,1,2,2,3,2,4,4,2}, R的關(guān)系矩陣 MR和關(guān)系圖 GR如下： ?????????????0010000011000011RMjump jump1 13 關(guān)系的運(yùn)算 關(guān)系的基本運(yùn)算 定義 關(guān)系的 定義域 、 值域 與 域 分別定義為 domR = { x | ?y (x,y?R) } ranR = { y | ?x (x,y?R) } fldR = domR ? ranR 例 5 R={1,2,1,3,2,4,4,3}, 則 domR={1, 2, 4} ranR={2, 3, 4} fldR={1, 2, 3, 4} 14 關(guān)系運(yùn)算 (逆與合成 ) 定義 關(guān)系的 逆運(yùn) 算 R?1 = { y, x | x, y?R } 定義 關(guān)系的 合成 運(yùn)算 R?S = { x, z | ? y (x, y?R ? y, z?S) } 例 6 R = {1,2, 2,3, 1,4, 2,2} S = {1,1, 1,3, 2,3, 3,2, 3,3} R?1 = {2,1, 3,2, 4,1, 2,2} R?S = {1,3, 2,2, 2,3} S?R = {1,2, 1,4, 3,2, 3,3} jump 15 合成的圖示法 利用圖示（不是關(guān)系圖）方法求合成 : R = {1,2, 2,3, 1,4, 2,2} S = {1,1, 1,3, 2,3, 3,2, 3,3} 則： R?S ={1,3, 2,2, 2,3} S?R ={1,2, 1,4, 3,2, 3,3} 16 關(guān)系運(yùn)算 (限制與像 ) 定義 設(shè) R為二元關(guān)系 , A是集合 (1) R在 A上的 限制 記作 R?A, 其中 R?A = { x,y | xRy∧ x∈ A } (2) A在 R下的 像 記作 R[A], 其中 R[A]=ran(R?A) 例 7 設(shè) R={1,2,1,3,2,2,2,4,3,2}, 則 R?{1} = {1,2,1,3} R?? = ? R?{2,3} = {2,2,2,4,3,2} R[{1}] = {2,3} R[?] = ? R[{3}] = {2} 說明： ?R在 A上的限制 R?A是 R 的子關(guān)系，即 R?A ? R ?A在 R下的像 R[A] 是 ranR 的子集，即 R[A]? ranR 17 關(guān)系運(yùn)算的性質(zhì) 定理 設(shè) F是任意的關(guān)系 , 則 (1) (F?1)?1=F (2) domF?1= ranF, ranF?1= domF 證 (1) 任取 x,y, 由逆的定義有 x,y∈ (F?1)?1 ? y,x∈ F?1 ? x,y∈ F. 所以有 (F?1)?1=F. (2) 任取 x, x∈ domF?1 ? ?y(x,y∈ F?1) ? ?y(y,x∈ F)? x∈ ranF 所以有 domF?1=ranF. 同理可證 ranF?1=domF. 18 定理 設(shè) F, G, H是任意的關(guān)系 , 則 (1) (F?G)?H = F?(G?H) (2) (F?G)?1 = G?1?F?1 關(guān)系運(yùn)算的性質(zhì) 證 (1) 任取 x,y, x,y?(F?G)?H ? ?t (x,t∈ F?G∧ t,y∈ H) ? ?t ( ?s (x,s∈ F∧ s,t∈ G)∧ t,y∈ H) ? ?t ?s (x,s∈ F∧ s,t∈ G∧ t,y∈ H) ? ?s (x,s∈ F∧ ?t (s,t∈ G∧ t,y∈ H)) ? ?s (x,s∈ F∧ s,y∈ G?H) ? x,y∈ F?(G?H) 所以 (F?G)?H = F?(G?H) 19 證明 (2) 任取 x,y, x,y∈ (F?G)?1 ? y,x∈ F?G ? ?t (y,t∈ F∧ t,x∈ G) ? ?t (x,t∈ G?1∧ t,y∈ F?1) ? x,y∈ G?1 ?F?1 所以 (F ? G)?1 = G?1 ?F?1 20 關(guān)系運(yùn)算的性質(zhì) 定理 設(shè) R為 A上的關(guān)系 , 則 R?IA= IA?R=R 證 :任取 x,y x,y∈ R?IA ? ?t (x,t∈ R∧ t,y∈ IA) ? ?t (x,t∈ R∧ t=y∧ y∈ A) ? x,y∈ R 21 關(guān)系運(yùn)算的性質(zhì) 定理 (1) F?(G?H) = F?G∪ F?H (2) (G∪ H)?F = G?F∪ H?F (3) F?(G∩H) ? F?G∩F?H (4) (G∩H)?F ? G?F∩H?F 只證 (3) 任取 x,y, x,y∈ F?(G∩H) ? ?t (x,t∈ F∧ t,y∈ G∩H) ? ?t (x,t∈ F∧ t,y∈ G∧ t,y∈ H) ? ?t ((x,t∈ F∧ t,y∈ G)∧ (x,t∈ F∧ t,y∈ H)) ? ?t (x,t∈ F∧ t,y∈ G)∧ ?t (x,t∈ F∧ t,y∈ H) ? x,y∈ F?G∧ x,y∈ F?H