清華離散數(shù)學(xué)(第2版)：4.4

1、4.4 等價關(guān)系與偏序關(guān)系4.4.1 等價關(guān)系4.4.2 等價類和商集4.4.3 集合的劃分4.4.4 偏序關(guān)系4.4.5 偏序集與哈斯圖1等價關(guān)系的定義與實(shí)例定義4.18 設(shè)R為非空集合上的關(guān)系. 如果R是自反的、對稱的和傳遞的, 則稱R為A上的等價關(guān)系. 設(shè) R 是一個等價關(guān)系, 若R, 稱 x等價于y, 記做xy.例1 設(shè) A=1, 2, , 8, 如下定義 A上的關(guān)系R： R=| x,yAxy (mod 3)其中 xy (mod 3) 叫做 x與y 模3相等, 即 x 除以3的余數(shù)與 y 除以3的余數(shù)相等. 不難驗(yàn)證R為A上的等價關(guān)系, 因?yàn)?xA, 有xx(mod 3) x,yA,

2、若xy(mod 3), 則有yx(mod 3) x,y,zA, 若xy(mod 3), yz(mod 3), 則有 xz(mod 3)2模3等價關(guān)系的關(guān)系圖設(shè) A=1, 2, , 8, R= | x,yAxy (mod 3) R 的關(guān)系圖如下：3等價類定義4.19 設(shè)R為非空集合A上的等價關(guān)系, xA，令 xR = y | yAxRy 稱 xR 為x關(guān)于R 的等價類, 簡稱為 x 的等價類, 簡記為x. 實(shí)例 A= 1, 2, , 8 上模 3 等價關(guān)系的等價類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,64等價類的性質(zhì) 定理4.8 設(shè)R是非空集合A上的等價關(guān)系, 則 (1

3、) xA, x 是A的非空子集. (2) x, yA, 如果 xRy, 則 x=y. (3) x, yA, 如果 x y, 則 x與y不交. (4) ，即所有等價類的并集就是A. 5性質(zhì)的證明由等價類定義可知, xA有xA. 由自反性有xRx，因此xx, 即x非空. 任取z, 則有zx R RRR R R從而證明了zy. 綜上所述必有xy. 同理可證y x. 這就得到了x=y.(3) 假設(shè)xy, 則存在zxy, 從而有zxzy, 即RR 成立. 根據(jù)R 的對稱性和傳遞性必有R, 與x y矛盾6性質(zhì)的證明（續(xù)）(4) 先證 . 任取y, y x (xAyx) yxxA yA 從而有 .再證A .

4、 任取y, yA yyyA y從而有A 成立. 綜上所述得7商集定義4.20 設(shè)R 為非空集合A 上的等價關(guān)系, 以R 的所有等價類作為元素的集合稱為A關(guān)于R 的商集, 記做 A/R, A/R = xR | xA 例2令A(yù)=1, 2, , 8，A關(guān)于模 3 等價關(guān)系R 的商集為 A/R = 1, 4,7, 2, 5, 8, 3, 6 A關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 8集合的劃分定義4.21 設(shè)A為非空集合, 若A的子集族 ( P(A) 滿足下面條件： (1) (2) xy (x,yxyxy=) (3) =A 則稱是A的一個劃分,

5、 稱 中的元素為A的劃分塊.例3 設(shè)Aa, b, c, d, 給定 1, 2, 3, 4, 5, 6如下： 1=a, b, c,d， 2=a, b,c,d 3=a,a, b, c, d， 4=a, b,c 5=,a, b,c, d， 6=a,a,b, c, d 則 1和 2是A的劃分, 其他都不是A的劃分. 9等價關(guān)系與劃分的一一對應(yīng)商集 A/R 就是A 的一個劃分 不同的商集對應(yīng)于不同的劃分 任給A 的一個劃分 , 如下定義A 上的關(guān)系 R：R = | x,yAx 與 y 在的同一劃分塊中 則R 為A上的等價關(guān)系, 且該等價關(guān)系確定的商集就是. 例4 給出A1,2,3上所有的等價關(guān)系求解思路

6、：先做出A的所有劃分, 然后根據(jù)劃分寫出 對應(yīng)的等價關(guān)系. 10例 4 1, 2和 3分別對應(yīng)于等價關(guān)系 R1, R2和R3.其中 R1=,IA R2=,IA R3=,IAA上的等價關(guān)系與劃分之間的對應(yīng)： 4對應(yīng)于全域關(guān)系EA 5對應(yīng)于恒等關(guān)系IA11實(shí)例根據(jù)有序?qū)Φ?x+y=2,3,4,5,6,7,8 將AA劃分. (AA)/R=, , , , , , , , , , , , , , 例5 設(shè)A=1,2,3,4，在AA上定義二元關(guān)系 R： ,R x+y = u+v，求R 導(dǎo)出的劃分. 解 AA=, , , , , , , , , , , , , , 12偏序關(guān)系定義4.22 非空集合A上的自

7、反、反對稱和傳遞的關(guān)系，稱為A上的偏序關(guān)系，記作. 設(shè)為偏序關(guān)系, 如果, 則記作 xy, 讀作 x“小于或等于”y. 實(shí)例 集合A上的恒等關(guān)系 IA 是A上的偏序關(guān)系. 小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系. 13相關(guān)概念定義4.23 x與y可比 設(shè)R為非空集合A上的偏序關(guān)系, x, yA, x與y 可比 xy yx.結(jié)論：x, yA，下述幾種情況發(fā)生其一且僅發(fā)生其一. xy, yx, xy, x與y不是可比的定義4.25 全序 R為非空集合A上的偏序, x, yA, x與y 都可比，則稱R為全序. 定義4.26 覆蓋 x,yA, 如果xy且不存在 zA使得 xzy,

8、 則稱 y覆蓋x.實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系 整除關(guān)系不是正整數(shù)集合上的全序關(guān)系 1, 2, 4, 6集合上的整除關(guān)系, 2覆蓋1, 4 和 6 覆蓋2. 但4不覆蓋1.14偏序集與哈斯圖定義4.27 集合A和A上的偏序關(guān)系一起叫做偏序集, 記作.實(shí)例：整數(shù)集和數(shù)的小于等于關(guān)系構(gòu)成偏序集 冪集P(A)和包含關(guān)系構(gòu)成偏序集. 哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關(guān)系圖特點(diǎn)： 每個結(jié)點(diǎn)沒有環(huán) 兩個連通的結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低 表示，位置低的元素的順序在前 具有覆蓋關(guān)系的兩個結(jié)點(diǎn)之間連邊15哈斯圖實(shí)例例6 16 例7 已知偏序集的哈斯圖如下圖所示, 試求出集合A和關(guān)系R

9、的表達(dá)式. 哈斯圖實(shí)例（續(xù)）A=a, b, c, d, e, f, g, h R=, IA 17偏序集的特定元素定義4.28 設(shè)為偏序集, BA, yB. (1) 若x(xByx)成立, 則稱 y 為 B 的最小元. (2) 若x(xBxy)成立, 則稱 y 為 B 的最大元. (3) 若x(xBxyx=y)成立, 則稱 y 為B的極小元. (4) 若x(xByxx=y)成立, 則稱 y 為B的極大元. 性質(zhì)：對于有窮集，極小元和極大元必存在，可能存在多個. 最小元和最大元不一定存在，如果存在一定惟一.最小元一定是極小元；最大元一定是極大元. 孤立結(jié)點(diǎn)既是極小元，也是極大元. 18定義4.29

10、 設(shè)為偏序集, BA, yA. （1） 若x (xBxy) 成立, 則稱 y 為B 的上界. （2） 若x (xByx) 成立, 則稱 y 為B 的下界. （3） 令Cy | y為B的上界, 則稱C的最小元為B 的最小上界 或上確界. （4） 令Dy | y為B的下界, 則稱D的最大元為B 的最大下界 或下確界.性質(zhì)： 下界、上界、下確界、上確界不一定存在 下界、上界存在不一定惟一 下確界、上確界如果存在，則惟一 集合的最小元就是它的下確界，最大元就是它的上確界；反之不對. 偏序集的特定元素(續(xù))19實(shí)例例8 設(shè)偏序集如下圖所示，求A 的極小元、最小元、極大元、最大元. 設(shè)B b, c, d

11、, 求B 的下界、上界、下確界、上確界. 解：極小元：a, b, c, g；極大元：a, f, h；沒有最小元與最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界為 d. 20偏序集的特殊子集定義4.30 設(shè)為偏序集, BA. (1) 如果x,yB，x與y都是可比的，則稱B是A中的一條鏈，B中的元素個數(shù)稱為鏈的長度； (2) 如果x,yB，xy，x與y都是不可比的，則稱B是A中的一條反鏈，B中的元素個數(shù)稱為反鏈的長度.實(shí)例：在偏序集中，1,2,4,8是長為4的鏈，1,4是長為2的鏈，2,3是長為2的反鏈. 對于單元集2，它的長度是1，既是鏈也是反鏈. 21分解為反鏈算法4.2 偏序集反鏈分解算法輸入：偏序集A輸出：A中的反鏈B1, B2, 1i12BiA 的所有極大元的集合（顯然Bi是一條反鏈）3令A(yù)ABi4if A 5 ii+16 轉(zhuǎn)2定理4.9 設(shè)為偏序集，如果A中最長的鏈長度為n, 則該偏序集可以分解為 n 條不相交的反鏈. 22拓?fù)渑判蛩惴?.3 拓?fù)渑判蜉斎耄浩蚣疉輸出：A中元素的排序1. i12. 從A中選擇一個極小元 ai 作為最小元3AAai4if A5 ii+16 轉(zhuǎn)2把偏序集擴(kuò)張成一個