《离散数学-等价关系与偏序关系.ppt》由会员分享，可在线阅读，更多相关《离散数学-等价关系与偏序关系.ppt（19页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学集合论集合论主要内容n集合代数n二元关系n函数集合的基本概念集合的运算有穷集合的计数集合恒等式有序对与笛卡儿积二元关系关系的运算关系的性质 关系的闭包等价关系与划分偏序关系函数的定义与性质函数的复合与反函数双射函数与集合的基数27.6等价关系与划分例例7.167.16 设设 A=1,2A=1,2,8,8,定义定义 A A 上的关系上的关系 R R如下如下: : 验证验证R R是是A A上的等价关系上的等价关系. .一一. . 等价关系等价关系 定定义义7.157.15 设设R R为为非非空空集集合合A A上上的的关关系系. .如如果果R R是是自自反反的的, , 对对称称的的和
2、和传递的传递的, ,则称则称R R为为A A上的等价关系上的等价关系. .对等价关系对等价关系R,R,若若 R, R, 则称则称 x x 等价于等价于y y, ,记为记为x xy y oror xRyxRy. . 解解: : x x A A, ,有有 , , 故故R R是自反的是自反的. . x,yx,y A A, , 若若 , , 则则 , , 故故R R是对称的是对称的. . x,y,zx,y,z A A, ,若若 , , 则则 , , 故故 R R是传递的是传递的. . R R是是A A上的一个等价关系上的一个等价关系. .3等价类定义定义 7.167.16 设设 R R 为非空集合为非
3、空集合A A上的等价关系上的等价关系, , x x A, A, 令令称称 x x R R为为x x在在R R下的等价类下的等价类 ( (简称为简称为x x的等价类的等价类),),有时简记为有时简记为 x x . . x x 称为该等价类的代表元称为该等价类的代表元. . 注注: :一个等价类是一个等价类是A A中在等价关系中在等价关系R R下彼此等价的所有元素的集下彼此等价的所有元素的集 合合, ,等价类中各元素的地位是平等的等价类中各元素的地位是平等的, ,每个元素都可以作为每个元素都可以作为 其所在等价类的代表元其所在等价类的代表元. .例如例如, ,在上例中的等价关系在上例中的等价关系R
4、 R下下,A,A中元素形成了三个等价类中元素形成了三个等价类: : 1 1 = = 4 4 = = 7 7 =1, 4, =1, 4, 7; 7; 2 2 = = 5 5 = = 8 8 =2, 5, =2, 5, 8;8; 3 3 = = 6 6 =3, 6.=3, 6., , , , , , , , , , , , , , , 4等价类的性质定理定理7.147.14 设设 R R 为非空集合为非空集合 A A上的等价关系上的等价关系, ,则则 （1 1） x x A, A, x x 是是A A的非空子集的非空子集. . （2 2） x, yx, y A,A,如果如果xRyxRy, , 则则
5、 x x = = y y （3 3） x, yx, y A,A,如果如果x x与与y y不具有关系不具有关系 R, R, 则则 x x 与与 y y 不相交不相交. . （4 4） x | xA = A x | xA = A证证：(1) (1) 显然显然. . (2) z(2) zx x R R R R（R R是对称的）是对称的） RR R R R R R R z zy y , , 从而从而 x x y y 同理可得同理可得, , y y x x . . 故故 x x = = y y 5等价类的性质(3) (3) 反证法反证法. . 假设假设 x x y y , ,则存在则存在 z zx x
6、y y . . 因而因而 z z x x 且且z z y y , ,即即 RR R. R. 根据根据R R的对称性和传递性的对称性和传递性, ,必有必有x, y R.R.这与前提条件矛盾这与前提条件矛盾. . 故原命题成立故原命题成立. .(4)先证先证 再证再证 因此因此6商集与划分定义定义7.177.17 设设R R为非空集合为非空集合A A上的等价关系上的等价关系, ,以以R R的所有等价类作为元素的所有等价类作为元素, , 形成的集合称为形成的集合称为A A关于关于R R的的商集商集, ,记为记为A/R,A/R,即即: :例如例如: :例例7.167.16中等价关系形成的商集为中等价关
7、系形成的商集为: : A/R A/R 1, 4, 7, 2, 5, 8, 3, 61, 4, 7, 2, 5, 8, 3, 6定义定义7.187.18 设设A A为非空集合为非空集合, ,若若A A的子集族的子集族 ( (P(A),P(A), 是由是由A A的一些子集形的一些子集形成的集合成的集合) ) 满足下列条件满足下列条件: : (1) (1) (2) (2) x x y(x,yy(x,y xyxy= xyxy= ) ) (3) (3) 则称则称 是是A A的一个的一个划分划分, ,而称而称 中的元素为中的元素为 A A的划分块或类的划分块或类. .五五. . 集合的划分集合的划分7等价
8、关系与划分例例7.17 7.17 设设A=a, b, c, d , A=a, b, c, d , 则则 1 1=a,b,c=a,b,c ,d d和和 2 2=a,b,c,=a,b,c,dd都是都是A A的划分的划分, ,而而 3 3=a,a,a,b,c,da,b,c,d和和 4 4= = ,a,b,a,b,cc都不是都不是A A的划分的划分. .注注: :给给定定非非空空有有限限集集A A上上的的一一个个等等价价关关系系R,R,在在R R下下彼彼此此等等价价的的元元素素构构成成的的子子集集便便形形成成了了A A的的一一个个划划分分, ,它它其其实实就就是是商商集集A/R, A/R, 其其每每个
9、个类类 ( (等等价价块块) ) 就就是是R R的一个等价类的一个等价类; ; 反之反之, ,任给任给A A的一个的一个 划分划分 , ,可定义可定义A A上的关系上的关系R R如下如下: : R= R= x,yx,y AxAx与与y y在在 的同一个类中的同一个类中 可可以以验验证证R R是是A A上上的的一一个个等等价价关关系系. .可可见见A A上上的的等等价价关关系系与与A A的的划划分分是是一一一一对应的对应的. .8例例例7.187.18 求求A=1, 2, 3A=1, 2, 3上所有的等价关系上所有的等价关系. .解解 先求出先求出A A的所有划分的所有划分: : 1 1=1,
10、2, 3; =1, 2, 3; 2 2=1, 2, 3=1, 2, 3； 3 3=2, 1, 3; =2, 1, 3; 4 4=3, 1, 2;=3, 1, 2; 5 5= 1, 2, = 1, 2, 3.3. 与这些划分一一对应的等价关系是与这些划分一一对应的等价关系是: : 1 1: : 全域关系全域关系E EA A 2 2: R: R2 2=, I=, IA A 3 3: R: R3 3=, I=, IA A 4 4: R: R4 4=, I=, IA A 5 5: : 恒等关系恒等关系I IA A97.7偏序关系一.一.偏序关系与偏序集偏序关系与偏序集定义定义7.197.19 设设R
11、R为非空集合为非空集合A A上的关系上的关系. .如果如果R R是是自反的自反的, ,反对称的反对称的和和传递的传递的, ,则称则称 R R 为为 A A上的偏序关系上的偏序关系, ,记为记为 . . 对一个偏序关系对一个偏序关系 , ,如果如果 , ,则记为则记为 x x y.y.注注: : 1. 1. 集集合合A A上上的的恒恒等等关关系系I IA A和和空空关关系系都都是是A A上上的的偏偏序序关关系系, ,但但全全域域关关系系E EA A 一般不是一般不是A A上的偏序关系上的偏序关系. . 2. 2. 实实数数域域上上的的小小于于等等于于关关系系（大大于于等等于于关关系系）, ,自自
12、然然数数域域上上的的整整除关系除关系, ,集合的包含关系等都是偏序关系集合的包含关系等都是偏序关系. .10可比与不可比注注: :在具有偏序关系的集合在具有偏序关系的集合A A中任二元素中任二元素 x x 和和 y y 之间必有下列四之间必有下列四 种情形之一种情形之一: : x x y y ,y,y x x ,x=y,x=y ,x,x与与y y不可比不可比. .例例 设设A=1, 2, 3A=1, 2, 3(1)(1) 是是A A上的整除关系上的整除关系, ,则则:1:1 2 2, , 1 1 3 3, 1, 11, 21, 22, 32, 33,3, 2 2 和和 3 3 不可比不可比;
13、;(2) (2) 是是 A A 上的大于等于关系上的大于等于关系, ,则则: 2 : 2 1, 3 1, 3 1, 3 1, 3 2, 12, 11, 21, 22,32,33.3.定义定义7.207.20 设设R R为非空集合为非空集合A A上的偏序关系上的偏序关系, ,定义定义(1) (1) x, x, y y A A, x , x y y当且仅当当且仅当 x x y y且且 xyxy (2) (2) x, x, y y A A, x , x 与与 y y 可比当且仅当可比当且仅当 x x y y 或或 y y x x11偏序集定义定义7.217.21 设设R R为非空集合为非空集合A A
14、上的偏序关系上的偏序关系, ,如果如果 x, yx, y A, x A, x 与与 y y 都是可比都是可比的的, ,则称则称R R为为A A上的全序关系上的全序关系. . 例如例如 大于等于关系大于等于关系( (小于等于关系小于等于关系) )是全序集是全序集, ,但整除关系一般不是全序集但整除关系一般不是全序集. .定义定义7.227.22 带有某种指定的偏序关系带有某种指定的偏序关系 的集合的集合A A称为偏序集称为偏序集, ,记为记为A, . .例如例如 整数集整数集Z Z和数的小于等于关系和数的小于等于关系构成偏序集构成偏序集 z, ; ; 集合集合A A的幂集的幂集P(A)P(A)和
15、集合的包含关系和集合的包含关系 构成偏序集构成偏序集P(A), .定义定义7.237.23 设设 A, 为偏序集为偏序集, , x, y x, y A A, ,如果如果 x x y y且不存在且不存在 z z A, A, 使得使得x x z z y, y, 则称则称 y y 覆盖覆盖 x.x. 例如例如 A=1, 2, 4, 6A=1, 2, 4, 6上的整除关系上的整除关系, ,有有2 2覆盖覆盖1,41,4和和6 6都覆盖都覆盖2,2,但但4 4不覆盖不覆盖1,61,6不覆盖不覆盖4.4.12哈斯图 利用偏序关系的自反性利用偏序关系的自反性, ,反对称性和传递性可简化偏序关系的关系图反对称
16、性和传递性可简化偏序关系的关系图, ,得得到偏序集的哈斯图到偏序集的哈斯图. . 设有偏序集设有偏序集A, , , 其哈斯图的画法如下其哈斯图的画法如下: :(1) (1) 以以 A A 的元素作为顶点的元素作为顶点, ,适当排列各顶点的顺序适当排列各顶点的顺序, ,使得对使得对 x, y x, y A, A, 若若x x y, y, 则将则将 x x 画在画在 y y 的下方的下方. .(2) (2) 对对A A中两个不同元素中两个不同元素x x和和y,y,如果如果y y覆盖覆盖x x, ,则用一条线段连接则用一条线段连接 x x 和和 y.y.例例7.197.19 画出偏序集画出偏序集1,
17、2,3,1,2,3,9,R,9,R整除整除 和和 的哈斯图的哈斯图. .解解: :它们的哈斯图分别为图它们的哈斯图分别为图A,A,图图B B表示如下表示如下: : 847236951图图A Aa,ba,b,cabb,cca,c 图图B B13例例例7.207.20 已知偏序集已知偏序集的哈斯图如下的哈斯图如下: :求集合求集合A A和关系和关系R R的表达式的表达式. .aedfhgbc解解 A=a, b, c, d, e, f, g, h,A=a, b, c, d, e, f, g, h, R R=,I IA.A.14特殊元素定义定义7.247.24 设设A, 为偏序集为偏序集, , B B
18、 A, yA, y B.B.(1)(1) 若若 x(xx(x ByBy x) x) 成立成立, ,则称则称 y y 是是B B的最小元的最小元; ;(2)(2) 若若 x(xx(x BxBx y) y) 成立成立, ,则称则称 y y 是是B B的最大元的最大元; ;(3)(3) 若若 x(xx(x BxBx yx=y) yx=y) 成立成立, ,则称则称 y y 是是B B的极小元的极小元; ;(4)(4) 若若 x(xx(x ByBy xx=yxx=y) )成立成立, ,则称则称 y y 是是B B的极大元的极大元. .注注: :(1)(1)极极大大 ( (极极小小) ) 元元未未必必是是
19、最最大大 ( (最最小小) ) 元元. .极极大大 ( (极极小小) ) 元元未未必必与与B B中中任何元素都可比任何元素都可比; ;( (2) 2) 对有限集对有限集B,B,极大极大( (极小极小) )元一定存在元一定存在, ,但最大但最大( (最小最小) )元不一定存在元不一定存在; ;(3) (3) 最大最大 ( (最小最小) ) 元如果存在元如果存在, ,必定是唯一的必定是唯一的; ; 而极大而极大 ( (极小极小) ) 元一般元一般不唯一不唯一. .但如果但如果B B中只有一个极大中只有一个极大 ( (极小极小) ) 元元, , 则它一定是则它一定是B B的最大的最大 ( (最小最小
20、) ) 元元. .15例解解: :极大元极大元:a:a, f, h; , f, h; 极小元极小元: a,b,c,g; : a,b,c,g; 无最大元和最小元无最大元和最小元. .例例7.217.21 求上例中求上例中A A的极大元的极大元, ,极小元极小元, ,最大元最大元, ,最小元最小元例例7.227.22 设设x x为集合为集合,A=P(x)-,A=P(x)- -x,-x,且且A A , ,若若 |x|= n, |x|= n, 问问: : ( (1)1)偏序集偏序集 A, R 是否有最大元是否有最大元? ? ( (2)2)偏序集偏序集 A, R 是否有最小元是否有最小元? ? ( (3
21、)3)偏序集偏序集 A, R 中极大元和极小元的一般形式是什么中极大元和极小元的一般形式是什么? ?解解: :首先首先, ,因因A A , , 故故n2,xn2,x中单个元素构成的子集都在中单个元素构成的子集都在 A A中中, ,他们他们在在 R R 下互相不可比下互相不可比, , 因此因此A A中无最大元和最小元中无最大元和最小元. .例例 x = 1,2,3, A = 1, 2, 3, 1,2, 1,3, 2,3 和和 x 不是不是A中元素中元素, 故故A中无最小元和最大元中无最小元和最大元1, 2, 3 都是极小元都是极小元; 1,2, 1,3, 2,3 都是极大元都是极大元16例 其次
22、考察其次考察(P(x),R(P(x),R ) )的哈斯图的哈斯图. . 其最低层是空集其最低层是空集 , ,记为第记为第0 0层层, ,由底向上由底向上, ,第第1 1层是单元集层是单元集, ,第第2 2层是二层是二元子集元子集, , , 第第n-1n-1层是层是x x的所有的所有n-1n-1元子集元子集, ,最顶层即第最顶层即第n n层层, ,只有一个顶只有一个顶点点x x. . 偏序集偏序集A, 的哈斯图是由的哈斯图是由 的哈斯图去掉第的哈斯图去掉第0 0层与第层与第n n层得到的层得到的, , 故故x x的所有单元集都是的所有单元集都是A,R 的极小元的极小元,x,x的所有的所有n-1n
23、-1元子集元子集都是都是A,R 的极大元的极大元. .17特殊元素定义定义7.257.25 设设A, 为偏序集为偏序集,B,B A, A, y y A A. . (1) (1) 若若 x(xx(x BxBx y)y)成立成立, , 则称则称y y为为B B的上界的上界; ;(2) (2) 若若 x(xx(x ByBy x x) )成立成立, ,则称则称y y为为B B的下界的下界; ;(3) (3) 令令 C Cy|yy|y为为B B的上界的上界,则称则称C C的最小元为的最小元为B B的最小上界或上确界的最小上界或上确界; ;(4) (4) 令令 D Dy|yy|y为为B B的下界的下界,则
24、称则称D D的最大元为的最大元为B B的最大下界或下确界的最大下界或下确界. .注注: :1.1.B B的最大元的最大元( (最小元最小元) )必定是必定是B B的上界的上界( (下界下界),),也是也是B B的上确界的上确界( (下确界下确界).).2. B2. B的上界和上确界都未必是的上界和上确界都未必是B B的最大元的最大元, ,因它们可能不在因它们可能不在B B中中. .同理同理, ,下下界和下确也未必是界和下确也未必是B B的最小元的最小元. .3. B3. B的上界的上界, ,上确界上确界, ,下界下界, ,下确界都可能不存在下确界都可能不存在. .但如果上确界但如果上确界( (下确界下确界) )存在存在, ,则它是唯一的则它是唯一的. .18
