集合论与图论2.2

《集合论与图论2.2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2.3关系的运算*关系的运算有七种,分别列出如下:定义7.6:设R是二元关系.(1)R中所有有序对的第一个元素构成的集合称为R的定义域,记作domR.domR={x

2、y(∈R)}(2)R中所有有序对的第二个元素构成的集合称为R的值域,记作ranR.ranR={y

3、x(∈R)}.(3)R的定义域和值域的并集称为R的域,记作fldR.fldR=domR∪ranR.例1:R={<1,2>,<1,3>,<2,4>,<4,3>},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}定义7.7:设R为二元关系,R的逆关系

4、,简称R的逆,记作R-1,定义为R-1={

5、∈R}.定义7.8:设F,G为二元关系,G对F的右复合,记做FG,定义为FG={

6、t(∈F∧∈G)}.例2:设F={<3,3>,<6,2>},G={<2,3>},则F-1={<3,3>,<2,6>}FG={<6,3>}GF={<2,3>}.*左复合:FG={

7、t(∈G∧∈F)}*有些书上用左复合,但右复合比较直观,本书用右复合.定义7.9:设R为二元关系,A是集合(1)R在A上的限制,记作R

8、A,定义为R

9、A={

10、xRy∧

11、x∈A}(2)A在R下的像,记作R[A],定义为R[A]=ran(R

12、A)*R

13、A是R的子关系,R[A]是ranR的子集.例3:设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},则R

14、{1}={<1,2>,<1,3>}R

15、φ=φR

16、{2,3}={<2,2>,<2,4>,<3,2>}R[{1}]={2,3}R[φ]=φR[{3}]={2}.*关系运算的优先级:1.逆运算2.关系的其它运算3.集合运算4.先括号里后括号外1.同级运算从左到右例子:ranF-1,FG∪FH,ran(F

17、A).*关系运算的性质:定理7.1:设F是任意的关系,则

18、(1)(F-1)-1=F(2)domF-1=ranF,ranF-1=domF.证明:(1)任取,由逆的定义,有∈(F-1)-1∈F-1∈F,所以(F-1)-1=F.(2)任取x,x∈domF-1y(∈F-1)y(∈F)x∈ranF.所以domF-1=ranF.同理可证ranF-1=domF.定理7.2:设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)-1=G-1F-1证明:(1)任取,∈(FG)Ht(∈FG∧∈H)t(s(∈

19、F∧∈G)∧∈H)ts(∈F∧∈G∧∈H)s(∈F∧t(∈G∧∈H))s(∈F∧∈GH)∈F(GH)所以(FG)H=F(GH).(1)的另一种证明:对任意∈(FG)H,则存在t使得∈FG且∈H.又由∈FG,有s使得∈F且∈G.由∈G和∈H,有∈GH,再由∈F,有∈F(GH).故(FG)HF(GH).对任意∈F(GH),存在s,使

20、得∈F且∈GH.再由∈GH,存在t,使得∈G且∈H.由∈F和∈G,有∈FG,再由∈H,有∈(FG)H.故(FG)HF(GH).因此(FG)H=F(GH).(2)任取,∈(FG)-1∈FGt(∈F∧∈G)t(∈F-1∧∈G-1)t(∈G-1∧∈F-1)∈G-1F-1.定理7.3:设R是A上的关系,则RIA=IAR=R.证明:任取,∈RIAt

21、(∈R∧∈IA)t(∈R∧t=y)∈R∈R∈R∧y∈A∈R∧∈IA∈RIA从而有RIA=R.同理可证IAR=R.定理7.4:设F,G,H为任意关系,则(1)F(G∪H)=(FG)∪(FH)(2)(G∪H)F=(GF)∪(HF)(3)F(G∩H)FG∩FH(4)(G∩H)FGF∩HF.证明:只证(3)式.任取,∈F(G∩H)t(∈F∧∈G∩H)t(∈F∧(∈G∧∈H))t((∈F∧

22、>∈G)∧(∈F∧∈H))t(∈F∧∈G