第四章 二元关系-2nd-zhou

第四章二元关系2/452/45回顾•关系的定义和性质•关系的表示方法–关系图–关系矩阵•关系的运算–关系的合成–关系合成的规则–关系的幂4.3关系的性质定义：设R为A上的二元关系(1)若对每个，皆有，则称R为自反的。用式子来表述即是：R是自反的xA,xxR(x)(xA,R)xx(2)若对每个，皆有，则称R为反自反的。用式子来表述即是：R是反自反的xA,xxR(x)(xA,R)xx关系的性质(3)对任意的，若，则，就称R为对称的。用式子来表述即是：R是对称的,xyA()()(,,,)xyxyAxyRyxR,xyR,yxR(4)对任意的，若且，则x=y，就称R为反对称的。用式子来表述即是：R是反对称的,xyA,xyR,yxR()()(,,,)xyxyAxyRyxRxy关系的性质,yzR(5)对任意的，若且，则，就称R为可传递的。用式子来表述即是：R是可传递的,,xyzA,xyR,xzR()()()(,,,,,)xyzxyzAxyRyzRxzR(6)存在，并且而，就称R为不可传递的。用式子来表述即是：R是不可传递的,,xyzA,,xyRyzR,xzR()()()(,,,)xyzxyRyzRxzR关系的性质例1：考虑自然数集合上的普通相等关系“=”，大于关系“”和大于等于关系“”具有的性质。解：(1)“=”关系是自反的、对称的、反对称的、可传递的；(2)“”关系是反自反的、反对称的、可传递的；(3)“”关系是自反的、反对称的、可传递的。例2：空集上的二元关系的性质。自反的、对称的、反对称的、反自反的、可传递的区分概念：空关系vs空集上的关系空关系：对于任何集合A,称空集为A上的空关系.性质：若A非空，空关系是反自反的，对称的，反对称的，可传递的；若A是空集，该空关系是自反的，反自反的，对称的，反对称的，可传递的空集上的关系：自反的，反自反的，对称的，反对称的，可传递的。在空集上可定义任意元关系。关系性质成立的充要条件定理7.9设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当R∩R1IA(5)R在A上传递当且仅当RRR证明证明只证(1)、(3)、(4)、(5)(1)必要性任取x,y,由于R在A上自反必有x,y∈IAx,y∈A∧x=yx,y∈R从而证明了IAR充分性.任取x,有x∈Ax,x∈IAx,x∈R因此R在A上是自反的.证明(3)必要性.任取x,y,x,y∈Ry,x∈Rx,y∈R1所以R=R1充分性.任取x,y,由R=R1得x,y∈Ry,x∈R1y,x∈R所以R在A上是对称的证明(4)必要性.任取x,y,有x,y∈R∩R1x,y∈R∧x,y∈R1x,y∈R∧y,x∈Rx=yx,yAx,y∈IA这就证明了R∩R1IA充分性.任取x,y,x,y∈R∧y,x∈Rx,y∈R∧x,y∈R1x,y∈R∩R1x,y∈IAx=y从而证明了R在A上是反对称的.证明(5)必要性.任取x,y有x,y∈RRt(x,t∈R∧t,y∈R)x,y∈R所以RRR充分性.任取x,y,y,z∈R,则x,y∈R∧y,z∈Rx,z∈RRx,z∈R所以R在A上是传递的自反性反自反性对称性反对称性传递性集合IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0M2中1位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环两点之间有边,是一对方向相反的边两点之间有边,是一条有向边点xi到xj有边,xj到xk有边,则xi到xk也有边关系性质的三种等价条件自反性反自反性对称性反对称性传递性R11√√√√√R1∩R2√√√√√R1∪R2√√√××R1R2×√√√×R1R2√××××关系的性质和运算之间的联系15/4515/45四、关系的闭包运算闭包的定义：给定集合X，R是X中的二元关系。如果有另一个关系满足R（1）是自反的(对称的、可传递的)；（2）（3）对于任何自反的(对称的、可传递的)关系，如果，则RRRRRRRR则称关系为R的自反的(对称的，可传递的)闭包。并用r(R)表示的R自反闭包，用s(R)表示R的对称闭包，用t(R)表示R的可传递闭包。R16/4516/45四、关系的闭包运算定理：给定集合X，R是X中的关系。于是可有(a)当且仅当，R才是自反的。(b)当且仅当，R才是对称的。(c)当且仅当，R才是传递的。()sRR()tRR证明：仅给出（a）的证明过程由闭包的定义可知，又由于R是包含了R的自反关系，根据自反闭包的定义有。因此有。反之，如果，则由自反闭包定义可知R是自反的。()RrR()rRR()rRR()rRR17/4517/45四、关系的闭包运算定理：设R为A上的关系,则有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…说明：对有穷集A(|A|=n)上的关系,(3)中的并最多不超过Rn证只证(1)和(3).(1)由IA=R0R∪R0知R∪R0是自反的,且满足RR∪R0设R是A上包含R的自反关系,则有RR和IAR.从而有R∪R0R.R∪R0满足闭包定义,所以r(R)=R∪R0.18/4518/45四、关系的闭包运算(3)先证R∪R2∪…t(R)成立.用归纳法证明对任意正整数n有Rnt(R).n=1时有R1=Rt(R).假设Rnt(R)成立,那么对任意的x,yx,y∈Rn+1=RnRt(x,t∈Rn∧t,y∈R)t(x,t∈t(R)∧t,y∈t(R))x,y∈t(R)这就证明了Rn+1t(R).由归纳法命题得证.再证t(R)R∪R2∪…成立,为此只须证明R∪R2∪…传递.任取x,y,y,z,则x,y∈R∪R2∪…∧y,z∈R∪R2∪…t(x,y∈Rt)∧s(y,z∈Rs)ts(x,z∈RtRs)ts(x,z∈Rt+s)x,z∈R∪R2∪…从而证明了R∪R2∪…是传递的.19/4519/45四、关系的闭包运算在整数集合中，小于关系“”的自反闭包是“≤”；恒等关系IX的自反闭包是IX。不等关系“≠”的自反闭包是全域关系；空关系的自反闭包是恒等关系。在整数集合中，小于关系“”的对称闭包是不等关系“≠”；小于或等于关系“≤”的对称闭包是全域关系；恒等关系IX的对称闭包是IX；不等关系“≠”的对称闭包是不等关系“≠”。20/4520/45四、关系的闭包运算例：给定集合X={a,b,c}，R和S是X中的关系，给定{,,,,,}{,,,,,}RabaccbSabbcca试求出t(R),t(S)，并画出关系图解：123()tRRRRR123123(){,,,,,,,,,,,,,,,,,}tSSSSSSSabbccaacbacbaabbccabcabcabcR,t(R)St(S)21/4521/45四、关系的闭包运算定理：设X是集合，R是X中的二元关系，于是有（1）如果R是自反的，那么s(R),t(R)也是自反的；（2）如果R是对称的，那么r(R),t(R)也是对称的；（3）如果R是可传递的，那么r(R)也是可传递的。xX证明（1）：若R是自反的，则对于所有的都有1,,()xxRxxRRsR1,,()iixxRxxRtR即s(R),t(R)是自反的22/45四、关系的闭包运算23/45四、关系的闭包运算证明（3）：24/4524/45四、关系的闭包运算定理：设X是集合，R是集合中的二元关系，于是有()()()()()()()()()arsRsrRbrtRtrRctsRstR证明：11111()()()()()()()XXXXXXasrRsRIRIRIRIRIRRIrRRrsR25/4525/45四、关系的闭包运算证明（b）：因为，，而对于所有的有，以及。根据这些关系式，可有()()XtrRtRI()()XrtRtRInNnXXIIXXIRRIR1()nniXXiRIIR于是12323()()()()()()()()iXXiXXXXXtrRtRIRIRIRIRIIRRRItRrtR26/4526/45四、关系的闭包运算证明（c）：如果，则，12RR12()()sRsR12()()tRtR根据对称闭包的定义，有。首先构成上式两侧的可传递闭包，再依次构成两侧的对称闭包,可以求得以及。而ts(R)是对称的，所以，从而有。()sRR()()tsRtR()()stsRstR()()ssRtstR()()tsRstR27/4527/45四、关系的闭包运算注意：（1）通常用R+表示R的可传递闭包t(R)，并读作“R加”。（2）通常用R*表示R的自反可传递闭包tr(R)，并读作“R星”。作业•88页2,5（1，3，5，6，7）•89页9,11,12,13（2，3）•90页18,21,22（1，3，5，7，9，11）•91页25,26,27