离散数学教学课件03-集合与关系-3.7~3.10.pptVIP

第三章 集合与关系 Sets and Relations 第八节 等价关系 定义： 设R是集合A上的二元关系，若R是自反的、对称的和可传递的，则称R是A上的等价关系(Equivalence Relation)。 若x,y ? R，或者xRy，称x等价y，记做x~y 等价关系 因为R是自反的，因此R的关系图中每个结点都有有向环 因为R是对称的，因此R的关系图中的有向弧都是成对出现，即若有从a到b的弧，必定有从b到a的弧 因为R是传递的，因此若有从a到b的弧以及从b到c的弧，必定有从a到c的弧 综上所述，等价关系的有向图的每个分图都是完全图即每个结点都有有向环，每两个结点之间都有成对的弧 等价关系 例3.8.1 同学集合A={a, b, c, d, e, f}，A中的关系R是“住在同一个房间”。问：R是等价关系吗？ 答：是。 1) 任何一个人都和自己住在同一房间，因此R是自反的 2) 若x和y住在同一房间（即xRy），则y和x也住在同一房间（即yRx），因此R是对称的 3) 若x和y住在同一房间(xRy)，并且y和z住在同一房间(yRz)，则x和z住在同一房间(xRz)，因此R是传递的 等价关系 假设a和b住在同一房间，d和e和f住在同一房间，c住一间。则 R={a,a,a,b,b,a,b,b,c,c,d,d,d,e,d,f,e,d,e,e,e,f,f,d,f,e,f,f} 关系图为： 等价关系 整数集合Z中的相等关系、在全集U所有子集的集合中的相等关系，以及命题演算中的命题集合的?关系等都是等价关系 空集上的任意二元关系R是等价关系 等价关系 定义： 设m是一个正整数，a和b都是整数，若存在某整数k，使得a-b=km，则称a与b是模m等价，记为 a ? b (mod m)m叫作等价的模数 等价关系 定理：模m等价是任何集合A ? Z上的等价关系。 证明：如果A= ? ，那么模m等价是A上的等价关系。 若A ≠ ? ，设任意a,b,c ? A，将模m等价记为R 1) 因为 a – a = 0·m，因此R是自反的 2) 假设有aRb，则存在一个整数k，使得a-b=k·m， 则b-a=-k·m，所以有bRa，所以R是对称的 3) 假设有aRb和bRc，则存在整数p和q，使得a-b=p·m， b-c=q·m，所以a-c=(a-b)+(b-c)=(p+q)·m 因此R是传递的 综上所述，R是自反的、对称的和传递的，所以它是等价关系。 等价类 定义： 设R是非空集合A上的等价关系，对于任意a ? A，令[a]R = {x|x ? A ∧ aRx}称[a]R是a关于R的等价类(Equivalence Classes)，简称a的等价类，简记为[a]。称a为[a]R的表示元素。 若等价类个数有限，则R的不同等价类的个数叫作R的秩。 对于任意a ? A ， [a]R非空，因为a ? [a]R 等价类 例3.8.2 设A={a,b,c,d,e,f}, R={a,a,a,b,b,a, b,b,c,c,d,d,d,e,d,f,e,d,e,e, e,f,f,d,f,e,f,f}，则等价关系R的关系图是： 等价类 例3.8.3 若R是整数集合Z上的模4等价关系，则等价类有： [0]R = {…, -8, -4, 0, 4, 8, …} = [4]R = [-4]R = ……[1]R = {…, -7, -3, 1, 5, 9, …} = [5]R = [-3]R = ……[2]R = {…, -6, -2, 2, 6, 10, …} = [6]R = [-2]R = …… [3]R = {…, -5, -1, 3, 7, 11, …} = [7]R = [-1]R = ……每个等价类中的元素互相模4等价。 若R是整数集合Z上的模2等价关系，则等价类有[0]R = {…, -4, -2, 0, 2, 4, …} = [2]R = [-2]R = …… [1]R = {…, -3, -1, 1, 3, 5, …} = [3]R = [-1]R = …… 等价类 定理1：设R是非空集合A上的等价关系，对于任意a,b ? A aRb ? [a]=[b] 证明：1) 若[a]=[b]，则a ?[a]=[b]，所以bRa， 根据R的对称性，可知有：aRb 2) 若aRb，对于任意x ?[a]，有aRx，所以也有xRa 根据R的传递性，可知有xRb；根据R的对称性，可知有bRx 则x ?[b]，所以[a] ?[b] 同理可证：对于任意x ?[b]有x ?[a]，即[b] ?[a] 所以： [a]=[b] 等价类 定理2：设R是非空集合A上的