離散數(shù)學(xué)第四章等價(jià)關(guān)系和偏序關(guān)系

1、1第1頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五等價(jià)關(guān)系的定義與實(shí)例定義 設(shè) R 為非空集合上的關(guān)系. 如果 R 是自反的、對稱的和傳遞的, 則稱 R 為 A 上的等價(jià)關(guān)系. 設(shè) R 是一個(gè)等價(jià)關(guān)系, 若R, 稱 x 等價(jià)于y, 記做 xy.實(shí)例 設(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ù)相等. 2第2頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五等價(jià)關(guān)系的驗(yàn)證驗(yàn)證模 3 相等關(guān)系 R 為 A上的等價(jià)關(guān)系, 因?yàn)?xA, 有x

2、 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)自反性、對稱性、傳遞性得到驗(yàn)證3第3頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五A上模3等價(jià)關(guān)系的關(guān)系圖設(shè) A=1,2,8, R= | x,yAxy(mod 3) 4第4頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五等價(jià)類定義 設(shè)R為非空集合A上的等價(jià)關(guān)系, xA，令xR = y | yAxRy 稱 xR 為 x 關(guān)于R 的等價(jià)類, 簡稱為 x 的等價(jià)類, 簡記為x. 實(shí)例 A= 1,

3、2, , 8 上模 3 等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,65第5頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五等價(jià)類的性質(zhì) 定理1 設(shè)R是非空集合A上的等價(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à)類的并集就是A. 6第6頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五實(shí)例A= 1, 2, , 8 上模 3 等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7， 2=5=8=2,5

4、,8， 3=6=3,6 以上3 類兩兩不交， 1,4,72,5,83,6 = 1,2, ,87第7頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五商集定義 設(shè)R為非空集合A上的等價(jià)關(guān)系, 以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集, 記做A/R, A/R = xR | xA 實(shí)例 A=1,2,8,A關(guān)于模3等價(jià)關(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第8頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五集合的劃分定義 設(shè)A為非空集合, 若A的子集族

5、(P(A) 滿足下面條件： (1) (2) xy (x,yxyxy=) (3) =A 則稱是A的一個(gè)劃分, 稱中的元素為A的劃分塊.9第9頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五例題例1 設(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 的劃分. 為什么？10第10頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五等價(jià)關(guān)系與劃分的一

6、一對應(yīng)商集 A/R 就是 A 的一個(gè)劃分 不同的商集對應(yīng)于不同的劃分 任給 A 的一個(gè)劃分, 如下定義 A 上的關(guān)系 R： R = | x,yAx 與 y 在的同一劃分塊中則 R 為 A上的等價(jià)關(guān)系, 且該等價(jià)關(guān)系確定的商集就是. 例2 給出A1,2,3上所有的等價(jià)關(guān)系求解思路：先做出A的所有劃分, 然后根據(jù)劃分寫出對應(yīng)的等價(jià)關(guān)系. 11第11頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五等價(jià)關(guān)系與劃分之間的對應(yīng)1,2和3分別對應(yīng)等價(jià)關(guān)系 R1, R2 和 R3. R1=,IA，R2=,IA R3=,IA4 對應(yīng)于全域關(guān)系 EA，5 對應(yīng)于恒等關(guān)系 IA12第12頁，共25頁，20

7、22年，5月20日，11點(diǎn)13分，星期五實(shí)例例3 設(shè) A=1, 2, 3, 4，在 AA上定義二元關(guān)系R： ,R x+y = u+v，求 R 導(dǎo)出的劃分. 解 AA=, , , , , , , , , , , , , 13第13頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五實(shí)例（續(xù)）根據(jù) 的 x + y = 2,3,4,5,6,7,8 將AA劃分成7個(gè)等價(jià)類： (AA)/R= , , , , , , , , , , , , , , 14第14頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五偏序關(guān)系定義 非空集合A上的自反、反對稱和傳遞的關(guān)系，稱為A上的偏序關(guān)系，記作. 設(shè)

8、為偏序關(guān)系, 如果, 則記作 xy, 讀作 x“小于或等于”y. 實(shí)例 集合A上的恒等關(guān)系 IA 是A上的偏序關(guān)系. 小于或等于關(guān)系, 整除關(guān)系和包含關(guān)系也是相應(yīng)集合上的偏序關(guān)系. 15第15頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五相關(guān)概念x與 y 可比：設(shè)R為非空集合A上的偏序關(guān)系, x,yA, x與y可比 xy yx.結(jié)論：任取兩個(gè)元素x和y, 可能有下述情況： xy (或yx), xy, x與y不是可比的.全序關(guān)系： R為非空集合A上的偏序, x,yA, x與 y 都是可比的，則稱 R 為全序（或 線序）實(shí)例：數(shù)集上的小于或等于關(guān)系是全序關(guān)系 整除關(guān)系不是正整數(shù)集合上的

9、全序關(guān)系16第16頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五覆蓋：設(shè)R為非空集合A上的偏序關(guān)系, x, yA, 如果 x y且不存在 zA 使得 x z y, 則稱 y 覆蓋x.實(shí)例： 1, 2, 4, 6 集合上的整除關(guān)系, 2 覆蓋 1, 4 和 6 覆蓋 2. 4 不覆蓋 1. 相關(guān)概念（續(xù)）17第17頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五偏序集與哈斯圖定義 集合A和A上的偏序關(guān)系一起叫做偏序集, 記作 .實(shí)例：整數(shù)集和小于等于關(guān)系構(gòu)成偏序集，冪集P(A)和包含關(guān)系構(gòu)成偏序集. 哈斯圖：利用偏序自反、反對稱、傳遞性簡化的關(guān)系圖特點(diǎn)：每個(gè)結(jié)點(diǎn)沒有環(huán)，兩個(gè)

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

11、y) 成立, 則稱 y 為 B 的最大元. (3) 若x (xBx y) 成立, 則稱 y 為B的極小元. (4) 若x (xBy x) 成立, 則稱 y 為B的極大元. 21第21頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五特殊元素的性質(zhì) 對于有窮集，極小元和極大元必存在，可能存在 多個(gè). 最小元和最大元不一定存在，如果存在一定惟一. 最小元一定是極小元；最大元一定是極大元. 孤立結(jié)點(diǎn)既是極小元，也是極大元. 22第22頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五定義 設(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的最大下界 或 下確界.偏序集的特定元素(續(xù))23第23頁，共25頁，2022年，5月20日，11點(diǎn)13分，星期五下界、上界、下確界、上確界不一定存在下界、上界存在不一定惟一下確界、上確界如果存在，則惟一集合的最小元就是它的下確界，最大元就是它的上確界；反之不對. 特殊元素的性質(zhì)24第24頁，共25頁，2022年，5月