離散數(shù)學等價關系與偏序關系（經典實用）

1、集合與圖論 離散數(shù)學等價關系與偏序關系1 第第9節(jié)節(jié) 等價關系與偏序關系等價關系與偏序關系 主要內容：主要內容： 等價關系等價關系 偏序關系偏序關系 集合與圖論 離散數(shù)學等價關系與偏序關系2 定義定義1 集合集合X上的二元關系上的二元關系R稱為稱為等價關系等價關系，如果，如果R 同時具有以下三個性質：同時具有以下三個性質： 例例1：集合集合X上的恒等關系是不是上的恒等關系是不是X上的等價關系？上的等價關系？ 1. R是自反的，即是自反的，即 x X，xRx; 2. R是對稱的，即如果是對稱的，即如果xRy，則，則yRx; 3. R是傳遞的，即如果是傳遞的，即如果xRy，yRz，則，則xRz。

2、是是X上的等價關系。上的等價關系。 1 等價關系等價關系 集合與圖論 離散數(shù)學等價關系與偏序關系3 等價關系實例等價關系實例 例例2：考慮整數(shù)集考慮整數(shù)集Z上的模上的模n同余關系。同余關系。 例例4：設設f:XY，Ker(f)=(x,y)x,y X，且，且f(x)=f(y)。 Ker(f)是是X上的等價關系上的等價關系。 例例3：實數(shù)集上的實數(shù)集上的“”、“”、“”、“”、“”都不是都不是 R上的等價關系。上的等價關系。 是等價關系。是等價關系。 集合與圖論 離散數(shù)學等價關系與偏序關系4 例例5：設設 A=1, 2, , 8, 如下定義如下定義 A上的關系上的關系R： R=(x,y)| x,y

3、 Axy (mod 3) R 的關系圖如下：的關系圖如下： 等價關系的關系圖等價關系的關系圖 集合與圖論 離散數(shù)學等價關系與偏序關系5 定義定義2 設設R是是X上的一個等價關系，上的一個等價關系，x X，X 的子集的子集Ex=yy X且且xRy稱為稱為x關于關于R的的等價類等價類，或，或 簡記為簡記為x的等價類。的等價類。 x的等價類常記為的等價類常記為x，即，即x=yy X且且xRy。 例例5：設設 A=1, 2, , 8, 如下定義如下定義 A上的關系上的關系R： R=(x,y)| x,y Axy (mod 3) 等價類的定義等價類的定義 A= 1, 2, , 8 上模上模 3 等價關系的

4、等價類：等價關系的等價類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6 集合與圖論 離散數(shù)學等價關系與偏序關系6 等價類的性質等價類的性質 (3) x, y X, 如果如果(x, y) R, 則則 xy=。 定理定理1 設設R是非空集合是非空集合X上的等價關系上的等價關系, 則則 (1) x X, x 。 (2) x, y X, 如果如果(x, y) R, 則則 x=y。 (4) ，即所有等價類的并集就是，即所有等價類的并集就是X。 集合與圖論 離散數(shù)學等價關系與偏序關系7 定義定義3 設設X為非空集合，為非空集合，X的若干個子集形成的集的若干個子集形成的集 族族 稱為稱為

5、X的一個的一個劃分劃分，如果，如果 具有性質：具有性質： 集合的劃分集合的劃分 如果如果 是是X的一個劃分，則當?shù)囊粋€劃分，則當 =k時，時， 被稱為被稱為X 的一個的一個k-劃分劃分。 (2) x,y ，若，若x y，則，則xy=; (1) ； (3) 。 稱稱 中的元素為中的元素為X的的劃分塊劃分塊。 集合與圖論 離散數(shù)學等價關系與偏序關系8 例例6：設設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

6、1和和 2是是A的劃分，其他都不是的劃分，其他都不是A的劃分。的劃分。 實實 例例 集合與圖論 離散數(shù)學等價關系與偏序關系9 定理定理1 設設R是是X上的一個等價關系，則上的一個等價關系，則R的所有等的所有等 價類的集合是價類的集合是X的一個劃分。的一個劃分。 等價關系與集合的劃分等價關系與集合的劃分 定理定理2 設設 是集合是集合X的一個劃分，令的一個劃分，令 R =(x,y) | x,y Xx與與y在在 的同一劃分塊中的同一劃分塊中 則則R是是X上的一個等價關系，并且上的一個等價關系，并且 就是就是R的等價類之的等價類之 集。集。 注：注： 由定理由定理1、2可得：可得：X上的等價關系與上

7、的等價關系與X的劃分的劃分 是一一對應的，并且互相確定。是一一對應的，并且互相確定。 集合與圖論 離散數(shù)學等價關系與偏序關系10 定義定義4 設設R是是X上的等價關系，由上的等價關系，由R所確定的所確定的X的的 劃分也就是劃分也就是R的所有等價類之集稱為的所有等價類之集稱為X對對R的的商集商集， 并記并記X/R。 即：即：X/R=x x X，x是是x的等價類的等價類。 等價關系等價關系R確定的劃分是確定的劃分是R的所有等價類之集的所有等價類之集 xx X 商商 集集 集合與圖論 離散數(shù)學等價關系與偏序關系11 例例7：令令A=1, 2, , 8。 A關于模關于模 3 等價關系等價關系R 的商集

8、為：的商集為： A/R = 1, 4,7, 2, 5, 8, 3, 6 A關于恒等關系和全域關系的商集為：關于恒等關系和全域關系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 實實 例例 集合與圖論 離散數(shù)學等價關系與偏序關系12 例例8：給出給出A1,2,3上所有的等價關系。上所有的等價關系。 求解思路：先做出求解思路：先做出A的所有劃分的所有劃分, 然后根據(jù)劃分寫出然后根據(jù)劃分寫出 對應的等價關系。對應的等價關系。 實實 例例 集合與圖論 離散數(shù)學等價關系與偏序關系13 實實 例例 1, 2和和 3分別對應于等價關系分別對應于等價關系 R1, R2和和R3，其中，

9、其中 R1=(2,3),(3,2)IA R2=(1,3),(3,1)IA R3=(1,2),(2,1)IA A上的等價關系與劃分之間的對應：上的等價關系與劃分之間的對應： 4對應于全域關系對應于全域關系EA； 5對應于恒等關系對應于恒等關系IA； 問題：問題：設集合設集合X為有限集，為有限集，|X|=n，則，則X上有多少個上有多少個 等價關系？等價關系？ 集合與圖論 離散數(shù)學等價關系與偏序關系14 定理定理4 設設R為為X上的一個二元關系，則上的一個二元關系，則 e(R)=(RR-1)*。 R的等價閉包的等價閉包(R的自反對稱傳遞閉包的自反對稱傳遞閉包)，記為，記為e(R), e(R)是是X上

10、包含上包含R的那些等價關系的交集。的那些等價關系的交集。 定理定理5 設設R,S是是X上的等價關系，則上的等價關系，則R S是等價關是等價關 系的充要條件是系的充要條件是R S=S R。 推論推論設設R,S是是X上的等價關系，則上的等價關系，則R S是等價關是等價關 系的充要條件是系的充要條件是R S S R。 等價關系的運算等價關系的運算 集合與圖論 離散數(shù)學等價關系與偏序關系15 定義定義1 集合集合X上的二元關系上的二元關系R稱為稱為偏序關系偏序關系，如，如 果果R同時滿足以下三個性質：同時滿足以下三個性質： 當抽象地討論當抽象地討論X上的偏序關系時，常用符號上的偏序關系時，常用符號“

11、”表表 示偏序關系。如果示偏序關系。如果x y，則讀作，則讀作“x小于或等于小于或等于y”。 1. R是自反的；是自反的； 2. R是反對稱的；是反對稱的； 3. R是傳遞的。是傳遞的。 約定約定x y且且x y時，就記為時，就記為xy。 實實 例例 集合與圖論 離散數(shù)學等價關系與偏序關系18 定義定義3 集合集合X上的偏序關系上的偏序關系 叫做叫做全序關系全序關系，如果，如果 x,y X，x y與與y x至少有一個成立。全序關系也稱為至少有一個成立。全序關系也稱為 線性序關系線性序關系。X與全序關系與全序關系構成的二元組構成的二元組(X,)稱為稱為全全 序集序集。 偏序集與全序集的主要區(qū)別在

12、于全序集中任兩個偏序集與全序集的主要區(qū)別在于全序集中任兩個 元素均可比較元素均可比較“大小大小”，而在偏序集中任意兩個元素，而在偏序集中任意兩個元素 不一定都能比較大小。不一定都能比較大小。 實數(shù)間的常用的實數(shù)間的常用的“小于或等于小于或等于”關系是不是全序關關系是不是全序關 系系? 全序關系與全序集全序關系與全序集 集合的包含關系與自然數(shù)間的整除關系是不是全集合的包含關系與自然數(shù)間的整除關系是不是全 序關系序關系? 是全序關系，相應的偏序集也是全序集。是全序關系，相應的偏序集也是全序集。 二者都不是全序關系。二者都不是全序關系。 集合與圖論 離散數(shù)學等價關系與偏序關系19 定義定義4 設設(

13、X,)是一個偏序集，稱是一個偏序集，稱y蓋住蓋住x，如果，如果 xy且對每個且對每個z X，若，若xzy，則，則x=z或或y=z。 如果如果y蓋住蓋住x，則，則y被稱為被稱為x的的后繼后繼，而，而x稱為稱為y的的前前 驅驅。 蓋住的定義蓋住的定義 例例3：偏序集偏序集(N,)中，稱中，稱3蓋住蓋住2，3是是2的后繼，的后繼，2是是3 的先驅的先驅。 1, 2, 4, 6集合上的整除關系集合上的整除關系, 2覆蓋覆蓋1, 4 和和 6 覆覆 蓋蓋2；但；但4不覆蓋不覆蓋1. 集合與圖論 離散數(shù)學等價關系與偏序關系20 哈斯哈斯(Hasse)圖圖 首先偏序關系首先偏序關系是自反的，所以偏序關系的關

14、系圖是自反的，所以偏序關系的關系圖 中每個頂點都有一個環(huán)，因此可以省略每個頂點的環(huán)。中每個頂點都有一個環(huán)，因此可以省略每個頂點的環(huán)。 其次由于偏序關系是傳遞的，那么只要在前驅與其次由于偏序關系是傳遞的，那么只要在前驅與 后繼間聯(lián)線即可。后繼間聯(lián)線即可。 最后由于反對稱性，若最后由于反對稱性，若xy，x y，則點，則點y畫在畫在x 的上方，這樣就不必用矢線了，按上述方法畫出的的上方，這樣就不必用矢線了，按上述方法畫出的 圖稱為圖稱為(X,)的的哈斯圖哈斯圖。 集合與圖論 離散數(shù)學等價關系與偏序關系21 特點：特點： (1)每個結點沒有環(huán)每個結點沒有環(huán); (2)兩個連通的結點之間的序關系通過結點兩

15、個連通的結點之間的序關系通過結點 位置的高低表示，位置低的元素的順序在前位置的高低表示，位置低的元素的順序在前; (3)具有覆蓋關系的兩個結點之間連邊。具有覆蓋關系的兩個結點之間連邊。 哈斯圖哈斯圖就是利用偏序的自反、反對稱、傳就是利用偏序的自反、反對稱、傳 遞性簡化了的關系圖。遞性簡化了的關系圖。 哈斯哈斯(Hasse)圖的特點圖的特點 集合與圖論 離散數(shù)學等價關系與偏序關系22 例例4：( 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整除 整除) (P(a, b, c), R ) 哈斯圖實例哈斯圖實例 集合與圖論 離散數(shù)學等價關系與偏序關系23 例例5：已知偏序集已知偏序集(

16、A,R)的哈斯圖如下圖所示，的哈斯圖如下圖所示， 試試 求出集合求出集合A和關系和關系R的表達式。的表達式。 A=a, b, c, d, e, f, g, h R=(b,d),(b,e),(b,f),(c,d), (c,e),(c,f),(d,f),(e,f), (g,h)IA 哈斯圖實例哈斯圖實例 集合與圖論 離散數(shù)學等價關系與偏序關系24 例例6：設設A=a1,a2,.,an是一個全序集，是一個全序集，則其元素則其元素 (A,)的哈斯圖象一條鏈子一樣。的哈斯圖象一條鏈子一樣。 所以，全序關系也叫做線性序關系，所以，全序關系也叫做線性序關系， 全序集又稱為線性序集。全序集又稱為線性序集。 可

17、以可以“從小到大從小到大”排列為：排列為： ai1ai2.ain 全序關系的哈斯圖全序關系的哈斯圖 集合與圖論 離散數(shù)學等價關系與偏序關系25 定義定義5 設設(X,)是一個偏序集，是一個偏序集，B X。如果存在一。如果存在一 個元素個元素a X使得對使得對B中每個元素中每個元素x有有xa，則稱，則稱a為為B的的 一個一個上界上界。 上界與下界的定義上界與下界的定義 如果存在一個元素如果存在一個元素b X，使得對，使得對B的每一個元素的每一個元素x 有有bx，則稱，則稱b為為B的一個的一個下界下界。 上界與下界都不一定存在。上界與下界都不一定存在。 例例7：令令A=2,3,6,12,24,36

18、，A在整除關系在整除關系“ ”下構成下構成 一個偏序集一個偏序集(A,)。 24,36不存在上界不存在上界, 上界與下界可能有很多元素上界與下界可能有很多元素 6,12,24,36都是子集都是子集2,3的上界。的上界。 2,3不存在下界不存在下界, 集合與圖論 離散數(shù)學等價關系與偏序關系26 定義定義6 設設(X,)是一個偏序集，是一個偏序集，B X。如果存在一個。如果存在一個 元素元素a B使得對使得對B中每個元素中每個元素x有有xa，則稱，則稱a是是B中的中的最最 大元素大元素。 最大元素一定是上界，最小元素一定是下界最大元素一定是上界，最小元素一定是下界; 最大與最小元素最大與最小元素

19、如果存在一個元素如果存在一個元素b B，使得對，使得對B的每一個元素的每一個元素x有有 bx，則稱，則稱b是是B中的中的最小元素最小元素。 有上下界不一定有最大與最小元素有上下界不一定有最大與最小元素, 最大元素與最小元素若有一定是唯一的。最大元素與最小元素若有一定是唯一的。 因為上下界不一定在子集中因為上下界不一定在子集中; 集合與圖論 離散數(shù)學等價關系與偏序關系27 定義定義7 設設(X,)是一個偏序集，是一個偏序集，B X。如果。如果B有上有上 界且界且B的一切上界之集有最小元素，則這個最小上界的一切上界之集有最小元素，則這個最小上界 稱為稱為B的的上確界上確界，記為，記為supB。 上

20、確界與下確界的定義上確界與下確界的定義 如果如果B有下界且有下界且B的一切下界之集有最大元素，的一切下界之集有最大元素， 則這個最大下界稱為則這個最大下界稱為B的的下確界下確界，記為，記為infB。 例例8：令令A=2,3,6,12,24,36，A在整除關系在整除關系“ ”下構成下構成 一個偏序集一個偏序集(A,)。 6,12,24,36都是子集都是子集2,3的上界。的上界。 6是子集是子集2,3的上確界。的上確界。 2,3,6,12都是子集都是子集24,36的下界。的下界。 12是子集是子集24,36的下確界。的下確界。 集合與圖論 離散數(shù)學等價關系與偏序關系28 A中有最大元素和最小元素嗎

21、？中有最大元素和最小元素嗎？ 實實 例例 例例9：令令A=2,3,6,12,24,36,A在整除關系在整除關系“ ”下構成一個下構成一個 偏序集偏序集(A,)。 A中沒有最大元素也沒有最小元素。中沒有最大元素也沒有最小元素。 因為因為24與與36不可比，不可比，2與與3也不可比。也不可比。 但是但是A中沒有比中沒有比24和和36更大的元素，也沒有比更大的元素，也沒有比2與與 3更小的元素。更小的元素。 稱稱24和和36都是極大元素都是極大元素,2與與3都是極小元素。都是極小元素。 集合與圖論 離散數(shù)學等價關系與偏序關系29 定義定義8 設設(X,)是一個偏序集，是一個偏序集，A X，A中元素中元素s稱為稱為 A的的極大元素極大元素，如果，如果A中沒有元素中沒有元素m使