第 4章 二元关系第 4章 二元关系
4.1 二元关系及其表示
4.2 关系的运算
4.3 关系的性质
4.4 关系的闭包运算
4.5 等价关系
4.6 相容关系
4.7 序关系返回总目录第 4章 二元关系第 4章 二元关系
4.1二元关系及其表示
4.1.1二元关系的概念定义 4.1.1设 A和 B是任意集合,如果 R?A× B,则称 R是
A到 B的二元关系 。 如果 R是 A到 A的二元关系,则称 R是 A上的二元关系 。
设 A=?1,2,3?,B=?a,b?,R=1,a?,?2,a?,?3,b。 R是 A
到 B的二元关系 。 S=3,1?,?2,2?,?2,1?,?1,1。 S是 A上的二元关系 。
定义 4.1.2设 A和 B是任意集合,R?A× B,若?x,yR，
则称 x与 y有 R关系 。 记为 xRy。 若?x,yR,则称 x与 y没有 R
关系 。 记为 x y。R?
第 4章 二元关系如果 R是 A到 B的二元关系,根据定义 4.1.2,?x,yR与
xRy,?x,yR与 x y的意义相同 。
定义 4.1.3设 A和 B是任意集合,空集?叫做 A到 B的空关系,仍然记为?。 A,B的笛卡尔积 A× B叫做 A到 B的全域关系,记为 E。 集合a,a?|a?A?叫做 A上的恒等关系 。 记为 IA。
【 例 4.1】 设 A=?a,b?,B=?1,2?,求 A上的恒等关系 IA和
A到 B的全域关系 A× B。
解,A上的恒等关系 IA=a,a?,?b,b,A到 B的全域关系
E =A× B=a,1?,?a,2?,?b,1?,?b,2
定理 4.1.1设 A是具有 n个元素的有限集,则 A上的二元关系有 2n2种 。
证明,设 A为具有 n个元素的有限集,即 |A|=n,由排列组合原理知 |A× A|=n2。 根据定理 3.1.2有 |P (A× A) |=2|A× A|=2,
即 A× A的子集有 2 个 。 所以具有 n个元素的有限集 A上有 2 种二元关系 。
2n 2n
2n
R?
第 4章 二元关系
4.1.2二元关系的表示
1.用列举法表示二元关系例 4.1中的 A到 B的全域关系
E=A× B=a,1?,?a,2?,?b,1?,?b,2
A上的恒等关系
IA=a,a?,?b,b
都是用列举法表示的 。
2.用描述法表示二元关系设 R是实数集,LR=x,y? | x?R∧ y?R∧ x≤ y?,LR是实数集 R上的二元关系 。
第 4章 二元关系
3.用矩阵表示二元关系如果 A,B是有限集,
A=?a1,a2,?,am?，
B=?b1,b2,?,bn?，
R是 A到 B的二元关系,R的关系矩阵定义为：
MR= m?n
R
R
b
b
a
ar
j
j
i
i
ij?
,
,
0
1
i=1,?,m j=1,?,n
称为二元关系 R的关系矩阵 。
ijr
第 4章 二元关系
【 例 4.3】 设 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=
011
001
110
101
第 4章 二元关系
【 例 4.4】 设 A=?1,2,3,4?,R是 A的二元关系,定义为：
R=1,1?,?1,2?,?2,1?,?3,2?,?3,1?,?4,3?,?4,2?,?4,1
写出 A上二元关系 R的关系矩阵 。
解,R的关系矩阵为：
MR=
0111
0011
0001
0011
例 4.4中的二元关系 R是 A上的二元关系,只需看成 A
到 A的二元关系,利用上述定义,就可以方便地写出它的关系矩阵 。 A上的二元关系和 A到 B的二元关系的关系矩阵的定义是相同的 。
第 4章 二元关系
4.用图表示二元关系如果 A和 B是有限集,R是 A到 B二元关系,还可以用图表示二元关系 R。 表示二元关系 R的图叫做 R的关系图 。 A到 B二元关系的关系图和 A上的二元关系的关系图的定义是不一样的 。 分别描述如下：
⑴ A到 B二元关系 R的关系图设 A=?a1,a2,?,am?,B=?b1,b2,?,bn?,R是 A到 B二元关系,R的关系图的绘制方法如下：
① 画出 m个小圆圈表示 A的元素,再画出 n个小圆圈表示 B的元素 。 这些小圆圈叫做关系图的结点 (下同 )。
②如果?ai,bjR，则从 ai到 bj画一根有方向 (带箭头 )的线。这些有方向 (带箭头 )的线叫做关系图的边
(下同 )。
第 4章 二元关系例 4.3中的二元关系 R的关系图如图 4.1。
⑵ A上的二元关系 R的关系图设 A=?a1,a2,?,am?,R是 A上的二元关系,其关系图如下绘制：
① 画出 m个小圆圈表示 A的元素 。
② 如果?ai,ajR,则从 ai到 aj画一根有方向 (带箭头 )
的线 。
例 4.4中的二元关系 R的关系图如图 4.2。
返回章目录第 4章 二元关系
4.2关系的运算定义 4.2.1设 A,B是集合,R?A× B。
dom R=?x|?x,yR? 叫做 R的定义域 。
ran R=?y|?x,yR?叫做 R的值域 。
FLD R= dom R∪ ran R叫做 R的域 。
A叫做 R的前域； B叫做 R的陪域 。
4.2.1二元关系的交,并,补,对称差运算定理 4.2.1设 R,S是 X到 Y的二元关系,则 R∪ S,R∩S，
R-S,~R,R S也是 X到 Y的二元关系 。
证明,因为 R,S是 X到 Y的二元关系,所以,
R?X× Y且 S?X× Y。 显然,
R∪ S?X× Y,即 R∪ S是 X到 Y的二元关系 。
R∩ S?X× Y,即 R∩ S是 X到 Y的二元关系 。
R-S?X× Y,即 R-S是 X到 Y的二元关系 。
第 4章 二元关系在二元关系运算中,认为全域关系是全集 。 所以
~R= X× Y-R?X× Y,即 ~R是 X到 Y的二元关系 。
由以上结论可以得到：
(R－ S)?X× Y和 (S－ R)?X× Y,从而
(R－ S)∪ (S－ R)?X× Y,所以
R S=(R－ S)∪ (S－ R)?X× Y,即 R S是 X到 Y的二元关系 。
【 例 4.5】 设 X=?1,2,3,4?,X上的二元关系 H和 S定义如下：
H=x,y? | 是整数?
S=x,y? | 是正整数?
试求 H∪ S,H∩ S,~H,S-H
2
yx?
3yx?
第 4章 二元关系解,将 H和 S用列举法表示：
H=1,1?,?1,3?,?2,2?,?2,4?,?3,3?,?3,1?,?4,4?,?4,2
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
4.2.2二元关系的复合运算定义 4.2.2 设 X,Y,Z是集合,R?X× Y,S?Y× Z,集合
x,zx?X∧ z?Z∧ (?y)(y?Y∧?x,yR∧?y,zS)?
叫做 R和 S的复合关系 。 记为 R°S,R°S?X× Z,即 R°S是 X到
Z的二元关系 。
第 4章 二元关系
【 例 4.6】 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
试求 R°S,S°R,R°(S°R),(R°S)°R,R°R,S°S,R°R°R
解,R°S=1,5?,?3,2?,?2,5
S°R=4,2?,?3,2?,?1,4
(R°S)°R=3,2
R°(S°R)=3,2
R°R=1,2?,?2,2
S°S=4,5?,?3,3?,?1,1
R°R°R =1,2?,?2,2
从例 4.6可以看出,R°S≠ S°R，这说明，二元关系的复合运算不满足交换律。
第 4章 二元关系定理 4.2.2 设 X,Y,Z,W是集合,R?X× Y,S?Y× Z，
T? Z× W,则 (R°S)°T= R°(S°T)
证明,?x,w(R°S)°T?(?z)(?x,zR°S∧?z,wT)
(?z)((?y)(?x,yR∧?y,zS)∧?z,wT)
(?z)(?y)((?x,yR∧?y,zS)∧?z,wT)
(?y)(?z)(?x,yR∧ (?y,zS∧?z,wT))
(?y)(?x,yR∧ (?z)(?y,zS∧?z,wT))
(?y)(?x,yR∧?y,wS°T)x,wR°(S°T)
所以 (R°S)°T=R°(S°T)
第 4章 二元关系定理 4.2.3 设 R是 A上的二元关系,R°IA=IA°R=R
证明,先证 R°IA=R
x,yR°IA?(?z)(?x,zR∧?z,yIA)
(?z)(?x,zR∧ z=y)x,yR
所以 R°IA?R
x,yRx,yR∧?y,yIAx,yR°IA
所以 R?R°IA
故 R°IA=R
类似的,可以证明 IA°R= R
第 4章 二元关系定理 4.2.4 设 R,S,T是 A上的二元关系,则
⑴ R°(S∪ T)=R°S∪ R°T
⑵ (R∪ S)°T=R°T∪ S°T
⑶ R°(S∩ T)?R°S∩ R°T
⑷ (R∩ S)°T?R°T∩ S°T
证明,仅证明 ⑶,类似地可证明 ⑴,⑵ 和 ⑷ 。
x,yR°(S∩ T)?(?z)(?x,zR∧?z,yS∩ T)
(?z)(?x,zR∧ (?z,yS∧?z,yT))
(?z)((?x,zR∧?z,yS)∧ (?x,zR∧?z,yT))
(?z)(?x,zR∧?z,yS)∧ (?z)(?x,zR∧?z,yT)
x,yR°S∧?x,yR°T
x,yR°S∩ R°T
故 R°(S∩ T)?R°S∩ R°T
第 4章 二元关系一般地说,R°S∩ R°T?R°(S∩ T),举反例如下：
设 A=?1,2,3,4,5?
R=4,1?,?4,2A× A
S=1,5?,?3,5A× A
T=2,5?,?3,5A× A
R°S∩ R°T =4,5∩4,5=4,5
R°(S∩ T) =4,1?,?4,2°3,5=?
R°S∩ R°T?R°(S∩ T)
定理 4.2.4的 ⑴ 说明,关系的复合运算,°” 对并运算
,∪,满足左分配律 。 ⑵ 说明,关系的复合运算,°”
对并运算,∪,满足右分配律 。 所以,复合运算,°”
对并运算,∪,满足分配律 。 由 ⑶ 和 ⑷ 知,复合运算
,°” 对交运算,∩,不满足分配律 。
第 4章 二元关系定义 4.2.3 设 R是 A上的二元关系,n为自然数,R的 n次幂记为 Rn,定义为：
⑴ R0=IA
⑵ Rn+1= Rn°R
由定义 4.2.3可以看出,A上的任何二元关系的 0次幂都相等,等于 A上的恒等关系 IA。 由定义 4.2.3还可以看出：
R1= R0 °R=IA°R=R
R2= R1°R= R°R
R3= R2°R=(R°R)°R
因为复合运算满足结合律,所以 R3又可以写成：
R3= R°R°R
同样的道理 Rn也可以写成,Rn= 的复合个 Rn RRR
第 4章 二元关系例如,在例 4.6中
R2=R°R=1,2?,?2,2
S2 =S°S=4,5?,?3,3?,?1,1
R3=R°R°R=1,2?,?2,2
定理 4.2.5设 A是具有 n个元素的有限集,R是 A上的二元关系,则必存在自然数 s和 t,使得 Rs=Rt,0≤ s＜ t≤ 2 。
证明,R是 A上的二元关系,对任何自然数 k,由复合关系的定义知,Rk仍然是 A上的二元关系,即 Rk?A× A。 另一方面,根据定理 4.1.1,A上的二元关系仅有 2 种 。 列出 R的各次幂 R0,R1,R2,?,,共有 2 ＋ 1个,必存在自然数 s和 t,使得 Rs=Rt,0≤ s＜ t≤ 2 。2n
2n
2n
22nR
2n
第 4章 二元关系
【 例 4.7】 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= R°R=1,1?,?1,3?,?2,2?,?2,4
R3= R2°R =1,2?,?2,1?,?2,3?,?1,4
R4=R3°R=1,1?,?1,3?,?2,2?,?2,4=R2，
0≤ 2＜ 4≤ 216=2
R5=R4°R=R2°R=R3
R6=R5°R=R3°R=R4= R2
R2n=R2
R2n+1=R3,n =1,2,3,?
24
第 4章 二元关系定理 4.2.6设 R是 A上的二元关系,m,n为自然数,则
⑴ Rm°Rn =Rm+n
⑵ (Rm)n=Rmn
证明,⑴ 对任意给定的 m?N,关于 n进行归纳证明：
当 n=0时,Rm °R0=Rm°IA=Rm=Rm+0
设 n=k时,Rm°Rk=Rm+k。 下证 n=k+1时,结果也对 。
Rm°Rk+1=Rm°(Rk°R)=(Rm°Rk)°R=Rm+k°R= 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=Rmk°Rm=Rmk+m=Rm(k+1)
设 X,Y,Z是集合,R?X× Y,S?Y× Z,R°S是 R和 S的复合关系,R°S?X× Z,它们的关系矩阵分别是 MR,MS和 MR°S。
以下研究这三个矩阵之间的关系 。
第 4章 二元关系设 X=?x1,x2,?,xm?,Y=?y1,y2,?,yn?,Z=?z1,z2,?,zP?
R?X× Y,S?Y× Z,R°S?X× Z
MR= m?n
i=1,?,m,j=1,?,n
MS= n?p
i=1,?,n,j =1,?,p
MR°S= m?p
i=1,?,m,j =1,?,p
iju RRyyxxu
j
j
i
i
ij?
,
,
0
1
ijv SSzzyyv
j
j
i
i
ij?
,
,
0
1
ijw
S
S
R
R
z
z
x
xw
j
j
i
i
ij?
,
,
0
1
第 4章 二元关系与,有如下的关系：
= i=1,?,m,j=1,?,p
将上述关系用矩阵符号记为：
MR ° S=MR °MS,其中,i=1,?,m,j =1,?,p
矩阵运算,°” 叫做关系矩阵 MR和 MS的布尔乘法 。
把关系矩阵的布尔乘法公式
= i=1,?,m,j =1,?,p
与线性代数中的矩阵乘法公式相比,发现,只要把矩阵乘法公式中的数乘改为合取,把数加改为析取,就得到了关系矩阵的布尔乘法公式 。
)(1 kjiknk vuijw
ijw )(1 kjik
n
k vu
ijw iju ijv
第 4章 二元关系
【 例 4.8】 A=?1,2,3,4,5?,A上的二元关系 R和 S定义如下：
R=1,2?,?2,2?,?3,4
S=1,3?,?2,5?,?3,1?,?4,2
试求 MR ° S和 MR °MS,它们是否相等?
解,按照 R 和 S的定义,求出
R°S=1,5?,?3,2?,?2,5
写出 R,S和 R ° S关系矩阵如下：
MR= MS= MR ° S=
00000
00000
01000
00010
00010
00000
00010
00001
10000
00100
00000
00000
00010
10000
10000
第 4章 二元关系
MR °MS= ° =
所以 MR ° S=MR °MS
4.2.3二元关系的求逆运算定义 4.2.4 设 X,Y是集合,R?X× Y,集合
y,xx,yR?
叫做 R的逆关系 。 记为 RC,RC?Y× X,RC是 Y到 X的二元关系 。
容易证明,RC的关系矩阵 是 R的关系矩阵 MR的转置矩阵,即 =MRT
可以验证,将 R关系图中的弧线的箭头反置,就可以得到
RC关系图 。
00000
00000
01000
00010
00010
00000
00010
00001
10000
00100
00000
00000
00010
10000
10000
CRM
CRM
第 4章 二元关系
【 例 4.9】 设 X=?1,2,3,4?,Y=?a,b,c?,X到 Y二元关系
R=1,a?,?2,b?,?4,c，
⑴ 试求 RC,写出 MR和,验证 =MRT
⑵ 画出 R和 RC的关系图,验证将 R关系图中的弧线的箭头反置可得到 RC关系图 。
解,RC=a,1?,?b,2?,?c,4
R和 RC的关系矩阵是：
MR= =
显然,=MRT
100
000
010
001
CRM
1000
0010
0001
CRM
CRM CRM
第 4章 二元关系
R和 RC的关系图分别是图 4.3和图 4.4,它们中的弧线的方向是相反的 。
第 4章 二元关系定理 4.2.7设 X,Y是集合,R?X× Y,则
⑴ (RC )C= R
⑵ dom RC= ran R,ran RC= dom R
证明,⑴?x,yRy,xRCx,y(RC)C
所以 (RC )C= R
⑵ x?dom RC?(?y)(?x,yRC)?(?y)(?y,xR)
x?ran R
所以 dom RC= ran R
类似的可以证明 ran RC= dom R
第 4章 二元关系定理 4.2.8设 X,Y是集合,R,S是 X到 Y的二元关系，则
⑴ (R∪ S)C = RC∪ SC
⑵ (R∩ S)C =RC∩ SC
⑶ (A× B)C=B× A
⑷ (~R) C =~ (R C)
⑸ (R-S)C =RC-SC
证明,⑴
x,y(R∪ S)Cy,xR∪ Sy,xR∨?y,xS
x,yRC∨?x,ySCx,yRC∪ SC
所以 (R∪ S)C =RC∪ SC
类似⑴可证明⑵和⑶。
⑷?x,y(~R)Cy,x~Ry,xRy,xR
x,yRCx,yRCx,y~ (RC)
所以 (~R) C =~(R C)
第 4章 二元关系返回章目录
⑸ 利用 ⑴,⑵ 和 ⑷ 证明：
(R-S)C=(R∩ ~S)C=RC∩ (~S)C=RC∩ ~(SC)=RC-SC
定理 4.2.9设 X,Y,Z是集合,R?X× Y,S?Y× Z,则
(R°S)C=SC°RC
证明：
z,x(R°S)Cx,z(R°S)
(?y)(?x,yR∧?y,zS)
(?y)(?y,xRC∧?z,ySC)
(?y)(?z,ySC∧?y,xRC)
z,xSC°RC
所以 (R°S)C=SC°RC
第 4章 二元关系
4.3 关系的性质定义 4.3.1 设 R?X× X,(?x)(x?X→?x,xR),则称 R在 X
上是自反的 。
设 R是 X上的自反关系,由定义 4.3.1知,R的关系矩阵 MR
的主对角线全为 1；在关系图中每一个结点上都有自回路 。
设 X=?1,2,3?,X上的二元关系
R=1,1?,?2,2?,?3,3?,?1,2
R是自反的,它的关系图如图 4.5所示,关系矩阵如下：
MR=
100
010
011
第 4章 二元关系定理 4.3.1 设 R是 X上的二元关系,R是自反的当且仅当
IX?R。
证明,设 R在 X上是自反的,下证 IX?R。
x,yIX?x=yx,yR,即 IX?R。
设 IX?R,下证 R在 X上是自反的 。
x?Xx,xIXx,xR,即 R在 X上是自反的 。
定义 4.3.2 设 R?X× X,(?x)(x?X→?x,xR),则称 R在 X
上是反自反的 。
设 R是 X上的反自反关系,由定义 4.3.2可知,R的关系矩阵 MR的主对角线全为 0；在 R的关系图中每一个结点上都没有自回路 。
设 X=?1,2,3?,X上的二元关系 R=1,2?,?2,3?,?3,1,R
是反自反的,它的关系图如图 4.6所示,关系矩阵如下：
第 4章 二元关系
MR =
001
100
010
【 例 4.11】 设 R是实数集合,
＞ =x,y?| x?R∧ y?R∧ x＞ y?
是实数集合上的大于关系 。 证明实数集合上的大于关系是反自反的 。
证明,?x?R,x≯ x,?x,x＞,所以＞是反自反的 。
第 4章 二元关系定理 4.3.2 设 R是 X上的二元关系,R是反自反的当且仅当 R∩ IX=?。
证明,设 R在 X上是反自反的,下证 R∩ IX=?。
假设 R∩ IX≠?
必存在?x,yR∩ IXx,yR∧?x,yIXx,yR∧
x=y,即?x,xR,这与 R是 X上的反自反关系相矛盾 。 所以
R∩ IX=?。
设 R∩ IX=?,下证 R在 X上是反自反的 。
任取 x?X
x,xIX，由于 R∩ IX=?，必然?x,xR，即 R在 X上是反自反的。
第 4章 二元关系
【 例 4.12】 设 A=?1,2,3?,定义 A上的二元关系如下：
R=1,1?,?2,2?,?3,3?,?1,3
S=1,3
T=1,1
试说明 R,S,T是否是 A上的自反关系或反自反关系 。
解,因为?1,1?,?2,2?和?3,3?都是 R的元素,所以 R
是 A上的自反关系,不是反自反关系 。 因为?1,1?,?2,2?
和?3,3?都不是 S的元素,所以 S是反自反关系,不是 A上的自反关系 。 因为?2,2T,所以 T不是 A上的自反关系 。
因为?1,1T,所以 T不是 A上的反自反关系 。
第 4章 二元关系定义 4.3.3 设 R?X× X,(?x)(?y)(x?X∧ y?X∧?x,yR
→?y,xR),则称 R在 X上是对称的 。
R是 X上的对称关系,由定义 4.3.3知,R的关系矩阵 MR
是对称阵 。 在 R的关系图中,如果两个不同的结点间有边,
一定有方向相反的两条边 。
设 X=?1,2,3?,X上的二元关系 R=1,2?,?2,1?,?3,3，
R是对称的 。 它的关系图如图 4.7所示,关系矩阵如下：
MR=
100
001
010
第 4章 二元关系
【 例 4.13】 设 A=?1,3,5,7?,定义 A上的二元关系如下：
R=a,b?|(a－ b)/2是整数?
试证明 R在 A上是自反的和对称的 。
证明,?a?A,(a-a)/2=0,0是整数,所以?a,aR。 即
R是自反的 。
a?A,?b?A,?a,bR,(a-b)/2是整数,因为整数的相反数也是整数,所以 (b-a)/2=-(a-b)/2是整数,?b,aR。
即 R是对称的 。
定理 4.3.3 设 R是 X上的二元关系,R是对称的当且仅当
R=RC。
证明,设 R是对称的,下证 R =RC。
x,yRy,xRx,yRC,所以 R =RC。
设 R =RC,下证 R是对称的 。
x,yRy,xRCy,xR,所以 R是对称的 。
第 4章 二元关系定义 4.3.4 设 R?X× X，
(?x)(?y)(x?X∧ y?X∧?x,yR∧?y,xR→ (x=y))
则称 R在 X上是反对称的 。
x,yR∧?y,xR→ (x=y)
(x=y)→?(?x,yR∧?y,xR)
(x=y)→ (?x,yR∨?y,xR)
((x=y)∨?x,yR)∨?y,xR
((x≠ y)∧?x,yR)∨?y,xR
(x≠ y)∧?x,yR→?y,xR
x,yR∧ (x≠ y)→?y,xR
由此,反对称的定义又可以等价的描述为：
(?x)(?y)(x?X∧ y?X∧?x,yR∧ (x≠ y)→?y,xR)
第 4章 二元关系设 R是 X上的反对称关系,由定义 4.3.4知,在 R的关系矩阵 MR中以主对角线为轴的对称位置上不能同时为 1(主对角线除外 )。 在 R的关系图中每两个不同的结点间不能有方向相反的两条边 。
设 X=?1,2,3?,X上的二元关系 R=1,2?,?2,3?,?3,3，
R是反对称的 。 它的关系图如图 4.8所示,关系矩阵如下：
MR=
100
100
010
第 4章 二元关系
【 例 4.14】 设 A=?1,2,3?,定义 A上的二元关系如下：
R=1,1?,?2,2
S=1,1?,?1,2?,?2,1
T=1,2?,?1,3
U=1,3?,?1,2?,?2,1
试说明 R,S,T,U是否是 A上的对称关系和反对称关系 。
解,R是 A上的对称关系,也是 A上的反对称关系 。
S是 A上的对称关系 。 因为?1,2?和?2,1?都是 S元素,而
1≠ 2,所以 S不是 A上的反对称关系 。
因为?1,2T,而?2,1T,所以 T不是 A上的对称关系 。
T是 A上的反对称关系 。
U不是 A上的对称关系,也不是 A上的反对称关系 。
第 4章 二元关系定理 4.3.4设 R是 X上的二元关系,则 R是反对称的当且仅当 R∩ RC?IX。
证明,设 R是反对称的,下证 R∩ RC?IX。
x,yR∩ RCx,yR∧?x,yRC
x,yR∧?y,xR
因为 R 是反对称的,所以 y=x,?x,y?=?x,x?=?y,yIX,故
R∩ RC?IX
设 R∩ RC?IX,下证 R是反对称的 。
x,yR∧?y,xRx,yR∧?x,yRC
x,yR∩ RC
因为 R∩ RC?IX,所以?x,yIX,故 x=y,R是反对称的 。
定义 4.3.5 设 R?X× X，
(?x)(?y)(?z)(x?X∧ y?X∧ z?X∧?x,yR∧?y,zR
→?x,zR)
则称 R在 X上是传递的 。
第 4章 二元关系
【 例 4.15】 设 R是实数集合,
S=x,y?|x?R∧ y?R∧ x=y?
是实数集合上的等于关系 。 证明实数集合上的等于关系是传递的 。
证明,?x?R,?y?R,?z?R,?x,yS且?y,zS,由
S的定义有 x=y和 y=z,由实数相等的概念得 x=z。 再根据 S的定义,?x,zS。 故实数集合上的等于关系 S是传递的 。
定理 4.3.5 设 R是 X上的二元关系,R是传递的当且仅当
R°R?R。
证明,设 R是传递的,下证 R°R?R。
x,yR°R,?z?X,使得?x,zR且?z,yR,又因为 R是传递的,所以?x,yR,这就证明了 R°R?R。
设 R°R?R,下证 R是传递的 。
x,yR且?y,zR,由复合关系的定义得?x,z R°R,因为 R°R?R,所以?x,zR,所以 R是传递的 。
第 4章 二元关系上述的 5个定理,可以作为相应概念的定义使用,用来判断和证明关系的性质 。 有些问题用这 5个定理处理是非常方便的 。 请看下面的例题 。
【 例 4.16】 设 R,S是 X上的二元关系,证明
⑴ 若 R,S是自反的,则 R∪ S和 R∩ S也是自反的 。
⑵ 若 R,S是对称的,则 R∪ S和 R∩ S也是对称的 。
⑶ 若 R,S是传递的,则 R∩ S也是传递的 。
证明,⑴ 设 R,S是自反的,由定理 4.3.1知,IX?R,IX?S，
所以 IX?R∪ S,IX?R∩ S,再由定理 4.3.1知,R∪ S和 R∩ S也是自反的 。
第 4章 二元关系
⑵ 设 R,S是对称的,由定理 4.3.3知,R=RC,S=SC,根据定理 4.2.8,R∪ S=RC∪ SC=(R∪ S)C,R∩ S=RC∩ SC=(R∩ S) C，
再由定理 4.3.3知,R∪ S和 R∩ S也是对称的 。
⑶ 设 R,S是传递的,由定理 4.3.5知,R°R?R,S°S?S，
据定理 4.2.4，
(R∩ S)°(R∩ S)?(R°R)∩ (R°S)∩ (S°R)∩ (S°S)
(R°R)∩ (S°S)?R∩ S
即 (R∩ S)°(R∩ S)?R∩ S,再由定理 4.3.5,R∩ S是传递的 。
以上研究了二元关系的 5个性质及其关系矩阵,关系图的特点,它们对今后的学习是重要的 。
返回章目录第 4章 二元关系
4.4关系的闭包运算定义 4.4.1 设 R?X× X,X上的二元关系 R′ 满足：
⑴ R′是自反的 (对称的，传递的 )。
⑵ R?R′。
⑶对 X上的任意二元关系 R′′，如果 R?R′′且 R′′是自反的
(对称的，传递的 )，就有 R′?R′′。
则称 R′是 R的自反 (对称，传递 )闭包。记为 r(R)(s(R),t(R))
定义 4.4.1的⑴和⑵的意思是自反 (对称，传递 )闭包 R′是包含 R的自反 (对称，传递 )关系；定义 4.4.1的⑶的意思是在所有包含 R的自反 (对称，传递 )关系中自反 (对称，传递 )闭包 R′
是最小的。所以，定义 4.4.1又可以描述为：包含 R的最小自反 (对称，传递 )关系是 R的自反 (对称，传递 )闭包。
传递闭包 t(R)有时也记为 R+，读作,R加,。传递闭包在语法分析中有很多重要的应用。
第 4章 二元关系当二元关系 R是自反 (对称，传递 )的时，求 R的自反 (对称，传递 )闭包方法由下面的定理给出了。
定理 4.4.1 设 R?X× X，则
⑴ R是自反的当且仅当 r(R)=R。
⑵ R是对称的当且仅当 s(R)=R。
⑶ R是传递的当且仅当 t(R)=R。
证明,仅证明⑴，其余留做练习。
设 R是自反的，下证 r(R)=R
令 R′=R
① R′=R,R是自反的，所以 R′是自反的。
②因为 R′=R，所以 R?R′。
③ R′′是 X上的任意自反关系且 R?R′′，因为 R′=R，所以
R′?R′′。
故 R′是 R的自反闭包。即 r(R)=R。
第 4章 二元关系设 r(R)=R，下证 R是自反的。
由自反闭包的定义知,R是自反的。
以下的几个定理给出了求二元关系 R的自反闭包、对称闭包和传递闭包的一般方法。
定理 4.4.2 设 R?X× X，则 r(R)=R∪ IX
证明,令 R′=R∪ IX
⑴ IX?R∪ IX，而 R∪ IX =R′，所以 IX?R′,R′是自反的。
⑵ R?R∪ IX，而 R∪ IX =R′，所以 R?R′
⑶ R′′是 X上的任意自反关系且 R?R′′，由于 R′′是自反的，
所以 IX?R′′，从而有 R′=R∪ IX?R′′。
根据自反闭包的定义,R′=R∪ IX是 R的自反闭包，即
r(R)=R∪ IX。
第 4章 二元关系定理 4.4.3 设 R?X× X，则 s(R)=R∪ RC
证明,令 R′=R∪ RC
⑴ (R′)C= (R∪ RC) C= RC∪ (RC)C= RC∪ R=R∪ RC=R′，所以 R′是对称的。
⑵ R?R∪ RC，而 R∪ RC =R′，所以 R?R′。
⑶ R′′是 X上的任意对称关系且 R?R′′，
x,yRCy,xRy,xR′′
x,yR′′(R′′是对称的 )，
所以 RC?R′′，从而有 R′=R∪ RC?R′′。 R′是 R的对称闭包，即
s(R)= R∪ RC。
定理 4.4.4 设 R?X× X，则 t(R)=R∪ R2∪ R3∪?
证明,先证 R∪ R2∪ R3∪t(R)
用数学归纳法证明,?i?I+ \ Ri?t(R)
第 4章 二元关系
① 当 i =1时，由传递闭包的定义,R1= R?t(R)。
② 设 i =n时,Rn?t(R)。下证 Rn+1?t(R)。
x,yRn+1?(?c)(?x,cRn∧?c,yR)
(?c)(?x,ct(R)∧?c,yt(R)) (① 和归纳假设 )
x,yt(R) (t(R)是传递的 )
即 Rn+1? t (R)
故 R∪ R2∪ R3∪t (R)
再证 t(R)?R∪ R2∪ R3∪?
显然 R?R∪ R2∪ R3∪?
以下证明 R∪ R2∪ R3∪? 是传递的。
x,yR∪ R2∪ R3∪? 且?y,zR∪ R2∪ R3∪?
t?I+使?x,yRt∧?s?I+ 使?y,zRs
x,zRt°Rs=Rt+s?R∪ R2∪ R3∪?
x,zR∪ R2∪ R3∪?
根据传递关系的定义,R∪ R2∪ R3∪? 是传递的。
第 4章 二元关系综上所述,R∪ R2∪ R3∪? 是包含 R的传递关系。而 R的传递闭包是包含 R的最小传递关系。所以
t(R)?R∪ R2∪ R3∪?
t(R)=R∪ R2∪ R3∪?
【 例 4.17】 设 A=?1,2,3?,定义 A上的二元关系 R为：
R=1,2?,?2,3?,?3,1
试求,r(R),s(R),t(R)
解,r(R)= R∪ IA=1,2?,?2,3?,?3,1?,?1,1?,?2,2?,?3,3
s(R)=R∪ RC=1,2?,?2,3?,?3,1?,?2,1?,?3,2?,?1,3
以下求 t(R)：
R2= R°R=1,3?,?2,1?,?3,2
R3= R2°R =1,1?,?2,2?,?3,3=IA
R4= R3°R = IA°R=R
继续这个运算，则有第 4章 二元关系
R= R4= R7=? =R3n+1=?
R2= R5= R8=? =R3n+2=?
R3= R6= R9=? =R3n+3=?
其中,n是任意的自然数。 t(R)=R∪ R2∪ R3∪?
t(R)= R∪ R2∪ R3
=1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?2,3?,
3,1?,?3,2?,?3,3
当 A是具有 n个元素的有限集时，由定理 4.2.5知，存在自然数 s和 t，使得 Rs=Rt,0≤ s＜ t≤ 2。于是
Rt+1=Rs+1,Rt+2=Rs+2,
即当 i≥ t,Ri就出现了重复。因为集合的并运算满足幂等律，
所以,t(R)=R∪ R2∪ R3∪? =R∪ R2∪ R3∪? ∪ R
这个结论还可以改善。
22n
第 4章 二元关系定理 4.4.5 设 |X|=n,R?X× X，则 t(R)= R∪ R2∪? ∪ Rn
证明,只需证明 t(R)?R∪ R2∪ R3∪? ∪ Rn
设?x,yt(R)=R∪ R2∪ R3∪?,由并集合的定义知，存在最小的正整数 k使得?x,yRk。下证 k≤ n。
设 k＞ n，根据复合关系的定义，存在 X中的元素序列：
x=a0,a1,a2,?,ak-1,ak=y，使 xRa1,a1Ra2,?,ak-1Rak(y)，
此序列中有 k+1个 X的元素,k+1＞ n+1＞ n。而 X中只有 n个元素，所以 a0,a1,a2,?,ak-1,ak中必有相同的元素，设 ai = aj，
0≤ i＜ j≤ k。去掉序列中 ai+1到 aj的所有元素，于是
xRa1,a1Ra2,?,ai-1Rai,ajRaj+1,?,ak-1Rak(y)
成立。即?x,yRs，其中 S=k-(j-i)。因为 j-i≥ 1，所以 S＜ k，
这与 k是使得?x,yRk的最小正整数的假设相矛盾。故 k≤ n。
所以 Rk?R∪ R2∪ R3∪? ∪ Rn，从而有
x,yR∪ R2∪ R3∪? ∪ Rn
t(R)?R∪ R2∪ R3∪? ∪ Rn
第 4章 二元关系显然,R∪ R2∪ R3∪? ∪ Rn?R∪ R2∪ R3∪? = t(R)，即
R∪ R2∪ R3∪? ∪ Rn?t(R)。
于是 t(R)=R∪ R2∪ R3∪? ∪ Rn
除了用关系的复合运算计算传递闭包外,还可以用关系矩阵求传递闭包 。 请看下列的例题 。
【 例 4.18】 设 A=?1,2,3?,定义 A上的二元关系 R为：
R=1,2?,?2,3?,?3,1试用关系矩阵求传递闭包 t(R)。
解：用 关系矩阵求 t(R)的方法如下：
001
100
010
RM
第 4章 二元关系
010
001
100
001
100
010
001
100
010
2 RRR MMM
100
010
001
001
100
010
010
001
100
23 RRR MMM
111
111
111
32)( RRRRt MMMM
其中,∨ 表示矩阵的对应元素进行析取运算 。
第 4章 二元关系定理 4.4.6设 R?X× X，则 (R∪ IX)n= (R∪ R2∪? ∪ Rn )∪ IX
证明,用数学归纳法证明：
当 n=2时，
(R∪ IX)2=(R∪ IX)(R∪ IX)=((R∪ IX)°R)∪ ((R∪ IX)°IX)
=(R°R)∪ (IX°R)∪ (R∪ IX)
=R2∪ R∪ R∪ IX=R2∪ R∪ IX=(R∪ R2)∪ IX
设 n=k时,(R∪ IX)k=(R∪ R2∪ R3∪? ∪ R k)∪ IX，
证明 n=k+1时,(R∪ IX)k+1=(R∪ R2∪? ∪ R k∪ R k+1)∪ IX
(R∪ IX)k+1=(R∪ IX)k°(R∪ IX)
=(R∪ R2∪ R3∪? ∪ R k∪ IX)°(R∪ IX)
=((R∪ R2∪ R3∪? ∪ R k∪ IX)°R)∪
((R∪ R2∪ R3∪? ∪ Rk∪ IX)°IX)
=(R2∪ R3∪? ∪ R k∪ R k+1∪ R)∪
(R∪ R2∪ R3∪? ∪ R k∪ IX)
=(R∪ R2∪ R3∪? ∪ R k∪ R k+1)∪ IX
第 4章 二元关系二元关系的闭包仍然是二元关系，还可以求它的闭包。
例如,R是 A上的二元关系,r(R)是它的自反闭包，还可以求
r(R)的对称闭包。 r(R)的对称闭包记为 s(r(R))，简记为 sr(R)，
读做 R的自反闭包的对称闭包。类似的,R的对称闭包的自反闭包 r(s(R))简记为 rs(R),R的对称闭包的传递闭包 t(s(R))，
简记为 ts(R),
通常用 R*表示 R的传递闭包的自反闭包 rt(R)，读作,R
星,。在研究形式语言和计算模型时经常使用 R*。
定理 4.4.7 设 R?X× X，则
⑴ rs(R)=sr(R)
⑵ rt(R)=tr(R)
⑶ st(R)?ts(R)
证明,⑴ rs(R)=r(s(R))=r(R∪ RC)=(R∪ RC)∪ IX
=(R∪ RC)∪ IX∪ IX=(R∪ IX)∪ (RC∪ IX)
=(R∪ IX)∪ (R∪ IX)C= s(R∪ IX)= sr(R)
第 4章 二元关系
⑵ tr(R)=t(r(R))= t(R∪ IX)
= =
=
= = t(R)∪ IX= rt(R)
⑶ 留给读者证明。
1
)(
i
i
XIR
1 1
)(
i X
i
j
j IR
1 11
)()(
i i X
i
j
j IR
Xi
i IR
1
返回章目录第 4章 二元关系
4.5 等价关系等价关系是最重要,最常见的二元关系之一 。 它有良好的性质 。 在计算机科学和计算机技术,信息科学和信息工程中都有广泛的应用 。 目前对等价关系的研究是深入而完备的 。 本节介绍等价关系的主要结论 。
定义 4.5.1 设 R?X× X,如果 R是自反的,对称的和传递的,则称 R是 X上的等价关系 。 设 R是等价关系,若
x,yR,称 x等价于 y。
因为等价关系是自反的和对称的，所以等价关系的关系矩阵主对角线全为 1且是对称阵；其关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边。
第 4章 二元关系
【 例 4.19】 设 A=?1,2,3,4,5?,R是 A上的二元关系,
R=1,1?,?1,2?,?2,1?,?2,2?,?3,3?,?3,4?,?4,3?,?4,4?,?5,5，
证明 R是 A上的等价关系 。
证明,写出 R的关系矩阵 MR如下：
MR的主对角线全为 1且是对称阵,所以 R是自反的和对称的；还可以用二元关系传递性的定义证明 R是传递的 。 故 R
是 A上的等价关系 。
10000
01100
01100
00011
00011
R
M
第 4章 二元关系也可以用关系图说明 R是等价关系 。 图 4.9是 R的关系图 。 在 R的关系图中每一个结点上都有自回路；每两个结点间如果有边,一定有方向相反的两条边 。 所以 R是自反的和对称的 。 与前面一样,
也可以用二元关系传递性的定义证明 R是传递的 。 故 R是 A上的等价关系 。
从图 4.9不难看出,等价关系 R
的关系图被分为三个互不连通的部分 。 每部分中的结点两两都有关系,不同部分中的任意两个结点则没有关系 。
第 4章 二元关系设 x和 y是两个整数,k是一个正整数,若 x,y用 k除的余数相等,就称 x和 y模 k同余,也称 x和 y模 k的的等价 。 记为 x ≡ y mod k
设 x(y)用 k除的商为 t1 ( t2 ),余数为 a1 ( a2 ),数学上将
x(y)表示成为：
x= k× t1＋ a1,t1?I,a1?I且 0≤ a1＜ k。
y= k× t2＋ a2,t2?I,a2?I且 0≤ a2＜ k。
若 x,y用 k除的余数相等,x-y= k× (t1-t2),t1-t2?I。
即 x-y可以被 k整除 。 所以,x和 y模 k同余还可以描述为,x-y可以被 k整除 。
第 4章 二元关系
【 例 4.20】 设 R=x,y x?I∧ y?I∧ x ≡ y mod k?是整数集合 I上的二元关系 。 证明 R是等价关系 。
证明,设 a,b,c是任意的整数 。
⑴ 因为 a-a=k× 0,所以 a≡a mod k,?a,aR。 故
R是自反的 。
⑵ 若?a,bR,a ≡ b mod k,a-b = k× t,t?I,b-a
=-(a-b)=k× (–t),–t?I,b≡a mod k,?b,aR。 故 R是对称的 。
⑶ 若?a,bR且?b,cR，
a-b = k× t1,t1?I,b-c = k× t2,t2?I，
a-c=(a-b)+(b-c)=k× t1+k× t2=k× (t1+t2),t1+t2?I,
a,cR,故 R是传递的 。
所以 R是整数集合 I上的等价关系 。
第 4章 二元关系定义 4.5.2 设 R是 X上的等价关系,?x?X,集合
y? y?X∧ xRy?
叫做 x形成的 R等价类 。 记为 [x]R
在例 4.19中,等价关系 R等价类为,[1]R=[2]R=?1,2?，
[3]R=[4]R=?3,4?,[5]R=?5?。 在 R的关系图 (图 4.9)中,三个互不连通的部分,每一部分中的所有结点构成一个等价类 。
上述模 3等价关系的等价类叫模 3等价类,模 3等价类有以下三个：
[0]R=,–6,–3,0,3,6,…?
[1]R=?…,–5,–2,1,4,7,…?
[2]R=?…,–4,–1,2,5,8,…?
定理 4.5.1 设 R是 X上的等价关系,?x?X,则有
⑴ [x]R?X
⑵ x?[x]R
定理证明留作练习 。
第 4章 二元关系从定理 4.5.1可以看出,等价关系的任何等价类是该等价关系前域 (或陪域 )的子集 。 例如,模 3等价类是整数集合的子集,[0]R?I,[1]R?I,[2]R?I。
从定理 4.5.1还可以看出,任何等价类是非空集合 。 x形成的 R等价类 [x]R至少有一个元素 x。 例如,在模 3等价类中,
0?[0]R,1?[1]R,2?[2]R。
定理 4.5.2 设 R是 X上的等价关系,对于 X的任意元素 a和 b，
aRb 的充分必要条件是 [a]R=[b]R
证明,设 aRb,下证 [a]R=[b]R
c?[a]R,aRc,由 R的对称性有 cRa,由条件 aRb和 R的传递性得 cRb,再根据 R的对称性有 bRc,c?[b]R,故 [a]R?[b]R。
类似地可以证明 [b]R?[a]R。 这就证明了 [a]R=[b]R。
设 [a]R=[b]R,下证 aRb。
由定理 4.5.1知 a?[a]R,因为 [a]R=[b]R,所以 a?[b]R,bRa，
由 R的对称性有 aRb。
第 4章 二元关系定义 4.5.3 设 R是 X上的等价关系,R的所有等价类组成的集合?[x]R?x?X?叫做 X关于 R的商集 。 记为 X/R。
在例 4.19中,等价关系 R 有三个等价类,[1]R=[2]R=?1,2?，
[3]R=[4]R=?3,4?,[5]R=?5?,A关于 R的商集
A/R=?[1]R,[2]R,[5]R?=1,2?,?3,4?,?5
模 3等价关系 R的等价类有以下三个,[0]R,[1]R和 [2]R，
由它确定的整数集合 I关于 R的商集 I/R=?[0]R,[1]R,[2]R?。
定理 4.5.3 设 R是 X上的等价关系,X关于 R的商集 X/R是 X
的一个划分 。
证明,⑴ 由定理 4.5.1知,[x]R?X且 [x]R≠?。
⑵ 证明 = X。 因为 [x]R?X,所以?X。
另一方面,x?X,由定理 4.5.1知,x?[x]R?,
x?,所以,X? 。 故 =X
Xx Rx? ][
Xx Rx? ][
Xx Rx? ][?Xx Rx? ][
Xx Rx? ][
Xx Rx? ][
第 4章 二元关系
⑶ 证明商集 X/R中的元素是两两互不相交的 。
设 [a]R≠ [b]R,证明 [a]R∩ [b]R =?
假定 [a]R∩ [b]R≠?
c?[a]R∩ [b]R
c?[a]R∧?c?[b]R
aRc∧ bRc?aRc∧ cRb (因为 R是对称的 )
aRb (因为 R是传递的 )
[a]R=[b]R (定理 4.5.2)
与假定矛盾 。
所以 [a]R∩ [b]R＝?
第 4章 二元关系定理 4.5.4 设 S=?S1,S2,?,Sm?是 X的一个划分,
R=x,y?| x和 y在同一个划分块中?，
则 R是 X上的等价关系 。
证明,⑴ 设 x?X=S1∪ S2∪? ∪ Sm,因为 S是 X的一个划分,所以存在惟一的划分块 Sj?S,使 x?Sj,于是有?x,xR，
即 R是自反的 。
⑵ 设?x,yR,x和 y在某个划分块 Sj中,则 y和 x也在划分块 Sj中,所以?y,xR,即 R是对称的 。
⑶ 设?x,yR∧?y,zR?x和 y在 Si中且 y和 z在 Sj中?
y?Si∩ Sj≠?,因为 S是 X的一个划分,其中元素两两互不相交,故必有 Si=Sj?x和 z在 Sj中x,zR,即 R是传递的 。
将定理 4.5.4中的等价关系 R叫做划分 S导出的等价关系 。
划分 S导出的等价关系 R也可以表示为：
R =(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)
第 4章 二元关系
【 例 4.21】 设 X=?1,2,3,4?,X的划分 S=1?,?2,3?，
4,试写出 S导出的等价关系 R。
解,R=1,1?,?2,2?,?2,3?,?3,2?,?3,3?,?4,4
=?1?×?1?∪?2,3?×?2,3?∪?4?×?4?
可以验证 R是 X上的等价关系 。
定理 4.5.5 设 R,S集合 X上的等价关系,则 R=S 当且仅当 X/R=X/S
证明,⑴ 设 R=S,证明 X/R=X/S。
先证?x?X,[x]R=[x]S
a?[x]R?xRa?xSa?a?[x]S,所以 [x]R?[x]S。
类似地可以证明 [x]S?[x]R,这就证明了 [x]R=[x]S。
第 4章 二元关系再证 X/R=X/S。
[x]R?X/R,[x]R=[x]S?X/S,即 [x]R?X/S,所以 X/R?X/S。
类似地可以证明 X/S?X/R,于是 X/R=X/S。
⑵ 设 X/R=X/S,证明 R=S。
因为 X/R=X/S,[a]R?X/R,必存在 [c]S?X/S,使 [a]R=[c]S
a,bR?aRb?b?[a]R?b?[a]R∧ a?[a]R
b?[c]S∧ a?[c]S
cSb∧ cSa?bSc∧ cSa (因为 S是对称的 )
bSa (因为 S是传递的 )
aSb (因为 S是对称的 )
a,bS
所以 R? S。
类似地可以证明 S?R,于是 R=S。
第 4章 二元关系
【 例 4.22】 设 X=?1,2,3?,写出集合 X上的所有等价关系 。
解,先写出集合 X上的所有划分,它们是：
S1=1,2,3,S2=1,2?,?3,S3=1,3?,?2
S4=2,3?,?1,S5=1?,?2?,?3
对应的等价关系为：
R1=?1,2,3?×?1,2,3?=X× X
R2=?1,2?×?1,2?∪?3?×?3?
=1,1?,?1,2?,?2,1?,?2,2?,?3,3
R3=?1,3?×?1,3?∪?2?×?2?
=1,1?,?1,3?,?3,1?,?3,3?,?2,2
R4=?2,3?×?2,3?∪?1?×?1?
=2,2?,?2,3?,?3,2?,?3,3?,?1,1
R5=?1?×?1?∪?2?×?2?∪?3?×?3?
=1,1?,?2,2?,?3,3=IX
第 4章 二元关系
4.6 相容关系定义 4.6.1 设 R?X× X,如果 R是自反的和对称的,则称 R是 X上的相容关系 。
根据定义 4.6.1,相容关系有以下三个性质：
① 所有等价关系都是相容关系 。
② 相容关系的关系矩阵主对角线全为 1且是对称阵 。
③ 相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边,一定有方向相反的两条边 。
返回章目录第 4章 二元关系
【 例 4.23】 设 A=?316,347,204,678,770?,A上的二元关系
R定义为,R=x,y?| x?A∧ y?A∧ x和 y有相同数码?,证明 R
是 A上的相容关系 。 写出关系矩阵和关系图 。 用关系矩阵和关系图验证 R是 A上的相容关系 。
证明,⑴ 集合 A中的每个数自己和自己有相同数码,故 R
是自反的；对于集合 A中任意 x和 y,如果 x和 y有相同数码,则
y和 x也有相同数码 。 故 R是对称的 。 于是,R是相容关系 。
令 a=316,b=347,c=204,d=678,e=770
用列举法将 R表示为：
R=a,a?,?a,b?,?a,d?,?b,a?,?b,b?,?b,c?,?b,d?,
b,e?,?c,b?,?c,c?,?c,e?,?d,a?,?d,b?,?d,d?,
d,e?,?e,b?,?e,c?,?e,d?,?e,e
=a,b?,?a,d?,?b,a?,?b,c?,?b,d?,?b,e?,?c,b?,?c,e?,
d,a?,?d,b?,?d,e?,?e,b?,?e,c?,?e,d∪ IA
第 4章 二元关系
11110
11011
10110
11111
01011
R
M
R的关系矩阵 MR主对角线全为 1且是对称阵，说明 R是相容关系。
R的关系图如图 4.10所示 。 在关系图中,每一个结点上都有自回路且每两个结点间如果有边,
一定有方向相反的两条边 。 表明了 R是相容关系 。
第 4章 二元关系因为相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边,一定有方向相反的两条边 。 所以可省去每一个结点上的自回路,将两个结点间方向相反的两条有向边改为一条无向边,得到一个简化图 。 此图叫做 R的简化关系图 。 例 4.23中的相容关系 R的简化关系图如图 4.11所示 。
第 4章 二元关系定义 4.6.2 设 R是 X上相容的关系,C?X,如果?a,b?C，
有?a,bR,则称 C是由相容关系 R产生的相容类 。
如果 R是 X上的相容关系,C是由相容关系 R产生的相容类 。 从定义可以看出：
① 相容类 C一定是 X的子集 。
②?x?X,因为相容关系 R是自反的,?x,xR,所以?x?
是由相容关系 R产生的一个相容类 。 即 X中的任何元素组成的单元素集是由相容关系 R产生的一个相容类 。
在例 4.23中,
a?,?a,b?,?b,c?,?b,d,e?都是 R产生的相容类 。
a,b?∪?d?=?a,b,d?和
b,c?∪?e?=?b,c,e?也是 R产生的相容类 。
但是?b,d,e?与任何非空集合的并集都不再是 R产生的相容类,这种相容类叫做最大相容类 。
第 4章 二元关系定义 4.6.3 设 R是 X上的相容关系,C是 R产生的相容类 。
如果它不是其它任何相容类的真子集,则称 C为最大相容类 。
记为 CR。
根据定义 4.6.3,最大相容类 CR具有如下的性质：
① CR中任意元素 x与 CR中的所有元素都有相容关系 R。
② X-CR中没有一个元素与 CR中的所有元素都有相容的关系 R。
性质 ① 的意思是,CR是 R产生的相容类,即最大相容类首先是相容类 。 性质 ② 的意思是,CR是最大相容类 。
利用相容关系的简化关系图可以求最大相容类,方法如下：
① 最大完全多边形的顶点构成的集合是最大相容类 。
② 孤立点构成的集合是最大相容类 。
③如果一条边不是任何完全多边形的边，则它的两个端点构成的集合是最大相容类。
第 4章 二元关系
【 例 4.24】 设 X=?1,2,3,4,5,6?，
R是 X上的相容关系,它的简化关系图如图 4.12所示,试找出所有最大相容类 。
解,最大完全 3边形的顶点构成的集合,?2,3,5?和?2,3,4?。
孤立点构成的集合,?6?。
不是任何完全多边形的边的两个端点构成的集合?1,5?。
所以,最大相容类为,
2,3,5?,?2,3,4?,?1,5?和?6?。
第 4章 二元关系定理 4.6.1 设 R是有限集合 X上的相容关系,C是 R产生的相容类,那么必存在最大相容类 CR,使得 C?CR。
证明,设 X=?x1,x2,?,xn?,令 C0=C。
如下构造相容类序列,C0?C1?C2
Ci+1=Ci∪?xj?
其中,j是使 xj?Ci 且 xj与 Ci的每一个元素都有相容关系 R的 x的最小下标 。
因为 |X|=n,所以至多经过 n-|C|步,可结束此过程 。
序列的最后一个集合就是要求的最大相容类 CR。
第 4章 二元关系定理 4.6.2 设 X是有限集合,R是 X上的相容关系,由 R产生的所有最大相容类构成的集合是 X的覆盖 。
证明,设 R产生的所有最大相容类构成的集合为,?C1,
C2,?,Cn?
⑴ 由相容类的定义知,任何最大相容类 Ci都是 X的子集 。
⑵ 证明 X= C1∪ C2∪? ∪ Cn
因为 Cj? X,所以 C1∪ C2∪? ∪ Cn? X。
x?X,?x?是相容类,根据定理 4.6.1,必存在最大相容类 Ci使得?xCi,而 Ci?C1∪ C2∪? ∪ Cn，
所以 x?C1∪ C2∪? ∪ Cn，
这就证明 X?C1∪ C2∪? ∪ Cn
故 X=C1∪ C2∪? ∪ Cn
第 4章 二元关系定义 4.6.4设 R是 X上的相容关系,S=?R产生的最大相容类?叫做集合 X的完全覆盖,记为 CR(X)。
例如,在例 4.24中最大相容类构成的集合为2,3,5?，
2,3,4?,?1,5?,?6,它是集合 X=?1,2,3,4,5,6?的一个完全覆盖 。 根据相容关系和相容类的定义,X中的任何元素组成的单元素集是由相容关系 R产生的一个相容类 。 所以
1?,?2?,?3?,?4?,?5?,?6? 都 是 相 容 类,集合
1?,?2?,?3?,?4?,?5?,?6是 X的覆盖 。 即完全覆盖是 X的覆盖,某些相容类构成集合也是 X的覆盖 。 所以由相容关系 R
产生的相容类构成的 X的覆盖并不惟一 。 但是一个相容关系只对应惟一的一个完全覆盖 。
第 4章 二元关系定理 4.6.3 设 S=?S1,S2,?,Sm?是 X的一个覆盖,则
R=(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)是 X上的相容关系 。
证明,⑴ x?X,因为 S是 X的一个覆盖,存在 Si?S,使
x?Si,于是有
x,xSi× Si?(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)=R,即
x,xR,所以 R是自反的 。
⑵ 设?x,yR=(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)，
x,ySi× Si,?y,xSi× Si，
而 Si× Si?(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)=R,即?y,xR，
所以 R是对称的 。
将定理 4.6.3中的 R叫做覆盖 S导出的相容关系 。
第 4章 二元关系
【 例 4.25】 设 X=?1,2,3,4?,S1=1,2,3?,?3,4，
S2=1,2?,?2,3?,?1,3?,?3,4是 X的两个覆盖 。 试写出 S1和 S2
导出的相容关系 R1和 R2。
解,R1=?1,2,3?×?1,2,3?∪?3,4?×?3,4?
=1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?2,3?,
3,1?,?3,2?,?3,3?,?3,4?,?4,3?,?4,4
R2=?1,2?×?1,2?∪?2,3?×?2,3?
∪?1,3?×?1,3?∪?3,4?×?3,4?
=1,1?,?1,2?,?2,1?,?2,2?,?2,3?,?3,2?,
3,3?,?1,3?,?3,1?,?3,4?,?4,3?,?4,4
在例 4.25中,S1≠ S2,但是 R1=R2。 这说明不同的覆盖可以导出相同的相容关系 。
定理 4.6.4 集合 X上的相容关系 R与集合 X的完全覆盖
CR(X)是一一对应的 。
证明留作作业 。
返回章目录第 4章 二元关系
4.7序关系
4.7.1偏序关系与哈斯图定义 4.7.1设 R?X× X,如果 R是自反的,反对称的和传递的,则称 R是 X上的偏序关系 。 记为?。 二重组?X,称为偏序集 。 如果?x,y,记为 x?y,读作 x小于等于 y。
【 例 4.26】 设 A是集合,P (A)是 A的幂集合,P (A)上的包含关系?定义如下：
=x,yx?P (A)∧ y?P (A)∧ x?y?
试证明?是 P (A)上偏序关系 。
证明,⑴?x?P(A),x?x,?x,x。 即?是自反的 。
⑵ 设?x,y∧?y,x,由包含关系?定义有 x?y∧
y?x,根据集合相等的定义,x=y。 即?是反对称的 。
⑶ 设?x,y∧?y,z,由包含关系?的定义有 x?y∧
y?z,根据集合包含的传递性,x?z,再由包含关系?定义有
x,z,即?是传递的 。是 P(A)上偏序关系 。
第 4章 二元关系另外,任意集合 A上的恒等关系 IA是自反的,反对称的和传递的,IA是 A上偏序关系；实数集合上的小于等于关系
(参看例 4.10)也是自反的,反对称的和传递的,它是实数集合上的偏序关系 。
定义 4.7.2 设?X,为偏序集,对 X中的元素 x和 y,如果
x?y,x≠ y且没有 X中的其它元素 z使 x?z和 z?y,则称 y盖住了 x。
【 例 4.27】 设 A=?2,5,6,10,15,30?,A上的整除关系 R定义如下：
R=x,yx?A∧ y?A∧ x整除 y?
验证 R是 A上的偏序关系，分析哪些元素盖住了另一些元素，
哪些元素没有盖住了另一些元素。
第 4章 二元关系解,因为 A的任何元素都能整除它自己,所以 R是自反的；
当 x整除 y且 y整除 x时,一定有 x=y,所以 R 是反对称的；当 x整除 y且 y整除 z,x一定整除 z,所以 R 是传递的 。 即 R是 A上的偏序关系 。
用列举法将 R表示为：
R=2,2?,?2,6?,?2,10?,?2,30?,?5,5?,?5,10?,
5,15?,?5,30?,?6,6?,?6,30?,?10,10?,?10,30?,
15,15?,?15,30?,?30,30
6和 10盖住了 2；但 30没有盖住了 2,因为?2,6R和
6,30R。
10和 15盖住了 5；但 30没有盖住了 5,因为?5,10R和
10,30R。
30盖住了 6,10和 15。
第 4章 二元关系定义 4.7.3设?X,为偏序集,集合
x,yx?X∧ y?X∧ y盖住了 x?
叫做 X上的盖住关系 。 记为 COV X。
设 COV X是 X上的盖住关系,如果?x,yCOV X,根据定义 4.7.3,y盖住了 x,由定义 4.7.2知,x?y,即?x,y。
故 COV X。 所以任何盖住关系 COV X都是相应偏序关系
的子集 。
在例 4.27中,偏序集?A,R?的盖住关系
COV A =2,6?,?2,10?,?5,10?,?5,15?,
6,30?,?10,30?,?15,30
第 4章 二元关系设?X,是偏序集，它的盖住关系 COV X是惟一的。
所以可以利用盖住关系做一图，表示该偏序集?X,。这个图叫做哈斯图。偏序集?X,的哈斯图的画法如下：
① 用,°” 表示 X中的每一个元素。
② 如果 x?y，则将 x画在 y的下方。
③ 若?x,yCOV X，则在 x和 y间画一条直线。
例 4.27的哈斯图是图 4.13。
第 4章 二元关系
【 例 4.28】 设 A=?a,b?,B=P (A)=,?a?,?b?,?a,b是 A
的幂集合,幂集合 P (A)上的包含关系
R?=x,y?| x?P (A)∧ y?P (A)∧ x?y?
试写出盖住关系 COVP (A),画出它的哈斯图 。
解,用列举法将 R?表示为
R?=,?a,,?b,,?a,b,a?,?a,b,
b?,?a,b∪ IB
在例 4.26中,已证 R?是 P (A)上的偏序关系 。 P (A)上的盖住关系为
COV P (A)=,?a,,?b,a?,?a,b,
b?,?a,b
哈斯图如图 4.14所示 。
第 4章 二元关系定义 4.7.4 设?X,是偏序集,B?X,b?B,如果 B中没有任何元素 x满足 x≠ b且 b?x(x?b),则称 b是 B的极大元
(极小元 )。
当 B=X时,B的极大元 (极小元 )称为偏序集?X,的极大元 (极小元 )。
第 4章 二元关系
【 例 4.29】 设 A=?a,b,c,d,e,f,g,h?,A上的二元关系
R=b,d?,?b,e?,?b,f?,?c,d?,?c,e?,?c,f?,?d,f?,?e,f?,?g,h∪ IA
验证 R是 A上的偏序关系 。 写出盖住关系 COV A,画出哈斯图 。
找出集合 A的极大元和极小元 。
解,容易验证 R是自反的,反对称的和传递的,R是 A上的偏序关系 。
COV A=b,d?,?b,e?,?c,d?,?c,e?,?d,f?,?e,f?,?g,h
哈斯图如图 4.15所示 。
集合 A的极大元是,a,f,h。
集合 A的极小元是,a,b,c,g。
第 4章 二元关系由定义 4.7.4和例 4.29可以得出以下结论：
① 孤立点既是极大元又是极小元 。
② 极大元和极小元不惟一 。 有限集合 B的极大元和极小元一定存在 。
③ 在哈斯图中,如果集合 B的某个元素不存在 B的其它元素从上 (下 )方与其相通,则该元素就是 B的极大元 (极小元 )。
定义 4.7.5 设?X,是偏序集,B?X,b?B,如果对任意 x?B,都有 x?b(b?x),则称 b是 B的最大元 (最小元 )。
当 B=X时,B的最大元 (最小元 )称为偏序集?X,的最大元 (最小元 )。 在例 4.29中,集合 A没有最大元和最小元 。
在例 4.28中,令 B=,?a,B的最大元是?a?,B的最小元是?。 令 B=a?,?b,B没有最大元和最小元 。
第 4章 二元关系定理 4.7.1 设?X,是偏序集,B?X,如果 B有最大元
(最小元 ),则必惟一 。
证明,设 a,b都是 B的最大元,由 a是 B的最大元得 b?a，
由 b是 B的最大元得 a?b,因为?是反对称的,所以 a=b。 即 B
的最大元惟一 。
类似地可证明最小元惟一 。
从以上例题和定理 4.7.1可以得出以下结论：
① 最大元和最小元不一定存在 。 如果存在,一定惟一 。
② 在哈斯图中,如果集合 B的某个元素向下 (上 )通向 B的所有元素,则该元素就是 B的最大元 (最小元 )。
定义 4.7.6 设?X,是偏序集,B?X,b?X,对任意 x?B，
都有 x?b(b?x),则称 b是 B的上界 (下界 )。
第 4章 二元关系
【 例 4.30】 设 A=?2,3,6,12,24,36?,其上的整除关系
R=a,b a?A∧ b?A∧ a能整除 b?
是 A上的偏序关系,试求盖住关系 COV A,画出哈斯图,确定下列集合的上界和下界 。
⑴ B1=?2,3,6?
⑵ B2=?12,24,36?
解,用列举法将 R表示为：
R=2,6?,?2,12?,?2,24?,?2,36?,?3,6?,?3,12?,?3,24?,
3,36?,?6,12?,?6,24?,?6,36?,?12,24?,?12,36∪ IA
盖住关系 COV A=2,6?,?3,6?,?6,12?,?12,24?,?12,36
第 4章 二元关系哈斯图如图 4.16所示 。
B1的上界是 6,12,24,36。 没有下界 。
B2的下界是 2,3,6,12。 没有上界 。
从本例可以看出：
① 上界和下界并不惟一 。
② 在哈斯图中,如果集合 X的某个元素向下 (上 )通向 B的所有元素,则该元素就是 B的上界 (下界 )。
定义 4.7.7设?X,是偏序集,B?X,如果存在 B的一个上界 (下界 )b,对 B的任意一个上界 (下界 )y,都有 b?y(y?b)，
则称 b是 B的最小上界 (最大下界 )。 也叫上确界 (下确界 )。 记为 LUB B (GLB B)。
在例 4.30中 B1的最小上界是 6； B1无下界,当然无最大下界 。 B2的最大下界是 12； B2无上界,当然无最小上界 。
第 4章 二元关系
4.7.2全序关系与良序集关系定义 4.7.8 设?X,为偏序集,如果?x?X,?y?X,都有 x?y或 y?x,则称偏序集?X,为全序集,也称为线序集 。
偏序关系?称为 X上的全序关系或线序关系 。
【 例 4.31】 设 N为自然数集合,N上的大于等于关系定义为
R≥ =x,yx?N∧ y?N∧ x≥ y?
证明 R≥ 是全序关系 。
证明,?x?N,x≥ x,?x,xR≥ 。 所以 R≥ 是自反的 。
当?x,yR≥ 且?y,xR≥,有 x≥ y且 y≥ x,从而 x=y。 所以 R≥ 是反对称的 。
当?x,yR≥ 且?y,zR≥,有 x≥ y且 y≥ z,则 x≥ z,即
x,zR≥ 。 所以 R≥ 是传递的 。
第 4章 二元关系综上所述,R≥ 是 N上的偏序关系 。
x?N,?y?N,必有 x≥ y或 y≥ x,即
x,yR≥ 或?y,xR≥,R≥ 是 N上的全序关系 。 其盖住关系为：
COV N=1,0?,?2,1?,?3,2?,
其哈斯图是图 4.17。
第 4章 二元关系
【 例 4.32】 设 P=a?,?a,b?,?a,b,c,P
上的包含关系
R?=x,yx?P∧ y?P∧ x?y?
验证 R?是全序关系 。
解,用列举法将 P上的包含关系 R?表示为：
R?=,?a,,?a,b,,?a,b,c,
a?,?a,b,a?,?a,b,c,
a,b?,?a,b,c∪ IP
容易验证 R?是 P上的偏序关系 。
从 R?的定义可以看出,对于 P中的任意两个元素 x和 y,必有 x?y或 y?x,所以 R?是 P上的全序关系 。 其盖住关系为：
COV P=,?a,a?,?a,b,
a,b?,?a,b,c
哈斯图如图 4.18所示 。
第 4章 二元关系定义 4.7.9 设?X,为偏序集,如果 X的每一个非空子集存在最小元,则偏序集?X,叫做良序集 。 偏序关系?称为
X上的良序关系 。
类似例 4.31可以证明自然数集合 N上的小于等于关系是偏序关系,而自然数集合的每一个非空子集都存在最小数 。
所以自然数集合上的小于等于关系?N,R≤?是良序集 。
定理 4.7.2 每一个良序集,一定是全序集 。
证明,设?X,是良序集,x和 y是 X中的任意两个元素,
显然?x,yX,由良序集的定义知,集合?x,y?必有最小元,
即 x是最小元或 y是最小元,如果 x是最小元,则有 x?y。 如果 y是最小元,则有 y?x。 所以?X,是全序集 。
第 4章 二元关系定理 4.7.3 有限全序集,一定是良序集 。
证明,设 X=?a1,a2,?,an?,? X,是全序集 。 下证
X,是良序集 。
设 B是 X的任意子集 。 因为 X是有限集,所以 B也是有限集,且 B中任意两个元素有关系?。 用以下方法可以找出 B
的最小元：
① 取 B的两个元素 x和 y,由于?X,是全序集,必有
x?y或 y?x,如果是前者选 x；如果是后者选 y。 记为 a。
② 再在 B中取没有选过的元素 b,则 a?b或 b?a,若为前者选 a；若为后者选 b。 记为 a′。
这个工作一直进行下去,直到 B中的元素选完 。 记最后选出来的元素为 c,因为关系?是传递的,所以 c是 B的最小元 。 所以?X,是良序集 。
返回总目录返回章目录
4.1 二元关系及其表示
4.2 关系的运算
4.3 关系的性质
4.4 关系的闭包运算
4.5 等价关系
4.6 相容关系
4.7 序关系返回总目录第 4章 二元关系第 4章 二元关系
4.1二元关系及其表示
4.1.1二元关系的概念定义 4.1.1设 A和 B是任意集合,如果 R?A× B,则称 R是
A到 B的二元关系 。 如果 R是 A到 A的二元关系,则称 R是 A上的二元关系 。
设 A=?1,2,3?,B=?a,b?,R=1,a?,?2,a?,?3,b。 R是 A
到 B的二元关系 。 S=3,1?,?2,2?,?2,1?,?1,1。 S是 A上的二元关系 。
定义 4.1.2设 A和 B是任意集合,R?A× B,若?x,yR，
则称 x与 y有 R关系 。 记为 xRy。 若?x,yR,则称 x与 y没有 R
关系 。 记为 x y。R?
第 4章 二元关系如果 R是 A到 B的二元关系,根据定义 4.1.2,?x,yR与
xRy,?x,yR与 x y的意义相同 。
定义 4.1.3设 A和 B是任意集合,空集?叫做 A到 B的空关系,仍然记为?。 A,B的笛卡尔积 A× B叫做 A到 B的全域关系,记为 E。 集合a,a?|a?A?叫做 A上的恒等关系 。 记为 IA。
【 例 4.1】 设 A=?a,b?,B=?1,2?,求 A上的恒等关系 IA和
A到 B的全域关系 A× B。
解,A上的恒等关系 IA=a,a?,?b,b,A到 B的全域关系
E =A× B=a,1?,?a,2?,?b,1?,?b,2
定理 4.1.1设 A是具有 n个元素的有限集,则 A上的二元关系有 2n2种 。
证明,设 A为具有 n个元素的有限集,即 |A|=n,由排列组合原理知 |A× A|=n2。 根据定理 3.1.2有 |P (A× A) |=2|A× A|=2,
即 A× A的子集有 2 个 。 所以具有 n个元素的有限集 A上有 2 种二元关系 。
2n 2n
2n
R?
第 4章 二元关系
4.1.2二元关系的表示
1.用列举法表示二元关系例 4.1中的 A到 B的全域关系
E=A× B=a,1?,?a,2?,?b,1?,?b,2
A上的恒等关系
IA=a,a?,?b,b
都是用列举法表示的 。
2.用描述法表示二元关系设 R是实数集,LR=x,y? | x?R∧ y?R∧ x≤ y?,LR是实数集 R上的二元关系 。
第 4章 二元关系
3.用矩阵表示二元关系如果 A,B是有限集,
A=?a1,a2,?,am?，
B=?b1,b2,?,bn?，
R是 A到 B的二元关系,R的关系矩阵定义为：
MR= m?n
R
R
b
b
a
ar
j
j
i
i
ij?
,
,
0
1
i=1,?,m j=1,?,n
称为二元关系 R的关系矩阵 。
ijr
第 4章 二元关系
【 例 4.3】 设 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=
011
001
110
101
第 4章 二元关系
【 例 4.4】 设 A=?1,2,3,4?,R是 A的二元关系,定义为：
R=1,1?,?1,2?,?2,1?,?3,2?,?3,1?,?4,3?,?4,2?,?4,1
写出 A上二元关系 R的关系矩阵 。
解,R的关系矩阵为：
MR=
0111
0011
0001
0011
例 4.4中的二元关系 R是 A上的二元关系,只需看成 A
到 A的二元关系,利用上述定义,就可以方便地写出它的关系矩阵 。 A上的二元关系和 A到 B的二元关系的关系矩阵的定义是相同的 。
第 4章 二元关系
4.用图表示二元关系如果 A和 B是有限集,R是 A到 B二元关系,还可以用图表示二元关系 R。 表示二元关系 R的图叫做 R的关系图 。 A到 B二元关系的关系图和 A上的二元关系的关系图的定义是不一样的 。 分别描述如下：
⑴ A到 B二元关系 R的关系图设 A=?a1,a2,?,am?,B=?b1,b2,?,bn?,R是 A到 B二元关系,R的关系图的绘制方法如下：
① 画出 m个小圆圈表示 A的元素,再画出 n个小圆圈表示 B的元素 。 这些小圆圈叫做关系图的结点 (下同 )。
②如果?ai,bjR，则从 ai到 bj画一根有方向 (带箭头 )的线。这些有方向 (带箭头 )的线叫做关系图的边
(下同 )。
第 4章 二元关系例 4.3中的二元关系 R的关系图如图 4.1。
⑵ A上的二元关系 R的关系图设 A=?a1,a2,?,am?,R是 A上的二元关系,其关系图如下绘制：
① 画出 m个小圆圈表示 A的元素 。
② 如果?ai,ajR,则从 ai到 aj画一根有方向 (带箭头 )
的线 。
例 4.4中的二元关系 R的关系图如图 4.2。
返回章目录第 4章 二元关系
4.2关系的运算定义 4.2.1设 A,B是集合,R?A× B。
dom R=?x|?x,yR? 叫做 R的定义域 。
ran R=?y|?x,yR?叫做 R的值域 。
FLD R= dom R∪ ran R叫做 R的域 。
A叫做 R的前域； B叫做 R的陪域 。
4.2.1二元关系的交,并,补,对称差运算定理 4.2.1设 R,S是 X到 Y的二元关系,则 R∪ S,R∩S，
R-S,~R,R S也是 X到 Y的二元关系 。
证明,因为 R,S是 X到 Y的二元关系,所以,
R?X× Y且 S?X× Y。 显然,
R∪ S?X× Y,即 R∪ S是 X到 Y的二元关系 。
R∩ S?X× Y,即 R∩ S是 X到 Y的二元关系 。
R-S?X× Y,即 R-S是 X到 Y的二元关系 。
第 4章 二元关系在二元关系运算中,认为全域关系是全集 。 所以
~R= X× Y-R?X× Y,即 ~R是 X到 Y的二元关系 。
由以上结论可以得到：
(R－ S)?X× Y和 (S－ R)?X× Y,从而
(R－ S)∪ (S－ R)?X× Y,所以
R S=(R－ S)∪ (S－ R)?X× Y,即 R S是 X到 Y的二元关系 。
【 例 4.5】 设 X=?1,2,3,4?,X上的二元关系 H和 S定义如下：
H=x,y? | 是整数?
S=x,y? | 是正整数?
试求 H∪ S,H∩ S,~H,S-H
2
yx?
3yx?
第 4章 二元关系解,将 H和 S用列举法表示：
H=1,1?,?1,3?,?2,2?,?2,4?,?3,3?,?3,1?,?4,4?,?4,2
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
4.2.2二元关系的复合运算定义 4.2.2 设 X,Y,Z是集合,R?X× Y,S?Y× Z,集合
x,zx?X∧ z?Z∧ (?y)(y?Y∧?x,yR∧?y,zS)?
叫做 R和 S的复合关系 。 记为 R°S,R°S?X× Z,即 R°S是 X到
Z的二元关系 。
第 4章 二元关系
【 例 4.6】 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
试求 R°S,S°R,R°(S°R),(R°S)°R,R°R,S°S,R°R°R
解,R°S=1,5?,?3,2?,?2,5
S°R=4,2?,?3,2?,?1,4
(R°S)°R=3,2
R°(S°R)=3,2
R°R=1,2?,?2,2
S°S=4,5?,?3,3?,?1,1
R°R°R =1,2?,?2,2
从例 4.6可以看出,R°S≠ S°R，这说明，二元关系的复合运算不满足交换律。
第 4章 二元关系定理 4.2.2 设 X,Y,Z,W是集合,R?X× Y,S?Y× Z，
T? Z× W,则 (R°S)°T= R°(S°T)
证明,?x,w(R°S)°T?(?z)(?x,zR°S∧?z,wT)
(?z)((?y)(?x,yR∧?y,zS)∧?z,wT)
(?z)(?y)((?x,yR∧?y,zS)∧?z,wT)
(?y)(?z)(?x,yR∧ (?y,zS∧?z,wT))
(?y)(?x,yR∧ (?z)(?y,zS∧?z,wT))
(?y)(?x,yR∧?y,wS°T)x,wR°(S°T)
所以 (R°S)°T=R°(S°T)
第 4章 二元关系定理 4.2.3 设 R是 A上的二元关系,R°IA=IA°R=R
证明,先证 R°IA=R
x,yR°IA?(?z)(?x,zR∧?z,yIA)
(?z)(?x,zR∧ z=y)x,yR
所以 R°IA?R
x,yRx,yR∧?y,yIAx,yR°IA
所以 R?R°IA
故 R°IA=R
类似的,可以证明 IA°R= R
第 4章 二元关系定理 4.2.4 设 R,S,T是 A上的二元关系,则
⑴ R°(S∪ T)=R°S∪ R°T
⑵ (R∪ S)°T=R°T∪ S°T
⑶ R°(S∩ T)?R°S∩ R°T
⑷ (R∩ S)°T?R°T∩ S°T
证明,仅证明 ⑶,类似地可证明 ⑴,⑵ 和 ⑷ 。
x,yR°(S∩ T)?(?z)(?x,zR∧?z,yS∩ T)
(?z)(?x,zR∧ (?z,yS∧?z,yT))
(?z)((?x,zR∧?z,yS)∧ (?x,zR∧?z,yT))
(?z)(?x,zR∧?z,yS)∧ (?z)(?x,zR∧?z,yT)
x,yR°S∧?x,yR°T
x,yR°S∩ R°T
故 R°(S∩ T)?R°S∩ R°T
第 4章 二元关系一般地说,R°S∩ R°T?R°(S∩ T),举反例如下：
设 A=?1,2,3,4,5?
R=4,1?,?4,2A× A
S=1,5?,?3,5A× A
T=2,5?,?3,5A× A
R°S∩ R°T =4,5∩4,5=4,5
R°(S∩ T) =4,1?,?4,2°3,5=?
R°S∩ R°T?R°(S∩ T)
定理 4.2.4的 ⑴ 说明,关系的复合运算,°” 对并运算
,∪,满足左分配律 。 ⑵ 说明,关系的复合运算,°”
对并运算,∪,满足右分配律 。 所以,复合运算,°”
对并运算,∪,满足分配律 。 由 ⑶ 和 ⑷ 知,复合运算
,°” 对交运算,∩,不满足分配律 。
第 4章 二元关系定义 4.2.3 设 R是 A上的二元关系,n为自然数,R的 n次幂记为 Rn,定义为：
⑴ R0=IA
⑵ Rn+1= Rn°R
由定义 4.2.3可以看出,A上的任何二元关系的 0次幂都相等,等于 A上的恒等关系 IA。 由定义 4.2.3还可以看出：
R1= R0 °R=IA°R=R
R2= R1°R= R°R
R3= R2°R=(R°R)°R
因为复合运算满足结合律,所以 R3又可以写成：
R3= R°R°R
同样的道理 Rn也可以写成,Rn= 的复合个 Rn RRR
第 4章 二元关系例如,在例 4.6中
R2=R°R=1,2?,?2,2
S2 =S°S=4,5?,?3,3?,?1,1
R3=R°R°R=1,2?,?2,2
定理 4.2.5设 A是具有 n个元素的有限集,R是 A上的二元关系,则必存在自然数 s和 t,使得 Rs=Rt,0≤ s＜ t≤ 2 。
证明,R是 A上的二元关系,对任何自然数 k,由复合关系的定义知,Rk仍然是 A上的二元关系,即 Rk?A× A。 另一方面,根据定理 4.1.1,A上的二元关系仅有 2 种 。 列出 R的各次幂 R0,R1,R2,?,,共有 2 ＋ 1个,必存在自然数 s和 t,使得 Rs=Rt,0≤ s＜ t≤ 2 。2n
2n
2n
22nR
2n
第 4章 二元关系
【 例 4.7】 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= R°R=1,1?,?1,3?,?2,2?,?2,4
R3= R2°R =1,2?,?2,1?,?2,3?,?1,4
R4=R3°R=1,1?,?1,3?,?2,2?,?2,4=R2，
0≤ 2＜ 4≤ 216=2
R5=R4°R=R2°R=R3
R6=R5°R=R3°R=R4= R2
R2n=R2
R2n+1=R3,n =1,2,3,?
24
第 4章 二元关系定理 4.2.6设 R是 A上的二元关系,m,n为自然数,则
⑴ Rm°Rn =Rm+n
⑵ (Rm)n=Rmn
证明,⑴ 对任意给定的 m?N,关于 n进行归纳证明：
当 n=0时,Rm °R0=Rm°IA=Rm=Rm+0
设 n=k时,Rm°Rk=Rm+k。 下证 n=k+1时,结果也对 。
Rm°Rk+1=Rm°(Rk°R)=(Rm°Rk)°R=Rm+k°R= 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=Rmk°Rm=Rmk+m=Rm(k+1)
设 X,Y,Z是集合,R?X× Y,S?Y× Z,R°S是 R和 S的复合关系,R°S?X× Z,它们的关系矩阵分别是 MR,MS和 MR°S。
以下研究这三个矩阵之间的关系 。
第 4章 二元关系设 X=?x1,x2,?,xm?,Y=?y1,y2,?,yn?,Z=?z1,z2,?,zP?
R?X× Y,S?Y× Z,R°S?X× Z
MR= m?n
i=1,?,m,j=1,?,n
MS= n?p
i=1,?,n,j =1,?,p
MR°S= m?p
i=1,?,m,j =1,?,p
iju RRyyxxu
j
j
i
i
ij?
,
,
0
1
ijv SSzzyyv
j
j
i
i
ij?
,
,
0
1
ijw
S
S
R
R
z
z
x
xw
j
j
i
i
ij?
,
,
0
1
第 4章 二元关系与,有如下的关系：
= i=1,?,m,j=1,?,p
将上述关系用矩阵符号记为：
MR ° S=MR °MS,其中,i=1,?,m,j =1,?,p
矩阵运算,°” 叫做关系矩阵 MR和 MS的布尔乘法 。
把关系矩阵的布尔乘法公式
= i=1,?,m,j =1,?,p
与线性代数中的矩阵乘法公式相比,发现,只要把矩阵乘法公式中的数乘改为合取,把数加改为析取,就得到了关系矩阵的布尔乘法公式 。
)(1 kjiknk vuijw
ijw )(1 kjik
n
k vu
ijw iju ijv
第 4章 二元关系
【 例 4.8】 A=?1,2,3,4,5?,A上的二元关系 R和 S定义如下：
R=1,2?,?2,2?,?3,4
S=1,3?,?2,5?,?3,1?,?4,2
试求 MR ° S和 MR °MS,它们是否相等?
解,按照 R 和 S的定义,求出
R°S=1,5?,?3,2?,?2,5
写出 R,S和 R ° S关系矩阵如下：
MR= MS= MR ° S=
00000
00000
01000
00010
00010
00000
00010
00001
10000
00100
00000
00000
00010
10000
10000
第 4章 二元关系
MR °MS= ° =
所以 MR ° S=MR °MS
4.2.3二元关系的求逆运算定义 4.2.4 设 X,Y是集合,R?X× Y,集合
y,xx,yR?
叫做 R的逆关系 。 记为 RC,RC?Y× X,RC是 Y到 X的二元关系 。
容易证明,RC的关系矩阵 是 R的关系矩阵 MR的转置矩阵,即 =MRT
可以验证,将 R关系图中的弧线的箭头反置,就可以得到
RC关系图 。
00000
00000
01000
00010
00010
00000
00010
00001
10000
00100
00000
00000
00010
10000
10000
CRM
CRM
第 4章 二元关系
【 例 4.9】 设 X=?1,2,3,4?,Y=?a,b,c?,X到 Y二元关系
R=1,a?,?2,b?,?4,c，
⑴ 试求 RC,写出 MR和,验证 =MRT
⑵ 画出 R和 RC的关系图,验证将 R关系图中的弧线的箭头反置可得到 RC关系图 。
解,RC=a,1?,?b,2?,?c,4
R和 RC的关系矩阵是：
MR= =
显然,=MRT
100
000
010
001
CRM
1000
0010
0001
CRM
CRM CRM
第 4章 二元关系
R和 RC的关系图分别是图 4.3和图 4.4,它们中的弧线的方向是相反的 。
第 4章 二元关系定理 4.2.7设 X,Y是集合,R?X× Y,则
⑴ (RC )C= R
⑵ dom RC= ran R,ran RC= dom R
证明,⑴?x,yRy,xRCx,y(RC)C
所以 (RC )C= R
⑵ x?dom RC?(?y)(?x,yRC)?(?y)(?y,xR)
x?ran R
所以 dom RC= ran R
类似的可以证明 ran RC= dom R
第 4章 二元关系定理 4.2.8设 X,Y是集合,R,S是 X到 Y的二元关系，则
⑴ (R∪ S)C = RC∪ SC
⑵ (R∩ S)C =RC∩ SC
⑶ (A× B)C=B× A
⑷ (~R) C =~ (R C)
⑸ (R-S)C =RC-SC
证明,⑴
x,y(R∪ S)Cy,xR∪ Sy,xR∨?y,xS
x,yRC∨?x,ySCx,yRC∪ SC
所以 (R∪ S)C =RC∪ SC
类似⑴可证明⑵和⑶。
⑷?x,y(~R)Cy,x~Ry,xRy,xR
x,yRCx,yRCx,y~ (RC)
所以 (~R) C =~(R C)
第 4章 二元关系返回章目录
⑸ 利用 ⑴,⑵ 和 ⑷ 证明：
(R-S)C=(R∩ ~S)C=RC∩ (~S)C=RC∩ ~(SC)=RC-SC
定理 4.2.9设 X,Y,Z是集合,R?X× Y,S?Y× Z,则
(R°S)C=SC°RC
证明：
z,x(R°S)Cx,z(R°S)
(?y)(?x,yR∧?y,zS)
(?y)(?y,xRC∧?z,ySC)
(?y)(?z,ySC∧?y,xRC)
z,xSC°RC
所以 (R°S)C=SC°RC
第 4章 二元关系
4.3 关系的性质定义 4.3.1 设 R?X× X,(?x)(x?X→?x,xR),则称 R在 X
上是自反的 。
设 R是 X上的自反关系,由定义 4.3.1知,R的关系矩阵 MR
的主对角线全为 1；在关系图中每一个结点上都有自回路 。
设 X=?1,2,3?,X上的二元关系
R=1,1?,?2,2?,?3,3?,?1,2
R是自反的,它的关系图如图 4.5所示,关系矩阵如下：
MR=
100
010
011
第 4章 二元关系定理 4.3.1 设 R是 X上的二元关系,R是自反的当且仅当
IX?R。
证明,设 R在 X上是自反的,下证 IX?R。
x,yIX?x=yx,yR,即 IX?R。
设 IX?R,下证 R在 X上是自反的 。
x?Xx,xIXx,xR,即 R在 X上是自反的 。
定义 4.3.2 设 R?X× X,(?x)(x?X→?x,xR),则称 R在 X
上是反自反的 。
设 R是 X上的反自反关系,由定义 4.3.2可知,R的关系矩阵 MR的主对角线全为 0；在 R的关系图中每一个结点上都没有自回路 。
设 X=?1,2,3?,X上的二元关系 R=1,2?,?2,3?,?3,1,R
是反自反的,它的关系图如图 4.6所示,关系矩阵如下：
第 4章 二元关系
MR =
001
100
010
【 例 4.11】 设 R是实数集合,
＞ =x,y?| x?R∧ y?R∧ x＞ y?
是实数集合上的大于关系 。 证明实数集合上的大于关系是反自反的 。
证明,?x?R,x≯ x,?x,x＞,所以＞是反自反的 。
第 4章 二元关系定理 4.3.2 设 R是 X上的二元关系,R是反自反的当且仅当 R∩ IX=?。
证明,设 R在 X上是反自反的,下证 R∩ IX=?。
假设 R∩ IX≠?
必存在?x,yR∩ IXx,yR∧?x,yIXx,yR∧
x=y,即?x,xR,这与 R是 X上的反自反关系相矛盾 。 所以
R∩ IX=?。
设 R∩ IX=?,下证 R在 X上是反自反的 。
任取 x?X
x,xIX，由于 R∩ IX=?，必然?x,xR，即 R在 X上是反自反的。
第 4章 二元关系
【 例 4.12】 设 A=?1,2,3?,定义 A上的二元关系如下：
R=1,1?,?2,2?,?3,3?,?1,3
S=1,3
T=1,1
试说明 R,S,T是否是 A上的自反关系或反自反关系 。
解,因为?1,1?,?2,2?和?3,3?都是 R的元素,所以 R
是 A上的自反关系,不是反自反关系 。 因为?1,1?,?2,2?
和?3,3?都不是 S的元素,所以 S是反自反关系,不是 A上的自反关系 。 因为?2,2T,所以 T不是 A上的自反关系 。
因为?1,1T,所以 T不是 A上的反自反关系 。
第 4章 二元关系定义 4.3.3 设 R?X× X,(?x)(?y)(x?X∧ y?X∧?x,yR
→?y,xR),则称 R在 X上是对称的 。
R是 X上的对称关系,由定义 4.3.3知,R的关系矩阵 MR
是对称阵 。 在 R的关系图中,如果两个不同的结点间有边,
一定有方向相反的两条边 。
设 X=?1,2,3?,X上的二元关系 R=1,2?,?2,1?,?3,3，
R是对称的 。 它的关系图如图 4.7所示,关系矩阵如下：
MR=
100
001
010
第 4章 二元关系
【 例 4.13】 设 A=?1,3,5,7?,定义 A上的二元关系如下：
R=a,b?|(a－ b)/2是整数?
试证明 R在 A上是自反的和对称的 。
证明,?a?A,(a-a)/2=0,0是整数,所以?a,aR。 即
R是自反的 。
a?A,?b?A,?a,bR,(a-b)/2是整数,因为整数的相反数也是整数,所以 (b-a)/2=-(a-b)/2是整数,?b,aR。
即 R是对称的 。
定理 4.3.3 设 R是 X上的二元关系,R是对称的当且仅当
R=RC。
证明,设 R是对称的,下证 R =RC。
x,yRy,xRx,yRC,所以 R =RC。
设 R =RC,下证 R是对称的 。
x,yRy,xRCy,xR,所以 R是对称的 。
第 4章 二元关系定义 4.3.4 设 R?X× X，
(?x)(?y)(x?X∧ y?X∧?x,yR∧?y,xR→ (x=y))
则称 R在 X上是反对称的 。
x,yR∧?y,xR→ (x=y)
(x=y)→?(?x,yR∧?y,xR)
(x=y)→ (?x,yR∨?y,xR)
((x=y)∨?x,yR)∨?y,xR
((x≠ y)∧?x,yR)∨?y,xR
(x≠ y)∧?x,yR→?y,xR
x,yR∧ (x≠ y)→?y,xR
由此,反对称的定义又可以等价的描述为：
(?x)(?y)(x?X∧ y?X∧?x,yR∧ (x≠ y)→?y,xR)
第 4章 二元关系设 R是 X上的反对称关系,由定义 4.3.4知,在 R的关系矩阵 MR中以主对角线为轴的对称位置上不能同时为 1(主对角线除外 )。 在 R的关系图中每两个不同的结点间不能有方向相反的两条边 。
设 X=?1,2,3?,X上的二元关系 R=1,2?,?2,3?,?3,3，
R是反对称的 。 它的关系图如图 4.8所示,关系矩阵如下：
MR=
100
100
010
第 4章 二元关系
【 例 4.14】 设 A=?1,2,3?,定义 A上的二元关系如下：
R=1,1?,?2,2
S=1,1?,?1,2?,?2,1
T=1,2?,?1,3
U=1,3?,?1,2?,?2,1
试说明 R,S,T,U是否是 A上的对称关系和反对称关系 。
解,R是 A上的对称关系,也是 A上的反对称关系 。
S是 A上的对称关系 。 因为?1,2?和?2,1?都是 S元素,而
1≠ 2,所以 S不是 A上的反对称关系 。
因为?1,2T,而?2,1T,所以 T不是 A上的对称关系 。
T是 A上的反对称关系 。
U不是 A上的对称关系,也不是 A上的反对称关系 。
第 4章 二元关系定理 4.3.4设 R是 X上的二元关系,则 R是反对称的当且仅当 R∩ RC?IX。
证明,设 R是反对称的,下证 R∩ RC?IX。
x,yR∩ RCx,yR∧?x,yRC
x,yR∧?y,xR
因为 R 是反对称的,所以 y=x,?x,y?=?x,x?=?y,yIX,故
R∩ RC?IX
设 R∩ RC?IX,下证 R是反对称的 。
x,yR∧?y,xRx,yR∧?x,yRC
x,yR∩ RC
因为 R∩ RC?IX,所以?x,yIX,故 x=y,R是反对称的 。
定义 4.3.5 设 R?X× X，
(?x)(?y)(?z)(x?X∧ y?X∧ z?X∧?x,yR∧?y,zR
→?x,zR)
则称 R在 X上是传递的 。
第 4章 二元关系
【 例 4.15】 设 R是实数集合,
S=x,y?|x?R∧ y?R∧ x=y?
是实数集合上的等于关系 。 证明实数集合上的等于关系是传递的 。
证明,?x?R,?y?R,?z?R,?x,yS且?y,zS,由
S的定义有 x=y和 y=z,由实数相等的概念得 x=z。 再根据 S的定义,?x,zS。 故实数集合上的等于关系 S是传递的 。
定理 4.3.5 设 R是 X上的二元关系,R是传递的当且仅当
R°R?R。
证明,设 R是传递的,下证 R°R?R。
x,yR°R,?z?X,使得?x,zR且?z,yR,又因为 R是传递的,所以?x,yR,这就证明了 R°R?R。
设 R°R?R,下证 R是传递的 。
x,yR且?y,zR,由复合关系的定义得?x,z R°R,因为 R°R?R,所以?x,zR,所以 R是传递的 。
第 4章 二元关系上述的 5个定理,可以作为相应概念的定义使用,用来判断和证明关系的性质 。 有些问题用这 5个定理处理是非常方便的 。 请看下面的例题 。
【 例 4.16】 设 R,S是 X上的二元关系,证明
⑴ 若 R,S是自反的,则 R∪ S和 R∩ S也是自反的 。
⑵ 若 R,S是对称的,则 R∪ S和 R∩ S也是对称的 。
⑶ 若 R,S是传递的,则 R∩ S也是传递的 。
证明,⑴ 设 R,S是自反的,由定理 4.3.1知,IX?R,IX?S，
所以 IX?R∪ S,IX?R∩ S,再由定理 4.3.1知,R∪ S和 R∩ S也是自反的 。
第 4章 二元关系
⑵ 设 R,S是对称的,由定理 4.3.3知,R=RC,S=SC,根据定理 4.2.8,R∪ S=RC∪ SC=(R∪ S)C,R∩ S=RC∩ SC=(R∩ S) C，
再由定理 4.3.3知,R∪ S和 R∩ S也是对称的 。
⑶ 设 R,S是传递的,由定理 4.3.5知,R°R?R,S°S?S，
据定理 4.2.4，
(R∩ S)°(R∩ S)?(R°R)∩ (R°S)∩ (S°R)∩ (S°S)
(R°R)∩ (S°S)?R∩ S
即 (R∩ S)°(R∩ S)?R∩ S,再由定理 4.3.5,R∩ S是传递的 。
以上研究了二元关系的 5个性质及其关系矩阵,关系图的特点,它们对今后的学习是重要的 。
返回章目录第 4章 二元关系
4.4关系的闭包运算定义 4.4.1 设 R?X× X,X上的二元关系 R′ 满足：
⑴ R′是自反的 (对称的，传递的 )。
⑵ R?R′。
⑶对 X上的任意二元关系 R′′，如果 R?R′′且 R′′是自反的
(对称的，传递的 )，就有 R′?R′′。
则称 R′是 R的自反 (对称，传递 )闭包。记为 r(R)(s(R),t(R))
定义 4.4.1的⑴和⑵的意思是自反 (对称，传递 )闭包 R′是包含 R的自反 (对称，传递 )关系；定义 4.4.1的⑶的意思是在所有包含 R的自反 (对称，传递 )关系中自反 (对称，传递 )闭包 R′
是最小的。所以，定义 4.4.1又可以描述为：包含 R的最小自反 (对称，传递 )关系是 R的自反 (对称，传递 )闭包。
传递闭包 t(R)有时也记为 R+，读作,R加,。传递闭包在语法分析中有很多重要的应用。
第 4章 二元关系当二元关系 R是自反 (对称，传递 )的时，求 R的自反 (对称，传递 )闭包方法由下面的定理给出了。
定理 4.4.1 设 R?X× X，则
⑴ R是自反的当且仅当 r(R)=R。
⑵ R是对称的当且仅当 s(R)=R。
⑶ R是传递的当且仅当 t(R)=R。
证明,仅证明⑴，其余留做练习。
设 R是自反的，下证 r(R)=R
令 R′=R
① R′=R,R是自反的，所以 R′是自反的。
②因为 R′=R，所以 R?R′。
③ R′′是 X上的任意自反关系且 R?R′′，因为 R′=R，所以
R′?R′′。
故 R′是 R的自反闭包。即 r(R)=R。
第 4章 二元关系设 r(R)=R，下证 R是自反的。
由自反闭包的定义知,R是自反的。
以下的几个定理给出了求二元关系 R的自反闭包、对称闭包和传递闭包的一般方法。
定理 4.4.2 设 R?X× X，则 r(R)=R∪ IX
证明,令 R′=R∪ IX
⑴ IX?R∪ IX，而 R∪ IX =R′，所以 IX?R′,R′是自反的。
⑵ R?R∪ IX，而 R∪ IX =R′，所以 R?R′
⑶ R′′是 X上的任意自反关系且 R?R′′，由于 R′′是自反的，
所以 IX?R′′，从而有 R′=R∪ IX?R′′。
根据自反闭包的定义,R′=R∪ IX是 R的自反闭包，即
r(R)=R∪ IX。
第 4章 二元关系定理 4.4.3 设 R?X× X，则 s(R)=R∪ RC
证明,令 R′=R∪ RC
⑴ (R′)C= (R∪ RC) C= RC∪ (RC)C= RC∪ R=R∪ RC=R′，所以 R′是对称的。
⑵ R?R∪ RC，而 R∪ RC =R′，所以 R?R′。
⑶ R′′是 X上的任意对称关系且 R?R′′，
x,yRCy,xRy,xR′′
x,yR′′(R′′是对称的 )，
所以 RC?R′′，从而有 R′=R∪ RC?R′′。 R′是 R的对称闭包，即
s(R)= R∪ RC。
定理 4.4.4 设 R?X× X，则 t(R)=R∪ R2∪ R3∪?
证明,先证 R∪ R2∪ R3∪t(R)
用数学归纳法证明,?i?I+ \ Ri?t(R)
第 4章 二元关系
① 当 i =1时，由传递闭包的定义,R1= R?t(R)。
② 设 i =n时,Rn?t(R)。下证 Rn+1?t(R)。
x,yRn+1?(?c)(?x,cRn∧?c,yR)
(?c)(?x,ct(R)∧?c,yt(R)) (① 和归纳假设 )
x,yt(R) (t(R)是传递的 )
即 Rn+1? t (R)
故 R∪ R2∪ R3∪t (R)
再证 t(R)?R∪ R2∪ R3∪?
显然 R?R∪ R2∪ R3∪?
以下证明 R∪ R2∪ R3∪? 是传递的。
x,yR∪ R2∪ R3∪? 且?y,zR∪ R2∪ R3∪?
t?I+使?x,yRt∧?s?I+ 使?y,zRs
x,zRt°Rs=Rt+s?R∪ R2∪ R3∪?
x,zR∪ R2∪ R3∪?
根据传递关系的定义,R∪ R2∪ R3∪? 是传递的。
第 4章 二元关系综上所述,R∪ R2∪ R3∪? 是包含 R的传递关系。而 R的传递闭包是包含 R的最小传递关系。所以
t(R)?R∪ R2∪ R3∪?
t(R)=R∪ R2∪ R3∪?
【 例 4.17】 设 A=?1,2,3?,定义 A上的二元关系 R为：
R=1,2?,?2,3?,?3,1
试求,r(R),s(R),t(R)
解,r(R)= R∪ IA=1,2?,?2,3?,?3,1?,?1,1?,?2,2?,?3,3
s(R)=R∪ RC=1,2?,?2,3?,?3,1?,?2,1?,?3,2?,?1,3
以下求 t(R)：
R2= R°R=1,3?,?2,1?,?3,2
R3= R2°R =1,1?,?2,2?,?3,3=IA
R4= R3°R = IA°R=R
继续这个运算，则有第 4章 二元关系
R= R4= R7=? =R3n+1=?
R2= R5= R8=? =R3n+2=?
R3= R6= R9=? =R3n+3=?
其中,n是任意的自然数。 t(R)=R∪ R2∪ R3∪?
t(R)= R∪ R2∪ R3
=1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?2,3?,
3,1?,?3,2?,?3,3
当 A是具有 n个元素的有限集时，由定理 4.2.5知，存在自然数 s和 t，使得 Rs=Rt,0≤ s＜ t≤ 2。于是
Rt+1=Rs+1,Rt+2=Rs+2,
即当 i≥ t,Ri就出现了重复。因为集合的并运算满足幂等律，
所以,t(R)=R∪ R2∪ R3∪? =R∪ R2∪ R3∪? ∪ R
这个结论还可以改善。
22n
第 4章 二元关系定理 4.4.5 设 |X|=n,R?X× X，则 t(R)= R∪ R2∪? ∪ Rn
证明,只需证明 t(R)?R∪ R2∪ R3∪? ∪ Rn
设?x,yt(R)=R∪ R2∪ R3∪?,由并集合的定义知，存在最小的正整数 k使得?x,yRk。下证 k≤ n。
设 k＞ n，根据复合关系的定义，存在 X中的元素序列：
x=a0,a1,a2,?,ak-1,ak=y，使 xRa1,a1Ra2,?,ak-1Rak(y)，
此序列中有 k+1个 X的元素,k+1＞ n+1＞ n。而 X中只有 n个元素，所以 a0,a1,a2,?,ak-1,ak中必有相同的元素，设 ai = aj，
0≤ i＜ j≤ k。去掉序列中 ai+1到 aj的所有元素，于是
xRa1,a1Ra2,?,ai-1Rai,ajRaj+1,?,ak-1Rak(y)
成立。即?x,yRs，其中 S=k-(j-i)。因为 j-i≥ 1，所以 S＜ k，
这与 k是使得?x,yRk的最小正整数的假设相矛盾。故 k≤ n。
所以 Rk?R∪ R2∪ R3∪? ∪ Rn，从而有
x,yR∪ R2∪ R3∪? ∪ Rn
t(R)?R∪ R2∪ R3∪? ∪ Rn
第 4章 二元关系显然,R∪ R2∪ R3∪? ∪ Rn?R∪ R2∪ R3∪? = t(R)，即
R∪ R2∪ R3∪? ∪ Rn?t(R)。
于是 t(R)=R∪ R2∪ R3∪? ∪ Rn
除了用关系的复合运算计算传递闭包外,还可以用关系矩阵求传递闭包 。 请看下列的例题 。
【 例 4.18】 设 A=?1,2,3?,定义 A上的二元关系 R为：
R=1,2?,?2,3?,?3,1试用关系矩阵求传递闭包 t(R)。
解：用 关系矩阵求 t(R)的方法如下：
001
100
010
RM
第 4章 二元关系
010
001
100
001
100
010
001
100
010
2 RRR MMM
100
010
001
001
100
010
010
001
100
23 RRR MMM
111
111
111
32)( RRRRt MMMM
其中,∨ 表示矩阵的对应元素进行析取运算 。
第 4章 二元关系定理 4.4.6设 R?X× X，则 (R∪ IX)n= (R∪ R2∪? ∪ Rn )∪ IX
证明,用数学归纳法证明：
当 n=2时，
(R∪ IX)2=(R∪ IX)(R∪ IX)=((R∪ IX)°R)∪ ((R∪ IX)°IX)
=(R°R)∪ (IX°R)∪ (R∪ IX)
=R2∪ R∪ R∪ IX=R2∪ R∪ IX=(R∪ R2)∪ IX
设 n=k时,(R∪ IX)k=(R∪ R2∪ R3∪? ∪ R k)∪ IX，
证明 n=k+1时,(R∪ IX)k+1=(R∪ R2∪? ∪ R k∪ R k+1)∪ IX
(R∪ IX)k+1=(R∪ IX)k°(R∪ IX)
=(R∪ R2∪ R3∪? ∪ R k∪ IX)°(R∪ IX)
=((R∪ R2∪ R3∪? ∪ R k∪ IX)°R)∪
((R∪ R2∪ R3∪? ∪ Rk∪ IX)°IX)
=(R2∪ R3∪? ∪ R k∪ R k+1∪ R)∪
(R∪ R2∪ R3∪? ∪ R k∪ IX)
=(R∪ R2∪ R3∪? ∪ R k∪ R k+1)∪ IX
第 4章 二元关系二元关系的闭包仍然是二元关系，还可以求它的闭包。
例如,R是 A上的二元关系,r(R)是它的自反闭包，还可以求
r(R)的对称闭包。 r(R)的对称闭包记为 s(r(R))，简记为 sr(R)，
读做 R的自反闭包的对称闭包。类似的,R的对称闭包的自反闭包 r(s(R))简记为 rs(R),R的对称闭包的传递闭包 t(s(R))，
简记为 ts(R),
通常用 R*表示 R的传递闭包的自反闭包 rt(R)，读作,R
星,。在研究形式语言和计算模型时经常使用 R*。
定理 4.4.7 设 R?X× X，则
⑴ rs(R)=sr(R)
⑵ rt(R)=tr(R)
⑶ st(R)?ts(R)
证明,⑴ rs(R)=r(s(R))=r(R∪ RC)=(R∪ RC)∪ IX
=(R∪ RC)∪ IX∪ IX=(R∪ IX)∪ (RC∪ IX)
=(R∪ IX)∪ (R∪ IX)C= s(R∪ IX)= sr(R)
第 4章 二元关系
⑵ tr(R)=t(r(R))= t(R∪ IX)
= =
=
= = t(R)∪ IX= rt(R)
⑶ 留给读者证明。
1
)(
i
i
XIR
1 1
)(
i X
i
j
j IR
1 11
)()(
i i X
i
j
j IR
Xi
i IR
1
返回章目录第 4章 二元关系
4.5 等价关系等价关系是最重要,最常见的二元关系之一 。 它有良好的性质 。 在计算机科学和计算机技术,信息科学和信息工程中都有广泛的应用 。 目前对等价关系的研究是深入而完备的 。 本节介绍等价关系的主要结论 。
定义 4.5.1 设 R?X× X,如果 R是自反的,对称的和传递的,则称 R是 X上的等价关系 。 设 R是等价关系,若
x,yR,称 x等价于 y。
因为等价关系是自反的和对称的，所以等价关系的关系矩阵主对角线全为 1且是对称阵；其关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边。
第 4章 二元关系
【 例 4.19】 设 A=?1,2,3,4,5?,R是 A上的二元关系,
R=1,1?,?1,2?,?2,1?,?2,2?,?3,3?,?3,4?,?4,3?,?4,4?,?5,5，
证明 R是 A上的等价关系 。
证明,写出 R的关系矩阵 MR如下：
MR的主对角线全为 1且是对称阵,所以 R是自反的和对称的；还可以用二元关系传递性的定义证明 R是传递的 。 故 R
是 A上的等价关系 。
10000
01100
01100
00011
00011
R
M
第 4章 二元关系也可以用关系图说明 R是等价关系 。 图 4.9是 R的关系图 。 在 R的关系图中每一个结点上都有自回路；每两个结点间如果有边,一定有方向相反的两条边 。 所以 R是自反的和对称的 。 与前面一样,
也可以用二元关系传递性的定义证明 R是传递的 。 故 R是 A上的等价关系 。
从图 4.9不难看出,等价关系 R
的关系图被分为三个互不连通的部分 。 每部分中的结点两两都有关系,不同部分中的任意两个结点则没有关系 。
第 4章 二元关系设 x和 y是两个整数,k是一个正整数,若 x,y用 k除的余数相等,就称 x和 y模 k同余,也称 x和 y模 k的的等价 。 记为 x ≡ y mod k
设 x(y)用 k除的商为 t1 ( t2 ),余数为 a1 ( a2 ),数学上将
x(y)表示成为：
x= k× t1＋ a1,t1?I,a1?I且 0≤ a1＜ k。
y= k× t2＋ a2,t2?I,a2?I且 0≤ a2＜ k。
若 x,y用 k除的余数相等,x-y= k× (t1-t2),t1-t2?I。
即 x-y可以被 k整除 。 所以,x和 y模 k同余还可以描述为,x-y可以被 k整除 。
第 4章 二元关系
【 例 4.20】 设 R=x,y x?I∧ y?I∧ x ≡ y mod k?是整数集合 I上的二元关系 。 证明 R是等价关系 。
证明,设 a,b,c是任意的整数 。
⑴ 因为 a-a=k× 0,所以 a≡a mod k,?a,aR。 故
R是自反的 。
⑵ 若?a,bR,a ≡ b mod k,a-b = k× t,t?I,b-a
=-(a-b)=k× (–t),–t?I,b≡a mod k,?b,aR。 故 R是对称的 。
⑶ 若?a,bR且?b,cR，
a-b = k× t1,t1?I,b-c = k× t2,t2?I，
a-c=(a-b)+(b-c)=k× t1+k× t2=k× (t1+t2),t1+t2?I,
a,cR,故 R是传递的 。
所以 R是整数集合 I上的等价关系 。
第 4章 二元关系定义 4.5.2 设 R是 X上的等价关系,?x?X,集合
y? y?X∧ xRy?
叫做 x形成的 R等价类 。 记为 [x]R
在例 4.19中,等价关系 R等价类为,[1]R=[2]R=?1,2?，
[3]R=[4]R=?3,4?,[5]R=?5?。 在 R的关系图 (图 4.9)中,三个互不连通的部分,每一部分中的所有结点构成一个等价类 。
上述模 3等价关系的等价类叫模 3等价类,模 3等价类有以下三个：
[0]R=,–6,–3,0,3,6,…?
[1]R=?…,–5,–2,1,4,7,…?
[2]R=?…,–4,–1,2,5,8,…?
定理 4.5.1 设 R是 X上的等价关系,?x?X,则有
⑴ [x]R?X
⑵ x?[x]R
定理证明留作练习 。
第 4章 二元关系从定理 4.5.1可以看出,等价关系的任何等价类是该等价关系前域 (或陪域 )的子集 。 例如,模 3等价类是整数集合的子集,[0]R?I,[1]R?I,[2]R?I。
从定理 4.5.1还可以看出,任何等价类是非空集合 。 x形成的 R等价类 [x]R至少有一个元素 x。 例如,在模 3等价类中,
0?[0]R,1?[1]R,2?[2]R。
定理 4.5.2 设 R是 X上的等价关系,对于 X的任意元素 a和 b，
aRb 的充分必要条件是 [a]R=[b]R
证明,设 aRb,下证 [a]R=[b]R
c?[a]R,aRc,由 R的对称性有 cRa,由条件 aRb和 R的传递性得 cRb,再根据 R的对称性有 bRc,c?[b]R,故 [a]R?[b]R。
类似地可以证明 [b]R?[a]R。 这就证明了 [a]R=[b]R。
设 [a]R=[b]R,下证 aRb。
由定理 4.5.1知 a?[a]R,因为 [a]R=[b]R,所以 a?[b]R,bRa，
由 R的对称性有 aRb。
第 4章 二元关系定义 4.5.3 设 R是 X上的等价关系,R的所有等价类组成的集合?[x]R?x?X?叫做 X关于 R的商集 。 记为 X/R。
在例 4.19中,等价关系 R 有三个等价类,[1]R=[2]R=?1,2?，
[3]R=[4]R=?3,4?,[5]R=?5?,A关于 R的商集
A/R=?[1]R,[2]R,[5]R?=1,2?,?3,4?,?5
模 3等价关系 R的等价类有以下三个,[0]R,[1]R和 [2]R，
由它确定的整数集合 I关于 R的商集 I/R=?[0]R,[1]R,[2]R?。
定理 4.5.3 设 R是 X上的等价关系,X关于 R的商集 X/R是 X
的一个划分 。
证明,⑴ 由定理 4.5.1知,[x]R?X且 [x]R≠?。
⑵ 证明 = X。 因为 [x]R?X,所以?X。
另一方面,x?X,由定理 4.5.1知,x?[x]R?,
x?,所以,X? 。 故 =X
Xx Rx? ][
Xx Rx? ][
Xx Rx? ][?Xx Rx? ][
Xx Rx? ][
Xx Rx? ][
第 4章 二元关系
⑶ 证明商集 X/R中的元素是两两互不相交的 。
设 [a]R≠ [b]R,证明 [a]R∩ [b]R =?
假定 [a]R∩ [b]R≠?
c?[a]R∩ [b]R
c?[a]R∧?c?[b]R
aRc∧ bRc?aRc∧ cRb (因为 R是对称的 )
aRb (因为 R是传递的 )
[a]R=[b]R (定理 4.5.2)
与假定矛盾 。
所以 [a]R∩ [b]R＝?
第 4章 二元关系定理 4.5.4 设 S=?S1,S2,?,Sm?是 X的一个划分,
R=x,y?| x和 y在同一个划分块中?，
则 R是 X上的等价关系 。
证明,⑴ 设 x?X=S1∪ S2∪? ∪ Sm,因为 S是 X的一个划分,所以存在惟一的划分块 Sj?S,使 x?Sj,于是有?x,xR，
即 R是自反的 。
⑵ 设?x,yR,x和 y在某个划分块 Sj中,则 y和 x也在划分块 Sj中,所以?y,xR,即 R是对称的 。
⑶ 设?x,yR∧?y,zR?x和 y在 Si中且 y和 z在 Sj中?
y?Si∩ Sj≠?,因为 S是 X的一个划分,其中元素两两互不相交,故必有 Si=Sj?x和 z在 Sj中x,zR,即 R是传递的 。
将定理 4.5.4中的等价关系 R叫做划分 S导出的等价关系 。
划分 S导出的等价关系 R也可以表示为：
R =(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)
第 4章 二元关系
【 例 4.21】 设 X=?1,2,3,4?,X的划分 S=1?,?2,3?，
4,试写出 S导出的等价关系 R。
解,R=1,1?,?2,2?,?2,3?,?3,2?,?3,3?,?4,4
=?1?×?1?∪?2,3?×?2,3?∪?4?×?4?
可以验证 R是 X上的等价关系 。
定理 4.5.5 设 R,S集合 X上的等价关系,则 R=S 当且仅当 X/R=X/S
证明,⑴ 设 R=S,证明 X/R=X/S。
先证?x?X,[x]R=[x]S
a?[x]R?xRa?xSa?a?[x]S,所以 [x]R?[x]S。
类似地可以证明 [x]S?[x]R,这就证明了 [x]R=[x]S。
第 4章 二元关系再证 X/R=X/S。
[x]R?X/R,[x]R=[x]S?X/S,即 [x]R?X/S,所以 X/R?X/S。
类似地可以证明 X/S?X/R,于是 X/R=X/S。
⑵ 设 X/R=X/S,证明 R=S。
因为 X/R=X/S,[a]R?X/R,必存在 [c]S?X/S,使 [a]R=[c]S
a,bR?aRb?b?[a]R?b?[a]R∧ a?[a]R
b?[c]S∧ a?[c]S
cSb∧ cSa?bSc∧ cSa (因为 S是对称的 )
bSa (因为 S是传递的 )
aSb (因为 S是对称的 )
a,bS
所以 R? S。
类似地可以证明 S?R,于是 R=S。
第 4章 二元关系
【 例 4.22】 设 X=?1,2,3?,写出集合 X上的所有等价关系 。
解,先写出集合 X上的所有划分,它们是：
S1=1,2,3,S2=1,2?,?3,S3=1,3?,?2
S4=2,3?,?1,S5=1?,?2?,?3
对应的等价关系为：
R1=?1,2,3?×?1,2,3?=X× X
R2=?1,2?×?1,2?∪?3?×?3?
=1,1?,?1,2?,?2,1?,?2,2?,?3,3
R3=?1,3?×?1,3?∪?2?×?2?
=1,1?,?1,3?,?3,1?,?3,3?,?2,2
R4=?2,3?×?2,3?∪?1?×?1?
=2,2?,?2,3?,?3,2?,?3,3?,?1,1
R5=?1?×?1?∪?2?×?2?∪?3?×?3?
=1,1?,?2,2?,?3,3=IX
第 4章 二元关系
4.6 相容关系定义 4.6.1 设 R?X× X,如果 R是自反的和对称的,则称 R是 X上的相容关系 。
根据定义 4.6.1,相容关系有以下三个性质：
① 所有等价关系都是相容关系 。
② 相容关系的关系矩阵主对角线全为 1且是对称阵 。
③ 相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边,一定有方向相反的两条边 。
返回章目录第 4章 二元关系
【 例 4.23】 设 A=?316,347,204,678,770?,A上的二元关系
R定义为,R=x,y?| x?A∧ y?A∧ x和 y有相同数码?,证明 R
是 A上的相容关系 。 写出关系矩阵和关系图 。 用关系矩阵和关系图验证 R是 A上的相容关系 。
证明,⑴ 集合 A中的每个数自己和自己有相同数码,故 R
是自反的；对于集合 A中任意 x和 y,如果 x和 y有相同数码,则
y和 x也有相同数码 。 故 R是对称的 。 于是,R是相容关系 。
令 a=316,b=347,c=204,d=678,e=770
用列举法将 R表示为：
R=a,a?,?a,b?,?a,d?,?b,a?,?b,b?,?b,c?,?b,d?,
b,e?,?c,b?,?c,c?,?c,e?,?d,a?,?d,b?,?d,d?,
d,e?,?e,b?,?e,c?,?e,d?,?e,e
=a,b?,?a,d?,?b,a?,?b,c?,?b,d?,?b,e?,?c,b?,?c,e?,
d,a?,?d,b?,?d,e?,?e,b?,?e,c?,?e,d∪ IA
第 4章 二元关系
11110
11011
10110
11111
01011
R
M
R的关系矩阵 MR主对角线全为 1且是对称阵，说明 R是相容关系。
R的关系图如图 4.10所示 。 在关系图中,每一个结点上都有自回路且每两个结点间如果有边,
一定有方向相反的两条边 。 表明了 R是相容关系 。
第 4章 二元关系因为相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边,一定有方向相反的两条边 。 所以可省去每一个结点上的自回路,将两个结点间方向相反的两条有向边改为一条无向边,得到一个简化图 。 此图叫做 R的简化关系图 。 例 4.23中的相容关系 R的简化关系图如图 4.11所示 。
第 4章 二元关系定义 4.6.2 设 R是 X上相容的关系,C?X,如果?a,b?C，
有?a,bR,则称 C是由相容关系 R产生的相容类 。
如果 R是 X上的相容关系,C是由相容关系 R产生的相容类 。 从定义可以看出：
① 相容类 C一定是 X的子集 。
②?x?X,因为相容关系 R是自反的,?x,xR,所以?x?
是由相容关系 R产生的一个相容类 。 即 X中的任何元素组成的单元素集是由相容关系 R产生的一个相容类 。
在例 4.23中,
a?,?a,b?,?b,c?,?b,d,e?都是 R产生的相容类 。
a,b?∪?d?=?a,b,d?和
b,c?∪?e?=?b,c,e?也是 R产生的相容类 。
但是?b,d,e?与任何非空集合的并集都不再是 R产生的相容类,这种相容类叫做最大相容类 。
第 4章 二元关系定义 4.6.3 设 R是 X上的相容关系,C是 R产生的相容类 。
如果它不是其它任何相容类的真子集,则称 C为最大相容类 。
记为 CR。
根据定义 4.6.3,最大相容类 CR具有如下的性质：
① CR中任意元素 x与 CR中的所有元素都有相容关系 R。
② X-CR中没有一个元素与 CR中的所有元素都有相容的关系 R。
性质 ① 的意思是,CR是 R产生的相容类,即最大相容类首先是相容类 。 性质 ② 的意思是,CR是最大相容类 。
利用相容关系的简化关系图可以求最大相容类,方法如下：
① 最大完全多边形的顶点构成的集合是最大相容类 。
② 孤立点构成的集合是最大相容类 。
③如果一条边不是任何完全多边形的边，则它的两个端点构成的集合是最大相容类。
第 4章 二元关系
【 例 4.24】 设 X=?1,2,3,4,5,6?，
R是 X上的相容关系,它的简化关系图如图 4.12所示,试找出所有最大相容类 。
解,最大完全 3边形的顶点构成的集合,?2,3,5?和?2,3,4?。
孤立点构成的集合,?6?。
不是任何完全多边形的边的两个端点构成的集合?1,5?。
所以,最大相容类为,
2,3,5?,?2,3,4?,?1,5?和?6?。
第 4章 二元关系定理 4.6.1 设 R是有限集合 X上的相容关系,C是 R产生的相容类,那么必存在最大相容类 CR,使得 C?CR。
证明,设 X=?x1,x2,?,xn?,令 C0=C。
如下构造相容类序列,C0?C1?C2
Ci+1=Ci∪?xj?
其中,j是使 xj?Ci 且 xj与 Ci的每一个元素都有相容关系 R的 x的最小下标 。
因为 |X|=n,所以至多经过 n-|C|步,可结束此过程 。
序列的最后一个集合就是要求的最大相容类 CR。
第 4章 二元关系定理 4.6.2 设 X是有限集合,R是 X上的相容关系,由 R产生的所有最大相容类构成的集合是 X的覆盖 。
证明,设 R产生的所有最大相容类构成的集合为,?C1,
C2,?,Cn?
⑴ 由相容类的定义知,任何最大相容类 Ci都是 X的子集 。
⑵ 证明 X= C1∪ C2∪? ∪ Cn
因为 Cj? X,所以 C1∪ C2∪? ∪ Cn? X。
x?X,?x?是相容类,根据定理 4.6.1,必存在最大相容类 Ci使得?xCi,而 Ci?C1∪ C2∪? ∪ Cn，
所以 x?C1∪ C2∪? ∪ Cn，
这就证明 X?C1∪ C2∪? ∪ Cn
故 X=C1∪ C2∪? ∪ Cn
第 4章 二元关系定义 4.6.4设 R是 X上的相容关系,S=?R产生的最大相容类?叫做集合 X的完全覆盖,记为 CR(X)。
例如,在例 4.24中最大相容类构成的集合为2,3,5?，
2,3,4?,?1,5?,?6,它是集合 X=?1,2,3,4,5,6?的一个完全覆盖 。 根据相容关系和相容类的定义,X中的任何元素组成的单元素集是由相容关系 R产生的一个相容类 。 所以
1?,?2?,?3?,?4?,?5?,?6? 都 是 相 容 类,集合
1?,?2?,?3?,?4?,?5?,?6是 X的覆盖 。 即完全覆盖是 X的覆盖,某些相容类构成集合也是 X的覆盖 。 所以由相容关系 R
产生的相容类构成的 X的覆盖并不惟一 。 但是一个相容关系只对应惟一的一个完全覆盖 。
第 4章 二元关系定理 4.6.3 设 S=?S1,S2,?,Sm?是 X的一个覆盖,则
R=(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)是 X上的相容关系 。
证明,⑴ x?X,因为 S是 X的一个覆盖,存在 Si?S,使
x?Si,于是有
x,xSi× Si?(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)=R,即
x,xR,所以 R是自反的 。
⑵ 设?x,yR=(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)，
x,ySi× Si,?y,xSi× Si，
而 Si× Si?(S1× S1)∪ (S2× S2)∪? ∪ (Sm× Sm)=R,即?y,xR，
所以 R是对称的 。
将定理 4.6.3中的 R叫做覆盖 S导出的相容关系 。
第 4章 二元关系
【 例 4.25】 设 X=?1,2,3,4?,S1=1,2,3?,?3,4，
S2=1,2?,?2,3?,?1,3?,?3,4是 X的两个覆盖 。 试写出 S1和 S2
导出的相容关系 R1和 R2。
解,R1=?1,2,3?×?1,2,3?∪?3,4?×?3,4?
=1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?2,3?,
3,1?,?3,2?,?3,3?,?3,4?,?4,3?,?4,4
R2=?1,2?×?1,2?∪?2,3?×?2,3?
∪?1,3?×?1,3?∪?3,4?×?3,4?
=1,1?,?1,2?,?2,1?,?2,2?,?2,3?,?3,2?,
3,3?,?1,3?,?3,1?,?3,4?,?4,3?,?4,4
在例 4.25中,S1≠ S2,但是 R1=R2。 这说明不同的覆盖可以导出相同的相容关系 。
定理 4.6.4 集合 X上的相容关系 R与集合 X的完全覆盖
CR(X)是一一对应的 。
证明留作作业 。
返回章目录第 4章 二元关系
4.7序关系
4.7.1偏序关系与哈斯图定义 4.7.1设 R?X× X,如果 R是自反的,反对称的和传递的,则称 R是 X上的偏序关系 。 记为?。 二重组?X,称为偏序集 。 如果?x,y,记为 x?y,读作 x小于等于 y。
【 例 4.26】 设 A是集合,P (A)是 A的幂集合,P (A)上的包含关系?定义如下：
=x,yx?P (A)∧ y?P (A)∧ x?y?
试证明?是 P (A)上偏序关系 。
证明,⑴?x?P(A),x?x,?x,x。 即?是自反的 。
⑵ 设?x,y∧?y,x,由包含关系?定义有 x?y∧
y?x,根据集合相等的定义,x=y。 即?是反对称的 。
⑶ 设?x,y∧?y,z,由包含关系?的定义有 x?y∧
y?z,根据集合包含的传递性,x?z,再由包含关系?定义有
x,z,即?是传递的 。是 P(A)上偏序关系 。
第 4章 二元关系另外,任意集合 A上的恒等关系 IA是自反的,反对称的和传递的,IA是 A上偏序关系；实数集合上的小于等于关系
(参看例 4.10)也是自反的,反对称的和传递的,它是实数集合上的偏序关系 。
定义 4.7.2 设?X,为偏序集,对 X中的元素 x和 y,如果
x?y,x≠ y且没有 X中的其它元素 z使 x?z和 z?y,则称 y盖住了 x。
【 例 4.27】 设 A=?2,5,6,10,15,30?,A上的整除关系 R定义如下：
R=x,yx?A∧ y?A∧ x整除 y?
验证 R是 A上的偏序关系，分析哪些元素盖住了另一些元素，
哪些元素没有盖住了另一些元素。
第 4章 二元关系解,因为 A的任何元素都能整除它自己,所以 R是自反的；
当 x整除 y且 y整除 x时,一定有 x=y,所以 R 是反对称的；当 x整除 y且 y整除 z,x一定整除 z,所以 R 是传递的 。 即 R是 A上的偏序关系 。
用列举法将 R表示为：
R=2,2?,?2,6?,?2,10?,?2,30?,?5,5?,?5,10?,
5,15?,?5,30?,?6,6?,?6,30?,?10,10?,?10,30?,
15,15?,?15,30?,?30,30
6和 10盖住了 2；但 30没有盖住了 2,因为?2,6R和
6,30R。
10和 15盖住了 5；但 30没有盖住了 5,因为?5,10R和
10,30R。
30盖住了 6,10和 15。
第 4章 二元关系定义 4.7.3设?X,为偏序集,集合
x,yx?X∧ y?X∧ y盖住了 x?
叫做 X上的盖住关系 。 记为 COV X。
设 COV X是 X上的盖住关系,如果?x,yCOV X,根据定义 4.7.3,y盖住了 x,由定义 4.7.2知,x?y,即?x,y。
故 COV X。 所以任何盖住关系 COV X都是相应偏序关系
的子集 。
在例 4.27中,偏序集?A,R?的盖住关系
COV A =2,6?,?2,10?,?5,10?,?5,15?,
6,30?,?10,30?,?15,30
第 4章 二元关系设?X,是偏序集，它的盖住关系 COV X是惟一的。
所以可以利用盖住关系做一图，表示该偏序集?X,。这个图叫做哈斯图。偏序集?X,的哈斯图的画法如下：
① 用,°” 表示 X中的每一个元素。
② 如果 x?y，则将 x画在 y的下方。
③ 若?x,yCOV X，则在 x和 y间画一条直线。
例 4.27的哈斯图是图 4.13。
第 4章 二元关系
【 例 4.28】 设 A=?a,b?,B=P (A)=,?a?,?b?,?a,b是 A
的幂集合,幂集合 P (A)上的包含关系
R?=x,y?| x?P (A)∧ y?P (A)∧ x?y?
试写出盖住关系 COVP (A),画出它的哈斯图 。
解,用列举法将 R?表示为
R?=,?a,,?b,,?a,b,a?,?a,b,
b?,?a,b∪ IB
在例 4.26中,已证 R?是 P (A)上的偏序关系 。 P (A)上的盖住关系为
COV P (A)=,?a,,?b,a?,?a,b,
b?,?a,b
哈斯图如图 4.14所示 。
第 4章 二元关系定义 4.7.4 设?X,是偏序集,B?X,b?B,如果 B中没有任何元素 x满足 x≠ b且 b?x(x?b),则称 b是 B的极大元
(极小元 )。
当 B=X时,B的极大元 (极小元 )称为偏序集?X,的极大元 (极小元 )。
第 4章 二元关系
【 例 4.29】 设 A=?a,b,c,d,e,f,g,h?,A上的二元关系
R=b,d?,?b,e?,?b,f?,?c,d?,?c,e?,?c,f?,?d,f?,?e,f?,?g,h∪ IA
验证 R是 A上的偏序关系 。 写出盖住关系 COV A,画出哈斯图 。
找出集合 A的极大元和极小元 。
解,容易验证 R是自反的,反对称的和传递的,R是 A上的偏序关系 。
COV A=b,d?,?b,e?,?c,d?,?c,e?,?d,f?,?e,f?,?g,h
哈斯图如图 4.15所示 。
集合 A的极大元是,a,f,h。
集合 A的极小元是,a,b,c,g。
第 4章 二元关系由定义 4.7.4和例 4.29可以得出以下结论：
① 孤立点既是极大元又是极小元 。
② 极大元和极小元不惟一 。 有限集合 B的极大元和极小元一定存在 。
③ 在哈斯图中,如果集合 B的某个元素不存在 B的其它元素从上 (下 )方与其相通,则该元素就是 B的极大元 (极小元 )。
定义 4.7.5 设?X,是偏序集,B?X,b?B,如果对任意 x?B,都有 x?b(b?x),则称 b是 B的最大元 (最小元 )。
当 B=X时,B的最大元 (最小元 )称为偏序集?X,的最大元 (最小元 )。 在例 4.29中,集合 A没有最大元和最小元 。
在例 4.28中,令 B=,?a,B的最大元是?a?,B的最小元是?。 令 B=a?,?b,B没有最大元和最小元 。
第 4章 二元关系定理 4.7.1 设?X,是偏序集,B?X,如果 B有最大元
(最小元 ),则必惟一 。
证明,设 a,b都是 B的最大元,由 a是 B的最大元得 b?a，
由 b是 B的最大元得 a?b,因为?是反对称的,所以 a=b。 即 B
的最大元惟一 。
类似地可证明最小元惟一 。
从以上例题和定理 4.7.1可以得出以下结论：
① 最大元和最小元不一定存在 。 如果存在,一定惟一 。
② 在哈斯图中,如果集合 B的某个元素向下 (上 )通向 B的所有元素,则该元素就是 B的最大元 (最小元 )。
定义 4.7.6 设?X,是偏序集,B?X,b?X,对任意 x?B，
都有 x?b(b?x),则称 b是 B的上界 (下界 )。
第 4章 二元关系
【 例 4.30】 设 A=?2,3,6,12,24,36?,其上的整除关系
R=a,b a?A∧ b?A∧ a能整除 b?
是 A上的偏序关系,试求盖住关系 COV A,画出哈斯图,确定下列集合的上界和下界 。
⑴ B1=?2,3,6?
⑵ B2=?12,24,36?
解,用列举法将 R表示为：
R=2,6?,?2,12?,?2,24?,?2,36?,?3,6?,?3,12?,?3,24?,
3,36?,?6,12?,?6,24?,?6,36?,?12,24?,?12,36∪ IA
盖住关系 COV A=2,6?,?3,6?,?6,12?,?12,24?,?12,36
第 4章 二元关系哈斯图如图 4.16所示 。
B1的上界是 6,12,24,36。 没有下界 。
B2的下界是 2,3,6,12。 没有上界 。
从本例可以看出：
① 上界和下界并不惟一 。
② 在哈斯图中,如果集合 X的某个元素向下 (上 )通向 B的所有元素,则该元素就是 B的上界 (下界 )。
定义 4.7.7设?X,是偏序集,B?X,如果存在 B的一个上界 (下界 )b,对 B的任意一个上界 (下界 )y,都有 b?y(y?b)，
则称 b是 B的最小上界 (最大下界 )。 也叫上确界 (下确界 )。 记为 LUB B (GLB B)。
在例 4.30中 B1的最小上界是 6； B1无下界,当然无最大下界 。 B2的最大下界是 12； B2无上界,当然无最小上界 。
第 4章 二元关系
4.7.2全序关系与良序集关系定义 4.7.8 设?X,为偏序集,如果?x?X,?y?X,都有 x?y或 y?x,则称偏序集?X,为全序集,也称为线序集 。
偏序关系?称为 X上的全序关系或线序关系 。
【 例 4.31】 设 N为自然数集合,N上的大于等于关系定义为
R≥ =x,yx?N∧ y?N∧ x≥ y?
证明 R≥ 是全序关系 。
证明,?x?N,x≥ x,?x,xR≥ 。 所以 R≥ 是自反的 。
当?x,yR≥ 且?y,xR≥,有 x≥ y且 y≥ x,从而 x=y。 所以 R≥ 是反对称的 。
当?x,yR≥ 且?y,zR≥,有 x≥ y且 y≥ z,则 x≥ z,即
x,zR≥ 。 所以 R≥ 是传递的 。
第 4章 二元关系综上所述,R≥ 是 N上的偏序关系 。
x?N,?y?N,必有 x≥ y或 y≥ x,即
x,yR≥ 或?y,xR≥,R≥ 是 N上的全序关系 。 其盖住关系为：
COV N=1,0?,?2,1?,?3,2?,
其哈斯图是图 4.17。
第 4章 二元关系
【 例 4.32】 设 P=a?,?a,b?,?a,b,c,P
上的包含关系
R?=x,yx?P∧ y?P∧ x?y?
验证 R?是全序关系 。
解,用列举法将 P上的包含关系 R?表示为：
R?=,?a,,?a,b,,?a,b,c,
a?,?a,b,a?,?a,b,c,
a,b?,?a,b,c∪ IP
容易验证 R?是 P上的偏序关系 。
从 R?的定义可以看出,对于 P中的任意两个元素 x和 y,必有 x?y或 y?x,所以 R?是 P上的全序关系 。 其盖住关系为：
COV P=,?a,a?,?a,b,
a,b?,?a,b,c
哈斯图如图 4.18所示 。
第 4章 二元关系定义 4.7.9 设?X,为偏序集,如果 X的每一个非空子集存在最小元,则偏序集?X,叫做良序集 。 偏序关系?称为
X上的良序关系 。
类似例 4.31可以证明自然数集合 N上的小于等于关系是偏序关系,而自然数集合的每一个非空子集都存在最小数 。
所以自然数集合上的小于等于关系?N,R≤?是良序集 。
定理 4.7.2 每一个良序集,一定是全序集 。
证明,设?X,是良序集,x和 y是 X中的任意两个元素,
显然?x,yX,由良序集的定义知,集合?x,y?必有最小元,
即 x是最小元或 y是最小元,如果 x是最小元,则有 x?y。 如果 y是最小元,则有 y?x。 所以?X,是全序集 。
第 4章 二元关系定理 4.7.3 有限全序集,一定是良序集 。
证明,设 X=?a1,a2,?,an?,? X,是全序集 。 下证
X,是良序集 。
设 B是 X的任意子集 。 因为 X是有限集,所以 B也是有限集,且 B中任意两个元素有关系?。 用以下方法可以找出 B
的最小元：
① 取 B的两个元素 x和 y,由于?X,是全序集,必有
x?y或 y?x,如果是前者选 x；如果是后者选 y。 记为 a。
② 再在 B中取没有选过的元素 b,则 a?b或 b?a,若为前者选 a；若为后者选 b。 记为 a′。
这个工作一直进行下去,直到 B中的元素选完 。 记最后选出来的元素为 c,因为关系?是传递的,所以 c是 B的最小元 。 所以?X,是良序集 。
返回总目录返回章目录
