離散數學-等價關系與偏序關系

1、離散數學離散數學集合論集合論 2 / 68主要內容n集合代數n二元關系n函數集合的基本概念集合的運算有窮集合的計數集合恒等式有序對與笛卡兒積二元關系關系的運算關系的性質 關系的閉包等價關系與劃分偏序關系函數的定義與性質函數的復合與反函數雙射函數與集合的基數 3 / 687.6 等價關系與劃分例例7.167.16 設設 A=1,2A=1,2,8,8,定義定義 A A 上的關系上的關系 R R如下如下: : 驗證驗證R R是是A A上的等價關系上的等價關系. . )3(mod,yxAyxyxR一一. . 等價關系等價關系 定義定義7.157.15 設設R R為非空集合為非空集合A A上的關系上的關

2、系. .如果如果R R是是自反的自反的, , 對稱的對稱的和和傳遞的傳遞的, ,則稱則稱R R為為A A上的等價關系上的等價關系. .對等價關系對等價關系R,R,若若 R, R, 則稱則稱 x x 等價于等價于y y, ,記為記為x xy y oror xRy xRy. . x) 3(modxx 解解: : x x A,A,有有 , , 故故R R是自反的是自反的. .) 3(modyx ) 3(modxy x,yx,y A A, , 若若 , , 則則 , , 故故R R是對稱的是對稱的. .) 3(modyx ) 3(modzy ) 3(modzx x,y,zx,y,z A,A,若若 ,

3、, 則則 , , 故故 R R是傳遞的是傳遞的. . R R是是A A上的一個等價關系上的一個等價關系. . 4 / 68等價類定義定義 7.167.16 設設 R R 為非空集合為非空集合A A上的等價關系上的等價關系, , x x A, A, 令令稱稱 x x R R為為x x在在R R下的等價類下的等價類 ( (簡稱為簡稱為x x的等價類的等價類),),有時簡記為有時簡記為 x x . . x x 稱為該等價類的代表元稱為該等價類的代表元. . 注注: :一個等價類是一個等價類是A A中在等價關系中在等價關系R R下彼此等價的所有元素的集下彼此等價的所有元素的集 合合, ,等價類中各元素

4、的地位是平等的等價類中各元素的地位是平等的, ,每個元素都可以作為每個元素都可以作為 其所在等價類的代表元其所在等價類的代表元. .例如例如, ,在上例中的等價關系在上例中的等價關系R R下下,A,A中元素形成了三個等價類中元素形成了三個等價類: : 1 1 = = 4 4 = = 7 7 =1, 4, 7; =1, 4, 7; 2 2 = = 5 5 = = 8 8 =2, 5, 8;=2, 5, 8; 3 3 = = 6 6 =3, 6.=3, 6. )(xRyAyyxR, , , , , , , , , , , , , , , 5 / 68等價類的性質定理定理7.147.14 設設 R

5、R 為非空集合為非空集合 A A上的等價關系上的等價關系, ,則則 （1 1） x x A, A, x x 是是A A的非空子集的非空子集. . （2 2） x, yx, y A,A,如果如果xRyxRy, , 則則 x x = = y y （3 3） x, yx, y A,A,如果如果x x與與y y不具有關系不具有關系 R, R, 則則 x x 與與 y y 不相交不相交. . （4 4） x | xA = A x | xA = A證證：(1) (1) 顯然顯然. . (2) z(2) zx x R R R R（R R是對稱的）是對稱的） RR R R R R R R z zy y , ,

6、 從而從而 x x y y 同理可得同理可得, , y y x x . . 故故 x x = = y y 6 / 68等價類的性質(3) (3) 反證法反證法. . 假設假設 x x y y , ,則存在則存在 z zx x y y . . 因而因而 z z x x 且且z z y y , ,即即 RR R. R. 根據根據R R的對稱性和傳遞性的對稱性和傳遞性, ,必有必有 R.R.這與前提條件矛盾這與前提條件矛盾. . 故原命題成立故原命題成立. .AAxxAAxx)()(AxAyxyAxxAxxyAAxxAxxyAyyyAyAxxAAAxx(4) 先證先證 再證再證 因此因此 7 / 6

7、8商集與劃分定義定義7.177.17 設設R R為非空集合為非空集合A A上的等價關系上的等價關系, ,以以R R的所有等價類作為元素的所有等價類作為元素, , 形成的集合稱為形成的集合稱為A A關于關于R R的的商集商集, ,記為記為A/R,A/R,即即: :例如例如: :例例7.167.16中等價關系形成的商集為中等價關系形成的商集為: : A/R A/R 1, 4, 7, 2, 5, 8, 3, 61, 4, 7, 2, 5, 8, 3, 6AxxRAR/定義定義7.187.18 設設A A為非空集合為非空集合, ,若若A A的子集族的子集族 ( (P(A), P(A), 是由是由A A

8、的一些子集形的一些子集形成的集合成的集合) ) 滿足下列條件滿足下列條件: : (1) (1) (2) (2) x x y(x,yy(x,y xyxy= xyxy= ) ) (3) (3) 則稱則稱 是是A A的一個的一個劃分劃分, ,而稱而稱 中的元素為中的元素為 A A的劃分塊或類的劃分塊或類. . 五五. . 集合的劃分集合的劃分 xAx 8 / 68等價關系與劃分例例7.17 7.17 設設A=a, b, c, d , A=a, b, c, d , 則則 1 1=a,b,c ,d=a,b,c ,d和和 2 2=a,b,c,d=a,b,c,d都是都是A A的劃分的劃分, ,而而 3 3=

9、a,a,b,c,d=a,a,b,c,d和和 4 4= = ,a,b,c,a,b,c都不是都不是A A的劃分的劃分. .注注: :給定非空有限集給定非空有限集A A上的一個等價關系上的一個等價關系R,R,在在R R下彼此等價的元素構成的子下彼此等價的元素構成的子集便形成了集便形成了A A的一個劃分的一個劃分, ,它其實就是商集它其實就是商集A/R, A/R, 其每個類其每個類 ( (等價塊等價塊) ) 就是就是R R的一個等價類的一個等價類; ; 反之反之, ,任給任給A A的一個的一個 劃分劃分 , ,可定義可定義A A上的關系上的關系R R如下如下: : R= R= x,yx,y AxAx與

10、與y y在在 的同一個類中的同一個類中 可以驗證可以驗證R R是是A A上的一個等價關系上的一個等價關系. .可見可見A A上的等價關系與上的等價關系與A A的劃分是一一的劃分是一一對應的對應的. . 9 / 68例例例7.187.18 求求A=1, 2, 3A=1, 2, 3上所有的等價關系上所有的等價關系. .解解 先求出先求出A A的所有劃分的所有劃分: : 1 1=1, 2, 3; =1, 2, 3; 2 2=1, 2, 3=1, 2, 3； 3 3=2, 1, 3; =2, 1, 3; 4 4=3, 1, 2;=3, 1, 2; 5 5= 1, 2, 3.= 1, 2, 3. 與這些

11、劃分一一對應的等價關系是與這些劃分一一對應的等價關系是: : 1 1: : 全域關系全域關系E EA A 2 2: R: R2 2=, I=, IA A 3 3: R: R3 3=, I=, IA A 4 4: R: R4 4=, I=, IA A 5 5: : 恒等關系恒等關系I IA A 10 / 687.7 偏序關系1 1偏序關系與偏序集偏序關系與偏序集定義定義7.197.19 設設R R為非空集合為非空集合A A上的關系上的關系. .如果如果R R是是自反的自反的, ,反對稱的反對稱的和和傳遞的傳遞的, ,則稱則稱 R R 為為 A A上的偏序關系上的偏序關系, ,記為記為 . . 對

12、一個偏序關系對一個偏序關系 , ,如果如果 , ,則記為則記為 x x y.y.注注: : 1. 1. 集合集合A A上的恒等關系上的恒等關系I IA A和空關系都是和空關系都是A A上的偏序關系上的偏序關系, ,但全域關但全域關系系E EA A 一般不是一般不是A A上的偏序關系上的偏序關系. . 2. 2. 實數域上的小于等于關系（大于等于關系）實數域上的小于等于關系（大于等于關系）, ,自然數域上的整自然數域上的整除關系除關系, ,集合的包含關系等都是偏序關系集合的包含關系等都是偏序關系. . 11 / 68可比與不可比注注: :在具有偏序關系的集合在具有偏序關系的集合A A中任二元素中

13、任二元素 x x 和和 y y 之間必有下列四之間必有下列四 種情形之一種情形之一: : x x y ,yy ,y x ,x=y ,xx ,x=y ,x與與y y不可比不可比. .例例 設設A=1, 2, 3A=1, 2, 3(1)(1) 是是A A上的整除關系上的整除關系, ,則則:1:1 2, 12, 1 3, 13, 11, 21, 22, 32, 33,3, 2 2 和和 3 3 不可比不可比; ;(2) (2) 是是 A A 上的大于等于關系上的大于等于關系, ,則則: 2 : 2 1, 3 1, 3 1, 3 1, 3 2, 1 2, 11, 21, 22,32,33.3.定義定義

14、7.207.20 設設R R為非空集合為非空集合A A上的偏序關系上的偏序關系, ,定義定義 (1) (1) x, yx, y A A, x , x y y當且僅當當且僅當 x x y y且且 xyxy (2) (2) x, yx, y A A, x , x 與與 y y 可比當且僅當可比當且僅當 x x y y 或或 y y x x 12 / 68偏序集定義定義7.217.21 設設R R為非空集合為非空集合A A上的偏序關系上的偏序關系, ,如果如果 x, yx, y A, x A, x 與與 y y 都是可比都是可比的的, ,則稱則稱R R為為A A上的全序關系上的全序關系. . 例如例

15、如 大于等于關系大于等于關系( (小于等于關系小于等于關系) )是全序集是全序集, ,但整除關系一般不是全序集但整除關系一般不是全序集. .定義定義7.227.22 帶有某種指定的偏序關系帶有某種指定的偏序關系 的集合的集合A A稱為偏序集稱為偏序集, ,記為記為A, .例如例如 整數集整數集Z Z和數的小于等于關系和數的小于等于關系構成偏序集構成偏序集 z, ; ; 集合集合A A的冪集的冪集P(A)P(A)和集合的包含關系和集合的包含關系 構成偏序集構成偏序集P(A), .定義定義7.237.23 設設 A, 為偏序集為偏序集, , x, y x, y A,A,如果如果 x x y y且不

16、存在且不存在 z z A, A, 使得使得x x z z y, y, 則稱則稱 y y 覆蓋覆蓋 x.x. 例如例如 A=1, 2, 4, 6A=1, 2, 4, 6上的整除關系上的整除關系, ,有有2 2覆蓋覆蓋1,41,4和和6 6都覆蓋都覆蓋2,2,但但4 4不覆蓋不覆蓋1,61,6不覆蓋不覆蓋4.4. 13 / 68哈斯圖 利用偏序關系的自反性利用偏序關系的自反性, ,反對稱性和傳遞性可簡化偏序關系的關系圖反對稱性和傳遞性可簡化偏序關系的關系圖, ,得得到偏序集的哈斯圖到偏序集的哈斯圖. . 設有偏序集設有偏序集A, , , 其哈斯圖的畫法如下其哈斯圖的畫法如下: :(1) (1) 以

17、以 A A 的元素作為頂點的元素作為頂點, ,適當排列各頂點的順序適當排列各頂點的順序, ,使得對使得對 x, y x, y A, A, 若若x x y, y, 則將則將 x x 畫在畫在 y y 的下方的下方. .(2) (2) 對對A A中兩個不同元素中兩個不同元素x x和和y,y,如果如果y y覆蓋覆蓋x,x,則用一條線段連接則用一條線段連接 x x 和和 y.y.例例7.197.19 畫出偏序集畫出偏序集1,2,3,1,2,3,9,R,9,R整除整除 和和 的哈斯圖的哈斯圖. . 解解: :它們的哈斯圖分別為圖它們的哈斯圖分別為圖A,A,圖圖B B表示如下表示如下: : 8472369

18、51圖圖A Aa,ba,b,cabb,cca,c 圖圖B B 14 / 68例例例7.207.20 已知偏序集已知偏序集的哈斯圖如下的哈斯圖如下: :求集合求集合A A和關系和關系R R的表達式的表達式. .aedfhgbc解解 A=a, b, c, d, e, f, g, h,A=a, b, c, d, e, f, g, h, R=,IR=,IA.A. 15 / 68特殊元素定義定義7.247.24 設設A, 為偏序集為偏序集, , B B A, yA, y B.B.(1) (1) 若若 x(xx(x ByBy x) x) 成立成立, ,則稱則稱 y y 是是B B的最小元的最小元; ;(2

19、) (2) 若若 x(xx(x BxBx y) y) 成立成立, ,則稱則稱 y y 是是B B的最大元的最大元; ;(3) (3) 若若 x(xx(x BxBx yx=y) yx=y) 成立成立, ,則稱則稱 y y 是是B B的極小元的極小元; ;(4) (4) 若若 x(xx(x ByBy xx=y)xx=y)成立成立, ,則稱則稱 y y 是是B B的極大元的極大元. .注注: :(1)(1) 極大極大 ( (極小極小) ) 元未必是最大元未必是最大 ( (最小最小) ) 元元. .極大極大 ( (極小極小) ) 元未必與元未必與B B中中任何元素都可比任何元素都可比; ;(2) (2

20、) 對有限集對有限集B,B,極大極大( (極小極小) )元一定存在元一定存在, ,但最大但最大( (最小最小) )元不一定存在元不一定存在; ;(3) (3) 最大最大 ( (最小最小) ) 元如果存在元如果存在, ,必定是唯一的必定是唯一的; ; 而極大而極大 ( (極小極小) ) 元一般元一般不唯一不唯一. .但如果但如果B B中只有一個極大中只有一個極大 ( (極小極小) ) 元元, , 則它一定是則它一定是B B的最大的最大 ( (最小最小) ) 元元. . 16 / 68例解解: :極大元極大元:a, f, h; :a, f, h; 極小元極小元: a,b,c,g; : a,b,c,

21、g; 無最大元和最小元無最大元和最小元. .例例7.217.21 求上例中求上例中A A的極大元的極大元, ,極小元極小元, ,最大元最大元, ,最小元最小元例例7.227.22 設設x x為集合為集合,A=P(x)-,A=P(x)- -x,-x,且且A A , ,若若 |x|= n, |x|= n, 問問: : (1) (1)偏序集偏序集 A, R 是否有最大元是否有最大元? ? (2) (2)偏序集偏序集 A, R 是否有最小元是否有最小元? ? (3) (3)偏序集偏序集 A, R 中極大元和極小元的一般形式是什么中極大元和極小元的一般形式是什么? ?解解: :首先首先, ,因因A A

22、, , 故故n2,xn2,x中單個元素構成的子集都在中單個元素構成的子集都在 A A中中, ,他們他們在在 R R 下互相不可比下互相不可比, , 因此因此A A中無最大元和最小元中無最大元和最小元. .例例 x = 1,2,3, A = 1, 2, 3, 1,2, 1,3, 2,3 和和 x 不是不是A中元素中元素, 故故A中無最小元和最大元中無最小元和最大元1, 2, 3 都是極小元都是極小元; 1,2, 1,3, 2,3 都是極大元都是極大元 17 / 68例 其次考察其次考察(P(x),R(P(x),R ) )的哈斯圖的哈斯圖. . 其最低層是空集其最低層是空集 , ,記為第記為第0 0層層, ,由底向上由底向上, ,第第1 1層是單元集層是單元集, ,第第2 2層是層是二元子集二元子集, , , 第第n-1n-1層是層是x x的所有的所有n-1n-1元子集元子集, ,最頂層即第最頂層即第n n層層, ,只有一個只有一個頂點頂點x x. . 偏序