第4章二元关系（二）ppt课件.ppt

《第4章二元关系（二）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章二元关系4.1二元关系及其表示4.2关系的运算4.3关系的性质4.4关系的闭包运算4.5等价关系4.6相容关系4.3关系的性质定义4.3.1设RX×X，(x)(xX→x,xR)，则称R在X上是自反的。设R是X上的自反关系，由定义4.3.1知，R的关系矩阵MR的主对角线全为1；在关系图中每一个结点上都有自回路。设X=1,2,3，X上的二元关系R=1,1,2,2,3,3,1,2R是自反的,它的关系图如图4.5所示，关系矩阵如下：MR=定理4.3.1设R是X上的二元关系，R是自反的当且仅当IXR。证明：设R在X上是自反的，下证IXR。x,yIX

2、x=yx,yR，即IXR。设IXR，下证R在X上是自反的。xXx,xIXx,xR，即R在X上是自反的。定义4.3.2设RX×X，(x)(xX→x,xR)，则称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所示，关系矩阵如下：MR=【例4.11】设R是实数集合，＞=x,y

3、xR∧yR∧x＞y是实数集合上的大于关系。证明实数集合上的

4、大于关系是反自反的。证明：xR，x≯x，x,x＞，所以＞是反自反的。定理4.3.2设R是X上的二元关系,R是反自反的当且仅当R∩IX=Æ。证明：设R在X上是反自反的，下证R∩IX=Æ。假设R∩IX≠Æ必存在x,yR∩IXx,yR∧x,yIXx,yR∧x=y，即x,xR，这与R是X上的反自反关系相矛盾。所以R∩IX=Æ。设R∩IX=Æ，下证R在X上是反自反的。任取xXx,xIX，由于R∩IX=Æ，必然x,xR，即R在X上是反自反的。【例4.12】设A=1,2,3，定义A上的二元关系如下：R=1,1,2,2,3,3,

5、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,2T，所以T不是A上的自反关系。因为1,1T，所以T不是A上的反自反关系。定义4.3.3设RX×X，(x)(y)(xX∧yX∧x,yR→y,xR)，则称R在X上是对称的。R是X上的对称关系，由定义4.3.3知，R的关系矩阵MR是对称阵。在R的关系图中，如果两个不同的结

6、点间有边，一定有方向相反的两条边。设X=1,2,3，X上的二元关系R=1,2,2,1,3,3，R是对称的。它的关系图如图4.7所示，关系矩阵如下：MR=【例4.13】设A=1,3,5,7，定义A上的二元关系如下：R=a,b

7、(a－b)/2是整数试证明R在A上是自反的和对称的。证明：aA，(a-a)/2=0，0是整数，所以a,aR。即R是自反的。aA，bA，a,bR，(a-b)/2是整数，因为整数的相反数也是整数，所以(b-a)/2=-(a-b)/2是整数，b,aR。即R是对称的。定理4.3.3设R是X上的二元关系,R是对称的当且

8、仅当R=RC。证明：设R是对称的，下证R=RC。x,yRy,xRx,yRC,所以R=RC。设R=RC，下证R是对称的。x,yRy,xRCy,xR,所以R是对称的。定义4.3.4设RX×X，(x)(y)(xX∧yX∧x,yR∧y,xR→(x=y))则称R在X上是反对称的。x,yR∧y,xR→(x=y)(x=y)→(x,yR∧y,xR)(x=y)→(x,yR∨y,xR)((x=y)∨x,yR)∨y,xR((x≠y)∧x,yR)∨y,xR(x≠y)∧x

9、,yR→y,xRx,yR∧(x≠y)→y,xR由此，反对称的定义又可以等价的描述为：(x)(y)(xX∧yX∧x,yR∧(x≠y)→y,xR)设R是X上的反对称关系，由定义4.3.4知，在R的关系矩阵MR中以主对角线为轴的对称位置上不能同时为1(主对角线除外)。在R的关系图中每两个不同的结点间不能有方向相反的两条边。设X=1,2,3，X上的二元关系R=1,2,2,3