第5章 关　　 系 5.1　关系的定义 定义5- 1 设 A 和 B 为集合,笛卡儿积A×B 的任意一个子集称为集合 A 到集合 B 的二元关系,简称关系,用大写字母 R 表示,如果∈R,记作xRy。如果 A =B, 则称 R 为集合 A 上的关系。 1 a,B={0,1, 例5.设A={b},2}, 则 : A×B={,,,,, } 由于关系 R 是A×B 的子集,因此 : R1={,, } R2={,,, } R3={ } R4= . 其中R1、R2、R3、R4 都是集合 A 到集合 B 的关系。 例5.2 设集合A={2,3,4}, 试计算该集合上的整除关系。 解:根据整除关系的定义,得知∈ R 当且仅当x| R={<2,2>,<3,3>,<4,4>,<2,4>} 集合 A 上的二元关系的数目依赖于 A 中的元素。如果|A|=n,那么 A×A =n2, 22 A×A 的子集就有2n个,每一个子集代表一个 A 上的二元关系,所以 A 上有2n个不同 的二元关系。例如,A={2,3,4},|A|=3,则 A 上有29=512 个不同的二元关系。 例5.3 设|A|=m,|B|=n,计算从 A 到 B 有多少个不同的关系? 解:|A|=m,|B|=n,则 =mn,A×B 的子集就有2mn 个,所以A×B 上有 A×B 第5 章　关系 87 2mn 个不同的关系。 对于任意集合A ,存在以下三个特殊关系: (1).是A ×A 的子集,所以.是A 上的关系,称为空关系; (2)全域关系:EA ={|a∈A ∧b∈A}=A ×A ; (3)恒等关系:IA ={|a∈A}。 例5.4 若集合A ={a,b},求EA 和IA 。 解: EA =A ×A ={,,,},IA ={,}。 除了以上三种特殊关系以外,还有一些常用的关系,定义如下: (1)小于等于关系:LA ={|a,b∈A ∧a≤b}; (2)整除关系:DA ={ a,b∈A ∧a b}; (3)集合上的包含关系:R. ={|x,y∈P(A)∧x.y}。 定义5-2 设二元关系R.A ×B,则R 中所有有序对的第一元素构成的集合称为R 的定义域,记作domR,表示为: domR={a|.b∈B→∈R} R 中所有有序对的第二元素构成的集合称为R 的值域,记作ranR,表示为: ranR={b|.a∈A →∈R} 显然,因为R.A ×B,所以domR.A ,ranR.B。 例5.5 设集合A ={1,2,3},R 是A 上的关系,定义如下: R={|a,b∈A ∧ (b-a)/2是整数} 试求出R、domR 及ranR。 解:由已知,有R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>},进一步得到 domR={1,2,3},ranR={1,2,3}。 5.2　关系的表示 关系实际上就是集合,关系常见的表示方法有3种,除了集合表示方法外,还可以用 关系矩阵和关系图表示。 5.2.1　关系的矩阵表示 定义5-3 设集合A ={a1,a2,…,am },集合B ={b1,b2,…,bn },集合A 到集合B 88 离散数学 的关系R 可以用矩阵MR =r( ij )m ×n 来表示,其中: rij= 1 ∈R 0 .R { i( =1,2,…,m ,j=1,2,…,n) 关系矩阵适合表示从A 到B 的关系或A 上的关系,其中A 和B 均为有限集合。 例5.6 设集合A ={1,2,3},集合B ={2,3,4},计算集合A 到集合B 上的大于等 于关系和集合A 上的小于等于关系,并用关系矩阵表示。 解: RA≥B ={|a∈A ,b∈B,a≥b}={<2,2>,<3,2>,<3,3>} RA≤A ={|a∈A ,b∈A ,a≤b} ={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>} 运用关系矩阵表示,如下所示: MRA ≥B = 0 0 0 1 0 0 1 1 0 é . êêêê ù . úúúú , MRA ≤A = 1 1 1 0 1 1 0 0 1 é . êêêê ù . úúúú 5.2.2　关系的关系图表示 定义5-4 设关系R 是集合A ={a1,a2,…,am }到集合B ={b1,b2,…,bn }的关系, 用关系图表示:将集合A 和集合B 中的每一个元素ai和bj分别用小圆圈表示,集合A 画 在左边,集合B 画在右边,如果∈R,则从表示ai的小圆圈向表示bj的小圆圈画 一条有向弧。 如果关系R 是集合A 上的关系,则通常只将集合A 中所有的元素用小圆圈表示,画 到一块,点与点之间没有顺序关系,若∈R,则从表示ai的小圆圈向表示aj 的 小圆圈画一条有向弧,如果∈R,则从ai画一条指向自己的环。 例5.7 画出例5.6所求出关系的关系图。 解:关系图如图5-1和图5-2所示。 图5-1 GRA≥B 图5-2 GRA≤A 第5 章　关系 89 在画关系图时,集合A 和集合B 中所有的元素都要用一个点表示,如图5-1中集合 A 的元素1也要用一个点表示。只要∈R 中,则都要从元素a 到元素b 画一条 有向边,这意味着关系R 中有多少个序偶,则在关系图GR 中就有多少条有向边,特别要 注意的是图5-2中元素1到1的一条有向边,它又称为1到1的一个环(或自环)。 5.3　关系的运算 5.3.1　关系的集合运算 根据关系的定义可知,关系的本质是由序偶构成的集合,因此,集合上的交集、并集、 差集和补集等运算同样适合关系。 定义5-5 设关系R 和S 是集合A 到集合B 的关系,即R、S.A ×B,则关系的并、 交、差、补及对称差运算如下: R∪S={|∈R∨∈S} R∩S={|∈R∧∈S} R-S={|∈R∧.S} R={|∈A ×B∧.R} R..S={|(∈R∧.S ) ∨ (.R∧∈S ) } 例5.8 设集合A ={2,3,4},R 为A 上的整除关系,S 为A 上的小于关系,分别计 算:R∪S、R∩S、R、R-S。 解:先求出关系R 和S: R={<2,2>,<2,4>,<3,3>,<4,4>} S={<2,3>,<2,4>,<3,4>} 再计算R∪S、R∩S、R、R-S: R∪S={<2,2>,<2,4>,<3,3>,<4,4>,<2,3>,<3,4>} R∩S={<2,4>} 因为R 为A 上的关系,所以R 对应的全集: U =A ×A ={<2,2>,<2,3>,<2,4>,<3,2><3,3>,<3,4>,<4,2>, <4,3>,<4,4>} R=U -R={<2,3><3,2>,<4,2>,<3,4>,<4,3>} 90 离散数学 R-S={<2,2>,<3,3>,<4,4>} 5.2　关系的复合运算 3. 定义5- 6 设 R 是集合 A 到集合 B 的关系, S 是集合 B 到集合 C 的关系,则 R 和 S 的复合关系R.. S 是集合 A 到集合 C 的关系,定义为: R..S={|.b∈B,b>∈R,c>∈S} 注意:如果关系 R 和 S 中有一个是空关系,复合的结果仍然是空关系,即: R...=...R=. 关系复合运算的一些例子:若 x 是 y 的母亲, y 是 z 的妻子,则 x 是 z 的岳母;若 a 是 b 的父亲,则 a 是 c 的祖父。 b 是 c 的父亲, R 为: 例5.设集合 A {b,d},=1,3,C=α,γ, A 到 B 的关系 9 =a,c, B {2,4},{β,δ}, a,a,b,d,c, B 到 C 的关系 S 为 R: ={(1),(2),(2),(3),(4)} , α),(β),(δ),(β)} , 试计算R..S。 S={(1,2,2,3, 解:根据复合运算的定义,求出所有满足条件的序偶 : (1)∈R,<1, α>∈R..S, 1∈B, α>∈S; (2)∈R,<2, β>∈R..S, 2∈B, β>∈S; (3)∈S; δ>∈R..S, 2>∈R,<2, (4)∈S; β>∈R..S, 2>∈R,<2, (5)∈S; δ>∈R..S, 2>∈R,<2,6)∈R..S,因为存在b=3∈B,使得∈R,<3,( 于是:R..S={(α),(β),(δ),(β),(δ),(β)}。 β>∈S。 a,a,a,b,b,d, 借助关系图,可以用图5-3来理解上面所给出的例子 。 图5- 3 R.. S 的关系表示 第5 章　关系 91 例5.10 设R 和S 均为集合A ={1,2,3}上的关系,其中 R={<1,2>,<1,3>,<2,3>,<3,3>} S={<1,3>,<2,1>,<2,2>,<3,3>} 计算R..S、S..R、R..R。 解:由复合关系定义可得: R..S={<1,1>,<1,2>,<1,3>,<2,3>,<3,3>} R..R={<1,3>,<2,3>} S..R={<1,3>,<2,2><2,3>,<3,3>} 由上述例子可知关系的复合运算不满足交换律,即一般来说R..S≠S..R。 定理5-1 设R、S、T 是集合A 上的关系,则有: (1)R..(S∪T ) = (R..S ) ∪ (R..T ) ; (2)R..(S∩T ) . (R..S ) ∩ (R..T ) ; (3)(R∪S )..T = (R..T ) ∪ (S..T ) ; (4)(R∩S )..T . (R..T ) ∩ (S..T ) 。 分析:关系本质上是由序偶构成的集合,关系的集合运算以及关系的复合运算的结 果都仍然是一个集合。因此,上述式子本质上是证明两个集合相等,即只需证明左右两 者互为子集。 证明: (1)对任意序偶∈R..(S∪T ) ,根据复合关系定义可知,存在元素c∈A , 使得: ∈R∧∈S∪T .∈R∧ (∈S∨∈T ) . (∈R∧∈S ) ∨ (∈R∧∈T ) .∈R..S∨∈R..T .∈ (R..S ) ∪ (R..T ) 因此有R..(S∪T ) . (R..S ) ∪ (R..T ) 。 同理,对任意序偶∈ (R..S ) ∪ (R..T ) ,根据并集的定义有: ∈R..S∨∈R..T 根据复合关系的定义可知,存在元素c1、c2∈A ,使得: (∈R∧∈S ) ∨ (∈R∧∈T ) . (∈R∧∈S∪T ) ∨ (∈R∧∈S∪T ) 92 离散数学 .∈R..(S∪T ) 因此有:(R..S ) ∪ (R..T ) .R..(S∪T ) 。 综上可得:R..(S∪T ) = (R..S ) ∪ (R..T ) 。 类似的方法,可以证明(2)、(3)和(4)。 定理5-2 设R 是集合A 到集合B 的关系,S 是集合B 到集合C 的关系,T 是集合 C 到集合D 的关系,则有 (R..S )..T =R..(S..T ) 证明: 第一步:证明(R..S)..T .R..(S..T)。 .(x,w )∈(R..S)..T ..z∈C:(x,z)∈R..S,(z,w )∈T ..z∈C.y∈B:(x,y)∈R,(y,z)∈S,(z,w ) ∈T .(x,y)∈R,(y,w )∈S..T .(x,w )∈R..(S..T) 第二步:类似的可证明(R..S)..T .R..(S..T)。实际上,上述过程可倒推回去。 所以有: (R..S )..T =R..(S..T ) 5.3.3　关系的幂运算 定义5-7 在关系R 和S 的复合运算R..S 中,如果R =S,将R..R 表示为R2,称为 R 的幂。类似地,如果R 是集合A 上的运算,则可以定义关系R 的n 次幂: (1)R0=IA ={|a∈A}; (2)Rm +n =Rm..Rn 。 由以上定义可知,对于A 上的任何关系R1 和R2 都有: R01 =R02 =IA 也就是A 上任何关系的0次幂都等于A 上的恒等关系IA 。此外对A 上的任何关系 R 都有R1=R0..R=IA..R=R。 例5.11 设集合A ={a,b,c,d,e},定义该集合上的关系R 如下: R={,,,,,} 则有: R2={,,,,} R3={,,,,} 第5 章　关系 93 R4={,,,,}=R3 R5=R4..R=R3..R=R3 定理5-3 设A 是有限集合,且|A|=n,R 是A 上的关系,则有: ∪∞ i=1 Ri=∪n i=1 Ri 分析:关系的复合仍然是关系,关系本质上讲是集合,因此上述等式左右两边都是集 合。证明两个集合相等,只需要证明两者互为子集。上述等式中,左边是无穷多个集合 的并集,右边是n 个集合的并集,且右边的集合也都在左边的等式内,即右边集合是左边 的子集,所以只需证明左边集合也是右边集合的子集即可。 证明: (1)显然有∪n i=1 Ri.∪∞ i=1 Ri; (2)∪∞ i=1 Ri=∪n i=1 Ri∪ ∪∞ i=n+1 Ri,显然∪n i=1 Ri.∪n i=1 Ri,因此只需证明∪∞ i=n+1 Ri.∪n i=1 Ri。对 任意的∈Rk(k≥n+1),由复合运算定义可知,存在a1,a2,…,ak-1∈A ,使得: ,,…,∈R 又|A|=n,k≥n+1≥n,因此根据鸽笼原理a,a1,a2,…,ak-1,b,这k+1个元素中 至少有两个元素相同。假设ai=aj i( ,…,,,…,,…,∈R 由于ai=aj,上述关系中可以删除如下部分: ,…, 变成: ,…,,…,∈R 成立,即∈Rk'=Rk-(j-i)。如果k- j( -i) ≥n+1,则可以继续上述过程,直到 ∈Rk'(k'≤n)。又Rk'.∪n i=1 Ri,得到∈∪n i=1 Ri,即Rk .∪n i=1 Ri。 由k 的任意性可知:∪∞ i=n+1 Ri.∪n i=1 Ri,进一步得到:∪∞ i=1 Ri.∪n i=1 Ri。 综上:∪∞ i=1 Ri=∪n i=1 Ri。 5.3.4　关系的逆运算 定义5-8 设R 是集合A 到集合B 的关系,则R 的逆关系表示为R-1,定义为: 94 离散数学 R-1={|∈R} 实际意义:若x 是y 的老师,则y 是x 的学生。 实数集合上的“大于等于”关系和“小于等于”关系,整数集合上的“整除”关系和“被 整除”关系,幂集合上的“包含”关系和“被包含”关系,均互为逆关系。有些关系的逆关系 是它自己,例如整数集合上的模k 同余关系和幂集上集合的补关系的逆关系都是它 自己。定 理5-4 设R 和S 是集合A 上的关系,则: (R..S )-1=S-1..R-1 分析:关系的逆运算后还是关系,关系从本质上讲是集合。因此该定理实际上是证 明左右两个集合相等,可以通过证明两者互为子集即可。 证明:.∈ (R..S ) -1,则有: ∈ (R..S ) -1 .∈R..S ..c(∈R∧∈S ) ..c(∈S-1∧∈R-1 ) .∈S-1..R-1 所以(R..S )-1=S-1..R-1。 5.4　关系的性质 5.4.1　自反性与反自反性 定义5-9 设关系R 是集合A 上的关系,如果对集合中的任意元素a∈A ,都有 ∈R,称关系R 满足自反性;如果对集合中的任意元素a,都有.R,称 关系满足反自反性。形式化如下: (1).a∈A ,都有∈R,则R 在A 上是自反的; (2).a∈A ,都有.R,则R 在A 上是反自反的。 例如,A 上的全域关系EA 、恒等关系IA 都是A 上的自反关系。小于等于关系、整除 关系和包含关系都是给定集合上的自反关系。而小于关系和真包含关系都是给定集合 上的反自反关系。 例5.12 设集合A = {a,b,c,d},在该集合上定义如下关系: 第5 章　关系 95 R = {(a,a),(a,b),(b,b),(c,c),(c,a),(d,d)} 试判断该关系是否满足自反性。 解:R 关系图如图5-4所示。 图5-4 R 的关系图 从关系图上看,如果每个元素都有指向自身的回路,则关系满足自反性;如果每个元 素都没有指向自身的回路,则关系满足反自反性。显然,上述关系R 每个元素都有指向 自身的回路,因此R 满足自反性。 R 矩阵表示如下: MR = 1 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 é . êêêêêê ù . úúúúúú 从矩阵上看,如果对角线全为1,则关系满足自反性,显然R 满足自反性。 例5.13 设集合A = {a,b,c,d},在该集合上定义如下关系: R = {(b,a),(a,b),(b,c),(c,d),(c,a)} 试判断该关系是否满足自反性。 解:关系图如图5-5所示。 图5-5 R 的关系图 如果每个元素都没有指向自身的回路,则关系满足反自反性。显然,上述关系R 每 个元素都没有指向自身的回路,因此R 满足反自反性。 R 的矩阵图如下: