1、第4章 二元關系第4章 二元關系4.1 4.1 二元關系及其表示二元關系及其表示4.2 4.2 關系的運算關系的運算4.3 4.3 關系的性質關系的性質4.4 4.4 關系的閉包運算關系的閉包運算4.5 4.5 等價關系等價關系4.6 4.6 相容關系相容關系4.7 4.7 序關系序關系第4章 二元關系第4章 二元關系 4.1二元關系及其表示 4.1.1二元關系的概念 定義4.1.1設A和B是任意集合，如果RAB，則稱R是A到B的二元關系。如果R是A到A的二元關系，則稱R是A上的二元關系。 設A=1,2,3，B=a,b，R=1,a,2,a,3,b。R是A到B的二元關系。S=3,1,2,2,2,

2、1,1,1。S是A上的二元關系。 定義4.1.2設A和B是任意集合，RAB，若x,yR，則稱x與y有R關系。記為xRy。若x,yR，則稱x與y沒有R關系。記為x y。R 第4章 二元關系 如果R是A到B的二元關系，根據定義4.1.2，x,yR與 xRy，x,yR與x y的意義相同。 定義4.1.3設A和B是任意集合，空集叫做A到B的空關系，仍然記為。A，B的笛卡爾積AB叫做A到B的全域關系，記為E。集合a,a|aA叫做A上的恒等關系。記為IA。 【例4.1】設A=a,b，B=1,2，求A上的恒等關系IA和A到B的全域關系AB。 解：A上的恒等關系IA=a,a,b,b，A到B的全域關系E =AB

3、=a,1,a,2,b,1,b,2 定理4.1.1設A是具有n個元素的有限集，則A上的二元關系有2n2種。 證明：設A為具有n個元素的有限集，即|A|=n，由排列組合原理知|AA|=n2。根據定理3.1.2有|P (AA) |=2|AA|=2 ，即AA的子集有2 個。所以具有n個元素的有限集A上有2 種二元關系。2n2n2nR 第4章 二元關系 4.1.2二元關系的表示 1.用列舉法表示二元關系 例4.1中的A到B的全域關系 E=AB=a,1,a,2,b,1,b,2 A上的恒等關系 IA=a,a,b,b都是用列舉法表示的。 2.用描述法表示二元關系 設R是實數集，LR= x,y | xRyRxy

4、， LR是實數集R上的二元關系。第4章 二元關系 3.用矩陣表示二元關系 如果A，B是有限集， A=a1,a2,am， B=b1,b2,bn， R是A到B的二元關系，R的關系矩陣定義為： MR= mnRRbbaarjjiiij,01 i=1,m j=1,n稱為二元關系R的關系矩陣。 ijr第4章 二元關系 【例4.3】設A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元關系，定義為：R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2寫出R的關系矩陣。 解：R的關系矩陣為：MR= 011001110101第4章 二元關系 【例4.4】設A=1,

5、2,3,4，R是A的二元關系，定義為：R=1,1,1,2,2,1,3,2,3,1,4,3,4,2,4,1寫出A上二元關系R的關系矩陣。 解：R的關系矩陣為： MR=0111001100010011 例4.4中的二元關系R是A上的二元關系，只需看成A到A的二元關系，利用上述定義，就可以方便地寫出它的關系矩陣。A上的二元關系和A到B的二元關系的關系矩陣的定義是相同的。第4章 二元關系 4.用圖表示二元關系 如果A和B是有限集，R是A到B二元關系，還可以用圖表示二元關系R。表示二元關系R的圖叫做R的關系圖。A到B二元關系的關系圖和A上的二元關系的關系圖的定義是不一樣的。分別描述如下： A到B二元關系

6、R的關系圖 設A=a1,a2,am，B=b1,b2,bn，R是A到B二元關系，R的關系圖的繪制方法如下： 畫出m個小圓圈表示A的元素，再畫出n個小圓圈表示B的元素。這些小圓圈叫做關系圖的結點(下同)。 如果ai,bj R，則從ai到bj畫一根有方向(帶箭頭)的線。這些有方向(帶箭頭)的線叫做關系圖的邊(下同)。 第4章 二元關系 例4.3中的二元關系R的關系圖如圖4.1。 A上的二元關系R的關系圖 設A=a1,a2,am，R是A上的二元關系，其關系圖如下繪制： 畫出m個小圓圈表示A的元素。 如果ai,ajR，則從ai到aj畫一根有方向(帶箭頭)的線。 例4.4中的二元關系R的關系圖如圖4.2。

7、 第4章 二元關系 4.2關系的運算 定義4.2.1設A，B是集合，RAB。 dom R=x|x,yR 叫做R的定義域。 ran R=y| x,yR 叫做R的值域。 FLD R= dom Rran R叫做R的域。 A叫做R的前域；B叫做R的陪域。 4.2.1二元關系的交、并、補、對稱差運算 定理4.2.1設R，S是X到Y的二元關系，則RS，RS，R-S，R，R S也是X到Y的二元關系。 證明：因為R，S是X到Y的二元關系，所以， RXY且SXY。顯然， RSXY，即RS是X到Y的二元關系。 RSXY，即RS是X到Y的二元關系。 R-SXY，即R-S是X到Y的二元關系。第4章 二元關系 在二元關

8、系運算中，認為全域關系是全集。所以 R= XY-R XY，即R是X到Y的二元關系。 由以上結論可以得到： (RS)XY和(SR)XY，從而 (RS)(SR)XY，所以 R S=(RS)(SR)XY，即R S是X到Y的二元關系。 【例4.5】設X=1,2,3,4，X上的二元關系H和S定義如下： H=x,y | 是整數 S=x,y | 是正整數試求HS，HS，H，S-H2yx 3yx 第4章 二元關系 解：將H和S用列舉法表示： H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2 S=4,1 HS=1,1,1,3,2,2,2,4,3,3,3,1,4,4, 4,2,4,1 HS= H

9、=X2- H=1,2,1,4,2,1,2,3,3,2,3,4, 4,3,4,1 SH=4,1 4.2.2二元關系的復合運算 定義4.2.2 設X，Y，Z是集合，RXY，SYZ，集合 x,zxXzZ(y)(yYx,yRy,zS)叫做R和S的復合關系。記為R S，R SXZ，即R S是X到Z的二元關系。 第4章 二元關系 【例4.6】X=1,2,3,4,5，X上的二元關系R和S定義如下： R=1,2,3,4,2,2 S=4,2,2,5,3,1,1,3試求R S，S R，R (S R)，(R S) R，R R，S S，R R R 解：R S=1,5,3,2,2,5 S R=4,2,3,2,1,4 (

10、R S) R=3,2 R (S R)=3,2 R R=1,2,2,2 S S=4,5,3,3,1,1 R R R =1,2,2,2 從例4.6可以看出，R SS R，這說明，二元關系的復合運算不滿足交換律。 第4章 二元關系 定理4.2.2 設X，Y，Z，W是集合，RXY，SYZ，T ZW，則 (R S) T= R (S T) 證明：x,w(R S) T(z)(x,zR Sz,wT) (z)(y)(x,yRy,zS)z,wT) (z)(y)(x,yRy,zS)z,wT) (y)(z)(x,yR(y,zSz,wT) (y)(x,yR(z)(y,zSz,wT) (y)(x,yRy,wS T)x,w

11、R (S T)所以 (R S) T=R (S T)第4章 二元關系 定理4.2.3 設R是A上的二元關系，R IA=IA R=R 證明：先證R IA=R x,yR IA(z)(x,zRz,yIA) (z)(x,zRz=y)x,yR所以 R IAR x,yRx,yRy,yIAx,yR IA所以 RR IA 故 R IA=R 類似的，可以證明IA R= R 第4章 二元關系 定理4.2.4 設R，S，T是A上的二元關系, 則 R (ST)=R SR T (RS) T=R TS T R (ST)R SR T (RS) TR TS T 證明：僅證明，類似地可證明、和。 x,yR (ST)(z)(x,z

12、Rz,yST) (z)(x,zR(z,ySz,yT) (z)(x,zRz,yS)(x,zRz,yT) (z)(x,zRz,yS)(z)(x,zRz,yT) x,yR Sx,yR T x,yR SR T故 R (ST)R SR T第4章 二元關系 一般地說，R SR TR (ST)，舉反例如下： 設A=1,2,3,4,5 R=4,1,4,2AA S=1,5,3,5AA T=2,5,3,5AA R SR T =4,54,5 =4,5 R (ST) =4,1,4,2 3,5= R SR TR (ST) 定理4.2.4的說明，關系的復合運算“ ”對并運算“”滿足左分配律。說明，關系的復合運算“ ”對并

13、運算“”滿足右分配律。所以，復合運算“ ”對并運算“”滿足分配律。由和知，復合運算“ ”對交運算“”不滿足分配律。 第4章 二元關系 定義4.2.3 設R是A上的二元關系，n為自然數，R的n次冪記為Rn，定義為： R0=IA Rn+1= Rn R 由定義4.2.3可以看出，A上的任何二元關系的0次冪都相等，等于A上的恒等關系IA。由定義4.2.3還可以看出： R1= R0 R=IA R=R R2= R1 R= R R R3= R2 R=(R R) R 因為復合運算滿足結合律，所以R3又可以寫成： R3= R R R 同樣的道理Rn也可以寫成： Rn= 的復合個RnRRR第4章 二元關系 例如,

14、在例4.6中 R2=R R=1,2,2,2 S2 =S S=4,5,3,3,1,1 R3=R R R=1,2,2,2 定理4.2.5設A是具有n個元素的有限集，R是A上的二元關系，則必存在自然數s和t，使得Rs=Rt，0st2 。 證明：R是A上的二元關系，對任何自然數k，由復合關系的定義知，Rk仍然是A上的二元關系，即RkAA。另一方面，根據定理4.1.1， A上的二元關系僅有2 種。列出R的各次冪R0，R1，R2 ， ，共有2 1個，必存在自然數s和t，使得Rs=Rt，0st2 。2n2n2n22nR2n第4章 二元關系 【例4.7】A= 1,2,3,4，A上的二元關系R定義如下： R=1

15、,2,2,1,2,3,3,4求二元關系R的各次冪，驗證定理4.2.5。 解：|A|=4 R0=IA=1,1,2,2,3,3,4,4 R1=R=1,2,2,1,2,3,3,4 R2=R1 R= R R=1,1,1,3,2,2,2,4 R3= R2 R =1,2,2,1,2,3,1,4 R4=R3 R=1,1,1,3,2,2,2,4=R2， 024216=2 R5=R4 R=R2 R=R3 R6=R5 R=R3 R=R4= R2 R2n=R2 R2n+1=R3, n =1,2,3,24第4章 二元關系 定理4.2.6設R是A上的二元關系，m，n為自然數，則 Rm Rn =Rm+n (Rm)n=Rm

16、n 證明：對任意給定的mN，關于n進行歸納證明： 當n=0時，Rm R0=Rm IA=Rm=Rm+0 設n=k時，Rm Rk=Rm+k。下證n=k+1時，結果也對。 Rm Rk+1=Rm (Rk R)=(Rm Rk) R=Rm+k R= Rm+k+1 對任意給定的mN，關于n進行歸納證明： 當n=0時，(Rm)0=IA=R0=Rm0 設n=k時，(Rm)k=Rmk。下證n=k+1時，結果也對。 (Rm)k+1=(Rm)k Rm=Rmk Rm=Rmk+m=Rm(k+1) 設X，Y，Z是集合，RXY，SYZ，R S是R和S的復 合關系，R SXZ，它們的關系矩陣分別是MR、MS和MR S。以下研究

17、這三個矩陣之間的關系。第4章 二元關系 設X=x1,x2, ,xm，Y=y1,y2, ,yn， Z=z1,z2, ,zP RXY， SYZ， R S XZ MR= mn i=1, ,m，j=1, ,n MS= np i=1,n，j =1, p MR S= mp i=1,m，j =1, p ijuRRyyxxujjiiij,01 ijvSSzzyyvjjiiij,01ijwSSRRzzxxwjjiiij,01第4章 二元關系 與 ， 有如下的關系： = i=1,m，j=1,p 將上述關系用矩陣符號記為： MR S=MR MS， 其中，i=1,m，j =1,p 矩陣運算“ ”叫做關系矩陣MR和MS

18、的布爾乘法。 把關系矩陣的布爾乘法公式 = i=1,m，j =1,p與線性代數中的矩陣乘法公式相比，發現，只要把矩陣乘法公式中的數乘改為合取，把數加改為析取，就得到了關系矩陣的布爾乘法公式。)(1kjiknkvu ijwijw)(1kjiknkvu ijwijuijv第4章 二元關系 【例4.8】A=1,2,3,4,5，A上的二元關系R和S定義如下： R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2試求MR S和MR MS，它們是否相等 ? 解：按照R 和S的定義，求出 R S=1,5,3,2,2,5 寫出R 、S和R S關系矩陣如下： MR= MS= MR S=00000000

19、0001000000100001000000000100000110000001000000000000000101000010000第4章 二元關系 MR MS= = 所以MR S=MR MS 4.2.3二元關系的求逆運算 定義4.2.4 設X，Y是集合，RXY，集合 y,xx,yR叫做R的逆關系。記為RC，RCYX，RC是Y到X的二元關系。 容易證明，RC的關系矩陣 是R的關系矩陣MR的轉置矩陣，即 =MRT 可以驗證，將R關系圖中的弧線的箭頭反置，就可以得到RC關系圖。000000000001000000100001000000000100000110000001000000000000

20、000101000010000CRMCRM第4章 二元關系 【例4.9】設X=1,2,3,4，Y=a,b,c，X到Y二元關系 R=1,a,2,b,4,c， 試求RC，寫出MR和 ，驗證 =MRT 畫出R和RC的關系圖，驗證將R關系圖中的弧線的箭頭反置可得到RC關系圖。 解：RC=a,1,b,2,c,4 R和RC的關系矩陣是： MR= =顯然， =MRT 100000010001CRM100000100001CRMCRMCRM第4章 二元關系 R和RC的關系圖分別是圖4.3和圖4.4，它們中的弧線的方向是相反的。第4章 二元關系 定理4.2.7設X，Y是集合，RXY，則 (RC )C= R do

21、m RC= ran R， ran RC= dom R 證明： x,yRy,xRCx,y(RC)C所以 (RC )C= R xdom RC(y)(x,yRC)(y)(y,xR) xran R所以 dom RC= ran R 類似的可以證明ran RC= dom R第4章 二元關系 定理4.2.8設X，Y是集合，R，S是X到Y的二元關系，則 (RS)C = RCSC (RS)C =RCSC (AB)C=BA (R) C = (R C) (R-S)C =RC-SC 證明： x,y(RS)Cy,xRSy,xRy,xS x,yRCx,ySCx,yRCSC所以 (RS)C =RCSC 類似可證明和。 x,

22、y(R)Cy,xRy,xRy,xR x,yRCx,yRC x,y (RC) 所以 (R) C =(R C)第4章 二元關系 利用、和證明： (R-S)C=(RS)C=RC(S)C=RC(SC)=RC-SC 定理4.2.9設X，Y，Z是集合，RXY，SYZ，則 (R S)C=SC RC 證明： z,x(R S)Cx,z(R S) (y)(x,yRy,zS) (y)(y,xRCz,ySC) (y)(z,ySCy,xRC) z,xSC RC所以 (R S)C=SC RC第4章 二元關系 4.3 關系的性質 定義4.3.1 設RXX，(x)(xXx,xR)，則稱R在X上是自反的。 設R是X上的自反關系

23、，由定義4.3.1知，R的關系矩陣MR的主對角線全為1；在關系圖中每一個結點上都有自回路。 設X=1,2,3，X上的二元關系 R=1,1,2,2,3,3,1,2R是自反的,它的關系圖如圖4.5所示，關系矩陣如下： MR=100010011第4章 二元關系 定理4.3.1 設R是X上的二元關系，R是自反的當且僅當IXR。 證明：設R在X上是自反的，下證IXR。 x,yIXx=yx,yR，即IXR。 設IXR，下證R在X上是自反的。 xXx,xIXx,xR，即R在X上是自反的。 定義4.3.2 設RXX，(x)(xXx,xR)，則稱R在X上是反自反的。 設R是X上的反自反關系，由定義4.3.2可知

24、，R的關系矩陣MR的主對角線全為0；在R的關系圖中每一個結點上都沒有自回路。 設X=1,2,3，X上的二元關系R=1,2,2,3,3,1，R是反自反的,它的關系圖如圖4.6所示，關系矩陣如下：第4章 二元關系MR = 001100010 【例4.11】設R是實數集合， =x,y| xRyRxy是實數集合上的大于關系。證明實數集合上的大于關系是反自反的。 證明：xR，xx，x,x，所以是反自反的。第4章 二元關系 定理4.3.2 設R是X上的二元關系, R是反自反的當且僅當RIX=。 證明：設R在X上是反自反的，下證RIX=。 假設RIX 必存在x,yRIXx,yRx,yIXx,yRx=y，即x

25、,xR，這與R是X上的反自反關系相矛盾。所以RIX=。 設RIX=，下證R在X上是反自反的。 任取xX x,xIX，由于RIX=，必然x,xR，即R在X上是反自反的。 第4章 二元關系 【例4.12】設A=1,2,3，定義A上的二元關系如下： R=1,1,2,2,3,3,1,3 S=1,3 T=1,1試說明R，S，T是否是A上的自反關系或反自反關系。 解：因為1,1、2,2和3,3都是R的元素，所以R是A上的自反關系，不是反自反關系。因為1,1、2,2和3,3都不是S的元素，所以S是反自反關系，不是A上的自反關系。因為2,2T，所以T不是A上的自反關系。因為1,1T，所以T不是A上的反自反關系

26、。 第4章 二元關系 定義4.3.3 設RXX，(x)(y)(xXyXx,yRy,xR)，則稱R在X上是對稱的。 R是X上的對稱關系，由定義4.3.3知，R的關系矩陣MR是對稱陣。在R的關系圖中，如果兩個不同的結點間有邊，一定有方向相反的兩條邊。 設X=1,2,3，X上的二元關系R=1,2,2,1,3,3，R是對稱的。它的關系圖如圖4.7所示，關系矩陣如下： MR=100001010第4章 二元關系 【例4.13】設A=1,3,5,7，定義A上的二元關系如下： R=a,b|(ab)/2是整數試證明R在A上是自反的和對稱的。 證明：aA，(a-a)/2=0，0是整數，所以 a,aR。即R是自反的

27、。 aA，bA，a,bR，(a-b)/2是整數，因為整數的相反數也是整數，所以(b-a)/2=-(a-b)/2是整數，b,aR。即R是對稱的。 定理4.3.3 設R是X上的二元關系, R是對稱的當且僅當R=RC。 證明：設R是對稱的，下證R =RC。 x,yRy,xRx,yRC , 所以 R =RC。 設R =RC，下證R是對稱的。 x,yRy,xRCy,xR, 所以R是對稱的。第4章 二元關系 定義4.3.4 設RXX， (x)(y)(xXyXx,yRy,xR(x=y)則稱R在X上是反對稱的。 x,yRy,xR(x=y) (x=y)(x,yRy,xR) (x=y)(x,yRy,xR) (x=

28、y)x,yR)y,xR (xy)x,yR)y,xR (xy)x,yRy,xR x,yR(xy)y,xR由此，反對稱的定義又可以等價的描述為： (x)(y)(xXyXx,yR(xy)y,xR)第4章 二元關系 設R是X上的反對稱關系，由定義4.3.4知，在R的關系矩陣MR中以主對角線為軸的對稱位置上不能同時為1(主對角線除外)。在R的關系圖中每兩個不同的結點間不能有方向相反的兩條邊。 設X=1,2,3，X上的二元關系R=1,2,2,3,3,3，R是反對稱的。它的關系圖如圖4.8所示，關系矩陣如下： MR= 100100010第4章 二元關系 【例4.14】 設A=1,2,3，定義A上的二元關系如

29、下： R=1,1,2,2 S=1,1,1,2,2,1 T=1,2,1,3 U=1,3,1,2,2,1試說明R，S，T，U是否是A上的對稱關系和反對稱關系。 解：R是A上的對稱關系，也是A上的反對稱關系。 S是A上的對稱關系。因為1,2和2,1都是S元素，而12，所以S不是A上的反對稱關系。 因為1,2T，而2,1T，所以T不是A上的對稱關系。T是A上的反對稱關系。 U不是A上的對稱關系，也不是A上的反對稱關系。第4章 二元關系 定理4.3.4設R是X上的二元關系，則R是反對稱的當且僅當RRCIX。 證明：設R是反對稱的，下證RRCIX。 x,yRRCx,yRx,yRC x,yRy,xR 因為R

30、是反對稱的，所以y=x，x,y=x,x=y,yIX，故RRCIX 設RRCIX，下證R是反對稱的。 x,yRy,xRx,yRx,yRC x,yRRC因為RRCIX，所以x,yIX，故x=y，R是反對稱的。 定義4.3.5 設RXX， (x)(y)(z)(xXyXzXx,yRy,z R x,zR)則稱R在X上是傳遞的。 第4章 二元關系 【例4.15】設R是實數集合， S=x,y|xRyRx=y是實數集合上的等于關系。證明實數集合上的等于關系是傳遞的。 證明：xR，yR，zR，x,yS且y,zS，由S的定義有x=y和y=z，由實數相等的概念得x=z。再根據S的定義，x,zS。故實數集合上的等于關

31、系S是傳遞的。 定理4.3.5 設R是X上的二元關系，R是傳遞的當且僅當R R R。 證明：設R是傳遞的，下證R RR。x,yR R，zX, 使得x,zR且z,yR，又因為R是傳遞的，所以x,yR，這就證明了R R R。 設R R R，下證R是傳遞的。x,yR且y,zR，由復合關系的定義得x,z R R ，因為R RR，所以x,zR，所以R是傳遞的。第4章 二元關系 上述的5個定理，可以作為相應概念的定義使用，用來判斷和證明關系的性質。有些問題用這5個定理處理是非常方便的。請看下面的例題。 【例4.16】設R，S是X上的二元關系，證明 若R，S是自反的，則RS和RS也是自反的。 若R，S是對稱

32、的，則RS和RS也是對稱的。 若R，S是傳遞的，則RS也是傳遞的。 證明：設R，S是自反的，由定理4.3.1知，IXR，IXS，所以IXRS，IXRS，再由定理4.3.1知，RS和RS也是自反的。 第4章 二元關系 設R，S是對稱的，由定理4.3.3知，R=RC，S=SC，根據定理4.2.8，RS=RCSC=(RS)C，RS=RCS C=(RS) C，再由定理4.3.3知，RS和RS也是對稱的。 設R，S是傳遞的，由定理4.3.5知，R RR，S SS，據定理4.2.4， (RS) (RS)(R R)(R S)(S R)(S S) (R R)(S S)RS即(RS) (RS)RS，再由定理4.

33、3.5，RS是傳遞的。 以上研究了二元關系的5個性質及其關系矩陣、關系圖的特點，它們對今后的學習是重要的。第4章 二元關系 4.4關系的閉包運算 定義4.4.1 設R XX，X上的二元關系R 滿足： R是自反的(對稱的，傳遞的)。 RR。 對X上的任意二元關系R，如果RR且R是自反的 (對稱的，傳遞的)，就有RR。 則稱R是R的自反(對稱，傳遞)閉包。記為r(R)(s(R), t(R) 定義4.4.1的和的意思是自反(對稱，傳遞)閉包R是包含R的自反(對稱，傳遞)關系；定義4.4.1的的意思是在所有包含R的自反(對稱，傳遞)關系中自反(對稱，傳遞)閉包R是最小的。所以，定義4.4.1又可以描述

34、為：包含R的最小自反(對稱，傳遞)關系是R的自反(對稱，傳遞)閉包。 傳遞閉包t(R)有時也記為R+，讀作“R加”。傳遞閉包在語法分析中有很多重要的應用。第4章 二元關系 當二元關系R是自反(對稱，傳遞)的時，求R的自反(對稱，傳遞)閉包方法由下面的定理給出了。 定理4.4.1 設RXX，則 R是自反的當且僅當r(R)=R。 R是對稱的當且僅當s(R)=R。 R是傳遞的當且僅當t(R)=R。 證明：僅證明，其余留做練習。 設R是自反的，下證r(R)=R 令R=R R=R，R是自反的，所以R是自反的。 因為R=R，所以RR。 R是X上的任意自反關系且RR，因為R=R，所以RR。 故R是R的自反閉

35、包。即r(R)=R。 第4章 二元關系 設r(R)=R，下證R是自反的。 由自反閉包的定義知，R是自反的。 以下的幾個定理給出了求二元關系R的自反閉包、對稱閉包和傳遞閉包的一般方法。 定理4.4.2 設RXX，則 r(R)=RIX 證明：令R=RIX IXRIX，而RIX =R，所以IXR，R是自反的。 RRIX，而RIX =R，所以R R R是X上的任意自反關系且RR，由于R是自反的，所以IX R，從而有R=RIXR。 根據自反閉包的定義，R=RIX是R的自反閉包，即r(R)=RIX。 第4章 二元關系 定理4.4.3 設RXX，則s(R)=RRC 證明：令R=RRC (R)C= (RRC)

36、 C= RC(RC)C= RCR=RRC=R，所以R是對稱的。 RRRC，而RRC =R，所以RR。 R是X上的任意對稱關系且RR， x,yRCy,xRy,xR x,yR(R是對稱的)，所以RCR，從而有R=RRCR。R是R的對稱閉包，即s(R)= RRC。 定理4.4.4 設RXX，則 t(R)=RR2R3 證明：先證RR2R3t(R) 用數學歸納法證明：iI+ Rit(R)第4章 二元關系 當i =1時，由傳遞閉包的定義，R1= Rt(R)。 設i =n時，Rnt(R)。下證 Rn+1t(R)。 x,yRn+1(c)(x,cRnc,yR) (c)(x,ct(R)c,yt(R) (和歸納假設

37、) x,yt(R) (t(R)是傳遞的)即 Rn+1 t (R) 故RR2R3 t (R) 再證t(R)RR2R3 顯然 RRR2R3 以下證明RR2R3是傳遞的。 x,yRR2R3且y,zRR2R3 tI+使x,yRtsI+ 使y,zRs x,zRt Rs=Rt+sRR2R3 x,zRR2R3 根據傳遞關系的定義，RR2R3是傳遞的。第4章 二元關系 綜上所述，RR2R3是包含R的傳遞關系。而R的傳遞閉包是包含R的最小傳遞關系。所以t(R)RR2R3 t(R)=RR2R3 【例4.17】設A=1,2,3，定義A上的二元關系R為： R=1,2,2,3,3,1試求：r(R)，s(R)，t(R)

38、解：r(R)= RIA=1,2,2,3,3,1,1,1,2,2,3,3 s(R)=RRC=1,2,2,3,3,1,2,1,3,2,1,3 以下求t(R)： R2= R R=1,3,2,1,3,2 R3= R2 R =1,1,2,2,3,3=IA R4= R3 R = IA R=R 繼續這個運算，則有第4章 二元關系 R= R4= R7= =R3n+1= R2= R5= R8= =R3n+2= R3= R6= R9= =R3n+3= 其中：n是任意的自然數。t(R)=RR2R3 t(R)= RR2R3 =1,1,1,2,1,3,2,1,2,2,2,3, 3,1,3,2,3,3 當A是具有n個元素

39、的有限集時，由定理4.2.5知，存在自然數s和t，使得Rs=Rt，0st2。于是 Rt+1=Rs+1，Rt+2=Rs+2，即當it，Ri就出現了重復。因為集合的并運算滿足冪等律，所以，t(R)=RR2R3=RR2R3R 這個結論還可以改善。 22n第4章 二元關系 定理4.4.5 設|X|=n，RXX，則 t(R)= RR2Rn 證明：只需證明t(R)RR2R3Rn 設x,yt(R)=RR2R3，由并集合的定義知，存在最小的正整數k使得x,yRk。下證kn。 設kn，根據復合關系的定義，存在X中的元素序列：x=a0，a1，a2，,ak-1,ak=y，使xRa1，a1Ra2, ,ak-1Rak(

40、y)，此序列中有k+1個X的元素，k+1n+1n。而X中只有n個元素，所以a0，a1，a2，,ak-1,ak中必有相同的元素，設ai = aj，0ijk。去掉序列中ai+1到aj的所有元素，于是xRa1，a1Ra2，ai-1Rai，ajRaj+1，ak-1Rak(y)成立。即x,yRs，其中S=k-(j-i)。因為j-i1，所以Sk，這與k是使得x,yRk的最小正整數的假設相矛盾。故kn。 所以RkRR2R3Rn，從而有 x,yRR2R3Rn t(R)RR2R3Rn第4章 二元關系 顯然，RR2R3Rn RR2R3= t(R)，即RR2R3Rnt(R)。 于是t(R)=RR2R3Rn 除了用關

41、系的復合運算計算傳遞閉包外，還可以用關系矩陣求傳遞閉包。請看下列的例題。 【例4.18】設A=1,2,3，定義A上的二元關系R為：R=1,2,2,3,3,1試用關系矩陣求傳遞閉包t(R)。 解：用關系矩陣求t(R)的方法如下：001100010RM第4章 二元關系0100011000011000100011000102RRRMMM10001000100110001001000110023RRRMMM11111111132)(RRRRtMMMM其中，表示矩陣的對應元素進行析取運算。 第4章 二元關系 定理4.4.6設RXX，則(RIX)n= (RR2Rn )IX 證明：用數學歸納法證明： 當n=

42、2時， (RIX)2=(RIX)(RIX)=(RIX) R)(RIX) IX) =(R R)(IX R)(RIX) =R2RRIX=R2RIX=(RR2)IX 設n=k時，(RIX)k=(RR2R3R k)IX， 證明n=k+1時，(RIX)k+1=(RR2R kR k+1)IX (RIX)k+1=(RIX)k (RIX) =(RR2R3R kIX) (RIX) =(RR2R3R kIX) R) (RR2R3RkIX) IX) =(R2R3R kR k+1R) (RR2R3R kIX) =(RR2R3R kR k+1)IX第4章 二元關系 二元關系的閉包仍然是二元關系，還可以求它的閉包。例如，

43、R是A上的二元關系, r(R)是它的自反閉包，還可以求r(R)的對稱閉包。r(R)的對稱閉包記為s(r(R)，簡記為sr(R)，讀做R的自反閉包的對稱閉包。類似的，R的對稱閉包的自反閉包r(s(R)簡記為rs(R)，R的對稱閉包的傳遞閉包t(s(R)，簡記為ts(R)， 通常用R*表示R的傳遞閉包的自反閉包rt(R)，讀作“R星”。在研究形式語言和計算模型時經常使用R*。 定理4.4.7 設R XX，則 rs(R)=sr(R) rt(R)=tr(R) st(R)ts(R) 證明： rs(R)=r(s(R)=r(RRC)=(RRC)IX =(RRC)IXIX=(RIX)(RCIX) =(RIX)

44、(RIX)C= s(RIX)= sr(R)第4章 二元關系 tr(R)=t(r(R)= t(RIX) = = = = = t(R)IX= rt(R) 留給讀者證明。1)(iiXIR11)(iXijjIR111)()(iiXijjIRXiiIR 1第4章 二元關系 4.5 等價關系 等價關系是最重要、最常見的二元關系之一。它有良好的性質。在計算機科學和計算機技術、信息科學和信息工程中都有廣泛的應用。目前對等價關系的研究是深入而完備的。本節介紹等價關系的主要結論。 定義4.5.1 設RXX，如果R是自反的，對稱的和傳遞的，則稱R是X上的等價關系。設R是等價關系，若x,yR，稱x等價于y。 因為等價

45、關系是自反的和對稱的，所以等價關系的關系矩陣主對角線全為1且是對稱陣；其關系圖每一個結點上都有自回路且每兩個結點間如果有邊，一定有方向相反的兩條邊。 第4章 二元關系 【例4.19】設A=1,2,3,4,5，R是A上的二元關系， R=1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5，證明R是A上的等價關系。 證明：寫出R的關系矩陣MR如下： MR的主對角線全為1且是對稱陣，所以R是自反的和對稱的；還可以用二元關系傳遞性的定義證明R是傳遞的。故R是A上的等價關系。1000001100011000001100011RM第4章 二元關系 也可以用關系圖說明R是等價關系。圖4.9

46、是R的關系圖。在R的關系圖中每一個結點上都有自回路；每兩個結點間如果有邊，一定有方向相反的兩條邊。所以R是自反的和對稱的。與前面一樣，也可以用二元關系傳遞性的定義證明R是傳遞的。故R是A上的等價關系。 從圖4.9不難看出，等價關系R的關系圖被分為三個互不連通的部分。每部分中的結點兩兩都有關系，不同部分中的任意兩個結點則沒有關系。第4章 二元關系 設x和y是兩個整數，k是一個正整數，若x，y用k除的余數相等，就稱x和y模k同余，也稱x和y模k的的等價。記為 x y mod k 設x(y)用k除的商為t1 ( t2 )，余數為a1 ( a2 )，數學上將x(y)表示成為： x= kt1a1， t1

47、I，a1I且0a1k。 y= kt2a2， t2I，a2I且0a2k。 若x，y用k除的余數相等，x-y= k(t1-t2)，t1-t2I。 即x-y可以被k整除。所以，x和y模k同余還可以描述為：x-y可以被k整除。第4章 二元關系 【例4.20】 設R=x,y xIyIx y mod k是整數集合I上的二元關系。證明R是等價關系。 證明：設a,b,c是任意的整數。 因為 a-a=k0，所以 aa mod k，a,aR。故R是自反的。 若a,bR，a b mod k，a-b = kt，tI，b-a =-(a-b)=k(t)，tI，ba mod k，b,aR。故R是對稱的。 若a,bR且b,c

48、R， a-b = kt1，t1I，b-c = kt2， t2 I， a-c=(a-b)+(b-c)=kt1+kt2=k(t1+t2)，t1+t2I，a,cR，故R是傳遞的。 所以R是整數集合I上的等價關系。 第4章 二元關系 定義4.5.2 設R是X上的等價關系，xX，集合y yXxRy 叫做x形成的R等價類。記為 xR 在例4.19中，等價關系R等價類為：1R=2R=1,2，3R=4R=3,4，5R=5。在R的關系圖(圖4.9)中，三個互不連通的部分，每一部分中的所有結點構成一個等價類。 上述模3等價關系的等價類叫模3等價類，模3等價類有以下三個： 0R=，6，3，0，3，6， 1R=，5，

49、2，1，4，7， 2R=，4，1，2，5，8， 定理4.5.1 設 R是X上的等價關系，xX，則有 xRX xxR 定理證明留作練習。第4章 二元關系 從定理4.5.1可以看出，等價關系的任何等價類是該等價關系前域(或陪域)的子集。例如，模3等價類是整數集合的子集：0RI，1RI，2RI。 從定理4.5.1還可以看出，任何等價類是非空集合。x形成的R等價類xR至少有一個元素x。例如，在模3等價類中，00R，11R，22R。 定理4.5.2 設R是X上的等價關系，對于X的任意元素a和b，aRb 的充分必要條件是aR=bR 證明：設aRb，下證 aR=bR caR，aRc，由R的對稱性有cRa，由

50、條件aRb和R的傳遞性得cRb，再根據R的對稱性有bRc，cbR，故aRbR。 類似地可以證明 bRaR。這就證明了aR=bR。 設 aR=bR，下證aRb。 由定理4.5.1知aaR，因為aR=bR，所以abR，bRa，由R的對稱性有aRb。第4章 二元關系 定義4.5.3 設R是X上的等價關系，R的所有等價類組成的集合xRxX叫做X關于R的商集。記為X/R。 在例4.19中，等價關系R 有三個等價類：1R=2R=1,2，3R=4R=3,4，5R=5，A關于R的商集 A/R=1R，2R，5R = 1,2，3,4，5 模3等價關系R的等價類有以下三個：0R，1R和2R，由它確定的整數集合I關于

51、R的商集I/R=0R，1R，2R。 定理4.5.3 設 R是X上的等價關系，X關于R的商集X/R是X的一個劃分。 證明：由定理4.5.1知，xRX且xR。 證明 = X。 因為 xRX，所以 X。 另一方面， xX，由定理4.5.1知，xxR ，x ，所以，X 。故 =XXxRxXxRxXxRxXxRxXxRxXxRx第4章 二元關系 證明商集X/R中的元素是兩兩互不相交的。 設 aRbR ，證明aRbR = 假定aRbR caRbR caRcbR aRcbRcaRccRb (因為R是對稱的) aRb (因為R是傳遞的) aR=bR (定理4.5.2)與假定矛盾。 所以aRbR第4章 二元關系

52、 定理4.5.4 設S=S1，S2，Sm是X的一個劃分， R=x,y| x和y在同一個劃分塊中，則R是X上的等價關系。 證明：設xX=S1S2Sm，因為S是X的一個劃分，所以存在惟一的劃分塊SjS，使xSj，于是有x,xR，即R是自反的。 設x,yR，x和y在某個劃分塊Sj中，則y和x也在劃分塊Sj中，所以y,xR，即R是對稱的。 設x,yRy,zRx和y在Si中且y和z在Sj中 ySiSj，因為S是X的一個劃分，其中元素兩兩互不相交，故必有Si=Sjx和z在Sj中x,zR，即R是傳遞的。 將定理4.5.4中的等價關系R叫做劃分S導出的等價關系。劃分S導出的等價關系R也可以表示為： R =(S

53、1S1)(S2S2)(SmSm)第4章 二元關系 【例4.21】設X=1,2,3,4，X的劃分S=1，2,3，4，試寫出S導出的等價關系R。 解：R=1,1,2,2,2,3,3,2,3,3,4,4 =112,32,344可以驗證R是X上的等價關系。 定理4.5.5 設R，S集合X上的等價關系，則R=S 當且僅當 X/R=X/S 證明：設R=S，證明X/R=X/S。 先證 xX，xR=xS axRxRaxSaaxS，所以xRxS。 類似地可以證明 xS xR，這就證明了xR=xS。第4章 二元關系 再證 X/R=X/S。 xRX/R，xR=xSX/S，即xRX/S，所以X/RX/S。 類似地可以

54、證明X/SX/R，于是X/R=X/S。 設X/R=X/S，證明R=S。 因為X/R=X/S，aRX/R，必存在cSX/S，使aR=cS a,bRaRbbaRbaRaaR bcSacS cSbcSabSccSa (因為S是對稱的) bSa (因為S是傳遞的) aSb (因為S是對稱的) a,bS 所以R S。 類似地可以證明S R，于是R=S。第4章 二元關系 【例4.22】設X=1,2,3，寫出集合X上的所有等價關系。 解：先寫出集合X上的所有劃分，它們是： S1=1,2,3， S2=1,2,3， S3=1,3,2 S4=2,3,1, S5=1,2,3 對應的等價關系為： R1=1,2,31,

55、2,3=XX R2=1,21,233 =1,1,1,2,2,1,2,2, 3,3 R3=1,31,322 =1,1,1,3,3,1,3,3,2,2 R4=2,32,311 =2,2,2,3,3,2,3,3,1,1 R5=112233 =1,1,2,2,3,3=IX第4章 二元關系 4.6 相容關系 定義4.6.1 設RXX，如果R是自反的和對稱的，則稱R是X上的相容關系。 根據定義4.6.1，相容關系有以下三個性質： 所有等價關系都是相容關系。 相容關系的關系矩陣主對角線全為1且是對稱陣。 相容關系的關系圖每一個結點上都有自回路且每兩個結點間如果有邊，一定有方向相反的兩條邊。第4章 二元關系

56、【例4.23】設A=316,347,204,678,770，A上的二元關系R定義為：R=x,y| xAyAx和y有相同數碼，證明R是A上的相容關系。寫出關系矩陣和關系圖。用關系矩陣和關系圖驗證R是A上的相容關系。 證明：集合A中的每個數自己和自己有相同數碼，故R是自反的；對于集合A中任意x和y，如果x和y有相同數碼，則y和x也有相同數碼。故R是對稱的。于是，R是相容關系。 令a=316，b=347，c=204，d=678，e=770 用列舉法將R表示為： R=a,a,a,b,a,d,b,a,b,b,b,c,b,d, b,e,c,b,c,c,c,e,d,a,d,b,d,d, d,e,e,b,e,

57、c,e,d,e,e =a,b,a,d,b,a,b,c,b,d,b,e,c,b,c,e, d,a,d,b,d,e,e,b,e,c,e,dIA第4章 二元關系1111011011101101111101011RM R的關系矩陣MR主對角線全為1且是對稱陣，說明R是相容關系。 R的關系圖如圖4.10所示。在關系圖中，每一個結點上都有自回路且每兩個結點間如果有邊，一定有方向相反的兩條邊。表明了R是相容關系。第4章 二元關系 因為相容關系的關系圖每一個結點上都有自回路且每兩個結點間如果有邊，一定有方向相反的兩條邊。所以可省去每一個結點上的自回路，將兩個結點間方向相反的兩條有向邊改為一條無向邊，得到一個簡

58、化圖。此圖叫做R的簡化關系圖。例4.23中的相容關系R的簡化關系圖如圖4.11所示。第4章 二元關系 定義4.6.2 設R是X上相容的關系，CX，如果a,bC，有a,bR，則稱C是由相容關系R產生的相容類。 如果R是X上的相容關系，C是由相容關系R產生的相容類。從定義可以看出： 相容類C一定是X的子集。 xX，因為相容關系R是自反的，x,xR，所以x是由相容關系R產生的一個相容類。即X中的任何元素組成的單元素集是由相容關系R產生的一個相容類。 在例4.23中， a,a,b,b,c,b,d,e都是R產生的相容類。 a,bd=a,b,d和 b,ce=b,c,e也是R產生的相容類。 但是b,d,e與

59、任何非空集合的并集都不再是R產生的相容類，這種相容類叫做最大相容類。第4章 二元關系 定義4.6.3 設R是X上的相容關系，C是R產生的相容類。如果它不是其它任何相容類的真子集，則稱C為最大相容類。記為CR。 根據定義4.6.3，最大相容類CR具有如下的性質： CR中任意元素x與CR中的所有元素都有相容關系R。 X-CR中沒有一個元素與CR中的所有元素都有相容的關系R。 性質的意思是：CR是R產生的相容類，即最大相容類首先是相容類。性質的意思是：CR是最大相容類。 利用相容關系的簡化關系圖可以求最大相容類，方法如下： 最大完全多邊形的頂點構成的集合是最大相容類。 孤立點構成的集合是最大相容類。

60、 如果一條邊不是任何完全多邊形的邊，則它的兩個端點構成的集合是最大相容類。 第4章 二元關系 【例4.24】設X=1,2,3,4,5,6，R是X上的相容關系，它的簡化關系圖如圖4.12所示，試找出所有最大相容類。 解：最大完全3邊形的頂點構成的集合：2,3,5和2,3,4。 孤立點構成的集合：6。 不是任何完全多邊形的邊的兩個端點構成的集合1,5。 所以，最大相容類為:2,3,5，2,3,4，1,5和6。第4章 二元關系 定理4.6.1 設R是有限集合X上的相容關系，C是R產生的相容類，那么必存在最大相容類CR，使得 CCR。 證明：設X=x1,x2, ,xn，令C0=C。 如下構造相容類序列