离散数学-第四章-等价关系和偏序关系ppt课件.ppt

《离散数学-第四章-等价关系和偏序关系ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学-第四章-等价关系和偏序关系ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、14.5 等价关系与偏序关系等价关系与偏序关系n等价关系的定义与实例等价关系的定义与实例n等价类及其性质等价类及其性质n商集与集合的划分商集与集合的划分n等价关系与划分的一一对应等价关系与划分的一一对应n偏序关系偏序关系n偏序集与哈斯图偏序集与哈斯图n偏序集中的特定元素偏序集中的特定元素2等价关系的定义与实例等价关系的定义与实例定义定义 设设 R 为非空集合上的关系为非空集合上的关系. 如果如果 R 是自反的、是自反的、对称的和传递的对称的和传递的, 则称则称 R 为为 A 上的上的等价关系等价关系. 设设 R 是一个等价关系是一个等价关系, 若若R, 称称 x 等价于等价于y, 记做记做 x

2、y. 实例实例 设设 A=1,2,8, 如下定义如下定义A上的关系上的关系 R： R = | x,yAxy(mod 3) 其中其中 xy(mod 3) 叫做叫做 x 与与 y 模模3相等相等, 即即 x 除以除以3的的余数与余数与 y 除以除以3的余数相等的余数相等. 3等价关系的验证等价关系的验证验证模验证模 3 相等关系相等关系 R 为为 A上的等价关系上的等价关系, 因为因为 xA, 有有x x(mod 3) x, yA, 若若 x y(mod 3), 则有则有 y x(mod 3) x, y, zA, 若若x y(mod 3), y z(mod 3), 则有则有 xz(mod 3)自反

3、性、对称性、传递性得到验证自反性、对称性、传递性得到验证4A上模上模3等价关系的关系图等价关系的关系图设设 A=1,2,8, R= | x,yAxy(mod 3) 5等价类等价类定义定义 设设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,66等价类的性质等价类的性质 定理定理1 设设R是非空集

4、合是非空集合A上的等价关系上的等价关系, 则则 (1) xA, x 是是A的非空子集的非空子集. (2) x, yA, 如果如果 x R y, 则则 x=y. (3) x, yA, 如果如果 x y, 则则 x与与y不交不交. (4) x | xA=A，即所有等价类的并集就即所有等价类的并集就是是A. 7实例实例A= 1, 2, , 8 上模上模 3 等价关系的等价类：等价关系的等价类： 1=4=7=1,4,7， 2=5=8=2,5,8， 3=6=3,6 以上以上3 类两两不交，类两两不交， 1,4,7 2,5,8 3,6 = 1,2, ,88商集商集定义定义 设设R为非空集合为非空集合A上的

5、等价关系上的等价关系, 以以R的所有的所有等价类作为元素的集合称为等价类作为元素的集合称为A关于关于R的的商集商集, 记做记做A/R, A/R = xR | xA 实例实例 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集合的划分集合的划分定义定义 设设A为非空集合为非空集合, 若若A的子集族的子集族( P(A) 满足下面条件：满足下面条件： (1) (2) x y (x,yxyxy=) (3)

6、 =A 则称则称是是A的一个的一个划分划分, 称称中的元素为中的元素为A的的划分划分块块.10例题例题例例1 设设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 的划分的划分. 为什么？为什么？11等价关系与划分的一一对应等价关系与划分的一一对应商集商集 A/R 就是就是 A 的一个划分的一个划分 不同的商集对应于不同的划分不

7、同的商集对应于不同的划分 任给任给 A 的一个划分的一个划分, 如下定义如下定义 A 上的关系上的关系 R： R = | x,yAx 与与 y 在在的同一划分块中的同一划分块中则则 R 为为 A上的等价关系上的等价关系, 且该等价关系确定的商集且该等价关系确定的商集就是就是. 例例2 给出给出A1,2,3上所有的等价关系上所有的等价关系求解思路：先做出求解思路：先做出A的所有划分的所有划分, 然后根据划分写然后根据划分写出对应的等价关系出对应的等价关系. 12等价关系与划分之间的对应等价关系与划分之间的对应1,2和和3分别对应等价关系分别对应等价关系 R1, R2 和和 R3. R1=,IA，

8、R2=,IA R3=,IA4 对应于全域关系对应于全域关系 EA，5 对应于恒等关系对应于恒等关系 IA13实例实例例例3 设设 A=1, 2, 3, 4，在，在 A A上定义二元关系上定义二元关系R： , R x+y = u+v，求求 R 导出的划分导出的划分. 解解 A A=, , , , , , , , , , , , , 14实例（续）实例（续）根据根据 的的 x + y = 2,3,4,5,6,7,8 将将A A划分成划分成7个个等价类：等价类： (A A)/R= , , , , , , , , , , , , , , 15偏序关系偏序关系定义定义 非空集合非空集合A上的自反、反对称

9、和传递的关系，上的自反、反对称和传递的关系，称为称为A上的上的偏序关系偏序关系，记作，记作 . 设设 为偏序关系为偏序关系, 如果如果 , 则记作则记作 x y, 读作读作 x“小于或等小于或等于于”y. 实例实例 集合集合A上的恒等关系上的恒等关系 IA 是是A上的偏序关系上的偏序关系. 小于或等于关系小于或等于关系, 整除关系和包含关系也是相应整除关系和包含关系也是相应集合上的偏序关系集合上的偏序关系. 16相关概念相关概念x与与 y 可比可比：设：设R为非空集合为非空集合A上的偏序关系上的偏序关系, x,y A, x与与y可比可比 x y y x.结论：任取两个元素结论：任取两个元素x和

10、和y, 可能有下述情况：可能有下述情况： x y (或或y x), xy, x与与y不是可比的不是可比的.全序关系全序关系： R为非空集合为非空集合A上的偏序上的偏序, x,y A, x与与 y 都是可比的，都是可比的，则称则称 R 为为全序全序（或（或 线序线序）实例：数集上的小于或等于关系是全序关系实例：数集上的小于或等于关系是全序关系 整除关系不是正整数集合上的全序关系整除关系不是正整数集合上的全序关系17覆盖覆盖：设：设R为非空集合为非空集合A上的偏序关系上的偏序关系, x, yA, 如如果果 x y且不存在且不存在 z A 使得使得 x z y, 则称则称 y 覆覆盖盖x.实例：实例

11、： 1, 2, 4, 6 集合上的整除关系集合上的整除关系, 2 覆盖覆盖 1, 4 和和 6 覆盖覆盖 2. 4 不覆盖不覆盖 1. 相关概念（续）相关概念（续）18偏序集与哈斯图偏序集与哈斯图定义定义 集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集, 记记作作 .实例：整数集和小于等于关系构成偏序集实例：整数集和小于等于关系构成偏序集，幂，幂集集P(A)和包含关系构成偏序集和包含关系构成偏序集. 哈斯图哈斯图：利用偏序自反、反对称、传递性简化的关：利用偏序自反、反对称、传递性简化的关系图系图特点：每个结点没有环，两个连通的结点之间的序特点：每个结点没有环，两个连通的

12、结点之间的序关系通过结点位置的高低表示，位置低的元素的顺关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边序在前，具有覆盖关系的两个结点之间连边19哈斯图实例哈斯图实例例例4 20A=a, b, c, d, e, f, g, h R=,IA 哈斯图实例（续）哈斯图实例（续）例例5 已知偏序集已知偏序集的哈斯图如右图所示的哈斯图如右图所示, 试求出集合试求出集合A和关系和关系R的表达式的表达式. 21偏序集的特定元素偏序集的特定元素定义定义 设设为偏序集为偏序集, B A, yB.(1) 若若 x(xBy x) 成立成立, 则称则称 y 为为 B 的的最小元最小元

13、.(2) 若若 x(xBx y) 成立成立, 则称则称 y 为为 B 的的最大元最大元. (3) 若若x (xBx y) 成立成立, 则称则称 y 为为B的的极小元极小元. (4) 若若x (xBy x) 成立成立, 则称则称 y 为为B的的极大元极大元. 22特殊元素的性质特殊元素的性质n 对于有穷集，极小元和极大元必存在，可能存在对于有穷集，极小元和极大元必存在，可能存在 多个多个. n 最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.n 最小元一定是极小元；最大元一定是极大元最小元一定是极小元；最大元一定是极大元. n 孤立结点既是极小元，也是极大元

14、孤立结点既是极小元，也是极大元. 23定义定义 设设为偏序集为偏序集, B A, y A. (1) 若若 x(xBx y) 成立成立, 则称则称 y 为为B的的上界上界. (2) 若若 x(xBy x) 成立成立, 则称则称 y 为为B的的下界下界. (3) 令令Cy | y为为B的上界的上界, 则称则称C的最小元为的最小元为B的的最小上界最小上界 或或 上确界上确界. (4) 令令Dy | y为为B的下界的下界, 则称则称D的最大元为的最大元为B的的最大下界最大下界 或或 下确界下确界.偏序集的特定元素偏序集的特定元素(续续)24n下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确

15、界不一定存在n下界、上界存在不一定惟一下界、上界存在不一定惟一n下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一n集合的最小元就是它的下确界，最大元就是它的集合的最小元就是它的下确界，最大元就是它的上确界；反之不对上确界；反之不对. 特殊元素的性质特殊元素的性质25实例实例例例6 设偏序集设偏序集如下图所示，求如下图所示，求 A 的极小元、的极小元、最小元、极大元、最大元最小元、极大元、最大元. 设设 Bb,c,d, 求求 B 的下的下界、上界、下确界、上确界界、上界、下确界、上确界. 极小元：极小元：a, b, c, g；极大元：极大元：a, f, h；没有最小元与最大元没有最小元与最大元.B的下界和最大下界的下界和最大下界都都不存在不存在, 上界有上界有d 和和 f, 最小上界为最小上界为 d.