離散數(shù)學等價關系與偏序關系(1)

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

2、系集合與圖論精選ppt3等價關系實例等價關系實例例例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上的等價關系。上的等價關系。是等價關系。是等價關系。集合與圖論精選ppt4例例5：設設 A=1, 2, , 8, 如下定義如下定義 A上的關系上的關系R： R=(x,y)| x,y Axy (mod 3)R 的關系圖如下：的關系圖如下：等價關系的關系圖等價關系的關系圖集合與圖論精選ppt5

3、 定義定義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 等價關系的等價類：等價關系的等價類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6集合與圖論精選ppt6等價類的性質(zhì)等價類的性質(zhì)(3) x

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

5、y ，若，若x y，則，則xy=;(1) ；(3) 。 稱稱 中的元素為中的元素為X的的劃分塊劃分塊。集合與圖論精選ppt8例例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 1和和 2是是A的劃分，其他都不是的劃分，其他都不是A的劃分。的劃分。實實 例例集合與圖論精選ppt9 定理定理1 設設R是是X上的一個等價關系，則上的一個等價關系，則R的所有等的所有等價類的集合是價類的集合是X的一個劃分。的一

6、個劃分。等價關系與集合的劃分等價關系與集合的劃分 定理定理2 設設 是集合是集合X的一個劃分，令的一個劃分，令 R =(x,y) | x,y Xx與與y在在 的同一劃分塊中的同一劃分塊中則則R是是X上的一個等價關系，并且上的一個等價關系，并且 就是就是R的等價類之集。的等價類之集。注：注： 由定理由定理1、2可得：可得：X上的等價關系與上的等價關系與X的劃分的劃分是一一對應的，并且互相確定。是一一對應的，并且互相確定。集合與圖論精選ppt10 定義定義4 設設R是是X上的等價關系，由上的等價關系，由R所確定的所確定的X的的劃分也就是劃分也就是R的所有等價類之集稱為的所有等價類之集稱為X對對R的

7、的商集商集，并記并記X/R。 即：即：X/R=x x X，x是是x的等價類的等價類。 等價關系等價關系R確定的劃分是確定的劃分是R的所有等價類之集的所有等價類之集 xx X商商 集集集合與圖論精選ppt11例例7：令令A=1, 2, , 8。A關于模關于模 3 等價關系等價關系R 的商集為：的商集為： A/R = 1, 4,7, 2, 5, 8, 3, 6 A關于恒等關系和全域關系的商集為：關于恒等關系和全域關系的商集為： A/IA = 1,2, ,8 A/EA = 1, 2, ,8 實實 例例集合與圖論精選ppt12例例8：給出給出A1,2,3上所有的等價關系。上所有的等價關系。求解思路：先

8、做出求解思路：先做出A的所有劃分的所有劃分, 然后根據(jù)劃分寫出然后根據(jù)劃分寫出 對應的等價關系。對應的等價關系。 實實 例例集合與圖論精選ppt13實實 例例 1, 2和和 3分別對應于等價關系分別對應于等價關系 R1, R2和和R3，其中，其中 R1=(2,3),(3,2)IA R2=(1,3),(3,1)IA R3=(1,2),(2,1)IAA上的等價關系與劃分之間的對應：上的等價關系與劃分之間的對應： 4對應于全域關系對應于全域關系EA； 5對應于恒等關系對應于恒等關系IA；問題：問題：設集合設集合X為有限集，為有限集，|X|=n，則，則X上有多少個上有多少個等價關系？等價關系？集合與圖

9、論精選ppt14定理定理4 設設R為為X上的一個二元關系，則上的一個二元關系，則 e(R)=(RR-1)*。 R的等價閉包的等價閉包(R的自反對稱傳遞閉包的自反對稱傳遞閉包)，記為，記為e(R), e(R)是是X上包含上包含R的那些等價關系的交集。的那些等價關系的交集。 定理定理5 設設R,S是是X上的等價關系，則上的等價關系，則R S是等價關是等價關系的充要條件是系的充要條件是R S=S R。 推論推論設設R,S是是X上的等價關系，則上的等價關系，則R S是等價關是等價關系的充要條件是系的充要條件是R S S R。等價關系的運算等價關系的運算集合與圖論精選ppt15 定義定義1 集合集合X上

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

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

12、關系，相應的偏序集也是全序集。二者都不是全序關系。二者都不是全序關系。集合與圖論精選ppt19 定義定義4 設設(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集合上的整除關系集合上的整除關系, 2覆蓋覆蓋1, 4 和和 6 覆覆蓋蓋2；但；但4不覆蓋不覆蓋1.集合與圖論精選ppt2

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

14、沒有環(huán); (2)兩個連通的結(jié)點之間的序關系通過結(jié)點兩個連通的結(jié)點之間的序關系通過結(jié)點位置的高低表示，位置低的元素的順序在前位置的高低表示，位置低的元素的順序在前; (3)具有覆蓋關系的兩個結(jié)點之間連邊。具有覆蓋關系的兩個結(jié)點之間連邊。 哈斯圖哈斯圖就是利用偏序的自反、反對稱、傳就是利用偏序的自反、反對稱、傳遞性簡化了的關系圖。遞性簡化了的關系圖。哈斯哈斯(Hasse)圖的特點圖的特點集合與圖論精選ppt22例例4：( 1, 2, 3, 4, 5, 6, 7, 8, 9 , R整除整除) (P(a, b, c), R )哈斯圖實例哈斯圖實例集合與圖論精選ppt23 例例5：已知偏序集已知偏序集(

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

16、排列為： ai1ai2.ain全序關系的哈斯圖全序關系的哈斯圖集合與圖論精選ppt25 定義定義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，A在整除關系在整除關系“ ”下構(gòu)成下構(gòu)成一個偏序集一個偏序集(A,

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

18、是B中的中的最小元素最小元素。 有上下界不一定有最大與最小元素有上下界不一定有最大與最小元素,最大元素與最小元素若有一定是唯一的。最大元素與最小元素若有一定是唯一的。因為上下界不一定在子集中因為上下界不一定在子集中;集合與圖論精選ppt27 定義定義7 設設(X,)是一個偏序集，是一個偏序集，B X。如果。如果B有上有上界且界且B的一切上界之集有最小元素，則這個最小上界的一切上界之集有最小元素，則這個最小上界稱為稱為B的的上確界上確界，記為，記為supB。上確界與下確界的定義上確界與下確界的定義 如果如果B有下界且有下界且B的一切下界之集有最大元素，的一切下界之集有最大元素，則這個最大下界稱為

19、則這個最大下界稱為B的的下確界下確界，記為，記為infB。例例8：令令A=2,3,6,12,24,36，A在整除關系在整除關系“ ”下構(gòu)成下構(gòu)成一個偏序集一個偏序集(A,)。6,12,24,36都是子集都是子集2,3的上界。的上界。6是子集是子集2,3的上確界。的上確界。2,3,6,12都是子集都是子集24,36的下界。的下界。12是子集是子集24,36的下確界。的下確界。集合與圖論精選ppt28A中有最大元素和最小元素嗎？中有最大元素和最小元素嗎？實實 例例例例9：令令A=2,3,6,12,24,36,A在整除關系在整除關系“ ”下構(gòu)成一下構(gòu)成一個偏序集個偏序集(A,)。 A中沒有最大元素也沒有最小元素。中沒有最大元素也沒有最小元素。 因為因為24與與36不可比，不可比，2與與3也不可比。也不可比。 但是但是A中沒有比中沒有比24和和36更大的元素，也沒有比更大的元素，也沒有比2與與3更小的元素。更小的元素。 稱稱24和和36都是極大元素都是極大元素,2與與3都是極小元素。都是極小元素。集合與圖論精選ppt29 定義定義8 設設(X,)是一個偏序集，是一個偏序集，A X，A中元素中元素s稱為稱為A的的極大元素極大元素，如果，如果A中