第四章 关 系
4.1 二元关系
4.2 关系运算
4.3 关系类型退出
4.1 二元关系二元关系,这里是指集合中两个元素之间的关系 。
1,基本概念定义 4.1.1 给定任意集合 A和 B,若 R?A?B，
则称 R为从 A到 B的二元关系,特别在 A=B时,称 R
为 A上的二元关系 。
可见,R是有序对的集合。若 <x,y>?R,则也表为 xRy,即 <x,y>?R?xRy。
若 R=?,则称 R为 A到 B上空关系；若 R=A?B，
称 R为 A到 B上全域关系。特别当 A=B时，称?为 A
上空关系，称 R=A?A为 A上的全域关系。称
R={<x,x>|x?A}为 A上的恒等关系，记为 IA。
类似地可定义 n元关系。若 S? Ai,则称 S
为 Ai上的 n元关系。特别 A1=A2=···=An时，称
S为 A上的 n元关系。
定义 4.1.2 令 R?A?B,且
D(R)={x|(?y)(xRy)}
R(R)={y|(?x)(xRy)}
F(R)=D(R)+R(R)
则称 D(R),R(R)和 F(R)分别是二元关系 R
的定义域、值域和域。
显然 D(R)?A,R(R)?B。
由于关系是有序对的集合，对它可进行集合运算，其结果也是有序对的集合，
即也是某一种二元关系。令 R和 S是两个二元关系，则 R∪ S,R∩ S,R-S,R?S和 R’
都分别定义了某一种二元关系，并且可表成：
x(R∪ S)y?xRy?xSy
x(R∩ S)y?xRy?xSy
x(R-S)y?xRy?xSy
x(R?S)y?xRy?xSy
xR ’y?xRy
2．关系矩阵与关系图表达从有穷集合到有穷集合的二元关系时
，矩阵和有向图都是得力的工具。
定义 4.1.3 给集合 A={a1,a2,··,am}和
B={b1,b2,··,bn},且 R?A?B,若
1 aiRbj
rij=
0 否则则称矩阵 MR=(rij)m?n为 R的关系矩阵。
当给定关系 R,可求出关系矩阵 MR；反之,
若给出关系矩阵 MR,也能求出关系 R。
集合 A上的二元关系 R也可用有向图表示 。
具体方法是：用小圆圈,?” 表示 A中的元素,
小圆圈称为图的结点 。 把对应于元素 ai和 aj的结点,分别标记 ai和 aj。。 若 <ai,aj>?R,则用弧线段或直线段把 ai和 aj连接起来,并在弧线或直线上设置一箭头,使之由 ai 指向 aj ；若 <ai,
ai>?R,则在结点 ai上画一条带箭示的自封闭曲线或有向环,称这样的弧线或封闭曲线为弧或有向环 。 这样得到的有向图 <A,R>叫做关系 R的图示,简称关系图,记为 GR。
3,关系的性质关系的性质是指集合中二元关系的性质,
这些性质扮演着重要角色,下面将定义这些性质,并给出它的关系矩阵和关系图的特点 。
定义 4.1.4 令 R?A?A,若对 A中每个 x,都有 xRx,则称 R是自反的,即
A上关系 R是自反的?<?x)(x?A?xRx)
该定义表明了,在自反的关系 R中,除其他有序对外,必须包括有全部由每个 x?A所组成的元素相同的有序对 。
在全集 U中所有子集的集合中,包含关系?
是自反的,相等关系 =也是自反的；但是,真包含关系?不是自反的 。 整数集合 Z中,关系 ≤是自反的,而关系 <不是自反的 。
定义 4.1.5 令 R?A?A，若对于 A中每个 x，
有 xRx，则称 R是反自反的，即
A上关系 R是反自反的?<?x)(x?A?xRx)
该定义表明了，一个反自反的关系 R中，
不应包括有任何相同元素的有序对。
由定义 4.1.4 说明中,可知真包含关系?是反自反的,但包含关系?不是反自反的；小于关系 <是反自反的,而 ≤不是反自反的 。
应该指出,任何一个不是自反的关系,未必是反自反的；反之,任何一个不是反自反的关系,未必是自反的 。 这就是说,存在既不是自反的也不是反自反的二元关系 。
定义 4.1.6 令 R?A?A，对于 A中每个 x和 y，
若 xRy，则 yRx，称 R是对称的，即
A上关系 R是对称的
(? x )(? y )(x,y? A? x R y → y R x )
该定义表明了，在表示对称的关系 R的有序对集合中，若有有序对 <x,y>，则必定还会有有序对 <y,x>。
在全集 U的所有子集的集合中,相等关系是对称的,包含关系?和真包含关系?都不是对称的；在整数集合 Z中,相等关系 =是对称的,
而关系 ≤和 <都不是对称的 。
定义 4.1.7 令 R?A?A，对于 A中每个 x和 y，
若 xRy且 yRx，则 x=y，称 R是反对称的，即
A上关系 R是反对称的
(?x )(?y)(x,y?A?x R y?yR x→ x = y )
该定义表明了，在表示反对称关系 R的有序对集合中，若存在有序对 <x,y>和 <y,x>，则必定是 x=y。或者说，在 R中若有有序对 <x,y>，
则除非 x=y，否则必定不会出现 <y,x>。
在全集 U的所有子集的集合中,相等关系 =，
包含关系?和真包含关系?都是反对称的,但全域关系不是反对称的 。 在整数集合 Z中,=,≤和
<也都是反对称的 。
可见,有些关系既是对称的又是反对称的,
如相等关系；有些关系是对称的但不是反对称的,如 Z中的,绝对值相等,；有些关系是反对称的,但不是对称的,如 Z中的 ≤和 <。 还有的关系既不是对称的又不是反对称的,例如,A={a,
c,b>,中 R={<a,b>,<a,c>,<c,a>}。
定义 4.1.8 令 R?A?A，对于 A中每个 x,y,z，
若 xRy且 yRx，则 xRz，称 R是传递的，即
A上关系 R是传递的
(?x)(?y)(?z)(x,y,z?A?xRy?yRz→ xRz)
该定义表明了，在表示可传递关系 R的有序对集合中，若有有序对 <x,y>和 <y,z>，则必有有序对 <x,z>。
显然,上述提到的关系中?,?,=和 ≤,<，
=都是传递的；在直线的集合中,平行关系是传递的,但垂直关系不是传递的 。
通过上面几个实例,看出：
① 若 A上关系 R是自反的,则 MR中主对角线上元素全为 1,而 GR中每个结点有有向环；反之亦然 。
② 若 A上关系 R是反自反的，则 MR中主对角线上元素全为 0，而 GR中每个结点无有向环；
反之亦然。
③若 A上关系 R是对称的，则 MR是对称矩阵，而 GR中任何两结点若有弧必成对出现；反之亦然。
④ 若 A上关系 R是反对称的，则 MR中以主对角线为对称元素不能同时为 1，而 GR中若两结点间有弧不能成对出现；反之亦然。
⑤若 A上关系 R是传递的，则 MR中若
rij=rjk=1，则 rik=1，而 GR中若有弧 <x,y>和 <y,z>
则必有弧 <x,z>；反之亦然。上述是正确的，但不易从 MR和 GR中判定关系 R传递性。
此外，还有：
①任何集合上的相等关系 =是自反的、对称的，反对称的和传递的，但不是反自反的。
②整数集合 Z中，关系 ≤是自反的、反对称的和传递的，但不是反自反的和对称的。关系 <
是反自反的，反对称的和传递的，但不是自反的和对称的。
③ 非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，
反对称的和传递的。
④非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。
下面给出一个定理，以结束本小节。
定理 4.1.1 设 R?A?A，若 R是反自反的和传递的，则 R是反对称的。
4.2 关系运算前已述及，关系是有序对的集合，因此可以对关系进行运算。若 R,S?A?B，则 R∪ S，
R∩S,R’,R-S?A?B。
1．复合运算定义 4.2.1 设 R是从 A到 B的关系,S是从 B
到 C的关系。经过对 R和 S实行复合（或合成）
运算,?”，得到了一个新的从 A到 C的关系，
记为 R?S，也称 R?S为关系 R和 S的复合（或合成）关系；或称 R?S为 R和 S的复合运算。形式地表为：
R?S={<a,c>|(?b)(b?B?aRb?bSc)}
定理 4.2.1 设 R?A?A,则 R?IA=IA?R=R
定理 4.2.2 若 R?A?B,S,T?B?C,W?C?D,则
① R?(S∪ T)=R?S∪ R?T
② R?(S∩T)? R?S∩R?T
③ (S∪ T)?W=S?W∪ T?W
④ (S∩T)?W? S?W∩T?W
定理 4.2.3 若 R?A?B,S?B?C,T?C?D，
则
(R?S)?T=R?(S?T)
复合运算是可结合的,但不是可交换的 。
望读者举例说明 。
2,幂运算定义 4.2.2 设 R是集合 A上的二元关系,
n?N,R的 n次幂记为 Rn,定义为：
(1) R0=IA
(2) Rn+1=Rn?R
定理 4.2.4 若 R?A?A,且 m,n?N,则
(1) Rm?Rn=Rm+n，
(2) (Rm)n=Rmn。
定理 4.2.5 令 R?A?A,且 |A|=n,则存在 i和 j，
使得 Ri=Rj,其中 0≤i<j≤2n2。
定理 4.2.6 令 R?A?A,若存在 i和 j,i<j,使得 Ri=Rj。 且 d=j-i,则
(1) 对任意 k≥0,Ri+k=Rj+k。
(2) 对任意 k,m≥0,Ri+md+k=Ri+k。
(3) 设 S={R0,R1,R2,··,Rj+1},对?n?N,有
Rn?S。
3,逆运算定义 4.2.3 设 R是从 A到 B的二元关系,由关系 R得到一个新的从 B到 A的关系,记为 R-1,称
R-1为 R的逆运算,亦称 R-1为 R的逆关系 。 形式地表为
R-1={<y,x>|<x,y>?R}
或者 xRy?y R-1x
由定义可知,?-1=?,(A?B)-1=B?A
定理 4.2.7 若 R?A?B,S?B?C,则 (R?S)-
1=S-1?R-1
定理 4.2.8 令 R,S?A?B,则
① (R-1)-1=R
② D(R-1)=R(R),R(R-1)=D(R)
③ (R∪ S)-1= R-1∪ S-1
④ (R∩S)-1= R-1∩S-1
⑤ (R-S)-1= R-1-S-1
⑥ R?S?R-1?S-1
定理 4.2.9 若 R?A?A,则 R为对称?R=R-1。
4,闭包运算关系的闭包运算是关系上的一元运算,是包含该关系且具有某种性质的最小关系 。
定义 4.2.4 设 R是 A上的二元关系,R的自反
（对称、传递）闭包是关系 R1，则
① R1是自反的（对称的、传递的）
② R?R1
③ 对任何自反的（对称的、传递的）关系
R2，若 R?R2，则 R1?R2。
R的自反、对称和传递闭包分别记为 r(R)、
s(R)和 t(R)。
定理 4.2.10 若 R?A?A，则
① R是自反的 iff r(R)=R
② R是对称的 iff s(R)=R
③ R是传递的 iff t(R)=R
证明 只证明①，余下自证。
若 R是自反的，则由定义 4.2.4可知,R具有对 R1所要求的性质，故 r(R)=R；反之，若
r(R)=R，则由定义 4.2.4① 知,R是自反的。
由闭包的定义可以知道，构造关系 R的闭包方法就是向 R中加入必要的有序对，使其具有所希望的性质。下面定理体现了这一点。
定理 4.2.11 令 R?A?A，则
① r(R)=R∪ IA
② s(R)=R∪ R-1
③ t(R)=
定理 4.2.12 若 R?A?A,|A|=n,则 t(R)= 。
定理 4.2.13 若 R?A?A,则
① rs(R)=sr(R)
② rt(R)=tr(R)
③ st(R)?ts(R)
5,关系运算的矩阵表示关系运算是可以用关系矩阵表示的 。
设 R,S?A?B,T?B?C,MR=(aij)m?n,
MS=(bij)m?n,MT=(cij)n?p,dij表示运算后所得新关系之关系矩阵的元素,则
① MR∪ S=MR∪ MS dij=aij?bij
1≤i≤m,1≤j≤n
② MR∩S=MR∩MS dij=aij?bij
1≤i≤m,1≤j≤n
③ dij=?aji
1≤i≤m,1≤j≤n
④ MR-S=MR? dij=aij?(?bij)
1≤i≤m,1≤j≤n
⑤ =MRT dij=aij
1≤i≤m,1≤j≤n
⑥ MR?T=MR?MT dij= (aik?ckj)
1≤i≤m,1≤j≤n
4.3 关系类型关系类型在本书中主要讨论有四种,它们是等价关系,偏序关系,相容关系和次序关系 。
1,等价关系定义 4.3.1 设 R是集合 A上二元关系,若 R是自反的,对称的和传递的,则称 R为 A上的等价关系 。 若 <a,b>?R,或 aRb,称 a等价 b,记 a?b。
由于 R是对称的,a等价 b即 b等价 a,反之亦然,a与 b彼此等价 。
鉴于空集合中的二元关系是等价关系,是一种平凡情形,因此,一般讨论非空集合上的等价关系 。
模 m等价是 Z或其子集上的等价关系,并且是一类重要的等价关系 。
定义 4.3.2 设 m为一正整数而 a,b?Z。 若存在 m,使 a-b=km,则称 a与 b是模 m等价,记为
a?b(mod m)。
定理 4.3.1 模 m等价是任何集合 A?Z上的等价关系 R。
定义 4.3.3 设 R为非空集合 A上的等价关系,
对?a?A,令
[a]R={x|x?A?aRx}
称 [a]R为 a关于 R的等价类,简称 a的等价类,
简记为 [a]。
显然,等价类 [a]R非空,因为 a?[a]R。
定理 4.3.2 设 R是非空集合 A上的等价关系,
则
①?a,b?A,若 aRb,则 [a]=[b]。
②?a,b?A,若 aRb,则 [a]∩[b]=?。
③ =A
利用非空集合 A及其上等价关系可以构造一个新集合 —商集 。
定义 4.3.4 设 R是非空集合 A上的等价关系,
以及
A/R={[a]R|a?A}
则称 A/R为 A对 R的商集 。
该定义表明了,商集 A/R是以 R的所有等价类为元素的集合 。
与商集有密切联系的概念是集合的划分 。
下面给出划分的定义 。
定义 4.3.5 设 A 是非空集合,若
B={A1,A2,··,An},且 ① Ai,② Ai∩Aj=?,i?j，
③ =A,则称 B是 A的划分 。 称 B中元素为 A
的划分块 。
可见,商集 A/R就是 A的一个划分,并且不同的商集对应于不同的划分 。 反之,任给 A的一个划分,B={A1,A2,··,An},如下定义 A上的关系
R：
R=
或 R={<a,b>|(?Ai)(Ai?B?a,b?Ai)}
则不难证明 R是 A上的等价关系，且 A/R就是划分 B。因此，非空集合 A上的等价关系与 A
的划分是一一对应的。
2,偏序关系定义 4.3.6 设 R是非空集合 A上的关系,若 R
是自反的,反对称和传递的,则称 R为 A上的偏序关系 。 称有序对 <A,R>为偏序集 。
若 R是偏序,<A,R>常记为 <A,≦ >,为便于书写,将 ≦ 通常记为 ≤,读作,小于或等于,,
因为,小于或等于,也是一种偏序,故不会产生混乱 。 所以,R是偏序,aRb就表成 a≤b。
若 R是 A上的偏序，则 R-1也是 A上偏序。若用 ≤表示 R，则用 ≥表示 R-1； <A,≤>和 <A,≥>都是偏序集，并且互为对偶。
注意,a≤b是指在偏序关系中的顺序性，是将 a排在 b的前边或者 a即是 b。根据不同偏序的定义，对序有着不同的解释，如包含关系是偏序关系 ≤,A≤B（一般写成 A?B）是指 A包含于
B；整除关系是偏序关系 ≤,3≤6（通常记为 3|6）
是指 3整除 6等等。
定义 4.3.7 设 R是非空集合 A上的偏序关系，
定义
①?a,b?A,a<b?a≤b?a?b
②?a,b?A,a与 b是可比的?a≤b?b≤a
其中 a<b读作 a“小于” b，它是指在偏序中，
a排在 b的前边。
可见，在偏序集 <A,≤>中，对?a,b?A，有
a<b(或 b<a),a=b,a与 b不可比三种情况发生，例如 A={1,2,3},≤是 A上的整除关系，则有
1<2,1<3,
1=1,2=2,3=3，
2与 3不可比。
利用非空集合 A上偏序关系 R可以简化其关系图，
得到偏序集 <A,R>的哈斯 (Hass)图。为了给出其画法，
首先定义偏序集中元素的盖住关系。
定义 4.3.8 设 <A,≤>为偏序集。a,b?A，若
a<b且不存在 c?A，使得 a<c<b，则称 b盖住 a。
在画偏序集 <A,≤>的哈斯图时，首先适当排列 A中元素的顺序。对于?a,b?A，若 a<b，
则将 a画在 b的下方；其次考虑 b是否盖住了 a，
若 b盖住 a，则用一条线段连接 a和 b。
定义 4.3.9 设 <A,≤>为偏序集,B?A,b?B，
① 若 (?x)(x?B?b≤x)为真，则称 b为 B的最小元。
② 若 (?x)(x?B?x≤b)为真，则称 b为 B的最大元。
③ 若?(?x)(b?x?x≤b)为真，则称 b为 B的极小元。
④ 若?(?x)(b?x?b≤x)为真，则称 b为 B的极大元。
从本定义可知，最小元与极小元是有区别的，最小元是 B中最小的元素，它与 B中其他元素都可比；而极小元不一定与 B中元素都可比，
只要没有比它小的元素，它就是极小元。对于有穷集 B，极小元一定存在，且可能有多个，但最小元不一定存在，若存在则必唯一。若 B中只有一个极小元，则它一定是 B的最小元。类似地可讨论极大元与最大元之间区别。
定义 4.3.10 设 <A,≤>为偏序集,B?A，
b?A，
① 若 (?x)(x?B?b≤x)为真,则称 b为 B的下界 。
② 若 (?x)(x?B?x≤b)为真,则称 b为 B的上界 。
③ 若 b是一下界且对每一个 B的下界 b’有
b’≤b，则称 b为 B的最大下界或下确界，记为 glb。
④ 若 b是一上界且对每一个 B的上界 b’有
b≤b’，则称 b为 B的最小上界或上确界，记为 lub。
由本定义可知,B的最小元一定是 B的下界，
并且也是 B的最大下界；但反之不一定正确,B
的下界不一定是 B的最小元，因为它可能不是 B
中的元素；类似地，讨论 B的最大元与其上界的关系。
B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。
如果 ≤是偏序关系,或 a≤b,或 b≤a,则说 a
和 b是可比的 。 但偏序集中的元素不一定是都可比的,所以才称,偏序,。 下面介绍的都是可比的情况 。
定义 4.3.11 设 <A,≤>为偏序集，若对任意
a,b?A,a与 b都是可比的，即
a,b?A?a≤b?b≤a
则称 ≤为 A上全序（或线序）关系，这时称
<A,≤>为全序集，或线序集，或链。
由本定义可以看出，全序集的哈斯图为一竖立的结点序列，或者说所有结点位于竖线上。
定义 4.3.12 设 <A,≤>为全序集，若 A的任意非空子集都有最小元，则称 ≤为 A上的良序关系，
称 <A,≤>为良序集。
可以证明,<N,≤>是良序集。
3,相容关系定义 4.3.13 设 R是非空集合 A上的二元关系,
若 R是自反的和对称的,则称 R为 A上的相容关系 。
显然,等价关系必定是相容关系,相容关系较之等价关系是更为普遍的二元关系 。
与相容关系有密切关系是覆盖的概念,下面给出覆盖的定义 。
定义 4.3.14 设 A 为 非 空 集 合,且
B={A1,A2,··,Am},若 =A,则称 B为 A的覆盖 。
显然,A的划分是 A的覆盖,但 A的覆盖未必是个划分 。
定义 4.3.15 设 R是非空集合 A上的相容关系，
C?A，若对 C中任意两元素 a,b有 aRb，称 C是由
R产生的相容类。
由本定义可知,A中任意元素 a，它可以组成 R的相容类。于是，可以作成不同的相容类集合，使其覆盖集合 A。
对于前两个相容类，都可加入新元素组成新的相容类；而后一相容类，加入任一新元素，
就不再组成相容类，称它为最大相容类。
定义 4.3.16 设 R是非空集合 A上的相容关系，
C是 R产生的相容类，若 A-C中的元素没有与 C中所有元素都有相容关系，则称 C为 R的最大相容类，记为 CR。
定义 4.3.17 设 R是非空集合 A上的相容关系，
其最大相容类集合称为集合 A的完全覆盖，记为
CR(A)。
显然，对于相容关系 R，只能对应唯一的完全覆盖。
利用关系图和关系矩阵都可找出所有最大相容类，这里只介绍利用关系矩阵构成所有最大相容类，其步骤如下：
① 只与自身相容的元素，能够分别单独地构成最大相容类，因此从矩阵中删除这些元素所在行和列。
② 从由①简化的矩阵最右一列开始向左扫描，发现 1时，以相应的行号和列号组成一相容类。
③ 往左继续扫描，发现 1时，以相应的行号和列号组成相容类，将它与前面已有的相容类比较，若可合并到已有相容类中去则合并；
若与已有的相容类中的部分元素相容，则另列新相容类，然后删除已被包含在任何相容类中的那些相容类，保留未被合并的相容类。
④ 重复步骤③直至扫描完所有列。
⑤ 将求得的最大相容类和孤立元素自身构成的最大相容类合在一起，构成所有最大相容类。
定理 4.3.3 给定集合 A的覆盖 {A1,A2,··,Am}，
由它确定的关系 R= 是相容关系 。
定理 4.3.4 集合 A上相容关系 R与其完全覆盖 CR(A)存在一一对应 。
证明 因为由集合 A上相容关系 R可产生最大相容类集合,这是唯一的,即该最大相容类集合就是其完全覆盖 CR(A)；反之,由定理 4.3.3
可知,由完全覆盖 CR(A)确定的相容关系也是唯一的,综上可知,集合 A上相容关系 R与其完全覆盖 CR(A)是一一对应的 。
4,准序关系定义 4.3.18 设 R是集合 A上的二元关系,若
R是反自反的和传递的,则称 R为 A上的准序关系,或拟序关系,通常记为 <表示准序,称
<A,<>为准序集 。
准序关系是反对称的,可有下面定理：
定理 4.3.5 若 R是非空集合 A上的准序关系，
则 R是反对称的。
准序集与偏序集是密切相关,唯一区别是恒等关系 IA。 下面定理表明这一点 。
定理 4.3.6 设 R是非空集合 A上的关系,
① 若 R是准序关系,r(R)=R∪ IA是偏序关系 。
② 若 R是偏序关系,则 R-IA是准序关系 。
4.1 二元关系
4.2 关系运算
4.3 关系类型退出
4.1 二元关系二元关系,这里是指集合中两个元素之间的关系 。
1,基本概念定义 4.1.1 给定任意集合 A和 B,若 R?A?B，
则称 R为从 A到 B的二元关系,特别在 A=B时,称 R
为 A上的二元关系 。
可见,R是有序对的集合。若 <x,y>?R,则也表为 xRy,即 <x,y>?R?xRy。
若 R=?,则称 R为 A到 B上空关系；若 R=A?B，
称 R为 A到 B上全域关系。特别当 A=B时，称?为 A
上空关系，称 R=A?A为 A上的全域关系。称
R={<x,x>|x?A}为 A上的恒等关系，记为 IA。
类似地可定义 n元关系。若 S? Ai,则称 S
为 Ai上的 n元关系。特别 A1=A2=···=An时，称
S为 A上的 n元关系。
定义 4.1.2 令 R?A?B,且
D(R)={x|(?y)(xRy)}
R(R)={y|(?x)(xRy)}
F(R)=D(R)+R(R)
则称 D(R),R(R)和 F(R)分别是二元关系 R
的定义域、值域和域。
显然 D(R)?A,R(R)?B。
由于关系是有序对的集合，对它可进行集合运算，其结果也是有序对的集合，
即也是某一种二元关系。令 R和 S是两个二元关系，则 R∪ S,R∩ S,R-S,R?S和 R’
都分别定义了某一种二元关系，并且可表成：
x(R∪ S)y?xRy?xSy
x(R∩ S)y?xRy?xSy
x(R-S)y?xRy?xSy
x(R?S)y?xRy?xSy
xR ’y?xRy
2．关系矩阵与关系图表达从有穷集合到有穷集合的二元关系时
，矩阵和有向图都是得力的工具。
定义 4.1.3 给集合 A={a1,a2,··,am}和
B={b1,b2,··,bn},且 R?A?B,若
1 aiRbj
rij=
0 否则则称矩阵 MR=(rij)m?n为 R的关系矩阵。
当给定关系 R,可求出关系矩阵 MR；反之,
若给出关系矩阵 MR,也能求出关系 R。
集合 A上的二元关系 R也可用有向图表示 。
具体方法是：用小圆圈,?” 表示 A中的元素,
小圆圈称为图的结点 。 把对应于元素 ai和 aj的结点,分别标记 ai和 aj。。 若 <ai,aj>?R,则用弧线段或直线段把 ai和 aj连接起来,并在弧线或直线上设置一箭头,使之由 ai 指向 aj ；若 <ai,
ai>?R,则在结点 ai上画一条带箭示的自封闭曲线或有向环,称这样的弧线或封闭曲线为弧或有向环 。 这样得到的有向图 <A,R>叫做关系 R的图示,简称关系图,记为 GR。
3,关系的性质关系的性质是指集合中二元关系的性质,
这些性质扮演着重要角色,下面将定义这些性质,并给出它的关系矩阵和关系图的特点 。
定义 4.1.4 令 R?A?A,若对 A中每个 x,都有 xRx,则称 R是自反的,即
A上关系 R是自反的?<?x)(x?A?xRx)
该定义表明了,在自反的关系 R中,除其他有序对外,必须包括有全部由每个 x?A所组成的元素相同的有序对 。
在全集 U中所有子集的集合中,包含关系?
是自反的,相等关系 =也是自反的；但是,真包含关系?不是自反的 。 整数集合 Z中,关系 ≤是自反的,而关系 <不是自反的 。
定义 4.1.5 令 R?A?A，若对于 A中每个 x，
有 xRx，则称 R是反自反的，即
A上关系 R是反自反的?<?x)(x?A?xRx)
该定义表明了，一个反自反的关系 R中，
不应包括有任何相同元素的有序对。
由定义 4.1.4 说明中,可知真包含关系?是反自反的,但包含关系?不是反自反的；小于关系 <是反自反的,而 ≤不是反自反的 。
应该指出,任何一个不是自反的关系,未必是反自反的；反之,任何一个不是反自反的关系,未必是自反的 。 这就是说,存在既不是自反的也不是反自反的二元关系 。
定义 4.1.6 令 R?A?A，对于 A中每个 x和 y，
若 xRy，则 yRx，称 R是对称的，即
A上关系 R是对称的
(? x )(? y )(x,y? A? x R y → y R x )
该定义表明了，在表示对称的关系 R的有序对集合中，若有有序对 <x,y>，则必定还会有有序对 <y,x>。
在全集 U的所有子集的集合中,相等关系是对称的,包含关系?和真包含关系?都不是对称的；在整数集合 Z中,相等关系 =是对称的,
而关系 ≤和 <都不是对称的 。
定义 4.1.7 令 R?A?A，对于 A中每个 x和 y，
若 xRy且 yRx，则 x=y，称 R是反对称的，即
A上关系 R是反对称的
(?x )(?y)(x,y?A?x R y?yR x→ x = y )
该定义表明了，在表示反对称关系 R的有序对集合中，若存在有序对 <x,y>和 <y,x>，则必定是 x=y。或者说，在 R中若有有序对 <x,y>，
则除非 x=y，否则必定不会出现 <y,x>。
在全集 U的所有子集的集合中,相等关系 =，
包含关系?和真包含关系?都是反对称的,但全域关系不是反对称的 。 在整数集合 Z中,=,≤和
<也都是反对称的 。
可见,有些关系既是对称的又是反对称的,
如相等关系；有些关系是对称的但不是反对称的,如 Z中的,绝对值相等,；有些关系是反对称的,但不是对称的,如 Z中的 ≤和 <。 还有的关系既不是对称的又不是反对称的,例如,A={a,
c,b>,中 R={<a,b>,<a,c>,<c,a>}。
定义 4.1.8 令 R?A?A，对于 A中每个 x,y,z，
若 xRy且 yRx，则 xRz，称 R是传递的，即
A上关系 R是传递的
(?x)(?y)(?z)(x,y,z?A?xRy?yRz→ xRz)
该定义表明了，在表示可传递关系 R的有序对集合中，若有有序对 <x,y>和 <y,z>，则必有有序对 <x,z>。
显然,上述提到的关系中?,?,=和 ≤,<，
=都是传递的；在直线的集合中,平行关系是传递的,但垂直关系不是传递的 。
通过上面几个实例,看出：
① 若 A上关系 R是自反的,则 MR中主对角线上元素全为 1,而 GR中每个结点有有向环；反之亦然 。
② 若 A上关系 R是反自反的，则 MR中主对角线上元素全为 0，而 GR中每个结点无有向环；
反之亦然。
③若 A上关系 R是对称的，则 MR是对称矩阵，而 GR中任何两结点若有弧必成对出现；反之亦然。
④ 若 A上关系 R是反对称的，则 MR中以主对角线为对称元素不能同时为 1，而 GR中若两结点间有弧不能成对出现；反之亦然。
⑤若 A上关系 R是传递的，则 MR中若
rij=rjk=1，则 rik=1，而 GR中若有弧 <x,y>和 <y,z>
则必有弧 <x,z>；反之亦然。上述是正确的，但不易从 MR和 GR中判定关系 R传递性。
此外，还有：
①任何集合上的相等关系 =是自反的、对称的，反对称的和传递的，但不是反自反的。
②整数集合 Z中，关系 ≤是自反的、反对称的和传递的，但不是反自反的和对称的。关系 <
是反自反的，反对称的和传递的，但不是自反的和对称的。
③ 非空集合上的空关系是反自反的，对称的，反对称的和传递的，但不是自反的。空集合上的空关系则是自反的，反自反的，对称的，
反对称的和传递的。
④非空集合上的全域关系是自反的，对称的和传递的，但不是反自反的和反对称的。
下面给出一个定理，以结束本小节。
定理 4.1.1 设 R?A?A，若 R是反自反的和传递的，则 R是反对称的。
4.2 关系运算前已述及，关系是有序对的集合，因此可以对关系进行运算。若 R,S?A?B，则 R∪ S，
R∩S,R’,R-S?A?B。
1．复合运算定义 4.2.1 设 R是从 A到 B的关系,S是从 B
到 C的关系。经过对 R和 S实行复合（或合成）
运算,?”，得到了一个新的从 A到 C的关系，
记为 R?S，也称 R?S为关系 R和 S的复合（或合成）关系；或称 R?S为 R和 S的复合运算。形式地表为：
R?S={<a,c>|(?b)(b?B?aRb?bSc)}
定理 4.2.1 设 R?A?A,则 R?IA=IA?R=R
定理 4.2.2 若 R?A?B,S,T?B?C,W?C?D,则
① R?(S∪ T)=R?S∪ R?T
② R?(S∩T)? R?S∩R?T
③ (S∪ T)?W=S?W∪ T?W
④ (S∩T)?W? S?W∩T?W
定理 4.2.3 若 R?A?B,S?B?C,T?C?D，
则
(R?S)?T=R?(S?T)
复合运算是可结合的,但不是可交换的 。
望读者举例说明 。
2,幂运算定义 4.2.2 设 R是集合 A上的二元关系,
n?N,R的 n次幂记为 Rn,定义为：
(1) R0=IA
(2) Rn+1=Rn?R
定理 4.2.4 若 R?A?A,且 m,n?N,则
(1) Rm?Rn=Rm+n，
(2) (Rm)n=Rmn。
定理 4.2.5 令 R?A?A,且 |A|=n,则存在 i和 j，
使得 Ri=Rj,其中 0≤i<j≤2n2。
定理 4.2.6 令 R?A?A,若存在 i和 j,i<j,使得 Ri=Rj。 且 d=j-i,则
(1) 对任意 k≥0,Ri+k=Rj+k。
(2) 对任意 k,m≥0,Ri+md+k=Ri+k。
(3) 设 S={R0,R1,R2,··,Rj+1},对?n?N,有
Rn?S。
3,逆运算定义 4.2.3 设 R是从 A到 B的二元关系,由关系 R得到一个新的从 B到 A的关系,记为 R-1,称
R-1为 R的逆运算,亦称 R-1为 R的逆关系 。 形式地表为
R-1={<y,x>|<x,y>?R}
或者 xRy?y R-1x
由定义可知,?-1=?,(A?B)-1=B?A
定理 4.2.7 若 R?A?B,S?B?C,则 (R?S)-
1=S-1?R-1
定理 4.2.8 令 R,S?A?B,则
① (R-1)-1=R
② D(R-1)=R(R),R(R-1)=D(R)
③ (R∪ S)-1= R-1∪ S-1
④ (R∩S)-1= R-1∩S-1
⑤ (R-S)-1= R-1-S-1
⑥ R?S?R-1?S-1
定理 4.2.9 若 R?A?A,则 R为对称?R=R-1。
4,闭包运算关系的闭包运算是关系上的一元运算,是包含该关系且具有某种性质的最小关系 。
定义 4.2.4 设 R是 A上的二元关系,R的自反
（对称、传递）闭包是关系 R1，则
① R1是自反的（对称的、传递的）
② R?R1
③ 对任何自反的（对称的、传递的）关系
R2，若 R?R2，则 R1?R2。
R的自反、对称和传递闭包分别记为 r(R)、
s(R)和 t(R)。
定理 4.2.10 若 R?A?A，则
① R是自反的 iff r(R)=R
② R是对称的 iff s(R)=R
③ R是传递的 iff t(R)=R
证明 只证明①，余下自证。
若 R是自反的，则由定义 4.2.4可知,R具有对 R1所要求的性质，故 r(R)=R；反之，若
r(R)=R，则由定义 4.2.4① 知,R是自反的。
由闭包的定义可以知道，构造关系 R的闭包方法就是向 R中加入必要的有序对，使其具有所希望的性质。下面定理体现了这一点。
定理 4.2.11 令 R?A?A，则
① r(R)=R∪ IA
② s(R)=R∪ R-1
③ t(R)=
定理 4.2.12 若 R?A?A,|A|=n,则 t(R)= 。
定理 4.2.13 若 R?A?A,则
① rs(R)=sr(R)
② rt(R)=tr(R)
③ st(R)?ts(R)
5,关系运算的矩阵表示关系运算是可以用关系矩阵表示的 。
设 R,S?A?B,T?B?C,MR=(aij)m?n,
MS=(bij)m?n,MT=(cij)n?p,dij表示运算后所得新关系之关系矩阵的元素,则
① MR∪ S=MR∪ MS dij=aij?bij
1≤i≤m,1≤j≤n
② MR∩S=MR∩MS dij=aij?bij
1≤i≤m,1≤j≤n
③ dij=?aji
1≤i≤m,1≤j≤n
④ MR-S=MR? dij=aij?(?bij)
1≤i≤m,1≤j≤n
⑤ =MRT dij=aij
1≤i≤m,1≤j≤n
⑥ MR?T=MR?MT dij= (aik?ckj)
1≤i≤m,1≤j≤n
4.3 关系类型关系类型在本书中主要讨论有四种,它们是等价关系,偏序关系,相容关系和次序关系 。
1,等价关系定义 4.3.1 设 R是集合 A上二元关系,若 R是自反的,对称的和传递的,则称 R为 A上的等价关系 。 若 <a,b>?R,或 aRb,称 a等价 b,记 a?b。
由于 R是对称的,a等价 b即 b等价 a,反之亦然,a与 b彼此等价 。
鉴于空集合中的二元关系是等价关系,是一种平凡情形,因此,一般讨论非空集合上的等价关系 。
模 m等价是 Z或其子集上的等价关系,并且是一类重要的等价关系 。
定义 4.3.2 设 m为一正整数而 a,b?Z。 若存在 m,使 a-b=km,则称 a与 b是模 m等价,记为
a?b(mod m)。
定理 4.3.1 模 m等价是任何集合 A?Z上的等价关系 R。
定义 4.3.3 设 R为非空集合 A上的等价关系,
对?a?A,令
[a]R={x|x?A?aRx}
称 [a]R为 a关于 R的等价类,简称 a的等价类,
简记为 [a]。
显然,等价类 [a]R非空,因为 a?[a]R。
定理 4.3.2 设 R是非空集合 A上的等价关系,
则
①?a,b?A,若 aRb,则 [a]=[b]。
②?a,b?A,若 aRb,则 [a]∩[b]=?。
③ =A
利用非空集合 A及其上等价关系可以构造一个新集合 —商集 。
定义 4.3.4 设 R是非空集合 A上的等价关系,
以及
A/R={[a]R|a?A}
则称 A/R为 A对 R的商集 。
该定义表明了,商集 A/R是以 R的所有等价类为元素的集合 。
与商集有密切联系的概念是集合的划分 。
下面给出划分的定义 。
定义 4.3.5 设 A 是非空集合,若
B={A1,A2,··,An},且 ① Ai,② Ai∩Aj=?,i?j，
③ =A,则称 B是 A的划分 。 称 B中元素为 A
的划分块 。
可见,商集 A/R就是 A的一个划分,并且不同的商集对应于不同的划分 。 反之,任给 A的一个划分,B={A1,A2,··,An},如下定义 A上的关系
R：
R=
或 R={<a,b>|(?Ai)(Ai?B?a,b?Ai)}
则不难证明 R是 A上的等价关系，且 A/R就是划分 B。因此，非空集合 A上的等价关系与 A
的划分是一一对应的。
2,偏序关系定义 4.3.6 设 R是非空集合 A上的关系,若 R
是自反的,反对称和传递的,则称 R为 A上的偏序关系 。 称有序对 <A,R>为偏序集 。
若 R是偏序,<A,R>常记为 <A,≦ >,为便于书写,将 ≦ 通常记为 ≤,读作,小于或等于,,
因为,小于或等于,也是一种偏序,故不会产生混乱 。 所以,R是偏序,aRb就表成 a≤b。
若 R是 A上的偏序，则 R-1也是 A上偏序。若用 ≤表示 R，则用 ≥表示 R-1； <A,≤>和 <A,≥>都是偏序集，并且互为对偶。
注意,a≤b是指在偏序关系中的顺序性，是将 a排在 b的前边或者 a即是 b。根据不同偏序的定义，对序有着不同的解释，如包含关系是偏序关系 ≤,A≤B（一般写成 A?B）是指 A包含于
B；整除关系是偏序关系 ≤,3≤6（通常记为 3|6）
是指 3整除 6等等。
定义 4.3.7 设 R是非空集合 A上的偏序关系，
定义
①?a,b?A,a<b?a≤b?a?b
②?a,b?A,a与 b是可比的?a≤b?b≤a
其中 a<b读作 a“小于” b，它是指在偏序中，
a排在 b的前边。
可见，在偏序集 <A,≤>中，对?a,b?A，有
a<b(或 b<a),a=b,a与 b不可比三种情况发生，例如 A={1,2,3},≤是 A上的整除关系，则有
1<2,1<3,
1=1,2=2,3=3，
2与 3不可比。
利用非空集合 A上偏序关系 R可以简化其关系图，
得到偏序集 <A,R>的哈斯 (Hass)图。为了给出其画法，
首先定义偏序集中元素的盖住关系。
定义 4.3.8 设 <A,≤>为偏序集。a,b?A，若
a<b且不存在 c?A，使得 a<c<b，则称 b盖住 a。
在画偏序集 <A,≤>的哈斯图时，首先适当排列 A中元素的顺序。对于?a,b?A，若 a<b，
则将 a画在 b的下方；其次考虑 b是否盖住了 a，
若 b盖住 a，则用一条线段连接 a和 b。
定义 4.3.9 设 <A,≤>为偏序集,B?A,b?B，
① 若 (?x)(x?B?b≤x)为真，则称 b为 B的最小元。
② 若 (?x)(x?B?x≤b)为真，则称 b为 B的最大元。
③ 若?(?x)(b?x?x≤b)为真，则称 b为 B的极小元。
④ 若?(?x)(b?x?b≤x)为真，则称 b为 B的极大元。
从本定义可知，最小元与极小元是有区别的，最小元是 B中最小的元素，它与 B中其他元素都可比；而极小元不一定与 B中元素都可比，
只要没有比它小的元素，它就是极小元。对于有穷集 B，极小元一定存在，且可能有多个，但最小元不一定存在，若存在则必唯一。若 B中只有一个极小元，则它一定是 B的最小元。类似地可讨论极大元与最大元之间区别。
定义 4.3.10 设 <A,≤>为偏序集,B?A，
b?A，
① 若 (?x)(x?B?b≤x)为真,则称 b为 B的下界 。
② 若 (?x)(x?B?x≤b)为真,则称 b为 B的上界 。
③ 若 b是一下界且对每一个 B的下界 b’有
b’≤b，则称 b为 B的最大下界或下确界，记为 glb。
④ 若 b是一上界且对每一个 B的上界 b’有
b≤b’，则称 b为 B的最小上界或上确界，记为 lub。
由本定义可知,B的最小元一定是 B的下界，
并且也是 B的最大下界；但反之不一定正确,B
的下界不一定是 B的最小元，因为它可能不是 B
中的元素；类似地，讨论 B的最大元与其上界的关系。
B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。
如果 ≤是偏序关系,或 a≤b,或 b≤a,则说 a
和 b是可比的 。 但偏序集中的元素不一定是都可比的,所以才称,偏序,。 下面介绍的都是可比的情况 。
定义 4.3.11 设 <A,≤>为偏序集，若对任意
a,b?A,a与 b都是可比的，即
a,b?A?a≤b?b≤a
则称 ≤为 A上全序（或线序）关系，这时称
<A,≤>为全序集，或线序集，或链。
由本定义可以看出，全序集的哈斯图为一竖立的结点序列，或者说所有结点位于竖线上。
定义 4.3.12 设 <A,≤>为全序集，若 A的任意非空子集都有最小元，则称 ≤为 A上的良序关系，
称 <A,≤>为良序集。
可以证明,<N,≤>是良序集。
3,相容关系定义 4.3.13 设 R是非空集合 A上的二元关系,
若 R是自反的和对称的,则称 R为 A上的相容关系 。
显然,等价关系必定是相容关系,相容关系较之等价关系是更为普遍的二元关系 。
与相容关系有密切关系是覆盖的概念,下面给出覆盖的定义 。
定义 4.3.14 设 A 为 非 空 集 合,且
B={A1,A2,··,Am},若 =A,则称 B为 A的覆盖 。
显然,A的划分是 A的覆盖,但 A的覆盖未必是个划分 。
定义 4.3.15 设 R是非空集合 A上的相容关系，
C?A，若对 C中任意两元素 a,b有 aRb，称 C是由
R产生的相容类。
由本定义可知,A中任意元素 a，它可以组成 R的相容类。于是，可以作成不同的相容类集合，使其覆盖集合 A。
对于前两个相容类，都可加入新元素组成新的相容类；而后一相容类，加入任一新元素，
就不再组成相容类，称它为最大相容类。
定义 4.3.16 设 R是非空集合 A上的相容关系，
C是 R产生的相容类，若 A-C中的元素没有与 C中所有元素都有相容关系，则称 C为 R的最大相容类，记为 CR。
定义 4.3.17 设 R是非空集合 A上的相容关系，
其最大相容类集合称为集合 A的完全覆盖，记为
CR(A)。
显然，对于相容关系 R，只能对应唯一的完全覆盖。
利用关系图和关系矩阵都可找出所有最大相容类，这里只介绍利用关系矩阵构成所有最大相容类，其步骤如下：
① 只与自身相容的元素，能够分别单独地构成最大相容类，因此从矩阵中删除这些元素所在行和列。
② 从由①简化的矩阵最右一列开始向左扫描，发现 1时，以相应的行号和列号组成一相容类。
③ 往左继续扫描，发现 1时，以相应的行号和列号组成相容类，将它与前面已有的相容类比较，若可合并到已有相容类中去则合并；
若与已有的相容类中的部分元素相容，则另列新相容类，然后删除已被包含在任何相容类中的那些相容类，保留未被合并的相容类。
④ 重复步骤③直至扫描完所有列。
⑤ 将求得的最大相容类和孤立元素自身构成的最大相容类合在一起，构成所有最大相容类。
定理 4.3.3 给定集合 A的覆盖 {A1,A2,··,Am}，
由它确定的关系 R= 是相容关系 。
定理 4.3.4 集合 A上相容关系 R与其完全覆盖 CR(A)存在一一对应 。
证明 因为由集合 A上相容关系 R可产生最大相容类集合,这是唯一的,即该最大相容类集合就是其完全覆盖 CR(A)；反之,由定理 4.3.3
可知,由完全覆盖 CR(A)确定的相容关系也是唯一的,综上可知,集合 A上相容关系 R与其完全覆盖 CR(A)是一一对应的 。
4,准序关系定义 4.3.18 设 R是集合 A上的二元关系,若
R是反自反的和传递的,则称 R为 A上的准序关系,或拟序关系,通常记为 <表示准序,称
<A,<>为准序集 。
准序关系是反对称的,可有下面定理：
定理 4.3.5 若 R是非空集合 A上的准序关系，
则 R是反对称的。
准序集与偏序集是密切相关,唯一区别是恒等关系 IA。 下面定理表明这一点 。
定理 4.3.6 设 R是非空集合 A上的关系,
① 若 R是准序关系,r(R)=R∪ IA是偏序关系 。
② 若 R是偏序关系,则 R-IA是准序关系 。
