《离散数学-3-10_等价关系与等价类revised幻灯片》由会员分享，可在线阅读，更多相关《离散数学-3-10_等价关系与等价类revised幻灯片（14页珍藏版）》请在金锄头文库上搜索。
1、第三章 集合与关系,3-10 等价关系与等价类 授课人：李朔 Email:,1,一、等价关系,等价关系是常用的重要关系，它使我们能对集合的元素分类，例如面积相等，相似，全等。其分类原则是每个元素仅属于某一类，且不同类之间没有公共元素。等价关系它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。目前对等价关系的研究是深入而完备的。 P131 定义3-10.1 设R为定义在集A上的一个关系，若R是自反的，对称的且传递的，则R称为等价关系。 例如：平面上三角形集合中，三角形的相似关系是等价关系，命题逻辑里的命题集合中，命题的等价关系。,2,一、等价关系,P131 例题1：A
2、=1, 2, 3, 4, R=, , , ，, , , 则易于验证R为A上等价关系。 关系图： 关系矩阵：,3,每一结点都有自回路，说明R是自反的。任意两结点间或没有弧线连接，或者成对弧出现，故R是对称的。同时可以知道R是传递的。故R是T上的等价关系。（需要逐个检查序偶）,主对角线全1（自反） 对称阵（对称） 传递性需计算，可证明R=t(R),一、等价关系,P131例题2：设I为整数集R=R 2）若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 =
3、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，关系图如下：,5,MR的主对角线全为1且是对称阵，所以R是自反的和对称的；还可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。,在R的关系图中每一个结点上都有自回路；每两个结点间如果有边，一定有方向
4、相反的两条边。所以R是自反的和对称的。与前面一样，也可以用二元关系传递性的定义证明R是传递的。故R是A上的等价关系。 从图中不难看出，等价关系R的关系图被分为三个互不连通的部分。每部分中的结点两两都有关系，不同部分中的任意两个结点则没有关系。,二、等价类,P131 定义3-10.2 设为集合上的等价关系，对任a，集合aR=xxA, xRa称为a关于的等价类。 如例中 1R = 4R = 1,4 2R = 3R = 2,3 对例，当k=3时，等价类为： 0R = 3R= -3 R = , -6, -3, 0, 3, 6, 1R = 4R= -2 R =, -5, -2, 1, 4, 7, 2R
5、= 5R= -1 R =, -4, -1, 2, 5, 8, P132 定理3-10.1 若R为A上等价关系，对于a, bA，有aRbaR =bR。,6,三、商集,P132 定义3-10.3 集合A上的等价关系R，其等价类集合称为A关于R的商集，记A/R. 例1中商集AR1R , 2R。 非空集A上全域关系EA是等价关系，其商集AEAA 非空集A上的恒等关系IA是等价关系，其商集 AIAxxA *由上可见，任两个等价类的交集为空，于是我们有下面的重要结果。,7,三、商集,P133 定理3-10.2 集合A上的等价关系，决定了A的一个划分，该划分就是商集AR。 证明：把与aA的等价元素放在一起组
6、成一集合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的一个划分。,8,三、商集,下面进一步证明，集合A上的一个划分确定了A的元素间等价关系。 P133 定理3-10.3 集A上的一个划分确定了A的元素间的一个等价关系。 证明：设S=S1, S2, , Sm为集A的一个划分。定义R：aRb当且仅当a, b在同一分块中。下面证明R
7、为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上等价关系。 *上述结论实际提供了一个由划分构造等价关系的做法。,9,三、商集,P134 例题4：设A=a, b, c, d, e, S=a, b,c,d, e为A的划分，试由S确定A的等价关系R。 解：我们用如下办法产生一个等价关系。 a, ba, b = , , , cc = d, ede = , , , 对上面产生集合求并
8、，即为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=,IA,11,三、商集,P134 定理3-10.4 设R1，R2为非空集A上的等价关系，则R1R2当且仅当AR1AR2。,12,本课小结,等价关系 等价类 商集,13,作业,P135 (8),14,
