离散数学 关系的性质

14.3关系的性质自反性反自反性对称性反对称性传递性2自反反自反对称反对称传递定义x∈A,有x,xR),x∈A,有x,xR,若x,y∈R有y,x∈R),若x,y∈R且xy,则y,xR若x,y∈Ry,z∈R，则x,z∈R),表达式IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边)如果两点之间有边,是一条有向边(无双向边)如果顶点xi连通到xk,则从xi到xk有边3自反性与反自反性例：自反关系：A上的全域关系EA,恒等关系IA小于等于关系LA,整除关系DA反自反关系：实数集上的小于关系幂集上的真包含关系4实例例1A={1,2,3},R1,R2,R3是A上的关系,其中R1＝{1,1,2,2}R2＝{1,1,2,2,3,3,1,2}R3＝{1,3}R2自反,R3反自反,R1既不是自反也不是反自反的5对称性与反对称性实例：对称关系：A上的全域关系EA,恒等关系IA和空关系反对称关系：恒等关系IA，空关系是A上的反对称关系.6实例例2设A＝{1,2,3},R1,R2,R3和R4都是A上的关系,其中R1＝{1,1,2,2}，R2＝{1,1,1,2,2,1}R3＝{1,2,1,3}，R4＝{1,2,2,1,1,3}R1对称、反对称.R2对称，不反对称.R3反对称，不对称.R4不对称、也不反对称.7传递性实例：A上的全域关系EA,恒等关系IA和空关系小于等于关系,小于关系，整除关系，包含关系，真包含关系8实例例3设A＝{1,2,3},R1,R2,R3是A上的关系,其中R1＝{1,1,2,2}R2＝{1,2,2,3}R3＝{1,3}R1和R3是A上的传递关系R2不是A上的传递关系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R10实例例.判断下图中关系的性质,并说明理由.(2)反自反，不是自反的；反对称，不是对称的；是传递的.(1)不自反也不反自反；对称,不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递.11自反性证明证明模式证明R在A上自反任取x,xA……………..….…….x,xR前提推理过程结论例4证明若IAR，则R在A上自反.证任取x,xAx,xIAx,xR因此R在A上是自反的.12对称性证明证明模式证明R在A上对称任取x,yx,yR……………..….…….y,xR前提推理过程结论例5证明若R=R1,则R在A上对称.证任取x,yx,yRy,xR1y,xR因此R在A上是对称的.13反对称性证明证明模式证明R在A上反对称任取x,yx,yRy,xR………..……….x=y前提推理过程结论例6证明若R∩R1IA,则R在A上反对称.证任取x,yx,yRy,xRx,yRx,yR1x,yR∩R1x,yIAx=y因此R在A上是反对称的.14传递性证明证明模式证明R在A上传递任取x,y，y,zx,yRy,zR…..……….x,zR前提推理过程结论例7证明若RRR,则R在A上传递.证任取x,y，y,zx,yRy,zRx,zRRx,zR因此R在A上是传递的.15运算与性质的关系自反性反自反性对称性反对称性传递性R11√√√√√R1∩R2√√√√√R1∪R2√√√××R1R2×√√√×R1∘R2√××××164.4关系的闭包闭包定义闭包的构造方法集合表示矩阵表示图表示闭包的性质17闭包定义定义设R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R,使得R满足以下条件：（1）R是自反的（对称的或传递的）（2）RR（3）对A上任何包含R的自反（对称或传递）关系R有RR.一般将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).18闭包的构造方法定理1设R为A上的关系,则有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…说明：•对于有穷集合A(|A|=n)上的关系,(3)中的并是有限的.•若R是自反的，则r(R)=R;若R是对称的，则s(R)=R;若R是传递的，则t(R)=R.19（3）t(R)＝R∪R2∪R3∪…先证R∪R2∪…t(R)成立，为此只需证明对任意的正整数n有Rnt(R)即可。用归纳法。n＝1时，有R1＝Rt(R)。假设Rnt(R)成立，那么对任意的x,y有x,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)（因为t(R)是传递的）这就证明了Rn+1t(R)。由归纳法命题得证。20再证t(R)R∪R2∪…成立，为此只须证明R∪R2∪…是传递的。任取x,y,y,z，则y,z∈R∪R2∪…∧x,y∈R∪R2∪…t(y,z∈Rt)∧s(x,y∈Rs)ts(y,z∈Rt∧x,y∈Rs)ts(x,z∈RtRs)ts(x,z∈Rt+s)x,z∈R∪R2∪…从而证明了R∪R2∪…是传递的。21推论设R为有穷集A上的关系，则存在正整数r使得t(R)=R∪R2∪…∪Rr22闭包的构造方法（续）设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则Mr=M+EMs=M+M’Mt=M+M2+M3+…E是和M同阶的单位矩阵,M’是M的转置矩阵.注意在上述等式中矩阵的元素相加时使用逻辑加.23闭包的构造方法（续）设关系R,r(R),r(R),s(R),t(R)的关系图分别记为G,Gr,Gs,Gt,则Gr,Gs,Gt的顶点集与G的顶点集相等.除了G的边以外,以下述方法添加新边：(1)考察G的每个顶点,如果没有环就加上一个环，最终得到Gr.(2)考察G的每条边,如果有一条xi到xj的单向边,i≠j,则在G中加一条xj到xi的反方向边，最终得到Gs.(3)考察G的每个顶点xi,找从xi出发的每一条长度不超过n的路径，如果从xi到路径中任何结点xj没有边，就加上这条边.当检查完所有的顶点后就得到图Gt.24实例例1设A={a,b,c,d},R={a,b,b,a,b,c,c,d,d,b},R和r(R),s(R),t(R)的关系图如下图所示.Rr(R)s(R)t(R)25R={a,b,b,a,b,c,c,d,d,b},r(R)=R∪R0={a,b,b,a,b,c,c,d,d,b}∪{a,a,b,b,c,c,d,d}={a,b,b,a,b,c,c,d,d,b,a,a,b,b,c,c,d,d}s(R)=R∪R1={a,b,b,a,b,c,c,d,d,b}∪{b,a,a,b,c,b,d,c,b,d}}={a,b,b,a,b,c,c,d,d,b,c,b,d,c,b,d}t(R)=R1∪R2∪R3∪R4={a,b,b,a,b,c,c,d,d,b}∪{a,a,a,c,b,b,b,d,c,b,d,a,d,c}∪{a,b,a,d,b,a,b,b,b,c,c,a,c,c,d,b,d,d}∪{a,a,a,b,a,c,,b,a,b,b,b,c,b,d,c,b,c,d,d,a,d,b,d,c}={a,a,a,b,a,c,a,d,b,a,b,b,b,c,b,d,c,a,c,b,c,c,c,d,d,a,d,b,d,c,d,d}26Mr=Ms=Mt=0100100011001010010011100001001000110100000101010100010001001010100110110001010001010100001001100100101001011110111110100101111011111111000101001010010111110100101001011110111127定理7.11设R是非空集合A上的关系，则（1）R是自反的当且仅当r(R)＝R。（2）R是对称的当且仅当s(R)＝R。（3）R是传递的当且仅当t(R)＝R。