关系的表示 设A={x1,x2,…,xn},R是A上的关系.令图G=<V,E>, 其中顶点集合V=A,边集为E.对于Ⅵx1,x2∈V,满足:<x1, x2>∈E台<x1,x2>∈R,称图G为R的关系图,记作GR 16
16 关系的表示 设A = { x1, x2, ..., xn }, R是A上的关系. 令图G = <V, E>, 其中顶点集合V = A, 边集为E. 对于∀x1, x2∈V, 满足: <x1, x2>∈E ⇔ <x1, x2>∈R, 称图G为R的关系图, 记作GR
关系的基本运算 关系的基本运算有:定义域,值域,域,逆关系,右复合(左 复合),限制和像等七种 设R是二元关系 >R中所有有序对的第一元素构成的集合称为R的定义域( Domain), 记作domR其形式化表示为:domR={x|y(<x,y>∈R)} >R中所有有序对的第二元素构成的集合称为R的值域 ( Range),记作ranR其形式化表示为:ranR={y x(<x,y>∈R)} >R的定义域和值域的并集称为R的域( Field,记作ndR 其形式化表示为:fdR= dome U ranR ·例:设R={<1,2>,<1,3>,<2,4>,<4,3>}, >domR={1,2,4},ranR={2,3,4},fdR={1,2,3,4}
17 关系的基本运算 z 关系的基本运算有: 定义域, 值域, 域, 逆关系, 右复合(左 复合), 限制和像等七种. z 设R是二元关系 ¾ R中所有有序对的第一元素构成的集合称为R的定义域(Domain), 记作domR.其形式化表示为: domR = { x | ∃y(<x, y>∈R) } ¾ R中所有有序对的第二元素构成的集合称为R的值域 (Range), 记作ranR.其形式化表示为: ranR = { y | ∃x(<x, y>∈R) } ¾ R的定义域和值域的并集称为R的域(Field), 记作fldR. 其形式化表示为: fldR = domR ∪ ranR z 例: 设 R = { <1, 2>, <1, 3>, <2, 4>, <4, 3> }, ¾ domR = { 1, 2, 4 }, ranR = { 2, 3, 4 }, fldR = { 1, 2, 3, 4 }
关系的基本运算 设R为二元关系,把R的逆关系简称R的逆,记作R1,其中 R1={<x,y>|<y,x>∈R} 设F和G为二元关系,G对F的右复合FG定义为: FG={<X,y>|3t(<x,t∈F∧<t,y>∈G)} 类似地,可以定义关系的左复合,即: FG={<x,y>|彐t(<x,t>∈G∧<t,y>∈F)} 如无特殊说明,本课程采用的复合运算遵循右复合的定义 例:设F={<3,3>,<6,2>},G={<2,3>},则 F1={<3,3>,<2,6>},F°G={<6,3>},GF={<2,3> 18
18 关系的基本运算 z 设R为二元关系, 把R的逆关系简称R的逆, 记作R-1, 其中 R-1 = { <x, y> | <y, x>∈R } z 设F和G为二元关系, G对F的右复合F°G定义为: F°G = { <x, y> | ∃t(<x, t>∈F∧<t, y>∈G) } z 类似地, 可以定义关系的左复合, 即: F°G = { <x, y> | ∃t(<x, t>∈G∧<t, y>∈F) } z 如无特殊说明,本课程采用的复合运算遵循右复合的定义. z 例: 设F = { <3, 3>, <6, 2> }, G = { <2, 3> }, 则 ¾ F-1 = { <3, 3>, <2, 6> }, F°G = { <6, 3> }, G°F = { <2, 3> }
关系的基本运算 设R为二元关系,A是集合 (1)R在A上的限制,记作R,其中RA={<x,y>|<x,y>∈R∧ X∈A} >(2)A在R下的像,记作R|A,其中R[A|=ran(RA) 不难看出:R在A上的限制是R的子关系,A在R下的像是 ranR的子集 19
19 关系的基本运算 z 设R为二元关系, A是集合 ¾ (1) R在A上的限制, 记作R A, 其中R A = { <x, y> | <x, y>∈R ∧ x∈A } ¾ (2) A在R下的像, 记作R[A], 其中R[A] = ran(R A) z 不难看出: R在A上的限制是R的子关系, A在R下的像是 ranR的子集
关系基本运算的性质 定理设F是任意的关系,则 >(1)(F)1=F (2)domF-=ranF, ranF-=domF 证明 (1)任取<x,y>,由逆的定义可知: ,y>∈(F) ∈F今 F 所以,有:(F)1=F (2)任取x X∈domF1分y(<x,y>∈F)兮丑y(<y,x>∈F X∈ranF 所以,有: domF-I=ranF 20 同理可证:ranF1=domF
20 关系基本运算的性质 z 定理 设F是任意的关系, 则 ¾ (1) (F-1)-1 = F ¾ (2) domF-1 = ranF, ranF-1 = domF 证明: (1) 任取<x, y>, 由逆的定义可知: <x, y>∈(F-1)-1 ⇔ <y, x>∈F-1 ⇔ <x, y>∈F 所以, 有: (F-1)-1 = F. (2) 任取x, x∈domF-1 ⇔ ∃y(<x, y>∈F-1) ⇔ ∃y(<y, x>∈F) ⇔ x∈ranF 所以, 有: domF-1 = ranF. 同理可证: ranF-1 = domF