二元关系4.5等价关系

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,1,离散数学,Discrete Mathematics,主讲：陈哲云,青岛理工大学计算机工程学院,2013.,09,第,4,章 二元关系,二元关系,4.1,二元关系基本概念,(,重点,),4.2,关系的运算,4.3,关系的性质,(,重点,),4.4,关系的闭包,4.5,等价关系和偏序关系,(,重点及难点,),4.6,函数的基本概念,等价关系,本节内容主要说明,等价关系,和,集合的划分,(,分类,),之间的关系：,1.,等价关系,等价类,商集,集合的划分,2.,集合的划分,等价关系,等价关系,定义,等价关系：,设,A,上的二元关系,R,如果,R,是,自反的,对称的,，,传递的,，则称,R,为,等价关系,。,若,R,，称,x,与,y,等价,，记作,x,y,。,等价关系,例,1,数学中一些常见的等价关系：,1.,数理逻辑中的,公式等值,关系。,2.,无向图中“,点的连通”,关系。,3.,方程组的“,同解,”关系。,4.,代数系统中的“,同构,”关系。,等价关系,例,2,设集合,A=1,2,3,4,5,6,7,8,，,R,是,A,上的,模,3,同余,关系，请画出关系图。,1,4,7,2,5,8,3,6,等价类,定义,等价类,把具有相同性质的元素归为一类,设,R,是,A,上的等价关系，则称,x,R,=y|yAx,y,为,x,关于,R,的等价类。,等价类,例,3,设学生集合,A=a,b,c,d,e,f,R,1,和,R,2,分别是,A,上的“,同性别,”关系和“,同宿舍,”关系，求所有元素关于,R,1,和,R,2,的等价类，其中元素属性如下表：,解：,关于,R,1,的等价类：,关于,R,2,的等价类：,a,b,c,d,e,f,性别,女,男,男,女,男,女,宿舍,1-203,2-302,2-302,1-203,2-302,1-202,等价类,练习,试写出,A=1,2,3,4,5,6,7,8,上关于,模,3,同余关系,的等价类。,解：,1=4=7=,1,4,7,2,=5,=8=,2,5,8,3=6=,3,6,.,等价类,上述两例可以看出，,1.,等价关系实际上“,同类关系,”，是对集合按照某种性质进行的“,分类,”,。,2.,这种分类的特点是，各个不同类之间无共同元素，同类元素具有相同的特性，所有类的并集是原集合。,等价类,定理,设,R,是非空集合,A,上的等价关系,则,(1),x,A,x,(2),x,y,A,如果,xRy,则,x,=,y,(3),x,y,A,如果,x,y,则,x,y,=,(4),等价类或者完全相同，或者完全不同，其并集恰好是,A,商集,定义,商集,等价类的集合,A/R=x|x,A,性质,商集是集合的一个划分。,集合的划分,定义,集合的划分,把集合,A,分为若干非空子集,A,1,A,2,A,n,满足：,(1),当,i,j,时，,A,i,A,j,(2),则子集族,=A,1,，,A,2,，,，,A,n,称为,A,的一个划分，,A,i,(i=1,2,.,n),称为划分块。,A,1,A,6,A,5,A,4,A,3,A,2,A,集合的划分,例,4,分别给出学生集合,A=a,b,c,d,e,f,根据“,性别,”和,“,宿舍,”进行的划分,1,和,2,。,解：,1,=a,d,f,b,c,d =A,1,，,A,2,其中,A,1,=a,d,f,，,A,2,=b,d,c,2,=a,d,f,b,c,d =A,1,，,A,2,，,A,3,其中,A,1,=a,d,，,A,2,=f,，,A,3,=b,d,c,a,b,c,d,e,f,性别,女,男,男,女,男,女,宿舍,1-203,2-302,2-302,1-203,2-302,1-202,集合的划分,例,5,试给出集合,A=1,2,3,的所有划分。,1,2,3,1,1,2,3,5,1,2,3,2,1,2,3,4,1,2,3,3,集合的划分与等价关系,性质,1.,等价关系对应集合的一个划分。,等价关系,等价类,商集,集合的划分,2.,集合的一个划分对应着一个等价关系，这个等价关系的商集恰好是这个划分。,集合的划分与等价关系,例,6,试给出学生集合,A=a,b,c,d,e,f,关于“,性别,”的划分所对应的等价关系,R,。,解：,=,a,d,f,b,c,d,=A,1,，,A,2,R=,|x,y,同性别,=|x,y,A,1,x,y,A,2,=|x,y,A,1,|x,y,A,2,=A,1,A,1,A,2,A,2,a,b,c,d,e,f,性别,女,男,男,女,男,女,=,?,集合的划分与等价关系,性质,设,=A,1,，,A,2,，,，,A,n,为,A,的一个划分，,则,所对应的等价关系,R,可由如下方法得到：,R,=,|x,y,属于,的,同一划分块（,具有相同的性质,）,=A,1,A,1,A,2,A,2,.,A,n,A,n,=,小结,等价关系是“分类关系”。,集合的划分与等价关系本质上相同，可以相互导出。,(1),等价关系导出划分：,等价关系 商集,(2),集合的划分导出等价关系：,R,=,|x,y,属于,的,同一划分块（,具有相同的性质,）,=,集合的划分与等价关系,例,7,试写出集合,A=1,2,3,上的所有等价关系。,解：,1.,写出所有划分：,2.,写出每个划分对应的每个等价关系：,(,略,),1,2,3,1,1,2,3,5,1,2,3,2,1,2,3,4,1,2,3,3,作业,1.,给定集合,A,=1,2,3,4,，且,A,中的关系,R,：,R,=,求包含,R,的最小的等价关系,R,*,（,前已求,）,并写出商集,A,/,R,*,。,2.,给定集合,S=1,2,3,4,5,找出,S,上的等价关系,R,，此关系,R,能够产生划分,1,2,3,4,5,，并画出关系图。,3.,设,A,=1,2,3,4,，在,A,A,上定义等价关系,R,：,R,x+y,=,u+v,，,求,R,导出的划分,.,