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