離散數(shù)學(xué)：第4章 二元關(guān)系與函數(shù)3

1、14.5 等價(jià)關(guān)系與偏序關(guān)系等價(jià)關(guān)系與偏序關(guān)系n等價(jià)關(guān)系的定義與實(shí)例等價(jià)關(guān)系的定義與實(shí)例n等價(jià)類及其性質(zhì)等價(jià)類及其性質(zhì)n商集與集合的劃分商集與集合的劃分n等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)n偏序關(guān)系偏序關(guān)系n偏序集與哈斯圖偏序集與哈斯圖n偏序集中的特定元素偏序集中的特定元素2等價(jià)關(guān)系的定義與實(shí)例等價(jià)關(guān)系的定義與實(shí)例定義定義 設(shè)設(shè) R 為非空集合上的關(guān)系為非空集合上的關(guān)系. 如果如果 R 是自反的、是自反的、對(duì)稱的和傳遞的對(duì)稱的和傳遞的, 則稱則稱 R 為為 A 上的上的等價(jià)關(guān)系等價(jià)關(guān)系. 設(shè)設(shè) R 是一個(gè)等價(jià)關(guān)系是一個(gè)等價(jià)關(guān)系, 若若R, 稱稱 x 等價(jià)于等價(jià)于y, 記做記做 x

2、y. 實(shí)例實(shí)例 設(shè)設(shè) A=1,2,8, 如下定義如下定義A上的關(guān)系上的關(guān)系 R： R = | x,yAxy(mod 3) 其中其中 xy(mod 3) 叫做叫做 x 與與 y 模模3相等相等, 即即 x 除以除以3的的余數(shù)與余數(shù)與 y 除以除以3的余數(shù)相等的余數(shù)相等. 3等價(jià)關(guān)系的驗(yàn)證等價(jià)關(guān)系的驗(yàn)證驗(yàn)證模驗(yàn)證模 3 相等關(guān)系相等關(guān)系 R 為為 A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 因?yàn)橐驗(yàn)?xA, 有有x x(mod 3) x, yA, 若若 x y(mod 3), 則有則有 y x(mod 3) x, y, zA, 若若x y(mod 3), y z(mod 3), 則有則有 xz(mod 3)自反

3、性、對(duì)稱性、傳遞性得到驗(yàn)證自反性、對(duì)稱性、傳遞性得到驗(yàn)證4A上模上模3等價(jià)關(guān)系的關(guān)系圖等價(jià)關(guān)系的關(guān)系圖設(shè)設(shè) A=1,2,8, R= | x,yAxy(mod 3) 5等價(jià)類等價(jià)類定義定義 設(shè)設(shè)R為非空集合為非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, xA，令，令xR = y | yAxRy 稱稱 xR 為為 x 關(guān)于關(guān)于R 的的等價(jià)類等價(jià)類, 簡(jiǎn)稱為簡(jiǎn)稱為 x 的等價(jià)類的等價(jià)類, 簡(jiǎn)簡(jiǎn)記為記為x. 實(shí)例實(shí)例 A= 1, 2, , 8 上模上模 3 等價(jià)關(guān)系的等價(jià)類：等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,66等價(jià)類的性質(zhì)等價(jià)類的性質(zhì) 定理定理1 設(shè)設(shè)R是非空集

4、合是非空集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 則則 (1) xA, x 是是A的非空子集的非空子集. (2) x, yA, 如果如果 x R y, 則則 x=y. (3) x, yA, 如果如果 x y, 則則 x與與y不交不交. (4) x | xA=A，即所有等價(jià)類的并集就即所有等價(jià)類的并集就是是A. 7實(shí)例實(shí)例A= 1, 2, , 8 上模上模 3 等價(jià)關(guān)系的等價(jià)類：等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7， 2=5=8=2,5,8， 3=6=3,6 以上以上3 類兩兩不交，類兩兩不交， 1,4,7 2,5,8 3,6 = 1,2, ,88商集商集定義定義 設(shè)設(shè)R為非空集合為非空集合A上的

5、等價(jià)關(guān)系上的等價(jià)關(guān)系, 以以R的所有的所有等價(jià)類作為元素的集合稱為等價(jià)類作為元素的集合稱為A關(guān)于關(guān)于R的的商集商集, 記做記做A/R, A/R = xR | xA 實(shí)例實(shí)例 A=1,2,8,A關(guān)于模關(guān)于模3等價(jià)關(guān)系等價(jià)關(guān)系R的商集為的商集為 A/R = 1,4,7, 2,5,8, 3,6 A關(guān)于恒等關(guān)系和全域關(guān)系的商集為：關(guān)于恒等關(guān)系和全域關(guān)系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 9集合的劃分集合的劃分定義定義 設(shè)設(shè)A為非空集合為非空集合, 若若A的子集族的子集族( P(A) 滿足下面條件：滿足下面條件： (1) (2) x y (x,yxyxy=) (3)

6、 =A 則稱則稱是是A的一個(gè)的一個(gè)劃分劃分, 稱稱中的元素為中的元素為A的的劃分劃分塊塊.10例題例題例例1 設(shè)設(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 的劃分的劃分. 為什么？為什么？11等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)等價(jià)關(guān)系與劃分的一一對(duì)應(yīng)商集商集 A/R 就是就是 A 的一個(gè)劃分的一個(gè)劃分 不同的商集對(duì)應(yīng)于不同的劃分不

7、同的商集對(duì)應(yīng)于不同的劃分 任給任給 A 的一個(gè)劃分的一個(gè)劃分, 如下定義如下定義 A 上的關(guān)系上的關(guān)系 R： R = | x,yAx 與與 y 在在的同一劃分塊中的同一劃分塊中則則 R 為為 A上的等價(jià)關(guān)系上的等價(jià)關(guān)系, 且該等價(jià)關(guān)系確定的商集且該等價(jià)關(guān)系確定的商集就是就是. 例例2 給出給出A1,2,3上所有的等價(jià)關(guān)系上所有的等價(jià)關(guān)系求解思路：先做出求解思路：先做出A的所有劃分的所有劃分, 然后根據(jù)劃分寫然后根據(jù)劃分寫出對(duì)應(yīng)的等價(jià)關(guān)系出對(duì)應(yīng)的等價(jià)關(guān)系. 12等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)等價(jià)關(guān)系與劃分之間的對(duì)應(yīng)1,2和和3分別對(duì)應(yīng)等價(jià)關(guān)系分別對(duì)應(yīng)等價(jià)關(guān)系 R1, R2 和和 R3. R1=,IA，

8、R2=,IA R3=,IA4 對(duì)應(yīng)于全域關(guān)系對(duì)應(yīng)于全域關(guān)系 EA，5 對(duì)應(yīng)于恒等關(guān)系對(duì)應(yīng)于恒等關(guān)系 IA13實(shí)例實(shí)例例例3 設(shè)設(shè) A=1, 2, 3, 4，在，在 A A上定義二元關(guān)系上定義二元關(guān)系R： , R x+y = u+v，求求 R 導(dǎo)出的劃分導(dǎo)出的劃分. 解解 A A=, , , , , , , , , , , , , 14實(shí)例（續(xù)）實(shí)例（續(xù)）根據(jù)根據(jù) 的的 x + y = 2,3,4,5,6,7,8 將將A A劃分成劃分成7個(gè)個(gè)等價(jià)類：等價(jià)類： (A A)/R= , , , , , , , , , , , , , , 15偏序關(guān)系偏序關(guān)系定義定義 非空集合非空集合A上的自反、反對(duì)稱

9、和傳遞的關(guān)系，上的自反、反對(duì)稱和傳遞的關(guān)系，稱為稱為A上的上的偏序關(guān)系偏序關(guān)系，記作，記作 . 設(shè)設(shè) 為偏序關(guān)系為偏序關(guān)系, 如果如果 , 則記作則記作 x y, 讀作讀作 x“小于或等小于或等于于”y. 實(shí)例實(shí)例 集合集合A上的恒等關(guān)系上的恒等關(guān)系 IA 是是A上的偏序關(guān)系上的偏序關(guān)系. 小于或等于關(guān)系小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系集合上的偏序關(guān)系. 16相關(guān)概念相關(guān)概念x與與 y 可比可比：設(shè)：設(shè)R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, x,y A, x與與y可比可比 x y y x.結(jié)論：任取兩個(gè)元素結(jié)論：任取兩個(gè)元素x和

10、和y, 可能有下述情況：可能有下述情況： x y (或或y x), xy, x與與y不是可比的不是可比的.全序關(guān)系全序關(guān)系： R為非空集合為非空集合A上的偏序上的偏序, x,y A, x與與 y 都是可比的，都是可比的，則稱則稱 R 為為全序全序（或（或 線序線序）實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系 整除關(guān)系不是正整數(shù)集合上的全序關(guān)系整除關(guān)系不是正整數(shù)集合上的全序關(guān)系17覆蓋覆蓋：設(shè)：設(shè)R為非空集合為非空集合A上的偏序關(guān)系上的偏序關(guān)系, x, yA, 如如果果 x y且不存在且不存在 z A 使得使得 x z y, 則稱則稱 y 覆覆蓋蓋x.實(shí)例：實(shí)例

11、： 1, 2, 4, 6 集合上的整除關(guān)系集合上的整除關(guān)系, 2 覆蓋覆蓋 1, 4 和和 6 覆蓋覆蓋 2. 4 不覆蓋不覆蓋 1. 相關(guān)概念（續(xù)）相關(guān)概念（續(xù)）18偏序集與哈斯圖偏序集與哈斯圖定義定義 集合集合A和和A上的偏序關(guān)系上的偏序關(guān)系 一起叫做一起叫做偏序集偏序集, 記記作作 .實(shí)例：整數(shù)集和小于等于關(guān)系構(gòu)成偏序集實(shí)例：整數(shù)集和小于等于關(guān)系構(gòu)成偏序集，冪，冪集集P(A)和包含關(guān)系構(gòu)成偏序集和包含關(guān)系構(gòu)成偏序集. 哈斯圖哈斯圖：利用偏序自反、反對(duì)稱、傳遞性簡(jiǎn)化的關(guān)：利用偏序自反、反對(duì)稱、傳遞性簡(jiǎn)化的關(guān)系圖系圖特點(diǎn)：每個(gè)結(jié)點(diǎn)沒有環(huán)，兩個(gè)連通的結(jié)點(diǎn)之間的序特點(diǎn)：每個(gè)結(jié)點(diǎn)沒有環(huán)，兩個(gè)連通的

12、結(jié)點(diǎn)之間的序關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順關(guān)系通過結(jié)點(diǎn)位置的高低表示，位置低的元素的順序在前，具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊序在前，具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間連邊19哈斯圖實(shí)例哈斯圖實(shí)例例例4 20A=a, b, c, d, e, f, g, h R=,IA 哈斯圖實(shí)例（續(xù)）哈斯圖實(shí)例（續(xù)）例例5 已知偏序集已知偏序集的哈斯圖如右圖所示的哈斯圖如右圖所示, 試求出集合試求出集合A和關(guān)系和關(guān)系R的表達(dá)式的表達(dá)式. 21偏序集的特定元素偏序集的特定元素定義定義 設(shè)設(shè)為偏序集為偏序集, B A, yB.(1) 若若 x(xBy x) 成立成立, 則稱則稱 y 為為 B 的的最小元最小元

13、.(2) 若若 x(xBx y) 成立成立, 則稱則稱 y 為為 B 的的最大元最大元. (3) 若若x (xBx y) 成立成立, 則稱則稱 y 為為B的的極小元極小元. (4) 若若x (xBy x) 成立成立, 則稱則稱 y 為為B的的極大元極大元. 22特殊元素的性質(zhì)特殊元素的性質(zhì)n 對(duì)于有窮集，極小元和極大元必存在，可能存在對(duì)于有窮集，極小元和極大元必存在，可能存在 多個(gè)多個(gè). n 最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.n 最小元一定是極小元；最大元一定是極大元最小元一定是極小元；最大元一定是極大元. n 孤立結(jié)點(diǎn)既是極小元，也是極大元

14、孤立結(jié)點(diǎn)既是極小元，也是極大元. 23定義定義 設(shè)設(shè)為偏序集為偏序集, B A, y A. (1) 若若 x(xBx y) 成立成立, 則稱則稱 y 為為B的的上界上界. (2) 若若 x(xBy x) 成立成立, 則稱則稱 y 為為B的的下界下界. (3) 令令Cy | y為為B的上界的上界, 則稱則稱C的最小元為的最小元為B的的最小上界最小上界 或或 上確界上確界. (4) 令令Dy | y為為B的下界的下界, 則稱則稱D的最大元為的最大元為B的的最大下界最大下界 或或 下確界下確界.偏序集的特定元素偏序集的特定元素(續(xù)續(xù))24n下界、上界、下確界、上確界不一定存在下界、上界、下確界、上確界不一定存在n下界、上界存在不一定惟一下界、上界存在不一定惟一n下確界、上確界如果存在，則惟一下確界、上確界如果存在，則惟一n集合的最小元就是它的下確界，最大元就是它的集合的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì)上確界；反之不對(duì). 特殊元素的性質(zhì)特殊元素的性質(zhì)25實(shí)例實(shí)例例例6 設(shè)偏序集設(shè)偏序集如下圖所示，求如下圖所