离散数学关系的性质.ppt

《离散数学关系的性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、14.3关系的性质自反性反自反性对称性反对称性传递性2自反反自反对称反对称传递定义x∈A,有R),x∈A,有R,若∈R有∈R),若∈R且xy,则R若∈R∈R，则∈R),表达式IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij＝1,且i≠j,则rji＝0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,是一对方向相反的边(无单边

2、)如果两点之间有边,是一条有向边(无双向边)如果顶点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和空关系反对称

3、关系：恒等关系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

4、,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)自反，不反自反；反对称，不是对称；不

5、传递.11自反性证明证明模式证明R在A上自反任取x,xA……………..….…….R前提推理过程结论例4证明若IAR，则R在A上自反.证任取x,xAIAR因此R在A上是自反的.12对称性证明证明模式证明R在A上对称任取R……………..….…….R前提推理过程结论例5证明若R=R1,则R在A上对称.证任取RR1R因此R在A上是对称的.13反对称性证明证明模式证明R在A上反对称任取

6、y>RR………..……….x=y前提推理过程结论例6证明若R∩R1IA,则R在A上反对称.证任取RRRR1R∩R1IAx=y因此R在A上是反对称的.14传递性证明证明模式证明R在A上传递任取，RR…..……….R前提推理过程结论例7证明若RRR,则R在A上传递.证任取，RRRR

7、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(

8、R).18闭包的构造方法定理1设R为A上的关系,则有(1)r(R)=R∪R0(2)s(R)=R∪R1(3)t(R)=R∪R2∪R3∪…说明：