离散数学-2-4-1(等价关系)[2014-10-13].ppt

主讲教师：常亮E-mail:changlQQ：737059669办公室电话:2291071手机导教师：周小川答疑时间：星期四上午10:20-11:50答疑地点：5教5楼软件工程教研室,离散数学,2.4特殊关系,关系可能具有的性质：自反反自反对称反对称传递特殊关系：具有上述某些性质的关系等价关系：自反、对称、传递偏序关系：自反、反对称、传递,2.4.1等价关系,定义2.21设R为非空集合A上的关系（即A并且RAA）。如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系。如果R,则称x与y等价.,例2.50,判断下列关系是否为等价关系R1:选修离散数学课程同学中的“同班”关系R2:幂集上的“”关系R3:直线间的“平行”关系R4:整数集上的“”关系R5:人群中的“朋友”关系,例2.52,给定一个正整数n，考虑整数集合Z上的整除关系R=|xZ，yZ，(xy)被n整除。证明R是Z上的等价关系。证明:（1）因此，R是自反的。（2）因此，R是对称的。（3）因此，R是传递的。综上，关系R为Z上的等价关系。证毕。xy(modn)：x-y可以被n整除，“x和y模n同余”。同余关系,例2.53,设集合A=a,b,c,d,e上的关系R1=,和R2=,，判断R1和R2是否为等价关系？用关系矩阵和关系图表示其中的等价关系。解:R1具有自反性、对称性和传递性，是等价关系。R2不是等价关系。,例2.53(续),设集合A=a,b,c,d,e上的关系R1=,和R2=,，判断R1和R2是否为等价关系？用关系矩阵和关系图表示其中的等价关系。解:相互等价的元素将关系矩阵分成了不同的块；相互等价的元素组成了关系图中相互连通的部分。,等价类,定义2.22设R是非空集合A上的等价关系，对于任意xA，称集合xR=y|yA且R为x关于R的等价类，或称为由x生成的一个R的等价类；并称其中的x为xR的生成元或代表元。即，xR表示由所有与x关于R等价的元素组成的集合。,例2.54,设R是集合A=1,2,3,4,5,6,7,8上的模3同余关系，用关系图表示该关系？并求R的所有等价类。解:集合A=1,2,3,4,5,6,7,8上的模3同余关系为R=,可以得到关系R的关系图如图所示。关于R的等价类如下1R=4R=7R=1,4,72R=5R=8R=2,5,83R=6R=3,6,等价类的性质,定理2.19设R为非空集合A上的等价关系，则：(1)对于任意xA，xR是A的非空子集.(2)对于任意x,yA，如果R,则xR=yR.(3)对于任意x,yA，如果R,则xRyR=.(4)xAxR=A.,商集,定义2.23设R是非空集合A上的等价关系；将由R的所有等价类构成的集合称为A关于R的商集,记A/R。A/R=xR|xA例2.25:令R是集合A=1,2,3,4,5,6,7,8上的模3同余关系；A关于R的商集为：A/R=1R,2R,3R=1,4,7,2,5,8,3,6A关于恒等关系的商集为：A/IA=1,2,3,4,5,6,7,8A关于全域关系的商集为：A/EA=1,2,3,4,5,6,7,8,商集的计算,例2.56对于集合A=a,b,c,d,e上的关系R=,，求A/R。解：根据等价类的定义有aR=bR=a,b,cR=c,dR=eR=d,e从而有A/R=a,b,c,d,e,划分,定义2.24对于非空集合A，如果某个集合S=S1,S2,Sm满足SiA且Si（i=1,2,m），SiSj=（ij；i=1,2,m；j=1,2,m），S1S2Sm=A，则将S称为A的一个划分，将S1,S2,Sm称为这个划分块。,例2.57,设集合A1,2,3,4，判断下列集合是否是A的划分1,2,3,41,2,3,41,2,3,1,4,1,2,3,41,2,31,2,3,4,例2.58,考察例2.55中集合A=1,2,3,4,5,6,7,8。商集A/R=1,4,7,2,5,8,3,6是否为A的划分？,等价类与划分(等价类-划分),定理2.20设R是非空集合A上的等价关系，则商集A/R是A的一个划分，将其称为由等价关系R导出的等价划分，其中每个等价类都是一个划分块。例2.59对于例2.56中集合A=a,b,c,d,e以及商集A/R=a,b,c,d,e。显然，A/R是集合A的一个划分。,等价类与划分(划分-等价类),定理2.21设S=S1,S2,Sm是非空集合A的一个划分，则由该划分确定的关系R=(S1S1)(S2S2)(SmSm)是A上的等价关系。将上述等价关系称为由划分S所导出的等价关系。,例2.60,对于集合A1,2,3,4的划分1,2,3,4，试构造A上的等价关系。解:根据定理2.21，构造如下关系R=(ll)(2,32,3)(44)=,=,显然，关系R是自反的、对称的和传递的，即，R是A上的等价关系。,练习,设A=1,2,3,4,5.1)求A的划分=1,2,3,4,5对应的等价关系。2)已知关系R=,，求R对应的划分。解:R=,A/R=1R,2R，其中1R=1,3，2R=2,4,5。,思考：对非空集合A来说，A上的等价关系与A的划