《离散数学等价关系与偏序关系ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学等价关系与偏序关系ppt课件.ppt（19页珍藏版）》请在三一办公上搜索。
1、离散数学,集合论,2/68,主要内容,集合代数二元关系函数,集合的基本概念集合的运算有穷集合的计数集合恒等式,有序对与笛卡儿积二元关系关系的运算关系的性质 关系的闭包等价关系与划分偏序关系,函数的定义与性质函数的复合与反函数双射函数与集合的基数,3/68,7.6 等价关系与划分,例7.16 设 A=1,2,8,定义 A 上的关系 R如下:验证R是A上的等价关系.,一.等价关系 定义7.15 设R为非空集合A上的关系.如果R是自反的,对称的和传递的,则称R为A上的等价关系.对等价关系R,若R,则称 x 等价于y,记为xy or xRy.,x,yA,若,则,故R是对称的.,x,y,zA,若,则,故
2、 R是传递的.,R是A上的一个等价关系.,4/68,等价类,定义 7.16 设 R 为非空集合A上的等价关系,xA,令称 xR为x在R下的等价类(简称为x的等价类),有时简记为 x.x 称为该等价类的代表元.注:一个等价类是A中在等价关系R下彼此等价的所有元素的集 合,等价类中各元素的地位是平等的,每个元素都可以作为 其所在等价类的代表元.例如,在上例中的等价关系R下,A中元素形成了三个等价类:1=4=7=1,4,7;2=5=8=2,5,8;3=6=3,6.,5/68,等价类的性质,定理7.14 设 R 为非空集合 A上的等价关系,则（1）xA,x是A的非空子集.（2）x,yA,如果xRy,则
3、 x=y（3）x,yA,如果x与y不具有关系 R,则 x 与 y 不相交.（4）x|xA=A证：(1)显然.(2)zx R R（R是对称的）RR R R zy,从而 x y 同理可得,y x.故 x=y,6/68,等价类的性质,(3)反证法.假设 xy,则存在 zxy.因而 z x 且z y,即RR.根据R的对称性和传递性,必有R.这与前提条件矛盾.故原命题成立.,(4)先证 再证 因此,7/68,商集与划分,定义7.17 设R为非空集合A上的等价关系,以R的所有等价类作为元素,形成的集合称为A关于R的商集,记为A/R,即:例如:例7.16中等价关系形成的商集为:A/R 1,4,7,2,5,8
4、,3,6,定义7.18 设A为非空集合,若A的子集族(P(A),是由A的一些子集形成的集合)满足下列条件:(1)(2)xy(x,y xyxy=)(3)则称是A的一个划分,而称中的元素为 A的划分块或类.,五.集合的划分,8/68,等价关系与划分,例7.17 设A=a,b,c,d,则 1=a,b,c,d和 2=a,b,c,d都是A的划分,而 3=a,a,b,c,d和4=,a,b,c都不是A的划分.注:给定非空有限集A上的一个等价关系R,在R下彼此等价的元素构成的子集便形成了A的一个划分,它其实就是商集A/R,其每个类(等价块)就是R的一个等价类;反之,任给A的一个 划分,可定义A上的关系R如下:
5、R=x,yAx与y在的同一个类中 可以验证R是A上的一个等价关系.可见A上的等价关系与A的划分是一一对应的.,9/68,例,例7.18 求A=1,2,3上所有的等价关系.解 先求出A的所有划分:1=1,2,3;2=1,2,3；3=2,1,3;4=3,1,2;5=1,2,3.与这些划分一一对应的等价关系是:1:全域关系EA 2:R2=,IA 3:R3=,IA 4:R4=,IA 5:恒等关系IA,10/68,7.7 偏序关系,偏序关系与偏序集定义7.19 设R为非空集合A上的关系.如果R是自反的,反对称的和传递的,则称 R 为 A上的偏序关系,记为.对一个偏序关系,如果,则记为 x y.注:1.集
6、合A上的恒等关系IA和空关系都是A上的偏序关系,但全域关系EA 一般不是A上的偏序关系.2.实数域上的小于等于关系（大于等于关系）,自然数域上的整除关系,集合的包含关系等都是偏序关系.,11/68,可比与不可比,注:在具有偏序关系的集合A中任二元素 x 和 y 之间必有下列四 种情形之一:xy,yx,x=y,x与y不可比.例 设A=1,2,3 是A上的整除关系,则:12,13,11,22,33,2 和 3 不可比;(2)是 A 上的大于等于关系,则:2 1,3 1,3 2,11,22,33.,定义7.20 设R为非空集合A上的偏序关系,定义,(1)x,yA,x y当且仅当 x y且 xy(2)
7、x,yA,x 与 y 可比当且仅当 x y 或 y x,12/68,偏序集,定义7.21 设R为非空集合A上的偏序关系,如果x,yA,x 与 y 都是可比的,则称R为A上的全序关系.例如 大于等于关系(小于等于关系)是全序集,但整除关系一般不是全序集.定义7.22 带有某种指定的偏序关系 的集合A称为偏序集,记为.例如 整数集Z和数的小于等于关系构成偏序集;集合A的幂集P(A)和集合的包含关系 构成偏序集.定义7.23 设 为偏序集,x,y A,如果 x y且不存在 z A,使得x z y,则称 y 覆盖 x.例如 A=1,2,4,6上的整除关系,有2覆盖1,4和6都覆盖2,但4不覆盖1,6不
8、覆盖4.,13/68,哈斯图,利用偏序关系的自反性,反对称性和传递性可简化偏序关系的关系图,得到偏序集的哈斯图.设有偏序集,其哈斯图的画法如下:(1)以 A 的元素作为顶点,适当排列各顶点的顺序,使得对 x,y A,若x y,则将 x 画在 y 的下方.(2)对A中两个不同元素x和y,如果y覆盖x,则用一条线段连接 x 和 y.例7.19 画出偏序集的哈斯图.,解:它们的哈斯图分别为图A,图B表示如下:,14/68,例,例7.20 已知偏序集的哈斯图如下:求集合A和关系R的表达式.,解 A=a,b,c,d,e,f,g,h,R=,IA.,15/68,特殊元素,定义7.24 设 为偏序集,B A,
9、yB.(1)若 x(xByx)成立,则称 y 是B的最小元;(2)若 x(xBxy)成立,则称 y 是B的最大元;(3)若 x(xBxyx=y)成立,则称 y 是B的极小元;(4)若 x(xByxx=y)成立,则称 y 是B的极大元.注:极大(极小)元未必是最大(最小)元.极大(极小)元未必与B中任何元素都可比;(2)对有限集B,极大(极小)元一定存在,但最大(最小)元不一定存在;(3)最大(最小)元如果存在,必定是唯一的;而极大(极小)元一般不唯一.但如果B中只有一个极大(极小)元,则它一定是B的最大(最小)元.,16/68,例,解:极大元:a,f,h;极小元:a,b,c,g;无最大元和最小
10、元.,例7.21 求上例中A的极大元,极小元,最大元,最小元,例7.22 设x为集合,A=P(x)-x,且A,若|x|=n,问:(1)偏序集 是否有最大元?(2)偏序集 是否有最小元?(3)偏序集 中极大元和极小元的一般形式是什么?,解:首先,因A,故n2,x中单个元素构成的子集都在 A中,他们在 R下互相不可比,因此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 都是极大元,17/68,例,其次考察(P(x),R)的哈斯图.其最低层是空集,记为第0层,由底向上,第1
11、层是单元集,第2层是二元子集,第n-1层是x的所有n-1元子集,最顶层即第n层,只有一个顶点x.偏序集的哈斯图是由的哈斯图去掉第0层与第n层得到的,故x的所有单元集都是的极小元,x的所有n-1元子集都是的极大元.,18/68,特殊元素,定义7.25 设为偏序集,BA,yA.,(1)若 x(xBxy)成立,则称y为B的上界;(2)若 x(xByx)成立,则称y为B的下界;(3)令 Cy|y为B的上界,则称C的最小元为B的最小上界或上确界;(4)令 Dy|y为B的下界,则称D的最大元为B的最大下界或下确界.注:B的最大元(最小元)必定是B的上界(下界),也是B的上确界(下确界).2.B的上界和上确界都未必是B的最大元,因它们可能不在B中.同理,下界和下确也未必是B的最小元.3.B的上界,上确界,下界,下确界都可能不存在.但如果上确界(下确界)存在,则它是唯一的.,该休息啦,
