离散数学集合论免费.ppt

文档介绍：1
自反性与反自反性
定义 设R为A上的关系, (1) 若x(x∈A→<x,x>R), 则称R在A上是自反的.(2) 若x(x∈A→<x,x>R), 则称R在A上是反自反的.
实例：
自反关系：A上的全域关系EA, 恒等关系IA
小于等于关系LA, 整除关系DA
反自反关系：实数集上的小于关系
幂集上的真包含关系
实例
例1 A={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既不是自反也不是反自反的
对称性与反对称性
定义 设R为A上的关系,  (1) 若xy(x,y∈A∧<x,y>∈R→<y,x>∈R), 则称R为A上对称的关系. (2) 若xy(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y), 则称R为A上的反对称关系.
实例：
对称关系：A上的全域关系EA, 恒等关系IA和空关系
反对称关系：恒等关系IA，空关系是A上的反对称关系.
实例
例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 不对称、也不反对称.
传递性
定义 设R为A上的关系, 若 xyz(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R),则称R是A上的传递关系.
实例：
A上的全域关系EA,恒等关系IA和空关系
小于等于关系, 小于关系，整除关系，包含关系，
真包含关系
实例
例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上的传递关系
关系性质的充要条件
设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
关系性质判别

自反
反自反
对称
反对称
传递
表达式
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 判断下图中关系的性质, 并说明理由.
(2)反自反，不是自反的；反对称，不是对称的；
是传递的.
(1)不自反也不反自反；对称, 不反对称；不传递.
(3)自反，不反自反；反对称，不是对称；不传递.