离散数学-3-10等价关系与等价类re.ppt
1,第三章 集合与关系,3-10 等价关系与等价类 授课人：李朔,2,一、等价关系,等价关系是常用的重要关系，它使我们能对集合的元素分类，例如面积相等，相似，全等。其分类原则是每个元素仅属于某一类，且不同类之间没有公共元素。等价关系它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。目前对等价关系的研究是深入而完备的。P131 定义3-10.1 设R为定义在集A上的一个关系，若R是自反的，对称的且传递的，则R称为等价关系。例如：平面上三角形集合中，三角形的相似关系是等价关系，命题逻辑里的命题集合中，命题的等价关系。,3,一、等价关系,P131 例题1：A=1,2,3,4,R=,，,则易于验证R为A上等价关系。关系图：关系矩阵：,每一结点都有自回路，说明R是自反的。任意两结点间或没有弧线连接，或者成对弧出现，故R是对称的。同时可以知道R是传递的。故R是T上的等价关系。（需要逐个检查序偶）,主对角线全1（自反）对称阵（对称）传递性需计算，可证明R=t(R),4,一、等价关系,P131例题2：设I为整数集R=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=tk,b-c=sk则a-c=a-b+b-c=(s+t)k故a c(mod k)因此为等价关系。*1.人群集合上年龄相等是等价关系，而朋友关系一般不是等价关系。*2.集合上的恒等关系和全域关系为等价关系。,5,一、等价关系,例 设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，关系图如下：,MR的主对角线全为1且是对称阵，所以R是自反的和对称的；还可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。,在R的关系图中每一个结点上都有自回路；每两个结点间如果有边，一定有方向相反的两条边。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。从图中不难看出，等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。,6,二、等价类,P131 定义3-10.2 设为集合上的等价关系，对任a，集合aR=xxA,xRa称为a关于的等价类。如例中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 定理3-10.1 若R为A上等价关系，对于a,bA，有aRbaR=bR。,7,三、商集,P132 定义3-10.3 集合A上的等价关系R，其等价类集合称为A关于R的商集，记A/R.例1中商集AR1R,2R。非空集A上全域关系EA是等价关系，其商集AEAA非空集A上的恒等关系IA是等价关系，其商集 AIAxxA*由上可见，任两个等价类的交集为空，于是我们有下面的重要结果。,8,三、商集,P133 定理3-10.2 集合A上的等价关系，决定了A的一个划分，该划分就是商集AR。证明：把与aA的等价元素放在一起组成一集合aR，所有这些集合构成商集AR。下面证明它是A的一个划分。1）ARa R aA，故。2）任一aA，因R自反，故aRa，即aaR。即A的每一个元属于一个分块。3）证明A的每一个元仅属于一个分块。反之设 abR，acR且bR cR，则由aRb,aRc有bRc，即bR=cR与假设矛盾。故AR是A上对应于R的一个划分。,9,三、商集,下面进一步证明，集合A上的一个划分确定了A的元素间等价关系。P133 定理3-10.3 集A上的一个划分确定了A的元素间的一个等价关系。证明：设S=S1,S2,Sm为集A的一个划分。定义R：aRb当且仅当a,b在同一分块中。下面证明R为A上等价关系。1）因a与a在同一块中，故aRa，即R是自反的。2）若a,b在同一块中，则b,a也在同一块中，故有aRb,bRa，即R对称。3）若a与b在同一块中，b与c在同一块中，则必有a与c在同一块中，即aRb,bRc必有aRc，故R传递的。可见R为A上等价关系。*上述结论实际提供了一个由划分构造等价关系的做法。,10,三、商集,P134 例题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,，,11,三、商集,例：设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=,IA,12,三、商集,P134 定理3-10.4 设R1，R2为非空集A上的等价关系，则R1R2当且仅当AR1AR2。,13,本课小结,等价关系等价类商集,14,作业,P135(8),
