




已阅读5页,还剩3页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
软件数学基础学习辅导 二元关系一、主要内容1.序偶与迪卡尔积2.关系的概念和性质:二元关系、关系矩阵与关系图。3.复合关系与逆关系 4.关系的自反性、对称性与反对称性、传递性。5.等价关系与等价类。6.偏序关系、偏序集、哈斯图、序关系、序集。7.函数、复合函数、反函数、单射、满射、双射。二、学习要求1.理解序偶与迪卡尔积的概念。2.理解关系的概念,练掌握关系矩阵与关系图。3.理解复合关系与逆关系的概念,掌握其求法。4.熟练掌握等价关系的概念;会判断等价关系。5.了解偏序关系、偏序集的概念,会用哈斯图表示;6.了解函数、复合函数与反函数的概念;掌握单射、满射、双射的判断方法。 7.知道序关系与序集的概念。 三、学习重点1. 知道关系的三种不同的表示方式, 会求给定关系的关系矩阵和关系图.2. 会判断给定关系是否具有某种特殊性质.3. 能熟练判断给定集合A上的二元关系是否为等价关系.4. 会由等价关系确定划分, 也会由划分决定等价关系.5. 掌握偏序集合的概念, 会画偏序关系的Hasse图, 也会由Hasse图给出偏序关系. 四、重、难点解析(一) 集合的笛卡尔积设A, B是两个集合, 称集合(x, y) | xA, yB 为集合A与B的笛卡尔积, 记作AB, 集合AB中的元素叫做有序对. 笛卡尔积有如下简单性质:(1) 如果用|A|来表示集合A所含元素的个数, 那么| AB |=|A| |B|. (2) A=, A=.(3) AB= BAA=B或者A, B之中至少有一个为空集.(4) 笛卡尔积对并和交运算都满足分配律:A(BC) = (AB)(AC), (BC)A = (BA)(CA), A(BC) = (AB)(AC), (BC)A = (BA) (CA). (5) 如果AC, BD, 那么ABCD.请自己给出上述性质的证明. 尤其是应该给出最后一个命题的逆命题不成立的例子.(二) 集合上的二元关系我们主要研究给定集合A上的二元关系. 所谓集合A上的一个二元关系, 说通俗一点就是给定一个法则R, 对于A中任意两个元素a, b, 利用这个法则可以判定a与b是否具有关系R. 如果使用更数学化的语言来叙述, 就是: R就是AA的一个子集. 比较平凡的关系有: 空关系, 恒等关系, 全关系. 我们要研究关系所具备的一些常见性质. 这类似于我们研究函数的常见性质. 所有这些研究, 必须建立在对关系有一个比较方便的表示方式. 下面就是关系最常用的三种表示方式: 集合、关系矩阵和关系图, 其中关系矩阵和关系图只能用来表示有限集合A上的关系. 1. 集合表示法因为集合A上的关系R就是AA的一个子集, 这样作为集合的R当然也就可以用列举法和描述法来加以表示. 例如 A=2, 3, 4, 6, 对于A上的整除关系R, 我们可以用描述法也可以用列举法来表示这个关系:R=(a, b) | a, bA且a整除b 或R=(2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (6, 6).2. 矩阵表示法设R是从有限集合A=a1, a2, , am上的一个关系, 可以按照如下方式定义一个m阶矩阵:矩阵MR为R的关系矩阵. 用关系矩阵来表示二元关系, 非常方便. 上面例1中集合A=2, 3, 4, 6上的整除关系R的矩阵为:需要注意的是关系矩阵并不是绝对唯一的, 与集合A的元素次序有关系.矩阵表示法最大的优点是, 很容易判定关系是否满足自反性, 对称性, 反对称性. 对于传递性, 也可以通过计算关系矩阵的乘积来判定, 但是多少有点麻烦.3. 有向图表示法设R是从有限集合A=a1, a2, , am上的二元关系, 以A的元素为顶点, 用一个从a到b的箭头来表示aRb, 则可以得到一个有向图, 称为R的关系图.例如 设A=1, 2, 3, 4, R=(1, 1), (1, 2) , (1, 3), (2, 3), (2, 4), (3, 4), (4, 2), 则R的关系图为: (三) 关系的运算 既然关系可看作AA的子集, 因此可以说关系也是集合. 所以, 对于同一个集合A上的关系, 可以进行交、并、差、补等运算. 但是, 对于关系而言, 最重要的两种运算是逆运算和复合运算. 这两种运算可以帮助判断给定关系是否具有某种特殊的性质. 逆运算: 设RAA是集合A上的关系, 则R-1=(x, y) | (y, x)R称为R的逆关系. 复合运算: 设RAA, SAA是二元关系, 则T=(x, z)|$yB使得(x, y)R且(y, z)S称为R与S的复合关系, 记作T=RoS或T=RS. 逆关系十分容易确定. 考虑一下, 关系与其逆关系R-1关系矩阵和关系图有什么关系? 下面用一个简单例子来说明如何进行关系的复合运算. 例如 设A=a, b, c, d, 定义A上的关系R如下:R=(a, a) , (a, b), (b, d), (c, a), (d, c), 求复合关系R2=RoR.分析: 计算复合关系RoR一般有三种方法, 可以根据不同的情况选取不同的计算, 下面我们只采用其中一种, 其余见书中有关例题.解 根据关系R中所包含的有序对, 按照复合关系RoR的定义: (a,b), (b, c)R(a,c)R2. 由此可得R2=(a, a) , (a, b), (a, d), (b, c), (c, a), (c, b), (d, a). (四) 关系的常见性质对于集合A上的二元关系R, 我们最关系的性质有:自反性: 若对于任意的都有, 则称是A上的一个自反关系. 对称性: 若对于任意的都有“xRyyRx”, 则称R是A上的一个对称关系.传递性: 若对于任意的都有“xRy, yRzxRz”, 则称R是A上的一个传递关系.反对称性: 若对于任意的都有“xRy, yRxx=y”, 则称R为集合A上的一个反对称关系. 如何判断给定的二元关系是否具有上述某个性质? 可以根据关系的不同表示方式来加以考察. 1. 利用定义考察关系R的性质自反性: 对于任意aA, R必须包含(a, a). 即: IAR.对称性: 若R包含(a, b), 则R必须同时包含(b, a). 即: R-1=R.传递性: 若R包含(a, b), (b, c), 则R必须同时包含(a, c). 即: R2R.反对称性: 若R包含(a, b), 而且ab, 则R不能同时包含(b, a). 即: RR-1 IA.2. 利用关系矩阵MR考察关系R的性质自反性: MR主对角线元素必须都是1.对称性: MR必须是对称矩阵. 即: MRT=MR.传递性: MR-MR2不出现负数.反对称性: 若ij, (i, j)位置与(j, i)位置不能同时为1(但是可以同时为0).3. 利用关系图考察关系R的性质自反性: 每个顶点必须有环.对称性: 若从a到b有有向边, 则从b到a也必须有有向边.传递性: 若从a到b有有向边, 从b到c有有向边, 则必须有从a到c的有向边.反对称性: 若ab, 从a到b有有向边, 则不能有从b到a的有向边.以上方法可以说各有好处. 第一种容易理解, 第二种容易计算, 第三种比较直观. 如果所使用的计算机编程能力比较强, 不妨自己编写程序, 让计算机来判断关系是否具有某种性质. (五) 等价关系与集合的划分等价关系: 若集合A上的二元关系R具有自反性、对称性、传递性, 则称其为等价关系.等价关系是最常用也是最重要的二元关系. 我们熟悉的: 数的相等关系、直线的平行关系都是等价关系. 但是, 实数的小于等于关系、集合的包含关系都不是等价关系.划分: 若集合的一个非空子集族满足(1); (2), 则称是的一个划分. 设R是A上的等价关系, aA, 集合aR=xA | (x, a)R称为a所在的等价类. 设R是A上的等价关系, 则 集合上的一个等价关系可以唯一确定的一个划分:; 集合的一个划分也可以唯一确定上的一个等价关系:.认清等价关系与划分本质是一回事是理解这两个概念的关键.例如 考虑整数集合Z上模5同余关系R5. 这是一个等价关系, 即R5=(x, y) | x y (mod 5).这个等价关系刚好有下列5个等价类:(五) 偏序关系偏序关系: 若集合A上二元关系具有自反性、传递性、反对称性, 则称R为集合A上的一个偏序关系, 称A为带有偏序关系R的偏序集, 记作(A, ).偏序集合的偏序关系 “”, 也读作“小于等于”. 之所以采用这样的符号和名称, 是因为偏序关系和小于等于关系具有完全相似的性质. 集合的包含关系也是偏序关系. 设(A, )是偏序集, 则A中的任何两个元素a, b只可能出现如下四种情况之一:a = b, a b, b a, a与b不可比较.顺便提一下, 如果一个偏序集合当中任意两个元素都可以比较, 就称为全序集.偏序关系的重要性不亚于等价关系. 对于这种特殊的关系, 我们也采用特殊的方式来表示, 这种表示方式就是Hasse图表示法.设有偏序集(A, ), 则其Hasse图构造法如下:S1. 以“点”表示A中的元素; S2. 若y是x的直接后继, 则y在x的上方; S3. 在x和x的直接后继间连线.例如 设A是正整数12的全部正整数因子组成的集合, 并设偏序关系为整除关系“|”, 则这个偏序关系的Hasse图如下: 五、 典型例题例1 设A=2, 3, 6, 12, R是A上的整除关系.(1) 给出R的集合表示式.(2) 给出R的关系矩阵.(3) 画出R的有向图.(4) 考察关系R是否具有自反性、对称性、传递性、反对称性.(5) R是否为等价关系? R是否为偏序关系? 分析 首先根据整除关系的含义, 列出A中整除有序数对: 2|2, 2|6, 2|12, 3|3, 3|6, 3|12, 6|6, 6|12, 12|12. 此即R所包含的全部有序对. 至于其矩阵和有向图很容易根据R的集合表达式得到. 然后可以利用定义、关系矩阵或者关系图来判定R所具有的性质. 最后根据这些性质就能知道这个关系是一个什么样的关系. 解 (1)根据关系R的定义:R=(2, 2), (2, 6), (2, 12), (3, 3), (3, 6), (3, 12), (6, 6), (6, 12), (12, 12).(2)R的关系矩阵MR如下:(3)R的关系图略. (4) 可以从R的意义、集合表示、关系矩阵或者关系图得到R自反、传递、反对称. (5) 根据(4)我们知道R是偏序关系, 不是等价关系. 例2 设T=1, 2, 3, , 9, A=TT. 按照下列方式定义集合A上的关系R:(a, b)R(c, d) a + d= b + c(1) 证明R是A上的等价关系.(2) 求出元素(5, 2)所在的等价类(5, 2).分析 求解本题时要注意集合A的元素本身都是有序对. 这样R由形如(2, 1), (3, 2)的元素组成. 由于|A|=81, 因此并不一定非要列举出R所包含的全部元素. 可以直接按照R的定义直接验证R满足: (i)自反性: (a, b)R(a, b); (ii) 对称性: (a, b)R(c, d) (c, d)R(a, b) ; (iii) 传递性: (a, b)R(c, d), (c, d)R(u, v) (a, b)R(u, v). 由此证明R是A上的等价关系.根据R的定义, 可以看出(a, b)R(c, d) a + d= b + c a - b = c - d. 由此看见, (a, b)R(5, 2) a-b=5-2=3.根据这个特点很容易写出等价类(5, 2).解 (1) (i) R满足自反性: 设 (a, b)A, a+b=b+a(a, b)R(a, b);(ii) R满足对称性: (a, b)R(c, d)a+d=b+cc+b=d+a (c, d)R(a, b) ; (iii)R满足传递性: (a, b)R(c, d), (c, d)R(u, v)a+d=b+c, c+v=d+u a-b=c-d=u-v a + v= b + u (a, b)R(u, v) 所以R是等价关系.(2) (5, 2)=(4, 1), (5, 2), (6, 3), (7, 4), (8, 5), (9, 6).例3 设A=a, b, c, d, e, f, 有一个划分S=a, b, c, d, e, f, 试由划分S确定A上的一个等价关系R.分析 根据题设要求, 我们需要求一个等价关系R, 使得R 的等价关类恰好是上述划分S中的三个子集合. 要使得a, b, c成为R的一个等价类, 那么其中的任意两个元素都满足关系R, 从而R必须包含这个子集中元素构成的任意一个有序对, 必然有R1=a, b, ca, b, cR, R2=d, ed, e R, R3=ff R.只要令R= R1 R2 R3即可. 解 我们用如下办法产生一个等价关系R:R1=a, b, ca, b, c=(a, a), (b, b), (c, c), (a, b), (a, c), (c, a), (b, c), (c, b)R2=d, ed, e=(d, d), (e, e), (d, e), (e, d)R3=ff=(f, f) R.R=R1R2R3.容易证明R是等价关系, 而且等价类正是S中的三个子集.例4 设有集合A=a, b, c, d, e上的偏序关系:R=(a, b), (a, c), (a, d), (a, e), (b, d), (b, e), (c, d), (c, e), (d, e)IA.画出Hass
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 电工考试题目及答案初级
- 2025年年产50000万米汽车线束项目可行性研究报告-商业计划书
- 中国橡胶胶布及制品项目创业投资方案
- 单词比赛考试题及答案大全
- 大学线上考试题型及答案
- 烧烤转租协议书
- 建筑c类考试试题及答案
- 船舶服务考试题及答案大全
- 2025年纳米碳酸钙项目可行性研究报告立项新版
- 中国软化剂项目经营分析报告
- 矛盾纠纷主题班会课件
- 调车作业安全培训
- 合规品质培训
- 2025年江西省中考数学试卷真题(含标准答案)
- 呼吸系统症状与体征的护理
- uart面试题及答案
- 电梯空调安装合同协议书
- 2025-2031年中国医学检验市场深度分析及行业前景展望报告
- 2024年河北省临漳县事业单位公开招聘村务工作者笔试题带答案
- 白内障病人护理查房
- 渗滤液考试题及答案
评论
0/150
提交评论