(1.5.7)--ch3—第六讲离散数学离散数学.pdf

《(1.5.7)--ch3—第六讲离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.5.7)--ch3—第六讲离散数学离散数学.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离离 散散 数数 学学 Discrete MathematicsDiscrete Mathematics 3-10 等价关系与等价类等价关系与等价类 1.等价关系等价关系(Equivalence Relations)设设R为定义在非空集合为定义在非空集合A上的一个关系上的一个关系,若若R 是是自反的、对称的和传递的自反的、对称的和传递的,则称则称R为为A上的上的等价关系等价关系.定义定义3.10.1 如如 (1)数的相等关系是任何数集上的等价关系数的相等关系是任何数集上的等价关系.(2)集合集合A上的恒等关系上的恒等关系,全域关系全域关系均是等价关系均是等价关系(3)三角形的全等关系三角形的全

2、等关系,三角形的相似关系三角形的相似关系是等价关系是等价关系 例例1.设设 A=1,2,3,4,A上的关系上的关系 R=,验证验证R是是 A上的等价关系上的等价关系 解解 1001011001101001(1)关系矩阵主对角线元素都是关系矩阵主对角线元素都是1,故故R是自反的是自反的;(2)关系矩阵是对称的关系矩阵是对称的,故故R是对称的是对称的;(3)从从R的序偶表达式中的序偶表达式中,可以看出可以看出R是传递的是传递的.如如,R,有有R,R 有有R,.写出写出R 的关系矩阵的关系矩阵 例例2 设设 Z 整数集整数集,定义定义 Z 上的上的同余关系同余关系R如下如下:R=|a,b Za-b=

3、km 则则R为为Z上的等价关系上的等价关系.R=|a,b Aab(modm)称为称为Z上的上的模模m同余关系同余关系.有时写成有时写成 证明证明:(1)a Z,有有:a-a=m 0,故故 R,(2)a,b Z,若若 R,则则 b-a=-mk,故故 R,(3)a,b,c Z,若若,R,则则 a-c=m(k+s),故故 R,即即a-b=mk,b-c=ms(k,s Z)即即a-b=mk(k为整数为整数),R是自反的是自反的.R是对称的是对称的.R是传递的是传递的.所以所以R为为Z 上的等价关系上的等价关系.定义定义3.10.2 设设 R 为集合为集合 A 上的等价关系上的等价关系,a A,集合集合

4、aR=x|x AaRx 称为元素称为元素a 形成的形成的 R 的的等价类等价类.由定义知由定义知,a 的等价类是的等价类是A中所有与中所有与a 等价的元素构成的集合等价的元素构成的集合.例例1中的等价类是中的等价类是:1=4=1,4 2=3=2,3 2.等价类等价类(Equivalence classes)例例 设设A=a,b,c,d,A上的关系上的关系,Ra aa bb ca cc cb bb ac bc ad d 则则R 是是 A上的等价关系上的等价关系 Ra,a b c Rb Rc Rdd 同一个等价类中元素均相互等价同一个等价类中元素均相互等价.不同等价类中的元素互不不同等价类中的元素

5、互不等价等价.等价类的性质等价类的性质(The Properties of Equivalence class)定理定理3.10.1 设设R为非空集合为非空集合A上的等价关系上的等价关系,则则(1)x A,xR是是A的非空子集的非空子集;(2)x,y A,若若 R当且仅当当且仅当xR=yR;(3)x,y A,若若 R,则则xR yR=;(4)xR|x A =A.定理定理3.10.2 集合集合A上的等价关系上的等价关系R,决定了决定了A的一个划分的一个划分,定义定义3.10.3 集合集合A上的等价关系上的等价关系R,其等价类集合其等价类集合aR|a A 称为称为A关于关于R的的商集商集,记作记作

6、A/R.即即 A/R=aR|a A R为为A上等价关系上等价关系.该划分就是商集该划分就是商集 A/R.如如 在集合在集合A=1,2,3,4上上,例例1中中A关于等价关系关于等价关系R的商集为的商集为 A/R=1R,2R=1,4 ,2,3 定理定理3.10.3 集合集合A的一个划分确定的一个划分确定A的元素间的一个等价关系的元素间的一个等价关系.由定理知集合由定理知集合A的划分的划分S=A1,A2,Am 所确定的所确定的A上的上的 等价关系等价关系R为为:R=(A1A1)(A2A2)(AmAm)例例3.设设A=a,b,c,d,A上的划分上的划分S=a,b,c,d 试由划分试由划分S 确定确定

7、A上的等价上的等价一个一个关系关系.R=(aa)(b,cb,c)(d d)=,定理定理3.10.4 设设R1和和R2为非空集合为非空集合A上的等价关系上的等价关系,则则 R1=R2当且仅当当且仅当A/R1=A/R2 例例 设设A=a,b,c,d,A上的划分上的划分 1,Sab cd 2,Sabcd 试求出等价关系试求出等价关系R1和和R2,使得使得R1和和R2的等价类分别是的等价类分别是S1和和S2的的划分块划分块.解解 定义定义 A上等价关系上等价关系 1,Ra ab bb cc bc cd d 则则 11/,A RSab cd定义定义 A上等价关系上等价关系 2,Ra ab bc cd d

8、 22/,A RSabcd例例.设设 A=1,2,3,求出求出A上所有的等价关系上所有的等价关系.解解 如下图如下图,先做出先做出A的所有划分的所有划分.R2=,U IA R3=,U IA R4=,U IA 这些划分与这些划分与A上的等价关系之间的一一对应是上的等价关系之间的一一对应是:1对应全域关系对应全域关系EA,5对应恒等关系对应恒等关系IA,2,3和和 4分别对应于等价关系分别对应于等价关系R2,R3 和和 R4,其中其中:1.设设R是集合是集合A上的对称关系和传递关系上的对称关系和传递关系,试证明：试证明：若对任意若对任意a A,存在存在b A,使得使得 R,则则R是等价关系是等价关系 2.设设R是非空集合是非空集合A上的关系上的关系,如果如果 1)对任意对任意a A,都有都有a R a;2)若若aRb,aRc,则则bRc;证明：证明：R是等价关系是等价关系.3.设设R是集合是集合A上的一个具有传递和自反性质的关系上的一个具有传递和自反性质的关系,T是是A上的关系上的关系,使得使得 T R且且 R,证明证明T是一个等价关系是一个等价关系.