离散数学-3-10等价关系与等价类rev

《离散数学-3-10等价关系与等价类rev》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、P131例题2：设I为整数集R={R2）若ab(modk),即a-b=tk则b-a=-tk，故ba(modk)3）若ab(modk)，bc(modk),则a-b=tk,b-c=sk则a-c=a-b+b-c=(s+t)k故ac(

4、modk)因此Ｒ为等价关系。*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，关系图如下：MR的主对角线全为1且是对称阵，所以R是自反的和对称的；还可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。在R

5、的关系图中每一个结点上都有自回路；每两个结点间如果有边，一定有方向相反的两条边。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。从图中不难看出，等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。5二、等价类P131定义3-10.2设Ｒ为集合Ａ上的等价关系，对任aＡ，集合[a]R={xxA,xRa}称为a关于Ｒ的等价类。如例１中[1]R=[4]R={1,4}[2]R=[3]R={2,3}对

6、例２，当k=3时，等价类为：[0]R=[3]R=[-3]R={,-6,-3,0,3,6,}[1]R=[4]R=[-2]R={,-5,-2,1,4,7,}[2]R=[5]R=[-1]R={,-4,-1,2,5,8,}P132定理3-10.1若R为A上等价关系，对于a,bA，有aRb[a]R=[b]R。6三、商集P132定义3-10.3集合A上的等价关系R，其等价类集合称为A关于R的商集，记A/R.例1中商集A／R＝{[1]R,[2]R}。非空集A上全域关系EA是等价关系，其商集A／E

7、A＝{A}非空集A上的恒等关系IA是等价关系，其商集A／IA＝{{x}xA}*由上可见，任两个等价类的交集为空，于是我们有下面的重要结果。7三、商集P133定理3-10.2集合A上的等价关系，决定了A的一个划分，该划分就是商集A／R。证明：把与aA的等价元素放在一起组成一集合[a]R，所有这些集合构成商集A／R。下面证明它是A的一个划分。1）A／R＝{[a]RaA}，故。2）任一aA，因R自反，故aRa，即a[a]R。即A的每一个元属于一个分块。3）证明A的每一个元仅属于一个分块。反之设a

8、[b]R，a[c]R且[b]R[c]R，则由aRb,aRc有bRc，即[b]R=[c]R与假设矛盾。故A／R是A上对应于R的一个划分。8三、商集下面进一步证明，集合A上的一个划分确定了A的元素间等价关系。P133定理3-10.3集A上的一个划分确定了A的元素间的一个等价关系。证明：设S={S1,S2,,Sm}为集A的一个划分。定义R：aRb当且仅当a,b在同一分块中。下面证明R为A上等价关系。1）因a与a在同一块中，故aRa，即R是