【正文】 1 主要內(nèi)容 ? 有序?qū)εc笛卡兒積 ? 二元關(guān)系的定義與表示法 ? 關(guān)系的運(yùn)算 ? 關(guān)系的性質(zhì) ? 關(guān)系的閉包 ? 等價(jià)關(guān)系與劃分 ? 偏序關(guān)系 第七章 二元關(guān)系 2 有序?qū)εc笛卡兒積 定義 由兩個(gè)元素 x 和 y，按照一定的順序組成的二元組 稱為 有序?qū)?，記作 x,y. 有序?qū)π再|(zhì) : (1) 有序性 x,y?y,x （當(dāng) x?y時(shí)） (2) x,y與 u,v相等的充分必要條件是 x,y=u,v ? x=u?y=v. 3 笛卡兒積 定義 設(shè) A,B為集合， A與 B的 笛卡兒積 記作 A?B，且 A?B = {x,y| x?A?y?B}. 例 1 A={1,2,3}, B={a,b,c} A?B ={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c} B?A ={a,1,b,1,c,1,a,2,b,2,c,2,a,3,b,3,c,3} A={?}, B=? P(A)?A = {?,?, {?},?} P(A)?B = ? 4 笛卡兒積的性質(zhì) (1) 不適合交換律 A?B ? B?A (A?B, A??, B??) (2) 不適合結(jié)合律 (A?B)?C ? A?(B?C) (A??, B??, C??) (3) 對(duì)于并或交運(yùn)算滿足分配律 A?(B?C) = (A?B)?(A?C) (B?C)?A = (B?A)?(C?A) A?(B?C) = (A?B)?(A?C) (B?C)?A = (B?A)?(C?A) (4) 若 A 或 B 中有一個(gè)為空集，則 A?B 就是空集 . A?? = ??B = ? (5) 若 |A| = m, |B| = n, 則 |A?B| = mn 5 性質(zhì)證明 證明 A?(B?C) = (A?B)?(A?C) 證 任取 x,y x,y∈ A (B∪ C) ? x∈ A∧ y∈ B∪ C ? x∈ A∧ (y∈ B∨ y∈ C) ? (x∈ A∧ y∈ B)∨ (x∈ A∧ y∈ C) ? x,y∈ A B∨ x,y∈ A C ? x,y∈ (A B)∪ (A C) 所以有 A (B∪ C) = (A B)∪ (A C). 6 實(shí)例 例 2 (1) 證明 A=B,C=D ? A?C=B?D (2) A?C = B?D是否推出 A=B,C=D? 為什么？ 解 (1) 任取 x,y 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)系 定義 如果一個(gè)集合滿足以下條件之一： (1) 集合非空 , 且它的元素都是有序?qū)? (2) 集合是空集 則稱該集合為一個(gè) 二元關(guān)系 , 簡(jiǎn)稱為關(guān)系，記作 R. 如果 x,y∈ R, 可記作 xRy；如果 x,y?R, 則記作 x y 實(shí)例： R={1,2,a,b}, S={1,2,a,b}. R是二元關(guān)系 , 當(dāng) a, b不是有序?qū)r(shí)， S不是二元關(guān)系 根據(jù)上面的記法，可以寫 1R2, aRb, a c等 . 8 A到 B的關(guān)系與 A上的關(guān)系 定義 設(shè) A,B為集合 , A B的任何子集所定義的二元關(guān)系叫做 從 A 到 B的二元關(guān)系 , 當(dāng) A=B時(shí)則叫做 A上的二元關(guān)系 . 22n例 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的子集有個(gè) . 所以 A上有 個(gè)不同的二元關(guān)系 . 例如 |A| = 3, 則 A上有 =512個(gè)不同的二元關(guān)系 . 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如下： ?????????????0010000011000011RM13 關(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} 15 合成的圖示法 利用圖示（不是關(guān)系圖）方法求合成 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) 說明： ? R在 A上的限制 R?A是 R 的子關(guān)系，即 R?A ? R ? A在 R下的像 R[A] 是 ranR 的子集，即 R[A]? ranR 17 實(shí)例 例 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} 18 關(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