04-关系-4.3-文本资料课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《04-关系-4.3-文本资料课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 04 关系 4.3 文本 资料 课件
- 资源描述:
-
1、第四章第四章 关关 系系第三节第三节 关系类型关系类型一、等价关系一、等价关系v集合中的各个元素总是具有某些有用的性质,时常不是把这些元集合中的各个元素总是具有某些有用的性质,时常不是把这些元素作为单一的个体,逐个地对待它们;而是按它们所具有的性质素作为单一的个体,逐个地对待它们;而是按它们所具有的性质进行分类,并根据这些性质处理它们,或者是使用它们。在处理进行分类,并根据这些性质处理它们,或者是使用它们。在处理实际问题时,可以不去考察那些不感兴趣的性质,而专注于感兴实际问题时,可以不去考察那些不感兴趣的性质,而专注于感兴趣的某些性质。凡是具有同样性质的元素,可以看成是不可区分趣的某些性质。凡
2、是具有同样性质的元素,可以看成是不可区分的或相互等价的,也称它们之间存在等价关系。的或相互等价的,也称它们之间存在等价关系。第三节第三节 关系类型关系类型一、等价关系一、等价关系v定义:定义:设设R是集合是集合A上的二元关系,上的二元关系,若若R是是和和,则称则称R是是A上的上的。若若 R,或者,或者xRy,称,称x等价等价y,记做,记做xy等价关系等价关系因为因为R是自反的,因此是自反的,因此R的关系图中每个结点都有有向环的关系图中每个结点都有有向环因为因为R是对称的,因此是对称的,因此R的关系图中的有向弧都是成对出的关系图中的有向弧都是成对出现,即若有从现,即若有从a到到b的弧,必定有从的
3、弧,必定有从b到到a的弧的弧(任意两个结任意两个结点间或没有弧连接,或有成对的弧出现点间或没有弧连接,或有成对的弧出现)。因为因为R是传递的,因此若有从是传递的,因此若有从a到到b的弧以及从的弧以及从b到到c的弧,的弧,必定有从必定有从a到到c的弧的弧等价关系等价关系例例4.3.1 同学集合同学集合A=a, b, c, d, e, f,A中的关系中的关系R是是“住住在同一个房间在同一个房间”。问:。问:R是等价关系吗?是等价关系吗?答:是。答:是。1) 任何一个人都和自己住在同一房间,因此任何一个人都和自己住在同一房间,因此R是是2) 若若x和和y住在同一房间(即住在同一房间(即xRy),则)
4、,则y和和x也住在同也住在同一房间(即一房间(即yRx),因此),因此R是是3) 若若x和和y住在同一房间住在同一房间(xRy),并且,并且y和和z住在同一房间住在同一房间(yRz),则,则x和和z住在同一房间住在同一房间(xRz),因此,因此R是是等价关系等价关系假设假设a和和b住在同一房间,住在同一房间,d和和e和和f住在同一房间,住在同一房间,c住一间。则住一间。则R=,关系图为:关系图为:abcefd等价关系等价关系整数集合整数集合Z中的相等关系、中的相等关系、在全集在全集U所有子集的集合中的相等关系,所有子集的集合中的相等关系,以及命题演算中的命题集合的以及命题演算中的命题集合的关系
5、等关系等都是等价关系都是等价关系空集上的任意二元关系空集上的任意二元关系R是等价关系是等价关系等价关系等价关系v定义:定义:设设m是一个正整数,是一个正整数,a和和b都是整数,若存在某整数都是整数,若存在某整数k,使得使得,则称,则称,记为,记为m叫作等价的叫作等价的等价关系等价关系v定理:定理:。证明:如果证明:如果A= ,那么模,那么模m等价是等价是A上的等价关系。上的等价关系。若若A ,设任意,设任意a,b,c A,将模,将模m等价记为等价记为R1) 因为因为 a a = 0m,因此,因此R是是2) 假设有假设有aRb,则存在一个整数,则存在一个整数k,使得,使得a-b=km,则则b-a
6、=-km,所以有,所以有bRa,所以,所以R是是3) 假设有假设有aRb和和bRc,则存在整数,则存在整数p和和q,使得,使得a-b=pm,b-c=qm,所以,所以a-c=(a-b)+(b-c)=(p+q)m因此因此R是是综上所述,综上所述,。等价类等价类v定义:定义:设设R是非空集合是非空集合A上的等价关系,对于任意上的等价关系,对于任意a A,令,令 称称,简称,简称a的等价类,简记为的等价类,简记为a。称。称a为为aR的的。(。(aR称为元素称为元素a形成的形成的R的等价类)的等价类)若等价类个数有限,则若等价类个数有限,则R的不同等价类的个数叫作的不同等价类的个数叫作。对于任意对于任意
7、a A , aR非空,因为非空,因为a aR按照按照R等价类的定义,是由集合等价类的定义,是由集合A中与中与a有等价关系有等价关系R的的所有元素,构成集合所有元素,构成集合aR。常用。常用a代替代替aR因此,任给集合因此,任给集合A及其上的等价关系及其上的等价关系R,必可写出,必可写出A上各个元素的等价类上各个元素的等价类等价等价类类例例4.3.2 设设A=a,b,c,d,e,f, R=, , ,,则等价关系,则等价关系R的关系图是:的关系图是:abcefd等价关系等价关系R的等价类如下:的等价类如下:aR = bR = a, b, cR = c dR = eR = fR = d, e, f等
8、价关系等价关系R的秩是的秩是3等价等价类类例例4.3.3 若若R是整数集合是整数集合Z上的模上的模4等价关系,则等价类有:等价关系,则等价类有:0R = , -8, -4, 0, 4, 8, = 4R = -4R = 1R = , -7, -3, 1, 5, 9, = 5R = -3R = 2R = , -6, -2, 2, 6, 10, = 6R = -2R = 3R = , -5, -1, 3, 7, 11, = 7R = -1R = 每个等价类中的元素互相等价。每个等价类中的元素互相等价。若若R是整数集合是整数集合Z上的模上的模2等价关系,则等价类有等价关系,则等价类有0R = , -4
9、, -2, 0, 2, 4, = 2R = -2R = 1R = , -3, -1, 1, 3, 5, = 3R = -1R = 等价类等价类v定理定理1:设:设R是非空集合是非空集合A上的等价关系,对于任意上的等价关系,对于任意a,b A证明:证明:1) ,则,则a a=b,所以所以bRa, 根据根据R的对称性,可知的对称性,可知2),对于任意对于任意x a,有有aRx,所以也有,所以也有xRa根据根据R的传递性,可知有的传递性,可知有xRb;根据;根据R的对称性,可知有的对称性,可知有bRx则则x b,所以,所以a b同理可证:对于任意同理可证:对于任意x b有有x a,即,即b a所以:
10、所以: xRa xRb等价类等价类v定理定理2:设:设R是非空集合是非空集合A上的等价关系,对于任意上的等价关系,对于任意a,b A证明:假设证明:假设a b ,则存在某个,则存在某个x A,有,有 x a b x a x b aRx bRx aRx xRb aRb与与 R矛盾。因此矛盾。因此a b = 。v也就是说,也就是说,等价类等价类v定理定理3:设:设R是非空集合是非空集合A上的等价关系,对于任意上的等价关系,对于任意a,b A证明:证明:1) 对任意的对任意的x a,可知,可知x A,所以,所以 a Aa Aa A2) 对任意的对任意的x A,有,有x x,所以,所以x a。因此因此
11、A aa Aa A所以:所以: a = Aa A等价类等价类v定理定理4:设:设R1和和R2是非空集合是非空集合A上的等价关系,那么上的等价关系,那么证明:证明: ,则对于任意,则对于任意a A,有,有aR1 = x|aR1x= x|aR2x= aR2 ,则有:,则有: x|aR1x= x|aR2x则对于任意则对于任意x A和和a A ,有,有aR1x x aR1 x aR2 aR2x因此因此R1=R2 集合的划分和覆盖集合的划分和覆盖 定义:定义:若把一个集合若把一个集合A分成若干个叫做分块的非空子集,使得分成若干个叫做分块的非空子集,使得A中每个元素至少属于一个分块,那么这些分块的全体构成
12、的集中每个元素至少属于一个分块,那么这些分块的全体构成的集合叫做合叫做A的一个的一个覆盖覆盖。如果。如果A中每个元素属于且仅属于一个分块,中每个元素属于且仅属于一个分块,那么这些分块的全体构成的集合叫做那么这些分块的全体构成的集合叫做A的一个的一个划分划分。 等价定义:等价定义:令令A为给定非空集合,为给定非空集合, B=A1, A2, , An (Ai A),Ai 且且 Ai=A,则集合,则集合B称作称作A的覆盖;的覆盖; 若除上述条件外,另有若除上述条件外,另有Ai Aj= (i j)则称则称B是是A的划分的划分划分划分i = 1n划分划分v利用非空集合利用非空集合A及其上的等价关系,及其
13、上的等价关系,可以构造一个新的集合:可以构造一个新的集合:。v定义:设定义:设A是非空集合,若是非空集合,若B=A1, A2, , An (Ai A) 且且Ai Ai Aj= (i j) Ai=A则称则称B是是A的的,称,称B中的元素为中的元素为A的的。若划分是有限的,则若划分是有限的,则|B|称为划分的称为划分的。i = 1n划分划分例例4.3.4 设设S = 1, 2, 3A= 1,2, 2,3 B= 1, 1,2, 1,3 C= 1, 2,3 D= 1,2,3 E= 1, 2, 3 F= 1, 1,2 问:哪些是问:哪些是S的划分?秩是多少?的划分?秩是多少?1,2 2,3 1 1,2
14、1,3 1 1,2 1 1,2 A划分划分例例4.3.4 设设S = 1, 2, 3A= 1,2, 2,3 B= 1, 1,2, 1,3 C= 1, 2,3 D= 1,2,3 E= 1, 2, 3 F= 1, 1,2 划分划分例例4.3.5 将一张纸撕成几片,则所得的碎片的集合将一张纸撕成几片,则所得的碎片的集合就是该纸的一个划分,该划分的秩就是碎片的张数就是该纸的一个划分,该划分的秩就是碎片的张数集合族集合族 x, -x|x 整数集合整数集合Z 是是Z的一个划分,的一个划分,其秩是无限的其秩是无限的自己尝试举出几个属于划分的例子。(课后思考)自己尝试举出几个属于划分的例子。(课后思考)商集商
15、集v定义:设定义:设A是非空集合,是非空集合,R是是A上等价关系,上等价关系,R的所有等价类集合的所有等价类集合 是是A的划分,称为的划分,称为,也叫作,也叫作A模模Rv定理:设定理:设R1和和R2是是A的等价关系,则的等价关系,则该定理说明:该定理说明:A上的等价关系可以诱导出上的等价关系可以诱导出A的划分,且是唯一的。的划分,且是唯一的。反之,反之,A的划分也可以诱导出的划分也可以诱导出A上的等价关系上的等价关系商集商集A/R是以是以R的所有等价类为元素的集合的所有等价类为元素的集合商集商集A/R就是就是A的一个划分,并且不同的商集对应于不同的划分的一个划分,并且不同的商集对应于不同的划分
16、商集商集v定理:设定理:设B=A1, A2, , An是非空集合是非空集合A上的任意划分,上的任意划分, 则则A的二元关系的二元关系或或是是A上的等价关系。上的等价关系。证明:证明:1) 因为对于任意一个因为对于任意一个a A,都有,都有aRa,因此,因此2) 假设有假设有aRb,那么存在某块,那么存在某块Ai ,使得,使得a Ai且且b Ai ,因此有,因此有bRa,所以,所以。3) 假设有假设有aRb,并且有,并且有bRc,则存在,则存在Ai和和Aj ,使得,使得a,b Ai且且b,c Aj,根据划分的定义可知,或者,根据划分的定义可知,或者Ai Aj或者或者AiAj,因此因此 AiAj,
17、因此有,因此有a,c Ai,因此有,因此有aRc,因此,因此。所以:所以:R是是A上的等价关系。上的等价关系。设集合设集合A有一个划分有一个划分B,现定义一个关系,现定义一个关系R,aRb当且当且仅当仅当a,b在同一分块中在同一分块中(a与与a在同一分块中,故在同一分块中,故aRa)若若a与与b在同一分块中,在同一分块中,b与与a也必须在同一分块中,也必须在同一分块中,即:即:aRb bRa若若a与与b在同一分块中,在同一分块中,b与与c在同一分块中,因为:在同一分块中,因为:Ai Aj=,即,即b属于且仅属于一个分块,故属于且仅属于一个分块,故a,c同块同块即:即:aRb bRc aRc商集
18、商集例例4.3.6 试给出试给出A=a,b,c上的所有等价关系上的所有等价关系解:解:A的所有划分为:的所有划分为:B1=a,b,cB2=a,b,cB3=a,c,bB4=b,c,aB5=a,b,c偏序关系偏序关系二、偏序关系二、偏序关系 在一个集合上,我们常常要考虑元素的次序关系,其中很重在一个集合上,我们常常要考虑元素的次序关系,其中很重要的就是偏序关系要的就是偏序关系v定义:定义:设设R是非空集合是非空集合A上的二元关系,上的二元关系,若若R是是,则称则称R是是A上的上的。称称为偏序集为偏序集偏序关系偏序关系v若若R是偏序,偏序集是偏序,偏序集常记为常记为v若若R是是A上的偏序,则上的偏序
19、,则R-1也是也是A上的偏序。上的偏序。若用若用 表示表示R,则用,则用 表示表示R-1 v和和都是偏序集都是偏序集注意:注意: 偏序关系偏序关系例例4.3.7 v是偏序集合,这里的是偏序集合,这里的“”表示小于等于关系表示小于等于关系v是偏序集合,这里的是偏序集合,这里的“ ”表示集合间的包含关系表示集合间的包含关系vA=2, 3, 6,D代表整除关系,代表整除关系,M代表整倍数关系,则代表整倍数关系,则D=,,M=,和和都是偏序集合都是偏序集合偏序关系偏序关系v定义:设定义:设R是非空集合是非空集合A上的偏序关系上的偏序关系 a, b A, a, b A,a b读作读作“a小于小于b”,它
20、是指在偏序中,它是指在偏序中,a排在排在b前边前边v可见,在偏序集可见,在偏序集中,对于中,对于 a, b A ,有,有a b或或b aa = b a 和和 b不可比不可比偏序关系偏序关系例例4.3.8 A=1, 2, 3, 是是A上的整除关系,则有上的整除关系,则有1 2, 1 31 = 1,2 = 2,3 = 32 和和 3 不可比不可比哈斯图哈斯图v定义:定义:设设为偏序集,对于为偏序集,对于 a, b A,若,若ab且不存在且不存在c A,使,使acb,则称,则称v偏序集可以用关系图来表示,但一般习惯用偏序集可以用关系图来表示,但一般习惯用表示。图中仅画出符合条件表示。图中仅画出符合条
展开阅读全文