等价关系与划分

等价关系与划分

ID:39341518

大小:420.81 KB

页数:21页

时间:2019-07-01

等价关系与划分_第1页
等价关系与划分_第2页
等价关系与划分_第3页
等价关系与划分_第4页
等价关系与划分_第5页
资源描述:

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

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、

4、x,yAx与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}

6、,A上的关系R={<1,2>,<3,2>}str(R)=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

8、A,若x≡y(mod3),y≡z(mod3),则有x≡z(mod3)。所以R是传递的。综上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上的等价

9、关系。7画出等价关系R={

10、x,yA∧x≡y(mod3)}的关系图,其中A={1,2,…,8}。不难看出,上述关系图被分为三个分离(互不连通)的部分。每部分中的数两两都有关系(模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

13、≡y(mod3)}等价类是:[1]=[4]=[7]={1,4,7}[2]=[5]=[8]={2,5,8}[3]=[6]={3,6}10将模3的等价关系加以推广,可以得到整数集合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

15、,1,…n-112定理7.14(等价类的性质)设R为非空集合A上的等价关系,则(1)[x]是A的非空子集(2)x,yA,如果xRy,则[x]=[y](3)x,y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

18、,7}、{2,5,8}、{3,6}14定义7.17(商集)设R为非空集合A上的等价关系,以R的所有等价类为元素的集合叫做A

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。