《第3章二元关系》由会员分享，可在线阅读，更多相关《第3章二元关系（154页珍藏版）》请在金锄头文库上搜索。
1、第3章 二元关系第第3章章 二元关系二元关系 3.1 基本概念基本概念3.2 关系的合成关系的合成3.3 关系上的闭包运算关系上的闭包运算3.4 次序关系次序关系3.5 等价关系和划分等价关系和划分 但迫笺营泼谐冀索恩沸蚤猪炙募鲸愿饭鸳瑟庞术囤庞挺惯掀孙陕剁馏坟臀第3章二元关系第3章二元关系第3章 二元关系3.1 基本概念基本概念 3.1.1关系关系的数学概念是建立在日常生活中关系的概念之上的.让我们先看两个例子例1设A=a,b,c,d是某乒乓球队的男队员集合,B=e,f,g是女队员集合.如果A和B元素之间有混双配对关系的是a和g,d和e.我们可表达为:R=a,g,d,e抡哎扣害枯尧嚷荷烫测恍
2、屏日贼蔬晶哆谍你寿垮饱棕挽芒跺扭氟班李棠楞第3章二元关系第3章二元关系第3章 二元关系这里R表示具有混双配对关系的序偶集合.所有可能具有混双配对关系的序偶集合是:AB=x,y|xAyB=a,e,a,f,a,g,b,e,b,f,b,g,c,e,c,f,c,g,d,e,d,f,d,g浑淫讣轧咸贾滦峻蝎儡蜜努鲁逐伙英伎尾坞遣幢乍蛙眯忌百珠高烘隆姬铁第3章二元关系第3章二元关系第3章 二元关系例2设学生集合A1=a,b,c,d,选修课集合A2=日语,法语,成绩等级集合A3=甲,乙,丙.如果四人的选修内容及成绩如下:a日乙b法甲c日丙d法乙我们可表达为S=a,日,乙,b,法,甲,c,日,丙,d,法,乙,
3、这里S表示学生和选修课及成绩间的关系.而可能出现的全部情况为萍汞捅福亩趴送筐烫硼鸭闭穿栅钾窑曼檬靠萎更崇辊祖拒或膨祷贯鞭共跳第3章二元关系第3章二元关系第3章 二元关系A1A2A3=x,y,z|xA1yA2zA3=a,日,甲,a,日,乙,a,日,丙,a,法,甲,a,法,乙,=a,法,丙,b,日,甲,b,日,乙,b,日,丙,b,法,甲,=b,法,乙,b,法,丙,c,日,甲,c,日,乙,c,日,丙,=c,法,甲,c,法,乙,c,法,丙,d,日,甲,d,日,乙,=d,日,丙,d,法,甲,d,法,乙,d,法,丙拘忆柱屡伺神附即疮蒜弧秘训封猾寓喊垮惫星饿动负产撅浓蘑陕昂溢丸醋第3章二元关系第3章二元关系
4、第3章 二元关系定义3.11(1)AB的子集叫做A到B的一个二元关系.(2)A1A2An(n1)的子集叫做A1A2An上的一个n元关系.(3)的子集叫做A上的n元关系论扦载否竞哪牙局蹈绞骑母扭惕喀嗜胸速摔遍梳潭酶泥越认肋拜蠢捏胰录第3章二元关系第3章二元关系第3章 二元关系从定义可看出,关系是一个集合,所有定义集合的方法,都可用来定义关系例1,例2是列举法的例子一个谓词P(x1,x2,xn)可以定义一个n元关系R:R=x1,x2,xn|P(x1,x2,xn)例如,实数R上的二元关系可定义如下:=x,y|xRyRxy反之,一个n元关系也可定义一个谓词:P(x1,x2,xn)=1(真),当x1,x
5、2,xnR时0(假),当x1,x2,xnR时泉欠设荧刚象醇魏磨穴掳篆钎寐陌苑干绕嘶碑牢或迎彭品绢桥阉瓷寿阂钎第3章二元关系第3章二元关系第3章 二元关系当n=1时,R=x|P(x)称为一元关系.它是一重组集合,表示论述域上具有性质P的元素集合,其意义与R=x|P(x)相同,仅记法不同而崐已例如,设P(x)表示“x是质数”,论述域是N,则质数集合可表示为xP(x)或xP(x)试枢寺嵌扳庶噎核尼匣烯暑前环热郁痈缚吗档僧畜舔屈兜匙徒褐羽逞猜蓉第3章二元关系第3章二元关系第3章 二元关系关系也可归纳地定义.自然数上的小于关系可定义如下:(1)(基础)0,1(2)(归纳)如果x,y,那么(i)x,y+1
6、(ii)x+1,y+1(3)(极小性)对一切x,yN,xy当且仅当x,y是由有限次应用条款(1)和(2)构成嘘槽曾总浦兽婚村强睬浇地宗邻乌祷糯缠销狈干氨守滑吐早淮盒晌苫哪赠第3章二元关系第3章二元关系第3章 二元关系定义3.12设R是的子集,如果R=,则称R为空关系,如果,则称R为全域关系.现在定义关系相等的概念,在关系相等的概念中不仅需要n重组集合相等,还需其叉积扩集也相同.定义3.13设R1是上的n元关系,R2是上的m元关系.那么R1=R2,当且仅当n=m,且对一切i,1in,Ai=Bi,并且R1和R2是相等的有序n重组集合撩掸贪蛰伙扶稽掌揪移似拙终痪艰宛抹突碌雷粱率奥高哦圆男氦快串役佳第
7、3章二元关系第3章二元关系第3章 二元关系3.1.2二元关系最重要的关系是二元关系.本章主要讨论二元关系,今后术语“关系”都指二元关系.若非二元关系将用“三元”或“n元”一类术语指出.二元关系有自己专用的记法和若干新术语设A=x1,x2,x7,B=y1,y2,y6R=x3,y1,x3,y2,x4,y4,x6,y2蠢看罐债蛹制栽假杰为言剑雁赃澈添蛀结帧留魂坏硼搭醚懈训收奥恳喂避第3章二元关系第3章二元关系第3章 二元关系A到B的二元关系R可如图3.11那样形象地表示.x3,y1R,也可写成x3Ry1,称为中缀记法,读做x3和y1有关系R.中缀记法常用来表示诸如“=”,“”,“”等关系,例如3,5
8、,通常写作35.钳聋港衫肤笑韩命迁纷滤昼魂粟撒担娃擅喇闰油产累霍仪锗程董丰巳眨袒第3章二元关系第3章二元关系第3章 二元关系图3.11伍假矛扑陆塔愧竭秒偷咨栈梦峰鲁择伍份尖挎盐戈伪捅舰寨晃痪眩础诊赘第3章二元关系第3章二元关系第3章 二元关系A叫做关系R的前域,B叫做关系R的陪域D(R)=xy(x,yR)叫做关系R的定义域R(R)=yx(x,yR)叫做关系R的值域关系是序偶的集合,对它可进行集合运算,运算结果定义一个新关系.设R和S是给定集合上的两个二元关系,则RS,RS,R-S,等可分别定义如下:x(RS)yxRyxSy x(RS)y xRyxSyx(R-S)yxRyx$yx()y xRy匡
9、杠嗅倦俊拘拱木巍克洪腔敏谢桥息名盔知具十位措尺撵郭烈摆葫而舀浮第3章二元关系第3章二元关系第3章 二元关系例3平面上的几何图形是平面R2的子集,也是一种关系.设(参看图3.12)R1=x,yx,yR2x2+y29 R2=x,yx,yR21x3)(0y3)R3=x,yx,yR2x2+y24则R1R2=x,yx,yR2(x2+y29(1x30y3)嘎昂呜巨射汐凹夺携侮雕泣株省丈献砧崇享喻临煎王塞贤典忌伊悉箭月檀第3章二元关系第3章二元关系第3章 二元关系R1R3=x,yx,yR2(x2+y29x2+y24)R1-R3=x,yx,yR2(x2+y29L(x2+y24)=x,yx,yR2L(x2+y2
10、4)沾陡盖札吼皆棚功枫竿姬盒渝昼啮皑营弦塘湍飘绿辰宣细写刀域者鞠炉美第3章二元关系第3章二元关系第3章 二元关系图3.12压适变筋逐园庆镭轧指畴诌给铅锥郧虱阮陕渊札够煎涵硅铺阜攻件公祷彦第3章二元关系第3章二元关系第3章 二元关系3.1.3关系矩阵和关系图表达有限集合到有限集合的二元关系时,矩阵是一有力工具定义3.14给定集合A=a1,a2,am和B=b1,b2,bn,及一个A到B的二元关系R.使.rij=1,如果aiRbj0,如aiRbj则称MR=rij矩阵是R的关系矩阵.昭耐焚照丑将凄就仕卸侍盖幼霓挫周缎届鸽蛰孝坷原密砷逻沦餐吉琴郴梁第3章二元关系第3章二元关系第3章 二元关系例4设A=a
11、1,a2,B=b1,b2,b3,R=a1,b1,a2,b1,a1,b3,a2,b2,则其关系矩阵为b1b2b3a1101a2110即遭芝秸候陌擂瞅蔫臭奥净对麦矛噶朴偏赖妒绩呢督菲渴琼某憨攒徘撬铂砂第3章二元关系第3章二元关系第3章 二元关系例5设A=1,2,3,4,A上的二元关系R=x,yxy,试求出关系矩阵解R=4,1,4,2,4,3,3,1,3,2,2,1润滁录禽蛆谚雕茎氓牌衙何逢碎疡芭政司既准贵瓤汞泥痹症确椒荣线阮襄第3章二元关系第3章二元关系第3章 二元关系图3.13运鞋顶艇驳耳矽梗弧碳誉镶仕啼删似丑离侥摹恤帜才逻捐抠葱养虱裸剑伶第3章二元关系第3章二元关系第3章 二元关系例6设A=1
12、,2,3,4,5,R=1,2,2,2,3,2,3,4,4,3,其图示如图3.13所示.图中结点5叫做孤立点利用关系R的图示,也可写出关系R.拈音潘缩匿谩鼻珊抓倔摘贾蓖荡噪赎碌医淖傣参茨帮庸某突收腥陆咬枷走第3章二元关系第3章二元关系第3章 二元关系3.1.4关系的特性在研究各种二元关系中,关系的某些特性扮演着重要角色,我们将定义这些特性,并给出它的图示和矩阵的特点定义3.15设R是A上的二元关系,(1)如果对A中每一x,xRx,那么R是自反的.即A上的关系R是自反的x(xAxRx)A=1,2,3,R1=1,1,2,2,3,3,1,2是自反的.其关系图和关系矩阵的特点如图3.14所示.测祈趴纹允
13、惺左拼球啼才歹朗汛挺侵闷骄花瘫量径兔涝娃盟虾蛇寝阔迷黍第3章二元关系第3章二元关系第3章 二元关系图3.14腋召欠韵兑绘濒钉凹篓骗系芜哇速唆氏疚令中威缓尊赦拿吵迟讳落痒慕姓第3章二元关系第3章二元关系第3章 二元关系(2)如果对A中每一x,xRx,那么R是反自反的.即A上的关系R是反自反的x(xAxRx)例如,A=1,2,3,R2=2,1,1,3,3,2是反自反的,其关系图和关系矩阵的特点如图3.15所示.图3.15哑秤倪瘸禁街研柜堡唇南啸忿般郑吧锋霖些凤熙椰哄饮摸犹费绷扦今术妇第3章二元关系第3章二元关系第3章 二元关系有些关系既不是自反的,又不是反自反的(如图3.16),例如,R3=1,1
14、,1,2,3,2,2,3,3,3图3.16主开草铲一炮舍刑膝庚涤惯霜族途否嗽独介语争弱稚迢贵迟朔度舒傈驶吩第3章二元关系第3章二元关系第3章 二元关系(3)如果对每一x,yA,xRy蕴含着yRx,那么R是对称的.即A上的关系R是对称的xy(xAyAxRyyRx)例如,A=1,2,3,R4=1,2,2,1,1,3,3,1,1,1是对称的.其关系图和关系矩阵的特点如图3.17所示瘁诈耐耽赌背章斯咖膨棺妒炬守诀忿挺匣嫩块艇陆伏镁碑秦涂家南剃性识第3章二元关系第3章二元关系第3章 二元关系图3.17概麦破伍髓当凋蛊毫诺截匀魏微于殖蓝挫馁屋宽札翻哭箍奶兹于盲导社咬第3章二元关系第3章二元关系第3章 二元
15、关系(4)如果对每一x,yA,xRy,yRx蕴含着x=y,那么R是反对称的.即A上的关系R是反对称的xy(xAyAxRyyRxx=y)例如,A=1,2,3,R5=1,2,2,3是反对称的,其关系图和关系矩阵的特点如图3.18所示.轩熙问愚酋岩索港椰沃诚伏较酵绿败诊犯鞠屿硫营嚷栽醒姥谆准碗坪辞番第3章二元关系第3章二元关系第3章 二元关系图3.18哟邱忘耗裹档泉军脐墅毕奢羊闹折摔绥盖桅叙亥虎堕溯霖死偷撑弃绑锣邻第3章二元关系第3章二元关系第3章 二元关系(5)如果对每一x,y,zA,xRy,yRz蕴含着xRz,那么R是传递的.即A上的关系R是传递的xyz(xAyAz=AxRyyRzxRz)例如,
16、A=1,2,3,4,R5=4,1,4,3,4,2,3,2,3,1,2,1是传递的.其关系图和关系矩阵如图3.110所示.图3.19哗膨愈感猪烃杠篓夫盗章煌薯翌缠孔揉通诡瓮坎绝末拂螟素弄索膝法磁陇第3章二元关系第3章二元关系第3章 二元关系图3.110连坑云崖催昼琢肿渗浆闺毙阻徊舌峻炭呐溯皑沉皿跌帐弛帘绷熊丑农崔蜕第3章二元关系第3章二元关系第3章 二元关系例7(a)任何集合上的相等关系是自反的,对称的,反对称的和传递的,但不是反自反的(b)整数集合I上,关系是自反的,反对称的,可传递的.但不是反自反的和对称的.关系是反自反的,反对称的,可传递的,但不是自反的和对崐称的(c)设=a,b,试考察上
17、的下列关系:(i)关系“与有同样长度”是自反的,对称的,可传递的,但不是反自反的和反对称的稽班抑誉怨棒及咖语储共张尿柬带质去钳怨茄褪宏槛荐耐富其藩陛洱骇育第3章二元关系第3章二元关系第3章 二元关系(ii)“xRy”当且仅当x是y的真词头”,这里R是反自反的,反对称的,可传递的,但不是自反的和对称的(iii)“xRy”当且仅当x的某真词头是y的一个真词尾”,这里R既不是自反的又不是反自反的,因为aaRaa,但abRab,既不是对称的也不是反对称的,并且不是传递的(d)非空集合上的空关系是反自反的,对称的,反对称的和传递的,但不是自反的.空集合上的空关系则是自反的,反自反的,对称的,反对称的和可
18、传递的蛔缓嵌囤贺浑辕藏牌架锑吁淹春簇惯苹面丧己假丙燎敷普硫凸慧四阔歹霓第3章二元关系第3章二元关系第3章 二元关系(e)基数大于1的集合上的全域关系是自反的,对称的和传递的,但不是反自反的和反对称的.例如图3.111所示的关系图3.111节馆士窒播将渗率环擞赌约膀补纱肚趁深队阜腮镶瞻卒札畜更柠贴身会因第3章二元关系第3章二元关系第3章 二元关系3.2 关系的合成关系的合成 3.2.1关系的合成前边已经指出,关系是序偶的集合,因此可以进行集合运算.本节介绍一种对关系来说,更为重要的运算合成运算.假设R1是A到B的关系,R2是B到C的关系(参看图3.21).合成关系R1R2是一个A到C的关系:如果
19、在关系图上,从aA到cC有一长度(路径中弧的条数)为2的路径,喻昂驾虹彼盏堑撅蛹捷炕脯疫炊耘主缠孝垛禄抬宴被课庆札蕉泌条儡磨肄第3章二元关系第3章二元关系第3章 二元关系其第一条弧属于R1,其第二条弧属于R2,那么a,cR1R2.合成关系R1R2就是由a,c这样的序偶组成的集合.芒遁览瞬薛站了池卉瑟曼起鲁几豁梧副海垫掣存痘话陡许爵犁费两反笔英第3章二元关系第3章二元关系第3章 二元关系图3.21几澈伐略拍揍鸦呕饱廖买和足穷朋灌循驻臭查眷饯嗡睡析伏扒粕棕皇萝班第3章二元关系第3章二元关系第3章 二元关系定义3.21设R1是从A到B的关系,R2是从B到C的关系,从A到C的合成关系记为R1R2,定义
20、为R1R2= a,c aAcCb bB a,b R1b,cR2例1(a)如果R1是关系“是的兄弟”,R2是关系“是的父亲”,那么R1R2是关系“是的叔伯”.R2R2是关系“是的祖父”毒逾夹腑综崔哦逃采草烁适窃菜融间羞邮渠夜摔桌货予枣浚坡遵噬寸络哪第3章二元关系第3章二元关系第3章 二元关系(b)给定集合A=1,2,3,4,B=2,3,4,C=1,2,3,设R是A到B的关系;S是B到C的关系.R=x,yx+y=6=2,4,3,3,4,2S=y,zy-z=1=2,1,3,2,4,3则RS=2,3,3,2,4,1.如图3.22所示.角因胶支庆辙壕多始朋够邓她袭营轩馁绑保儡暇麻揽闪皇疮篙锭浩访庙肺第3
21、章二元关系第3章二元关系第3章 二元关系图3.22座颠蓟邵遇出涯绷绞沂宗腕蛮容绚尔蝶吻符炳形患欧刽攫挨甄昧焊该数橡第3章二元关系第3章二元关系第3章 二元关系(c)设A=1,2,3,4,5,R和S都是A上二元关系.如果R=1,2,3,4,2,2,S=4,2,2,5,3,1,1,3则RS=1,5,3,2,2,5SR=4,2,3,2,1,4(RS)R=3,2R(SR)=3,2RR=1,2,2,2SS=4,5,3,3,1,1苇像熔杜荔尚舅酱替箕矮澳萌儿袜筋松徘履荤塑扫待阻浴束屉修辞坎碌慑第3章二元关系第3章二元关系第3章 二元关系(d)设R是A到B的二元关系,IA,IB分别是A和B上的相等关系,则I
22、AR=RIB=R(e)如果关系R的值域与关系S的定义域的交集是空集,则合成关系RS是空关系.下边介绍合成关系的性质澎轩狰慰乱寄鸣合谅辩捌歹润互砖煌磅啪顶育箍卤檬侗遏酮肤汰索渐射铰第3章二元关系第3章二元关系第3章 二元关系定理3.21设R1是从A到B的关系,R2和R3是从B到C的关系,R4是从C到D的关系,那么(a)R1(R2R3)=R1R2R1R3(b)R1(R2R3)R1R2R1R3(c)(R2R3)R4=R2R4R3R4(d)(R2R3)R4R2R4R3R4(a),(c),(d)部分的证明留作练习,我们仅证明(b)部分癸孔砾狡氓冕狰腊太营静猾菲煞填揭撰辙藏蔚屏犬浚歌寞揭逊抓坪竣缉宿第3章
23、二元关系第3章二元关系第3章 二元关系证先证明公式.因为a,cR1(R2R3)ba,bR1(b,cR2R3)ba,bR1(b,cR2b,cR3)b(a,bR1b,cR2)(a,bR1b,cR3)ba,bR1b,cR2ba,bR1b,cR3a,cR1R2a,cR1R3a,cR1R2R1R3即a,cR1(R2R3)a,cR1R2R1R3所以,R1(R2R3)R1R2R1R3帖隧卒传具泞骗贪夫驼庙惕呆畴哥酝庶寥脚午钡钒她蒙诺惺粳鄂葫双示再第3章二元关系第3章二元关系第3章 二元关系再证包含可能是真包含.举反例证明如果A=a,B=b1,b2,b3,C=cA到B的关系R1=a,b1,a,b2B到C的关系
24、R2=b1,c,b3,cB到C的关系R3=b2,c,b3,c那么,R1(R2R3)=,R1R2R1R3=a,c.此时R1(R2R3)R1R2R1R3.证毕唯矩思央袋暮捎伯窟过胀从杏杜宿冲甲磊撒透浚侥弱轰以獭缠驶猪习邓乘第3章二元关系第3章二元关系第3章 二元关系定理3.22设R1,R2和R3分别是从A到B,B到C和C到D的关系,那么(R1R2)R3=R1(R2R3)证先证(R1R2)R3R1(R2R3)设a,d(R1R2)R3,那么对某cC,a,cR1R2和c,d崐R3.因为a,cR1R2,存在bB使a,bR1和b,cR2.因为b,cR2和c,dR3,得b,dR2R3,所以a,dR1(R2R3
25、).这样,就证明了(R1R2)R3R1(R2R3).R1(R2R3)(R1R2)R3的证明是类似的,留给读者自证.上述证明也可用等价序列表达雨芝邓奈铡酋垫睁菏漠炸誓袁身粗殆阵妙盏侨狈拨介刀域逾怔撵醋怠秀久第3章二元关系第3章二元关系第3章 二元关系3.2.2关系R的幂当R是A上的一个关系时,R可与自身合成任意次而形成A上的一个新关系.在这种情况下,RR常表示为R2,RRR表示为R3等等,我们能归纳地定义这一符号如下定义3.22设R是集合A上的二元关系,nN,那么R的n次幂记为Rn,定义如下:(1)R0是A上的相等关系,R0=x,xxA(2)Rn+1=RnR愚止躬抓要粹摆杯灼展饲褒距搪沧瓤鱼夺萧
26、祖语杨杨闲拧迸溪送漱又扣赘第3章二元关系第3章二元关系第3章 二元关系定理3.23设R是A上的二元关系,并设m和n是N的元素,那么(a)RmRn=Rm+n(b)(Rm)n=Rmn可用归纳法证明.请读者自证.秒薪谅建怜攫票涤拥笑哦砰搬表着亢易渐跋膊竖折宛酝衙税绪毯攻荤揭常第3章二元关系第3章二元关系第3章 二元关系定理3.24设A=n,R是集合A上的一个关系,那么存在i和j使Ri=Rj而0ij证A上的每一二元关系是AA的子集,因为AA=n2,(AA)=,因此A上有个不同关系.所以,R的不同的幂不会超过个.但序列R0,R1,有+1项,因此R的这些幂中至少有两个是相等的.证毕为座血牌钝抠瑚北显周投蛮
27、咬消妇耶银臆吟涉鸭安努捉矮株铺灰丧甸贾佛第3章二元关系第3章二元关系第3章 二元关系定理3.25设R是集合A上的一个二元关系.若存在i和j,ij,使Ri=Rj.记d=j-i,那么(a)对所有k0,Ri+k=Rj+k(b)对所有k,m0,Ri+md+k=Ri+k(c)记S=R0,R1,R2,Rj-1,那么R的每一次幂是S的元素,即对nN,RnS胃土睬捡远鲜腹梨惩蜘建瞧衫组向凉朝粱枯贺蝎依署寄善祟泉泥柿啼列菠第3章二元关系第3章二元关系第3章 二元关系证(a)和(b)部分用归纳法证明,留作练习对于(c),设nN,如果nj,那么根据S的定义,RnS.假设nj,那么我们能将n表示为i+md+k,这里k
28、d,根据(b)部分,得Rn=Ri+k,因为i+kj,这证明了RnS.定理中的i,j,在实用时宜取最小的非负整数,以保证S中无重复元素.图3.23嫌涧循旧改欢父完辟杜汾绳淑趣照督鳖努姆判惫煞泻氯洒祟洁冶恿括目幂第3章二元关系第3章二元关系第3章 二元关系例2设A=a,b,c,d,R=a,b,c,b,b,c,c,d,其关系图如图3.23所示,则R0=a,a,b,b,c,c,d,dR2=a,c,b,b,b,d,c,cR3=a,b,a,d,b,c,c,b,c,dR4=a,c,b,b,b,d,c,c它们的关系图如图3.24所示庚放粟浑策决着纺徊愧依置置拱型奏淆帮敞烃婶芜贱肺钉侠酝误绊览揩重第3章二元关系
29、第3章二元关系第3章 二元关系图3.24溯叠苛坏律君凭雹舵祖溯薪府泻势扔员纵谐错沃彝搓尖纹遁闯预扬戏泞僻第3章二元关系第3章二元关系第3章 二元关系由于R4=R2,根据定理3.25(c),对所有nN,RnR0,R1,R2,R3,可见不必再算了.事实上易证R5=R3,R6=R4=R2,用归纳法可得R2n+1=R3和R2n=R2,这里n1蓄才侥更刹鲍侠飞熏墓果铃基腰莉绘办苫跳酒烦傍峨合陕榔慕疡懒磁哦崎第3章二元关系第3章二元关系第3章 二元关系3.2.3合成关系的矩阵表达定理3.26设X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zp,R是X到Y的关系,MR=aij是mn矩阵,S是Y
30、到Z的关系,MS=bij是np矩阵.则MRS=cij=MRMS,这里蛹袋琐条为菠窒莆肆渐卖糕蛛幽悬饮啥斌嘶墟尚汕轨增羡坛有件睬磅崩酬第3章二元关系第3章二元关系第3章 二元关系证因为如果存在某k使aik和bki都等于1,则cij=1.但aik和bkj都等于1意味着xiRyk和ykSzj.所以xi(RS)zj.可见如此求得的MRS确实表达了RS的关系.因此上述等式是正确的.如果不仅存在一个k使aik和bki都是1,此时cij仍为1,只是从xi到zj不止一条长度为2的路径,但等式仍然正确.上段的论证,已隐含了不止一个k的情况.本定理说明合成关系矩阵可用关系矩阵(布尔矩阵)的乘法表达.躬厘箩衅刨历轨
31、掳狱浅秽箔预泻祸叹莉懂堪联薪式趁喂诛唉汪闹焙讶以蹿第3章二元关系第3章二元关系第3章 二元关系例3设X=1,2,Y=a,b,c,Z=,R=1,a,1,b,2,c,S=a,b,则萤拍删武畔魁伴庇辉际赞埔举喘剑购伐馈涯绍布鸥囊乒辜悼灌谭摹挨奋肯第3章二元关系第3章二元关系第3章 二元关系图3.25韩宣荆条脏口纯梆瘪驭遇毙桨妙矩辽裕酌藤哟嵌吭华床庄卓涂锹臣瘸朋爬第3章二元关系第3章二元关系第3章 二元关系定理3.27关系矩阵的乘法是可结合的证利用关系合成的可结合性证明.(MRMS)MT=MRSMT=M(RS)T=MR(ST)=MRMST=MR(MSMT).不仅合成关系可用关系矩阵表达,而且关系的集合
32、运算也可用关系矩阵表达.设R和S是X到Y上的二元关系,MR=aij,MS=bij,cij是运算后所得新关系之关系矩阵的元素,则国拴杰瓷肘锣南付簿汛仟素淋忌走算帅剂溃崖敝兢银炎称档崩铜邯输尖鹿第3章二元关系第3章二元关系第3章 二元关系MRS=MRMScij=aijbijMRS=MRMScij=aijbijcij=LaijMR-S=MRcij=aij(Lbij)拌兹夫校挛叮娃托湘截铺嗣桨辰经甭椽暴制康偏卧枫磊井兆掘陶弛储弦世第3章二元关系第3章二元关系第3章 二元关系3.3 关系上的闭包运算关系上的闭包运算 3.3.1逆关系在讨论闭包运算时,要用到逆关系的概念,因此我们先介绍逆关系定义3.31设
33、R是从A到B的二元关系,关系R的逆(或叫R的逆关系)记为,是一从B到A的二元关系,定义如下:领咱容婆浆笆汰粉瓮盏诽案客袄荒隶氯茨详揍窃苟压淫老航鞘迭相汞傻贷第3章二元关系第3章二元关系第3章 二元关系例1(a)I上的关系(b)集合族上的关系的逆是关系(c)空关系的逆是空关系(d)=BA,即AB的全域关系的逆等于BA的全域关系.定理3.31设R是从A到B的关系,而S是从B到C的关系,则它缀表妖么赊归凯颧躁喘隆画偏祁趁粱朋褐在屎信形停憨耪季颜凝蚌逛肋第3章二元关系第3章二元关系第3章 二元关系定理3.32设R,R1和R2都是从A到B的二元关系,那么下列各式成立:这里 表示垂跟寡谣督答姬缝吭烟挥铂咙
34、净掐均耶徽弘翔瓜傀俘故洗裴欲空珐墓底冒第3章二元关系第3章二元关系第3章 二元关系3.3.2关系的闭包运算关系的闭包运算是关系上的一元运算,它把给出的关系R扩充成一新关系R,使R具有一定的性质,且所进行的扩充又是最“节约”的定义3.32设R是A上的二元关系,R的自反(对称,传递)闭包是关系R,使(i)R是自反的(对称的,传递的)(ii)RR(iii)对任何自反的(对称的,传递的)关系R,如果RR,那么RR詹装宪抛唯闺胆仗网妹锣掺武静灰容胺并拽拾所针拓阔钉牡传斯椽困毫环第3章二元关系第3章二元关系第3章 二元关系R的自反,对称和传递闭包分别记为r(R),s(R)和t(R).由定义可以看出,R的自
35、反(对称,传递)闭包是含有R并且具有自反(对称,传递)性质的最小关系.如果R已经是自反的(对称的,传递的),那么,具有该性质并含有R的最小关系就是R自身.下一定理说明这一点.定理3.34设R是集合A上的二元关系,那么(a)R是自反的当且仅当r(R)=R(b)R是对称的当且仅当s(R)=R(c)R是传递的当且仅当t(R)=R秘析蚌逻壕擞魏恫几肮芭碰烹郁守永殊辑行掣岂针蜡鸟盏微激供柴径白邹第3章二元关系第3章二元关系第3章 二元关系证(a)如果R是自反的,那么R具有定义3.32对R所要求的性质,因此r(R)=R.反之,如果r(R)=R.那么,根据定义3.32的性质(i),R是自反的.(b)和(c)
36、的证明是类似的,略.构造R的自反,对称和传递闭包的方法就是给R补充必要的序偶,使它具有所希望的特性.下面我们用关系图来说明如何实现这一点.缆应眨倦蛾睡羚门互账恤佰露锄凋过夜晶菏增腰矣建杉奎拯稍乙焦卿涨杉第3章二元关系第3章二元关系第3章 二元关系定理3.35设R是集合A上的二元关系.那么,r(R)=RE(这里E是A上相等关系,在本节中均如此.)证设R=RE.显然,R是自反的且RR.余下只需证明最小性,现假设R是A上的自反关系且RR.因R是自反的,所以RE,又RR,所以RRE=R.这样,定义3.32都满足.所以,R=r(R).证毕柒徊咳答丹锐蓖耗顷潜崭浇筐廷巡稚颊宗咸喳药奄闸抿状蛋淹窘烬嫌双苞第
37、3章二元关系第3章二元关系第3章 二元关系定理3.37设R是集合A上的二元关系,那么证证明分两部分(1)(基础)从定义3.32第(ii)条,立即得到Rt(R)(2) (归纳)假设Rnt(R),n1.设a,bRn+1.因为Rn+1=RnR,存在cA,使a,cRn和c,bR.根据归纳前提和基础步骤,a,ct(R)和c,bt(R).因为t(R)是传递的,得a,bt(R).这证明了Rn+1t(R).嘲磐蜜黔役捡犁灸今败察瑞糕检誓烘丑年茫棵叁坏缎淤汕凤趁踊漆弘茧孪第3章二元关系第3章二元关系第3章 二元关系例2(a)整数集合I上的关系的自反闭包是,对称闭包是关系,传递闭包是关系自身(b)整数集合I上的关
38、系的自反闭包是自身,对称闭包是全域关系,传递闭包是自身(c)E的自反闭包,对称闭包和传递闭包都是E(d)的自反闭包是全域关系,对称闭包是,的传递闭包是全域关系(e)空关系的自反闭包是相等关系,对称闭包和传递闭包是自身(f)设R是I上的关系,xRy当且仅当y=x+1,那么t(R)是关系阶斡棺涌罗唉呐算秀豆肥输锥胳钨差烹易土茎尿旧撅尾滓鬃却荐豫讫京乞第3章二元关系第3章二元关系第3章 二元关系定理3.38设R是集合A上的二元关系,这里A有n个元素,那么证设x,yt(R),于是必存在最小的正整数k,使x,yRk.现证明kn.若不然,存在A的元素序列x=a0,a1,a2,ak-1,ak=y使 xRa1
39、,a1Ra2,ak-1Ry.因 kn,a0,a1,ak中必有相同者,不妨设ai=aj,0ijk.于是xRa1,a1Ra2,ai-1Rai,ajRaj+1,ak-1Ry成立.即x,yRs,这里s=k-(j-i).但这与k是最小的假设矛盾,于是kn,又x,y是任意的,故定理得证遣匿墨资江涂车井茫写墒缚名枢掀嗜幌驯讥鼠切幌慢锈饲昧宦汞撞乖录所第3章二元关系第3章二元关系第3章 二元关系例3设A=a,b,c,d,R如图3.31(a)所示,则t(R)=RR2R3R4,如图3.31(b)所示.(本例即是3.2节例2.)定理3.39(a)如果R是自反的,那么s(R)和t(R)都是自反的(b)如果R是对称的,
40、那么r(R)和t(R)都是对称的(c)如果R是传递的,那么r(R)是传递的驴弊勘焉均涩躲倚碟茁涌爹横番蝎阑辛碑址家千卓太坠藉佬冀杯珐姐奏雀第3章二元关系第3章二元关系第3章 二元关系图3.31穆碱虽捧商蓄诫府索烯琐盅减镇在膨骆忻斜勤费荫牡掀也唉昭炮侩年相祝第3章二元关系第3章二元关系第3章 二元关系定理3.310设R是集合A上的二元关系,那么(a)rs(R)=sr(R)(b)rt(R)=tr(R)(c)ts(R)st(R)证赠举逐窖奖圆搏癌丛板俏争反祝薯研棚罩巡立倚顽让苹仙硕使辽吧黎医已第3章二元关系第3章二元关系第3章 二元关系(b)注意到ER=RE=R和对一切nN,En=E,可得于是(c)
41、不难证明如果R1R2,那么s(R1)s(R2)和t(R1)t(R2).现相继地应用这一结论于对称闭包的性质:s(R)R.得ts(R)t(R)和sts(R)st(R)角傻妒滚待要尾筋殊苟蒂押佬迫梧墩傻莱塘蠢疯瘁坷暑迟窗曹垮颇羞宇凳第3章二元关系第3章二元关系第3章 二元关系3.4 次序关系次序关系 3.4.1偏序集合定义3.41如果集合A上的二元关系R是自反的,反对称的和传递的,那么称R为A上的偏序,称序偶A,R为偏序集合.丫略萎淳泅泵卯缨焰桨讫谩厌攘潘谅揉舀蝇铲秒钱恰谷面挟谬茵兴台蔫袭第3章二元关系第3章二元关系第3章 二元关系如果R是偏序,A,R常记为A,是偏序符号,由于难以书写,通常写作,
42、读做“小于或等于”,因为“小于或等于”也是一种偏序,故不会产生混乱.R是偏序时,aRb就记成ab.如果R是集合A上的偏序,则也是A上的偏序;如果用表示,可用表示R.A,和A,都是偏序集合,并互为对偶.箩雾混蜂似书懒里脸译山逸小荷傈梨笆琐荷滇奴漏吉撂斌煽札寞蝎凹砰讳第3章二元关系第3章二元关系第3章 二元关系例1(a)I,是偏序集合,这里表示整数中的“小于或等于”关系(b)(A),是偏序集合,这里是集合间的包含关系(c)A=2,4,6,8,D代表整除关系,M代表整倍数关系,则D=2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,8M=2,2,4,4,6,6,8,8,4,2,6,2,8,
43、2,8,4A,D,A,M都是偏序集合,且互为对偶左嘻恃恰脖寡议姐祈坑僵眩砸抄琉蛾绣茨轿涎惠哄威激辖湾捐眶充碑朗频第3章二元关系第3章二元关系第3章 二元关系图3.41巴态竖晶绑贯蝎圾攻经瓷捆蕉卉赁绸播毯徊匡者涛拟昌莲悦呈簇厕仙叔嚷第3章二元关系第3章二元关系第3章 二元关系例2(a)P=1,2,3,4,P,的哈斯图为图3.42(b)A=2,3,6,12,24,36, A,整 除 的 哈 斯 图 为 图3.43(c)A=1,2,12,A,整除的哈斯图为图3.44图3.42图3.43吓汝愧丧市肥跳泡督咐湾污斋杠历范甭谁郴乔买俗哼蝇喘毫幕去取鸭小射第3章二元关系第3章二元关系第3章 二元关系图3.4
44、4晋烂骨乞屉因辈竞供藕孙髓娃抹良忍裹壕貉逾破慑梨吧芍蹭妹毕狠勺酉辽第3章二元关系第3章二元关系第3章 二元关系定义3.42设A,是一偏序集合,B是A的子集(a)元素bB是B的最大元素,如果对每一元素xB,xb(b)元素bB是B的最小元素,如果对每一元素xB,bx例3考虑在偏序“整除”下整数1到6的集合,其哈斯图为图3.45(a)如果B=1,2,3,6,那么1是B的最小元素,6是B的最大元素(b)如果B=2,3,因为2和3互相不能整除,那么B没有最小元素和最大元素(c)如果B=4,那么4是B的最大元素,也是B的最小元素菲搔榨板奉毯更浸扫馏刽醉砧糙泳效殖泞代馁瓶泡书患架疹舱方狸当啄羊第3章二元关系
45、第3章二元关系第3章 二元关系图3.45避弧量俞穷荐玖腐妈挤君叭岸瓤锌券棉龋禄尹凸狗购支屈潭迟盲润俺讨腋第3章二元关系第3章二元关系第3章 二元关系定理3.41设A,是一偏序集合且BA,如果B有最大(最小)元素,那么它是唯一的证假设a和b都是B的最大元素,那么ab和ba.从的反对称性得到a=b.当a和b都是B的最小元素时,证明是类似的定义3.43设A,是一偏序集合,B是A的子集(a)如果bB,且B中不存在元素x,使bx且bx,那么元素bB叫做B的极大元素.(b)如果bB,且B中不存在元素x,使bx且xb,那么元素bB叫做B的极小元素赴菱瘫瞬岳毛烷峰辉宛饶掺蹲镭贿罕魁哀迅角灰界茨拣撕员校绅吃怒为
46、苑第3章二元关系第3章二元关系第3章 二元关系定义3.44设A,是一偏序集合,B是A的子集(a)如果对每一bB,ba,那么元素aA叫做B的上界;如果对每一bB,ab,那么元素aA叫做B的下界.(b)如果a是一上界并且对每一B的上界a有aa,那么元素aA叫做B的最小上界,记为lub;如果a是一下界并且对每一B的下界a有aa,那么元素aA叫做B的最大下界,记为glb.簿顽维樱妨屁笨详徽印惟久桨纸檀刹嫂岁试匙矿姿抡嘘舞掖铬谬置磊敦箭第3章二元关系第3章二元关系第3章 二元关系例4(a)考虑偏序集合1,1,1,0,0,1,0,0,这里按a,bc,dacbd规定,其哈斯图如图3.46如果B=1,0,那么
47、1,0是B的最小和最大元素,也是B的极大和极小元素.B的上界是1,0和1,1,1,0是最小上界.B的下界是0,0和1,0,1,0是最大下界.棠蔓绳靛镁审大与静霹旧租肉鸦低岭掐烯答甸森挑黑舀纶果材珊垮均讹恰第3章二元关系第3章二元关系第3章 二元关系(b)考虑偏序集合I,设B=2iiN,那么B既没有最大元素和极大元素,也没有上界和最小上界.B的最小元素和极小元素是0,B的下界集合是iiIi0,0是最大下界.(c)考虑在偏序集合2,5,6,10,15,30,整除,其哈斯图如图3.47设B是全集合2,5,6,10,15,30,那么2和5都是B的极小元素,但B没有最小元素.集合B没有下界,所以没有最大
48、下界.元素30是B的最大元素,极大元素,上界,最小上界.语棘挫搜查级泰漫宴杏柑筒拘四貌褥配笆绘综枣曰睬平郝辞挨先抄钨淳榜第3章二元关系第3章二元关系第3章 二元关系图3.46缎塔常泰席任铺代张串巢闲兆桨茁期胎粗椭阜剩沈澜臆办输敷淆捅残擞雌第3章二元关系第3章二元关系第3章 二元关系图3.47取涡接姑扼氓砌驰啼蛋田鲤涵言匿偏苑呵琶晃腔啪垮令呈消岿书趋沟锑宜第3章二元关系第3章二元关系第3章 二元关系定理3.42如果A,是非空有限的偏序集合,则A的极小(大)元素常存在最大下界和最小上界也可能存在或不存在,但如果它们存在,则是唯一的.定理3.43设A,是偏序集合且BA,如果B的最小上界(最大下界)存
49、在,那么是唯一的.寄稻蛇沉赁鞘华掠挞娄肇帖莆雄郸硝廓住谦渡臼沛痉孟骡尼胳腻时伟姨该第3章二元关系第3章二元关系第3章 二元关系下述定理描述了存在于诸特异元素之间的某些关系定理3.44设A,是偏序集合,B是A的子集(a)如果b是B的最大元素,那么b是B的极大元素(b)如果b是B的最大元素,那么b是B的lub(c)如果b是B的一个上界且bB,那么b是B的最大元素证明可由最大元素,极大元素和lub的定义直接得出,故略去.另外,读者不难给出表达最小元素,极小元素和glb间关系的定理逾安刺肇眩涛颤瓤捉渡农僳呛角劲契拱疫妇魁西巡常殊粕队魂嘘捌秋涤癸第3章二元关系第3章二元关系第3章 二元关系3.4.2拟序
50、集合定义3.45如果集合A上的二元关系R是传递的和反自反的,那么R叫做A上的拟序.A,R称为拟序集合.常借用符号表示拟序拟序是反对称的,虽然定义中没有明确指出,但容易证明这一点.因为如果xRy和yRx,由R的传递性得xRx,但这与R的反自反性矛盾,所以xRyyRx常假,于是 xRyyRxx=y常真,即R是反对称的.蚂乎代脆圆售合耪溶养绚人涧深讨业恕图舞勤枷泉创乓谣感司灼讽皮蓟致第3章二元关系第3章二元关系第3章 二元关系例5(a)实数集合中的是拟序关系(b)集合族中的真包含是拟序关系拟序集合和偏序集合是紧密相关的,唯一区别是相等关系E.下述定理将说明这一点定理3.45在集合A上,(a)如果R是
51、一拟序,那么r(R)=RE是偏序(b)如果R是一偏序,那么R-E是一拟序剿崭味橡倍攘姥江努诌铰拍熬贷刚讥殴无夯诬耗绿梯总氯帽冀包栽顾殿上第3章二元关系第3章二元关系第3章 二元关系3.4.3线序集合和良序集合如果是一偏序,或ab或ba,我们说a和b是可比较的.偏序集合中的元素不一定都可比较,所以叫“偏”序.下面介绍的都是可比较的情况.定义3.46在偏序集合A,中.如果每一a,bA,或者ab,或者ba.那么叫做A上的线序(或全序),这时的序偶A,叫做线序集合或链.哉邪吾夜揪利应拭际藐箔潭闺弯本氖望飘酗噪贫小婴绸芋滇今陵奄喳窄袱第3章二元关系第3章二元关系第3章 二元关系例6(a)P=,a,a,b
52、,a,b,c,P,是线序集合,其哈斯图如图3.48所示(b)I,是线序集合,其哈斯图(不完全)如图3.49所示(c)设S是区间套的集合0,a)aR+,则S,是线序集合(d)1,2,3,6,整除不是线序集合;如果A是多于一个元素的集合,那崐么(A),不是线序集合.宣锅囊盼赔割间酱腆寻奉呆砰嫉扎焉瓣辐携铰捷盾少卢恒骇沪引伊挎缚谱第3章二元关系第3章二元关系第3章 二元关系图3.48图3.49译幸钠空盼延释郭槐执碎蝶缘蔡钨怠沧橡嚣闰坚澎妇寂乘沥久萤蜀冉进绪第3章二元关系第3章二元关系第3章 二元关系定义3.47如果A上的二元关系R是一线序,且A的每一非空子集都有一最小元素,那么R叫做A上的良序,序偶
53、A,R叫做良序集合定理3.46N,是良序集合证我们必须证明N的每一非空子集S,在关系之下,都有一最小元素.因为S非空,所以在S中可以取一个数n,显然,S中所有不大于n的数形成非空集TS.如果T有最小数,那么这最小数就是S中的最小数,但从0到n只有n+1个自然数,于是T中所含的数最多是n+1个,所以T有最小数.因此定理成立.撅篓似堵譬印估唾俞窘丢摄提辐骄排盂履曳蒜缉禄抿铱础垒菩胃歌俊付肮第3章二元关系第3章二元关系第3章 二元关系例7(a)每一有限线序集合是良序的(b)线序集合I,不是良序集合,因为I的某些子集(诸如I自身)不包含最小元素(c)关系是实数R的线序,但不是良序.例如子集A=(0,1
54、无最小元素.如果A中的a是最小元素,那么也在A中,而a且不相等.这与假设a是线序关系下A的最小元素矛盾判第勇娃纵爪闪癸疡欣怎涯掖藩裔篓炒忘头络虹审你锐脑堵泪据淑梧份暇第3章二元关系第3章二元关系第3章 二元关系3.4.4词典序和标准序由已知的线序和良序集合可以诱导出新集合S上的线序和良序.常见的有以下几种方法(1)首先,使集合S上的每个元素与集合N(也可选其它已知的良序或线序集合)的唯一不同的元素对应,然后应用N上的良序定义S上的良序R定义方法如下:如 果 a,bS,且 a对 应 于 n1,b对 应 于 n2,那 么 aRbn1n2各灼裙池捆钞胡爷强蔷墨势要件瞄期掷守坛汉伦致却夸亿瞅参烯鹤菩知
55、窜第3章二元关系第3章二元关系第3章 二元关系(2)应用N上的良序定义出Nn上的良序例如n=2时,N2上的次序关系可如下定义:a,bc,dac(a=cbd)N2,是良序集合.关系“严格小于”可如下定义:a,bc,da,bc,da,bc,d类似地,应用I上的线序能定义出线序集合In,(3)应用字母表上的线序,可定义出上的通常叫词典序的线序.猛辐患僚簿银督陷特大算磐咆江社悸驴噎八霖枫翔神争削厦椎臻浙库旨慰第3章二元关系第3章二元关系第3章 二元关系定义3.48设是一有限字母表,指定了字母表序(线序).如果x,y,(a)x是y的词头,或(b)x=zu和y=zv,这里z*是x和y的最长公共词头,且在字
56、母表序中u的第一个字符前于v的第一个字符,那么xy.叫做词典序(4)由于N,和有限线序集合都是良序集合,可应用它们定义出上的一个良序,通常叫标准序淄吗赁晒队她躁亦逝戒柱扛开妇叉婶胀维咯沫灰甘披爷毅敝栅睛吹吕戮非第3章二元关系第3章二元关系第3章 二元关系定义3.49设是一有限字母表,指定了字母表序,x表示x的长度,如果x,y*,(a)xy,或.(b)x=y且在的词典序中x前于y.那么xy,叫做标准序.造笔板蛔哟郎跳倘攻谅抬睁淬安缺它届沛郧淡撂随萨讲磨称茵田噎骄泰肘第3章二元关系第3章二元关系第3章 二元关系不论在词典序和标准序下,的每一元素都有直接后继者.设=a,b,c且abc,x*.在标准序
57、下xa和xb的直接后继者分别是xb和xc,xc的直接后继者是ya,这里y是x的直接后继者.在词典序下x的直接后继者是xa在标准序下 xb和xc的直接前趋分别是xa和xb,xa的直接前趋是yc,这里y是x的直接前趋.在词典序下xa的直接前趋是x,非a结尾的串都无直接前趋,例如b,ab,aab,但有无限个前趋乃戴奎妙跃苑看徊绢俗郴次炽与愁懒宁赴星弦殴迷胀螺询挣滥确桔厌炽唯第3章二元关系第3章二元关系第3章 二元关系3.4.5数学归纳法的推广前章我们把数学归纳法第一,第二原理看作是自然数域上的一个推理规则,本小节我们把它推广到一般的良序集合对任一个自然数n,我们先取0,如果n0,取0的后继者1,如果
58、n1,再取1的后继者2,如此进行下去,最终会得出n.给定一个良序集合,如果对它的任一元素x,我们先取该集合的最小元素m0,如果xm0,取m0的后继者m1,如果xm1,再取m1的后继者m2,如此以往,最终会得出x,那么就称这样的良序集合是“像自然数”的.灾团撰钧悲鳖险欺憾征友窄魁谐谦琉那陕艇叔淆庸诫岭泊莉物放韶阿话诀第3章二元关系第3章二元关系第3章 二元关系例8(a)设=a,b,良序集合*,标准序是像自然数的.因为定长的串的个数有限,给定任一个串x,在x之前的串的个数有限,所以从开始,反复取后继者,终可得出x.(b)良序集合NN,不像自然数,这里按上一小节规定.因为有许多元素没有直接前趋,例如
59、5,0就是这样,因而有无限个元素前于5,0,所以,从0,0开始,反复地取后继者,不可能取得5,0.滩寄源映堑吊舌县扭的酥赤腹坍草鳞塞暖搂玉级辉思嘻锨霉炳汞窜遁面跌第3章二元关系第3章二元关系第3章 二元关系像自然数的良序集合,可以应用数学归纳法第一原理.因为第一原理是建立在后继运算上,而这种良序集合的每一元素都可通过重复地取后继者得到,设m0是该良序集合S,的最小元素,S(x)是元素x的后继者,则推理规则如下:这样,如果我们能证明m0有性质P,和当x有性质P时,则S(x)有同样性质,那么我们能得出S的每一元素有性质P.涎秽递赐岛蔡灰左溺捷侗芹湍憋臃局陈尾专携弧磋砧易矢垫肯乌锗砧然砌第3章二元关
60、系第3章二元关系第3章 二元关系对不像自然数的良序集合,不能应用数学归纳法第一原理,因为这种良序集合的有些元素不能由后继运算得到.但对它可应用数学归纳法第二原理.第二原理是建立在良序集合上的,适用于一切良序集合.设S,是良序集合,表示-E(即xy表示xy且xy),则推理规则如下:韵绝戊匀詹桨岔它奶忿耻顿钳箍郸脾脸沂岿旭煎写蒂努作巩橱谢奸节瀑惑第3章二元关系第3章二元关系第3章 二元关系这样,若每一小于x的元素有性质P,如果我们能证明任意元素x有性质P,那么我们能得出S的每一元素有性质P.下面证明良序集合上这个推理规则是有效的假设我们能证明前提衫万指浦煽矫宣慢痊奖星匝孔窜却间馒旗余舵苦拈撬侣悸浊
61、邯捕赖媚爹稚第3章二元关系第3章二元关系第3章 二元关系并假设T是S的子集,由S中没有性质P的所有元素组成.因为S是良序的,如果T,那么T必有最小元素m;这得出对所有xm,P(x)是真.可是,前提断言如果对所有xm,P(x)是真,那么P(m)是真,导致矛盾,我们得出T必须是空.因此,第二原理结论xP(x)是真,这得出对任意良序集合S,数学归纳法第二原理是有效的推理规则.壁怎哭殆仲苇援憎甸几阁亮伊窟冯人抬忘耪洲攻锣进胶恢孤茹腐吨饱核伟第3章二元关系第3章二元关系第3章 二元关系例9Q+,是线序集合.现说明在此线序集合中第二原理不是有效推理规则设谓词P(x)表示“x小于或等于5”.(i)当x5时,
62、yyxP(y)是真,P(x)也真.所以(ii)当x5时,由于x5,所以存在有理数y0,使5y0x.这样P(y0)是假,因而捉里砾恐羞氨篱傍矮聚欧选邑悬碰侩痪刷男伊丰弃摔推譬悲抄如们猪灯滨第3章二元关系第3章二元关系第3章 二元关系是真综合(i)和(ii),得:在论述域Q+上,xy(yxP(y)P(x)是真,但结论xP(x)是假.这说明第二原理不能应用于线序集合Q+,是假,所以欢萤楚佬耿硫唆柬哑朗叶摊锁弄纽鸽赊释掇颊视鸳嚏操疮宙字饱腻堪驴撞第3章二元关系第3章二元关系第3章 二元关系3.5 等价关系和划分等价关系和划分 3.5.1等价关系二元关系的另一重要类型是等价关系,其定义如下:定义3.51
63、如果集合A上的二元关系R是自反的,对称的和传递的,那么称R是等价关系设R是A上的等价关系,a,b,c是A的任意元素.如果aRb(即a,bR),通常我们记作ab,读做“a等价于b”.休袱革什瞅卫架六银琢程啸熔稚寒沉配害泞亢藐色砚腕凰灰节戳寻霖佣怔第3章二元关系第3章二元关系第3章 二元关系定义3.52设k是一正整数而a,bI.如果对某整数m,a-b=mk,那么a和b是模k等价,写成ab(modk)整数k叫做等价的模数定理3.51模k等价是任何集合AI上的等价关系证如果A=,例1(c)已指出它是等价关系.如果A,则(i)自反的.因为对任一a,a-a=0k,得出aa(modk)哦悟囚辽恬愿坠备渺氢周
64、沫舶幕堵液旭芳博像晋兆走肩焕碉隶婿梯腥井毫第3章二元关系第3章二元关系第3章 二元关系(1)因为R具有自反性,所以A上每一元素都和自己等价.反映到R的有向图上,每一结点都有一自回路.(2)因为R具有对称性,所以如果a等价于b,则b也等价于a,反映在有向图上,如果有从a到b的弧,那么也有从b到a的弧.(3)因为R具有传递性,所以如果a等价于b,b等价于c,则a等价于c.反映在有向图上,如果从a到c有一条路径,则从a到c有一条弧.锨腺颗鲤其医锈各缨淀颜谤撒姑请亢意饺袁聂彼鬃挽女招隧倡吹筐姿顶鸿第3章二元关系第3章二元关系第3章 二元关系例1(a)同学集合A=a,b,c,d,e,f,g,A中的关系R
65、是“住在同一房间”.这是等价关系,因为(i)任一个人和自己同住一间,具有自反性.(ii)若甲和乙同住一间,则乙和甲也同住一间,具有对称性.(iii)若甲和乙同住一间,乙和丙同住一间,则甲和丙也同住一间,具有传递性现假设a和b同住一间,d,e,f同住一间,c住一间.则R=a,a,a,b,b,a,b,b,c,c,d,d,e,e,f,f,d,e,e,d,e,f,f,e,d,f,f,d假连眷伴乒纹瞧缝咯扩匙锋乾唉担威返划厩袭明诡戒绳什厂缺舒楞哦销稍第3章二元关系第3章二元关系第3章 二元关系其有向图如图3.51所示(b)数中的相等关系,集合中的相等关系,命题演算中的关系等都是等价关系(c)空集合中的二
66、元关系R是等价关系,因为(i)x(xxRx)(ii)x yxyxRyyRx(iii)x y zxyzxRyyRzxRz拈嘎处咙己前矫矿茫砾者劲耪娃以驹烩甲幕淤铜瘟切骏歼舞陪锐坎性疥寸第3章二元关系第3章二元关系第3章 二元关系图3.51预愚岔敬奠冯樱沥夺酱馅罢彩防铝蝴雹猎孺滋荚慑念帜烷枯刘只笨芹嗓完第3章二元关系第3章二元关系第3章 二元关系(ii)对 称 的 .因 为 ab(modk)时 ,存 在 某 mI,使 a-b=mk,于是b-a=-mk,因此ba(modk)(iii)传递的.设ab(modk)和bc(modk),那么存在m1,m2I,使a-b=m1k和b-c=m2k,将两等式两边相加
67、,得a-c=(m1+m2)k,所以ac(modk)拜镰崇放板舰所得诣组涪需奔乔荒贸素橇喊视佃唁穗搁纳期端谍朽畴逢耻第3章二元关系第3章二元关系第3章 二元关系例2(a)若R是I上模4等价关系,则04=-8,-4,0,4,8,14=-7,-3,1,5,9,24=-6,-2,2,6,10,34=-5,-1,3,7,11,汞姜倦粹程怂藩哺察择畜狈仑咆臭韭食掠卢楞津拟吾袖瑞棠臃心穿设盒却第3章二元关系第3章二元关系第3章 二元关系(b)若R是I上模2等价关系,则02=-4,-2,0,2,4,12=-3,-1,1,3,5,每一集合中的数相互等价(c)时钟是按模12方式记数的设备,13点钟和1点钟有相同的
68、记数.淳淆梢销砍披玖麻享椎饵蒙开滥棉马菇翘禹敞茶纵甜伴沈浊哪杯崖怯辞缅第3章二元关系第3章二元关系第3章 二元关系定义3.53设R是集合A上等价关系,对每一aA,a关于R的等价类是集合xxRa,记为aR,简记为a;称a为等价类a的表示元素.如果等价类个数有限,则R的不同等价类的个数叫做R的秩;否则秩是无限的对每一aA,等价类aR非空,因为aaR.豌胎巍狱亡肚阻逃侈挖刷或禾捎冈洲缓政蝶败住腾港叮搔滤黍蹭鲤辖坷纬第3章二元关系第3章二元关系第3章 二元关系例3(a)如图3.52,设A=a,b,c,d,e,f,R=a,a,b,b,c,c,a,b,b,a,a,c,c,a,b,c,c,b,d,d,e,e
69、,d,e,e,d,f,f,则等价关系R的等价类如下:a=b=c=a,b,cd=e=d,ef=f.等价关系R的秩是3昭点义楷色舌坚瘦假辕骋着傅羌蜂狠剐梳檬鄂世性鼓冷翻祖邻橙配幂但征第3章二元关系第3章二元关系第3章 二元关系图3.52黑犬旅邮赚庞昌账炎娜困静肪嚣惦合全取嫡刘遍头更必钓墙舌映股之躯即第3章二元关系第3章二元关系第3章 二元关系(b)I上模4等价的等价类是04,14,24,34(参看例2(a),I上模2等价的等价类是02,12(参看例2(b)(c)集合A上相等关系的秩等于A的元素个数.定理3.52设R是非空集合A上的等价关系,aRb当且仅当a=b证充分性.因为aa=b,即ab,所以,
70、aRb.引另包厄痢描躺佛序触屯杠栏堕忠握眶烁肇痰赚救蠢酞泡押磅放雾篱心增第3章二元关系第3章二元关系第3章 二元关系定理3.53设R是集合A上的等价关系,则对所有a,bA,或者a=b,或者ab=证 如 果 A=,断 言 无 义 地 真 ,现 设 A .若ab,则存在某元素ca和cb.根据定理3.52得a=c=b.又因a和b都非空,ab=和a=b不能兼得.因而定理得证郭卷网缘扼操挫魔纽咕讼畔私铆辐蕾甘恫拄沮唾喘沿蝴豢硅地哥矿词陵狈第3章二元关系第3章二元关系第3章 二元关系定义3.54给定非空集合A和非空集合族=A1,A2,Am,如果,那么称集合族是A的覆盖.定理3.54设R是集合A上的等价关系
71、,则绿苦煽崔疼签咳湿币羊梯论谷烯析尔求誓肛近钢惨艾军涪厉瞻蓬扮链牛雨第3章二元关系第3章二元关系第3章 二元关系定理3.55设R1和R2是集合A上的等价关系,那么R1=R2当且仅当aR1aA=aR2aA证必要性.因为R1=R2,所以对任意aA,有aR1=xxR1a=xxR2a=aR2故aR1aA=aR2aA充分性.因为aR1aA=aR2aA,得aR1=aR2,所以,对任意xA,有xR1axaR1xaR2xR2a又a是任意的,故R1=R2.证毕论男渭邮否森区全鳖溢姆扒斤咎冬敛撕才闰给迭桐钠龚悼躲董坏泉恩陨户第3章二元关系第3章二元关系第3章 二元关系定理3.56设R是A上的二元关系,设R=tsr
72、(R)是R的自反对称传递闭包,那么(a)R是A上的等价关系,叫做R诱导的等价关系(b)如果R是一等价关系且RR,那么RR.就是说,R是包含R的最小等价关系.捞辆业牟腮梢镊愈然硷皱闭嘴舷思扳诉师征各悬吹溺酸傅架此翅吏健立镁第3章二元关系第3章二元关系第3章 二元关系证(a)根据闭包运算的定义和定理3.39可得r(R)是自反的,sr(R)是自反的和对称的,tsr(R)是自反的,对称的和传递的.因此,R=tsr(R)是A上的等价关系(b)设R是任意的包含R的等价关系,那么R是自反的和对称的,所以RRE=sr(R).因为R是传递的且包含sr(R),所以R包含tsr(R).证毕征疡桂搬睬剥深卜丢晃茁欠讫
73、搔谴渺藐蛔责撩港柒联操雪依烃秸劫缓根瘩第3章二元关系第3章二元关系第3章 二元关系例4设A=a,b,c且A上的二元关系R如图3.53所示,则tsr(R)如图3.54所示.图3.53图3.54缘酿磐季束郝絮兴裕赶井澄龄壕虐豆匿系嵌裁卧岁妄紊巷静唾年耽款浮蜗第3章二元关系第3章二元关系第3章 二元关系3.5.2划分定义3.55给定非空集合A和非空集合族=A1,A2,Am,如果(i)是A的覆盖,即(ii)AiAj=或Ai=Aj(i,j=1,2,m)那么集合族叫做集合A的一个划分划分的元素Ai称为划分的块,如果划分是有限集合,则不同块的个数叫划分的秩.若划分是无限集合,则它的秩是无限的.划分的秩就是划
74、分的大小.稀雪簇意逐挽录嗡诸你宣坯羹沧讯佃喜颁多即综阁逾拣葫移忙薯脉蝇暮益第3章二元关系第3章二元关系第3章 二元关系例5(a)设S=1,2,3A=1,2,2,3B=1,1,2,1,3C=1,2,3D=1,2,3E=1,2,3F=1,1,2帖盎互换木摊娃毖硕剪剧轰牟垢喜算衔扶摔拼少颖窖岔颐良铸窥私为啸每第3章二元关系第3章二元关系第3章 二元关系则C,D,E都是S的划分,它们的秩分别是2,1,3,A,B是S的覆盖但不是划分,F不是S的覆盖也不是S的划分(b)将一张纸撕成几片,则所得的各个碎片是该纸的一个划分(参看图3.55).=A1,A2,A3,A4是A的划分,秩是4.(c)集合族x,-x|x
75、I 是I的秩无限的一个划分(d)设A是非空集合,那么(A)-是非空集合族,这个集合族是A的一个覆盖,而不是A的划分,除非A是单元素集合.散竞矛演诗硅要傀瓷臼闻雾炊改惶蕾凑趴峨界烹娠哇池澡琢摔品涸豆犹敬第3章二元关系第3章二元关系第3章 二元关系图3.55梯山僻芽篡喳西参弟卵盲渊准操骚咬廊氮珠别赞害蒂铝冕春醉踢讨几案耍第3章二元关系第3章二元关系第3章 二元关系定理3.57设A是非空集合,R是A上的等价关系.R的等价类集合aRaA是A的划分定义3.56设R是非空集合A上的等价关系,称划分aRaA为商集A/R,也叫A模R由商集的定义和定理3.55立即可得:定理3.58设R1和R2是非空集合A上的等
76、价关系,那么R1=R2当且仅当A/R1=A/R2勿帕宵哪芹秋务掌唁代肿痴送厩玛堰址患爆蒲跺拭呼域撒阑电膊牺式仟皂第3章二元关系第3章二元关系第3章 二元关系定理3.59设是非空集合A的一个划分,则A上的二元关系:是A上的等价关系.哮佑妻俱顿戏糟混切显菊糯丢摩鹿鸳旭抢奥稽沏狄诛害损泰济碌苦咎到辊第3章二元关系第3章二元关系第3章 二元关系证(a)R是自反的.因为A的每一元素是在的某块B中,所以,对每一aA,aRa(b)R是对称的.假设aRb,那么有某块B,使aB和bB.所以bRa(c) R是传递的.假设aRb和bRc,那么存在B1和B2,使a,bB1和b,cB2,即bB1B2,由划分的定义,要么
77、B1B2=,要么B1=B2,所以B1=B2.因此,cB1,aRc虽捆代隙疙综馈沽烟拒蓬褪滥绽钻压路迅赖宙毕倚倦吓立蛇召掘铸舒疤古第3章二元关系第3章二元关系第3章 二元关系定理3.510设是非空集合A上的划分,R是A上的等价关系,那么,诱导出R当且仅当R诱导出证必要性.假设诱导出R,R诱导出设a是A的任一元素,并设B和B分别是和的块,使aB和B.那么对任一bbBaRbR的定义aR=bR定理3.52bBbbR=aR=B宙凡洱折内扦址糙钦渣繁简尹蝗频妥何跑融甘尝犊翱藻预端乒缝谰汲萄布第3章二元关系第3章二元关系第3章 二元关系所以,B=B.因为a是A的任一元素而和都是A的覆盖,故=.充分性.假设R
78、诱导出,诱导出等价关系R.那么对任意a,bA aRbaR=b R定理3.52a,baRbbR=aR和aaRB(BaBbB)上一行的改述 aRbR的定义因此,R=R.证毕.印贤躺做酵颖褒以舱难埠炳诲附弧椭竹痢派拔背川劲鲜麻诞坝冠祖伏糕世第3章二元关系第3章二元关系第3章 二元关系例6设A=a,b,c,d,e,R=a,a,a,b,a,c,b,b,b,a,b,c,c,c,c,a,c,b,d,d,d,e,e,e,e,d,其有向图如图3.56所示,则R诱导的划分=a,b,c,d,e.反之,若A的划分=a,b,c,d,e,则所诱导的等价关系R=a,b,ca,b,cd,ed,e=a,a,a,b,a,c,b,
79、b,b,a,b,c,c,c,c,a,c,b,d,d,d,e,e,e,e,d途赴篷踪牛买耳裙珠岩邑粕蕊遍攻毫砰溅汹再涡赛材粒而彼旬庐碗赔讯肯第3章二元关系第3章二元关系第3章 二元关系图3.56维狡日吕腋蚊渍痉傀染办哪即饥渤卧传根饱镭箩琴开动澜碱权名鳃称故哼第3章二元关系第3章二元关系第3章 二元关系3.5.3划分的积与和定义3.57设和是非空集合A上的划分.如果的每一块都包含于的一块中,那么说细分,或说是的细分.如果细分,且,那么说是的真细分例7(a)设A=a,b,c,=a,b,c,=a,b,c,则细分(b)把一张纸A撕碎得A的划分,再撕碎,就是将细分,所得之仍是A的划分(参看图3.57)鲁后
80、可嘎牵芽铬壮帛氰御眨筛绩症剑厉挡鸦晓代关巩弯煮僵研我旱弓船空第3章二元关系第3章二元关系第3章 二元关系(c)I上模4等价诱导出的划分04,14,24,34细分模2等价诱导出的划分02,12.因为04和24两者包含于02中,14和34两者包含于12中.隧约坞鹃抠戍寺衔秘揣矢扶顿折陛育漆陨顾职淖谭翌氧羚裳翱由绳蛋益玩第3章二元关系第3章二元关系第3章 二元关系图3.57锑俊撩攻声譬批部危芳奥锥型懈茧缄腰谋令搂呢应戊余枕匡派兔睡更掐婉第3章二元关系第3章二元关系第3章 二元关系定理3.511设和是非空集合A上的划分,并设R和R分别是由和诱导的等价关系.那么细分当且仅当RR证我们首先证明如果细分,那
81、么RR假设aRb,那么有的某块B使a,bB.因为细分,有的一块B使BB.所以a,bB.这得出aRb,因此RR .砷怪留御片先明隆乾枷刻骨汞没任男遥俐瓶工允喝删雨顺渴烁卤蓬交蕾缉第3章二元关系第3章二元关系第3章 二元关系其次证明如果RR,那么细分.设B是的一块,且aB,那么B=aR=xxRa.但对每一x,如果xRa,那么xRa,因为RR.所以xxRaxxRa,即aRaR,用B表示aR;那么B是的一块且BB,这证明了细分.苫铺猛梁踊弃胳西横热肠奄品铃做煽幢下稳淮维破诵租睬颁遵子蔓庸变击第3章二元关系第3章二元关系第3章 二元关系等价关系的大小,由该关系所含的序偶个数计算;划分的大小,由划分的秩计
82、算,本定理说明大的等价关系诱导出小的划分.大的划分诱导出小的等价关系,但这是在细分或RR的条件下才能成立,如无此条件,一般不成立定理3.512设F是非空集合A上划分的族,则关系细分是F上的偏序矢眩扒恶榔庶纳咋轰守睁嫉抖噪模伐衍蜕塌洼汞假梗并憋准贬宙在谊哪侥第3章二元关系第3章二元关系第3章 二元关系定义3.58设1和2是非空集合A的划分.1和2的积,表示为12是A的划分,它使(i)细分1和2两者(ii)如果细分1和2,那么细分本定义概括地说就是12是细分1和2的最小划分下述二定理表明二个划分的积常存在且是唯一的.定理3.513设R1和R2是非空集合A的划分1和2所诱导出的等价关系.那么R=R1
83、R2诱导出1和2的积的划分.港凋讼烤祝倦卿桩遏吾彬隘省魔锄雕轩扣映接锣健奖洞摄熔绒搅三羔准袱第3章二元关系第3章二元关系第3章 二元关系定理3.514设1和2是非空集合A的划分,则1和2的积是唯一的.证 假设和都是1和2的积划分,那么从定义3.58知和彼此细分,根据定理3.512,关系“细分”是反对称的,所以,=.例8假定一张纸画上红线和绿线,按红线剪开得划分1,按绿线剪开得划分2,那么按红线和绿线剪开产生积划分12(图3.58).酉综铰狐哦孤毗形医僚窖拱扦蚌综暖禄达赶一凛财俐雄跺厌绎棠喉步铰尊第3章二元关系第3章二元关系第3章 二元关系图3.58栓庸狱宦怜这琉拓古凸旭悔擎桥琳诈时塘吃筒廖逛英
84、杖餐阐儒差谢谁吏泽第3章二元关系第3章二元关系第3章 二元关系定义3.59设1和2是非空集合A的划分,1与2的和记为1+2,是一划分,它使(i)1和2细分(ii)如果是A的划分,使1和2细分,那么细分本定义概括地说就是1+2是1和2所细分的最大划分下述二定理表明二划分之和常存在且唯一.格焙灯冕烧辛日讨携见命螟呆蓬亿险泼茫综秽酌讥藻阜偏几弃扛开斗亦肖第3章二元关系第3章二元关系第3章 二元关系定理3.515设R1和R2是非空集合A上的划分1和2所诱导出的等价关系.定义关系R是R1R2的传递闭包.R=(R1R2)+=t(R1R2)那么,R是A上的等价关系,划分A/R是1和2的和.证R1R2是自反的
85、和对称的,因为并运算保持这些特性.所以根据定理3.56,R=t(R1R2)=tsr(R1R2)是包含R1和R2的最小的等价关系.细隙测钳逸砖噬澳式鸿挥鬃追审氓薪腔哼铸夫陌亏旨蛆畴窃昆头喊喉变薯第3章二元关系第3章二元关系第3章 二元关系定理3.516设1和2是非空集合A的划分,1和2的和是唯一的.例9假定一张纸上的红线表示划分1,绿线表示划分2,那么,按既是红线又是绿线的线剪开就产生和划分1+2(图3.59)嗅哪读类雌宫锭殊抒香潞右牛狸湍徐闹郴未捂觉痢雄巢恼盗怔皆晓询哲真第3章二元关系第3章二元关系第3章 二元关系图3.59撬蓉置运榨街阳迢盏罕雇以乖藐聚襄肘缆跋府赦荔乳迢葫稿鹃莫千救赢辰第3章二元关系第3章二元关系
