離散數(shù)學(xué)：r03關(guān)系c

1、1n關(guān)系的概念及運算關(guān)系的概念及運算n關(guān)系的性質(zhì)關(guān)系的性質(zhì)n關(guān)系的閉包運算關(guān)系的閉包運算n等價關(guān)系等價關(guān)系n序關(guān)系序關(guān)系 關(guān)系關(guān)系2 3.3 關(guān)系的閉包運算關(guān)系的閉包運算n設(shè)設(shè)R是是A上的二元關(guān)系，如果有另一個關(guān)系上的二元關(guān)系，如果有另一個關(guān)系R滿足：滿足：R 是是自反自反的的(對稱的，可傳遞的對稱的，可傳遞的)；R R ；對于任何對于任何自反自反的的(對稱的，可傳遞的對稱的，可傳遞的)關(guān)系關(guān)系R ，如果有如果有R R ，就有就有R R ，則稱關(guān)系則稱關(guān)系 R 為為R的的自反自反(對稱，傳遞對稱，傳遞)閉包閉包（reflexive closure, symmetric closure, tra

2、nsitive closure）。記為：）。記為：r(R), (s(R), t(R)。3關(guān)系的閉包運算關(guān)系的閉包運算定理定理1：設(shè)：設(shè)R是是A上的二元關(guān)系，如果上的二元關(guān)系，如果R是自反的，當(dāng)且僅當(dāng)是自反的，當(dāng)且僅當(dāng)r(R)=R；R是對稱的，當(dāng)且僅當(dāng)是對稱的，當(dāng)且僅當(dāng)s(R)=R；R是傳遞的，當(dāng)且僅當(dāng)是傳遞的，當(dāng)且僅當(dāng)t(R)=R；例例. 設(shè)設(shè)A=a,b，分別求以下，分別求以下A上的二元關(guān)系的自反、對稱和上的二元關(guān)系的自反、對稱和 傳遞閉包。傳遞閉包。 (1) R=, ； (2) S=AA ； (3) T= 。解：解：(1) r(R) = s(R) = t(R) = R ; (2) r(S)

3、= s(S) = t(S) = S ; (3) r(T) =, , s(T) = t(T) = T4關(guān)系的閉包運算關(guān)系的閉包運算定理定理2：n設(shè)設(shè)R是是A上的二元關(guān)系，則上的二元關(guān)系，則r(R)=RIA。證明：證明： 令令R =RIA ， (i) 對任意的對任意的xA，因為有因為有IA ，故故R ，所所以以R 在在A上是自反的。上是自反的。(ii) 又又R RIA ，即即R R 。(iii) 若有自反關(guān)系若有自反關(guān)系R 且且R R ，顯然有顯然有IA R ，于是于是 RIA R ，即即 R R 。 所以所以r(R)=RIA 。5關(guān)系的閉包運算關(guān)系的閉包運算n設(shè)設(shè)R是是A上的二元關(guān)系，則上的二元

4、關(guān)系，則s(R)=RR-1。證明：令證明：令R =RR-1， (i) 設(shè)設(shè)R ,則則R或或R-1 即即R-1或或R，故故RR-1 =R ， 所以所以R 是對稱的。是對稱的。 (ii) 因為因為R RR-1，即即R R 。(iii) 設(shè)設(shè)R 是對稱的，且是對稱的，且R R ,對任意的對任意的R ，則則 R或或R-1。當(dāng)當(dāng)R時，有時，有R ； 當(dāng)當(dāng)R-1時，有時，有R，則則R ， 又因為又因為R 對稱，所以對稱，所以R ，因此，因此，R R 。所以所以s(R)=RR-1。6關(guān)系的閉包運算關(guān)系的閉包運算231( )iit RRRRR 設(shè)設(shè)R是是A上的二元關(guān)系，則上的二元關(guān)系，則111( ),( )i

5、iststs tiiiiRRix yRy zRs tx yRy xRx zRRRRx zRRii RRR 證證明明：令令。任任取取那那么么必必存存在在正正整整數(shù)數(shù)，使使得得，則則有有所所以以即即是是傳傳遞遞的的。12111211121(),k,.,.,.,.,kkkkkiiiARRRRRx yRRRR RRAxxxx xRxxRxyRRRx xRxxRxyR 任任取取 上上的的傳傳遞遞關(guān)關(guān)系系且且現(xiàn)現(xiàn)證證明明。任任取取則則存存在在某某正正整整數(shù)數(shù) 使使得得而而由由復(fù)復(fù)合合運運算算的的定定義義可可知知： 中中存存在在元元素素使使得得。因因為為，所所以以有有，。又又因因1,( )iiRx yRRR

6、t RR 為為是是傳傳遞遞的的，所所以以，從從而而。綜綜上上所所述述有有。關(guān)系的閉包運算關(guān)系的閉包運算8關(guān)系的閉包運算關(guān)系的閉包運算傳遞閉包傳遞閉包對稱閉包對稱閉包自反閉包自反閉包UUI上的不等于關(guān)系上的不等于關(guān)系 UUU全域關(guān)系全域關(guān)系UUI上的小于等于關(guān)系上的小于等于關(guān)系 I上的小于關(guān)系上的小于關(guān)系例：設(shè)例：設(shè)A=a,b,c，RA2，且給定，且給定R=,， 求求r(R)，s(R)，t(R)。解：解：r(R)=, s(R)=, t(R)=, 9用關(guān)系圖求用關(guān)系圖求R的閉包：的閉包：設(shè)設(shè)G是集合是集合A上的二元關(guān)系上的二元關(guān)系R的有向圖，則的有向圖，則 r(R): G中每一結(jié)點加自回路；中每一

7、結(jié)點加自回路； s(R): 添加對稱?。惶砑訉ΨQ??； t(R): 若有從若有從a到到b的非零長度的路徑，則添加從的非零長度的路徑，則添加從a到到b的弧。的弧。關(guān)系的閉包運算關(guān)系的閉包運算關(guān)系的閉包運算關(guān)系的閉包運算 定理定理3：設(shè)：設(shè)R是有限集合是有限集合A上的二元關(guān)系且上的二元關(guān)系且|A|=n，那么有，那么有102( )nt RRRR 22122222( ),( )( ),inninnnnnkkt RRRRRRRRiRRRRRRiiRRRRRRx yAx yRRRknx yRkx yRknAxa 證證明明：已已知知現(xiàn)現(xiàn)證證明明顯顯然然有有。證證明明，為為此此，需需要要證證明明對對于于任任何何

8、，如如有有必必存存在在正正整整數(shù)數(shù)，使使得得。采采用用反反證證法法：假假設(shè)設(shè) 是是滿滿足足的的最最小小正正整整數(shù)數(shù)，且且，則則 中中存存在在元元素素序序列列0111121,kkkaaayx aa aayR ，使使得得關(guān)系的閉包運算關(guān)系的閉包運算11011112111()2|,(0),()()kkijiijjikjkijikjtAna aaaaaijkx aa aaaa aayRx aRayRx yRx yRtikjkjikkknRR 由由于于，則則中中必必有有相相同同者者，不不妨妨設(shè)設(shè)，于于是是，得得到到那那么么，即即，其其中中。這這與與 的的最最小小性性相相矛矛盾盾，于于是是。故故有有22(

9、 )nnnRRRRt RRRR 成成立立。綜綜上上所所述述，。12關(guān)系的閉包運算關(guān)系的閉包運算定理定理4：設(shè)：設(shè)R是是A上的二元關(guān)系，則有上的二元關(guān)系，則有 (a)如果如果R是自反的，那么是自反的，那么s(R)和和t(R)都是自反的；都是自反的； (b)如果如果R是對稱的，那么是對稱的，那么r(R)和和t(R)都是對稱的；都是對稱的； (c)如果如果R是傳遞的，那么是傳遞的，那么r(R)是傳遞的；是傳遞的；注意注意: : (c) 中中s(R)不一定傳遞，不一定傳遞， 如如 R=, s(R)=,13關(guān)系的閉包運算關(guān)系的閉包運算關(guān)系關(guān)系R的自反，對稱，傳遞閉包可以進一步復(fù)合，有如下定理：的自反，對

10、稱，傳遞閉包可以進一步復(fù)合，有如下定理：定理定理5：設(shè)：設(shè)A是集合，是集合，R是是A上的二元關(guān)系，則上的二元關(guān)系，則 (a) rs(R) = sr(R)， (b) rt(R) = tr(R)， (c) st(R) ts(R)。證明：證明：()As RI( )( )asr R1()()AARIRI11()()AARIRI1ARRI( )As RI( )rs R14(b) rt(R) = tr(R)因為因為IAR=RIA=R，對一切對一切nN，(IA)n=IA，可得可得11( )()ijAijtr RRI i()() ()()iAAAARIRIRIRI 1( )()()iAAitr Rt RIRI

11、1()iijAAjRIRI111( )( )ijiAAAijiRIRIt RIrt R15(c) st(R) ts(R) 如果如果R1 R2，則則s(R1) s(R2)，t(R1) t(R2)(作業(yè)作業(yè))， 又又R s(R)，則則t(R) ts(R)，st(R) sts(R)， 而而s(R)是對稱的，則是對稱的，則ts(R)是對稱的，則是對稱的，則sts(R)=ts(R)， 所以所以st(R) ts(R)。 st(R) ts(R) 例如，整數(shù)集合例如，整數(shù)集合I上的小于關(guān)系上的小于關(guān)系“”，st()=s()=ts()=t()=II=U(全域關(guān)系全域關(guān)系)16n關(guān)系的概念及運算關(guān)系的概念及運算n

12、關(guān)系的性質(zhì)關(guān)系的性質(zhì)n關(guān)系的閉包運算關(guān)系的閉包運算n等價關(guān)系等價關(guān)系n序關(guān)系序關(guān)系 關(guān)系關(guān)系17集合的覆蓋和劃分集合的覆蓋和劃分n若把一個集合若把一個集合A分成若干個叫做分塊的非空子集，使得分成若干個叫做分塊的非空子集，使得A中中每個元素至少屬于一個分塊，那么這些分塊的全體構(gòu)成的集每個元素至少屬于一個分塊，那么這些分塊的全體構(gòu)成的集合叫做合叫做A的一個的一個覆蓋覆蓋(cover)。如果。如果A中每個元素屬于且僅屬中每個元素屬于且僅屬于一個分塊，那么這些分塊的全體構(gòu)成的集合叫做于一個分塊，那么這些分塊的全體構(gòu)成的集合叫做A的一個的一個劃分劃分(partition)。n等價定義為：令等價定義為：令

13、A為給定非空集合，為給定非空集合，S=S1,S2,.,Sn，其中其中Si A，Si不為空集不為空集(i=1,2,.n)且且S1S2.Sn=A，集合集合S則稱為集合則稱為集合A的的覆蓋覆蓋。此外，如果。此外，如果Si和和Sj交為空集，這里交為空集，這里i不不等于等于j，則稱則稱S為為A的的劃分劃分。18集合的覆蓋和劃分集合的覆蓋和劃分n劃分的元素劃分的元素Si稱為劃分稱為劃分的的塊塊(block)，如果劃分是有限集合，如果劃分是有限集合，則不同塊的個數(shù)稱為劃分的則不同塊的個數(shù)稱為劃分的秩秩；若劃分是無限集合，則它的；若劃分是無限集合，則它的秩是無限的。劃分的秩就是劃分的大小。秩是無限的。劃分的秩

14、就是劃分的大小。n對于有限集合對于有限集合A，秩為，秩為1的劃分稱為的劃分稱為A的最小劃分，秩為的最小劃分，秩為|A|的的劃分稱為劃分稱為A的最大劃分。的最大劃分。19集合的覆蓋和劃分集合的覆蓋和劃分例如，例如，A=a,b,c，則則S=a,b,b,c,Q=a,a,b,a,c,D=a,b,c,G=a,b,c,E=a,b,c,F=a,a,c,覆蓋覆蓋劃分最小劃分最大劃分既不是覆蓋，也不是劃分若是劃分，則必是覆蓋；若是覆蓋，則不一定是劃分。20等價關(guān)系等價關(guān)系n設(shè)設(shè)R為定義在集合為定義在集合A上的一個關(guān)系，若上的一個關(guān)系，若R是是自反的自反的、對稱的對稱的和和傳遞的傳遞的，則，則R稱為稱為等價關(guān)系等

15、價關(guān)系(equivalence relation)。 如三角形集合上三角形的相似關(guān)系，某一班級中的同學(xué)關(guān)系。如三角形集合上三角形的相似關(guān)系，某一班級中的同學(xué)關(guān)系。例：設(shè)集合例：設(shè)集合A=1,2,3,4，A上關(guān)系上關(guān)系R=,。驗證驗證R是是A上等價關(guān)系。上等價關(guān)系。21等價關(guān)系等價關(guān)系例：設(shè)例：設(shè)I為整數(shù)集合，為整數(shù)集合，R=|xy(mod k)(模模k同余關(guān)系同余關(guān)系)，證明證明R是等價關(guān)系。是等價關(guān)系。證明：設(shè)任意證明：設(shè)任意a,b,cI(i)：因為因為a-a=k*0，所以所以R，即，即R是自反的；是自反的；(ii)：若若ab(mod k)，a-b=kt(tI)，則則b-a=-kt，所以所以

16、ba(mod k)，即，即R是對稱的；是對稱的； (iii)：若若ab(mod k)，bc(mod k)，則則a-b=kt， b-c=ks(tI，sI)， a-c=a-b+b-c=k(t+s)，所以所以ac(mod k)，即即R是傳遞的。是傳遞的。 因此因此R是是A上的等價關(guān)系。上的等價關(guān)系。22等價關(guān)系等價關(guān)系定理定理1：設(shè)：設(shè)R是是A上的二元關(guān)系，設(shè)上的二元關(guān)系，設(shè)R=tsr(R)是是R的自反對稱傳的自反對稱傳遞閉包，那么遞閉包，那么R是是A上的等價關(guān)系，稱為上的等價關(guān)系，稱為R誘導(dǎo)的等價關(guān)系誘導(dǎo)的等價關(guān)系；如果如果R”是任意等價關(guān)系，且是任意等價關(guān)系，且R R”，那么那么R R”。即即R是是包含包含R的最小等價關(guān)系。的最小等價關(guān)系。證明：證明：r(R)是自反的，所以是自反的，所以sr(R)是自