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

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

2、 R = { | x,y∈A∧x≡y(mod 3) }其中 x≡y(mod 3) 叫做 x 與 y 模3相等, 即 x 除以3的余數(shù)與 y 除以3的余數(shù)相等.,3,等價(jià)關(guān)系的驗(yàn)證,驗(yàn)證模 3 相等關(guān)系 R 為 A上的等價(jià)關(guān)系, 因?yàn)??x∈A, 有x ≡ x(mod 3) ?x, y∈A, 若 x ≡ y(mod 3), 則有 y ≡ x(mod 3) ?x, y, z∈A, 若x ≡ y(mod 3), y ≡ z(mo

3、d 3), 則有 x≡z(mod 3)自反性、對(duì)稱性、傳遞性得到驗(yàn)證,4,A上模3等價(jià)關(guān)系的關(guān)系圖,,,設(shè) A={1,2,…,8}, R={ | x,y∈A∧x≡y(mod 3) },5,等價(jià)類,定義 設(shè)R為非空集合A上的等價(jià)關(guān)系, ?x∈A，令[x]R = { y | y∈A∧xRy }稱 [x]R 為 x 關(guān)于R 的等價(jià)類, 簡(jiǎn)稱為 x 的等價(jià)類, 簡(jiǎn)記為[x].,實(shí)例 A={ 1, 2,

4、 … , 8 }上模 3 等價(jià)關(guān)系的等價(jià)類： [1]=[4]=[7]={1,4,7} [2]=[5]=[8]={2,5,8} [3]=[6]={3,6},6,等價(jià)類的性質(zhì),定理1 設(shè)R是非空集合A上的等價(jià)關(guān)系, 則 (1) ?x∈A, [x] 是A的非空子集. (2) ?x, y∈A, 如果 x R y, 則 [x]=[y]. (3) ?x, y∈A, 如果 x y, 則 [x]與[y]不

5、交. (4) ∪{ [x] | x∈A}=A，即所有等價(jià)類的并集就是A.,7,實(shí)例,A={ 1, 2, … , 8 }上模 3 等價(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, … ,8},8,商集,定義

6、 設(shè)R為非空集合A上的等價(jià)關(guān)系, 以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集, 記做A/R, A/R = { [x]R | x∈A },實(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}}

7、 A/EA = { {1, 2, … ,8} },9,集合的劃分,定義 設(shè)A為非空集合, 若A的子集族π(π?P(A)) 滿足下面條件： (1) ??π (2) ?x?y (x,y∈π∧x≠y→x∩y=?) (3) ∪π=A 則稱π是A的一個(gè)劃分, 稱π中的元素為A的劃分塊.,10,例題,例1 設(shè)A＝{a, b, c, d}, 給定π1,π2,π3,π4,π5,π6如下： π1=

8、{ {a, b, c}, si6falt }， π2= { {a, b}, {c}, spa7r1p } π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),,商集 A/R 就是

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

10、160; R1={,}∪IA，R2={,}∪IA R3={,}∪IA,π4 對(duì)應(yīng)于全域關(guān)系 EA，π5 對(duì)應(yīng)于恒等關(guān)系 IA,13,實(shí)例,例3 設(shè) A={1, 2, 3, 4}，在 A?A上定義二元關(guān)系R： ,>?R ? x+y = u+v，求 R 導(dǎo)出的劃分.,解 A?A={, , , , , , ,,, , , , , , , },14,實(shí)例（續(xù)）,根據(jù)

11、 的 x + y = 2,3,4,5,6,7,8 將A?A劃分成7個(gè)等價(jià)類： (A?A)/R={ {}, {,}, {, , }, {, , , }, {, , }, {, }, {} },15,偏序關(guān)系,定義 非空集合A上的自反、反對(duì)

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

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

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

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

16、若?x(x∈B→y?x) 成立, 則稱 y 為 B 的最小元.(2) 若?x(x∈B→x?y) 成立, 則稱 y 為 B 的最大元. (3) 若??x (x∈B∧x ? y) 成立, 則稱 y 為B的極小元. (4) 若??x (x∈B∧y ? x) 成立, 則稱 y 為B的極大元.,22,特殊元素的性質(zhì),對(duì)于有窮集，極小元和極大元必存在，可能存在 多個(gè). 最小元和最大元不一定存在，如果存在一定惟一. 最小元一定

17、是極小元；最大元一定是極大元. 孤立結(jié)點(diǎn)既是極小元，也是極大元.,23,定義 設(shè)為偏序集, B?A, y?A. (1) 若?x(x∈B→x?y) 成立, 則稱 y 為B的上界. (2) 若?x(x∈B→y?x) 成立, 則稱 y 為B的下界. (3) 令C＝{y | y為B的上界}, 則稱C的最小元為B的最小上界 或 上確界. (4) 令D＝{y | y為B的下界}, 則稱D的最大元為B的最大下界 或 下確

18、界.,偏序集的特定元素(續(xù)),24,下界、上界、下確界、上確界不一定存在下界、上界存在不一定惟一下確界、上確界如果存在，則惟一集合的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì).,特殊元素的性質(zhì),25,實(shí)例,例6 設(shè)偏序集如下圖所示，求 A 的極小元、最小元、極大元、最大元. 設(shè) B＝{b,c,d}, 求 B 的下界、上界、下確界、上確界.,極小元：a, b, c, g；極大元：a, f, h；沒有最小元與最大元