离散数学关系的性质.pptVIP

1第1页，共27页，星期日，2025年，2月5日

自反反自反对称反对称传递定义?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有边第2页，共27页，星期日，2025年，2月5日

自反性与反自反性例：自反关系：A上的全域关系EA,恒等关系IA小于等于关系LA,整除关系DA反自反关系：实数集上的小于关系幂集上的真包含关系

第3页，共27页，星期日，2025年，2月5日

实例例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既不是自反也不是反自反的第4页，共27页，星期日，2025年，2月5日

对称性与反对称性实例：对称关系：A上的全域关系EA,恒等关系IA和空关系?反对称关系：恒等关系IA，空关系是A上的反对称关系.

第5页，共27页，星期日，2025年，2月5日

实例例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不对称、也不反对称.第6页，共27页，星期日，2025年，2月5日

传递性实例：A上的全域关系EA,恒等关系IA和空关系?小于等于关系,小于关系，整除关系，包含关系，真包含关系

第7页，共27页，星期日，2025年，2月5日

实例例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上的传递关系第8页，共27页，星期日，2025年，2月5日

关系性质的充要条件设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

第9页，共27页，星期日，2025年，2月5日

实例例.判断下图中关系的性质,并说明理由.(2)反自反，不是自反的；反对称，不是对称的；是传递的.(1)不自反也不反自反；对称,不反对称；不传递.(3)自反，不反自反；反对称，不是对称；不传递.第10页，共27页，星期日，2025年，2月5日

自反性证明证明模式证明R在A上自反任取x,x?A?……………..….…….?x,x?R前提推理过程结论例4证明若IA?R，则R在A上自反.证任取x,

x?A?x,x?IA?x,x?R

因此R在A上是自反的.第11页，共27页，星期日，2025年，2月5日

对称性证明证明模式证明R在A上对称任取x,yx,y?R?……………..….…….?y,x?R前提推理过程结论例5证明若R=R?1,则R在A上对称.证任取x,y

x,y?R?y,x?R?1?y,x?R

因此R在A上是对称的.

第12页，共27页，星期日，2025年，2月5日

反对称性证明证明模式证明R在A上反对称任取x,yx,y?R?y,x?R?………..……….?x=y