等价关系与划分ppt课件.pptx

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,划分的图形表示 一般用“圆”来表示一个划分，将圆划分成若干份来表示划分块。,例如: 1= a，b，c ， d 2= a，b ， c ， d ,19,例7.18 给出A=1，2，3上所有的等价关系 解： 利用图形对A进行划分。 这些划分与A上的等价关系之间是一一对应的： 1：R1对应于全域关系EA 2：R2=,IA 3；R3=,IA 4：R4=,IA 5：R5对应于恒等关系IA,20,思考题 求出四元集上可定义多少个不同的等价关系?,