离散数学-3-10 等价关系与等价类revised.ppt

《离散数学-3-10 等价关系与等价类revised.ppt》由会员分享，可在线阅读，更多相关《离散数学-3-10 等价关系与等价类revised.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 集合与关系3-10 等价关系与等价类 授课人：李朔Email:1一、等价关系一、等价关系等价关系是常用的重要关系，它使我们能对集合的元素分类，例如面积相等，相似，全等。其分类原则是每个元素仅属于某一类，且不同类之间没有公共元素。等价关系它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。目前对等价关系的研究是深入而完备的。P131 P131 定义定义3-10.13-10.1 设R为定义在集A上的一个关系，若R是自反的，对称的且传递的，则R称为等价关系等价关系。例如：平面上三角形集合中，三角形的相似关系是等价关系，命题逻辑里的命题集合中，命题的等价关系。2一、等

2、价关系P131 P131 例题例题1 1：A=1,2,3,4,R=,，,则易于验证R为A上等价关系。关系图：关系矩阵：每一结点都有自回路，说明每一结点都有自回路，说明R R是自是自反的。任意两结点间或没有弧线连反的。任意两结点间或没有弧线连接，或者成对弧出现，故接，或者成对弧出现，故R R是对称是对称的。同时可以知道的。同时可以知道R R是传递的。故是传递的。故R R是是T T上的等价关系。（需要逐个检上的等价关系。（需要逐个检查序偶）查序偶）主对角线全主对角线全1 1（自反）（自反）对称阵（对称）对称阵（对称）传递性需计算，可证明传递性需计算，可证明R=t(R)R=t(R)3一、等价关系P1

3、31P131例题例题2 2：设I为整数集R=x,yy(mod k)，则为上等价关系。其中其中xy(mod k)xy(mod k)叫做叫做x x与与y y模模k k相等，即相等，即x x除以除以k k的余数与的余数与y y除以除以k k的余的余数相等数相等.(.(x=sk+a,y=tk+a x=sk+a,y=tk+a,s s、t t为整数，为整数，a a为自然数，为自然数，-2=-1*3+1)-2=-1*3+1)证：因对任a,b,cI,1）a-a=0k,故R2）若a b(mod k),即a-b=tk则b-a=-tk，故b a(mod k)3）若a b(mod k)，b c(mod k),则a-b

4、=tk,b-c=sk则a-c=a-b+b-c=(s+t)k故a c(mod k)因此为等价关系。*1.人群集合上年龄相等是等价关系，而朋友关系一般不是等价关系。*2.集合上的恒等关系和全域关系为等价关系。4一、等价关系例例 设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的关系矩阵MR，关系图如下：M MR R的主对角线全为的主对角线全为1 1且是对且是对称阵，所以称阵，所以R R是自反的和对是自反的和对称的；还可以用二元关系称的；还可以用二元关系传递性的定义证明传递性的定义证明R R

5、是传递是传递的。故的。故R R是是A A上的等价关系。上的等价关系。在在R的的关关系系图图中中每每一一个个结结点点上上都都有有自自回回路路；每每两两个个结结点点间间如如果果有有边边，一一定定有有方方向向相相反反的的两两条条边边。所所以以R是是自自反反的的和和对对称称的的。与与前前面面一一样样，也也可可以以用用二二元元关关系系传传递递性性的的定定义义证明证明R是传递的。故是传递的。故R是是A上的等价关系。上的等价关系。从从图图中中不不难难看看出出，等等价价关关系系R的的关关系系图图被被分分为为三三个个互互不不连连通通的的部部分分。每每部部分分中中的的结结点点两两两两都都有有关关系系，不不同同部部

6、分分中中的的任任意意两两个个结结点则没有关系。点则没有关系。5二、等价类二、等价类P131 P131 定义定义3-10.23-10.2 设为集合上的等价关系，对任a，集合aR=xxA,xRa称为a关于的等价类等价类。n如例中如例中1R=4R=1,42R=3R=2,3对例对例，当k=3时，等价类为：0R=3R=-3 R=,-6,-3,0,3,6,1R=4R=-2 R=,-5,-2,1,4,7,2R=5R=-1 R=,-4,-1,2,5,8,P132 P132 定理定理3-10.1 3-10.1 若R为A上等价关系，对于a,bA，有aRbaRbaaR R=bbR R。6三、商集P132 P132

7、定义定义3-10.33-10.3 集合A上的等价关系R，其等价类集合称为A A关于关于R R的商集，记的商集，记A/RA/R.n例例1 1中商集AR1R,2R。n非空集A上全域关系EA是等价关系，其商集AEAAn非空集A上的恒等关系IA是等价关系，其商集 AIAxxA*由上可见，任两个等价类的交集为空由上可见，任两个等价类的交集为空，于是我们有下面的重要结果。7三、商集P133 P133 定理定理3-10.23-10.2 集合A上的等价关系，决定了A的一个划分，该划分就是商集划分就是商集A AR R。证明：把与aA的等价元素放在一起组成一集合aR，所有这些集合构成商集AR。下面证明它是A的一个

8、划分。1）ARa R aA，故 。2）任一aA，因R自反，故aRa，即aaR。即A的每一个元属于一个分块。3）证明A的每一个元仅属于一个分块。反之设 abR，acR且bR cR，则由aRb,aRc有bRc，即bR=cR与假设矛盾。故AR是A上对应于R的一个划分。8三、商集下面进一步证明，集合A上的一个划分确定了A的元素间等价关系。P133 P133 定理定理3-10.33-10.3 集A上的一个划分确定了A的元素间的一个等价关系。证明：设S=S1,S2,Sm为集A的一个划分。定义R：aRb当且仅当a,b在同一分块中。下面证明R为A上等价关系。1）因a与a在同一块中，故aRa，即R是自反的。2）

9、若a,b在同一块中，则b,a也在同一块中，故有aRb,bRa，即R对称。3）若a与b在同一块中，b与c在同一块中，则必有a与c在同一块中，即aRb,bRc必有aRc，故R传递的。可见R为A上等价关系。*上述结论实际提供了一个由划分构造等价关系的做法。9三、商集P134 P134 例题例题4 4：设A=a,b,c,d,e,S=a,b,c,d,e为A的划分，试由S确定A的等价关系R。解：我们用如下办法产生一个等价关系。a,ba,b=,cc=d,ede=,对上面产生集合求并，即为R。R,，,10三、商集例：例：设A=1,2,3，求出A上所有等价关系。解：先求出A的各种划分：仅一个分块的划分1，对应等价关系R1；仅两个分块的划分2，对应等价关系R2；仅两个分块的划分3，对应等价关系R3；仅两个分块的划分4，对应等价关系R4；有三个分块的划分5，对应等价关系R5。如图：因此：R1=,，IA=EA R2=,IA R3=,IA R4=,IA R5=,IA11三、商集P134 P134 定理定理3-10.43-10.4 设R1，R2为非空集A上的等价关系，则R R1 1R R2 2当且仅当当且仅当A AR R1 1A AR R2 2。12本课小结等价关系等价类商集 13作业P135(8)14