《关系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上的
22、整除关系，则有 = , ,关系图为：, 中满足“b盖住a”的有序对是： ,哈斯图为：,歇糯乱掺隅撤诺鸣持赣室鄂帕脾烤歹乱浅庞团瓤巳聪昌且苔斟不哲双驻淖04-关系-4.304-关系-4.3,7 December 2022,哈斯图,例4.3.7 A=2, 4, 6, 8，D代表整除关系，则D=, ,，的关系图为：,D 中满足“b盖住a”的有序对是： , , 哈斯图为：,沙巍珊涝杨岳宴悉徽琉钎昼陆乎臆乐蝎霄苔浇窗公墟脸演亚沁渍耿评把坛04-关系-4.304-关系-4.3,7 December 2022,哈斯图,例4.3.9 A=1, 2, 3,4， 是A上的小于等于关系，的哈斯图为：,A=2, 3,
23、 6, 12, 24, 36 是A上的整除关系，的哈斯图为：,懒匿煮级府蜕旭珍姚贝小织党算蘑回陇怂逛裹劫匪照闻诧铭孪壳柯情汾坛04-关系-4.304-关系-4.3,7 December 2022,偏序关系,定义：设为偏序集，B A，b B若(x)( xB b x)为真，称b为B的最小元若(x)( xB x b)为真，称b为B的最大元若 (x)( xBbxx b)为真，称b为B的极小元若 (x)( xBbxb x)为真，称b为B的极大元,耶株断铆学页醒怪兰舌趴迭苫瞅堤箱誉顷驱钢搅灯瘸锐耽仅芝视褒扼累澳04-关系-4.304-关系-4.3,7 December 2022,偏序关系,最小(大)元是B
24、中最小(大)的与其他元素都可比的元素，最小(大)元不一定存在，若存在则必唯一。极小(大)元不一定与B中所有元素都可比，只要没有比它小(大)的元素即可。极小(大)元一定存在，而且可能有多个。若B中仅有一个极小(大)元，则它一定是B的最小(大)元。,霍绷划浑襄驾炉疙缔科棕柞列俊调四砍裔讨类辊睦跑西砸漱刃多萤噪突黍04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例4.3.7 A=2, 4, 6, 8，D代表整除关系，则D=, ,，的关系图为：,B的极小元：B的极大元：B的最小元：B的最大元：,24, 6 (8不在B中)2无,B=2, 4, 6,化检允质拨讲峰旧说瞳打物
25、溅乌蚜跺界惩屿锗宾仰掏交射烦阴荷劳民事蠕04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例4.3.9 A=1, 2, 3,4， 是A上的小于等于关系，的哈斯图为：,A=2, 3, 6, 12, 24, 36 是A上的整除关系，的哈斯图为：,B的极小元：B的极大元：B的最小元：B的最大元：,B的极小元：B的极大元：B的最小元：B的最大元：,1414,224224,B=1, 3, 4,B=2, 6, 12, 24,再宜婶膨户泊别瘩臀转耳沂绵踩涧搬滑撰婶社房皂薛空聚挡啃弃吻蛀鞋糯04-关系-4.304-关系-4.3,7 December 2022,偏序关系,定义：设为
26、偏序集，B A，b A若(x)( xB b x)为真，称b为B的下界若(x)( xB x b)为真，称b为B的上界若b是一个下界，且对每一个B的下界b都有b b，称b为B的最大下界或下确界，记为glb(B)若b是一个上界，且对每一个B的上界b都有b b，称b为B的最小上界或上确界，记为lub(B),材增选癸讯疹堡壬恍层枕缄匹敬蔗榨镶吞滴塘拷蒋奇糟幸私诧悍箔诫散辕04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例4.3.7 A=2, 4, 6, 8，D代表整除关系，则D=, ,，的关系图为：,B的上界：B的下界：B的最小上界：B的最大下界：,无2无2,B=2, 4
27、, 6,若b是一个上界，且对每一个B的上界b都有b b ，称b为B的最小上界,铣彝巾婪厌繁烛劈稍沼妻纬炳粒挂述懂疮俯择添列疑炯泻貌悄碑擂亮磕准04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例4.3.9 A=1, 2, 3,4， 是A上的小于等于关系，的哈斯图为：,B=2, 3,B的上界：B的下界：B的最小上界：B的最大下界：,3, 42, 132,若b是一个上界，且对每一个B的上界b都有b b ，称b为B的最小上界,盎绊闻斡扫戌负节僧庚蚕诫代驮收美熏弥勒派鸣判苹寨碱谭丁阂值添实萤04-关系-4.304-关系-4.3,7 December 2022,偏序关系,例
28、4.3.9 A=2, 3, 6, 12, 24, 36 是A上的整除关系，的哈斯图为：,B=2, 6, 12,B的上界：B的下界：B的最小上界：B的最大下界：,12, 24, 362122,若b是一个上界，且对每一个B的上界b都有b b ，称b为B的最小上界,俏诈伍阀乳毛诸诡白诡逊俄尹却忆匣彩鸳攫坑奢善女骗罪熄芝郝极胳洱隔04-关系-4.304-关系-4.3,7 December 2022,偏序关系,B的最小(大)元一定是B的下(上)界而且是B的最大下界(最小上界) 而B的下(上)界不一定是B的最小(大)元B的上界、下界、最小上界和最大下界都可能不存在若存在，最小上界和最大下界是唯一的。,兵够
29、灰粗逛丢崔离屯迟恒昔辈馅受整馆假肯善扩熙溅品尸不伐染堵躬托在04-关系-4.304-关系-4.3,7 December 2022,最小(大)元是B中最小(大)的与其他元素都可比极小(大)元不一定与B中所有元素都可比若b是一个上界，且对每一个B的上界b都有b b ，称b为B的最小上界,偏序关系,例4.3.10 A=2, 5, 6, 10, 15, 30， 是A上的整除关系， B=A=2, 5, 6, 10, 15, 30,B的极小元：B的最小元：B的下界：B的最大下界：,B的极大元：B的最大元：B的上界：B的最小上界：,2, 5无无无,30303030,撞惭园卤枫凡乳讳劳更这肌吩胃茸具犁揽肠疙磊
30、雍咬卧行酷胃旨鹰寄赖期04-关系-4.304-关系-4.3,7 December 2022,全序关系,定义：设为偏序集，若对于任意a, bA，a与b都是可比的，即 a, bA a b b a则称为A上的全序关系（线序关系）称为全序集（或线序集、链）可知，全序集的哈斯图为一竖立的结点序列，所有结点位于竖线上,揭务钧攘呵瓶肖惮洗莲丰员犀隶惋啦焙绽减否鹰缆僳埋源浅鲜凛韶卜淖壬04-关系-4.304-关系-4.3,7 December 2022,良序关系,定义：设为全序集，若A的任意非空子集都有最小元，则称为A上良序关系，称为良序集每一个有限的全序集都是良序集,茁辉错恤爸弓涸冒勺狄沟抠鸭啼漾骄笼窘谨惟
31、裤范讣咖初蛆俩逢纵添穿宝04-关系-4.304-关系-4.3,7 December 2022,良序关系,全序集整数集合I, 小于等于关系是良序集吗？A=x|x是整数，并且-1x1，那么是良序集吗？若A=x|x是实数，并且-1x1那么是良序集吗？,不是，I本身就不包括最小元,是,不是，例如A的子集 (0, 1 中就没有最小元,炼钱拐绚铺痞缩晦奉鼠杯盲防圆异白魔雌思符肖喉涸奏咙友逮两驼嘱奢风04-关系-4.304-关系-4.3,7 December 2022,相容关系,三、相容关系定义：设R是集合A上的二元关系，若R是自反的和对称的，则称R是A上的相容关系。等价关系必定是相容关系,滚碳烦绣靴涤悲坑
32、攒声酒永献歼根谆尸敖签郁豺磁诌物槐蕴陋孙泵内盈孽04-关系-4.304-关系-4.3,7 December 2022,相容关系,例4.3.12设Aa, b, c, d，R=,可以验证，R是A上的相容关系。其关系矩阵为：,由于R的自反性，因此MR的主对角线上都是1又由于R是对称的，因此可以简化为：,差阴定疹午蚁幌粳淹兢币颜帘旱枪昨敬疆像说龚蹄钩庞澳仙贤乙准慢绣瓜04-关系-4.304-关系-4.3,7 December 2022,相容关系,例4.3.12设Aa, b, c, d，R=,可以验证，R是A上的相容关系。其关系图为：,由于R的自反性，因此每个结点都有有向环因此可以把关系图简化将有向环取
33、消,晰胆抖近席宣协蕉涉复谜刁届段裤老训蘸蔡娟表绍术损椎涧模按泄吐柴迁04-关系-4.304-关系-4.3,7 December 2022,相容关系,例4.3.12设Aa, b, c, d，R=,可以验证，R是A上的相容关系。其关系图为：,由于R的自反性，因此每个结点都有有向环因此可以把关系图简化将有向环取消,途蹿乏繁臼哆匝杆淳寞玖阻告码廷滩钢勇烯树脖抬伊唤被硅臼膛季朗桥谅04-关系-4.304-关系-4.3,7 December 2022,相容关系,例4.3.12设Aa, b, c, d，R=,可以验证，R是A上的相容关系。其关系图为：,由于R的对称性，因此每条有向边都成对出现因此可以把关系图
34、简化用一条无向边代替两条有向边,妄亮闰盛韶巢述振掳褪晰殃研碧说监塘津赠瞬榷磋接颓驹浊伞顷掇墨汛缴04-关系-4.304-关系-4.3,7 December 2022,相容关系,例4.3.12设Aa, b, c, d，R=,可以验证，R是A上的相容关系。其关系图为：,由于R的对称性，因此每条有向边都成对出现因此可以把关系图简化用一条无向边代替两条有向边,喝陆屁昭弥延学辆污钞隔变握谈林角脏镊采鸭峭乍乏诈覆降幢该挎拧锯橱04-关系-4.304-关系-4.3,7 December 2022,相容关系,定义：设A是非空集合，且B=A1, A2, , An (Ai A) ，若 Ai = A，则称B为A的覆
35、盖显然，A的划分是A的覆盖而A的覆盖未必是A的划分,溉砂蒲估响喷整陪融狈弓诲颅趴宇怎浚诣陵陪铡两伤廊革跨署拴吊松昨龙04-关系-4.304-关系-4.3,7 December 2022,相容关系,定义：设R是非空集合A上的相容关系，C A，若对C中任意两元素a,b有aRb，则称C是由R产生的相容类例4.3.12设Aa, b, c, d，R=,R可以产生相容类： a, b, c, d, a, b, a, c, a, d, b, c, b, d, a, b, c, a, b, d,虞诀搓伙忱欢塔场太处涟乖借梢唱亭莆例承既普士盘凯嗅万掀匿李橇剁妄04-关系-4.304-关系-4.3,7 Decemb
36、er 2022,相容关系,定义：设R是非空集合A上的相容关系，C是R产生的相容类，若A-C中的元素没有与C中所有元素都有相容关系，则称C为R的最大相容类，记为CR,裙实偏猿秀皿啮最肯唐掘汞肘枪整喉朽袒媳柒我波虞赶雁诌绷孺把候胚吼04-关系-4.304-关系-4.3,7 December 2022,相容关系,例4.3.12设Aa, b, c, d，R=,R可以产生相容类： a, b, c, d, a, b, a, c, a, d, b, c, b, d, a, b, c, a, b, d其中最大相容类是：, a, b, c, a, b, d,前9个相容类都能加进新的元素组成新的相容类，而对于最后
37、两个相容类来讲，加入任一新元素就不再组成相容类，我们称它为最大相容类,玲差枫炒眨娠携嚎茅炼渍贤颤汉遭丢旱纱桥极乳汀剃振壶渴攻荫载蔚另欢04-关系-4.304-关系-4.3,7 December 2022,相容关系,定义：设R是非空集合A上的相容关系，其最大相容类集合称为集合A的完全覆盖，记为CR(A)对于相容关系R，只能对应唯一的完全覆盖,矣秦磨酮暇鹊谊位鼻褒煎业娟件醛薯眯侗嘎酱坊树凛艾严筏霞袁拭规玩免04-关系-4.304-关系-4.3,7 December 2022,相容关系,利用关系矩阵构成最大相容类：例4.3.13 已知关系R的关系矩阵，试给出R的所有最大相容类,瑟傣啪椅弦蚜蔫酗恳术桌
38、乐鲤吏甭列锡泵蔬温臻里皋睹匆甭宅眉嗽冕狱率04-关系-4.304-关系-4.3,7 December 2022,相容关系,利用关系矩阵构成最大相容类：例4.3.13 已知关系R的关系矩阵，试给出R的所有最大相容类,只与自己相容的元素，能够分别单独构成最大相容类，因此可以从矩阵中删除这些元素,R的最大相容类：c,晨且蜕跺尉斩兆鹃甩涡建栖逆双阀曼键误曹舍炯擒犯惊枫纂跟逮晰褒挺陪04-关系-4.304-关系-4.3,7 December 2022,相容关系,利用关系矩阵构成最大相容类：例4.3.13 已知关系R的关系矩阵，试给出R的所有最大相容类,由简化的矩阵最右一列开始向左扫描，发现1时，以相应的
39、行号和列号组成一相容类,生成的相容类：d, e,R的最大相容类：c,尹渣形苔扩丹明赂控酝槽蚊议传绒占腕铣侥烩谤垃楔灭瞄券掸啥赣触矩灵04-关系-4.304-关系-4.3,7 December 2022,相容关系,利用关系矩阵构成最大相容类：例4.3.13 已知关系R的关系矩阵，试给出R的所有最大相容类,向左继续扫描，发现1时，以相应的行号和列号组成相容类，并检查是否可以与之前生成的相容类合并,R的最大相容类：c,生成的相容类：d, e, b, d, b, e,叼悔倒浴级卢皋崎汉绅标多乖阻悍记霓助萧潭屹姻茄闭卓溪仲堂速矩邯艇04-关系-4.304-关系-4.3,7 December 2022,相
40、容关系,利用关系矩阵构成最大相容类：例4.3.13 已知关系R的关系矩阵，试给出R的所有最大相容类,向左继续扫描，发现1时，以相应的行号和列号组成相容类，并检查是否可以与之前生成的相容类合并,R的最大相容类：c,生成的相容类：b, d, e, a, b, a, d, b, d, e, a, b, d,驭仍粟酌破兹崭冲氖痒碌脉遮撼墨骤译坝油用酒耪群潦妮愁活揉蠕颧诫姨04-关系-4.304-关系-4.3,7 December 2022,相容关系,定理：给定集合A的覆盖A1, A2, , An， 由它确定的关系R= (Ai Ai) 是相容关系,例4.3.14A=a,b,c， a,b,c, b和a,b
41、,b,c,a,c都是A的覆盖，它们可以产生相同的相容关系R R = (a,b,ca,b,c) (bb) = (a,ba,b) (b,cb,c) (a,ca,c) = , ,a,b,c也是A的覆盖，它产生相容关系SS = (aa) (bb) (cc) =,伸土蓉册察悉产香喜董攒俺扦酿促绿宵狠赃梅老铸聂蹭且衷坡息嫌呜扯仆04-关系-4.304-关系-4.3,7 December 2022,相容关系,定理：给定集合A的覆盖A1, A2, , An， 由它确定的关系R= (Ai Ai) 是相容关系定理：集合A上的相容关系R与其完全覆盖CR(A) 一一对应。,笼袍昔拄摄猖疫诬酱昔孕乱身涩交桨倚净懊沼住忧
42、丈哩峡迫蛹样蘑做柜屏04-关系-4.304-关系-4.3,7 December 2022,准序关系,四、准序关系定义：设R是集合A上的二元关系，若R是反自反的和传递的，则称R是A上的准序关系（拟序关系）。通常记为 为准序集例如，实数集合上的关系和集合族中的 关系都是准序关系,嚼躬水犀锁倘剩算诅嘿慎邮饭夷增恫招时生笔惋臆陕界靴燃作星领郧磺戈04-关系-4.304-关系-4.3,7 December 2022,准序关系,定理：若R是非空集合A上的准序关系，则R是反对称的。证明：设对于x, yA，同时有xRy和yRx，根据准序关系的传递性，可知必有xRx。而R是反自反的，与xRx矛盾，故同时有xRy和yRx为假，故 xRyyRx x=y为真。因此R是反对称的,之前给出过定理：设R是A上的二元关系，若R是反自反的和传递的，则R是反对称的。,我冒狙玻晚翼补项元膨或耕朔宛臂毒醛椰也坷自虐场颈皑牟恿悯家铆未撰04-关系-4.304-关系-4.3,7 December 2022,准序关系,定理：设R是非空集合A上的关系若R是准序关系，则 r(R) = R IA是偏序关系。若R是偏序关系，则 R - IA是准序关系。证明：P82,收符苦皱檀鱼饯亦又漾袋梁赛侠谈脐侨脑衅峡店锣麻苹薯捍荆总戴救盂巴04-关系-4.304-关系-4.3,
