離散數(shù)學(xué)等價關(guān)系與偏序關(guān)系

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

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

3、是是X上的一個等價關(guān)系，上的一個等價關(guān)系，x X，X的子集的子集Ex=yy X且且xRy稱為稱為x關(guān)于關(guān)于R的的等價類等價類，或，或簡記為簡記為x的等價類。的等價類。x的等價類常記為的等價類常記為x，即，即x=yy X且且xRy。例例5：設(shè)設(shè) A=1, 2, , 8, 如下定義如下定義 A上的關(guān)系上的關(guān)系R： R=(x,y)| x,y Axy (mod 3)等價類的定義等價類的定義A= 1, 2, , 8 上模上模 3 等價關(guān)系的等價類：等價關(guān)系的等價類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6集合與圖論6/30等價類的性質(zhì)等價類的性質(zhì)(3) x, y X, 如果如果(

4、x, y) R, 則則 xy=。定理定理1 設(shè)設(shè)R是非空集合是非空集合X上的等價關(guān)系上的等價關(guān)系, 則則 (1) x X, x 。(2) x, y X, 如果如果(x, y) R, 則則 x=y。 (4) ，即所有等價類的并集就是，即所有等價類的并集就是X。集合與圖論7/30 定義定義3 設(shè)設(shè)X為非空集合，為非空集合，X的若干個子集形成的集的若干個子集形成的集族族 稱為稱為X的一個的一個劃分劃分，如果，如果 具有性質(zhì)：具有性質(zhì)： 集合的劃分集合的劃分 如果如果 是是X的一個劃分，則當?shù)囊粋€劃分，則當 =k時，時， 被稱為被稱為X的一個的一個k-劃分劃分。(2) x,y ，若，若x y，則，則x

5、y=;(1) ；(3) 。 稱稱 中的元素為中的元素為X的的劃分塊劃分塊。集合與圖論8/30例例6：設(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的劃分。的劃分。實實 例例集合與圖論9/30 定理定理1 設(shè)設(shè)R是是X上的一個等價關(guān)系，則上的一個等價關(guān)系，則R的所有等的所有等價類的集合是價類的集合是X的一個劃分。的一個劃分。等價關(guān)系與集合的劃分等價關(guān)系

6、與集合的劃分 定理定理2 設(shè)設(shè) 是集合是集合X的一個劃分，令的一個劃分，令 R =(x,y) | x,y Xx與與y在在 的同一劃分塊中的同一劃分塊中則則R是是X上的一個等價關(guān)系，并且上的一個等價關(guān)系，并且 就是就是R的等價類之的等價類之集。集。注：注： 由定理由定理1、2可得：可得：X上的等價關(guān)系與上的等價關(guān)系與X的劃分的劃分是一一對應(yīng)的，并且互相確定。是一一對應(yīng)的，并且互相確定。集合與圖論10/30 定義定義4 設(shè)設(shè)R是是X上的等價關(guān)系，由上的等價關(guān)系，由R所確定的所確定的X的的劃分也就是劃分也就是R的所有等價類之集稱為的所有等價類之集稱為X對對R的的商集商集，并記并記X/R。 即：即：X

7、/R=x x X，x是是x的等價類的等價類。 等價關(guān)系等價關(guān)系R確定的劃分是確定的劃分是R的所有等價類之集的所有等價類之集 xx X商商 集集集合與圖論11/30例例7：令令A(yù)=1, 2, , 8。A關(guān)于模關(guān)于模 3 等價關(guān)系等價關(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 實實 例例集合與圖論12/30例例8：給出給出A1,2,3上所有的等價關(guān)系。上所有的等價關(guān)系。求解思路：先做出求解思路：先做出A的所有劃分的所有劃分, 然

8、后根據(jù)劃分寫出然后根據(jù)劃分寫出 對應(yīng)的等價關(guān)系。對應(yīng)的等價關(guān)系。 實實 例例集合與圖論13/30實實 例例 1, 2和和 3分別對應(yīng)于等價關(guān)系分別對應(yīng)于等價關(guān)系 R1, R2和和R3，其中，其中 R1=(2,3),(3,2)IA R2=(1,3),(3,1)IA R3=(1,2),(2,1)IAA上的等價關(guān)系與劃分之間的對應(yīng)：上的等價關(guān)系與劃分之間的對應(yīng)： 4對應(yīng)于全域關(guān)系對應(yīng)于全域關(guān)系EA； 5對應(yīng)于恒等關(guān)系對應(yīng)于恒等關(guān)系IA；問題：問題：設(shè)集合設(shè)集合X為有限集，為有限集，|X|=n，則，則X上有多少個上有多少個等價關(guān)系？等價關(guān)系？集合與圖論14/30定理定理4 設(shè)設(shè)R為為X上的一個二元關(guān)系

9、，則上的一個二元關(guān)系，則 e(R)=(RR-1)*。 R的等價閉包的等價閉包(R的自反對稱傳遞閉包的自反對稱傳遞閉包)，記為，記為e(R), e(R)是是X上包含上包含R的那些等價關(guān)系的交集。的那些等價關(guān)系的交集。 定理定理5 設(shè)設(shè)R,S是是X上的等價關(guān)系，則上的等價關(guān)系，則R S是等價關(guān)是等價關(guān)系的充要條件是系的充要條件是R S=S R。 推論推論設(shè)設(shè)R,S是是X上的等價關(guān)系，則上的等價關(guān)系，則R S是等價關(guān)是等價關(guān)系的充要條件是系的充要條件是R S S R。等價關(guān)系的運算等價關(guān)系的運算集合與圖論15/30 定義定義1 集合集合X上的二元關(guān)系上的二元關(guān)系R稱為稱為偏序關(guān)系偏序關(guān)系，如，如果果

10、R同時滿足以下三個性質(zhì)：同時滿足以下三個性質(zhì)： 當抽象地討論當抽象地討論X上的偏序關(guān)系時，常用符號上的偏序關(guān)系時，常用符號“ ”表表示偏序關(guān)系。如果示偏序關(guān)系。如果x y，則讀作，則讀作“x小于或等于小于或等于y”。1. R是自反的；是自反的；2. R是反對稱的；是反對稱的；3. R是傳遞的。是傳遞的。約定約定x y且且x y時，就記為時，就記為xy。實實 例例集合與圖論18/30 定義定義3 集合集合X上的偏序關(guān)系上的偏序關(guān)系 叫做叫做全序關(guān)系全序關(guān)系，如果，如果 x,y X，x y與與y x至少有一個成立。全序關(guān)系也稱為至少有一個成立。全序關(guān)系也稱為線性序關(guān)系線性序關(guān)系。X與全序關(guān)系與全序

11、關(guān)系構(gòu)成的二元組構(gòu)成的二元組(X,)稱為稱為全全序集序集。 偏序集與全序集的主要區(qū)別在于全序集中任兩個偏序集與全序集的主要區(qū)別在于全序集中任兩個元素均可比較元素均可比較“大小大小”，而在偏序集中任意兩個元素，而在偏序集中任意兩個元素不一定都能比較大小。不一定都能比較大小。實數(shù)間的常用的實數(shù)間的常用的“小于或等于小于或等于”關(guān)系是不是全序關(guān)關(guān)系是不是全序關(guān)系系?全序關(guān)系與全序集全序關(guān)系與全序集 集合的包含關(guān)系與自然數(shù)間的整除關(guān)系是不是全集合的包含關(guān)系與自然數(shù)間的整除關(guān)系是不是全序關(guān)系序關(guān)系?是全序關(guān)系，相應(yīng)的偏序集也是全序集。是全序關(guān)系，相應(yīng)的偏序集也是全序集。二者都不是全序關(guān)系。二者都不是全序

12、關(guān)系。集合與圖論19/30 定義定義4 設(shè)設(shè)(X,)是一個偏序集，稱是一個偏序集，稱y蓋住蓋住x，如果，如果xy且對每個且對每個z X，若，若xzy，則，則x=z或或y=z。 如果如果y蓋住蓋住x，則，則y被稱為被稱為x的的后繼后繼，而，而x稱為稱為y的的前前驅(qū)驅(qū)。蓋住的定義蓋住的定義例例3：偏序集偏序集(N,)中，稱中，稱3蓋住蓋住2，3是是2的后繼，的后繼，2是是3的先驅(qū)的先驅(qū)。 1, 2, 4, 6集合上的整除關(guān)系集合上的整除關(guān)系, 2覆蓋覆蓋1, 4 和和 6 覆覆蓋蓋2；但；但4不覆蓋不覆蓋1.集合與圖論20/30哈斯哈斯(Hasse)圖圖 首先偏序關(guān)系首先偏序關(guān)系是自反的，所以偏序

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

14、通過結(jié)點位置的高低表示，位置低的元素的順序在前位置的高低表示，位置低的元素的順序在前; (3)具有覆蓋關(guān)系的兩個結(jié)點之間連邊。具有覆蓋關(guān)系的兩個結(jié)點之間連邊。 哈斯圖哈斯圖就是利用偏序的自反、反對稱、傳就是利用偏序的自反、反對稱、傳遞性簡化了的關(guān)系圖。遞性簡化了的關(guān)系圖。哈斯哈斯(Hasse)圖的特點圖的特點集合與圖論22/30例例4：( 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整除整除) (P(a, b, c), R )哈斯圖實例哈斯圖實例集合與圖論23/30 例例5：已知偏序集已知偏序集(A,R)的哈斯圖如下圖所示，的哈斯圖如下圖所示， 試試求出集合求出集合A和關(guān)系和關(guān)系

15、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 哈斯圖實例哈斯圖實例集合與圖論24/30例例6：設(shè)設(shè)A=a1,a2,.,an是一個全序集，是一個全序集，則其元素則其元素(A,)的哈斯圖象一條鏈子一樣。的哈斯圖象一條鏈子一樣。所以，全序關(guān)系也叫做線性序關(guān)系，所以，全序關(guān)系也叫做線性序關(guān)系，全序集又稱為線性序集。全序集又稱為線性序集。可以可以“從小到大從小到大”排列為：排列為： ai1ai2.ain全序關(guān)系的哈斯圖全序關(guān)系的哈斯圖集合與圖論25/30 定義

16、定義5 設(shè)設(shè)(X,)是一個偏序集，是一個偏序集，B X。如果存在一。如果存在一個元素個元素a X使得對使得對B中每個元素中每個元素x有有xa，則稱，則稱a為為B的的一個一個上界上界。上界與下界的定義上界與下界的定義 如果存在一個元素如果存在一個元素b X，使得對，使得對B的每一個元素的每一個元素x有有bx，則稱，則稱b為為B的一個的一個下界下界。上界與下界都不一定存在。上界與下界都不一定存在。例例7：令令A(yù)=2,3,6,12,24,36，A在整除關(guān)系在整除關(guān)系“ ”下構(gòu)成下構(gòu)成一個偏序集一個偏序集(A,)。24,36不存在上界不存在上界,上界與下界可能有很多元素上界與下界可能有很多元素6,12

17、,24,36都是子集都是子集2,3的上界。的上界。2,3不存在下界不存在下界,集合與圖論26/30 定義定義6 設(shè)設(shè)(X,)是一個偏序集，是一個偏序集，B X。如果存在一個。如果存在一個元素元素a B使得對使得對B中每個元素中每個元素x有有xa，則稱，則稱a是是B中的中的最最大元素大元素。最大元素一定是上界，最小元素一定是下界最大元素一定是上界，最小元素一定是下界;最大與最小元素最大與最小元素 如果存在一個元素如果存在一個元素b B，使得對，使得對B的每一個元素的每一個元素x有有bx，則稱，則稱b是是B中的中的最小元素最小元素。 有上下界不一定有最大與最小元素有上下界不一定有最大與最小元素,最

18、大元素與最小元素若有一定是唯一的。最大元素與最小元素若有一定是唯一的。因為上下界不一定在子集中因為上下界不一定在子集中;集合與圖論27/30 定義定義7 設(shè)設(shè)(X,)是一個偏序集，是一個偏序集，B X。如果。如果B有上有上界且界且B的一切上界之集有最小元素，則這個最小上界的一切上界之集有最小元素，則這個最小上界稱為稱為B的的上確界上確界，記為，記為supB。上確界與下確界的定義上確界與下確界的定義 如果如果B有下界且有下界且B的一切下界之集有最大元素，的一切下界之集有最大元素，則這個最大下界稱為則這個最大下界稱為B的的下確界下確界，記為，記為infB。例例8：令令A(yù)=2,3,6,12,24,3

19、6，A在整除關(guān)系在整除關(guān)系“ ”下構(gòu)成下構(gòu)成一個偏序集一個偏序集(A,)。6,12,24,36都是子集都是子集2,3的上界。的上界。6是子集是子集2,3的上確界。的上確界。2,3,6,12都是子集都是子集24,36的下界。的下界。12是子集是子集24,36的下確界。的下確界。集合與圖論28/30A中有最大元素和最小元素嗎？中有最大元素和最小元素嗎？實實 例例例例9：令令A(yù)=2,3,6,12,24,36,A在整除關(guān)系在整除關(guān)系“ ”下構(gòu)成一個下構(gòu)成一個偏序集偏序集(A,)。 A中沒有最大元素也沒有最小元素。中沒有最大元素也沒有最小元素。 因為因為24與與36不可比，不可比，2與與3也不可比。也不可比。 但是但是A中沒有比中沒有比24和和36更大的元素，也沒有比更大的元素，也沒有比2與與3更小的元素。更小的元素。 稱稱24和和36都是極大元素都是極大元素,2與與3都是極小元素。都是極小元素。集合與圖論29/30 定義定義8 設(shè)設(shè)(X,)是一個偏序集，是一個偏序集，A X