版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1/36第四章 二元关系2/452/45回顾关系的性质关系的闭包运算3/453/45四、关系的闭包运算定理:设X是集合,R是集合中的二元关系,于是有证明:4/454/45四、关系的闭包运算证明(b):因为 , ,而对于所有的 有 ,以及 。根据这些关系式,可有于是5/455/45四、关系的闭包运算证明(c):如果 ,则 ,根据对称闭包的定义,有 。首先构成上式两侧的可传递闭包,再依次构成两侧的对称闭包,可以求得 以及 。而ts(R)是对称的,所以 ,从而有 。 6/456/45四、关系的闭包运算注意:(1)通常用R+表示R的可传递闭包t(R),并读作“R加”。(2)通常用R*表示R的自反可传递
2、闭包tr(R),并读作“R星”。7/457/454.5特殊关系一、集合的划分和覆盖定义:给定非空集合S,设非空集合A=A1,A2, An,如果有则称集合A是集合S的覆盖。注意:集合的覆盖不唯一。例如:S=a,b,c,A =a,b,b,c,B=a,b,c,A和B都是集合S的覆盖。8/458/45一、集合的划分和覆盖定义:给定非空集合S,设非空集合A=A1,A2, An,如果有则称集合A是集合S的一个划分。划分中的元素Ai称为划分的类。 划分的类的数目叫划分的秩。 划分是覆盖的特定情况,即中元素互不相交的特定情况。 9/459/45一、集合的划分和覆盖例:设S=1,2,3,考虑下列集合S的覆盖S的
3、覆盖S的覆盖、划分,秩为2S的覆盖、划分,秩为1,最小划分S的覆盖、划分,秩为3,最大划分10/4510/45一、集合的划分和覆盖定义:设A和A是非空集合S的两种划分,并可以表示成如果A的每一类Aj,都是A的某一类Ai的子集,那么称划分A是划分A的加细,并称A加细了A。如果A是A的加细并且AA,则称A是A的真加细。11/4511/45极小项、完全交集定义:划分全集E的过程,可看成是在表达全集的文氏图上划出分界线的过程。设A,B,C是全集E的三个子集。由A,B和C生成的E的划分的类,称为极小项或完全交集。 n个子集生成2n个极小项,用 表示。12/4512/45一、集合的划分和覆盖定理: 由全集
4、的n个子集A1,A2, An所生成的全部极小项集合,能够构成全集E的一个划分。 证明:证明这个定理,只需证明全集E中的每一个元素,都仅属于一个完全交集就够了。 如果 ,则 ,或 , 或 ; 或 。由此可见,定有这里 或是Ai或是 Ai 。试考察两个不同的完全交集T。因为两个完全交集是不同的,就是说存在这样一个i,使得 和 ,因此可有 ,即 ;因而任何一个 都不能同时属于两个不同的完全交集。 13/4513/45一、集合的划分和覆盖注意:不难看出,这里所说的完全交集,与命题演算中的极小项相似。但是和极小项的集合不同,极大项的集合不能构成全集的划分。 14/4514/45二、等价关系定义:设X是任
5、意集合, R是集合中的二元关系。如果R是自反的、对称的和可传递的, 则称R是等价关系。即满足以下几点:如果R是集合X中的等价关系,则R的域是集合X自身,所以,称R是定义于集合X中的关系。 例如 数的相等关系是任何数集上的等价关系。 又例如一群人的集合中姓氏相同的关系也是等价关系。但朋友关系不是等价关系,因为它不可传递。 15/4515/45二、等价关系例:给定集合X=1,2,7,R是X中的二元关系,并且给定成 试证明R是等价关系。解:R的关系矩阵如下: R的关系图如下:16/4516/45二、等价关系注意:上例是模数系统中模等价关系的特定情况。 设Z+是正整数集合,m是个正整数。对于 来说,可
6、将R定义成 。 这里,“x-y可被m整除”等价于命题“当用m去除x和y时,它们都有同样的余数”。故关系R也称为模m同余关系。 17/4517/45元素的等价 设R是集合A上的等价关系,若元素aRb,则称a与b等价,或称b与a等价。定义:设m是个正整数, 。如果对于某一个整数n,有x-y=nm,则称x模m等价于y,并记作 整数m称为等价的模数。“ ”表示模m等价关系R。18/4518/45二、等价关系定理:任何集合 中的模m相等关系,是一个等价关系。 证明:设R是任何集合 中的模m相等价关系。如果X=,则R是个空关系,显然有是自反的、对称的和可传递的。如果X ,则需考察下列三条: (1)对于任何
7、 来说,因为x-x=0m,所以有 。因此,模m相等关系是自反的。 (2)对于任何 来说,如果 ,则存在某一个 ,能使x-y=nm。于是可有y-x=(-n)m,因此有 ,即模m相等关系是对称的。 (3)设 , 和 。于是存在 ,能使 和 。而 ,从而可有 ,即模m相等关系是可传递的。 19/4519/45等价类 定义 设 是集合A上的等价关系,则A 中等价于元素 的所有元素组成的集合称为 生成的等价类,用 表示,即 说明:简单起见,有时候把aR简单写作a或a/R。20/4520/45等价类例:设X=a,b,c,d,R是X中的等价关系,并把R给定成 则:21/4521/45等价类的性质设X是一集合
8、,X是R中的等价关系2. 对于所有的 ,或者 ,或者证明:当X=,上述结论肯定为真。当X时,分两种情况讨论 (1)xRy (2)xRy. 如果xX,则x xR。该性质是明显的,因为是自反的,所以有xRx,于是x xR22/4522/45等价类的性质(1) xRy故 。 类似地可以证明由上得若 ,则xRz , 由R 的对称性有zRx, 又由R的传递性有zRy ,因此 (2) xRy假设 , 因此有 且 ,故 于是由xRz,zRy,得xRy,与xRy相矛盾23/4523/45等价类的性质3.证明:假定 ,对于某个 ,有 。由于 ,会有 ,因而 。设 ,于是因而证毕。24/4524/45等价类的性质
9、例 设A=a,b,c,d,A上的关系R是A上的等价关系 同一个等价类中元素均相互等价。不同等价类中的元素互不等价。 由A的各元素所生成的等价类必定覆盖A,决定了集合A的一种划分。 25/4525/45二、等价关系定理:设R是非空集合X中的等价关系。R的等价类的集合 ,是X的一个划分。 定义:设R是非空集合X中的等价关系。R的各元素生成的等价类集合 叫按R去划分X的商集,记作X/R,也可以写成X(mod R)。由定义可知,按R对集合X的划分X/R是一个集合,并且X/R的基数是X的不同的R等价类的数目,因此X/R的基数又称为等价关系R的秩。 26/4526/45特殊的等价关系全域关系:令等价关系R
10、1=X X,这里X的每一个元素与X的所有元素都有R1的关系。按R1划分X的商集乃是集合X。等价关系R1是全域关系。全域关系会造成集合X的最小划分。 恒等关系R:X的每一个元素仅关系到它自身,而不关系到其它元素。显然,R是个恒等关系。按R划分X的商集,仅由单元素集合组成。恒等关系R会造成集合X的最大划分。这些划分均称作X的平凡划分。 27/4527/45等价关系与集合的划分例:令R是整数集合I中的“模3同余”关系,R可给定成 求Z的元素所生成的R等价类。 解:等价类是可以看出,等价关系可以造成集合的一个划分。 28/4528/45等价关系与集合的划分定理:设C是非空集合X的一个划分,则由这个划分
11、所确定的下述关系R必定是个等价关系,并称R为由C划分导出的X中的等价关系。 证明:要证明R是个等价关系,就必须证明R是自反的、对称的和可传递的。(a)由于C是X的划分,C必定覆盖X。对任意的 ,必有x属于C的某一个元素S。所以对于每一个 ,都有xRx,即R是自反的。 29/4529/45等价关系与集合的划分证明:(b) 假定xRy。于是存在一个 ,且 和 ,所以有yRx。因此,R是对称的。(c)假定xRy和yRz。于是存在两个元素 和 ,且 和 ,所以有 。这样就有S1=S2,因此, 。从而xRz,所以有R是可传递的。综上,R是个等价关系。证毕。 可以看出,给定集合的一种划分,就可以写出一个等价关系。反过来,集合中的等价关系也能够生成该集合的划分。30/4530/45等价关系与集合的划分例:设X=a,b,c,d,e和C=a,b,c,d,e。试写出由划分C导出的X中的等价关系。 解:用R表示这个等价关系,(每一个类做笛卡尔乘积)注意:集合中的等价关系能够生成该集合的划分,反过来集合中的任何一种划分又能确定
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 文化石销售合同分析3篇
- 数据库优化与信息服务合同3篇
- 换岗指南劳动合同变更的实操建议3篇
- 摩托车销售合同范本全新版3篇
- 招标文件评审表的填写规范3篇
- 摩托车车辆买卖的协议书范本3篇
- 房屋买卖合同的合同终止3篇
- 支付后续工程款协议书3篇
- 师承合同协议书3篇
- 职业学校教师聘用合同模板
- 充电桩采购安装售后服务方案
- 体质健康成绩测试全自动化计算模板
- 垃圾清运服务投标方案(技术方案)
- 人教版小学三年级上学期期末数学试卷(及答案)
- 人教版六年级下册数学工程问题(课件)
- 冲压成型精密五金机构件生产QC工程图
- 2023柔性棚洞防护结构技术规程
- 组织设计与工作分析-南京财经大学中国大学mooc课后章节答案期末考试题库2023年
- 2019新人教版高中化学选择性必修一全册重点知识点归纳总结(复习必背)
- 压铸岗位的安全要求
- DB43-T 140-2023 造林技术规程
评论
0/150
提交评论