第4章二元关系(二).

第4章二元关系第4章二元关系4.1二元关系及其表示4.2关系的运算4.3关系的性质4.4关系的闭包运算4.5等价关系4.6相容关系第4章二元关系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=100010011第4章二元关系定理4.3.1设R是X上的二元关系，R是自反的当且仅当IXR。证明：设R在X上是自反的，下证IXR。x,yIX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所示，关系矩阵如下：第4章二元关系MR=001100010【例4.11】设R是实数集合，＞=x,y|xR∧yR∧x＞y是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。证明：xR，x≯x，x,x＞，所以＞是反自反的。第4章二元关系定理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章二元关系【例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,2T，所以T不是A上的自反关系。因为1,1T，所以T不是A上的反自反关系。第4章二元关系定义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的关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。设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|(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是对称的当且仅当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章二元关系定义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,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)第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上的二元关系如下：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元素，而1≠2，所以S不是A上的反对称关系。因为1,2T，而2,1T，所以T不是A上的对称关系。T是A上的反对称关系。U不是A上的对称关系，也不是A上的反对称关系。第4章二元关系定理4.3.4设R是X上的二元关系，则R是反对称的当且仅当R∩RCIX。证明：设R是反对称的，下证R∩RCIX。x,yR∩RCx,yR∧x,yRCx,yR∧y,xR因为R是反对称的，所以y=x，x,y=x,x=y,yIX，故R∩RCIX设R∩RCIX，下证R是反对称的。x,yR∧y,xRx,yR∧x,yRCx,yR∩RC因为R∩RCIX，所以x,yIX，故x=y，R是反对称的。定义4.3.5设RX×X，(x)(y)(z)(xX∧yX∧zX∧x,yR∧y,zR→x,zR)则称R在X上是传递的。第4章二元关系【例4.15】设R是实数集合，S=x,y|xR∧yR∧x=y是实数集合上的等于关系。证明实数集合上的等于关系是传递的。证明：xR，yR，zR，x,yS且y,zS，由S的定义有x=y和y=z，由实数相等的概念得x=z。再根据S的定义，x,zS。故实数集合上的等于关系S是传递的。定理4.3.5设R是X上的二元关系，R是传递的当且仅当R∘RR。证明：设R是传递的，下证R∘RR。x,yR∘R，zX,使得x,zR且z,yR，又因为R是传递的，所以x,yR，这就证明了R∘RR。设R∘RR，下证R是传递的。x,yR且y,zR，由复合关系的定义得x,zR∘R，因为R∘RR，所以x,zR，所以R是传递的。第4章二元关系上述的5个定理，可以作为相应概念的定义使用，用来判断和证明关系的性质。有些问题用这5个定理处理是非常方便的。请看下面的例题。【例4.16】设R，S是X上的二元关系，证明⑴若R，S是自反的，则R∪S和R∩S也是自反的。⑵若R，S是对称的，则R∪S和R∩S也是对称的。⑶若R，S是传递的，则R∩S也是传递的。证明：⑴设R，S是自反的，由定理4.3.1知，IXR，IXS，所以IXR∪S，IXR∩S，再由定理4.3.1知，R∪S和R∩S也是自反的。第4章二元关系⑵设R，S是对称的，由定理4.3.3知，R=RC，S=SC，根据定理4.2.8，R∪S=RC∪SC=(R∪S)C，R∩S=RC∩SC=(R∩S)C，再由定理4.3.3知，R∪S和R∩S也是对称的。⑶设R，S是传递的，由定理4.3.5知，R∘RR，S∘SS，据定理4.2.4，(R∩S)∘(R∩S)(R∘R)∩(R∘S)∩(S∘R)∩(S∘S)(R∘R)∩(S∘S)R∩S即(R∩S)∘(R∩S)R∩S，再由定理4.3.5，R∩S是传递的。以上研究了二元关系的5个性质及其关系矩阵、关系图的特点，它们对今后的学习是重要的。第4章二元关系4.4关系的闭包运算定义4.4.1设RX×X，X上的二元关系R′满足：⑴R′是自反的(对称的，传递的)。⑵RR′。⑶对X上的任意二元关系R′′，如果RR′′且R′′是自反的(对称的，传递的)，就有R′R′′。则称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是自反(对称，传递)的时，求R的自反(对称，传递)闭包方法由下面的定理给出了。定理4.4.1设RX×X，则⑴R是自反的当且仅当r(R)=R。⑵R是对称的当且仅当s(R)=R。⑶R是传递的当且仅当t(R)=R。证明：仅证明⑴，其余留做练习。设R是自反的，下证r(R)=R令R′=R①R′=R，R是自反的，所以R′是自反的。②因为R′=R，所以RR′。③R′′是X上的任意自反关系且RR′′，因为R′=R，所以R′R′′。故R′是R的自反闭包。即r(R)=R。第4章二元关系设r(R)=R，下证R是自反的。由自反闭包的定义知，R是自反的。以下的几个定理给出了求二元关系R的自反闭包、对称闭包和传递闭包的一般方法。定理4.4.2设RX×X，则r(R)=R∪IX证明：令R′=R∪IX⑴IXR∪IX，而R∪IX=R′，所以IXR′，R′是自反的。⑵RR∪IX，而R∪IX=R′，所以RR′⑶R′′是X上的任意自反关系且RR′′，由于R′′是自反的，所以IXR′′，从而有R′=R∪IXR′′。根据自反闭包的定义，R′=R∪IX是R的自反闭包，即r(R)=R∪IX。第4章二元关系定理4.4.3设RX×X，则s(R)=R∪RC证明：令R′=R∪RC⑴(R′)C=(R∪RC)C=RC∪(RC)C=RC∪R=R∪RC=R′，所以R′是对称的。⑵RR∪RC，而R∪RC=R′，所以RR′。⑶R′′是X上的任意对称关系且RR′′，x,yRCy,xRy,xR′′x,yR′′(R′′是对称的)，所以RCR′′，从而有R′=R∪RCR′′。R′是R的对称闭包，即s(R)=R∪RC。定理4.4.4设RX×X，则t(R)=R∪R2∪R3∪…证明：先证R∪R2∪R3∪…t(R)用数学归纳法证明：iI+\Rit(R)第4章二元关系①当i=1时，由传递闭包的定义，R1=Rt(R)。②设i=n时，Rnt(R)。下证Rn+1t(R)。x,yRn+1(c)(x,cRn∧c,yR)(c)(x,ct(R)∧c,yt(R))(①和归纳假设)x,yt(R)(t(R)是传递的)即Rn+1t(R)故R∪R2∪R3∪…t(R)再证t(R)R∪R2∪R3∪…显然RR∪R2∪R3∪…以下证明R∪R2∪R3∪…是传递的。x,y