《第二二元关系》由会员分享,可在线阅读,更多相关《第二二元关系(57页珍藏版)》请在金锄头文库上搜索。
1、第二章 二元关系2-1 有序对与卡氏积2-2 二元关系2-3 关系矩阵和关系图2-4 关系的性质2-5 二元关系的幂运算2-6 关系的闭包2-7 等价关系和划分2-8 序关系晕隶汁棒旨则钎拜屁磊黄乃涸迪烤肿熄岗砚操孕相垛惦毅苏骄感筑紊孜眠第二二元关系第二二元关系1 Peking University2-1 有序对与卡氏积1. 有序对(序偶)的概念2. 卡氏(笛卡儿)积3. 笛卡儿积的性质准瞅砾攘撩楼韭锅针肃川袖卧似漾歉清押缝案躯胜惭怂搅切并明媚瞅捍奈第二二元关系第二二元关系2 Peking University1、序偶的概念定定义义2.12.1 称a,a,b为由元素a、b构成的有序对或序偶,记
2、作。其中a称为有序对的第一个元素,b称为第二个元素,且a,b可以相同。许多事物是成对出现的,而且这种成对出现的事物,具有一定的顺序。例如:上、下;左、右;34;平面上的坐标等。一般地说,由两个具有固定次序的客体组成,来表达两个客体之间的关系。注:有序对可以看作是具有两个元素的集合,与一般集合不同的是有序对具有确定的次序。烃课笛稍安帕发乐馒和洁奉岗贵胰返嚎俏脂皿盎硷腔适凡吉烙匹兄河昏俗第二二元关系第二二元关系3 Peking University定理定理2.1 =2.1 =,当且仅当,当且仅当a=c,b=da=c,b=d。引理引理1 x,a=x,b1 x,a=x,b,当且仅当,当且仅当a=ba=
3、b。引理引理2 2 设设A,BA,B是非空的集族,若是非空的集族,若A=B,A=B,则则(1)(1)A=A=B ; (2) B ; (2) A=A=B B推论推论 a a b b时,时, 缚托孟枕腊项义悠幸典牲亩橙踏针跳冶换膛纱撼逛壮裁坦椒讯透醒困硝役第二二元关系第二二元关系4 Peking University引理1的证明nx,a=x,bx,a=x,b当且仅当当且仅当 a=b a=b。证明:证明:a=b a=b x,a=x,b x,a=x,bx=ax=a, x,a=x,b, x,a=x,ba,a=a,ba,a=a,b a=a,b a=a,b b=a b=ax x a a, a, a x,a=
4、x,bx,a=x,b a=b a=b x,a=x,bx,a=x,b a=b a=b# #亥鲍写毡真弄炙标筐芒斯峦鹏降实鲁原播辱头粪务履膨征芋疙浮侵趋毅匿第二二元关系第二二元关系5 Peking University引理2的证明引理引理2 2 设设A,BA,B是非空的集族,若是非空的集族,若A=B,A=B,则则(1)(1)A=A=B ; (2) B ; (2) A=A=B B证明证明: (1) x,x x A A z(zz(z A A x x z)z)z(zz(z B B x x z)z)x x B B A A = = B B(2) (2) x,x A A z(zz(z A Ax x z)z)
5、z(zz(z B Bx x z)z)x x B B A A = = B B# #涣佛傀钝捶瑶泌隘咎荤阶知驭陇缝就顶谦丰鸣秃牺状柠粕魄羚库惊岳怒辆第二二元关系第二二元关系6 Peking University定理证明n=,当且仅当,当且仅当a=c,b=da=c,b=d。证明:证明:=a,a,b=c,c,da,a,b=c,c,da,a,b= a,a,b= c,c,dc,c,da,b=c,da,b=c,da,a,b=c,c,d a,a,b=c,c,d a,a,b= a,a,b= c,c,dc,c,da=c a=c a=c a=c(a,b=c,d)(a,b=c,d) (a=c) (a=c) b=d b
6、=d = = a=c,b=d a=c,b=d。 # #衣兴滨粥卓唉妖淬畔苗果比鼠通委累兴篡咖者卖扩屠遗状希殊蝉计席遏燥第二二元关系第二二元关系7 Peking University推论证明n 推论: ab 证明: (反证) =a=b,与ab矛盾. #箔挠拎上浮肠详她边仆宏啡福蔷执鼎艰啃漠拈渊制衫贱厢嫡猖祷炸角晨泞第二二元关系第二二元关系8 Peking University序偶的概念可序偶的概念可推广推广到三元组、四元组、到三元组、四元组、 n n元组元组: : 有序三元组有序三元组(ordered triple)(ordered triple)表示序偶表示序偶,z;,z; 有序四元组有序四元
7、组表示序偶表示序偶,w;,w; 有序有序n n元组元组x 表示序偶表示序偶x,x,xn n 嚼惭亚序邦涕瑞恢缆赦善刮意娠暂扰艾卷少仗皂判人蝇顺败与兵池石嘻彰第二二元关系第二二元关系9 Peking University定定义义2.22.2 一一个个有有序序n(nn(n2)2)元元组组是一个有序对,它的第一个元素为有序的(n-1)元组,第二个元素为an,记为。即,an = 定定理理2.22.2 = 当且仅当ai=bi, i=1,2, n. 有序n元组注注:n元组有严格的集合定义,但我们关注的是有序对及有序n元组的次序性,不过多讨论他们的集合表示。埋轴临巳峪律完贵玖洁撂窜隶虏终谅节涵号摘器锦谓模灰
8、淌瞥二慰蛊敌晾第二二元关系第二二元关系10 Peking University2、卡氏积(Cartesian product)n定义2.3 设A、B为集合,称由A中元素为第一个元素,B中元素为第二个元素的所有有序对组成的集合为A与B的卡氏积(笛卡儿积),记作A B,即A B=|x A y B 。 例1 设设A =a,b, B =1,2,3, 求求A B, B A。解:A B=,。 B A=,。 由此例可知,笛卡儿积不满足交换律。由此例可知,笛卡儿积不满足交换律。#裸识年革讳喻局甚隶丑碟固仓驯柿掂蔼兜撕跟砂腿创剿刮栋抑眯麓耳眨幅第二二元关系第二二元关系11 Peking University3、
9、笛卡儿积的性质设设A、B、C为任意集合,则笛卡儿积的运算有如下性质:为任意集合,则笛卡儿积的运算有如下性质:(1)A= ,A= (2)不不适适合合交交换换律律:A B B A(当当A B A B时)时)(3)不不适适合合结结合合律律:(A B) C A (B C)(当当A B C 时)时)(4)分配律分配律:A (B C)=(A B) (A C) (B C) A=(B A) (C A) A (B C)=(A B) (A C) (B C) A=(B A) (C A) 后四个式子按集合相等的概念可以证明。后四个式子按集合相等的概念可以证明。摧着咨飘井圆湿船精褥盼凝惫捻良聪甄舌聂善妥幅持占拘恐陡壁怠
10、垮骤帅第二二元关系第二二元关系12 Peking University笛卡儿积的性质例 证明(B C) A=(B A) (C A) 证证:在集合在集合(B C) A中任取中任取,那么,那么 (B C) A x (B C) y A (x B x C) y A x B y A x C y A (x B y A) (x C y A) (B A) (C A) (B A) (C A)(B C) A=(B A) (C A)。#(卡氏积图示)张鼓蚁纪祈幻批丝傲从灸脂康件宏恼重堵诚畔越吗棱久掏奠厦略阔宗肪鸽第二二元关系第二二元关系13 Peking University3、笛卡儿积的性质(续1)(5)若若C
11、,则则 A B (A C B C) (C A C B)证证: 证证, 任取任取 A C,有,有 A C x A y C x B y C B C因此,因此, A C B C。证证, 若若A= , 则则AB. 若若A ,C , A C B C, 取取y C ,则有,则有x A x A y C (已设(已设y C ,故,故y C 为真)为真) A C B C x B y C x B因此,因此, A B类似可证:类似可证: A B (C A C B)。 #(6)设设A、B、C、D为任意非空集合,则为任意非空集合,则 (A B C D) A C B D (证明与性质(证明与性质(5)的证明方法类似,从略
12、)的证明方法类似,从略)鼻滚律韧麓锄贾犹降六佑解刷菩镊聋荧葬舰轩峪代订颊傣梨艰肺苍杆荧衷第二二元关系第二二元关系14 Peking University3、笛卡儿积的性质(续2)例 证明证明(A-B) C=(A C)-(B C)。证证: (A-B) C x (A-B) y C x A x B y C (x A y C x B) (x A y C y C) (x A y C) (x B y C) (x A y C) ( x By C) (x A y C)(x B y C) A C B C (A C)-(B C)所以,所以,(A-B) C=(A C)-(B C)。#潍巢蚀到啃丙僚馁烃抠你尸丈汝忻搽
13、终乏艾喻烯届痰贬摆误兔宝蔓苟橇模第二二元关系第二二元关系15 Peking Universityn维卡氏积n定义2.4 设A1,A2,An为n个集合(n2),称集合|x1A1x2A2 xnAn 为n n维卡氏积维卡氏积,记作A1 A2 An ,当A1= =A2= = =An=A时,记A生成的n维卡氏积为An设设A A1 1,A,A2 2,A,An n均为有穷集合,并设均为有穷集合,并设|A|Ai i|=n|=ni i, i=1,2,n, i=1,2,n,则,则 |A|A1 1 A A2 2 A An n|=n|=n1 1 n n2 2 n nn n性质性质:例如AB(CD)=(ABC)(ABD
14、)ABC= A= B= C= .毛喘弄牲蓝囱荡噎派允瑶檄凉盔狄枝芒哭访帽渔袄侈矣卢毅恰眯键嘶题阳第二二元关系第二二元关系16 Peking University2.2 二元关系 事物之间存在着各式各样的关系,例如,三名学生事物之间存在着各式各样的关系,例如,三名学生A、B、C选修选修 、 、 、 四门课,设四门课,设A选选 和和 ,B选选 ,C选选 和和 ,那么,学生选课的对应关系可记作,那么,学生选课的对应关系可记作 : R=,这个序偶的集合这个序偶的集合R反映了学生集合反映了学生集合S=A,B,C与课程集与课程集合合T= , , , 之间的关系。之间的关系。关系的概念关系的运算(定理)频愿
15、郎汞熏过革掘蛊瞻俘焉绒吞锤百诅阳花膘骸藉夹卉医逃场呜客社髓沧第二二元关系第二二元关系17 Peking University定定义义2.52.5 若集合F中的全体元素均为有序的n(n2)元组,则称F为n n元元关关系系。当n=2时,称F为为二元关系, ,简称为关系。简称为关系。对于二元关系对于二元关系F,若,若 F,记作记作 xFy表示方法表示方法:(中缀,前缀,后缀)中缀,前缀,后缀)规定空集规定空集为为n元空关系,简称元空关系,简称空关系空关系煎窥峡秆汹搔原提淫混赦钨蹿正敏钾催胚记瞧观装颓杉烤戏逼顿蛛驯糠兵第二二元关系第二二元关系18 Peking Universityn元关系(续)n例1
16、: F1=,F1是4元关系. # n例2:F2=, F2是3元关系. #n例3:R1=, R1是2元关系. # n例4:R2=, R2是2元关系. # n例5:A=,a,1, A不是关系. #绚停勘迈惦撇须向誊幕操捉泉粕蝎俗汽瀑然欺父篮龙炉纪怂蟹址比兰趣长第二二元关系第二二元关系19 Peking University关系的概念(续1)定义2.6 设设A A和和B是是两两个个任任意意集集合合,卡卡氏氏积积A A B的任一子集的任一子集R称为称为A到到B B的二元的二元关系。RABRP(AB)若若|A|=m,|B|=n, 则则|AB|=mn, 故故|P(AB)|=2mn即即A到到B不同的二元关系
17、共有不同的二元关系共有2mn个个粮罪杆亲程腥攫厘盔纬炔操沫去余缴蔷咎赴弥氨瞎炮粟蒲堰墙拦放晶矣倘第二二元关系第二二元关系20 Peking University关系举例例 设设A=1A=1,2 2,3 3,44,求,求A A上的小于等于关系上的小于等于关系L LA A解解:L LA A=|x,y=|x,y A A x x yy =, =, , , # #蹬靴鸣牡脸肥漓蝉窿寐堰鸭营伙锨掏侣疮陷篡佰概待遗教锐擦峭庞杜枢坤第二二元关系第二二元关系21 Peking University关系举例n设A=a1,a2, B=b,则A到B的二元关系共有4个:R1= , R2=, R3=,R4=,. B到A的
18、二元关系也有4个:R5= , R6=, R7=,R8=,. #待神拱荷蝉察蜂舆汕道蓝暇熬撇液氨赌端稼原父况懂部逆食早闰肪姻权旗第二二元关系第二二元关系22 Peking University A上的二元关系A上的二元关系: 是AA的任意子集R是A上的二元关系RAARP(AA) 郁薯扑荆谬当殷雕憾虱软浩渭埂微怒酥盎梅惜寇眺仁翱二膳郎阀雀备妨和第二二元关系第二二元关系23 Peking University例 设集合设集合A A有有n n个元素个元素, ,问问A A上可能的二元关系有多少个?上可能的二元关系有多少个?解解:集集合合A A上上的的二二元元关关系系与与A A A A的的子子集集个个数数
19、相相同同。若若|A|=n|A|=n,则则|A|A A|=nA|=n2 2, , A A A A的的子子集集个个数数就就有有2 2的的n n2 2次次方方个个。所所以以A A上不同的二元关系有上不同的二元关系有2 2的的n n2 2次方个。次方个。 例如,集合例如,集合A=a,bA=a,b上的二元关系有上的二元关系有1616个个关系的概念(续4)以擂摊冠指龟放颐绷巧讣剧管勾丧专瘤冀头砷又闻钎博滥取核驼愤扩栅遵第二二元关系第二二元关系24 Peking University关系的概念(续3)求:求:集合集合A=a,bA=a,b上的上的1616个二元关系。个二元关系。R1= (空关系空关系) ;R2
20、=, R3=, R4=, R5=;R6= , (恒等关系恒等关系IA),R7=, R8=,R9=, R10=, R11=,;R12=, R13=,R14=, R15=,;R16= , (全域关系全域关系EA) 。勉芝缩挫因酱滤饿刽美像垃无雀缅掷副郧办躺绢妆茁癌痉堕定冠获唬获籍第二二元关系第二二元关系25 Peking University几种特殊的关系称称EA= ( x A y A) =A A A 是是A上上的的全域全域关系。称称IA= ( x A) 是是A上上的的恒等恒等关系。若A是实数集或其子集,称DA= ( x A y A x|y) 是是A上上的的整除整除关系。称LA= ( x A y
21、A x y) 是是A上上的的小于等于小于等于关系。若A为任意的集合称A= ( xA yA x y) 是是P(A)上上的的包含包含关系。称A= ( xA yA x y) 是是P(A)上上的的真包含真包含关系激指铅舅倔脾特毅综遣处柒镍萄破啊铅毅履死绽影旬用窄峰绅蟹酶娃今欲第二二元关系第二二元关系26 Peking University整除关系举例例: A=1,2,3,4,5,6, 则DA=, , , , , , , ,.#隆没因劲霖妄戳侠击谚井坦窥史敢谣径论宙陆邵枕舜趾裸坠南纯欢吁帆绪第二二元关系第二二元关系27 Peking University二元关系相关概念n 定义域, 值域, 域n 逆,
22、合成(复合)n 限制, 象n 单根, 单值题润盈坑乱垫铬瓢酌蜗刨膨串藉阎囱小楚迁靠绞旋久茨叔造娇楷剁午修唆第二二元关系第二二元关系28 Peking University关系相关的概念定义2.7 设设R为任一集合,称为任一集合,称domR = xy ( R) 为为R的的定义域,称称ranR = yx ( R) 为为R的的值域, 称称fldR = domR ranR为为R的的域。喊胶吃伸祟泡劈冻骗泄笼旋剁揣颜佯球瞪屉榜晚际元贝拇碾逛禄搅蠢林汁第二二元关系第二二元关系29 Peking University例:设R1=a,b,R2=a,b, R3=,解:当a,b不是有序对时, R1和R2不是关系.
23、由定义得domR1=, ranR1=, fldR1=,domR2=c,e,ranR2=d,f,fldR2=c,e,d,f,domR3=1,3,5,ranR3=2,4,6,fldR3=1,2,3,4,5,6#邹策彦藐碟嫩逝钵迢欺堡润筐陈肃腊巡恋泵鹃体始佛塞海纫傲锄潮弧涩程第二二元关系第二二元关系30 Peking University关系的运算定义2.8 设F,G,A为3个集合,(1)F的逆(inverse):称F-1=|F(2) F与G的合成合成或复合复合(composite): FG=|z(G F)GxzyF怕衔震绷烹钥烤擞宫尺掺断承凋趁地纱勿铂比赘状凌崎面窝笔儡坊可贪罕第二二元关系第二二元
24、关系31 Peking Universityn注意(1) 当R中无有序对时,domR,ranR,fldR均为(2) FG的合成为逆序合成逆序合成式吮起芦尺孰曾怖彰柯勤撇协呻拓田绊骗财篙恨滥馅凸甫牧硝匹涡救粪啃第二二元关系第二二元关系32 Peking University限制和像FA=| F x A为为F在在A上的上的限制限制(restriction)FA=ran(FA)为为A在在F下的下的像像FA=y|x(xA xRy) 磊粘兄泅八丢显苗丙铂式断甥佯杰尼硒畦瘤譬二硝痘节骸恬侵脯辽起玩敲第二二元关系第二二元关系33 Peking University单根若对于任意的若对于任意的yranF,唯一
25、地存在着xdomF, 使得F,则称F是单根单根(single rooted)的y( yran F !x( xdomF xFy) )(yran F)(!xdomF)(xFy) !表示“存在唯一的”胀金租极葵诌没搅却强暂吵淌健藉救郎蔗招梢速论仍券吹敢岛陆慨翟澜限第二二元关系第二二元关系34 Peking University单值(single valued)n若对于任意的xdomF,唯一地存在着yranF,使得F,则称F是单值单值的 x( xdomF !y( yran F xFy) (xdomF)(!yran F)(xFy)仍骇捷阔铅删锻前斜袁念寒宗茧卡磁杨哎徽刑蝎炸森吊汽投擂惦滑翅节托第二二元关
26、系第二二元关系35 Peking University举例设A=a,b,c,d, B=a,b, R=, F=, , G=,,求(1) A-1,B-1,R-1. (2) BR-1, GB, GR, RG. (3) F a, F a, F a,a, F-1 a.(4) Fa, Fa,a, F-1a, F-1a解解:(1) A-1=, B-1=,R-1=,.(2) BR-1=, GB=, GR=, RG=.(3) F a=,F a=, F a,a=F, F-1 a=.(4) Fa=b,a, Fa,a=b,a,a,a, F-1a= , F-1a=a#诸惟诀阂跺躇繁啦琅凄趁铂寡恐彪霖击龙衍咏宵伐熊抑巢绊
27、粹雷无茵赔穆第二二元关系第二二元关系36 Peking Universityn定理2.3 定义域和值域相关的定理n定理2.4逆的定义域和值域相关定理n定理2.5合成的结合律n定理2.6合成相关的分配律n定理2.7逆合成定理n定理2.8限制相关的定理n定理2.9像相关的定理佐堵空割龋狄光铲缠忻府釜啃祖吉拼鞋郸多样女卯伶又曳樱惫锐抬拄侨难第二二元关系第二二元关系37 Peking University定理定理2.3 设F,G为二集合,则(1)dom(FG) = domFdomG; (2)ran(FG) = ranFranG; (3)dom(FG) domFdomG;(4)ran(FG) ranFr
28、anG; (5)domFdomG dom(F G);(6)ranFranG ran(F G).幌屎翁介霉蝇贰稼薯灭诬米酿凡悉惟骂尉重雄迅捡屑篱礁蜂皋禽癌析话咨第二二元关系第二二元关系38 Peking University定理2.3的证明证:dom(FG) = domFdomG证明:x, xdom(FG)y( FG)y( F)(G)y( F) y(G)xdom(F) xdom(G)x (dom(F) dom(G) dom(FG) = domFdomG#页洋先柿朵龚猩械枉谚眺犯幸锥敖形雨逾杀垣鹰佯靖钥豹旦护霹百补狼津第二二元关系第二二元关系39 Peking University证:ran(FG
29、) ranFranG证明:y, yran(FG)x( FG)x(FG)x(F)x(G)(P7)yran(F)yran(G)y(ranF ranG) ran(FG) ranFranG#定理2.3的证明(续)予筏弄钦板亦忱釉揉个跺否郭耍崔送厅肇掺哮呢痴厄裔桃舒溉贪瓶匈勒铝第二二元关系第二二元关系40 Peking University证:domFdomG dom(F G)证明:x, x(domF-domG)(xdomF)(xdomG)y(F)z(G) y(F-G)x dom(F-G) domFdomG dom(F G)定理2.3的证明(续)渺陕哈狮醉把价蔚燎岩谣宇宫或婿竭候尽丧帕仟吐扫狡皆麦教鞘灶
30、传剃酣第二二元关系第二二元关系41 Peking University逆的定义域和值域相关定理定理2.4 设F为任一集合,则(1)domF-1=ranF;(2)ranF-1=domF;(3)(F-1)-1F,当F为关系时,等号成立帕核鸿婆游甄佳矾萧呕撂届瑚愁杖身演鸭洋抵专嘴硼辞生碱裹骚八妨随了第二二元关系第二二元关系42 Peking University定理2.4(1)的证明(1) 证明: x, xdomF-1yF-1yFxranFdomF-1=ranF#逼脂拷娩曰空奢嗣楚甲苞夯宏辩嘲柠电蔫渔磺兵痒隘镊仁纳跪僵滇屹哄慑第二二元关系第二二元关系43 Peking University定理2.4
31、(3)的证明(3) (F-1)-1F, 当F是关系时, 等号成立.证明: (1) 设F是关系, 则,(F-1)-1 x(F-1)-1y yF-1xxFy.这时(F-1)-1= F. 当F不是关系时,(F-1)-1F, 例如, 设F=,a, 则F-1=, (F-1)-1= F(F-1)-1F. #秉相宇释海瓦翟吧蒂筷漾咕般龋榜仲顿蠢陷磕岁端散塌掠遣梨咯臀什杠虑第二二元关系第二二元关系44 Peking University合成运算的结合律定理定理2.5 设R1,R2,R3为三个集合,则(R1 R2)R3 = R1(R2R3)证明: , (R1 R2)R3 z(R3(R1 R2)z(R3 t(R2
32、 R1)z t(R3R2 R1)t(z (R3R2 R1)t(R2 R3 R1) R1 (R2 R3)(R1 R2)R3 = R1(R2R3)#熏葬唆谨吸宦挛喝朽俘错乞卒耗穗臃稍扒丈嚏绕不思扔堕毗铺剑皮锁鳃裹第二二元关系第二二元关系45 Peking UniversityxyztR3R2R1辗寐掠夜臼计硬娘那骨紧装说伟颅创渴灯申愧澄欲剧元雀而揪顶嚎使毋系第二二元关系第二二元关系46 Peking University合成运算的分配律定理定理2.6设R1,R2,R3为三个集合,则(1)R1(R2 R3)=R1R2 R1R3;(2)(R1R2)R3 =R1R3R2R3;(3)R1(R2R3) R1
33、R2 R1R3;(4)(R1R2)R3 R1R3 R2R3.肠迢抿妹秩句位枫跺各呼时更阴侮颠订汾氢簿话碑篡汉腰熙尉滩吭绦白缺第二二元关系第二二元关系47 Peking University分配律的证明R1(R2 R3)=R1R2 R1R3证明:证明: , R1 (R2 R3) z( (R2 R3) R1) z( R2 R3) R1) z( R2 R1) ( R3 R1) z( R2 R1) z( R3 R1) R1 R2 R1 R3 (R1 R2 R1 R3) R1 (R2 R3)=R1 R2 R1 R3#紊栗跌侣眺脓戳邯韩缔狮秃郎纱裔稻猾敦哇厢职叹焦祖凌蒋三翅坍免还茫第二二元关系第二二元关系
34、48 Peking University分配律的证明(续)R1(R2R3) R1R2 R1R3证明: , R1 (R2R3) z( (R2R3) R1) z( R2 R3) R1) z( R2 R1) ( R3 R1) z( R2 R1) z( R3 R1) R1 R2 R1 R3 R1 R2R1 R3 R1 (R2 R3)=R1 R2 R1 R3#系晓粪巨际宋救债榴汐近叹碧迂旦裤酸墨谬晴酷寻假蓟噶菏妹隧奶皱详姆第二二元关系第二二元关系49 Peking University合成的逆运算 定理定理2.7 设F,G为二集合,则(FG)-1=G-1 F-1证明: , (FG)-1 FG z( G
35、F)z( G-1 F-1) G-1 F-1(FG)-1=G-1 F-1#烩七匙堤属嫂乙沧套碴胺责劲福子汇篷亚操泛丫柜塑津矛鲜硼鼎镶户惊陋第二二元关系第二二元关系50 Peking UniversityGG-1FF-1(FG)-1=G-1 F-1(FG)-1G-1 F-1xzyxzy蛮态拧夏丑薛狮蛇热鸳赣对募京铁粳塞搜伴膀乱寨琳粉澜喊乃荐伟雀梳十第二二元关系第二二元关系51 Peking University定理2.8定理2.8 设设R,S,A,B,A为集合为集合,A,则则(1)R (AB)=(R A)(R B);(2)R A =R A|A A ;(3)R (AB)=(R A)(R B);(4)
36、R A =R A|A A ;(5)(RS) A=R(S A).区拧宿莫筷这唉剁寺膨悟枫穗赡极枣循虹晨凤柔辩酝蹭旁傀瀑藉物剪碍虾第二二元关系第二二元关系52 Peking University定理2.8(2)的证明(2) RA = RA | AA;证明证明: , (RA) xRy xA xRy A( AA xA ) A( xRy xA AA ) A( (RA) AA ) RA | AA. RA = RA | AA#你玲拉绅骏揉娶代冲是舜劝书婉堕搁谊射葱辜嗜嗡衍肩厕而案陆澈避侩僳第二二元关系第二二元关系53 Peking University定理2.8(4)的证明(4) RA = RA | AA;
37、 (A)证明证明:, (RA) xRyxAxRy A(AAxA)A(xRy (AA xA)A(xRy AA)(xRy xA)A(RAA)(RA)A(AA(RA)A(AA RA) RA | AA RA = RA | AA#扬蓄科沿媚喂怜舰漫行群乌祭锐秘域彤取形哭阎淋贸淫闸镀妆爸车膜宵傣第二二元关系第二二元关系54 Peking University定理2.8(5)的证明(5) (RS)A = R(SA)证明证明: , (RS)A)(RS)xA z(xSzzRy ) xA z(xSzzRy xA) z(xSzxA) zRy )z( (SA) zRy ) R(SA) (RS)A = R(SA). #敏偶趴庚券圣勋船箩蕴佬佑丹再拙玉乱顿手扣胁巷柠忘衬譬厕谬剥缎蕾盎第二二元关系第二二元关系55 Peking University小结n有序对n卡氏积n二元关系相关的基本概念n二元关系相关的运算n基本概念和运算相关的定律吉笆豹锋椎拣埃续秽糯植学憨悼窗古宿筛屯惭彩债捉钡逆知敦涵葫氟竹深第二二元关系第二二元关系56 Peking UniversityP53: 1P54: 6, 7(1), 9, 11(2,4,5),12洗萝狞彤问抄篱晒叶残京分锅雾坍茁虏候菠章仁哇樟缅惋驻怠粹绑控给鳞第二二元关系第二二元关系57 Peking University