離散數(shù)學(xué) 3-9 集合的劃分和覆蓋3-10 等價(jià)關(guān)系與等價(jià)類

1、Discrete Mathematics山東科技大學(xué)山東科技大學(xué)信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院3-8 3-8 關(guān)系的閉包關(guān)系的閉包關(guān)系的自反閉包關(guān)系的自反閉包關(guān)系的對(duì)稱閉包關(guān)系的對(duì)稱閉包關(guān)系的傳遞閉包關(guān)系的傳遞閉包一、關(guān)系的閉包定義一、關(guān)系的閉包定義定義定義3-8.1：設(shè)：設(shè)R是是X上的二元關(guān)系，如果另外有一上的二元關(guān)系，如果另外有一個(gè)關(guān)系個(gè)關(guān)系R滿足：滿足：(1)R是自反的是自反的(對(duì)稱的對(duì)稱的，傳遞的傳遞的)；(2)R R；(3)對(duì)于任何自反的對(duì)于任何自反的(對(duì)稱的對(duì)稱的，傳遞的傳遞的)關(guān)系關(guān)系R，如果，如果有有R R，就有，就有R R。則稱關(guān)系。則稱關(guān)系R為為R的自反的自反(對(duì)稱，

2、對(duì)稱，傳遞傳遞)閉包。記作閉包。記作r(R)，(s(R)，t(R)例：設(shè)集合例：設(shè)集合X=x，y，z，X上的關(guān)系上的關(guān)系R=，則，則:自反閉包自反閉包r(R)=，對(duì)稱閉包對(duì)稱閉包s(R)=，傳遞閉包傳遞閉包t(R)=， 由閉包的定義可以知道，構(gòu)造關(guān)系由閉包的定義可以知道，構(gòu)造關(guān)系R的閉包方的閉包方法就是向法就是向R中加入必要的有序?qū)Γ蛊渚哂兴Ｍ屑尤氡匾挠行驅(qū)?，使其具有所希望的性質(zhì)。下面定理體現(xiàn)了這一點(diǎn)。的性質(zhì)。下面定理體現(xiàn)了這一點(diǎn)。二、關(guān)系的性質(zhì)與閉包的關(guān)系二、關(guān)系的性質(zhì)與閉包的關(guān)系1、定理、定理3-8.1：設(shè)：設(shè)R是是X上的二元關(guān)系，則上的二元關(guān)系，則(1)R是自反的，當(dāng)且僅當(dāng)是自反

3、的，當(dāng)且僅當(dāng)r(R)=R(2)R是對(duì)稱的，當(dāng)且僅當(dāng)是對(duì)稱的，當(dāng)且僅當(dāng)s(R)=R(3)R是傳遞的，當(dāng)且僅當(dāng)是傳遞的，當(dāng)且僅當(dāng)t(R)=R證明證明 只證明必要性必要性: 令R為自反. 由于RR, 并取右方R為S, 以及任何包含R的自反關(guān)系 T, 有S T, 可見(jiàn)R滿足自反閉包定義, 即r(R) = R. 充分性充分性: 由自反閉包定義R是自反的.二、關(guān)系的性質(zhì)與閉包的關(guān)系二、關(guān)系的性質(zhì)與閉包的關(guān)系1、定理、定理3-8.1：設(shè)：設(shè)R是是X上的二元關(guān)系，則上的二元關(guān)系，則(1)R是自反的，當(dāng)且僅當(dāng)是自反的，當(dāng)且僅當(dāng)r(R)=R(2)R是對(duì)稱的，當(dāng)且僅當(dāng)是對(duì)稱的，當(dāng)且僅當(dāng)s(R)=R(3)R是傳遞的，

4、當(dāng)且僅當(dāng)是傳遞的，當(dāng)且僅當(dāng)t(R)=R2、定理、定理3-8.2：設(shè)：設(shè)R是集合是集合X上的二元關(guān)系，則上的二元關(guān)系，則r(R)=Rx證明：證明：R Rx，Rx是自反的，定義的前兩條滿足是自反的，定義的前兩條滿足了。設(shè)了。設(shè)R”滿足滿足R R”，R”是自反的，是自反的， Rx，則，則 R或或x。如果。如果 R則由則由R R”， R”。如果。如果x則必有則必有x=y，即，即x，由，由R”的自反性，的自反性，則則 R”，總之均有，總之均有 R”，所以，所以RX R”，滿足定義第三條。得，滿足定義第三條。得r(R)=Rx。 對(duì)關(guān)系矩陣而言，對(duì)關(guān)系矩陣而言，r(R)的關(guān)系矩陣只要將的關(guān)系矩陣只要將MR的

5、的對(duì)角元置對(duì)角元置1即可。即可。3、定理、定理3-8.3：設(shè)：設(shè)R是集合是集合X上的二元關(guān)系，則上的二元關(guān)系，則s(R)=R Rc。證明：證明：R R Rc滿足定義第一條。滿足定義第一條。 R Rc R Rc Rc R R Rc，所以，所以R Rc是對(duì)是對(duì)稱的，滿足定義的第二條。稱的，滿足定義的第二條。如果如果R R”，且，且R”是對(duì)稱的，是對(duì)稱的， R Rc，則，則 R或或 Rc，如，如 R，由，由R R”，則，則 R”，如，如 Rc則則 R則則 R”，又因又因R”對(duì)稱，所以對(duì)稱，所以 R”，所以，所以R Rc R”，滿足，滿足定義第三條。得定義第三條。得s(R)=R Rc。4、定理、定理3

6、-8.4：設(shè)：設(shè)R是集合是集合X上的二元關(guān)系，則上的二元關(guān)系，則 t(R)= R(i)=R R(2) R(3) 證明證明首先證明首先證明 R t(R). 用歸納法證明如下用歸納法證明如下: 基礎(chǔ)步基礎(chǔ)步: 根據(jù)傳遞閉包定義根據(jù)傳遞閉包定義, R t(R); 歸納步歸納步: 假設(shè)假設(shè)n1時(shí)時(shí)Rn t(R), 欲欲證證Rn+1 t(R)令令 x,y X, 則則: x Rn+1yx Rn * Ry ( z)(xRnzzRy) xRnzzRy xt(R)zzt(R)y xt(R)y 因此因此, Rn t(R). 于是于是, Ri t(R).U1iU1iU1i次證次證t(R) Ri, 由于包含由于包含

7、R的傳遞關(guān)系都包含的傳遞關(guān)系都包含t(R)，且且R Ri, 因此只需證明因此只需證明 Ri是傳遞即可是傳遞即可. 令令x, y, z X, 則則 x( Ri)yy( Ri)z ( j)(xRjy) ( k)(yRkz) xRjyyRkz xRjy * yRkz xRj+kz x( Ri)z因此因此, Ri是傳遞的是傳遞的. 綜上可知綜上可知, t(R) = Ri.U1iU1iU1iU1iU1iU1iU1iU1i例題例題1：設(shè)：設(shè)A=a，b，c，R是是A上的二元關(guān)系，且給定上的二元關(guān)系，且給定R=，求，求r(R)，s(R)，t(R)。解：解：r(R)=，s(R)=，為了求為了求t(R)，先寫出，

8、先寫出 0 1 0MR= 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1MR2= 0 0 1 0 0 1 = 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0MR3= 1 0 0 0 0 1 = 0 0 1 0 1 0 1 0 0 1 0 0繼續(xù)計(jì)算求解，會(huì)得出繼續(xù)計(jì)算求解，會(huì)得出R4=R=R3n+1, R5=R2=R3n+2 , R6=R3=R3n+3所以所以t(R)= R R2 R35、定理、定理3-8.5：設(shè)：設(shè)X含有含有n個(gè)元素的集合，個(gè)元素的集合，R是是X上的上的二元關(guān)系，則存在一個(gè)正整數(shù)二元關(guān)系，則存在一個(gè)正整數(shù)kn，使得，使得t(R)

9、=R R(2) R(3) R(K)例：例：A=a，b，c，d，R=，求，求t(R)。解：解：R(2)=，R(3)=R(4)=所以所以t(R)=R R(2) R(3) R(4) =， ，6、Warshall算法算法設(shè)設(shè)R是個(gè)元素集合是個(gè)元素集合X上的二元關(guān)系，上的二元關(guān)系，(1)A是是R的關(guān)系矩陣；的關(guān)系矩陣；(2)置置i=1；(3)對(duì)所有，如果對(duì)所有，如果aji=1，則對(duì)，則對(duì)k=1，2，najk=ajk+aik（第（第i行與第行與第j行邏輯相加，記于第行邏輯相加，記于第j行）行）(4)i=i+1；(5)如果如果in，則轉(zhuǎn)到步驟，則轉(zhuǎn)到步驟(3)，否則停止。，否則停止。舉例 P124 例3 W

10、arshall算法的C語(yǔ)言實(shí)現(xiàn)7、求閉包的關(guān)系圖作法：、求閉包的關(guān)系圖作法：(1)r(R)在在R的基礎(chǔ)上添加自回路，使得每點(diǎn)均有自的基礎(chǔ)上添加自回路，使得每點(diǎn)均有自回路?；芈贰?2)s(R)在在R中兩結(jié)點(diǎn)間只有一條弧時(shí)，再添一條反中兩結(jié)點(diǎn)間只有一條弧時(shí)，再添一條反向弧，使兩結(jié)點(diǎn)間或是向弧，使兩結(jié)點(diǎn)間或是0條弧，或是兩條弧，原來(lái)?xiàng)l弧，或是兩條弧，原來(lái)兩點(diǎn)間沒(méi)有弧不能添加。兩點(diǎn)間沒(méi)有弧不能添加。(3)t(R)在在R中如結(jié)點(diǎn)中如結(jié)點(diǎn)x通過(guò)有向路能通到通過(guò)有向路能通到z，則添加，則添加一條從一條從x到到z的有向弧，其中包括如的有向弧，其中包括如x能達(dá)到自身，能達(dá)到自身，則必須添從則必須添從x到到x的自

11、回路。的自回路。8、定理、定理3-8.6：若：若R A A，則，則rs(R)=sr(R)rt(R)=tr(R)st(R) ts(R)作業(yè) P127: (1),(2),(7):a,c3-9 集合的劃分和覆蓋 在集合的研究中，除了常常把兩個(gè)集合在集合的研究中，除了常常把兩個(gè)集合相互比較之外，有時(shí)也要把一個(gè)集合分成若相互比較之外，有時(shí)也要把一個(gè)集合分成若干子集加以討論。干子集加以討論。一、集合的劃分和覆蓋一、集合的劃分和覆蓋定義定義3-9.1：若把一個(gè)集合：若把一個(gè)集合A分成若干個(gè)叫做分塊的分成若干個(gè)叫做分塊的非空集合非空集合，使得，使得A中中每個(gè)元素至少屬于一個(gè)分塊每個(gè)元素至少屬于一個(gè)分塊，那么這

12、些分塊的全體構(gòu)成的集合叫做那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)覆蓋。的一個(gè)覆蓋。如果如果A中中每個(gè)元素屬于且僅屬于一個(gè)分塊每個(gè)元素屬于且僅屬于一個(gè)分塊，那么這，那么這些分塊的全體構(gòu)成的集合叫做些分塊的全體構(gòu)成的集合叫做A的一個(gè)劃分的一個(gè)劃分(或分劃或分劃)。一、集合的劃分和覆蓋一、集合的劃分和覆蓋定義定義3-9.1：令：令A(yù)為非空集合，為非空集合，S=S1，S2，Sm，其中其中Si，Si A， Si=A，集合，集合S稱作集合稱作集合A的的覆蓋覆蓋。如果除以上條件外，另有如果除以上條件外，另有SiSj=(i j)，則稱，則稱S是是A的的劃分劃分(或或分劃分劃)。1mi例如，例如，A=a，b，

13、c，考慮下列子集：，考慮下列子集：S=a，b，b，c，Q=a，a，b，a，cD=a，b，c，G=a，b，cE=a，b，c，F(xiàn)=a，a，c則：則：D、E、G、S、Q是是A的覆蓋的覆蓋D、E、G是是A的劃分的劃分F既不是劃分也不是覆蓋。既不是劃分也不是覆蓋。 若是劃分則必是覆蓋，其逆不成立。若是劃分則必是覆蓋，其逆不成立。任何一個(gè)集合的最小劃分，就是由這個(gè)集合的全部任何一個(gè)集合的最小劃分，就是由這個(gè)集合的全部元素組成的一個(gè)分塊的集合。如元素組成的一個(gè)分塊的集合。如G是是A的最小劃分。的最小劃分。任何一個(gè)集合的最大劃分，就是由每個(gè)元素構(gòu)成一任何一個(gè)集合的最大劃分，就是由每個(gè)元素構(gòu)成一個(gè)單元素分塊的集

14、合。如個(gè)單元素分塊的集合。如E是是A的最大劃分。的最大劃分。二、交叉劃分二、交叉劃分定義定義3-9.2：若：若A1，A2，Ar與與B1，B2，Bs是同一集合是同一集合A的兩種劃分，則其中所有的兩種劃分，則其中所有Ai Bj組成組成的集合，稱為原來(lái)兩種劃分的交叉劃分。的集合，稱為原來(lái)兩種劃分的交叉劃分。例如，所有生物的集合例如，所有生物的集合X，可分割成，可分割成P，A，其中，其中P表示所有植物的集合，表示所有植物的集合，A表示所有動(dòng)物的集合，又表示所有動(dòng)物的集合，又X也可分割成也可分割成E，F(xiàn)，其中，其中E表示史前生物，表示史前生物，F(xiàn)表示史表示史后生物，則其交叉劃分為后生物，則其交叉劃分為Q

15、=P E，P F，A E，A F。定理定理3-9.1：設(shè)：設(shè)A1，A2，Ar與與B1，B2，Bs是同一集合是同一集合X的兩種劃分，則其的兩種劃分，則其交叉劃分亦是原集交叉劃分亦是原集合的一種劃分。合的一種劃分。加細(xì)加細(xì)定義定義3-9.3：給定：給定X的任意兩個(gè)劃分的任意兩個(gè)劃分A1，A2，Ar與與B1，B2，Bs，若對(duì)每一個(gè)，若對(duì)每一個(gè)Aj均有均有Bk使使Aj Bk，則，則A1，A2，Ar稱為稱為B1，B2，Bs的加細(xì)的加細(xì)。定理定理3-9.2：任何兩種劃分的交叉劃分，都是原來(lái)各劃分的：任何兩種劃分的交叉劃分，都是原來(lái)各劃分的一種加細(xì)。一種加細(xì)。證明：設(shè)證明：設(shè)A1，A2，Ar與與B1，B2，

16、Bs的交叉劃分為的交叉劃分為T，對(duì)，對(duì)T中任意元素中任意元素Ai Bj必有必有Ai Bj Ai，Ai Bj Bj，故，故T必是必是原劃分的加細(xì)。原劃分的加細(xì)。作業(yè) P130：（4）、（5）3-10 等價(jià)關(guān)系與等價(jià)類一、等價(jià)關(guān)系一、等價(jià)關(guān)系定義定義3-10.1：設(shè)：設(shè)R為集合為集合A上的二元關(guān)系，若上的二元關(guān)系，若R是自是自反的、對(duì)稱的和傳遞的，則稱反的、對(duì)稱的和傳遞的，則稱R為等價(jià)關(guān)系。為等價(jià)關(guān)系。aRb，稱為，稱為a等價(jià)于等價(jià)于b。由于由于R是對(duì)稱的，是對(duì)稱的，a等價(jià)等價(jià)b即即b等價(jià)等價(jià)a，反之亦然，反之亦然，a與與b彼此等價(jià)。彼此等價(jià)。例如，平面上三角形集合中，三角形的相似關(guān)系是例如，平面

17、上三角形集合中，三角形的相似關(guān)系是等價(jià)關(guān)系。等價(jià)關(guān)系。鑒于空集合中的二元關(guān)系是等價(jià)關(guān)系，是一種平凡鑒于空集合中的二元關(guān)系是等價(jià)關(guān)系，是一種平凡情形，因此，一般討論非空集合上的等價(jià)關(guān)系。情形，因此，一般討論非空集合上的等價(jià)關(guān)系。例題例題1：設(shè)集合：設(shè)集合T=1，2，3，4，R=，。驗(yàn)證。驗(yàn)證R是是T上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。解：畫出解：畫出R的關(guān)系圖的關(guān)系圖每個(gè)結(jié)點(diǎn)都有自回路，說(shuō)明每個(gè)結(jié)點(diǎn)都有自回路，說(shuō)明R是自反的。任意兩是自反的。任意兩個(gè)結(jié)點(diǎn)間或沒(méi)有弧線連接，或有成對(duì)弧出現(xiàn)，故個(gè)結(jié)點(diǎn)間或沒(méi)有弧線連接，或有成對(duì)弧出現(xiàn)，故R是對(duì)稱的。從序偶表示式中，可以看出，是對(duì)稱的。從序偶表示式中，可以看出，

18、R是傳是傳遞的。遞的。故故R是是T上的等價(jià)關(guān)系。上的等價(jià)關(guān)系。模模m等價(jià)是等價(jià)是I（整數(shù)集合）或其子集上的等（整數(shù)集合）或其子集上的等價(jià)關(guān)系，并且是一類重要的等價(jià)關(guān)系。價(jià)關(guān)系，并且是一類重要的等價(jià)關(guān)系。定義：設(shè)定義：設(shè)m為一正整數(shù)，而為一正整數(shù)，而a，b I。若存。若存在在k，使，使a-b=km，則稱，則稱a與與b是模是模m等價(jià)，等價(jià)，記為記為a b(mod m)。如如1與與4是模是模3等價(jià)，等價(jià)， 1與與7是模是模3等價(jià)，等價(jià)， 4與與7是模是模3等價(jià)，等價(jià)，4與與1是模是模3等價(jià)，等價(jià)， 7與與1是模是模3等價(jià)，等價(jià)， 1與與1是模是模3等價(jià)，等價(jià)，例題例題2：設(shè)：設(shè)I是整數(shù)集，是整數(shù)集，

19、R=(a，b)|a b(modk)，a，b I，證明，證明R是等價(jià)關(guān)系。是等價(jià)關(guān)系。證明：設(shè)任意證明：設(shè)任意a，b，c I(1)因?yàn)橐驗(yàn)閍-a=k 0，所以，所以 R，R是是自反的。自反的。(2)若若 R，a b(modk)，a-b=kt(t為整數(shù)為整數(shù))，則則b-a=-kt，所以，所以b a(modk)， R，R是對(duì)是對(duì)稱的。稱的。(3)若若 R， R，a b(modk)，b c(modk)，則，則a-b=kt，b-c=ks(t，s為整數(shù)為整數(shù))，a-c=k(t+s)，所以，所以a c(modk)， R，R是是傳遞的。傳遞的。因此因此R是等價(jià)關(guān)系。是等價(jià)關(guān)系。二、等價(jià)類二、等價(jià)類1、定義、定

20、義3-10.2：設(shè)：設(shè)R為集合為集合A上的等價(jià)關(guān)系，對(duì)任何上的等價(jià)關(guān)系，對(duì)任何a A，集合，集合aR=x|x A，aRx稱為元素稱為元素a形成的形成的R等價(jià)類。等價(jià)類。顯然，等價(jià)類顯然，等價(jià)類aR非空，因?yàn)榉强眨驗(yàn)閍 aR。例題例題3：設(shè)：設(shè)I是整數(shù)集，是整數(shù)集，R是模是模3關(guān)系，關(guān)系，即即R=(x，y)|x y(mod3)，x，y I，確定由，確定由I的元素的元素所產(chǎn)生的等價(jià)類。所產(chǎn)生的等價(jià)類。解：由解：由I的元素所產(chǎn)生的等價(jià)類是的元素所產(chǎn)生的等價(jià)類是0R=，-6，-3，0，3，6，1R=，-5，-2，1，4，7，2R=，-4，-1，2，5，8，例：例：A=52張撲克牌張撲克牌，R1=a與

21、與b同花，同花，a，b是撲克是撲克，R2=a與與b同點(diǎn)，同點(diǎn)，a，b是撲克是撲克，即即R1是同花關(guān)系，是同花關(guān)系， R2是同點(diǎn)關(guān)系，是同點(diǎn)關(guān)系，R1和和R2都是等價(jià)關(guān)系。都是等價(jià)關(guān)系。R1把把A分為四類同花類，分為四類同花類，R2把把A分為分為13類同點(diǎn)類。類同點(diǎn)類。例：例：A=0，1，2，3，4，5，R=，R把把A分成了三個(gè)等價(jià)類：分成了三個(gè)等價(jià)類：0，1，2，3，4，5。2、定理、定理3-10.1：設(shè)給定集合：設(shè)給定集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系R，對(duì)，對(duì)于于a，b A有有aRb iff aR=bR。證明：假定證明：假定aR=bR，因?yàn)?，因?yàn)閍 aR，故，故a bR，即，即aRb。反之，若反之，若aRb，則，則bRa， 設(shè)設(shè)c aRaRcbRcc bR即即aR bR同理，若同理，若aRb，設(shè)，設(shè)c bRbRcaRcc aR即即bR aR由此證得若由此證得若aRb，則，則aR=bR。三、商集三、商集1、定義、定義3-10.3：集合：集合A上的等價(jià)關(guān)系上的等價(jià)關(guān)系R，其等價(jià)類，其等價(jià)類的集合的集合aR|a A稱為稱為A關(guān)于關(guān)于R的商集，記作的商集，記作A/R。如例題如例題1中商集中商集T/R=1R，2R，例題例題3中商集中商集I/R=0R，1R，2R 等價(jià)關(guān)系等價(jià)關(guān)系R把把A的元素分為若