《离散数学17课件》由会员分享，可在线阅读，更多相关《离散数学17课件（24页珍藏版）》请在金锄头文库上搜索。
1、1,4.4 等价关系与偏序关系,4.4.1 等价关系 4.4.2 等价类和商集 4.4.3 集合的划分 4.4.4 偏序关系 4.4.5 偏序集与哈斯图,2,等价关系的定义与实例,定义4.18 设R为非空集合上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若R, 称 x等价于y, 记做xy. 例1 设 A=1, 2, , 8, 如下定义 A上的关系R： R=| x,yAxy (mod 3) 其中 xy (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为 xA, 有xx(m
2、od 3) x,yA, 若xy(mod 3), 则有yx(mod 3) x,y,zA, 若xy(mod 3), yz(mod 3), 则有 xz(mod 3),3,模3等价关系的关系图,设 A=1, 2, , 8, R= | x,yAxy (mod 3) R 的关系图如下：,4,等价类,定义4.19 设R为非空集合A上的等价关系, xA，令 xR = y | yAxRy 称 xR 为x关于R 的等价类, 简称为 x 的等价类, 简记为x. 实例 A= 1, 2, , 8 上模 3 等价关系的等价类： 1=4=7=1,4,7 2=5=8=2,5,8 3=6=3,6,5,等价类的性质,定理4.8
3、设R是非空集合A上的等价关系, 则 (1) xA, x 是A的非空子集. (2) x, yA, 如果 xRy, 则 x=y. (3) x, yA, 如果 x y, 则 x与y不交. (4) ，即所有等价类的并集就是A. ,6,性质的证明,由等价类定义可知, xA有xA. 由自反性有xRx，因此xx, 即x非空. 任取z, 则有 zx R R RR R R 从而证明了zy. 综上所述必有xy. 同理可证y x. 这就得到了x=y. (3) 假设xy, 则存在zxy, 从而有 zxzy, 即RR 成立. 根据R 的对称性和传递性必有R, 与x y矛盾,7,性质的证明（续）,(4) 先证 . 任取y
4、, y x (xAyx) yxxA yA 从而有 . 再证A . 任取y, yA yyyA y 从而有A 成立. 综上所述得,8,商集,定义4.20 设R 为非空集合A 上的等价关系, 以R 的所有等 价类作为元素的集合称为A关于R 的商集, 记做 A/R, A/R = xR | xA 例2 令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 ,9,集合的划分,定义4.21 设A为非空集合, 若A的子集族 ( P(A) 满足下面条件
5、： (1) (2) xy (x,yxyxy=) (3) =A 则称是A的一个划分, 称 中的元素为A的划分块. 例3 设Aa, 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的划分.,10,等价关系与划分的一一对应,商集 A/R 就是A 的一个划分 不同的商集对应于不同的划分 任给A 的一个划分 , 如下定义A 上的关系 R： R = | x,yAx 与 y 在的同一划分块中 则R 为A
6、上的等价关系, 且该等价关系确定的商集就是.,例4 给出A1,2,3上所有的等价关系 求解思路：先做出A的所有划分, 然后根据划分写出 对应的等价关系.,11,例 4, 1, 2和 3分别对应于等价关系 R1, R2和R3. 其中 R1=,IA R2=,IA R3=,IA,A上的等价关系与划 分之间的对应： 4对应于全域关系EA 5对应于恒等关系IA,12,实例,根据有序对的 x+y=2,3,4,5,6,7,8 将AA划分. (AA)/R=, , , , , , , , , , , , , , ,例5 设A=1,2,3,4，在AA上定义二元关系 R： ,R x+y = u+v， 求R 导出的划
7、分.,解 AA=, , , , , , , , , , , , , , ,13,偏序关系,定义4.22 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系，记作. 设为偏序关系, 如果 , 则记作 xy, 读作 x“小于或等于”y. 实例 集合A上的恒等关系 IA 是A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏序关系.,14,相关概念,定义4.23 x与y可比 设R为非空集合A上的偏序关系, x, yA, x与y 可比 xy yx. 结论：x, yA，下述几种情况发生其一且仅发生其一. xy, yx, xy, x与y不是可比的 定义4.25 全序 R为非空集
8、合A上的偏序, x, yA, x与y 都可比，则称R为全序. 定义4.26 覆盖 x,yA, 如果xy且不存在 zA使得 xzy, 则称 y覆盖x. 实例：数集上的小于或等于关系是全序关系 整除关系不是正整数集合上的全序关系 1, 2, 4, 6集合上的整除关系, 2覆盖1, 4 和 6 覆盖2. 但4不覆盖1.,15,偏序集与哈斯图,定义4.27 集合A和A上的偏序关系一起叫做偏序集, 记作. 实例：整数集和数的小于等于关系构成偏序集 幂集P(A)和包含关系构成偏序集. 哈斯图：利用偏序自反、反对称、传递性简化的关系图 特点： 每个结点没有环 两个连通的结点之间的序关系通过结点位置的高低 表
9、示，位置低的元素的顺序在前 具有覆盖关系的两个结点之间连边,16,哈斯图实例,例6 ,17,例7 已知偏序集 的哈斯图如下图所示, 试求出集合A和关系 R的表达式.,哈斯图实例（续）,A=a, b, c, d, e, f, g, h R=, IA,18,偏序集的特定元素,定义4.28 设为偏序集, BA, yB. (1) 若x(xByx)成立, 则称 y 为 B 的最小元. (2) 若x(xBxy)成立, 则称 y 为 B 的最大元. (3) 若x(xBxyx=y)成立, 则称 y 为B的极小元. (4) 若x(xByxx=y)成立, 则称 y 为B的极大元. 性质： 对于有穷集，极小元和极大
10、元必存在，可能存在多个. 最小元和最大元不一定存在，如果存在一定惟一. 最小元一定是极小元；最大元一定是极大元. 孤立结点既是极小元，也是极大元.,19,定义4.29 设为偏序集, BA, yA. （1） 若x (xBxy) 成立, 则称 y 为B 的上界. （2） 若x (xByx) 成立, 则称 y 为B 的下界. （3） 令Cy | y为B的上界, 则称C的最小元为B 的最小上界 或上确界. （4） 令Dy | y为B的下界, 则称D的最大元为B 的最大下界 或下确界. 性质： 下界、上界、下确界、上确界不一定存在 下界、上界存在不一定惟一 下确界、上确界如果存在，则惟一 集合的最小元就
11、是它的下确界，最大元就是它的上确界；反之不对.,偏序集的特定元素(续),20,实例,例8 设偏序集如下图所示，求A 的极小元、最小元、 极大元、最大元. 设B b, c, d , 求B 的下界、上界、下 确界、上确界.,解：极小元：a, b, c, g； 极大元：a, f, h； 没有最小元与最大元. B的下界和最大下界 都不存在, 上界有d 和 f, 最小上界为 d.,21,偏序集的特殊子集,定义4.30 设为偏序集, BA. (1) 如果x,yB，x与y都是可比的，则称B是A中的一条 链，B中的元素个数称为链的长度； (2) 如果x,yB，xy，x与y都是不可比的，则称B是A 中的一条反链
12、，B中的元素个数称为反链的长度. 实例：在偏序集中，1,2,4,8是长为4的 链，1,4是长为2的链，2,3是长为2的反链. 对于单元 集2，它的长度是1，既是链也是反链.,22,分解为反链,算法4.2 偏序集反链分解算法 输入：偏序集A 输出：A中的反链B1, B2, 1i1 2BiA 的所有极大元的集合（显然Bi是一条反链） 3令AABi 4if A 5 ii+1 6 转2,定理4.9 设为偏序集，如果A中最长的链长度为n, 则该偏序集可以分解为 n 条不相交的反链.,23,拓扑排序,算法4.3 拓扑排序 输入：偏序集A 输出：A中元素的排序 1. i1 2. 从A中选择一个极小元 ai 作为最小元 3AAai 4if A 5 ii+1 6 转2,把偏序集扩张成一个全序集，称为拓扑排序.,24,实例,有偏序约束的任务集A， 偏序集的哈斯图如图 A = T1, T2, T3, T4, T5, S1, T6, S2, T, T9, T10 可行的拓扑排序有多个， 如： T1, T2, T3, T4, S1, T5, T6, S2, T, T9, T10； T1, T2, T3, T4, S1, T6, S2, T, T9, T5, T10;,
