《离散数学》PPT课件：第4章 二元关系与函数（4.3-4.4）关系的性质、关系的闭包

43关系的性质 ■自反性 反自反性 ■对称性 ■反对称性 ■传递性

1 4.3 关系的性质 ◼ 自反性 ◼ 反自反性 ◼ 对称性 ◼ 反对称性 ◼ 传递性

自反性与反自反性 定义设R为A上的关系, (1)若x(x∈A→∈R,则称R在A上是自反的 (2)若vx(x∈A→gR,则称R在A上是反自反的 实例 反关系:A上的全域关系EA,恒等关系I4 小于等于关系LA整除关系D4 反自反关系:实数集上的小于关系 幂集上的真包含关系

2 自反性与反自反性 定义 设R为A上的关系, (1) 若x(x∈A→R), 则称R在A上是自反的. (2) 若x(x∈A→R), 则称R在A上是反自反的. 实例： 反关系：A上的全域关系EA, 恒等关系IA 小于等于关系LA, 整除关系DA 反自反关系：实数集上的小于关系 幂集上的真包含关系

实例 例1A=({1,2,3},R1R2,R3是A上的关系,其中 R1={,} R2={1,1>,2,2>,,1,2>} R3={ R2自反, R3反自反, R1既不是自反也不是反自反的

3 实例 例1 A={1,2,3}, R1 , R2 , R3是A上的关系, 其中 R1＝{,} R2＝{,,,} R3＝{} R2自反, R3反自反, R1既不是自反也不是反自反的

对称性与反对称性 定义设R为A上的关系, (1)若 Vxvyl,y∈A∧∈R→∈R),则称R 为A上对称的关系 (2)若 xvv(xy∈A∧∈R∧水x>∈R→x=y), 则称R为A上的反对称关系 实例: 对称关系:A上的全域关系E4恒等关系4和空 关系必 反对称关系:恒等关系I,空关系是A上的反对 称关系

4 对称性与反对称性 定义 设R为A上的关系, (1) 若xy(x,y∈A∧∈R→∈R), 则称R 为A上对称的关系. (2) 若xy(x,y∈A∧∈R∧∈R→x=y), 则称R为A上的反对称关系. 实例： 对称关系：A上的全域关系EA, 恒等关系IA和空 关系 反对称关系：恒等关系IA，空关系是A上的反对 称关系

实例 例2设4={1,2,3},R1,R2,R3和R4都是A上的关系, 其中 R1={,},R2={,1,2>,} R3={1,2>,},R4={,2,1>,1,3 R1对称、反对称 R2对称,不反对称 R3反对称,不对称 R4不对称、也不反对称

5 实例 例2 设A＝{1,2,3}, R1 , R2 , R3和R4都是A上的关系, 其中 R1＝{,}， R2＝{,,} R3＝{,}， R4＝{,,} R1 对称、反对称. R2 对称，不反对称. R3 反对称，不对称. R4 不对称、也不反对称

传递性 定义设R为A上的关系,若 Vxvy√x(x,z∈A∧xx,少>∈R∧,x∈R→∈R), 则称R是A上的传递关系 实例: A上的全域关系E恒等关系和空关系 小于等于关系,小于关系,整除关系,包含关系, 真包含关系

6 传递性 定义 设R为A上的关系, 若 xyz(x,y,z∈A∧∈R∧∈R→∈R), 则称R是A上的传递关系. 实例： A上的全域关系EA,恒等关系IA和空关系 小于等于关系, 小于关系，整除关系，包含关系， 真包含关系

实例 例3设A={1,2,3},R1R2,R3是A上的关系,其中 R1={1,1>,2,2> R2={,} R3={ R1和R3是4上的传递关系 R2不是A上的传递关系

7 实例 例3 设A＝{1,2,3}, R1 , R2 , R3是A上的关系, 其中 R1＝{,} R2＝{,} R3＝{} R1 和 R3 是A上的传递关系 R2不是A上的传递关系

关系性质的充要条件 设R为A上的关系,则 (1)R在A上自反当且仅当IR (2)R在A上反自反当且仅当R∩/= (3)R在A上对称当且仅当R=R1 (4)R在A上反对称当且仅当R∩R-cI4 (5)R在A上传递当且仅当R°RcR

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

关系性质判别 自反反自反对称 反对称传递 表达式| LSR ROI=0R=R1 R∩R1 CLI RORCR 关系主对主对角矩阵是对称若rn=1,且对MP中1 矩阵角线线元素矩阵 i,则 所在位置, 元素全是0 M中相应 全是1 位置都是1 关系图每个每个顶如果两个顶如果两点如果顶点 顶点点都没点之间有边,之间有边,x连通到 都有有环是一对方向是一条有xk,则从x 环 相反的边向边无双到x有边 (无单边)向边)

9 关系性质判别 自反 反自反 对称 反对称 传递 表达式 IAR R∩IA = R=R−1 R∩R−1 IA RRR 关系 矩阵 主对 角线 元素 全是1 主对角 线元素 全是0 矩阵是对称 矩阵 若rij ＝1, 且 i≠j, 则rji ＝ 0 对M2中1 所在位置, M中相应 位置都是1 关系图 每个 顶点 都有 环 每个顶 点都没 有环 如果两个顶 点之间有边, 是一对方向 相反的边 (无单边) 如果两点 之间有边, 是一条有 向边(无双 向边) 如果顶点 xi 连通到 xk , 则从 xi 到 xk 有边

实例 例8判断下图中关系的性质,并说明理由 (1)不自反也不反自反;对称,不反对称;不传递 (2)反自反,不是自反的;反对称,不是对称的; 是传递的 (3)自反,不反自反;反对称,不是对称;不传递 10

10 实例 例8 判断下图中关系的性质, 并说明理由. (2)反自反，不是自反的；反对称，不是对称的； 是传递的. (1)不自反也不反自反；对称, 不反对称；不传递. (3)自反，不反自反；反对称，不是对称；不传递