《等价关系与划分》PPT课件.ppt

《《等价关系与划分》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.6等价关系与划分1等价关系是一类重要的关系。定义7.15(等价关系)设R非空集合上的关系，如果R是自反的、对称的和传递的，则称R为A上的等价关系。设R是一个等价关系，若R，称x等价于y，记作xy。例设A={1,2,3}，R1，R2，R3是A上的关系R1={<1,1>,<2,2>,<3,3>}R2={<1,1>,<2,2>,<3,3>,<1,2>，<2,3>}R3={<1,1>,<2,2>,<3,3>,<1,3>,<3,1>}2例设A为某班学生的集合，讨论下列关系是否为等价关系。R1={

2、x,yAx与y同年生}R2={

3、x,yAx与

4、y同姓}R3={

5、x,yAx的年龄比y小}解：R1是等价关系；R2是等价关系；R3不是等价关系；3如tsr(R)必为一个等价关系例A={1,2,3}，A上的关系R={<1,1>,<2,2>,<1,2>}tsr(R)={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}通过闭包运算将任意的关系R构造成为一个等价关系4对R求三种闭包共有6种顺序，问每种顺序的运算结果是否一定为等价关系？不一定。由于对称闭包不一定保持关系的传递性，因此先求传递闭包后求对称闭包得到的关系不一定是等价关系例A={1,2,3}，A上的关系R={<1,2>,<3,2>}str(R)=

6、IA{<1,2>,<2,1>,<3,2>,<2,3>}显然str(R)不是等价关系用闭包运算去构造等价关系时，传递闭包运算应该放在对称闭包运算的后面5例设AN，R={

7、x,yA∧x≡y(mod3)}为A上的关系，其中x≡y(mod3)叫做x与y模3相等，其含义为x除以3的余数与y除以3的余数相等。证明R为A上的等价关系。证明:xA，有x≡x(mod3)，即R，所以R是自反的。x,yA，若x≡y(mod3)，则有y≡x(mod3)。所以R是对称的。x,y,zA，若x≡y(mod3)，y≡z(mod3)，则有x≡z(mod3)。所以R是传递

8、的。综上R为A上的等价关系。6例：已知A=P(X),CX,x,yA,RxyC。证明R为A上的等价关系.证明：（1）xA，由于xx=CR,所以R是自反的。（2）x,yA，RxyCyxCR,所以R是对称的。（3）x,y,z∈A，若∈R，∈R，则有xyC，yzC。xz=(xy)(yz)C∈R.所以R是传递的。综上所证，R是A上的等价关系。7画出等价关系R={

9、x,yA∧x≡y(mod3)}的关系图，其中A={1,2,…,8}。不难

10、看出，上述关系图被分为三个分离（互不连通）的部分。每部分中的数两两都有关系(模3相等)，位于不同部分中的数之间则没有关系。称每一部分中的顶点构成了一个等价类。8定义7.16（等价类）设R为非空集合上的等价关系，xA，令[x]R={y

11、yA∧xRy}，称[x]R为x关于R的等价类，简称为x的等价类，简记为[x]。说明：x的等价类是A中所有与x等价的元素构成的集合。9集合A={1,2,…,8}上的等价关系R={

12、x,yA∧x≡y（mod3）}等价类是：[1]=[4]=[7]={1，4，7}[2]=[5]=[8]={2，5，8}[3]=[6]={3，6}10将模3

13、的等价关系加以推广，可以得到整数集合Z上的模n等价关系。对于任意的整数x和y，定义模n相等关系：xyx≡y（modn）易证是整数集合Z上的等价关系。11将Z中所有的整数根据它们除以n的余数分类如下：余数为0的数，其形式为nz，zZ余数为1的数，其形式为nz+1，zZ…余数为n-1的数，其形式为nz+n-1，zZ以上构成了n个等价类：[i]=[n+i]=[2n+i]=…={nz+i

14、zZ}，i=0,1,…n-112定理7.14（等价类的性质）设R为非空集合A上的等价关系，则（1）[x]是A的非空子集（2）x，yA，如果xRy，则[x]=[y]（3）x，y

15、A，如果xRy，则[x]与[y]不交（4）∪{[x]

16、xA}=A定理的含义：（1）：任何等价类都是集合A的非空子集（2）和（3）：在A中任何两个元素，它们的等价类相等或不相交，不能部分相交。（4）：所有等价类的并集就是A（3）和（4）：等价关系将A划分成若干个互不相交的子集13例集合A={1,2,…,8}上的等价关系R={

17、x,yA∧x≡y（mod3）}等价类是{1,4,7}、{2,5,8}、{3,6}14定义7.17（商集）设R为非空集合A上的等价关系，以R的所有等价类为元素的集合叫做A