離散數(shù)學(xué)3-7復(fù)合關(guān)系和逆關(guān)系3-8關(guān)系的閉包

1、Discrete Mathematics山東科技大學(xué)山東科技大學(xué)信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院3-6 關(guān)系的性質(zhì)關(guān)系的性質(zhì) n兄弟關(guān)系n師生關(guān)系一、自反性和反自反性一、自反性和反自反性1、自反性自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個xX，有R，則稱R是自反的。 R在X上自反(x)(xXR)2、反自反性反自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個xX，有R，則稱R是反自反的。 R在X上反自反(x)(xXR)例如，在實數(shù)集合中，”是自反的，因為對于任意實數(shù)xx成立。 平面上三角形的全等關(guān)系是自反的。例：X=a，b，c，R1=， R2=， R3=，注意：注意：R不是自反的，未必

2、一定是反自反的。一個關(guān)系可不是自反的，未必一定是反自反的。一個關(guān)系可能既不是自反的，也不是反自反的。能既不是自反的，也不是反自反的。3、關(guān)系矩陣的特點、關(guān)系矩陣的特點n自反關(guān)系的關(guān)系矩陣的對角元素均為1；n反自反關(guān)系的關(guān)系矩陣的對角元素均為0。4、關(guān)系圖的特點、關(guān)系圖的特點n自反關(guān)系的關(guān)系圖，每個結(jié)點均有自回路；n反自反關(guān)系的關(guān)系圖，每個結(jié)點均沒有自回路。5、結(jié)論：、結(jié)論：R是X上的二元關(guān)系，則：(1)R是自反關(guān)系的充要條件是IXR。(2)R是反自反關(guān)系的充要條件是RIX=。二、對稱性和反對稱性二、對稱性和反對稱性1、對稱性對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個x，yX，每當R，就有

3、R，則稱R是對稱的。R在X上對稱(x)(y)(xXyXRR)2、反對稱性反對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個x，yX，每當R和R必有x=y，則稱R是反對稱的。 R在X上反對稱(x)(y)(xXyXRRx=y)例如，平面上三角形的相似關(guān)系是對稱的。例：R1=，R2=， R3=， R4=，注意：存在關(guān)系既不是對稱的，也不是反對稱的。也存在關(guān)系既是對稱的，也是反對稱的。 3、關(guān)系矩陣和關(guān)系圖的特點n對稱關(guān)系的關(guān)系矩陣是對稱矩陣，即對所有i，j，rijrji；n對稱關(guān)系的關(guān)系圖，任何兩個不同的結(jié)點之間，或者有雙向兩條弧，或者沒有弧。n反對稱關(guān)系的關(guān)系矩陣，如果在非對角元上rij1，則在其

4、對稱位置上rji0n反對稱關(guān)系的關(guān)系圖，任何兩個不同的結(jié)點之間至多有一條弧。 三、傳遞性三、傳遞性1、定義：設(shè)R是集合X上的二元關(guān)系，如果對于任意x，y，zX，每當R，R時就有R，則稱R是傳遞的。R在X上傳遞(x)(y)(z)(xXyXzXRRR)例：R1=,是傳遞的，R2=,也是傳遞的，它沒有違背定義。R3=,不是傳遞的。 2、定理：設(shè)R、S是A上的傳遞關(guān)系，則RS也是A上的傳遞關(guān)系。 注意：R、S均是傳遞的，但RS未必是傳遞的。例：R=，S=，則R、S均是傳遞的，但RS=，不是傳遞的。證明：設(shè) RS ， RS ，則 R， R且 S ， S 。 因為R、S是A上的傳遞關(guān)系，所以R ， S ，

5、從而 RS，即RS是A上的傳遞關(guān)系。綜合練習(xí)：綜合練習(xí)：集合A上的關(guān)系R，如果R是對稱且傳遞的，則它也是自反的。其理由是，從aRb，由對稱性得bRa，再由傳遞性得aRa。你說對嗎？為什么？你說對嗎？為什么？不對！再看自反性、對稱性、傳遞性的定義。自反性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個xX，有R，則稱R是自反的。對稱性：設(shè)R是集合X上的二元關(guān)系，如果對于每一個x，yX，每當R，就有R，則稱R是對稱的。傳遞性：設(shè)R是集合X上的二元關(guān)系，如果對于任意x,y,zX，每當R，R時就有R，則稱R是傳遞的。自反性是說自反性是說對于每一個對于每一個x X，有，有 R。對稱性是說對稱性是說每當每當 R

6、，就有，就有 R，沒有要求沒有要求對于每一個對于每一個x X，傳遞性是說傳遞性是說每當每當 R， R時就有時就有 R ，也沒有要求，也沒有要求對于每一個對于每一個x X。因此不能從一個關(guān)系是對稱且傳遞的推出它是是因此不能從一個關(guān)系是對稱且傳遞的推出它是是自反的。自反的。例如A=a，b，c， R=，是A上的一個二元關(guān)系，R是對稱且傳遞的，但R不是自反的，因為對于cA，沒有 R。112頁例題4 設(shè)某人有三個兒子，組成集合A=T,G,H，在A上的兄弟關(guān)系具有哪些性質(zhì)。例題5 集合I=1,2,3,4，I上的關(guān)系R=,討論R的性質(zhì)。小結(jié)小結(jié)n關(guān)系的定義及表示n關(guān)系的性質(zhì)n自反性n反自反性n對稱性n反對稱

7、性n傳遞性作業(yè)nP113: (2)(3)(6)上次課回顧關(guān)系：定義、表示關(guān)系的性質(zhì)：自反性反自反性對稱性反對稱性傳遞性3-7 復(fù)合關(guān)系和逆關(guān)系 本節(jié)講述關(guān)系的運算。一、復(fù)合關(guān)系一、復(fù)合關(guān)系引例：（1）a、b、c三人，a、b是兄妹關(guān)系，b、c是母子關(guān)系，則a、c是舅甥關(guān)系；（2）若設(shè)R是兄妹關(guān)系，S是母子關(guān)系，則R與S的復(fù)合T是舅甥關(guān)系。（3）如R是父子關(guān)系，R與R復(fù)合是祖孫關(guān)系。一、復(fù)合關(guān)系一、復(fù)合關(guān)系1、復(fù)合關(guān)系、復(fù)合關(guān)系(關(guān)系的復(fù)合運算關(guān)系的復(fù)合運算)定義定義3-7.1：設(shè)X、Y、Z是三個集合，R是X到 的關(guān)系，S是 到Z的關(guān)系，則RS稱為R和S的復(fù)合關(guān)系，表示為RS=xXzZ(y)(yY

8、RS) 從R和S求RS，稱為關(guān)系的合成運算。說明：R與S能進行復(fù)合的必要條件是R的值域所屬集合Y與S前域所屬集合Y是同一個集合。例：X=1，2，3，4，5，Y=3，4，5，Z=1，2，3，R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系：R=|x+y=6=，S=y-z=2=，則RS=，另可以用推導(dǎo)：x+y=6，y-z=2，消去y得x+z=4例：集合X=x，y，z，d，e，R=，S=，則RS=， SR=，RR=， SS=例題1：令R=，S=，試求RS，SR，R(SR)，(RS)R，RR，SS，RRR。解：RS=，SR=，R(SR)=(RS)R=RR=，SS=，RRR=，關(guān)系的復(fù)合運算不滿足交換律，滿足結(jié)合律。

9、例題2：設(shè)R1和R2是集合X=0，1，2，3上的關(guān)系，R1=|j=i+1或j=i/2，R2=|i=j+2試求R1R2，R2R1，R1R2R1，R1R1，R1R1R1。解：R1=,R2=,R1R2=,R2R1=,R1R2R1=,R1R1=,R1R1R1=,關(guān)系的關(guān)系的n次冪：次冪：設(shè)R是X上的二元關(guān)系，nN，則關(guān)系的n次冪R(n)定義為：(1)R(0)=x；(2)R(n+1)=R(n)R說明：如果R是X到Y(jié)的關(guān)系，且XY，則R2是無意義的，因為RR是無法復(fù)合的。例：設(shè)X=1，2，3，4，5，X上關(guān)系R為R=,，則：R(0)=x=,，R(1)=RR(2)=,R(3)=,R(4)=,R(5)=,2、

10、復(fù)合關(guān)系矩陣：、復(fù)合關(guān)系矩陣：設(shè)集合X=x1，x2，xm，Y=y1，y2，yn，Z=z1，zP，R是X到Y(jié)的關(guān)系，其關(guān)系矩陣MR=(uij)mn，S是Y到Z的關(guān)系，其關(guān)系矩陣MS=(vjk)np，復(fù)合關(guān)系RS是X到Z的關(guān)系，其關(guān)系矩陣MRS=(wik)mp和和運算運算 邏輯加邏輯加：000 011101 111 邏輯乘邏輯乘：000 010100 1112、復(fù)合關(guān)系矩陣：、復(fù)合關(guān)系矩陣：設(shè)集合X=x1，x2，xm，Y=y1，y2，yn，Z=z1，zP，R是X到Y(jié)的關(guān)系，其關(guān)系矩陣MR=(uij)mn，S是Y到Z的關(guān)系，其關(guān)系矩陣MS=(vjk)np，復(fù)合關(guān)系RS是X到Z的關(guān)系，其關(guān)系矩陣MRS

11、=(wik)mp，則wik=(uijvjk)。j=1nMR的第的第i行和行和MS的第的第k列對應(yīng)的元素，先做邏列對應(yīng)的元素，先做邏輯乘輯乘 ，再做邏輯加，再做邏輯加例題3：給定集合A=1，2，3，4，5，在A上定義兩個關(guān)系。R=，S=，。求RS和SR的矩陣。解： 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1M RS= 0 0 0 1 0 1 0 0 0 0 = 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

12、 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0M SR= 1 0 0 0 0 0 0 0 1 0 = 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0二、逆關(guān)系二、逆關(guān)系1、逆關(guān)系、逆關(guān)系定義定義3-7.2：設(shè)R是集合X到Y(jié)的二元關(guān)系，如將R中每一序偶中的元素順序互換，所得到的集合稱為R的逆關(guān)系，記作Rc=|R。說明：Rc的關(guān)系矩陣是R的關(guān)系矩陣的轉(zhuǎn)置，Rc的關(guān)系圖是將R的關(guān)系圖中的弧改變方向。例：設(shè)某合X=x，y，z， X上的關(guān)系R=，則Rc=，例題4：

13、給定集合X=a，b，c，R是X上的二元關(guān)系。R的關(guān)系矩陣 1 0 1M R= 1 1 0 1 1 1求Rc和RRc的關(guān)系矩陣。解： 1 1 1M Rc= 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1M RRc = 1 1 0 0 1 1 = 1 1 1 1 1 1 1 0 1 1 1 12、定理、定理3-7.1：設(shè)R，R1和R2均是A到B的二元關(guān)系，則(1)(Rc)c=R(2)(R1R2)c=R1cR2c(3)(R1R2)c=R1cR2c(4)(AB)c=BA(5)(R)c= Rc R= AB - R(6)(R1-R2)c=R1c-R2c證明：(2)(R1R2)c R1R2 R1

14、R2 R1c R2c R1cR2c3、定理、定理3-7.2：設(shè)R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，則(RS)c=ScRc。證明：(RS)c RS (y)(yYRS) (y)(yYRcSc ) ScRc例：X=x，y，z，Y=1，2，3，4，5，R是X上關(guān)系，S是X到Y(jié)的關(guān)系。R=，S=，則RS=， ，Rc=，Sc=，ScRc=， ，可驗證：ScRc=(RS)c4、定理、定理3-7.3：設(shè)R是X上的二元關(guān)系，則(1)R是對稱的，當且僅當R=Rc(2)R是反對稱的，當且僅當RRcIx證明： (1)因為R是對稱的，故RRRc，所以R=Rc。反之，若R=Rc，因為RRcR，所以R是對稱的。 (2)設(shè)R

15、是反對稱的， RRc R Rc R R，因為 R是反對稱的， 所以x=y，故RRcIx。 反之，若RRcIx ， RRc有 Ix ，即x=y。又 RRc R Rc R R，但x=y， 故R是反對稱的。即當R和R時，必有x=y。作業(yè) P119: (2) a,b (4)b,d3-8 關(guān)系的閉包本節(jié)講述關(guān)系的閉包運算。本節(jié)講述關(guān)系的閉包運算。要求會求關(guān)系的自反要求會求關(guān)系的自反(對稱、傳遞對稱、傳遞)閉包。閉包。 現(xiàn)在來討論另一種重要關(guān)系現(xiàn)在來討論另一種重要關(guān)系閉包閉包. 所謂閉包是指，對于給定的關(guān)系所謂閉包是指，對于給定的關(guān)系R和一種性質(zhì)和一種性質(zhì)P, 則則把包含把包含R并且滿足性質(zhì)并且滿足性質(zhì)P

16、的最小關(guān)系稱為的最小關(guān)系稱為R對于對于P的的閉包閉包, 記為記為P(R). 若若P是自反的是自反的, 則稱則稱R是自反閉包是自反閉包, 記為記為r(R), 若若P是對稱的，則稱是對稱的，則稱R是對稱閉包是對稱閉包, 記為記為s(R); 若若P是傳遞的是傳遞的, 則稱則稱R是傳遞閉包是傳遞閉包,記為記為t(R). 一、關(guān)系的閉包定義一、關(guān)系的閉包定義定義定義3-8.1：設(shè)：設(shè)R是是X上的二元關(guān)系，如果另外有一上的二元關(guān)系，如果另外有一個關(guān)系個關(guān)系R滿足：滿足：(1)R是自反的是自反的(對稱的，傳遞的對稱的，傳遞的)；(2)R R；(3)對于任何自反的對于任何自反的(對稱的，傳遞的對稱的，傳遞的)

17、關(guān)系關(guān)系R，如果，如果有有R R，就有，就有R R。則稱關(guān)系。則稱關(guān)系R為為R的自反的自反(對稱，對稱，傳遞傳遞)閉包。記作閉包。記作r(R)，(s(R)，t(R)例：設(shè)集合例：設(shè)集合X=x，y，z，X上的關(guān)系上的關(guān)系R=，則，則:自反閉包自反閉包r(R)=，對稱閉包對稱閉包s(R)=，傳遞閉包傳遞閉包t(R)=， 由閉包的定義可以知道，構(gòu)造關(guān)系由閉包的定義可以知道，構(gòu)造關(guān)系R的閉包方的閉包方法就是向法就是向R中加入必要的有序?qū)?，使其具有所希望中加入必要的有序?qū)Γ蛊渚哂兴Ｍ男再|(zhì)。下面定理體現(xiàn)了這一點。的性質(zhì)。下面定理體現(xiàn)了這一點。二、關(guān)系的性質(zhì)與閉包的關(guān)系二、關(guān)系的性質(zhì)與閉包的關(guān)系1、定

18、理、定理3-8.1：設(shè)：設(shè)R是是X上的二元關(guān)系，則上的二元關(guān)系，則(1)R是自反的，當且僅當是自反的，當且僅當r(R)=R(2)R是對稱的，當且僅當是對稱的，當且僅當s(R)=R(3)R是傳遞的，當且僅當是傳遞的，當且僅當t(R)=R證明證明 只證明必要性必要性: 令R為自反. 由于RR, 并取右方R為S, 以及任何包含R的自反關(guān)系 T, 有S T, 可見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是自反的，當且僅當是自反

19、的，當且僅當r(R)=R(2)R是對稱的，當且僅當是對稱的，當且僅當s(R)=R(3)R是傳遞的，當且僅當是傳遞的，當且僅當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”，滿足定義第三條。得，滿足定義第三條。

20、得r(R)=Rx。 對關(guān)系矩陣而言，對關(guān)系矩陣而言，r(R)的關(guān)系矩陣只要將的關(guān)系矩陣只要將MR的的對角元置對角元置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是對是對稱的，滿足定義的第二條。稱的，滿足定義的第二條。如果如果R R”，且，且R”是對稱的，是對稱的， R Rc，則，則 R或或 Rc，如，如 R，由，由R R”，則，則 R”，如，如 Rc則則 R則則 R”，又因又因R”對稱，所以對稱，所以 R”，所

21、以，所以R Rc R”，滿足，滿足定義第三條。得定義第三條。得s(R)=R Rc。4、定理、定理3-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時時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(

22、R). 于是于是, Ri t(R).U1iU1iU1i次證次證t(R) Ri, 由于包含由于包含 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=，

23、求，求r(R)，s(R)，t(R)。解：解：r(R)=，s(R)=，為了求為了求t(R)，先寫出，先寫出 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ù)計算求解，會得出繼續(xù)計算求解，會得出R4=R=R3n+1, R5=R2=R3n+2 , R6=R3=R3n+3所以所以t(R)= R R2 R35、定理、定理3-8.5：設(shè)：設(shè)X含有含有n個元素的集合，個元素的集合，