等价关系与划分.ppt

7.6 等价关系与划分 1 等价关系是一类重要的关系。 定义7.15(等价关系) 设R非空集合上的关系， 如果R是自反的、对称的和传递的，则称R为A上的 等价关系。 设R是一个等价关系，若R，称x等价于 y，记作xy。 例 设A=1,2,3，R1，R2，R3是A上的关系 R1=, R2=,， R3=, 2 例 设A为某班学生的集合，讨论下列关系是否为等 价关系。 R1=|x, yA x与y同年生 R2=|x, yA x与y同姓 R3=|x, yA x的年龄比y小 解：R1是等价关系； R2是等价关系； R3不是等价关系； 3 如tsr(R)必为一个等价关系 例 A=1,2,3，A上的关系R=, tsr(R)=, 通过闭包运算将任意的关系R构造成为一个等价关系 4 对R求三种闭包共有6种顺序，问每种顺序的运算结 果是否一定为等价关系？ 不一定。 由于对称闭包不一定保持关系的传递性，因此先求 传递闭包后求对称闭包得到的关系不一定是等价关系 例 A=1,2,3，A上的关系R=, str(R)=IA, 显然str(R)不是等价关系 用闭包运算去构造等价关系时，传递闭包运算应该 放在对称闭包运算的后面 5 例 设AN，R=|x, yAxy (mod 3) 为A上的 关系，其中xy (mod 3)叫做x与y模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上的等价关系。 6 例：已知A=P(X), CX, x, yA, R xyC。 证明R为A上的等价关系. 证明： （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上的等价关系。 7 画出等价关系R=|x,yAxy(mod 3)的 关系图 ，其中A=1,2,8。 不难看出，上述关系图被分为三个分离（互不连 通）的部分。每部分中的数两两都有关系(模3相等)， 位于不同部分中的数之间则没有关系。 称每一部分中的顶点构成了一个等价类。 8 定义7.16（等价类） 设R为非空集合上的等价关系，xA，令 xR=y|yAxRy，称xR为x关于R的等价类，简 称为x的等价类，简记为x。 说明： x的等价类是A中所有与x等价的元素构成的集合。 9 集合A=1,2,8上的等价关系 R=|x, yAxy（mod 3） 等价类是： 1=4=7=1，4，7 2=5=8=2，5，8 3=6=3，6 10 将模3的等价关系加以推广，可以得到整数集合 Z上的模n等价关系。 对于任意的整数x和y，定义模n相等关系： xyxy（mod n） 易证是整数集合Z上的等价关系。 11 将Z中所有的整数根据它们除以n的余数分类如下： 余数为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 12 定理7.14（等价类的性质） 设R为非空集合A上 的等价关系，则 （1）x是A的非空子集 （2）x，yA，如果xRy，则x=y （3）x，yA，如果xRy，则x与y不交 （4）x|xA =A 定理的含义： （1）：任何等价类都是集合A的非空子集 （2）和（3）：在A中任何两个元素，它们的等价类相等或 不相交，不能部分相交。 （4）：所有等价类的并集就是A （3）和（4）：等价关系将A划分成若干个互不相交的子集 13 例集合A=1,2,8上的等价关系R=|x, yAxy（mod 3） 等价类是1, 4, 7、2, 5, 8、3, 6 14 定义7.17（商集）设R为非空集合A上的等价关系 ，以R的所有等价类为元素的集合叫做A在R下的商集 ，记作A/R，即A/R=xR|xA 例 集合A=1,2,8上的等价关系R=|x, yAxy（mod 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 15 定义7.18（划分）设A为非空集合，若A的子集族 （P(A)，是A的子集构成的集合）满足以下的条件 ： （1） （2）xy（x，yxy xy=） 即中任意两个集合不相交 （3）=A，即中所有集合的并集等于A 则称是A的一个划分，称中的元素为A的划分块 16 例设A=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的划分 17 集合A的等价关系与集合A的划分一一对应 （1）每个A上的等价关系所产生的商集是一个划分 （2）每个A的划分决定一个A上等价关系R 通过A的一个划分来确定等价关系R的方法是： 对任意的x,yA，R当且仅当x和y在的同一 划分块中。 例 A=a,b,c,d的一个划分为=a,b,c,d 则对应的等价关系为： R=, IA 18 a b c d a b d c 划分的图形表示 一般用“圆”来表示一个划分，将圆划分成若干份来 表示划分块。 例如: 1= a，b，c ， d 2= a，b ， c ， d 19 例7.18 给出A=1，2，3上