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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,4.5,等价关系与偏序关系,等价关系的定义与实例,等价类及其性质,商集与集合的划分,等价关系与划分的一一对应,偏序关系,偏序集与哈斯图,偏序集中的特定元素,1,等价关系的定义与实例,定义,设,R,为非空集合上的关系,.,如果,R,是自反的、对称的和传递的,则称,R,为,A,上的,等价关系,.,设,R,是一个等价关系,若,R,称,x,等价于,y,记做,x,y,.,实例,设,A,=1,2,8,如下定义,A,上的关系,R,：,R,=|,x,y,A,x,y,(mod,3),其中,x,y,(mod,3),叫做,x,与y,模,3,相等,即,x,除以,3,的余数与,y,除以,3,的余数相等,.,2,等价关系的验证,验证模,3,相等关系,R,为,A,上的等价关系,因为,x,A,有,x,x,(mod,3),x,y,A,若,x,y,(mod,3),则有,y,x,(mod,3),x,y,z,A,若,x,y,(mod,3),y,z,(mod,3),则有,x,z,(mod,3),自反性、对称性、传递性得到验证,3,A,上模,3,等价关系的关系图,设,A,=1,2,8,R,=|,x,y,A,x,y,(mod,3),4,等价类,定义,设,R,为非空集合,A,上的等价关系,x,A,，令,x,R,=,y,|,y,A,xRy,称x,R,为,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,等价类的性质,定理,1,设,R,是非空集合,A,上的等价关系,则,(1),x,A,x,是,A,的非空子集,.(2),x,y,A,如果,x R y,则,x,=,y,.(3),x,y,A,如果,x y,则,x,与,y,不交,.(4),x,|,x,A,=,A,，,即所有等价类的并集就是,A,.,6,实例,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,83,6=1,2,8,7,商集,定义,设,R,为非空集合,A,上的等价关系,以,R,的所有等价类作为元素的集合称为,A,关于,R,的,商集,记做,A,/,R,A,/,R,=,x,R,|,x,A,实例,A,=1,2,8,A,关于模,3,等价关系,R,的商集为,A/R,=1,4,7,2,5,8,3,6,A,关于恒等关系和全域关系的商集为：,A/I,A,=1,2,8,A/E,A,=1,2,8,8,集合的划分,定义,设,A,为非空集合,若,A,的子集族,(,P,(,A,),满足下面条件：,(1),(2),x,y,(,x,y,x,y,x,y,)(3),=,A,则称,是,A,的一个,划分,称,中的元素为,A,的,划分块,.,9,例题,例,1,设,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,的划分,.,为什么？,10,等价关系与划分的一一对应,商集,A,/,R,就是,A,的一个划分,不同的商集对应于不同的划分,任给,A,的一个划分,如下定义,A,上的关系,R,：,R,=|,x,y,A,x,与,y,在,的同一划分块中,则,R,为,A,上的等价关系,且该等价关系确定的商集就是,.,例,2,给出,A,1,2,3,上所有的等价关系,求解思路：先做出,A,的所有,划分,然后根据划分写,出对应的等价关系,.,11,等价关系与划分之间的对应,1,2,和,3,分别对应等价关系,R,1,R,2,和,R,3,.,R,1,=,I,A,，,R,2,=,I,A,R,3,=,I,A,4,对应于,全域关系,E,A,，,5,对应于,恒等关系,I,A,12,实例,例,3,设,A,=1,2,3,4,，在,A,A,上定义二元关系,R,：,R,x+y,=,u+v,，,求,R,导出的划分,.,解,A,A,=,13,实例（续）,根据,的,x,+,y,=2,3,4,5,6,7,8,将,A,A,划分成,7,个,等价类：,(,A,A,),/,R,=,14,偏序关系,定义,非空集合,A,上的,自反,、反对称和,传递,的关系，称为,A,上的,偏序关系,，记作,.,设,为偏序关系,如果,则记作,x,y,读作,x,“,小于或等于”,y,.,实例,集合,A,上的恒等关系,I,A,是,A,上的偏序关系,.,小于或等于关系,整除关系和包含关系也是相应集合上的偏序关系,.,15,相关概念,x,与,y,可比,：设,R,为非空集合,A,上的偏序关系,x,y,A,x,与,y,可比,x,y,y,x,.,结论：任取两个元素,x,和,y,可能有下述情况：,x,y,(,或,yx,),x,y,x,与,y,不是可比的,.,全序关系,：,R,为非空集合,A,上的偏序,x,y,A,x,与,y,都是可比的，则称,R,为,全序,（或,线序,）,实例：数集上的小于或等于关系是全序关系,整除关系不是正整数集合上的全序关系,16,覆盖,：设,R,为非空集合,A,上的偏序关系,x,y,A,如果,x,y,且不存在,z,A,使得,x,z,y,则称,y,覆盖,x,.,实例：,1,2,4,6,集合上的整除关系,2,覆盖,1,4,和,6,覆盖,2.,4,不覆盖,1.,相关概念（续）,17,偏序集与哈斯图,定义,集合,A,和,A,上的偏序关系,一起叫做,偏序集,记作,.,实例：整数集和小于等于关系构成偏序集,，幂集,P,(,A,),和包含关系构成偏序集,.,哈斯图,：利用偏序自反、反对称、传递性简化的关系图,特点：每个结点没有环，两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前，具有覆盖关系的两个结点之间连边,18,哈斯图实例,例,4 ,19,A,=,a,b,c,d,e,f,g,h,R,=,I,A,哈斯图实例（续）,例,5,已知偏序集,的哈斯图如右图所示,试求出集合,A,和关系,R,的表达式,.,20,偏序集的特定元素,定义,设,为偏序集,B,A,y,B,.(1),若,x,(,x,B,y,x,),成立,则称,y,为,B,的,最小元,.(2),若,x,(,x,B,x,y,),成立,则称,y,为,B,的,最大元,.(3),若,x,(,x,B,x,y,),成立,则称,y,为,B,的,极小元,.(4),若,x,(,x,B,y,x,),成立,则称,y,为,B,的,极大元,.,21,特殊元素的性质,对于有穷集，极小元和极大元必存在，可能存在,多个,.,最小元和最大元不一定存在，如果存在一定惟一,.,最小元一定是极小元；最大元一定是极大元,.,孤立结点既是极小元，也是极大元,.,22,定义,设,为偏序集,B,A,y,A,.,(1),若,x,(,x,B,x,y,),成立,则称,y,为,B,的,上界,.(2),若,x,(,x,B,y,x,),成立,则称,y,为,B的,下界,.(3),令,C,y,|,y,为,B,的上界,则称,C,的最小元为,B,的,最小上界,或,上确界,.(4),令,D,y,|,y,为,B,的下界,则称,D,的最大元为,B,的,最大下界,或,下确界,.,偏序集的特定元素,(,续,),23,下界、上界、下确界、上确界不一定存在,下界、上界存在不一定惟一,下确界、上确界如果存在，则惟一,集合的最小元就是它的下确界，最大元就是它的上确界；反之不对,.,特殊元素的性质,24,实例,例,6,设偏序集,如,下图所示，,求,A,的极小元、最小元、极大元、最大元,.,设,B,b,c,d,求,B,的下界、上界、下确界、上确界,.,极小元：,a,b,c,g,；,极大元：,a,f,h,；,没有最小元与最大元,.,B,的下界和最大下界都,不存在,上界有,d,和,f,最小上界为,d,.,25,