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