《离散数学等价关系与偏序关系ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学等价关系与偏序关系ppt课件.ppt（31页珍藏版）》请在金锄头文库上搜索。
1、集合与图论 第9节 等价关系与偏序关系 主要内容 等价关系 偏序关系 1 集合与图论 定义1 集合X上的二元关系R称为等价关系 如果R 同时具有以下三个性质 例1 集合X上的恒等关系是不是X上的等价关系 1 R是自反的 即 x X xRx 2 R是对称的 即如果xRy 则yRx 3 R是传递的 即如果xRy yRz 则xRz 是X上的等价关系 1 等价关系 2 集合与图论 等价关系实例 例2 考虑整数集Z上的模n同余关系 例4 设f X Y Ker f x y x y X 且f x f y Ker f 是X上的等价关系 例3 实数集上的 都不是R上 的等价关系 是等价关系 3 集合与图论 例5
2、 设 A 1 2 8 如下定义 A上的关系R R x y x y A x y mod 3 R 的关系图如下 等价关系的关系图 4 集合与图论 定义2 设R是X上的一个等价关系 x X X的 子集Ex y y X且xRy 称为x关于R的等价类 或简 记为x的等价类 x的等价类常记为 x 即 x y y X且xRy 例5 设 A 1 2 8 如下定义 A上的关系R R x y x y A x y mod 3 等价类的定义 A 1 2 8 上模 3 等价关系的等价类 1 4 7 1 4 7 2 5 8 2 5 8 3 6 3 6 5 集合与图论 等价类的性质 3 x y X 如果 x y R 则 x
3、 y 定理1 设R是非空集合X上的等价关系 则 1 x X x 2 x y X 如果 x y R 则 x y 4 即所有等价类的并集就是X 6 集合与图论 定义3 设X为非空集合 X的若干个子集形成的集 族 称为X的一个划分 如果 具有性质 集合的划分 如果 是X的一个划分 则当 k时 被称为X的 一个k 划分 2 x y 若x y 则x y 1 3 称 中的元素为X的划分块 7 集合与图论 例6 设A a b c d 给定 1 2 3 4 5 6 如下 1 a b c d 2 a b c d 3 a a b c d 4 a b c 5 a b c d 6 a a b c d 1和 2是A的划
4、分 其他都不是A的划分 实 例 8 集合与图论 定理1 设R是X上的一个等价关系 则R的所有等 价类的集合是X的一个划分 等价关系与集合的划分 定理2 设 是集合X的一个划分 令 R x y x y X x与y在 的同一划分块中 则R是X上的一个等价关系 并且 就是R的等价类之集 注 由定理1 2可得 X上的等价关系与X的划分 是一一对应的 并且互相确定 9 集合与图论 定义4 设R是X上的等价关系 由R所确定的X的 划分也就是R的所有等价类之集称为X对R的商集 并记X R 即 X R x x X x 是x的等价类 等价关系R确定的划分是R的所有等价类之集 x x X 商 集 10 集合与图论
5、 例7 令A 1 2 8 A关于模 3 等价关系R 的商集为 A R 1 4 7 2 5 8 3 6 A关于恒等关系和全域关系的商集为 A IA 1 2 8 A EA 1 2 8 实 例 11 集合与图论 例8 给出A 1 2 3 上所有的等价关系 求解思路 先做出A的所有划分 然后根据划分写出 对应的等价关系 实 例 12 集合与图论 实 例 1 2和 3分别对应于等价关系 R1 R2和R3 其中 R1 2 3 3 2 IA R2 1 3 3 1 IA R3 1 2 2 1 IA A上的等价关系与划分之间的对应 4对应于全域关系EA 5对应于恒等关系IA 问题 设集合X为有限集 X n 则X
6、上有多少个 等价关系 13 集合与图论 定理4 设R为X上的一个二元关系 则 e R R R 1 R的等价闭包 R的自反对称传递闭包 记为e R e R 是X上包含R的那些等价关系的交集 定理5 设R S是X上的等价关系 则R S是等价关 系的充要条件是R S S R 推论 设R S是X上的等价关系 则R S是等价关 系的充要条件是R S S R 等价关系的运算 14 集合与图论 定义1 集合X上的二元关系R称为偏序关系 如 果R同时满足以下三个性质 当抽象地讨论X上的偏序关系时 常用符号 表 示偏序关系 如果x y 则读作 x小于或等于y 1 R是自反的 2 R是反对称的 3 R是传递的 约
7、定x y且x y时 就记为xy 实 例 17 集合与图论 定义3 集合X上的偏序关系 叫做全序关系 如果 x y X x y与y x至少有一个成立 全序关系也称为 线性序关系 X与全序关系 构成的二元组 X 称为全 序集 偏序集与全序集的主要区别在于全序集中任两个 元素均可比较 大小 而在偏序集中任意两个元素不 一定都能比较大小 实数间的常用的 小于或等于 关系是不是全序关系 全序关系与全序集 集合的包含关系与自然数间的整除关系是不是全 序关系 是全序关系 相应的偏序集也是全序集 二者都不是全序关系 18 集合与图论 定义4 设 X 是一个偏序集 称y盖住x 如果 x y且对每个z X 若x
8、z y 则x z或y z 如果y盖住x 则y被称为x的后继 而x称为y的前 驱 盖住的定义 例3 偏序集 N 中 称3盖住2 3是2的后继 2是3 的先驱 1 2 4 6 集合上的整除关系 2覆盖1 4 和 6 覆 盖2 但4不覆盖1 19 集合与图论 哈斯 Hasse 图 首先偏序关系 是自反的 所以偏序关系的关系图 中每个顶点都有一个环 因此可以省略每个顶点的环 其次由于偏序关系是传递的 那么只要在前驱与 后继间联线即可 最后由于反对称性 若x y x y 则点y画在x 的上方 这样就不必用矢线了 按上述方法画出的图 称为 X 的哈斯图 20 集合与图论 特点 1 每个结点没有环 2 两个
9、连通的结点之间的序关系通过结点 位置的高低表示 位置低的元素的顺序在前 3 具有覆盖关系的两个结点之间连边 哈斯图就是利用偏序的自反 反对称 传 递性简化了的关系图 哈斯 Hasse 图的特点 21 集合与图论 例4 1 2 3 4 5 6 7 8 9 R整除 P a b c R 哈斯图实例 22 集合与图论 例5 已知偏序集 A R 的哈斯图如下图所示 试 求出集合A和关系R的表达式 A a b c d e f g h R b d b e b f c d c e c f d f e f g h IA 哈斯图实例 23 集合与图论 例6 设A a1 a2 an 是一个全序集 则其元素 A 的哈
10、斯图象一条链子一样 所以 全序关系也叫做线性序关系 全序集又称为线性序集 可以 从小到大 排列为 ai1 ai2 ain 全序关系的哈斯图 24 集合与图论 定义5 设 X 是一个偏序集 B X 如果存在一 个元素a X使得对B中每个元素x有x a 则称a为B的一 个上界 上界与下界的定义 如果存在一个元素b X 使得对B的每一个元素x 有b x 则称b为B的一个下界 上界与下界都不一定存在 例7 令A 2 3 6 12 24 36 A在整除关系 下构成一 个偏序集 A 24 36 不存在上界 上界与下界可能有很多元素 6 12 24 36都是子集 2 3 的上界 2 3 不存在下界 25 集
11、合与图论 定义6 设 X 是一个偏序集 B X 如果存在一个 元素a B使得对B中每个元素x有x a 则称a是B中的最 大元素 最大元素一定是上界 最小元素一定是下界 最大与最小元素 如果存在一个元素b B 使得对B的每一个元素x有 b x 则称b是B中的最小元素 有上下界不一定有最大与最小元素 最大元素与最小元素若有一定是唯一的 因为上下界不一定在子集中 26 集合与图论 定义7 设 X 是一个偏序集 B X 如果B有上 界且B的一切上界之集有最小元素 则这个最小上界 称为B的上确界 记为supB 上确界与下确界的定义 如果B有下界且B的一切下界之集有最大元素 则这个最大下界称为B的下确界
12、记为infB 例8 令A 2 3 6 12 24 36 A在整除关系 下构成一 个偏序集 A 6 12 24 36都是子集 2 3 的上界 6是子集 2 3 的上确界 2 3 6 12都是子集 24 36 的下界 12是子集 24 36 的下确界 27 集合与图论 A中有最大元素和最小元素吗 实 例 例9 令A 2 3 6 12 24 36 A在整除关系 下构成一个 偏序集 A A中没有最大元素也没有最小元素 因为24与36不可比 2与3也不可比 但是A中没有比24和36更大的元素 也没有比2与 3更小的元素 称24和36都是极大元素 2与3都是极小元素 28 集合与图论 定义8 设 X 是一
13、个偏序集 A X A中元素s称为 A的极大元素 如果A中没有元素m使得m s且s m 若A中有极大元素 则极大元素属于A 而且未必 唯一 甚至可能有无穷多个 如果A中有元素d 使得 x A 若x d 则x d不 成立 那么d被称为A的极小元素 极大元素不一定是最大元素 但最大元素一定是 极大元素 同样若A中有极小元素 则极小元素属于A 而且 未必唯一 甚至可能有无穷多个 同样极小元素不一定是最小元素 但最小元素一定 是极小元素 极大元素与极小元素的定义 29 集合与图论 解 极小元 a b c g 极大元 a f h 没有最小元与最大元 B的下界和最大下界都 不存在 上界有d 和 f 最小上界为 d 实 例 例10 设偏序集 A 如下图所示 求A 的极小元 最小元 极大元 最大元 设B b c d 求B 的下界 上界 下确界 上确界 30 此课件下载可自行编辑修改 供参考 感谢您的支持 我们努力做得更好 31
