第4章 二元关系

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。 如下构造相容类序列