等价关系和划分

,离散数学,单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,南京信息工程大学数理学院,*,南京信息工程大学 离散数学教学组 制作,离 散 数 学,电 子 课 件,单击此处编辑母版标题,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,27 十一月 2024,南京信息工程大学数理学院,2,第三章 二元关系,3.1,基本概念,3.2,关系的合成,3.3,关系上的闭包运算,3.4,次序关系,3.5,等价关系和划分,27 十一月 2024,南京信息工程大学数理学院,3,第,3-5,讲 等价关系和划分,1.,等价关系,2.,划分,3.,划分的积与和,4.,第,3-5,讲 作业,27 十一月 2024,南京信息工程大学数理学院,4,等价关系是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。,定义,1,设,R,A,A,，,如果,R,是,自反的、对称的和传递,的，则称,R,是,A,上的等价关系,。设,R,是,等价关系,，若,x,y,R,，称,x,等价于,y,。,例如：三角形的相似关系是等价关系,等价关系的特性,关系矩阵：,主对角线全为,1,且是,对称矩阵,；,关系图：每一个结点上都有自回路；每两个不同结点间或没有弧线连接，或有成对弧出现。,1,、等价关系,27 十一月 2024,南京信息工程大学数理学院,5,例,1,设,A,=,1,2,3,4,5,，,R,是,A,上的二元关系，,R,=,1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5,，,证明,R,是,A,上的等价关系,。,证明：,写出,R,的,关系矩阵,M,R,如下：,M,R,的主对角线全为,1,且是对称阵，所以,R,是自反的和对称的；还可以用二元关系传递性的定义证明,R,是传递的。故,R,是,A,上的等价关系。,27 十一月 2024,南京信息工程大学数理学院,6,在,R,的,关系图,中每一个结点上都有自回路；每两个不同结点间如果有边，一定有方向相反的两条边。所以,R,是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明,R,是传递的。故,R,是,A,上的等价关系。,注：等价关系,R,的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。,27 十一月 2024,南京信息工程大学数理学院,7,定义,2,设,x,和,y,是,两个整数，,k,是一个正整数，若,x,，,y,用,k,除的余数相等,，就称,x,和,y,模,k,同余,，也称,x,和,y,模,k,等价,。记为,x,y,(mod,k,),设,x,(,y,),用,k,除的商为,t,1,(,t,2,),，余数为,a,1,(,a,2,),，数学上将,x,(,y,),表示成为：,x,=,k,t,1,a,1,，,t,1,I,，,a,1,I,且,0,a,1,k,。,y,=,k,t,2,a,2,，,t,2,I,，,a,2,I,且,0,a,2,k,。,若,x,，,y,用,k,除的余数相等，,x,-,y,=,k,(,t,1,-,t,2,),，,t,1,-,t,2,I,。,即,x,-,y,可以被,k,整除。所以，,x,和,y,模,k,同余还可以描述为：,x,-,y,可以被,k,整除,。,27 十一月 2024,南京信息工程大学数理学院,8,例,2,设,R,=,x,y,x,I,y,I,x,y,（,mod,k,）,是整数集合,I,上的二元关系。,证明,R,是等价关系,。,证明：,设,a,b,c,是任意的整数。,因为,a,-,a,=,k,0,，所以,a,a,mod,k,，,a,a,R,。故,R,是,自反的,。,若,a,b,R,，,a,b,mod,k,，,a,-,b,=,k,t,，,t,I,，,b,-,a,=,-,(,a,-,b,)=,k,(,t,),，,t,I,，,b,a,mod,k,，,b,a,R,。故,R,是,对称的,。,若,a,b,R,且,b,c,R,，,a,-,b,=,k,t,1,，,t,1,I,，,b,-,c,=,k,t,2,，,t,2,I,，,a,-,c,=(,a,-,b,)+(,b,-,c,)=,k,t,1,+,k,t,2,=,k,(,t,1,+,t,2,),，,t,1,+,t,2,I,，,a,c,R,，故,R,是,传递的,。,所以,R,是整数集合,I,上的等价关系。,27 十一月 2024,南京信息工程大学数理学院,9,定义,3,设,R,是,A,上的等价关系,，,x,A,，集合,y,y,A,xRy,叫做,x,形成的,R,等价类,。记为,x,R,在例,1,中，等价关系,R,等价类为：,1,R,=2,R,=,1,2,，,3,R,=4,R,=,3,4,，,5,R,=,5,。在,R,的关系图中，,三个互不连通的部分，每一部分中的所有结点构成一个等价类,。,上述,模,3,等价关系的等价类叫模,3,等价类,，模,3,等价类有以下三个：,0,R,=,，,6,，,3,，,0,，,3,，,6,，,1,R,=,，,5,，,2,，,1,，,4,，,7,，,2,R,=,，,4,，,1,，,2,，,5,，,8,，,定理,1,设,R,是,X,上的等价关系，,x,X,，则有,x,R,X,x,x,R,27 十一月 2024,南京信息工程大学数理学院,10,注：,等价关系的任何等价类是该等价关系前域,(,或陪域,),的子集,。,例如，模,3,等价类是整数集合的子集：,0,R,I,，,1,R,I,，,2,R,I,。,任何等价类是非空集合,。,x,形成的,R,等价类,x,R,至少有一个元素,x,。,例如，在模,3,等价类中，,0,0,R,，,1,1,R,，,2,2,R,。,定理,2,设,R,是,X,上的等价关系，对于,X,的任意元素,a,和,b,，,aRb,的充分必要条件是,a,R,=,b,R,证明：,设,aRb,，下证,a,R,=,b,R,c,a,R,，,aRc,，由,R,的对称性有,cRa,，由条件,aRb,和,R,的传递性得,cRb,，再根据,R,的对称性有,bRc,，,c,b,R,，故,a,R,b,R,。,类似地可以证明,b,R,a,R,。这就证明了,a,R,=,b,R,。,设,a,R,=,b,R,，下证,aRb,。,由定理,1,知,a,a,R,，因为,a,R,=,b,R,，所以,a,b,R,，,bRa,，由,R,的对称性有,aRb,。,27 十一月 2024,南京信息工程大学数理学院,11,定义,4,设,A,是非空集合，,=,S,1,，,S,2,，,，,S,m,，,S,i,，,i,=1,m,，且满足：,S,i,，,S,i,A,S,1,S,2,S,m,=,A,则称,是,A,的一个覆盖,。,定义,5,设,A,是非空集合，,=,S,1,，,S,2,，,，,S,m,，,S,i,，,i,=1,m,，,是,A,的一个覆盖，满足,S,i,S,j,=,，,i,j,，则称,是,A,的一个划分,。称,S,i,，,i,=1,m,，是,A,的划分块。,定义中的,“,S,i,S,j,=,，,i,j,”,是指,中的元素两两互不相交。,2,、划分,27 十一月 2024,南京信息工程大学数理学院,12,例,3,设,A,=,a,b,c,，以下是,A,的子集构成的集合：,S,=,a,b,b,c,Q,=,a,a,b,a,c,D,=,a,b,c,G,=,a,b,c,E,=,a,b,c,F,=,a,a,c,试确定,哪些集合是,A,的覆盖？哪些集合是,A,的划分？哪些集合既不是覆盖，也不是划分？,解：,S,和,Q,是,A,的覆盖，但不是划分；,D,、,G,和,E,是,A,的覆盖，也是划分；,F,不是,A,的覆盖，也不是划分。,27 十一月 2024,南京信息工程大学数理学院,13,集合,G,=,a,b,c,是,单元素集,，它有一个元素,a,b,c,。对单元素集,a,b,c,，认为它的元素的并集就是,a,b,c,，同时也认为它的元素是两两互不相交的。所以集合,G,=,a,b,c,是,A,的划分。,在,A,的所有划分中基数最大的划分叫做,A,的,最大划分,，基数最小的划分叫做,A,的,最小划分,。,在例,3,中，,E,是,A,的最大划分，,G,是,A,的最小划分。,27 十一月 2024,南京信息工程大学数理学院,14,例,4,设,A,=,1,2,3,，试,确定,A,的所有划分,。,解：,有,一个划分块,的划分是：,1,2,3,有,两个划分块,的划分是：,1,2,3,2,1,3,3,1,2,有,三个划分块,的划分是：,1,2,3,图,3.9,是,A,的所有划分的示意图。,(a),表示有一个划分块的划分,1,2,3,。,(b),、,(c),和,(d),表示有两个划分块的划分,1,2,3,、,2,1,3,和,3,1,2,。,(e),表示有三个划分块的划分,1,2,3,。,27 十一月 2024,南京信息工程大学数理学院,15,定理,3,设,R,是,X,上的等价关系，,X,关于,R,的商集,X,/,R,是,X,的一个划分,。,定义,6,设,R,是,X,上的等价关系，,R,的,所有等价类组成的集,合,x,R,x,X,叫做,X,关于,R,的商集,。记为,X,/,R,。,在例,1,中，等价关系,R,有三个等价类：,1,R,=2,R,=,1,2,，,3,R,=4,R,=,3,4,，,5,R,=,5,，,A,关于,R,的商集,A,/,R,=,1,R,，,2,R,，,5,R,=,1,2,，,3,4,，,5,模,3,等价关系,R,的等价类有以下三个：,0,R,，,1,R,和,2,R,，由它确定的,整数集合,I,关于,R,的商集,I,/,R,=,0,R,，,1,R,，,2,R,27 十一月 2024,南京信息工程大学数理学院,16,定理,4,设,S,=,S,1,，,S,2,，,，,S,m,是,X,的一个划分，,R,=,x,y,|,x,和,y,在同一个划分块中,，,则,R,是,X,上的等价关系,。,证明：,设,x,X,=,S,1,S,2,S,m,，因为,S,是,X,的一个划分，所以存在惟一的划分块,S,j,S,，使,x,S,j,，于是有,x,x,R,，即,R,是自反的。,设,x,y,R,，,x,和,y,在某个划分块,S,j,中，则,y,和,x,也在划分块,S,j,中，所以,y,x,R,，即,R,是对称的。,设,x,y,R,y,z,R,x,和,y,在,S,i,中且,y,和,z,在,S,j,中,y,S,i,S,j,，因为,S,是,X,的一个划分，其中元素两两互不相交，故必有,S,i,=,S,j,x,和,z,在,S,j,中,x,z,R,，即,R,是传递的。,将定理,4,中的等价关系,R,叫做,划分,S,导出的等价关系,。划分,S,导出的等价关系,R,也可以表示为：,R,=(,S,1,S,1,),(,S,2,S,2,),(,S,m,S,m,),27 十一月 2024,南京信息工程大学数理学院,17,例,5,设,X,=,1,2,3,4,，,X,的划分,S,=,1,，,2,3,，,4,，试写出,S,导出的等价关系,R,。,解：,R,=,1,1,2,2,2,3,3,2,3,3,4,4,=,1,1,2,3,2,3,4,4,可以验证,R,是,X,上的等价关系。,定理,5,设,R,，,S,是,集合,X,上的等价关系，则,R,=,S,当且仅当,X,/,R,=,X,/,S,证明：,设,R,=,S,，证明,X,/,R,=,X,/,S,。,先证,x,X,，,x,R,=,x,S,a,x,R,xRa,xSa,a,x,S,，所以,x,R,x,S,。,类似地可以证明,x,S,x,R,，这就证明了,x,R,=,x,S,。,27 十一月 2024,南京信息工程大学数理学院,18,再证,X,/,R,=,X,/,S,。,x,R,X,/,R,，,x,R,=,x,S,X,/,S,，即,x,R,X,/,S,，,所以,X,/,R,X,/,S,。,类似地可以证明,X,/,S,X,/,R,，于是,X,/