二元关系的复合运算
定理3-6.2 设X，Y，Z，W是集合，RX×Y，SY×Z，T Z×W，则 (RS)T= R(ST) 证明：<x,w>∈(RS)T(z)(<x,z>∈RS∧<z,w>∈T) (z)((y)(<x,y>∈R∧<y,z>∈S)∧<z,w>∈T) (z)(y)((<x,y>∈R∧<y,z>∈S)∧<z,w>∈T) (y)(z)(<x,y>∈R∧(<y,z>∈S∧<z,w>∈T)) (y)(<x,y>∈R∧(z)(<y,z>∈S∧<z,w>∈T)) (y)(<x,y>∈R∧<y,w>∈ST)<x,w>∈R(ST) 所以 (RS)T=R(ST)
二元关系的复合运算
定义3-6.2 设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义 为： ⑴ R0=IA ⑵ Rn+1= RnR 由定义3-6.2可以看出，A上的任何二元关系的0次幂都相等，等于 A上的恒等关系IA。由定义3-6.2还可以看出： R1= R0 R=IAR=R R2= R1R= RR R3= R2R=(RR)R …… 因为复合运算满足结合律，所以R3又可以写成： n个R的复合 R3= RRR R 同样的道理Rn也可以写成： Rn= R R
MR=
例中的二元关系R是A上的二元关系， 只需看成A到A的二元关系，利用上述 定义，就可以方便地写出它的关系矩 阵。A上的二元关系和A到B的二元关 系的关系矩阵的定义是相同的。
二元关系的表示
4.用图表示二元关系 如果A和B是有限集，R是A到B二元关系，还可 以用图表示二元关系R。表示二元关系R的图叫 做R的关系图。A到B二元关系的关系图和A上的 二元关系的关系图的定义是不一样的。分别描 述如下：
二元关系的表示
例6 设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关 系，定义为： R=<a1,b1>,<a1,b3>,<a2,b2>,<a2,b3>, <a3,b1>,<a4,b1>,<a4,b2> 写出R的关系矩阵。 解: R的关系矩阵为：
MR= 1 0 1 1 0 1 0 1 1 1 0 0
二元关系的复合运算
例如,在例4.6中 R2=RR=<1,2>,<2,2> S2 =SS=<4,5>,<3,3>,<1,1> R3=RRR=<1,2>,<2,2> 定理3-6.5 设A是具有n个元素的有限集，R是A上的二元关系，则必存在 n2 自然数s和t，使得Rs=Rt，0≤s＜t≤2 。
… 证明：R是A上的二元关系，对任何自然数k，由复合关系的定义知，Rk 仍然是A上的二元关系，即RkA×A。另一方面，根据定理4.1.1， n2 A上的二元关系仅有2 种。列出R的各次幂R0，R1， 2 2 2 n，共有2 n＋1个，必存在自然数s和t，使得Rs=Rt， 2 ，…， R R2 0≤s＜t≤2 n 。
二元关系的复合运算
定理3-6.3 设R是A上的二元关系，RIA=IAR=R 证明：先证RIA=R <x,y>∈RIA(z)(<x,z>∈R∧<z,y>∈IA) (z)(<x,z>∈R∧z=y)<x,y>∈R 所以 RIAR <x,y>∈R<x,y>∈R∧<y,y>∈IA<x,y>∈RIA 所以 RRIA 故 RIA=R 类似的，可以证明IAR= R
二元关系的表示
1.用列举法表示二元关系 例4 设A=a,b，B=1,2， A到B的全域关系：E=A×B=<a,1>,<a,2>,<b,1>,<b,2> A上的恒等关系： IA=<a,a>,<b,b> 都是用列举法表示的。 2.用描述法表示二元关系 例5 设R是实数集， LR = <x,y>|x∈R∧y∈R∧x≤y， LR是实数集R上的二元关系。
3
H=<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<3,1>,<4,4>,<4,2>
二元关系的复合运算
定义3-6.1 设X，Y，Z是集合，RX×Y，SY×Z，集合 <x,z>x∈X∧z∈Z∧(y)(y∈Y∧<x,y>∈R∧<y,z>∈S) 叫做R和S的复合关系。记为RS,RSX×Z, RS是X到Z的二元关系。 例2 X=1,2,3,4,5，X上的二元关系R和S定义如下： R=<1,2>,<3,4>,<2,2> S=<4,2>,<2,5>,<3,1>,<1,3> 试求RS，SR，R(SR)，(RS)R，RR，SS，RRR 解: RS=<1,5>,<3,2>,<2,5>； SR=<4,2>,<3,2>,<1,4> (RS)R=<3,2>； R(SR)=<3,2> RR=<1,2>,<2,2>； SS=<4,5>,<3,3>,<1,1> RRR =<1,2>,<2,2> 可以看出,RS≠SR,这说明,二元关系的复合运算不满足交换律。
二元关系的复合运算
例 A= 1,2,3,4，A上的二元关系R定义如下： R=<1,2>,<2,1>,<2,3>,<3,4> 求二元关系R的各次幂，验证定理4.2.5。 解：|A|=4 R0=IA=<1,1>,<2,2>,<3,3>,<4,4> R1=R=<1,2>,<2,1>,<2,3>,<3,4> R2=R1 R= RR=<1,1>,<1,3>,<2,2>,<2,4> R3= R2R =<1,2>,<2,1>,<2,3>,<1,4> R4=R3 R=<1,1>,<1,3>,<2,2>,<2,4>=R2， 2 0≤2＜4≤216=2 4 R5=R4R=R2R=R3 R6=R5R=R3R=R4= R2 …… R2n=R2 R2n+1=R3, n =1,2,3,…
二元关系的复合运算
定理3-6.6设R是A上的二元关系，m，n为自然数，则 ⑴ RmRn =Rm+n ⑵ (Rm)n=Rmn 证明: ⑴ 对任意给定的m∈N，关于n进行归纳证明： 当n=0时，Rm R0=Rm IA=Rm=Rm+0 设n=k时，RmRk=Rm+k。下证n=k+1时，结果也对。 RmRk+1=Rm(RkR)=(RmRk)R=Rm+kR= Rm+k+1 ⑵ 对任意给定的m∈N，关于n进行归纳证明： 当n=0时，(Rm)0=IA=R0=Rm×0 设n=k时，(Rm)k=Rmk。下证n=k+1时，结果也对。 (Rm)k+1=(Rm)k Rm=RmkRm=Rmk+m=Rm(k+1)
关系的运算
例1 设X=1,2,3,4，X上的二元关系H和S定义如下，试求 H∪S，H∩S， ~H，S-H。 H=<x,y> | x y 是整数
2
S=<x,y> | x y 是正整数 解: 将H和S用列举法表示： S=<4,1> H∪S=<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<3,1>,<4,4>,<4,2>,<4,1> H∩S = φ ~H=X2-H=<1,2>,<1,4>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>,<4,1> S－H=<4,1>
二元关系的复合运算
定理3-6.4 设R，S，T是A上的二Байду номын сангаас关系, 则 ⑵ (R∪S)T=RT∪ST ⑷ (R∩S)TRT∩ST ⑴ R(S∪T)=RS∪RT; ⑶ R(S∩T)RS∩RT;
证明：仅证明⑶，类似地可证明⑴、⑵和⑷。 <x,y>∈R(S∩T)(z)(<x,z>∈R∧<z,y>∈S∩T) (z)(<x,z>∈R∧(<z,y>∈S∧<z,y>∈T)) (z)((<x,z>∈R∧<z,y>∈S)∧(<x,z>∈R∧<z,y>∈T)) (z)(<x,z>∈R∧<z,y>∈S)∧(z)(<x,z>∈R∧<z,y>∈T) <x,y>∈RS∧<x,y>∈RT <x,y>∈RS∩RT 故 R(S∩T)RS∩RT
A到B二元关系的关系图
⑴ A到B二元关系R的关系图 设A=a1,a2,…,am，B=b1,b2,…,bn，R是A到B二元 关系，R的关系图的绘制方法如下： ① 画出m个小圆圈表示A的元素，再画出n个小圆圈表示 B的元素。这些小圆圈叫做关系图的结点(下同)。 ② 如果<ai,bj >∈R，则从ai到bj 画一根有方向(带箭头)的线。这些 有方向(带箭头)的线叫做关系图的 边(下同)。