【正文】 , h； 沒有最小元與最大元 . B的下界和最大下界都不存在； 上界有 d 和 f, 最小上界為 d. 72 實例 例 15 設 X為集合 , A＝ P(X)－ {?}－ {X}, 且 A≠?. 若 |X|=n, n≥2. 問： (1) 偏序集 A, R? 是否存在最大元？ (2) 偏序集 A, R? 是否存在最小元？ (3) 偏序集 A, R? 中極大元和極小元的一般形式是什么？ 并說明理由 . 解 (1) A, R? 不存在最小元和最大元 , 因為 n≥2. (2) A, R? 的極小元就是 X 的所有單元集 , 即 {x}, x∈ X. (3) A, R? 的極大元恰好比 X 少一個元素 , 即 X?{x}, x∈ X. 73 第七章 習題課 主要內容 ? 有序對與笛卡兒積的定義與性質 ? 二元關系、從 A到 B的關系、 A上的關系 ? 關系的表示法：關系表達式、關系矩陣、關系圖 ? 關系的運算：定義域、值域、域、逆、合成、限制、像、冪 ? 關系運算的性質 : A上關系的自反、反自反、對稱、反對稱、傳遞的性質 ? A上關系的自反、對稱、傳遞閉包 ? A上的等價關系、等價類、商集與 A的劃分 ? A上的偏序關系與偏序集 74 基本要求 ? 熟練掌握關系的三種表示法 ? 能夠判定關系的性質（等價關系或偏序關系） ? 掌握含有關系運算的集合等式 ? 掌握等價關系、等價類、商集、劃分、哈斯圖、偏序集等概念 ? 計算 A?B, dom R, ranR, fldR, R?1, R?S , Rn , r(R), s(R), t(R) ? 求等價類和商集 A/R ? 給定 A的劃分 ?，求出 ? 所對應的等價關系 ? 求偏序集中的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界 ? 掌握基本的證明方法 證明涉及關系運算的集合等式 證明關系的性質、證明關系是等價關系或偏序關系 75 練習 1 1．設 A = {1, 2, 3}, R = {x,y | x, y?A且 x+2y ? 6 }， S = {1,2, 1,3,2,2}, 求 : (1) R的集合表達式 (2) R?1 (3) dom R, ran R, fld R (4) R?S, R3 (5) r(R), s(R), t(R) 76 解答 (1) R = {1,1, 1,2, 2,1, 2,2, 3,1} (2) R?1 = {1,1, 2,1, 1,2, 2,2, 1,3 } (3) domR = {1, 2, 3}, ranR = {1,2}, fldR = {1, 2, 3} (4) R?S = {1,2, 1,3, 2,2, 2,3, 3,2, 3,3} R3 = {1,1, 1,2, 2,1, 2,2, 3,1, 3,2} (5) r(R) = {1,1, 1,2, 2,1, 2,2, 3,1, 3,3} s(R) = {1,1,1,2,2,1, 2,2, 3,1, 1,3} t(R) = {1,1, 1,2, 2,1, 2,2, 3,1, 3,2} 77 練習 2 2．設 A={1,2,3,4}，在 A?A上定義二元關系 R： x,y,u,v?R ? x+y = u+v， 求 R導出的劃分 . A?A={1,1, 1,2, 1,3, 1,4, 2,1, 2,2, 2,3, 2,4,3,1, 3,2, 3,3, 3,4, 4,1, 4,2, 4,3, 4,4} 根據(jù) x,y 中的 x+y = 2, 3, 4, 5, 6, 7, 8 將 A劃分成等價類： A/R={{1,1}, {1,2,2,1}, {1,3, 2,2, 3,1}, {1,4, 2,3, 3,2, 4,1}, {2,4, 3,3, 4,2}, {3,4, 4,3}, {4,4}} 78 3．設 R是 Z上的模 n 等價關系 , 即 x?y ? x ? y(modn), 試給出由 R確定的 Z的劃分 ?. 練習 3 解 設除以 n 余數(shù)為 r 的整數(shù)構成等價類 [r]，則 [r] ={ kn+r | k?Z }, r = 0, 1, …, n?1 ? = { [r] | r = 0, 1, …, n?1} 79 圖 11 練習 4 4．設偏序集 A, R 的哈斯圖如圖所示 . (1) 寫出 A和 R的集合表達式 (2) 求該偏序集中的極大元、極小元、最大元、最小元 解 (1) A = {a, b, c, d, e} R = {d,b, d,a, d,c, e,c, e,a, b,a, c,a}?IA (2) 極大元和最大元是 a, 極小元 是 d, e； 沒有最小元 . a b c d e 80 練習 5 5．設 R是 A上的二元關系， 設 S = {a,b | ?c(a,c?R?c,b?R)}. 證明如果 R是等價關系，則 S也是等價關系。 證 R是 A上的等價關系 . (1) 證自反 任取 x, x?A ? x,x?R ? ?x (x,x?R?x,x?R) ? x,x?S (2) 證對稱 任取 x,y, x,y?S ? ?c(x,c?R?c,y?R) ? ?c (c,x?R?y,c?R) ?y,x?S (3) 證傳遞 任取 x,y, y,z, x,y?S ? y,z?S ? ?c (x,c?R?c,y?R) ? ?d (y,d?R?d,z?R) ? x,y?R?y,z? R ? x,z?S 81 6．設偏序集 A,R和 B,S，定義 A?B上二元關系 T: x,yTu,v ? xRu ? ySv 證明 T為偏序關系 . 練習 6 證 (1) 自反性 任取 x,y, x,y?A?B ? x?A?y?B ? xRx?ySy ? x,yTx,y (2) 反對稱性 任取 x,y,u,v x,yTu,v?u,vTx,y ? xRu ? ySv ? uRx ? vSy ? (xRu ? uRx) ? (ySv ? vSy) ? x=u ? y=v ? x,y=u,v (3) 傳遞性 任取 x,y,u,v, w,t x,yTu,v?u,vTw,t ? xRu ? ySv ? uRw ? vSt ? (xRu ? uRw) ? (ySv ? vSt) ? xRw ? ySt ? x,yTw,t 82 關系性質的證明方法 1. 證明 R在 A上自反 任取 x, x?A ? ……………………..….……. ? x,x?R 前提 推理過程 結論 2. 證明 R在 A上對稱 任取 x,y， x,y ?R ? ………………………………. ? y,x?R 前提 推理過程 結論 83 3. 證明 R在 A上反對稱 任取 x,y， x,y?R?y,x?R ? …………………….. ? x = y 前提 推理過程 結論 4. 證明 R在 A上傳遞 任取 x,y,y,z， x,y?R?y,z?R ? …………………….. ? x,z?R 前提 推理過程 結論 關系性質的證明方法 84 7． R,S為 A上的關系，證明 R?S ? t(R) ? t(S) 練習 7 證 只需證明對于任意正整數(shù) n, Rn ? Sn. 對 n歸納 . n=1, 顯然為真 . 假設對于 n，命題為真，任取 x,y x,y?Rn+1 ? x,y?Rn°R ? ?t (x, t?Rn ? t, y?R) ? ?t (x, t?Sn ? t, y?S) ? x,y?Sn°S ? x,y?Sn+1 85 ? 數(shù)學歸納法（主要用于冪運算） ? 證明中用到關系運算的定義和公式 , 如： x?domR ? ?y(x,y?R) y?ranR ? ?x(x,y?R) x,y?R ? y,x?R?1 x,y?R°S ? ?t (x,t?R?t,y?S) x,y?R?A ? x?A ? x,y?R y?R?A] ? ?x (x?A ? x,y?R) r(R) = R?IA s(R) = R?R?1 t(R) = R?R2?… 關系等式或包含式的證明方法