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

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

2、圖論3/30等價(jià)關(guān)系實(shí)例等價(jià)關(guān)系實(shí)例例例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上的等價(jià)關(guān)系上的等價(jià)關(guān)系。例例3：實(shí)數(shù)集上的實(shí)數(shù)集上的“”、“”、“”、“”、“”都不是都不是R上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。是等價(jià)關(guān)系。是等價(jià)關(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)系圖如下：等價(jià)關(guān)系的關(guān)系圖等價(jià)關(guān)系的關(guān)系圖集合與圖論5/30 定義定義2 設(shè)設(shè)R

3、是是X上的一個(gè)等價(jià)關(guān)系，上的一個(gè)等價(jià)關(guān)系，x X，X的子集的子集Ex=yy X且且xRy稱為稱為x關(guān)于關(guān)于R的的等價(jià)類等價(jià)類，或，或簡(jiǎn)記為簡(jiǎn)記為x的等價(jià)類。的等價(jià)類。x的等價(jià)類常記為的等價(jià)類常記為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)等價(jià)類的定義等價(jià)類的定義A= 1, 2, , 8 上模上模 3 等價(jià)關(guān)系的等價(jià)類：等價(jià)關(guān)系的等價(jià)類： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6集合與圖論6/30等價(jià)類的性質(zhì)等價(jià)類的性質(zhì)(3) x, y X, 如果如果(

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

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

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

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

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

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

11、關(guān)系構(gòu)成的二元組構(gòu)成的二元組(X,)稱為稱為全全序集序集。 偏序集與全序集的主要區(qū)別在于全序集中任兩個(gè)偏序集與全序集的主要區(qū)別在于全序集中任兩個(gè)元素均可比較元素均可比較“大小大小”，而在偏序集中任意兩個(gè)元素，而在偏序集中任意兩個(gè)元素不一定都能比較大小。不一定都能比較大小。實(shí)數(shù)間的常用的實(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,)是一個(gè)偏序集，稱是一個(gè)偏序集，稱y蓋住蓋住x，如果，如果xy且對(duì)每個(gè)且對(duì)每個(gè)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)系圖中每個(gè)頂點(diǎn)都有一個(gè)環(huán)，因此可以省略每個(gè)頂點(diǎn)的環(huán)。中每個(gè)頂點(diǎn)都有一個(gè)環(huán)，因此可以省略每個(gè)頂點(diǎn)的環(huán)。 其次由于偏序關(guān)系是傳遞的，那么只要在前驅(qū)與其次由于偏序關(guān)系是傳遞的，那么只要在前驅(qū)與后繼間聯(lián)線即可。后繼間聯(lián)線即可。 最后由于反對(duì)稱性，若最后由于反對(duì)稱性，若xy，x y，則點(diǎn)，則點(diǎn)y畫在畫在x的上方，這樣就不必用矢線了，按上述方法畫出的的上方，這樣就不必用矢線了，按上述方法畫出的圖稱為圖稱為(X,)的的哈斯圖哈斯圖。 集合與圖論21/30特點(diǎn)：特點(diǎn)： (1)每個(gè)結(jié)點(diǎn)沒(méi)有環(huán)每個(gè)結(jié)點(diǎn)沒(méi)有環(huán); (2)兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系通過(guò)結(jié)點(diǎn)兩個(gè)連通的結(jié)點(diǎn)之間的序關(guān)系

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

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

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

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

18、大元素與最小元素若有一定是唯一的。最大元素與最小元素若有一定是唯一的。因?yàn)樯舷陆绮灰欢ㄔ谧蛹幸驗(yàn)樯舷陆绮灰欢ㄔ谧蛹?集合與圖論27/30 定義定義7 設(shè)設(shè)(X,)是一個(gè)偏序集，是一個(gè)偏序集，B X。如果。如果B有上有上界且界且B的一切上界之集有最小元素，則這個(gè)最小上界的一切上界之集有最小元素，則這個(gè)最小上界稱為稱為B的的上確界上確界，記為，記為supB。上確界與下確界的定義上確界與下確界的定義 如果如果B有下界且有下界且B的一切下界之集有最大元素，的一切下界之集有最大元素，則這個(gè)最大下界稱為則這個(gè)最大下界稱為B的的下確界下確界，記為，記為infB。例例8：令令A(yù)=2,3,6,12,24,3

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