二元关系 设A和B为集合,A×B的任何子集所定义的二元关系叫做 从A到B的二元关系当A=B时,则称该关系为A上的二元 关系 例如:A={0,1},B={1,2,3},那么 R1={<0,2>} R2=A×B R3=φ R4={≤0,1>} 都是从A到B的二元关系,且R3和R4也是A上的二元关系 集合A上二元关系的数目依赖于A中的元素数. >若|A|=n,则,AxA|=m2,AxA的子集就有2个 因为每一个子集代表一个A上的二元关系,所以,A上 有2n2个不同的二元关系. 例如:A|=3,则A上有232=512个不同的二元关系
11 二元关系 z 设A和B为集合, A × B的任何子集所定义的二元关系叫做 从A到B的二元关系.当A = B时, 则称该关系为A上的二元 关系. 例如: A = { 0, 1 }, B = { 1, 2, 3 }, 那么, R1 = { <0, 2> } R2 = A × B R3 = φ R4 = {<0, 1>} 都是从A到B的二元关系, 且R3和R4也是A上的二元关系. z 集合A上二元关系的数目依赖于A中的元素数. ¾ 若|A| = n, 则, |A × A| = n2, A × A的子集就有2n2个. ¾ 因为每一个子集代表一个A上的二元关系, 所以, A上 有2n2个不同的二元关系. ¾ 例如: |A| = 3, 则A上有232 = 512个不同的二元关系
空关系,全域关系和恒等关系 对于任何集合A,称空集ψ为A上的空关系 对任意集合A,A上的全域关系( Universal relation)为 EA={<x,y>|x∈A∧y∈A}=A×A; A上的恒等关系 (Identity relation)为IA={x,x>x∈A} 例如,A={1,2},则 EA={<1,1>,<1,2>,<2,1>,<2,2>} IA={<1,1>,<2,2>}
12 空关系,全域关系和恒等关系 z 对于任何集合A, 称空集φ为A上的空关系. z 对任意集合A, A上的全域关系(Universal Relation) 为 EA = { <x, y> | x ∈A ∧ y∈A } = A × A; A上的恒等关系(Identity Relation)为 IA = { <x, x> | ∀x∈A }. 例如, A = { 1, 2 }, 则 EA = { <1, 1>, <1, 2>, <2, 1>, <2, 2> } IA = { <1, 1>, <2, 2> }
常用的关系 除空关系,全域关系和恒等关系这三种特殊关系之外,还有一些常用 的关系 LA =<X, y >X, yEA, XSY,ACRI DB={<x,y>|x,y∈B,x整除y,BZ} Rc={<x,y>|x,y∈C,xsy,C是集合族} 其中,L叫做A上的小于等于(≤关系,D1叫做B上的整除关系,其中x是y 的因子,Rc叫做C上的包含关系 例如,A={1,2,3},B={a,b},则有 LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} 设C={,{a},{b},则有 R={φ,φ>,φ,{a}>,φ,{b}>,<{a},{a}>,<t},{b} 类似地,还可以定义大于等于关系,小于关系,大于关系,真包含关系等 13
13 常用的关系 z 除空关系, 全域关系和恒等关系这三种特殊关系之外, 还有一些常用 的关系: LA = { <x, y> | x, y∈A, x ≤ y, A ⊆ R } DB = { <x, y> | x, y∈B, x整除y, B ⊆ Z* } R⊆ = { <x, y> | x, y∈C, x ⊆ y, C是集合族 } 其中, LA叫做A上的小于等于(≤)关系, DB叫做B上的整除关系, 其中x是y 的因子, R⊆叫做C上的包含关系. 例如, A = { 1, 2, 3 }, B = { a, b }, 则有 LA = { <1, 1>, <1, 2>, <1, 3>, <2, 2>, <2, 3>, <3, 3> } DA = { <1, 1>, <1, 2>, <1, 3>, <2, 2>, <3, 3> } 设C={φ,{a},{b}},则有 R⊆ = {<φ , φ>, <φ , {a}>, <φ , {b}>, <{a} , {a}>, <{b} , {b}>} 类似地, 还可以定义大于等于关系, 小于关系, 大于关系, 真包含关系等
关系的表示 给出一个关系的方法有三种: 集合表达式 >关系矩阵 关系图 14
14 关系的表示 z 给出一个关系的方法有三种: ¾ 集合表达式 ¾ 关系矩阵 ¾ 关系图
关系的表示 设A={xpx2…,xn}R是A上的关系令 <x.X.>∈R >∈R (i,j=1,2 则,R的关系矩阵M如下所示
15 关系的表示 设A = { x1, x2, ..., xn }, R是A上的关系.令 ( , 1,2,..., ) , , 0 1 i j n x x R x x R r i j i j ij = ⎩⎨⎧ < >∉ < >∈ = 则, R的关系矩阵MR如下所示. ⎥⎥⎥⎥⎦⎤ ⎢⎢⎢⎢⎣⎡ = = n n nnnn R ij r r r r r r r r r M r L M M M M LL 1 2 21 22 2 11 12 1 ( )