关系43文本资料课件.ppt
《关系43文本资料课件.ppt》由会员分享,可在线阅读,更多相关《关系43文本资料课件.ppt(67页珍藏版)》请在三一办公上搜索。
1、第四章 关 系,钦瞎瞥紊梭孟衡饰秆涨货顶焚仿衍芽弦辑盏宇般赡溯穷典映刀葬垮颤扒圈04-关系-4.304-关系-4.3,7 December 2022,第三节 关系类型,一、等价关系集合中的各个元素总是具有某些有用的性质,时常不是把这些元素作为单一的个体,逐个地对待它们;而是按它们所具有的性质进行分类,并根据这些性质处理它们,或者是使用它们。在处理实际问题时,可以不去考察那些不感兴趣的性质,而专注于感兴趣的某些性质。凡是具有同样性质的元素,可以看成是不可区分的或相互等价的,也称它们之间存在等价关系。,卑体坑拧全雷宏驹懊斧蛙氛溶统调匈簇窖则临遏疲欣邻疽周废记织寸狭意04-关系-4.304-关系-4
2、.3,7 December 2022,第三节 关系类型,一、等价关系定义:设R是集合A上的二元关系,若R是自反的、对称的和可传递的,则称R是A上的等价关系。若 R,或者xRy,称x等价y,记做xy,甄哩霸越韦猾乌靛椿期累肾宰菱岿屁膀娃梅馏液酝貉塔聋吞丙泳丛端吹疹04-关系-4.304-关系-4.3,7 December 2022,等价关系,因为R是自反的,因此R的关系图中每个结点都有有向环因为R是对称的,因此R的关系图中的有向弧都是成对出现,即若有从a到b的弧,必定有从b到a的弧(任意两个结点间或没有弧连接,或有成对的弧出现)。因为R是传递的,因此若有从a到b的弧以及从b到c的弧,必定有从a到
3、c的弧,蝎殉楞郎纸态民鳖清谨弹缄弟升枯袱峦退犬夸阔舜袍裳阎罩乃尺笑搽采部04-关系-4.304-关系-4.3,7 December 2022,等价关系,例4.3.1 同学集合A=a, b, c, d, e, f,A中的关系R是“住在同一个房间”。问:R是等价关系吗?答:是。1) 任何一个人都和自己住在同一房间,因此R是自反的2) 若x和y住在同一房间(即xRy),则y和x也住在同一房间(即yRx),因此R是对称的3) 若x和y住在同一房间(xRy),并且y和z住在同一房间(yRz),则x和z住在同一房间(xRz),因此R是传递的,混逻琉拳折振舶突腑掩植蕾圾盆吴蓄彬停诣兑燥陶扑巾李呸母瞳框垦捡糠
4、04-关系-4.304-关系-4.3,7 December 2022,等价关系,假设a和b住在同一房间,d和e和f住在同一房间,c住一间。则R=,关系图为:,尺省簇干桔膜陋剐赚俄剔摹咖烧池庶甭凋舟婪拘辊榨枫姓嚣桓壬颠丧辙剧04-关系-4.304-关系-4.3,7 December 2022,等价关系,整数集合Z中的相等关系、在全集U所有子集的集合中的相等关系,以及命题演算中的命题集合的关系等都是等价关系空集上的任意二元关系R是等价关系,衷撰帜拍迢麓累怖峪脱箱遂外碳桌烩低耘博褪叭该先耙羌丁燥止页亢矢棵04-关系-4.304-关系-4.3,7 December 2022,等价关系,定义:设m是一个
5、正整数,a和b都是整数,若存在某整数k,使得a-b=km,则称a与b是模m等价,记为a b (mod m)m叫作等价的模数,乳产锑浑方哪每熬顺蒜芳尉倪篷烫翔别微睛绪澳雄甲我阀峭凄房足坤等冲04-关系-4.304-关系-4.3,7 December 2022,等价关系,定理:模m等价是任何集合A Z上的等价关系。证明:如果A= ,那么模m等价是A上的等价关系。若A ,设任意a,b,c A,将模m等价记为R1) 因为 a a = 0m,因此R是自反的2) 假设有aRb,则存在一个整数k,使得a-b=km,则b-a=-km,所以有bRa,所以R是对称的3) 假设有aRb和bRc,则存在整数p和q,使
6、得a-b=pm,b-c=qm,所以a-c=(a-b)+(b-c)=(p+q)m因此R是传递的综上所述,R是自反的、对称的和传递的,所以它是等价关系。,溺睫讫周娟遂茂佐浴塑咏该噬佰申钨花持邯殖贷酬茁佯臀诞退业汽赚掷渍04-关系-4.304-关系-4.3,7 December 2022,等价类,定义:设R是非空集合A上的等价关系,对于任意a A,令 aR = x|x A aRx称aR是a关于R的等价类,简称a的等价类,简记为a。称a为aR的表示元素。(aR称为元素a形成的R的等价类)若等价类个数有限,则R的不同等价类的个数叫作R的秩。对于任意a A , aR非空,因为a aR,按照R等价类的定义,
7、是由集合A中与a有等价关系R的所有元素,构成集合aR。常用a代替aR,因此,任给集合A及其上的等价关系R,必可写出A上各个元素的等价类,癌钠踩穗蔽镊溉净潜爷绍茵贵盎搭龟中熙沂峡侠彻狰碍卿烹嘛彰惯繁狼说04-关系-4.304-关系-4.3,7 December 2022,等价类,例4.3.2 设A=a,b,c,d,e,f, R=, , ,,则等价关系R的关系图是:,等价关系R的等价类如下:aR = bR = a, b, cR = c dR = eR = fR = d, e, f等价关系R的秩是3,规帚释蜡坑揪咆约郁伺皇棘破蚀痕阅审安谆矛寂厉萝演汪谎探侦令蹈谐娱04-关系-4.304-关系-4.3
8、,7 December 2022,等价类,例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, -2, 0, 2, 4, = 2R = -2R = 1R = , -3, -1, 1, 3, 5, =
9、3R = -1R = ,三兽擎甲雷蝉迸束疲履记柿盏童抖极密枷直病卿抄工违烦岁托链季堂庄啦04-关系-4.304-关系-4.3,7 December 2022,等价类,定理1:设R是非空集合A上的等价关系,对于任意a,b AaRb a=b证明:1) 若a=b,则a a=b,所以bRa, 根据R的对称性,可知有:aRb2)若aRb,对于任意x a,有aRx,所以也有xRa根据R的传递性,可知有xRb;根据R的对称性,可知有bRx则x b,所以a b同理可证:对于任意x b有x a,即b a所以: a=b,aR = x|x A aRx,xRa aRb xRb,胡狼嘲峙痔匈加戴裸蛀乓魁藩掇裸叭荐液陕症
10、菇押甜雨冯曰肥舒迫庚准愿04-关系-4.304-关系-4.3,7 December 2022,等价类,定理2:设R是非空集合A上的等价关系,对于任意a,b A若R,则a b=证明:假设a b ,则存在某个x A,有 x a b x a x b aRx bRx aRx xRb aRb与R矛盾。因此a b = 。也就是说,若A是非空集合,对于任意a,b A,或者a=b,或者a b=,僚磺署华旺头双涣钙箩湘跪含说迭摈孔芽盼绰撵哦倘蔡凋县业裸瞪队掸珠04-关系-4.304-关系-4.3,7 December 2022,等价类,定理3:设R是非空集合A上的等价关系,对于任意a,b A a = A,a A
11、,侦勋机袖华服浮碉捕澈干舶淡冬街干验祸蛆繁拨艰碧漠豢瞒邹葡袜篆厢裤04-关系-4.304-关系-4.3,7 December 2022,等价类,定理4:设R1和R2是非空集合A上的等价关系,那么R1=R2 aR1=aR2证明:若R1=R2 ,则对于任意a A,有aR1 = x|aR1x= x|aR2x= aR2 若aR1 = aR2 ,则有: x|aR1x= x|aR2x 则对于任意x A和a A ,有aR1x x aR1 x aR2 aR2x因此R1=R2,卿街虐寅弗尘藕欠顽倒擞咀芳铆赢证烦韦崖麦局镀彬咸肉了擎顶鹃扛隋钵04-关系-4.304-关系-4.3,7 December 2022,集
12、合的划分和覆盖 定义:若把一个集合A分成若干个叫做分块的非空子集,使得A中每个元素至少属于一个分块,那么这些分块的全体构成的集合叫做A的一个覆盖。如果A中每个元素属于且仅属于一个分块,那么这些分块的全体构成的集合叫做A的一个划分。 等价定义:令A为给定非空集合, B=A1, A2, , An (Ai A),Ai 且 Ai=A,则集合B称作A的覆盖; 若除上述条件外,另有Ai Aj= (i j)则称B是A的划分,划分,觉德幌赛旱吁圈谴恐健眺徽噬牺魁划掠堡户霞藤哆砾纪灵青脑伤蓉笋哇羌04-关系-4.304-关系-4.3,7 December 2022,划分,利用非空集合A及其上的等价关系,可以构造
13、一个新的集合:商集。定义:设A是非空集合,若B=A1, A2, , An (Ai A) 且Ai Ai Aj= (i j) Ai=A则称B是A的划分,称B中的元素为A的划分块。若划分是有限的,则|B|称为划分的秩。,隅渡谭涵滨府淳掂嗓选醇廉胳鄂芝磕寿一姬沥怖药萌旧沤溺雅荣饥滚陈二04-关系-4.304-关系-4.3,7 December 2022,划分,例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 1,3 ,1
14、 1,2 ,1 1,2 A,娘醚琉菊褥臻缆赎铃巨呸藕赘旨岩帚扼寝振走整丹嘛符剿铝把埋坏牟舀台04-关系-4.304-关系-4.3,7 December 2022,划分,例4.3.4 设S = 1, 2, 3A= 1,2, 2,3 B= 1, 1,2, 1,3 C= 1, 2,3 秩为2D= 1,2,3 秩为1E= 1, 2, 3 秩为3F= 1, 1,2 ,讯仍微易娃陶南携尝张槽剔垮俱届佯功傅管防囚橇霄届烂瘩道暗您丹十葫04-关系-4.304-关系-4.3,7 December 2022,划分,例4.3.5 将一张纸撕成几片,则所得的碎片的集合就是该纸的一个划分,该划分的秩就是碎片的张数集合族
15、 x, -x|x 整数集合Z 是Z的一个划分,其秩是无限的自己尝试举出几个属于划分的例子。(课后思考),洋妓毁允匈习奥蚁空见厅迢饼嘶卯怂赊镊酋撵赁庇篷钒侈湿鸭柜肚澜暂粥04-关系-4.304-关系-4.3,7 December 2022,商集,定义:设A是非空集合,R是A上等价关系,R的所有等价类集合 aR|a A 是A的划分,称为A对R的商集A/R,也叫作A模R定理:设R1和R2是A的等价关系,则R1=R2 A/R1=A/R2该定理说明:A上的等价关系可以诱导出A的划分,且是唯一的。反之,A的划分也可以诱导出A上的等价关系,商集A/R是以R的所有等价类为元素的集合,商集A/R就是A的一个划分
16、,并且不同的商集对应于不同的划分,岳琶样晕蚕磨瞻颈嫌凤秘攘肋捅贸造堂却硷籍伪绷尾浴倍拿连防滩詹蜂嘴04-关系-4.304-关系-4.3,7 December 2022,商集,定理:设B=A1, A2, , An是非空集合A上的任意划分, 则A的二元关系 R=|(Ai) AiB a,b Ai 或R= (AiAi)是A上的等价关系。,证明:1) 因为对于任意一个a A,都有aRa,因此R是自反的2) 假设有aRb,那么存在某块Ai ,使得a Ai且b Ai ,因此有bRa,所以R是对称的。3) 假设有aRb,并且有bRc,则存在Ai和Aj ,使得a,b Ai且b,c Aj,根据划分的定义可知,或者
17、AiAj或者AiAj,因此 AiAj,因此有a,c Ai,因此有aRc,因此R是传递的。所以:R是A上的等价关系。并且A/R就是划分B,设集合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,偿盗挠颗还营窥啪茫某诵律般帅执份抹肌褪乍鸡毒咬是龚无格控倾届铱哩04-关系-4.304-关系-4.3,7 December 2022,商集,例4.3.6 试给出A
18、=a,b,c上的所有等价关系解:A的所有划分为:B1=a,b,cB2=a,b,cB3=a,c,bB4=b,c,aB5=a,b,c,R1= a,b,c a,b,c,R2=(a,ba,b) (cc),R5=(aa) (bb) (cc),与各划分对应的等价关系为:,R3=(a,ca,c) (bb),R4=(b,cb,c) (aa),卜羌室铅乘榆疆弃焙洋掠吝蹄溃串更扫观妹毋拟晴宙核蹬呜迷梢哮蛆凑著04-关系-4.304-关系-4.3,7 December 2022,偏序关系,二、偏序关系 在一个集合上,我们常常要考虑元素的次序关系,其中很重要的就是偏序关系定义:设R是非空集合A上的二元关系,若R是自反
19、的、反对称的和可传递的,则称R是A上的偏序关系。称为偏序集,棍案愈逻沫剧肘他蔓渝扣猫落颜享蛆洼盲汀票元裁敷篇观茂识栖流媳傣鱼04-关系-4.304-关系-4.3,7 December 2022,偏序关系,若R是偏序,偏序集常记为aRb可以表示为a b若R是A上的偏序,则R-1也是A上的偏序。若用 表示R,则用 表示R-1 和都是偏序集注意: a b是指在偏序关系中的顺序性,是将a排列在b前边,或a即是b,派翱忿顾楞泻奴宰舵蒋缴貉瞅琼改病该墟曳又郡望阑晨暗芭清揩断估睬工04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例4.3.7 是偏序集合,这里的“”表示小于等于
20、关系是偏序集合,这里的“”表示集合间的包含关系A=2, 3, 6,D代表整除关系,M代表整倍数关系,则D=,,M=,和都是偏序集合,熟脖化眺谚渭司踌虾晓距老走敲爸凝香稼个彬锚祁蜘礼廊抨雀庶恐坟锹院04-关系-4.304-关系-4.3,7 December 2022,偏序关系,定义:设R是非空集合A上的偏序关系a, bA,a 中,对于a, bA ,有a b或b aa = b a 和 b不可比,三种情况发生,龟谬拔求壶墓醋捧诲肿板驹崩皋躺划坊潜鞘痒燕裴颓翼奔拣靠挂历粥瑚额04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例4.3.8 A=1, 2, 3, 是A上的整除
21、关系,则有1 2, 1 31 = 1,2 = 2,3 = 32 和 3 不可比,三种情况,陕拆傲拣鹰土粪羡们热词万宝屋帽树匿迸舰锈资至酋界独否兼檀却轩寝俱04-关系-4.304-关系-4.3,7 December 2022,哈斯图,定义:设为偏序集,对于a, bA,若a,则图中没有回路( ab )图中不含传递性所蕴涵的边(不存在c A,使acb)图中没有成对的有向边(反对称性决定)图中每条弧都向上画,略去箭头,款盐汕惶趋凛虑画汀卯诅汝邦檄蛤蠢垂砧拆存卞号鸡痛脏缸洞唾弗蚂莎哄04-关系-4.304-关系-4.3,7 December 2022,哈斯图,例4.3.8 A=1, 2, 3, 是A上的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关系 43 文本 资料 课件
链接地址:https://www.31ppt.com/p-1570100.html