2.1等价关系与划分ppt课件

1、7.6 7.6 等价关系与划分等价关系与划分 等价关系是一类重要的关系。 定义7.15(等价关系) 设R非空集合上的关系，如果R是自反的、对称的和传递的，则称R为A上的等价关系。 设R是一个等价关系，假设R，称x等价于y，记作xy。 例例 设设A=1,2,3A=1,2,3，R1R1，R2R2，R3R3是是A A上的关系上的关系 R1=, R1=, R2=, R2=,， R3=, R3=,例 设A为某班学生的集合，讨论下列关系是否为等价关系。 R1=|x, yA x与y同年生 R2=|x, yA x与y同姓 R3=|x, yA x的年龄比y小解：R1是等价关系； R2是等价关系； R3不是等价关

2、系； 如tsr(R)必为一个等价关系 例 A=1,2,3，A上的关系R=, tsr(R)=,通过闭包运算将任意的关系R构造成为一个等价关系 对R求三种闭包共有6种顺序，问每种顺序的运算结果是否一定为等价关系？ 不一定。 由于对称闭包不一定保持关系的传递性，因此先求传递闭包后求对称闭包得到的关系不一定是等价关系 例 A=1,2,3，A上的关系R=, str(R)=IA, 显然str(R)不是等价关系 用闭包运算去构造等价关系时，传递闭包运算应该放在对称闭包运算的后面 例例 设设AN，R=|x, yAxy (mod 3) 为为A上上的关系，其中的关系，其中xy (mod 3)叫做叫做x与与y模模3

3、相等，其含义为相等，其含义为x除以除以3的余数与的余数与y除以除以3的余数相等。证明的余数相等。证明R为为A上的等上的等价关系。价关系。 证明证明: xA，有，有xx (mod 3)，即，即R，所以，所以R是是自反的。自反的。 x,yA，若，若xy (mod 3)，则有，则有yx (mod 3)。所。所以以R是对称的。是对称的。 x,y,zA，若，若xy (mod 3)，yz (mod 3)，则有，则有xz (mod 3)。所以。所以R是传递的。是传递的。 综上综上R为为A上的等价关系。上的等价关系。 例：已知A=P(X), CX, x, yA, R xyC。 证明R为A上的等价关系.证明：（

4、1）xA，由于xx=C R, 所以R是自反的。（2）x,yA，RxyCyxCR, 所以R是对称的。（3）x,y,zA，假设R，R， 则有xyC， yzC。 xz=(xy)(yz)C R. 所以R是传递的。 综上所证，R是A上的等价关系。 画出等价关系R=|x,yAxy(mod 3)的关系图 ，其中A=1,2,8。 不难看出，上述关系图被分为三个分离互不连通的部分。每部分中的数两两都有关系(模3相等)，位于不同部分中的数之间则没有关系。称每一部分中的顶点构成了一个等价类。 定义定义7.167.16等价类）等价类） 设设R R为非空集合上的等价关系，为非空集合上的等价关系，x xA A，令，令xR

5、=y|yxR=y|yAxRyAxRy，称，称xRxR为为x x关于关于R R的等价类，的等价类，简称为简称为x x的等价类，简记为的等价类，简记为xx。 说明：说明： x x的等价类是的等价类是A A中所有与中所有与x x等价的元素构成的集合。等价的元素构成的集合。 集合A=1,2,8上的等价关系 R=|x, yAxymod 3）等价类是： 1=4=7=1，4，7 2=5=8=2，5，8 3=6=3，6 将模3的等价关系加以推广，可以得到整数集合Z上的模n等价关系。 对于任意的整数x和y，定义模n相等关系： xyxymod n） 易证是整数集合Z上的等价关系。将Z中所有的整数根据它们除以n的余

6、数分类如下： 余数为0的数，其形式为nz，zZ 余数为1的数，其形式为nz+1，zZ 余数为n-1的数，其形式为nz+n-1，zZ 以上构成了n个等价类： i=n+i=2n+i=nz+i|zZ，i=0,1,n-1 定理定理7.147.14等价类的性质）等价类的性质） 设设R R为非空集合为非空集合A A上上的等价关系，那么的等价关系，那么 （1 1）xx是是A A的非空子集的非空子集 （2 2）x x，y yA A，如果，如果xRyxRy，那么，那么x=yx=y （3 3）x x，y yA A，如果，如果xRyxRy，那么，那么xx与与yy不交不交 （4 4）x|xx|xA =AA =A定理的

7、含义： （1）：任何等价类都是集合A的非空子集 （2和3）：在A中任何两个元素，它们的等价类相等或不相交，不能部分相交。 （4）：所有等价类的并集就是A （3和4）：等价关系将A划分成若干个互不相交的子集 例集合A=1,2,8上的等价关系R=|x, yAxymod 3） 等价类是1, 4, 7、2, 5, 8、3, 6 定义定义7.17商集设商集设R为非空集合为非空集合A上的等价关系，上的等价关系，以以R的所有等价类为元素的集合叫做的所有等价类为元素的集合叫做A在在R下的商集，下的商集，记作记作A/R，即，即A/R=xR|xA 例例 集合集合A=1,2,8上的等价关系上的等价关系R=|x, y

8、Axymod 3）等价类是等价类是1, 4, 7、2, 5, 8、3, 6。 所以所以A在在R下的商集为下的商集为1, 4, 7, 2, 5, 8, 3, 6。 A在在R下的商集也可写成下的商集也可写成1, 2, 3。 整数集整数集Z在模在模n等价关系下的商集是等价关系下的商集是 nz+i|zZ | i=0,1,n-1 或或0, 1, ., n-1 定义7.18划分设A为非空集合，若A的子集族P(A)，是A的子集构成的集合满足以下的条件： （1） （2）xyx，yxy xy=） 即中任意两个集合不相交 （3）=A，即中所有集合的并集等于A 则称是A的一个划分，称中的元素为A的划分块 例设例设A

9、=a,b,c,d，给定，给定1,2,3,4,5,6如下，如下，判别它们是否为判别它们是否为A的划分。的划分。 1= a，b，c ， d 2= a，b ， c ， d 3= a ， a，b，c，d 4= a，b ， c 5= ， a，b ， c，d 6= a， a ， b，c，d 其中1,2是A的划分，3,4,5,6不是A的划分 集合集合A A的等价关系与集合的等价关系与集合A A的划分一一对应的划分一一对应 （1 1每个每个A A上的等价关系所产生的商集是一个划分上的等价关系所产生的商集是一个划分 （2 2每个每个A A的划分的划分决定一个决定一个A A上等价关系上等价关系R R 通过通过A

10、A的一个划分来确定等价关系的一个划分来确定等价关系R R的方法是：的方法是：对任意的对任意的x,yx,yA A，R R当且仅当当且仅当x x和和y y在在的同的同一划分块中。一划分块中。 例例 A=a,b,c,d A=a,b,c,d的一个划分为的一个划分为=a,b,c,d=a,b,c,d 则则对应的等价关系为：对应的等价关系为： R=, IA R=, IAa b cda bdc 划分的图形表示 一般用“圆来表示一个划分，将圆划分成若干份来表示划分块。例如: 1= a，b，c ， d 2= a，b ， c ， d 例例7.18 7.18 给出给出A=1A=1，2 2，33上所有的等价关系上所有的等价关系 解：解： 利用图形对利用图形对A A进行划分。进行划分。 这些划分与这些划分与A A上的等价关系之间是一一对应的：上的等价关系之