04-关系-4.3---文本资料课件.ppt

勋镀嗅邦软座洽曾率吏札敲封柞啡谷缚裸叮陀咳王算锰伴道罕雕撵斧抬沙04-关系-4.304-关系-4.3第四章第四章 关关 系系钦瞎瞥紊梭孟衡饰秆涨货顶焚仿衍芽弦辑盏宇般赡溯穷典映刀葬垮颤扒圈04-关系-4.304-关系-4.3第三节第三节 关系类型关系类型一、等价关系一、等价关系v集合中的各个元素总是具有某些有用的性质，时常不是把这些元集合中的各个元素总是具有某些有用的性质，时常不是把这些元素作为单一的个体，逐个地对待它们；而是按它们所具有的性质素作为单一的个体，逐个地对待它们；而是按它们所具有的性质进行分类，并根据这些性质处理它们，或者是使用它们在处理进行分类，并根据这些性质处理它们，或者是使用它们在处理实际问题时，可以不去考察那些不感兴趣的性质，而专注于感兴实际问题时，可以不去考察那些不感兴趣的性质，而专注于感兴趣的某些性质凡是具有同样性质的元素，可以看成是不可区分趣的某些性质凡是具有同样性质的元素，可以看成是不可区分的或相互等价的，也称它们之间存在等价关系的或相互等价的，也称它们之间存在等价关系卑体坑拧全雷宏驹懊斧蛙氛溶统调匈簇窖则临遏疲欣邻疽周废记织寸狭意04-关系-4.304-关系-4.3第三节第三节 关系类型关系类型一、等价关系一、等价关系v定义：定义：设设R是集合是集合A上的二元关系，上的二元关系，若若R是是自反的自反的自反的自反的、对称的对称的对称的对称的和和可传递的可传递的可传递的可传递的，则称则称R是是A上的上的等价关系等价关系等价关系等价关系。

若若 R，或者，或者xRy，称，称x等价等价y，记做，记做xy甄哩霸越韦猾乌靛椿期累肾宰菱岿屁膀娃梅馏液酝貉塔聋吞丙泳丛端吹疹04-关系-4.304-关系-4.3等价关系等价关系因为因为R是自反的，因此是自反的，因此R的关系图中每个结点都有有向环的关系图中每个结点都有有向环因为因为R是对称的，因此是对称的，因此R的关系图中的有向弧都是成对出的关系图中的有向弧都是成对出现，即若有从现，即若有从a到到b的弧，必定有从的弧，必定有从b到到a的弧的弧(任意两个结任意两个结点间或没有弧连接，或有成对的弧出现点间或没有弧连接，或有成对的弧出现)因为因为R是传递的，因此若有从是传递的，因此若有从a到到b的弧以及从的弧以及从b到到c的弧，的弧，必定有从必定有从a到到c的弧的弧蝎殉楞郎纸态民鳖清谨弹缄弟升枯袱峦退犬夸阔舜袍裳阎罩乃尺笑搽采部04-关系-4.304-关系-4.3等价关系等价关系例例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是是传递的传递的传递的传递的混逻琉拳折振舶突腑掩植蕾圾盆吴蓄彬停诣兑燥陶扑巾李呸母瞳框垦捡糠04-关系-4.304-关系-4.3等价关系等价关系假设假设a和和b住在同一房间，住在同一房间，d和和e和和f住在同一房间，住在同一房间，c住一间。

则住一间则R=,关系图为：关系图为：abcefd尺省簇干桔膜陋剐赚俄剔摹咖烧池庶甭凋舟婪拘辊榨枫姓嚣桓壬颠丧辙剧04-关系-4.304-关系-4.3等价关系等价关系整数集合整数集合Z中的相等关系、中的相等关系、在全集在全集U所有子集的集合中的相等关系，所有子集的集合中的相等关系，以及命题演算中的命题集合的以及命题演算中的命题集合的关系等关系等都是等价关系都是等价关系空集上的任意二元关系空集上的任意二元关系R是等价关系是等价关系衷撰帜拍迢麓累怖峪脱箱遂外碳桌烩低耘博褪叭该先耙羌丁燥止页亢矢棵04-关系-4.304-关系-4.3等价关系等价关系v定义：定义：设设m是一个正整数，是一个正整数，a和和b都是整数，若存在某整数都是整数，若存在某整数k，使得使得a-b=kma-b=km，则称，则称a a与与与与b b是模是模是模是模mm等价等价等价等价，记为，记为a a b (mod m) b (mod m)m叫作等价的叫作等价的模数模数模数模数乳产锑浑方哪每熬顺蒜芳尉倪篷烫翔别微睛绪澳雄甲我阀峭凄房足坤等冲04-关系-4.304-关系-4.3等价关系等价关系v定理：定理：模模模模mm等价是任何集合等价是任何集合等价是任何集合等价是任何集合A A Z 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，使得，使得a-b=pm，b-c=qm，所以，所以a-c=(a-b)+(b-c)=(p+q)m因此因此R是是传递的传递的传递的传递的综上所述，综上所述，R R是自反的、对称的和传递的，所以它是等价关系是自反的、对称的和传递的，所以它是等价关系是自反的、对称的和传递的，所以它是等价关系是自反的、对称的和传递的，所以它是等价关系溺睫讫周娟遂茂佐浴塑咏该噬佰申钨花持邯殖贷酬茁佯臀诞退业汽赚掷渍04-关系-4.304-关系-4.3等价类等价类v定义：定义：设设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a A，令，令 aaR R = x|x = x|x A A aRx aRx称称aaR R是是是是a a关于关于关于关于R R的的的的等价类等价类等价类等价类，简称，简称a的等价类，简记为的等价类，简记为a。

称称a为为aR的的表示元素表示元素表示元素表示元素aR称为元素称为元素a形成的形成的R的等价类）的等价类）若等价类个数有限，则若等价类个数有限，则R的不同等价类的个数叫作的不同等价类的个数叫作R R的的的的秩秩秩秩对于任意对于任意a A ， aR非空，因为非空，因为a aR按照按照R等价类的定义，是由集合等价类的定义，是由集合A中与中与a有等价关系有等价关系R的的所有元素，构成集合所有元素，构成集合aR常用a代替代替aR因此，任给集合因此，任给集合A及其上的等价关系及其上的等价关系R，必可写出，必可写出A上各个元素的等价类上各个元素的等价类癌钠踩穗蔽镊溉净潜爷绍茵贵盎搭龟中熙沂峡侠彻狰碍卿烹嘛彰惯繁狼说04-关系-4.304-关系-4.3等价等价类类例例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等价关系等价关系R的秩是的秩是3规帚释蜡坑揪咆约郁伺皇棘破蚀痕阅审安谆矛寂厉萝演汪谎探侦令蹈谐娱04-关系-4.304-关系-4.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, -2, 0, 2, 4, = 2R = -2R = 1R = , -3, -1, 1, 3, 5, = 3R = -1R = 三兽擎甲雷蝉迸束疲履记柿盏童抖极密枷直病卿抄工违烦岁托链季堂庄啦04-关系-4.304-关系-4.3等价类等价类v定理定理1：设：设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a,b AaRb aRb a=ba=b证明：证明：1) 若若若若a=ba=b，则，则a a=b，所以所以bRa， 根据根据R的对称性，可知的对称性，可知有：有：有：有：aRbaRb2)若若若若aRbaRb，对于任意对于任意x a，有有aRx，所以也有，所以也有xRa根据根据R的传递性，可知有的传递性，可知有xRb；根据；根据R的对称性，可知有的对称性，可知有bRx则则x b，所以，所以a b同理可证：对于任意同理可证：对于任意x b有有x a，即，即b a所以：所以： a=ba=baaR R = x|x = x|x A A aRx aRxxRa aRb aRb xRb胡狼嘲峙痔匈加戴裸蛀乓魁藩掇裸叭荐液陕症菇押甜雨冯曰肥舒迫庚准愿04-关系-4.304-关系-4.3等价类等价类v定理定理2：设：设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a,b A若若若若 R R，则，则，则，则a a b=b=证明：假设证明：假设a b ，则存在某个，则存在某个x A，有，有 x a b x a x b aRx bRx aRx xRb aRb与与 R矛盾。

因此矛盾因此a b = v也就是说，也就是说，若若若若A A是非空集合，对于任意是非空集合，对于任意是非空集合，对于任意是非空集合，对于任意a,b a,b A A，或者或者或者或者a=ba=b，或者，或者，或者，或者a a b=b=僚磺署华旺头双涣钙箩湘跪含说迭摈孔芽盼绰撵哦倘蔡凋县业裸瞪队掸珠04-关系-4.304-关系-4.3等价类等价类v定理定理3：设：设R是非空集合是非空集合A上的等价关系，对于任意上的等价关系，对于任意a,b A a =a = A Aa a A A证明：证明：1) 对任意的对任意的x a，可知，可知x A，所以，所以 a Aa Aa A2) 对任意的对任意的x A，有，有x x，所以，所以x a因此因此A aa Aa A所以：所以： a = Aa A侦勋机袖华服浮碉捕澈干舶淡冬街干验祸蛆繁拨艰碧漠豢瞒邹葡袜篆厢裤04-关系-4.304-关系-4.3等价类等价类v定理定理4：设：设R1和和R2是非空集合是非空集合A上的等价关系，那么上的等价关系，那么R R1 1=R=R2 2 aaR1R1=a=aR2R2证明：证明：若若若若R R1 1=R=R2 2 ，则对于任意，则对于任意a A，有，有aR1 = x|aR1x= x|aR2x= aR2 若若若若aaR1 R1 = a= aR2R2 ，则有：，则有： x|aR1x= x|aR2x 则对于任意则对于任意x A和和a A ，有，有aR1x x aR1 x aR2 aR2x因此因此R1=R2 卿街虐寅弗尘藕欠顽倒擞咀芳铆赢证烦韦崖麦局镀彬咸肉了擎顶鹃扛隋钵04-关系-4.304-关系-4.3集合的划分和覆盖集合的划分和覆盖 定义：定义：若把一个集合若把一个集合A分成若干个叫做分块的非空子集，使得分成若干个叫做分块的非空子集，使得A中每个元素至少属于一个分块，那么这些分块的全体构成的集中每个元素至少属于一个分块，那么这些分块的全体构成的集合叫做合叫做A的一个的一个覆盖覆盖。

如果如果A中每个元素属于且仅属于一个分块，中每个元素属于且仅属于一个分块，那么这些分块的全体构成的集合叫做那么这些分块的。