离散数学关系的性质PPT课件.ppt

1 4 3关系的性质 关系的性质及特点关系性质的充要条件关系性质的证明运算和性质的关系 1 2 1 自反的二元关系 1 定义 R是 上的二元关系 若 x x A R 则称R在A上是自反的二元关系 例如 a b c R a a b b c c a b 则 是自反的 又如 1 2 3 R是 上的整除关系 显然 是自反的 因为 1 1 2 2 3 3 都属于R 即如果对于 中的每一个元素a 都有 a a R 则称 为自反的二元关系 一 关系的性质及特点 2 3 注意 在关系的自反性定义中 要求对于A中的每一个元素a都有 a a R 所以当A a b c 而R a a b b 时 R并不是自反的 因为 c c R 又如A 1 2 3 R是A上的二元关系 当a b A 且a和b都是素数时 a b R 可见 2 2 3 3 2 3 3 2 也不是自反关系 因为 1 1 R 3 4 2 关系矩阵的特点 关系矩阵中主对角线上的元素全为1 3 关系图的特点 关系图中每个顶点都有环 实例 A上的全域关系EA 恒等关系IA 小于等于关系LA 整除关系DA都是自反关系 4 5 2 反自反的二元关系 1 定义 R是 上的二元关系 若 x x A R 则称R在A上是反自反的二元关系 例如 a b c R a b b c b a 则 是反自反的 又如 1 2 3 R是 上的小于关系 即当a b时 a b R 显然 是反自反的 注意 非自反的二元关系不一定是反自反的二元关系 因为存在着这样的二元关系 它既不是自反的又不是反自反的 如 a b c R a a a b 那么 不是自反的 因为 b b c c 都不属于 也不是反自反的 因为 a a R 即对于 中的每一个元素a 都有 a a R 则称 为反自反的二元关系 5 6 实例 实数集上的小于关系 空关系 幂集上的真包含关系都是反自反关系 2 关系矩阵的特点 关系矩阵中主对角线上的元素全为0 3 关系图的特点 关系图中每个顶点都没有环 6 7 例1A 1 2 3 R1 R2 R3是A上的关系 其中 R1 R2 R3 R1既不是自反也不是反自反的 R2为自反关系 R3为反自反关系 7 8 3 对称的二元关系 1 定义 R是 上的二元关系 若 x y x y A R R 则称R为A上对称的二元关系 例如 a b c d R a a a b b a b d d b 则 是对称的二元关系 又如 1 2 3 4 5 对于 中元素a和b 如果a b是模3同余关系 则 a b 易见 是对称关系 即如果 a b R 就一定有 b a R 则称 为对称的二元关系 8 9 实例 A上的全域关系EA 恒等关系IA和空关系 都是对称关系 2 关系矩阵的特点 关系矩阵为对称矩阵 3 关系图的特点 关系图中如果两个顶点之间有边一定是一对方向相反的边 9 10 4 反对称的二元关系 即R是 上的二元关系 每当有 a b 和有 b a 时 必有a b 则称 是反对称的二元关系 反对称的定义也可写为 是 上的二元关系 当a b时 如果 a b 则必有 b a R 称 为反对称的二元关系 例如 1 2 3 R是 上的小于关系 即a b a b 易见 1 2 1 3 2 3 所以 是反对称的 又如 是一些整数组成的集合 如果a整除b 则 a b R也是反对称的 1 定义 若 x y x y A R R x y 则称R为A上的反对称关系 10 11 注意 对称的 和 反对称的 这两个概念并非相互对立 相互排斥的 存在着既不是对称的又不是反对称的二元关系 也存在着既是对称的又是反对称的二元关系 又如A a b c R a a 可知 是对称的 又是反对称的 因为虽有 a b R b a R 但 c d R时 d c R 因此R不是对称的 例如A a b c d R a b b a c d 这里R既不是对称的 也不是反对称的 因为有 a b R和 b a R 因此R不是反对称的 11 12 实例 恒等关系IA 空关系 都是A上的反对称关系 2 关系矩阵的特点 关系矩阵中以主对角线对称的元素不能同时为1 3 关系图的特点 关系图中如果两个顶点之间有边一定是一条有向边 12 13 例2设A 1 2 3 R1 R2 R3和R4都是A上的关系 其中R1 R2 R3 R4 R1对称 反对称 R2对称 不反对称 R3反对称 不对称 R4不对称 也不反对称 13 14 5 可传递的二元关系 1 定义 R是A上的二元关系 x y z x y z A R R R 则称R是A上的传递关系 例如整除关系是可传递的 因为每当 a b R时 即a能整除b b能整除c时 显然a能整除c 所以必有 a c R 又如A a b c d e 其中a b c d e分别是表示5个人 且a b c同住一个房间 d和e同住另一个房间 如果同住一房间的人认为是相关的 显然这种同房间关系是可传递的 每当有 a b R和 b c R时 必有 a c R 则称为可传递的二元关系 14 15 实例 A上的全域关系EA 恒等关系IA和空关系 小于等于关系 小于关系 整除关系 包含关系 真包含关系都是传递的二元关系 2 关系矩阵的特点 3 关系图的特点 关系图中如果两个顶点xi到xj之间有边 xj到xk之间有边 则从xi到xk之间有边 15 16 关系性质判别汇总 16 例3设A 1 2 3 R1 R2是A上的关系 其中 R1 R2 R1是A上的传递关系R2不是A上的传递关系 17 18 例4判断下图中关系的性质 并说明理由 2 反自反 不是自反的 反对称 不是对称的 1 不自反也不反自反 对称 不反对称 不传递 3 自反 不反自反 反对称 不是对称 不传递 18 19 二 关系性质的充要条件 设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 19 20 1 自反性证明 证明模式证明R在A上自反任取x x A R前提推理过程结论 例5证明若IA R 则R在A上自反 三 关系类型的证明 证任取x x A IA R因此R在A上是自反的 20 21 2 对称性证明 证明模式证明R在A上对称任取 R R前提推理过程结论 例6证明若R R 1 则R在A上对称 证任取 R R 1 R因此R在A上是对称的 21 22 3 反对称性证明 证明模式证明R在A上反对称任取 R R x y前提推理过程结论 例7证明若R R 1 IA 则R在A上反对称 证任取 R R R R 1 R R 1 IA x y因此R在A上是反对称的 22 23 4 传递性证明 证明模式证明R在A上传递任取 R R R前提推理过程结论 例8证明若R R R 则R在A上传递 证任取 R R R R R因此R在A上是传递的 23 思考1 设A a b c R是A上的二元关系且R a a b b a c c a 问R是自反的吗 是反自反的吗 是对称的吗 是反对称的吗 是可传递的吗 解 由于c R 但 c c R 所以R不是自反关系 又由于 c a R a c R 但 c c R 所以R不是传递关系 显然R是对称关系 R不是反对称关系 由于 a a R b b R 所以R也不是反自反关系 24 思考2 设A a b 写出 1 A上所有的自反关系 2 A上所有的反自反关系 3 A上所有的对称关系 4 A上所有的反对称关系 解 1 由于A A a a b b a b b a 而A上的自反关系必须含有 a a b b 所以A上的自反关系共有4种 它们是 a a b b a a b b a b a a b b b a a a b b a b b a 25 2 由于A上的反自反关系必须不含有 a a b b 所以A上的反自反关系也有4种 它们是 空关系 a b b a a b b a 3 由于A上的对称关系R 当 a b R时 必有 b a R 所以只需考虑在 a a b b a b 中选取0个 1个 2个 3个有序对构成的集合 它们是空关系 a a b b a b b a a a b b a a a b b a b b a b b a a a b b a b b a 所以A上的对称关系有8种 26 27 所以在A A的子集中删去同时含有 a b 和 b a 的子集后 其它子集都是反对称关系 共有12种 即 空关系 a a a b b a b b a a a b a a b a a a b b a b b b b a b b a a a b b b a a b a b b 4 由于A上的反对称关系 当 a b R必有 b a R 27 28 思考3 设A 1 2 3 问在A上有多少种不同的自反关系 解 当R是A上的自反关系时 R必须含有表格中对角线上的3个小方格所表示的有序对 对于表格中余下的6个小方格 可以依次选取1个 2个 6个小方格 也可以不取 它们所表示的二元关系都是A上的自反关系 因此 A上共有64个自反关系 28 5 传递性的判定方法 判定定理1 设集合A a1 a2 an R是A上的二元关系 R的关系矩阵为MR 令MR2 MR MR 则R是A上的传递关系的充要条件是对MR2中1所在位置 MR中相应位置都是1 例9 设A a b c d e R 试判断R的传递性 判定定理2 设集合A a1 a2 an R是A上的二元关系 R的关系矩阵为MR R是A上的传递关系的充要条件是若MR中的零元素aij 0所对应的MR2的元素bij 0时 则R是A上的传递关系 29 思考 设A a1 a