欢迎来到天天文库
浏览记录
ID:37921016
大小:674.31 KB
页数:22页
时间:2019-06-02
《离散数学--4.3关系的性质》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、4.3关系的性质4.3.1关系性质的定义和判别自反性与反自反性对称性与反对称性传递性4.3.2关系的闭包闭包定义闭包计算Warshall算法1自反性与反自反性定义4.14设R为A上的关系, (1)若x(x∈A→R),则称R在A上是自反的.(2)若x(x∈A→R),则称R在A上是反自反的.自反:A上的全域关系EA,恒等关系IA,小于等于关系LA,整除关系DA反自反:实数集上的小于关系、幂集上的真包含关系.R2自反,R3反自反,R1既不自反也不反自反.例1A={a,b,c},R1,R2,R3是A上的关系,其中R1={,}R2={2、a>,,,}R3={}2对称性与反对称性例2设A={a,b,c},R1,R2,R3和R4都是A上的关系,其中R1={,},R2={,,}R3={,},R4={,,}定义4.15设R为A上的关系, (1)若xy(x,y∈A∧∈R→∈R),则称R为A上对称的关系.(2)若xy(x,y∈A∧∈R∧∈R→x=y),则称R为A上的反对称关系.实例对称:A上的全域关系EA,恒等关系IA和空关系反对称3、:恒等关系IA,空关系是A上的反对称关系R1对称、反对称.R2对称,不反对称.R3反对称,不对称.R4不对称、也不反对称3传递性例3设A={a,b,c},R1,R2,R3是A上的关系,其中R1={,}R2={,}R3={}定义4.16设R为A上的关系,若xyz(x,y,z∈A∧∈R∧∈R→∈R),则称R是A上的传递关系.实例:A上的全域关系EA,恒等关系IA和空关系,小于等于关系,小于关系,整除关系,包含关系,真包含关系R1和R3是A上的传递关系,R2不是A上的传递关系.4关系性质的充4、要条件设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当R∩R1IA(5)R在A上传递当且仅当R∘RR5自反性证明证明模式证明R在A上自反任取x,xA………………..….…….R前提推理过程结论例4证明若IAR,则R在A上自反.证任取x,xAIAR因此R在A上是自反的.6对称性证明证明模式证明R在A上对称任取R……………..….…….R前提推理过程结论例5证明若R=R1,则R在A上对称.5、证任取RR1R因此R在A上是对称的.7反对称性证明证明模式证明R在A上反对称任取RR………..……….x=y前提推理过程结论例6证明若R∩R1IA,则R在A上反对称.证任取RRRR1R∩R1IAx=y因此R在A上是反对称的.8传递性证明证明模式证明R在A上传递任取,RR…..……….R前提推理过程结论例7证明若R∘RR,则R在A6、上传递.证任取,RRR∘RR因此R在A上是传递的.9关系性质判别自反性反自反性对称性反对称性传递性表达式IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij=1,且i≠j,则rji=0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,一定是一对方向相反的边(无单边)如果两点之间有边,一定是一条有向边(无双向边)如果顶点xi到xj有边,xj到xk有边,则从xi到xk也有边10实例例8判断下图中关系的性质,7、并说明理由(3)自反,不是反自反;反对称,不是对称;不传递.(1)(2)(3)(1)不自反也不反自反;对称,不反对称;不传递.(2)反自反,不是自反;反对称,不是对称;传递.11运算与性质的关系自反性反自反性对称性反对称性传递性R11√√√√√R1∩R2√√√√√R1∪R2√√√××R1R2×√√√×R1∘R2√××××12闭包定义定义4.17设R是非空集合A上的关系,R的自反(对称或传递)闭
2、a>,,,}R3={}2对称性与反对称性例2设A={a,b,c},R1,R2,R3和R4都是A上的关系,其中R1={,},R2={,,}R3={,},R4={,,}定义4.15设R为A上的关系, (1)若xy(x,y∈A∧∈R→∈R),则称R为A上对称的关系.(2)若xy(x,y∈A∧∈R∧∈R→x=y),则称R为A上的反对称关系.实例对称:A上的全域关系EA,恒等关系IA和空关系反对称
3、:恒等关系IA,空关系是A上的反对称关系R1对称、反对称.R2对称,不反对称.R3反对称,不对称.R4不对称、也不反对称3传递性例3设A={a,b,c},R1,R2,R3是A上的关系,其中R1={,}R2={,}R3={}定义4.16设R为A上的关系,若xyz(x,y,z∈A∧∈R∧∈R→∈R),则称R是A上的传递关系.实例:A上的全域关系EA,恒等关系IA和空关系,小于等于关系,小于关系,整除关系,包含关系,真包含关系R1和R3是A上的传递关系,R2不是A上的传递关系.4关系性质的充
4、要条件设R为A上的关系,则(1)R在A上自反当且仅当IAR(2)R在A上反自反当且仅当R∩IA=(3)R在A上对称当且仅当R=R1(4)R在A上反对称当且仅当R∩R1IA(5)R在A上传递当且仅当R∘RR5自反性证明证明模式证明R在A上自反任取x,xA………………..….…….R前提推理过程结论例4证明若IAR,则R在A上自反.证任取x,xAIAR因此R在A上是自反的.6对称性证明证明模式证明R在A上对称任取R……………..….…….R前提推理过程结论例5证明若R=R1,则R在A上对称.
5、证任取RR1R因此R在A上是对称的.7反对称性证明证明模式证明R在A上反对称任取RR………..……….x=y前提推理过程结论例6证明若R∩R1IA,则R在A上反对称.证任取RRRR1R∩R1IAx=y因此R在A上是反对称的.8传递性证明证明模式证明R在A上传递任取,RR…..……….R前提推理过程结论例7证明若R∘RR,则R在A
6、上传递.证任取,RRR∘RR因此R在A上是传递的.9关系性质判别自反性反自反性对称性反对称性传递性表达式IARR∩IA=R=R1R∩R1IARRR关系矩阵主对角线元素全是1主对角线元素全是0矩阵是对称矩阵若rij=1,且i≠j,则rji=0对M2中1所在位置,M中相应位置都是1关系图每个顶点都有环每个顶点都没有环如果两个顶点之间有边,一定是一对方向相反的边(无单边)如果两点之间有边,一定是一条有向边(无双向边)如果顶点xi到xj有边,xj到xk有边,则从xi到xk也有边10实例例8判断下图中关系的性质,
7、并说明理由(3)自反,不是反自反;反对称,不是对称;不传递.(1)(2)(3)(1)不自反也不反自反;对称,不反对称;不传递.(2)反自反,不是自反;反对称,不是对称;传递.11运算与性质的关系自反性反自反性对称性反对称性传递性R11√√√√√R1∩R2√√√√√R1∪R2√√√××R1R2×√√√×R1∘R2√××××12闭包定义定义4.17设R是非空集合A上的关系,R的自反(对称或传递)闭
此文档下载收益归作者所有