第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章 二元关系 4.3 关系的性质 定义4.3.1 设RXX，(x)(xXx,xR)，则称R在X上是自反的。 设R是X上的自反关系，由定义4.3.1知，R的关系矩阵MR的主对角线全为1；在关系图中每一个结点上都有自回路。 设X=1,2,3，X上的二元关系 R=1,1,2,2,3,3,1,2R是自反的,它的关系图如图4.5所示，关系矩阵如

2、下： 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可知，R的关系矩阵MR的主对角线全为0；在R的关系图中每一个结点上都没有自回路。 设X=1,2,3，X上的二元关系R=1,2,2,3,3,1，R是反自反的,它的关系图如图4.6所示，关系矩阵如下：第4章 二元关系

3、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,xR，这与R是X上的反自反关系相矛盾。所以RIX=。 设RIX=，下证R在X上是反自反的。 任取xX x,xIX，由于RIX=，必然x,xR，即R在X上是反自反的。 第4章 二元关系 【例4.12】设A=1

4、,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上的反自反关系。 第4章 二元关系 定义4.3.3 设RXX，(x)(y)(xXyXx,yRy,xR)，则称R在X上是对称的。 R是X上的对称关系，由定义4.3.3知，R的关系矩阵MR是对称阵。在R的关系图中，如果两个不同

5、的结点间有边，一定有方向相反的两条边。 设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是自反的。 aA，bA，a,bR，(a-b)/2是整数，因为整数的相反数也是整数，所以(b-a)/2=-(a-b)/2是整数，b,aR。即R是对称的。 定理4.3.3 设R是X上的二元关系, R是对称的当且仅当R=R

6、C。 证明：设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=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章 二元关系

7、设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上的二元关系如下： 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是

8、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是反对称的，所以y=x，x,y=x,x=y,yIX，故RRCIX 设RRCIX，下证R是反对称的。 x,yRy,xRx,yRx,yRC x,yRRC因为RRCIX，所以x,yIX，故x=y，R是反对称的。 定

9、义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。故实数集合上的等于关系S是传递的。 定理4.3.5 设R是X上的二元关系，R是传递的当且仅当R R R。 证明：设R是传递的，下证R RR。x,yR R，zX, 使得x,zR且z,yR，又因为R是传递的，所以x,yR，这就证明了

10、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是对称的，则RS和RS也是对称的。 若R，S是传递的，则RS也是传递的。 证明：设R，S是自反的，由定理4.3.1知，IXR，IXS，所以IXRS，IXRS，再由定理4.3.1知，RS和RS也是自反的。 第4章 二

11、元关系 设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.3.5，RS是传递的。 以上研究了二元关系的5个性质及其关系矩阵、关系图的特点，它们对今后的学习是重要的。第4章 二元关系 4.4关系的闭包运算 定义4.4.1 设R XX，X上的二元关系R 满足： R是自反

12、的(对称的，传递的)。 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又可以描述为：包含R的最小自反(对称，传递)关系是R的自反(对称，传递)闭包。 传递闭包t(R)有时也记为R+，读作“R加”。传递闭包在语法分析中有很多重要的应用。第4章 二元关系 当二元关系R是自反(对称，传递)的时

13、，求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的自反闭包。即r(R)=R。 第4章 二元关系 设r(R)=R，下证R是自反的。 由自反闭包的定义知，R是自反的。 以下的几个定理给出了求二元关系R的自反闭包、对称闭包和传递闭包的一般方法。 定理4.4.2 设RXX

14、，则 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) C= RC(RC)C= RCR=RRC=R，所以R是对称的。 RRRC，而RRC =R，所以RR。 R是X上的任意对称关系且RR， x,yRCy,xRy,xR x,yR(R是对称的)，所以RCR，从而有R=

15、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) (和归纳假设) x,yt(R) (t(R)是传递的)即 Rn+1 t (R) 故RR2R3 t (R) 再证t(R)RR2R3 显然 RRR2R3 以下证明RR2R3是传递的。 x,yRR2R3且y,zRR2R3 tI+

16、使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) 解：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

17、 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个元素的有限集时，由定理4.2.5知，存在自然数s和t，使得Rs=Rt，0st2。于是 Rt+1=Rs+1，Rt+2=Rs+2，即当it，Ri就出现了重复。因为集合的并运算满足幂等律，所以，t(R)=RR2R3=R

18、R2R3R 这个结论还可以改善。 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(y)，此序列中有k+1个X的元素，k+1n+1n。而X中只有n个元素，所以a0，a1，a2，,ak-1,ak中必有相同的元素，设ai = aj，0ijk。去掉序列中ai+1到aj的所有元素，于是xRa1，a1

19、Ra2，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 除了用关系的复合运算计算传递闭包外，还可以用关系矩阵求传递闭包。请看下列的例题。 【例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=2时， (RIX)2=(RIX)(RIX)=(RIX) R)(RIX) IX) =(R R)(IX R)(RIX) =R2RRIX=R