第 7章 二元关系离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 有序对与笛卡儿集
– 二元关系的定义和表示法
– 关系的运算
– 关系的性质
– 关系的闭包
– 等价关系与划分
– 偏序关系
本章与后续各章的关系
– 本章是函数的基础
– 本章是图论的基础本章内容
7.1 有序对与笛卡儿积
7.2 二元关系
7.3 关系的运算
7.4 关系的性质
7.5 关系的闭包
7.6 等价关系与划分
7.7 偏序关系本章小结习题作业
7.1 有序对与笛卡儿积定义 7.1 由两个元素 x和 y（ 允许 x=y） 按一定顺序排列成的二元组叫做一个 有序对 (ordered pair)或 序偶,记作 <x,y>,其中 x
是它的第一元素,y是它的第二元素。
有序对 <x,y>具有以下性质：
（ 1）当 x≠y 时,<x,y>≠<y,x> 。
（ 2） <x,y>＝ <u,v>的充分必要条件是 x＝ u且 y＝ v。
说明? 有序对中的元素是有序的
集合中的元素是无序的例 7.1
例 7.1 已知 <x+2,4>＝ <5,2x+y>,求 x和 y。
由有序对相等的充要条件有
x+2＝ 5
2x+y＝ 4
解得 x＝ 3,y＝ -2。
解答定义 7.2 设 A,B为集合,用 A中元素为第一元素,B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做 A和 B
的 笛卡儿积 (Cartesian product)，记作 A× B。
笛卡儿积的符号化表示为
A× B＝ {<x,y>|x∈A∧y∈B}
笛卡儿积的定义
A表示某大学所有学生的集合,B表示大学开设的所有课程的集合，
则 A× B可以用来表示该校学生选课的所有可能情况。
令 A是直角坐标系中 x轴上的点集,B是直角坐标系中 y
轴上的点集，
于是 A× B就和平面点集一一对应。
举例笛卡尔积举例设 A={a,b},B={0,1,2},则
A× B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}
B× A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
举例说明? 如果 |A|=m,|B|=n,则 |A× B|=mn。
笛卡儿积的运算性质
(1)对任意集合 A,根据定义有
A×?＝?,?×A＝?
(2)一般的说,笛卡儿积运算不满足交换律,即
A×B≠B ×A (当 A≠? ∧ B≠? ∧ A≠B 时 )
(3)笛卡儿积运算不满足结合律,即
(A×B)×C≠A ×(B×C) (当 A≠? ∧ B≠? ∧ C≠? 时 )
(4)笛卡儿积运算对并和交运算满足分配律,即
A×(B∪ C)=(A×B)∪ (A×C)
(B∪ C)×A=(B×A)∪ (C×A)
A×(B∩ C)=(A×B)∩ (A×C)
(B∩ C)×A=(B×A)∩ (C×A)
(5)A?C ∧ B?D? A×B? C×D
A×(B∪C)=(A ×B)∪(A ×C)的证明任取 <x,y>
<x,y>∈A × (B∪C)
x∈A ∧ y∈B∪C
x∈A ∧ (y∈B∨y∈C)
(x∈A∧y∈B) ∨ (x∈A∧y∈C)
<x,y>∈A × B ∨ <x,y>∈A × C
<x,y>∈(A × B)∪(A × C)
所以 A×(B∪ C)=(A×B)∪ (A×C)
关于 A?C∧B?D? A×B?C×D的讨论该性质的逆命题不成立，可分以下情况讨论。
（ 1）当 A=B=?时，显然有 A?C 和 B?D 成立。
（ 2）当 A≠?且 B≠?时，也有 A?C和 B?D成立，证明如下：
任取 x∈A,由于 B≠?,必存在 y∈B,因此有
x∈A∧y∈B
<x,y>∈A × B
<x,y>∈C × D
x∈C∧y∈D
x∈C
从而证明了 A?C。
同理可证 B?D。
关于 A?C∧B?D? A×B?C×D的讨论该性质的逆命题不成立，可分以下情况讨论。
（ 3）当 A＝?而 B≠?时，有 A?C成立，但不一定有 B?D成立。
反例：令 A＝?,B＝ {1},C＝ {3},D＝ {4}。
（ 4）当 A≠?而 B＝?时，有 B?D成立，但不一定有 A?C成立。
反例略。
例 7.2
例 7.2 设 A={1,2},求 P(A)× A。
P(A)× A
＝ {?,{1},{2},{1,2}}× {1,2}
＝ {<?,1>,<?,2>,
<{1},1>,<{1},2>,
<{2},1>,<{2},2>,
<{1,2},1>,<{1,2},2>}
解答例 7.3
例 7.3 设 A,B,C,D为任意集合，判断以下命题是否为真，并说明理由。
(1) A× B＝ A× C? B＝ C
(2) A-(B× C)＝ (A-B)× (A-C)
(3) A＝ B∧ C＝ D? A× C＝ B× D
(4) 存在集合 A,使得 A? A× A
(1) 不一定为真。当 A＝?,B＝ {1},C＝ {2}时，有
A× B＝?＝ A× C,但 B≠C 。
(2) 不一定为真。当 A=B={1},C＝ {2}时，有
A-(B× C)＝ {1}–{<1,2>}＝ {1}
(A-B)× (A-C)＝?× {1}＝?
(3) 为真。由等量代入的原理可证。
(4) 为真。当 A＝?时，有 A?A× A 成立。
解答
7.2 二元关系 (binary relation)
定义 7.3 如果一个集合满足以下条件之一：
（ 1）集合非空，且它的元素都是有序对
（ 2）集合是空集则称该集合为一个 二元关系,记作 R。 二元关系也可简称为 关系 。对于二元关系 R,如果 <x,y>∈R,可记作 xRy； 如果
<x,y>?R,则记作 xRy。
设 R1＝ {<1,2>,<a,b>},R2＝ {<1,2>,a,b}。
则 R1是二元关系,R2不是二元关系，只是一个集合，
除非将 a和 b定义为有序对。
根据上面的记法可以写 1R12,aR1b,aR1c等。
举例
R＝ {<上,下 >,<前,后 >,<正,反 >,<左,右 >}是否为二元关系？
集合 A上的二元关系的数目依赖于 A中的元素数。
如果 |A|=n,那么 |A× A|=n2,A× A的子集就有 个。
每一个子集代表一个 A上的二元关系，所以 A上有 个不同的二元关系。
例如 |A|=3,则 A上有 个不同的二元关系。
7.2 二元关系定义 7.4 设 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上的二元关系。
举例
22n
22n
232
说明常用的关系定义 7.5 对任意集合 A,定义全域关系 EA={<x,y>|x∈A∧y∈A}=A × A
恒等关系 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,y∈A∧x?y},其中 A?R。
整除关系,DB={<x,y>|x,y∈B∧x 整除 y},其中 A?Z*
Z*是非零整数集
包含关系,R?＝ {<x,y>|x,y∈A∧x?y},其中 A是集合族。
(1)设 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>}
(2)令 A=P(B)={?,{a},{b},{a,b}},则 A上的包含关系是
R?＝ {<?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,
<{a},{a}>,<{a},{a,b}>,<{b},{b}>,
<{b},{a,b}>,<{a,b},{a,b}>}
举例例 7.4
例 7.4 设 A={1,2,3,4},下面各式定义的 R都是 A上的关系，
试用列元素法表示 R。
(1) R={<x,y> | x是 y的倍数 }
(2) R={<x,y> | (x-y)2∈A}
(3) R={<x,y> | x/y是素数 }
(4) R={<x,y> | x≠y}
解答
(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}
(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,
<2,3>,<1,2>}
(3)R={<2,1>,<3,1>,<4,2>}
(4)R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,
<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}
关系的表示方法
关系的三种表示方法：
– 集合表达式
– 关系矩阵
– 关系图
关系矩阵和关系图可以表示有穷集上的关系。
关系矩阵和关系图的定义设 A={x1,x2,…,xn},R是 A上的关系。令
n),1,2,j( i,Rx若x0 Rx若x1{r
ji
ji
ij
nnn2n1
2n2221
1n1211
ij
rrr
rrr
rrr
)(r
则是 R的 关系矩阵,记作 MR。
设 A={x1,x2,…,xn},R是 A上的关系。令图 G=<V,E>,其中顶点集合 V=A,边集为 E。 对于? xi,xj∈V,满足
<xi,xj>∈E? xiRxj
称图 G为 R的 关系图,记作 GR。
关系矩阵和关系图的实例设 A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，
则 R的关系矩阵和关系图分别是
0010
0000
1100
0011
M R
7.3 关系的运算定义 7.6 设 R是二元关系。
(1)R中所有有序对的第一元素构成的集合称为 R的 定义域
(domain),记为 dom R。 形式化表示为：
dom R ＝ {x |?y(<x,y>∈R )}
(2)R中所有有序对的第二元素构成的集合称为 R的 值域 (range)
，记作 ran R。 形式化表示为
ran R＝ {y |? x(<x,y>∈R)}
(3)R的定义域和值域的并集称为 R的 域 (field)，记作 fld R。
形式化表示为
fld R＝ dom R ∪ ran R
例 7.5 求 R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。
解答 dom R＝ {1,2,4} ran R＝ {2,3,4} fld R＝ {1,2,3,4}
关系的逆和右复合运算定义 7.7 设 R为二元关系,R的逆关系，简称 R的 逆 (inverse)，
记作 R-1,其中
R-1＝ {<x,y>|<y,x>∈R}
定义 7.8 设 F,G为二元关系,G对 F的 右复合 (composite)记作
F?G,其中
F?G＝ {<x,y> |?t(<x,t>∈F∧< t,y>∈G)}
例 7.6 设 F＝ {<3,3>,<6,2>},G={<2,3>},则
F-1 ＝ {<3,3>,<2,6>}
F?G＝ {<6,3>} G?F＝ {<2,3>}
说明? 可以把二元关系看作一种作用,<x,y>∈R 可以解释为
x通过 R的作用变到 y。
F?G表示两个作用的连续发生。
关系的限制和像定义 7.9 设 R为二元关系,A是集合
(1) R在 A上的 限制 (restriction)记作 R↑ A,其中
R↑A={<x,y>|xRy∧x∈A}
(2) A在 R下的 像 (image)记作 R[A],其中
R[A]=ran(R↑A)
说明? R在 A上的限制 R↑A 是 R的子关系。 A在 R下的像 R[A]是 ran R的子集。
例 7.7
设 R＝ {<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}
R↑ {1}＝ {<1,2>,<1,3>}
R↑? ＝?
R↑ {2,3}＝ {<2,2>,<2,4>},<3,2>}
R[{1}]＝ {2,3}
R[?] ＝?
R[{3}]＝ {2}
关系与集合的说明
关系是集合，集合运算对于关系也是适用的。
规定：
– 关系运算中逆运算优先于其它运算
– 所有的关系运算都优先于集合运算，
– 优先权的运算以括号决定运算顺序。
例如：
– ran F-1
– F?G∪F?H
– ran (F↑A)
例题
设 A表示是学校的所有学生的集合,B表示学校的所有课程的集合，并设 R1由所有有序对 <a,b>组成，其中 a是选修课程 b的学生
。 R2由所有的有序对 <a,b>构成，其中课程 b是 a的必修课。则关系 R1∪R 2,R1∩R 2,R1⊕R 2,R1－ R2,R2－ R1的含义为
R1∪R 2,a是一个学生，他或者选修了课程 b,或者课程 b是他的必修课。
R1∩R 2,a是一个学生，他选修了课程 b并且课程 b也是 a的必修课。
R1⊕R 2,学生 a已经选修了课程 b,但课程 b不是 a的选修课，或者课程 b是 a的必修课，但是 a没有选修它。
R1－ R2,学生 a已经选修了课程 b,但课程 b不是 a的选修课。
R2－ R1,课程 b是学生 a的必修课，但是 a没有选修它。
定理 7.1
定理 7.1 设 F是任意的关系，则
(1)(F-1)-1＝ F
(2)dom F-1＝ ran F,ran F-1＝ dom F
(1)任取 <x,y>,由逆的定义有
<x,y>∈ (F-1)-1
<y,x>∈ F-1
<x,y>∈F
(2)任取 x
x∈ dom F-1
y(<x,y>∈F -1)
y(<y,x>∈F)
x∈ran F
所以有 dom F-1＝ ran F
证明定理 7.2
定理 7.2 设 F,G,H是任意的关系，则
(1)(F?G)?H＝ F?(G?H)
(2)(F?G)-1＝ G-1? F-1
证明 (1)任取 <x,y>，
<x,y>∈ (F?G)?H
t(<x,t>∈F?G∧( t,y)∈H)
t(?s(<x,s>∈F∧< s,t>∈G)∧< t,y>∈H)
t?s(<x,s>∈F∧< s,t>∈G∧< t,y>∈H)
s(<x,s>∈F∧?t(<s,t>∈G∧< t,y>∈H))
s(<x,s>∈F∧< s,y>∈G?H)
<x,y>∈ F?(G?H)
定理 7.2
定理 7.2 设 F,G,H是任意的关系，则
(1)(F?G)?H＝ F?(G?H)
(2)(F?G)-1＝ G-1?F-1
证明 (2)任取 <x,y>，
<x,y>∈ (F?G)-1
<y,x>∈F?G
t(<y,t>∈F∧< t,x>∈G)
t(<t,y>∈F -1∧<x,t>∈G -1)
<x,y>∈G -1? F-1
定理 7.3
定理 7.3 设 R为 A上的关系，则
R? IA＝ IA? R＝ R
证明 (1)任取 <x,y>，
<x,y>∈ R? IA
t(<x,t>∈R∧( t,y)∈I A)
t(<x,t>∈R∧ t＝ y)
<x,y>∈R
<x,y>∈ R
<x,y>∈R∧y∈A
<x,y>∈R∧<y,y>∈I A)
<x,y>∈ R? IA
综上所述，有 R?IA＝ R
同理可证 IA?R＝ R
定理 7.4
定理 7.4 设 F,G,H是任意的关系，则
(1) F?(G∪ H)＝ F?G∪F?H
(2) (G∪H)?F＝ G?F∪H?F
(3) F?(G∩H)?F?G∩F?H
(4) (G∩H)?F?G?F∩ H?F
证明 (3) <x,y>∈ F?(G∩H)
t(<x,t>∈F∧( t,y)∈G∩H)
t(<x,t>∈F∧( t,y)∈G∧( t,y)∈H)
t((<x,t>∈F∧( t,y)∈G ) ∧ (<x,t>∈F∧( t,y)∈H ))
t(<x,t>∈F∧( t,y)∈G) ∧?t(<x,t>∈F∧( t,y)∈H)
<x,y>∈F?G ∧ <x,y>∈F?H
<x,y>∈ F?G∩F?H
定理 7.4的推论
由数学归纳法不难证明定理 7.4的结论对于有限多个关系的并和交也是成立的，即有
R?(R1∪R 2∪ … ∪R n)＝ R?R1∪R?R2∪ … ∪R?Rn
R1?∪R 2∪ … ∪R n)?R＝ R1?R∪R 2?R∪ … ∪R n?R
R?(R1∩R 2∩ … ∩R n)?R?R1∩R?R2∩ … ∩R?Rn
R1∩R 2∩ … ∩R n)?R?R1?R∩R 2?R∩ … ∩R n?R
定理 7.5
定理 7.5 设 F为关系,A,B为集合，则
(1) F↑(A∪B) ＝ F↑A∪F↑B
(2) F[A∪B] ＝ F[A]∪F[B]
(3) F↑(A∩B) ＝ F↑A∩F↑B
(4) F[A∩B]?F[A]∩F[B]
定理 7.5 (1)的证明
(1) F↑(A∪B) ＝ F↑A∪F↑B
证明 任取 <x,y>，
<x,y>∈F↑(A∪B)
<x,y>∈F ∧ x∈(A∪B)
<x,y>∈F ∧ (x∈A∨x∈B)
(<x,y>∈F∧x∈A) ∨ (<x,y>∈F∧x∈B)
<x,y>∈F ↑ A ∨ <x,y>∈F ↑ B
<x,y>∈F ↑ A∪F ↑ B
所以有 F↑(A∪B) ＝ F↑A∪F↑B 。
定理 7.5 (4)的证明
(4) F[A∩B]?F[A]∩F[B]
证明 任取 y，
y∈F[A∩B]
x(<x,y>∈F∧ x∈A∩B)
x(<x,y>∈F∧ x∈A∧ x∈B)
x((<x,y>∈F∧ x∈A)∧(< x,y>∈F∧ x∈B))
x(<x,y>∈F∧ x∈A) ∧?x(<x,y>∈F∧ x∈B)
y∈F[A] ∧ y∈F[B]
y∈F[A]∩F[B]
所以有 F[A∩B]?F[A]∩F[B]
关系的幂运算定义 7.10 设 R为 A上的关系,n为自然数，则 R的 n次幂定义为：
（ 1） R0＝ {<x,x>|x∈A} ＝ IA
（ 2） Rn+1＝ Rn? R
说明? 对于 A上的任何关系 R1和 R2都有R
1
0＝ R
2
0＝ I
A
即,A上任何关系的 0次幂都相等，都等于 A上的恒等关系 IA。
对于 A上的任何关系 R都有 R1＝ R,因为
R1＝ R0? R＝ IA? R＝ R
Rn的计算
给定 A上的关系 R和自然数 n,怎样计算 Rn呢？
若 n是 0或 1，结果是很简单的。下面考虑 n?2 的情况。
– 如果 R是用 集合表达式 给出的，可以通过 n-1次右复合 计算得到 Rn。
– 如果 R是用 关系矩阵 M给出的，则 Rn的关系矩阵是 Mn,即 n
个矩阵 M之积 。与普通矩阵乘法不同的是，其中的相加是逻辑加，即
1+1＝ 1,1+0＝ 0+1＝ 1,0+0＝ 0
– 如果 R是用 关系图 G给出的，可以直接由图 G得到 Rn的关系图 G'。 G'的顶点集与 G相同。考察 G的每个顶点 xi,如果 在
G中从 xi出发经过 n步长的路径到达顶点 xj,则在 G'中加一条从 xi到 xj的边 。当把所有这样的便都找到以后，就得到图 G'。
例 7.8
例 7.8 设 A＝ {a,b,c,d},R＝ {<a,b>,<b,a>,<b,c>,<c,d>},求
R的各次幂，分别用矩阵和关系图表示。
解答
0000
1000
0101
0010
M
0000
1000
0101
0010
0000
1000
0101
0010
M 2
0000
1000
0101
0010
0000
0000
1010
0101
MMM 23
1000
0100
0010
0001
M 0
0000
0000
1010
0101
000
000
011
100
例 7.8
因此 M4＝ M2,即 R4＝ R2。 因此可以得到
R2＝ R4＝ R6＝ …
R3＝ R5＝ R7＝ …
用关系图的方法得到 R0,R1,R2,R3,… 的关系图如下图所示。
0000
1000
0101
0010
0000
0000
0101
1010
MMM 34
0000
0000
1010
0101
幂运算的性质定理 7.6 设 A为 n元集,R是 A上的关系，则存在自然数 s和 t,
使得 Rs=Rt。
R为 A上的关系，对任何自然数 k,Rk都是 A× A的子集。证明又知 |A× A|=n2,|P(A× A)|=,2n2
即 A× A的不同子集仅 个。2n2
当列出 R的各次幂 R0,R1,R2,…,,… 时，2n2R
必存在自然数 s和 t使得 Rs=Rt。
说明? 该定理说明有穷集上只有有穷多个不同的二元关系。当 t足够大时,Rt必与某个 Rs(s<t)相等。
如例 7.8中的 R4=R2。
定理 7.7
定理 7.7 设 R是 A上的关系,m,n∈N,则
(1)Rm? Rn＝ Rm+n
(2)(Rm)n＝ Rmn
证明 (1)对于任意给定的 m∈N,施归纳于 n。
若 n=0,则有所以对一切 m,n∈N 有 Rm? Rn＝ Rm+n。
Rm? R0＝ Rm? IA＝ Rm＝ Rm+0
假设 Rm? Rn=Rm+n,则有
Rm? Rn+1＝ Rm?(Rn? R)＝ (Rm? Rn)?R＝ Rm+n+1，
定理 7.7
定理 7.7 设 R是 A上的关系,m,n∈N,则
(1)Rm? Rn＝ Rm+n
(2)(Rm)n＝ Rmn
证明 (2)对于任意给定的 m∈N,施归纳于 n。
若 n=0,则有所以对一切 m,n∈N 有 (Rm)n=Rmn。
(Rm)0＝ IA＝ R0＝ Rm× 0
假设 (Rm)n＝ Rmn,则有
(Rm)n+1＝ (Rm)n? Rm＝ Rmn+m＝ Rm(n+1)
定理 7.8
定理 7.8 设 R是 A上的关系，若存在自然数 s,t(s<t)使得 Rs=Rt,则
(1) 对任何 k∈N 有 Rs+k=Rt+k
(2) 对任何 k,i∈N 有 Rs+kp+i=Rs+i,其中 p=t-s
(3) 令 S={R0,R1,…,Rt-1},则对于任意的 q∈N 有 Rq∈S
证明 (1) R
s+k＝ Rs? Rk＝ Rt? Rk＝ Rt+k
(2)对 k归纳。
若 k=0,则有 Rs+0 p+i＝ Rs+i
假设 Rs+kp+i＝ Rs+i,其中 p＝ t-s,则
Rs+(k+1)p+i＝ Rs+kp+i+p＝ Rs+i? Rp=Rs+p+i
＝ Rs+t-s+i＝ Rt+i＝ Rs+i
由归纳法命题得证。
Rs+kp+i? Rp＝
定理 7.8
定理 7.8 设 R是 A上的关系，若存在自然数 s,t(s<t)使得 Rs=Rt,则
(1) 对任何 k∈N 有 Rs+k=Rt+k
(2) 对任何 k,i∈N 有 Rs+kp+i=Rs+i,其中 p=t-s
(3) 令 S={R0,R1,…,Rt-1},则对于任意的 q∈N 有 Rq∈S
证明 (3)任取 q∈N,若 q<t,显然有 Rq∈S,
若 q?t,则存在自然数 k和 i使得
q＝ s+kp+i
其中 0? i?p -1,p＝ t-s。 于是
Rq＝ Rs+kp+i＝ Rs+i
s+i?s+p -1 ＝ s+t-s-1＝ t-1
这就证明了 Rq∈S 。
定理 7.8的说明
有穷集 A上的关系 R的幂序列 R0,R1,… 是一个周期性变化的序列。就象正弦函数一样，利用它的周期性可以将 R的高次幂化简为 R的低次幂。
例 7.9 设 A={a,b,d,e,f},R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>}
。 求出最小的自然数 m和 n,使得 m<n且 Rm=Rn。
解答 由 R的定义可以看出 A中的元素可分成两组，即 {a,b}和
{d,e,f}。 它们在 R的右复合运算下有下述变化规律：
a→b→a→b …
d→e→f→d→e→f …
对于 a或 b,每个元素的变化周期是 2。对于 d,e,f,每个元素的变化周期是 3。因此必有 Rm=Rm+6,其中 6是 2和 3的最小公倍数。取 m=0,n=6即满足题目要求。
7.4 关系的性质
自反性
反自反性
对称性
反对称性
传递性自反性和反自反性定义 7.11 设 R为 A上的关系，
(1)若?x(x∈A→ <x,x>∈R),则称 R在 A上是 自反 (reflexivity)
的。
(2)若?x(x∈A→<x,x>?R),则称 R在 A上是 反自反
(irreflexivity)的。
例如 全域关系 EA,恒等关系 IA,小于等于关系 LA,整除关系
DA都是为 A上的 自反关系 。
包含关系 R是给定集合族 A上的 自反关系 。
小于关系 和 真包含关系 都是给定集合或集合族上的 反自反关系 。
例 7.10
例 7.10 设 A={1,2,3},R1,R2,R3是 A上的关系，其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,1>,<2,2>,<3,3>,<1,2>}
R3＝ {<1,3>}
说明 R1,R2和 R3是否为 A上的自反关系和反自反关系。
解答
R1既不是自反的也不是反自反的，
R2是自反的，
R3是反自反的。
对称性和反对称性定义 7.12 设 R为 A上的关系，
（ 1）若?x?y(x,y∈A∧<x,y>∈R→<y,x>∈R),则称 R为 A上对称 (symmetry)的关系。
（ 2）若?x?y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称 R
为 A上的 反对称 (antisymmetry)关系。
例如
A上的 全域关系 EA,恒等关系 IA和 空关系 都是 A上的 对称关系 。
恒等关系 IA和 空关系 也是 A上的 反对称 关系。
但全域关系 EA一般不是 A上的反对称关系，除非 A为单元集或空集。
例 7.11
例 7.11 设 A＝ {1,2,3},R1,R2,R3和 R4都是 A上的关系，其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,1>,<1,2>,<2,1>}
R3＝ {<1,2>,<1,3>}
R4＝ {<1,2>,<2,1>,<1,3>}
说明 R1,R2,R3和 R4是否为 A上对称和反对称的关系。
解答 R1既是对称也是反对称的。
R2是对称的但不是反对称的。
R3是反对称的但不是对称的。
R4既不是对称的也不是反对称的。
传递性定义 7.13 设 R为 A上的关系，若
x?y?z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)
则称 R是 A上的 传递 (transitivity)关系。
例如
A上的 全域关系 EA,恒等关系 IA和 空关系 都是 A上的 传递关系 。
小于等于关系,整除关系 和 包含关系 也是相应集合上的 传递关系 。
小于关系 和 真包含关系 仍旧是相应集合上的传递关系。
例 7.12
例 7.12 设 A＝ {1,2,3},R1,R2,R3是 A上的关系，其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,2>,<2,3>}
R3＝ {<1,3>}
说明 R1,R2和 R3是否为 A上的传递关系。
解答
R1和 R3是 A上的传递关系，
R2不是 A上的传递关系。
关系性质的等价描述定理 7.9 设 R为 A上的关系，则
1） R在 A上自反当且仅当 IA? R
2） R在 A上反自反当且仅当 R∩I A＝?
3） R在 A上对称当且仅当 R＝ R-1
4） R在 A上反对称当且仅当 R∩R -1? IA
5） R在 A上传递当且仅当 R?R?R
说明? 利用该定理可以从关系的集合表达式来判断或证明关系的性质。
分析 关系性质的证明方法定理 7.9 (1)的证明
（ 1） R在 A上自反当且仅当 IA? R
必要性 。
任取 <x,y>,有
<x,y>∈I A
x,y∈A ∧ x ＝ y
<x,y>∈R
所以 IA? R
充分性 。
任取 x,有
x∈A
<x,x>∈I A
<x,x>∈R
所以 R在 A上是自反的。
定理 7.9 (2)的证明
（ 2） R在 A上反自反当且仅当 R∩I A＝?
充分性。
任取 x,有
x∈A
<x,x>∈I A
<x,x>?R (R∩I A=?)
所以 R在 A上是反自反的。
必要性。用反证法。
假设 R∩I A≠?，
必存在 <x,y>∈R∩I A。
由于 IA是 A上恒等关系，
可知 x∈A 且 <x,x>∈R 。
这与 R在 A上是反自反的相矛盾。
定理 7.9 (3)的证明
（ 3） R在 A上对称当且仅当 R＝ R-1
必要性。
任取 <x,y>,有
<x,y>∈R
<y,x>∈R
(因为 R在 A上对称 )
<x,y>∈R -1
所以 R＝ R-1
充分性。
任取 <x,y>，
由 R＝ R-1 得
<x,y>∈R
<y,x>∈R -1
<y,x>∈R
所以 R在 A上是对称的。
定理 7.9 (4)的证明
（ 4） R在 A上反对称当且仅当 R∩R -1? IA
必要性。
任取 <x,y>,有
<x,y>∈R∩R -1
<x,y>∈R ∧ <x,y>∈R -1
<x,y>∈R ∧ <y,x>∈R
x＝ y (R是反对称的 )
<x,y>∈I A
所以 R∩R -1?IA
充分性。
任取 <x,y>,则有
<x,y>∈R ∧ <y,x>∈R
<x,y>∈R ∧ <x,y>∈R -1
<x,y>∈R∩R -1
<x,y>∈I A (R∩R -1?IA)
x＝ y
所以 R在 A上是反对称的。
定理 7.9 (5)的证明
（ 5） R在 A上传递当且仅当 R?R?R
必要性 。任取 <x,y>,有
<x,y>∈R?R
t(<x,t>∈R∧< t,y>∈R)
<x,y>∈R (因为 R在 A上是传递的 )
所以 R?R?R。
充分性 。任取 <x,y>,<y,z>∈R,则
<x,y>∈R∧<y,z>∈R
<x,z>∈R?R
<x,z>∈R (因为 R?R?R)
所以 R在 A上是传递的。
例 7.13
例 7.13 设 A是集合,R1和 R2是 A上的关系，证明：
(1)若 R1,R2是自反的和对称的，则 R1∪R 2也是自反的和对称的。
(2)若 R1和 R2是传递的，则 R1∩R 2也是传递的。
例 7.13 (1)的证明
(1)若 R1,R2是自反的和对称的，则 R1∪R 2也是自反的和对称的。
证明 由于 R1和 R2是 A上的自反关系，故有
IA? R1 和 IA? R2
从而得到 IA? R1∪R 2。
根据定理 7.9可知 R1∪R 2在 A上是自反的。
再由 R1和 R2的对称性有
R1＝ R1-1 和 R2＝ R2-1
根据练习七第 18题的结果有
(R1∪R 2)-1＝ R1-1∪R 2-1＝ R1∪R 2
从而证明了 R1∪R 2也是 A上对称的关系。
例 7.13 (2)的证明
(2)若 R1和 R2是传递的，则 R1∩R 2也是传递的。
证明 由 R1和 R2的传递性有
R1? R1? R1 和 R2? R2? R2
再使用定理 7.4得
(R1∩R 2)?(R1∩R 2)
R1? R1∩R 1? R2∩R 2? R1∩R 2? R2
(R1∩R 2)∩R 1? R2∩R 2? R1
(将前面的包含式代入 )
R1∩R 2
从而证明了 R1∩R 2也是 A上的传递关系。
关系性质的特点自反性 反自反性 对称性 反对称性 传递性集合表达式 IA? R R∩I A＝? R＝ R-1 R∩R -1? IA R?R?R
关系矩阵 主对角线元素全是 1
主对角线元素全是 0
矩阵是对称矩阵若 rij＝ 1，
且 i≠j,则
rji＝ 0
对 M2中 1所在位置,M
中相应的位置都是 1
关系图 每个顶点都有环每个顶点都没有环如果两个顶点之间有边，一定是一对方向相反的边 (无单边 )
如果两点之间有边，一定是一条有向边 (无双向边 )
如果顶点 xi
到 xj有边，
xj到 xk有边
，则从 xi到
xk也有边例 7.14
例 7.14 判断下图中关系的性质，并说明理由。
（ 1）对称的，不是自反的，不是反自反的，不是反对称的，
不是传递的。
（ 2）是反自反的，不是自反的，是反对称的，不是对称的，
是传递的 。
（ 3） 是自反的，不是反自反的，是反对称的，不是对称的，
不是传递的。
关系的性质和运算之间的关系自反性 反自反性 对称性 反对称性 传递性
R1-1 √ √ √ √ √
R1∩R 2 √ √ √ √ √
R1∪R 2 √ √ √ × ×
R1－ R2 × √ √ √ ×
R1? R2 √ × × × ×
问题
如果存在一条从数据中心 a到 b的电话线,<a,b>就属于关系 R。
如何确定从一个中心是否有一条电话线 (可能不直接 )链接到另一个中心？
通过构造 包含 R的 最小 的 传递关系 来找出每一对有着联系的数据中心，这个关系叫做 R的 传递闭包 。
波士顿 芝加哥丹佛底特律圣地亚哥纽约
7.5 关系的闭包
闭包（ closure） 的定义
闭包的构造方法
闭包的性质
闭包的相互关系闭包的定义定义 7.14 设 R是非空集合 A上的关系,R的 自反 （ 对称 或 传递 ）
闭包 是 A上的关系 R′,使得 R′ 满足以下条件：
（ 1） R′ 是 自反 的（ 对称 的或 传递 的）
（ 2） R?R′
（ 3） 对 A上任何包含 R的 自反 （ 对称 或 传递 ）关系 R″ 有
R′? R″ 。
一般将 R的 自反闭包 记作 r(R),对称闭包 记作 s(R),传递闭包 记作 t(R)。
闭包的构造方法定理 7.10 设 R为 A上的关系，则有
（ 1） r(R)＝ R∪ R0
（ 2） s(R)＝ R∪ R-1
（ 3） t(R)＝ R∪ R2∪R 3∪ …
证明思路
(1)和 (2)：证明右边的集合满足闭包定义的三个条件。
(3) 采用集合相等的证明方法。
证明左边包含右边，即 t(R)包含每个 Rn。
证明右边包含左边，即 R∪ R2∪ … 具有传递的性质。
定理 7.10 (1)的证明
（ 1） r(R)＝ R∪R 0
证明 ① 由 IA＝ R
0? R∪R 0,可知 R∪R 0是自反的，
② R?R∪R 0。
③ 设 R″是 A上包含 R的自反关系，
则有 R?R″和 IA?R″。
任取 <x,y>,必有
<x,y>∈ R∪R 0
<x,y>∈R∪I A
<x,y>∈R ″∪R ″＝ R″
所以 R∪R 0? R″。
综上所述,r(R)＝ R∪R 0。
定理 7.10 (2)的证明
（ 2） s(R)＝ R∪R -1
证明 ① R?R∪R
-1。
② 证明 R∪R -1是对称的，
任取 <x,y>,有
<x,y>∈ R∪R -1
<x,y>∈R∨<x,y>∈R -1
<y,x>∈R -1∨<y,x>∈R
<y,x>∈ R∪R -1
所以 R∪R -1 是对称的 。
综上所述,s(R)＝ R∪R -1。
③ 设 R″ 是包含 R的对称关系，
任取 <x,y>,有
<x,y>∈ R∪R -1
<x,y>∈R∨<x,y>∈R -1
<x,y>∈R∨<y,x>∈R
<x,y>∈R ″ ∨<y,x>∈R ″
<x,y>∈R ″ ∨<x,y>∈R ″
<x,y>∈R ″
所以 R∪R -1?R″ 。
定理 7.10 (3)的证明
（ 3） t(R)＝ R∪R 2∪R 3∪ …
证明 先证 R∪R2∪ …? t(R)成立，为此只需证明对任意的正整数 n有 Rn? t(R)即可。用归纳法。
n＝ 1时，有 R1＝ R? t(R)。
假设 Rn?t(R)成立，那么对任意的 <x,y>有
<x,y>∈R n+1＝ Rn? R
t(<x,t>∈R n∧< t,y>∈R)
t(<x,t>∈t(R)∧< t,y>∈t(R))
<x,y>∈t(R) （ 因为 t(R)是传递的）
这就证明了 Rn+1? t(R)。
由归纳法命题得证。
定理 7.10 (3)的证明
（ 3） t(R)＝ R∪R 2∪R 3∪ …
证明 再证 t(R)?R∪R
2∪ … 成立，为此只须证明 R∪R 2∪ … 是传递的。
任取 <x,y>,<y,z>,则
<x,y>∈R∪R 2∪ … ∧ <y,z>∈R∪R 2∪ …
t(<x,y>∈R t) ∧?s(<y,z>∈R s)
t?s(<x,y>∈R t ∧ <y,z>∈R s)
t?s(<x,z>∈R t? Rs)
t?s(<x,z>∈R t+s)
<x,z>∈R∪R 2∪ …
从而证明了 R∪R 2∪ … 是传递的。
推论推论 设 R为有穷集 A上的关系，则存在正整数 r使得
t(R)=R∪R 2∪ … ∪R r
证明 由定理 7.6和 7.10(3)得证。
例题 求整数集合 Z上的关系 R＝ {<a,b> | a<b}的自反闭包和对称闭包。
解答 r(R)＝ R∪R 0＝ {<a,b>|a<b}∪{<a,b>|a ＝ b}
＝ {<a,b>|a?b}
s(R)＝ R∪R -1＝ {<a,b>|a<b}∪{<b,a>|b<a}
＝ {<a,b>|a≠b}
通过关系矩阵求闭包的方法设关系 R,r(R),s(R),t(R)的关系矩阵分别为 M,Mr,Ms和
Mt,则
Mr ＝ M＋ E 对角线上的值都改为 1
Ms ＝ M＋ M′ 若 aij＝ 1,则令 aji＝ 1
Mt ＝ M＋ M2＋ M3＋ … 沃舍尔算法其中 E是和 M同阶的单位矩阵,M′ 是 M的转置矩阵。
注意在上述等式中矩阵的元素相加时使用逻辑加。
通过关系图求闭包的方法设关系 R,r(R),s(R),t(R)的关系图分别记为 G,Gr,Gs，
Gt,则 Gr,Gs,Gt的顶点集与 G的顶点集相等。
除了 G的边以外，以下述方法 添加新的边 。
1)考察 G的每个顶点，如果 没有环就加上一个环 。最终得到的是 Gr。
2)考察 G的每一条边,如果有一条 xi到 xj的单向边,i≠j,则在 G中 加一条边 xj到 xi的反方向边 。最终得到 Gs。
3)考察 G的每个顶点 xi,找出从 xi出发的所有 2步,3步,…,n
步长的路径 （ n为 G中的顶点数）。
设路径的终点为 。
如果没有从 xi到 (l=1,2,…,k)的边，就加上这条边。当检查完所有的顶点后就得到图 Gt。
k21 jjj x,,x,x?
Ijx
例 7.15
例 7.15 设 A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}
,则 R和 r(R),s(R),t(R)的关系图如下图所示。其中 r(R)，
s(R),t(R)的关系图就是使用上述方法直接从 R的关系图得到的。
Warshall 算法输入,M（ R的关系矩阵）
输出,MT（ t(R)的关系矩阵 ）
1.MT←M
2.for k ← 1 to n do
3,for i ← 1 to n do
4,for j ← 1 to n do
5,MT[i,j]←M T[i,j]+MT[i,k]*MT[k,j]
注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。
Warshall 算法 举例例 设 A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，
求 t(R)。
0010
1000
0101
0010
M 0
0010
1000
0111
0010
M 1
分析 k＝ 1 时,MT[i,j]←M T[i,j]+MT[i,1]*MT[1,j]
MT[1,j]←M T[1,j]+MT[1,1]*MT[1,j]
MT[2,j]←M T[2,j]+MT[2,1]*MT[1,j] 将第 1行加到第 2行上
MT[3,j]←M T[3,j]+MT[3,1]*MT[1,j]
MT[4,j]←M T[4,j]+MT[4,1]*MT[1,j]
得到 M1。
Warshall 算法 举例
0010
1000
0101
0010
M 0
0010
1000
0111
0010
M 1
0111
1000
0111
0111
M 2
k＝ 1时，第 1列中只有 M[2,1]
＝ 1,将第 1行加到第 2行上。
k＝ 2时，第 2列中 M[1,2]＝
M[2,2]＝ M[4,2]＝ 1,将第 2
行分别加到第 1,2,4行上。
Warshall 算法 举例
0111
1000
0111
0111
M 2
1111
1000
1111
1111
M 3
1111
1111
1111
1111
M 4
k＝ 3时，第 3列中 M[1,3]＝ M[2,3]
＝ M[4,3]＝ 1,将第 3行分别加到第 1,2,4行上。
k＝ 4时，第 4列中 M[1,4]＝
M[2,4]＝ M[3,4]＝ M[4,4]＝ 1，
将第 4行分别加到第 1,2,3,4行上。
闭包的主要性质定理 7.11 设 R是非空集合 A上的关系，则
（ 1） R是自反的当且仅当 r(R)＝ R。
（ 2） R是对称的当且仅当 s(R)＝ R。
（ 3） R是传递的当且仅当 t(R)＝ R。
证明 （ 1）充分性。
因为 R＝ r(R),所以 R是自反的。
必要性。
显然有 R? r(R)。
由于 R是包含 R的自反关系，根据自反闭包定义有 r(R)?R。
从而得到 r(R)=R。
闭包的主要性质定理 7.12 设 R1和 R2是非空集合 A上的关系，且 R1? R2,则
（ 1） r(R1)? r(R2)
（ 2） s(R1)? s(R2)
（ 3） t(R1)? t(R2)
证明,(1)任取 <x,y>,有
<x,y>∈r(R 1)
<x,y>∈R 1∪I A
<x,y>∈R 1 ∨ <x,y>∈I A
<x,y>∈R 2 ∨ <x,y>∈I A
<x,y>∈R 2∪I A
<x,y>∈r(R 2)
命题命题 R是对称的，则 Rn也是对称的，其中 n是任何正整数。
证明
n=1,R1＝ R显然是对称的。
假设 Rn是对称的，则对任意的 <x,y>,有
<x,y>∈R n+1
<x,y>∈R n? R
t(<x,t>∈R n∧< t,y>∈R)
t(<t,x>∈R n∧<y,t>∈R)
<y,x>∈R?Rn
<y,x>∈R 1+n＝ Rn+1
所以 Rn+1是对称的。由归纳法命题得证。
关系性质与闭包运算之间的联系定理 7.13 设 R是非空集合 A上的关系，
（ 1）若 R是自反的，则 s(R)与 t(R)也是自反的。
（ 2）若 R是对称的，则 r(R)与 t(R)也是对称的。
（ 3）若 R是传递的，则 r(R)是传递的。
证明：只证（ 2）。
定理 7.13 (2)的证明
（ 2）若 R是对称的，则 r(R)与 t(R)也是对称的。
证明 r(R)是对 称的。
由于 R是 A上的对称关系，所以 R＝ R-1,同时 IA＝ IA-1。
r(R)-1 ＝ (R∪R 0)-1
＝ (R∪I A)-1
＝ R-1∪I A-1
＝ R∪I A
＝ r(R)
所以,r(R)是对称的。
定理 7.13 (2)的证明
（ 2）若 R是对称的，则 r(R)与 t(R)也是对称的。
下面证明 t(R)的对称性。
任取 <x,y>
<x,y>∈t(R)
n(<x,y>∈R n)
n(<y,x>∈R n) （ 因为 Rn是对称的）
<y,x>∈t(R)
所以,t(R)是 对称的。
定理 7.13的讨论
从这里可以看出，如果计算关系 R的自反、对称、传递的闭包,为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边,若令 tsr(R)表示 R的自反、对称、传递闭包，
则
tsr(R)=t(s(r(R)))
自反性 对称性 传递性
r(R) √ √ √
s(R) √ √ × (反例 )
t(R) √ √ √
反例 A={1,2,3}，
R={<1,3>} 是传递的
s(R)={<1,3>,<3,1>}
显然 s(R)不是传递的。
7.6 等价关系与划分定义 7.15 设 R为非空集合上的关系。如果 R是 自反的,对称的和 传递的,则称 R为 A上的 等价关系 (equivalent relation)。
设 R是一个等价关系，若 <x,y>∈R,称 x等价于 y,记做 x～
y。
举例 (1)平面上三角形集合中，三角形的相似关系。
(2)人群中的同性关系。
例 7.16
例 7.16 设 A＝ {1,2,…,8},如下定义 A上的关系 R：
R＝ {<x,y>|x,y∈A∧x≡y(mod 3)}
其中 x≡y(mod 3) 叫做 x与 y模 3相等,即 x除以 3的余数与 y除以 3
的余数相等。不难验证 R为 A上的等价关系，因为
x∈A,有 x≡x(mod 3)
x,y∈A,若 x≡y(mod 3),则有 y≡x(mod 3)
x,y,z∈A,若 x≡y(mod 3),y≡z(mod 3),则有 x≡z(mod 3)
等价类定义 7.16 设 R为非空集合 A上的等价关系,?x∈A,令
[x]R={y|y∈A∧xRy}
称 [x]R为 x关于 R的 等价类,简称为 x的 等价类,简记为 [x]
或 x 。
x的等价类是 A中所有与 x等价的元素构成的集合。
例 7.16中的等价类是：
[1]＝ [4]＝ [7]＝ {1,4,7}
[2]＝ [5]＝ [8]＝ {2,5,8}
[3]＝ [6]＝ {3,6}
整数集合 Z上的模 n等价关系设 x是任意整数,n为给定的正整数，则存在唯一的整数 q和 r,使得
x＝ qn+r
其中 0? r?n -1,称 r为 x除以 n的余数 。
例如 n＝ 3,那么－ 8除以 3的余数为 1，因为 -8＝ -3× 3+1
对于任意的整数 x和 y,定义 模 n相等关系～
x～ y? x≡y(mod n)
不难验证它是整数集合 Z上的等价关系。
将 Z中的所有整数根据它们除以 n的余数分类如下：
0的数，其形式为 nz,z∈Z
余数为 1的数，其形式为 nz+1,z∈Z
…
余数是 n-1的数，其形式为 nz+n-1,z∈Z
以上构成了 n个等价类，使用等价类的符号可记为
[i]＝ {nz+i|z∈Z},i=0,1,…,n-1
等价类的性质定理 7.14 设 R是非空集合 A上的等价关系，则
1）?x∈A,[x]是 A的非空子集。
2）?x,y∈A,如果 xRy,则 [x]＝ [y]。
3）?x,y∈A,如果 <x,y>?R,则 [x]与 [y]不交。
4） ∪{[ x]|x∈A} ＝ A。
证明 （ 1） 由等价类的定义可知,?x∈A 有 [x]?A。
又由于等价关系的自反性有 x∈[x],即 [x]非空。
定理 7.14
（ 2）?x,y∈A,如果 xRy,则 [x]=[y]。
任取 z,则有
z∈[x]
<x,z>∈R
<z,x>∈R (因为 R是对称的 )
<z,x>∈R ∧ <x,y>∈R
<z,y>∈R (因为 R是传递的 )
<y,z>∈R (因为 R是对称的 )
z∈[y] 。
所以 [x]?[y]。
同理可证 [y]?[x]。
因此,[x]=[y]。
定理 7.14
（ 3）?x,y∈A,如果 <x,y>?R,则 [x]与 [y]不交。
假设 [x]∩[y]≠?,
则存在 z∈[x]∩[y],
从而有 z∈[x]∧ z∈[y],
即 <x,z>∈R∧<y,z>∈R 成立。
根据 R的对称性和传递性，必有 <x,y>∈R,与 <x,y>?R矛盾，
即假设错误，原命题成立。
定理 7.14
（ 4） ∪{[ x]|x∈A} ＝ A。
先证 ∪{[ x]|x∈A}?A
任取 y,y∈∪{[x]|x∈A}
x(x∈A∧y∈[ x])
y∈A (因为 [x]?A)
从而有 ∪{[ x]|x∈A}? A。
再证 A?∪{[x]|x∈A}
任取 y,y∈A? y∈[y]∧y∈A
y∈∪{[x]|x∈A}
从而有 A?{[x]|x∈A} 成立。
∪{[ x]|x∈A} ＝ A。
商集定义 7.17 设 R为非空集合 A上的等价关系，以 R的所有等价类作为元素的集合称为 A关于 R的 商集 (quotient set),记做
A/R,即
A/R={[x]R|x∈A}
例 7.16中的商集为
{{1,4,7},{2,5,8},{3,6}}
整数集合 Z上模 n等价关系的商集是
{{nz+i|z∈Z}|i=0,1,…,n-1}
划分定义 7.18 设 A为非空集合，若 A的子集族 π(π?P(A),是 A的子集构成的集合 ) 满足下面的条件：
（ 1）π
2）?x?y(x,y∈π∧x≠y→x∩y ＝?)
3） ∪π=A
则称 π 是 A的一个 划分 (partitions)，称 π 中的元素为 A的 划分块 。
说明? 设集合 π 是 A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于 A,则称 π 是集合 A的划分 。
例 7.17
例 7.17 设 A＝ {a,b,c,d},给定 π 1,π 2,π 3,π 4,π 5,π 6,如下：
π 1={{a,b,c},{d}}
π 2={{a,b},{c},{d}}
π 3={{a},{a,b,c,d}}
π 4={{a,b},{c}}
π 5={?,{a,b},{c,d}}
π 6={{a,{a}},{b,c,d}}
判断哪一个是 A的划分
π 1和 π 2是 A的划分，其它都不是 A的划分。
因为 π 3中的子集 {a}和 {a,b,c,d}有交,∪ π 4≠A,π 5中含有空集，而 π 6根本不是 A的子集族。
商集与划分
商集就是 A的一个划分，并且不同的商集将对应于不同的划分。
反之，任给 A的一个划分 π,如下定义 A上的关系 R：
R={<x,y>|x,y∈A∧x 与 y在 π 的同一划分块中 }
则不难证明 R为 A上的等价关系，且该等价关系所确定的商集就是 π 。
由此可见,A上的等价关系与 A的划分是一一对应的 。
例 7.18
例 7.18 给出 A＝ {1,2,3}上所有的等价关系这些划分与 A上的等价关系之间的一一对应是：
π 1对应于全域关系 EA，
π 5的对应于恒等关系 IA，
π 2,π 3和 π 4分别对应于等价关系 R2,R3和 R4。 其中
R2={<2,3>,<3,2>}∪I A
R3={<1,3>,<3,1>}∪I A
R4={<1,2>,<2,1>}∪I A
例题例题 问集合 A＝ {a,b,c,d}上有多少个不同的等价关系？
解答 只要求出 A上的全部划分，即为等价关系。
划分为 一个块 的情况,1种，即 {a,b,c,d}
划分为 两个块 的情况,7种，即
{{a,b},{c,d}},{{a,c},{b,d}},{{a,d},{b,c}}
{{a},{b,c,d}},{{b},{a,c,d}},{{c},{a,b,d}}，
{{d},{a,b,c}}
划分为 三个块 的情况,6种，即
{{a,b},{c},{d}},{{a,c},{b},{d}},{{a,d},{b},{c}},
{{a},{b},{c,d}},{{a},{c},{b,d}},{{a},{d},{b,c}}
划分为 四个块 的情况,1种，即 {a},{b},{c},{d}}
因此，共有 15种不同的等价关系。
7.7 偏序 (partial order)关系定义 7.19 设 R为非空集合 A上的关系。如果 R是 自反 的,反对称的和 传递 的，则称 R为 A上的 偏序关系,记作? 。
设? 为偏序关系，如果 <x,y>∈?,则记作 x?y,读作 ―x小于或等于 y‖。
注意 这里的,小于或等于,不是指数的大小，而是 在偏序关系中的顺序性 。 x,小于或等于,y的含义是：依照这个序,x
排在 y的前边或者 x就是 y。 根据不同偏序的定义，对序有着不同的解释。
偏序关系举例集合 A上的恒等关系 IA 小于或等于关系整除关系 包含关系可比定义 7.20 设 R为非空集合 A上的偏序关系，定义
(1)?x,y∈A,x＜ y? x? y∧x≠y 。
(2)?x,y∈A,x与 y可比? x? y∨y? x。
其中 x＜ y读作 x―小于,y。 这里所说的,小于,是指在偏序中 x排在 y的前边。
在具有偏序关系的集合 A中任取两个元素 x和 y,可能有下述几种情况发生：
x＜ y(或 y＜ x),x＝ y,x与 y不是可比的。
例如 A＝ {1,2,3},? 是 A上的整除关系，则有
1＜ 2,1＜ 3，
1=1,2=2,3=3，
2和 3不可比。
全序关系定义 7.21 设 R为非空集合 A上的偏序关系，如果?x,y∈A,x与
y都是可比的,则称 R为 A上的 全序关系 (或 线序关系 )。
例如数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。
整除关系一般来说不是全序关系，如集合 {1,2,3}上的整除关系就不是全序关系，因为 2和 3不可比。
偏序集定义 7.22 集合 A和 A上的偏序关系? 一起叫做 偏序集,记作
<A,? >。
例如整数集合 Z和数的小于或等于关系? 构成偏序集 <Z,?>
集合 A的幂集 P(A)和包含关系 R?构成偏序集 <P(A),R?>。
覆盖 (cover)
定义 7.23 设 <A,?> 为偏序集。x,y∈A,如果 x＜ y 且不存在 z∈A 使得 x＜ z＜ y,则称 y覆盖 x。
例如 {1,2,4,6}集合上的整除关系，
有 2覆盖 1,4和 6都覆盖 2。但 4不覆盖 1，因为有 1＜ 2＜ 4。
6也不覆盖 4，因为 4＜ 6不成立。
哈斯图 (Hasse diagram)
利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为 哈斯图 。
画偏序集 <A,?> 的哈斯图的方法
(1)用小圆圈代表元素。
(2)?x,y∈A,若 x＜ y,则将 x画在 y的下方。
(3)对于 A中的两个不同元素 x和 y,如果 y覆盖 x,就用一条线段连接 x和 y。
例 7.19
例 7.19 画出偏序集 <{1,2,3,4,5,6,7,8,9},R整除 >和
<P({a,b,c}),R?>的哈斯图。
例 7.20
例 7.20 已知偏序集 <A,R>的哈斯图如右图所示，试求出集合 A和关系 R的表达式。
解答
A={a,b,c,d,e,f,g,h}
R={ <b,d>,<b,e>,<b,f>,<c,d>,
<c,e>,<c,f>,<d,f>,<e,f>,
<g,h>}∪I A
偏序集中的特殊元素定义 7.24 设 <A,? >为偏序集,B?A,y∈B 。
1） 若?x(x∈B→ y? x)成立，则称 y为 B的 最小元 。
2）若?x(x∈B→x? y)成立，则称 y为 B的 最大元 。
3）若?x(x∈B∧x? y→x ＝ y)成立，则称 y为 B的 极小元 。
4）若?x(x∈B∧ y? x→x ＝ y)成立，则称 y为 B的 极大元 。
36
3
24
2
12
6
B 最大元 最小元 极大元 极小元
{2,3,6,12
,24,36}
{6,12}
{2,3,6}
{6}
无 无 24,26 2,3
12 6 12 6
6 无 6 2,3
6 6 6 6
特殊元素的性质
最小元是 B中最小的元素，它与 B中其它元素都可比。
极小元不一定与 B中元素可比，只要没有比它小的元素，
它就是极小元。
对于有穷集 B,极小元一定存在，但最小元不一定存在。
最小元如果存在，一定是唯一的。
极小元可能有多个，但不同的极小元之间是不可比的（无关系）。
如果 B中只有一个极小元，则它一定是 B的最小元。
哈斯图中，集合 B的极小元是 B中各元素中的最底层。
例 7.21
例 7.21 设偏序集 <A,?> 如右图所示，求 A的极小元、最小元、极大元、最大元。
解答极小元,a,b,c,g
极大元,a,f,h。
没有最小元与最大元说明 哈斯图中的孤立顶点既是极小元也是极大元。
例 7.22
例 7.22 设 X为集合,A＝ P(X)－ {?}－ {X},且 A≠?。
若 |X|＝ n,问：
（ 1）偏序集 <A,R?>是否存在最大元？
（ 2）偏序集 <A,R?>是否存在最小元？
（ 3）偏序集 <A,R?>中极大元和极小元的一般形式是什么？
并说明理由。
解答 <A,R?>不存在最小元和最大元，因为 n?2 。
考察幂集 P(X)的哈斯图，最底层的顶点是空集，记作第 0层
。由底向上，第 1层是单元集，第 2层是二元子集,… 由
|X|=n,则第 n－ 1层是 X的 n－ 1元子集，第 n层，也就是最高层只有一个顶点 X。 偏序集 <A,R?>与 <P(X),R?>相比，恰好缺少第 0层与第 n层 (因为 X是 n元集 )。因此 <A,R?>的极小元就是 X的所有单元集，即 {x},x∈X ； 而极大元恰好少一个元素，即 X-{x},x∈X 。
上界、下界定义 7.25 设 <A,?> 为偏序集,B?A,y∈A 。
（ 1） 若?x(x∈B→x? y)成立，则称 y为 B的 上界 。
（ 2）若?x(x∈B→ y?x) 成立，则称 y为 B的 下界 。
（ 3）令 C＝ {y|y为 B的上界 }，则称 C的最小元为 B的 最小上界或 上确界 。
（ 4）令 D＝ {y|y为 B的下界 }，则称 D的最大元为 B的 最大下界或 下确界 。
上界与下界举例
36
3
24
2
12
6
B 上界 下界 上确界 下确界
{2,3,6,12
,24,36}
{6,12}
{2,3,6}
{6}
无 无 无 无
12,24,36 2,3,6 12 6
6,12,24,36 无 6 无
6,12,24,36 2,3,6 6 6
考虑右图中的偏序集。令 B＝ {b
,c,d},则 B的下界和最大下界都不存在，上界有 d和 f,最小上界为 d。
上界与下界的性质
B的最小元一定是 B的下界，同时也是 B的最大下界。
B的最大元一定是 B的上界，同时也是 B的最小上界。
B的下界不一定是 B的最小元，因为它可能不是 B中的元素。
B的上界也不一定是 B的最大元。
B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。
偏序关系的实例 —调 度问题给定有穷的任务集 T和 m台相同的机器,T上存在偏序关系?,
如果 t1<t2,那么任务 t1完成以后 t2才能开始工作 。
t∈T,
l(t)表示完成任务 t所需要的时间，
d(t)表示任务 t的截止时间，
l(t),d(t)∈Z +。
设开始时间为 0，
f:T→{0,1,…,D}表示任务集 T的一个调度方案，
其中 f(t)表示任务 t的开始时间。
D表示完成所有任务的最终时间。
偏序关系的实例 —调 度问题假设每项任务都可以安排在任何一台机器上进行工作，
如果 f满足下述三个条件，则称 T为 可行调度 。
(1)?t∈T,f(t)+l(t)?d(t)
（ 表示每项任务都要在截至时间内完成 ）
(2)?i,0?i?D,|{t∈T:f(t)?i ＜ f(t)+l(t)}|?m
（ 表示任何时刻同时工作的机器台数不超过 m）
(3)?t,t′∈ T,t＜ t′?f(t)+l(t)?f(t ′ )
（ 表示任务安排必须满足任务集的偏序约束 ）
求使得 D最小的可行调度。
例 7.23
设 m＝ 2,T＝ {t1,t2,…,t6},每项任务的截止时间都等于 7。去掉自反成分,T的偏序约束如右图所示。每个任务结点中的数字表示完成该任务所有的时间。
1
t6
1
t5
2
t4
1 2
1
t3 t2
t1
下图中给出了两个可行的调度方案。
t6 t4 t2 t1
t5 t3?
t4 t2 t1
t6 t5 t3?
D＝ 6
D＝ 5
本章主要内容
有序对与卡氏积
二元关系（包括空关系，恒等关系，全域关系等）及其表示
（关系矩阵，关系图）
关系的五种性质（自反性，反自反性，对称性，反对称性，
传递性）
二元关系的幂运算
关系的三种闭包（自反闭包，对称闭包，传递闭包）
等价关系和划分（包括等价类，商集，划分块等）
偏序关系（包括哈斯图，最大元，最小元，极大元，极小元
，上界，下界，最小上界，最大下界等）
本章学习要求
掌握：有序对及卡氏积的概念及卡氏积的性质
掌握：二元关系,A到 B的二元关系,A上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系在集合上的限制，集合在关系下的象等概念，掌握关系的定义域
、值域、逆、合成、限制、象等的主要性质
掌握：关系矩阵与关系图的概念及求法
掌握：集合 A上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质本章学习要求
掌握,A上二元关系的 n次幂的定义及主要性质
掌握 A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法
掌握：等价关系、等价类、商集、划分、等概念，以及等价关系与划分之间的对应
掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念作业习题七,
1,3,4,12,13,14,16,22,26、
31,32,39,42,46,48
关系性质的证明
通常的证明方法是利用定义证明。
R在 A上自反任取 x,有
x∈A? …………………………………?<x,x>∈R
R在 A上对称任取 <x,y>,有
<x,y>∈R? ……………………………?<y,x>∈R
R在 A上反对称任取 <x,y>,有
<x,y>∈R ∧ <x,y>∈R? ……………? x＝ y
R在 A上传递任取 <x,y>,<y,z>,有
<x,y>∈R ∧ <y,z>∈R? ……………? <x,z>∈R
有关关系性质的练习题
在正整数集合上定义关系 R：
<x,y>∈R,如果 x和 y的最大公因子是 1。
判断 R是否满足关系的五条性质？
设 A={a,b,c},试给出 A的一个二元关系 R,使其同时不满足五个性质。
N元素集合上有多少个自反的关系？
例题例题 在正整数集合上定义关系 R：
<x,y>∈R,如果 x和 y的最大公因子是 1。
判断 R是否满足关系的五条性质？
分析 按增序系统地列出所有的序对，然后观察。
<x,y> x＋ y 最大公因子 是否在 R中
<1,1> 2 1 是
<1,2> 3 1 是
<2,1> 3 1 是
<1,3> 4 1 是
<2,2> 4 2 否
<3,1> 4 1 是
…… … … …
例题解答 自反 否 <2,2>?R
反自反 否 <1,1>?R
对称 是 <x,y>∈R→<y,x>∈R
反对称 否 <1,2>∈R∧<2,1>∈R 但 1≠ 2
传递 否 <2,1>∈R∧<1,2>∈R 但 <2,2>?R
扩展 (1)从列出的若干序偶来考察是否属于关系。
(2)按一定规则列出序偶。
(3)一个范例即可证明不满足某种性质。
(4)证明某种性质成立，必须取出关系中的每个元素。
例题例题 设 A={a,b,c},试给出 A的一个二元关系 R,使其同时不满足五个性质。
分析 因为关系的各种性质的存在，都要求满足一定的条件
，要做的就是创造或破坏这些条件。
从 A× A出发，通过删除某些序偶，使其不满足那些性质。
解答 令 R＝ {<a,a>,<b,b>,<b,c>,<c,b>,<c,a>}
<c,c>?R 不满足自反性
<a,a>∈R 不满足反自反性
<c,a>∈R ∧ <a,c>?R 不满足对称性
<b,c>∈R∧<c,b>∈R∧b ≠ c 不满足反对称性
<b,c>∈R∧<c,a>∈R∧<b,a>?R 不满足传递性习题设 R＝ {<x,y>|x,y∈N 且 x+3y＝ 12}
(1)求 R的集合表达式
(2)求 dom R，
ran R
(3)求 R?R
(4)求 R↑{2,3,4,6}
(5)求 R[{3}]
(6)R3
解答：
{<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}
{0,3,6,9,12}，
{0,1,2,3,4}
{<3,3>,<12,4>}
{<3,3>,<6,2>}
{3}
{<3,3>}
习题
设 R是复数集合 C上的关系，且满足 xRy?x-y＝ a+bi,a和 b
为给定的非负整数，试确定 R的性质并证明之。
解答
（ 1）当 a＝ b＝ 0时，满足自反性、对称性、反对称性和传递性，不满足反自反性。
（ 2）当 a,b不全为 0时，只满足反自反性、反对称性。
习题例题 设 I为整数集,R＝ {<x,y>|x≡y(mod k)},证明 R是等价关系 。
证明 设任意 a,b,c∈I
(1)因为 a－ a＝ 0,所以 <a,a>∈R 。
(2)若 a≡b(mod k),a－ b＝ kt(t为整数 ),则
b－ a＝ -kt,所以 b≡a(mod k)。
(3)若 a≡b(mod k),b≡c(mod k),则
a－ b＝ kt,b－ c＝ ks(t和 s为整数 )，
a－ c＝ a－ b＋ b－ c＝ kt＋ ks＝ k(t＋ s)，
所以 a≡c(mod k)
因此,R是等价关系 。
本章的主要内容
– 有序对与笛卡儿集
– 二元关系的定义和表示法
– 关系的运算
– 关系的性质
– 关系的闭包
– 等价关系与划分
– 偏序关系
本章与后续各章的关系
– 本章是函数的基础
– 本章是图论的基础本章内容
7.1 有序对与笛卡儿积
7.2 二元关系
7.3 关系的运算
7.4 关系的性质
7.5 关系的闭包
7.6 等价关系与划分
7.7 偏序关系本章小结习题作业
7.1 有序对与笛卡儿积定义 7.1 由两个元素 x和 y（ 允许 x=y） 按一定顺序排列成的二元组叫做一个 有序对 (ordered pair)或 序偶,记作 <x,y>,其中 x
是它的第一元素,y是它的第二元素。
有序对 <x,y>具有以下性质：
（ 1）当 x≠y 时,<x,y>≠<y,x> 。
（ 2） <x,y>＝ <u,v>的充分必要条件是 x＝ u且 y＝ v。
说明? 有序对中的元素是有序的
集合中的元素是无序的例 7.1
例 7.1 已知 <x+2,4>＝ <5,2x+y>,求 x和 y。
由有序对相等的充要条件有
x+2＝ 5
2x+y＝ 4
解得 x＝ 3,y＝ -2。
解答定义 7.2 设 A,B为集合,用 A中元素为第一元素,B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做 A和 B
的 笛卡儿积 (Cartesian product)，记作 A× B。
笛卡儿积的符号化表示为
A× B＝ {<x,y>|x∈A∧y∈B}
笛卡儿积的定义
A表示某大学所有学生的集合,B表示大学开设的所有课程的集合，
则 A× B可以用来表示该校学生选课的所有可能情况。
令 A是直角坐标系中 x轴上的点集,B是直角坐标系中 y
轴上的点集，
于是 A× B就和平面点集一一对应。
举例笛卡尔积举例设 A={a,b},B={0,1,2},则
A× B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}
B× A={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
举例说明? 如果 |A|=m,|B|=n,则 |A× B|=mn。
笛卡儿积的运算性质
(1)对任意集合 A,根据定义有
A×?＝?,?×A＝?
(2)一般的说,笛卡儿积运算不满足交换律,即
A×B≠B ×A (当 A≠? ∧ B≠? ∧ A≠B 时 )
(3)笛卡儿积运算不满足结合律,即
(A×B)×C≠A ×(B×C) (当 A≠? ∧ B≠? ∧ C≠? 时 )
(4)笛卡儿积运算对并和交运算满足分配律,即
A×(B∪ C)=(A×B)∪ (A×C)
(B∪ C)×A=(B×A)∪ (C×A)
A×(B∩ C)=(A×B)∩ (A×C)
(B∩ C)×A=(B×A)∩ (C×A)
(5)A?C ∧ B?D? A×B? C×D
A×(B∪C)=(A ×B)∪(A ×C)的证明任取 <x,y>
<x,y>∈A × (B∪C)
x∈A ∧ y∈B∪C
x∈A ∧ (y∈B∨y∈C)
(x∈A∧y∈B) ∨ (x∈A∧y∈C)
<x,y>∈A × B ∨ <x,y>∈A × C
<x,y>∈(A × B)∪(A × C)
所以 A×(B∪ C)=(A×B)∪ (A×C)
关于 A?C∧B?D? A×B?C×D的讨论该性质的逆命题不成立，可分以下情况讨论。
（ 1）当 A=B=?时，显然有 A?C 和 B?D 成立。
（ 2）当 A≠?且 B≠?时，也有 A?C和 B?D成立，证明如下：
任取 x∈A,由于 B≠?,必存在 y∈B,因此有
x∈A∧y∈B
<x,y>∈A × B
<x,y>∈C × D
x∈C∧y∈D
x∈C
从而证明了 A?C。
同理可证 B?D。
关于 A?C∧B?D? A×B?C×D的讨论该性质的逆命题不成立，可分以下情况讨论。
（ 3）当 A＝?而 B≠?时，有 A?C成立，但不一定有 B?D成立。
反例：令 A＝?,B＝ {1},C＝ {3},D＝ {4}。
（ 4）当 A≠?而 B＝?时，有 B?D成立，但不一定有 A?C成立。
反例略。
例 7.2
例 7.2 设 A={1,2},求 P(A)× A。
P(A)× A
＝ {?,{1},{2},{1,2}}× {1,2}
＝ {<?,1>,<?,2>,
<{1},1>,<{1},2>,
<{2},1>,<{2},2>,
<{1,2},1>,<{1,2},2>}
解答例 7.3
例 7.3 设 A,B,C,D为任意集合，判断以下命题是否为真，并说明理由。
(1) A× B＝ A× C? B＝ C
(2) A-(B× C)＝ (A-B)× (A-C)
(3) A＝ B∧ C＝ D? A× C＝ B× D
(4) 存在集合 A,使得 A? A× A
(1) 不一定为真。当 A＝?,B＝ {1},C＝ {2}时，有
A× B＝?＝ A× C,但 B≠C 。
(2) 不一定为真。当 A=B={1},C＝ {2}时，有
A-(B× C)＝ {1}–{<1,2>}＝ {1}
(A-B)× (A-C)＝?× {1}＝?
(3) 为真。由等量代入的原理可证。
(4) 为真。当 A＝?时，有 A?A× A 成立。
解答
7.2 二元关系 (binary relation)
定义 7.3 如果一个集合满足以下条件之一：
（ 1）集合非空，且它的元素都是有序对
（ 2）集合是空集则称该集合为一个 二元关系,记作 R。 二元关系也可简称为 关系 。对于二元关系 R,如果 <x,y>∈R,可记作 xRy； 如果
<x,y>?R,则记作 xRy。
设 R1＝ {<1,2>,<a,b>},R2＝ {<1,2>,a,b}。
则 R1是二元关系,R2不是二元关系，只是一个集合，
除非将 a和 b定义为有序对。
根据上面的记法可以写 1R12,aR1b,aR1c等。
举例
R＝ {<上,下 >,<前,后 >,<正,反 >,<左,右 >}是否为二元关系？
集合 A上的二元关系的数目依赖于 A中的元素数。
如果 |A|=n,那么 |A× A|=n2,A× A的子集就有 个。
每一个子集代表一个 A上的二元关系，所以 A上有 个不同的二元关系。
例如 |A|=3,则 A上有 个不同的二元关系。
7.2 二元关系定义 7.4 设 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上的二元关系。
举例
22n
22n
232
说明常用的关系定义 7.5 对任意集合 A,定义全域关系 EA={<x,y>|x∈A∧y∈A}=A × A
恒等关系 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,y∈A∧x?y},其中 A?R。
整除关系,DB={<x,y>|x,y∈B∧x 整除 y},其中 A?Z*
Z*是非零整数集
包含关系,R?＝ {<x,y>|x,y∈A∧x?y},其中 A是集合族。
(1)设 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>}
(2)令 A=P(B)={?,{a},{b},{a,b}},则 A上的包含关系是
R?＝ {<?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,
<{a},{a}>,<{a},{a,b}>,<{b},{b}>,
<{b},{a,b}>,<{a,b},{a,b}>}
举例例 7.4
例 7.4 设 A={1,2,3,4},下面各式定义的 R都是 A上的关系，
试用列元素法表示 R。
(1) R={<x,y> | x是 y的倍数 }
(2) R={<x,y> | (x-y)2∈A}
(3) R={<x,y> | x/y是素数 }
(4) R={<x,y> | x≠y}
解答
(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}
(2)R={<2,1>,<3,2>,<4,3>,<3,1>,<4,2>,<2,4>,<1,3>,<3,4>,
<2,3>,<1,2>}
(3)R={<2,1>,<3,1>,<4,2>}
(4)R=EA-IA={<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,
<3,2>,<3,4>,<4,1>,<4,2>,<4,3>}
关系的表示方法
关系的三种表示方法：
– 集合表达式
– 关系矩阵
– 关系图
关系矩阵和关系图可以表示有穷集上的关系。
关系矩阵和关系图的定义设 A={x1,x2,…,xn},R是 A上的关系。令
n),1,2,j( i,Rx若x0 Rx若x1{r
ji
ji
ij
nnn2n1
2n2221
1n1211
ij
rrr
rrr
rrr
)(r
则是 R的 关系矩阵,记作 MR。
设 A={x1,x2,…,xn},R是 A上的关系。令图 G=<V,E>,其中顶点集合 V=A,边集为 E。 对于? xi,xj∈V,满足
<xi,xj>∈E? xiRxj
称图 G为 R的 关系图,记作 GR。
关系矩阵和关系图的实例设 A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}，
则 R的关系矩阵和关系图分别是
0010
0000
1100
0011
M R
7.3 关系的运算定义 7.6 设 R是二元关系。
(1)R中所有有序对的第一元素构成的集合称为 R的 定义域
(domain),记为 dom R。 形式化表示为：
dom R ＝ {x |?y(<x,y>∈R )}
(2)R中所有有序对的第二元素构成的集合称为 R的 值域 (range)
，记作 ran R。 形式化表示为
ran R＝ {y |? x(<x,y>∈R)}
(3)R的定义域和值域的并集称为 R的 域 (field)，记作 fld R。
形式化表示为
fld R＝ dom R ∪ ran R
例 7.5 求 R={<1,2>,<1,3>,<2,4>,<4,3>}的定义域、值域和域。
解答 dom R＝ {1,2,4} ran R＝ {2,3,4} fld R＝ {1,2,3,4}
关系的逆和右复合运算定义 7.7 设 R为二元关系,R的逆关系，简称 R的 逆 (inverse)，
记作 R-1,其中
R-1＝ {<x,y>|<y,x>∈R}
定义 7.8 设 F,G为二元关系,G对 F的 右复合 (composite)记作
F?G,其中
F?G＝ {<x,y> |?t(<x,t>∈F∧< t,y>∈G)}
例 7.6 设 F＝ {<3,3>,<6,2>},G={<2,3>},则
F-1 ＝ {<3,3>,<2,6>}
F?G＝ {<6,3>} G?F＝ {<2,3>}
说明? 可以把二元关系看作一种作用,<x,y>∈R 可以解释为
x通过 R的作用变到 y。
F?G表示两个作用的连续发生。
关系的限制和像定义 7.9 设 R为二元关系,A是集合
(1) R在 A上的 限制 (restriction)记作 R↑ A,其中
R↑A={<x,y>|xRy∧x∈A}
(2) A在 R下的 像 (image)记作 R[A],其中
R[A]=ran(R↑A)
说明? R在 A上的限制 R↑A 是 R的子关系。 A在 R下的像 R[A]是 ran R的子集。
例 7.7
设 R＝ {<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}
R↑ {1}＝ {<1,2>,<1,3>}
R↑? ＝?
R↑ {2,3}＝ {<2,2>,<2,4>},<3,2>}
R[{1}]＝ {2,3}
R[?] ＝?
R[{3}]＝ {2}
关系与集合的说明
关系是集合，集合运算对于关系也是适用的。
规定：
– 关系运算中逆运算优先于其它运算
– 所有的关系运算都优先于集合运算，
– 优先权的运算以括号决定运算顺序。
例如：
– ran F-1
– F?G∪F?H
– ran (F↑A)
例题
设 A表示是学校的所有学生的集合,B表示学校的所有课程的集合，并设 R1由所有有序对 <a,b>组成，其中 a是选修课程 b的学生
。 R2由所有的有序对 <a,b>构成，其中课程 b是 a的必修课。则关系 R1∪R 2,R1∩R 2,R1⊕R 2,R1－ R2,R2－ R1的含义为
R1∪R 2,a是一个学生，他或者选修了课程 b,或者课程 b是他的必修课。
R1∩R 2,a是一个学生，他选修了课程 b并且课程 b也是 a的必修课。
R1⊕R 2,学生 a已经选修了课程 b,但课程 b不是 a的选修课，或者课程 b是 a的必修课，但是 a没有选修它。
R1－ R2,学生 a已经选修了课程 b,但课程 b不是 a的选修课。
R2－ R1,课程 b是学生 a的必修课，但是 a没有选修它。
定理 7.1
定理 7.1 设 F是任意的关系，则
(1)(F-1)-1＝ F
(2)dom F-1＝ ran F,ran F-1＝ dom F
(1)任取 <x,y>,由逆的定义有
<x,y>∈ (F-1)-1
<y,x>∈ F-1
<x,y>∈F
(2)任取 x
x∈ dom F-1
y(<x,y>∈F -1)
y(<y,x>∈F)
x∈ran F
所以有 dom F-1＝ ran F
证明定理 7.2
定理 7.2 设 F,G,H是任意的关系，则
(1)(F?G)?H＝ F?(G?H)
(2)(F?G)-1＝ G-1? F-1
证明 (1)任取 <x,y>，
<x,y>∈ (F?G)?H
t(<x,t>∈F?G∧( t,y)∈H)
t(?s(<x,s>∈F∧< s,t>∈G)∧< t,y>∈H)
t?s(<x,s>∈F∧< s,t>∈G∧< t,y>∈H)
s(<x,s>∈F∧?t(<s,t>∈G∧< t,y>∈H))
s(<x,s>∈F∧< s,y>∈G?H)
<x,y>∈ F?(G?H)
定理 7.2
定理 7.2 设 F,G,H是任意的关系，则
(1)(F?G)?H＝ F?(G?H)
(2)(F?G)-1＝ G-1?F-1
证明 (2)任取 <x,y>，
<x,y>∈ (F?G)-1
<y,x>∈F?G
t(<y,t>∈F∧< t,x>∈G)
t(<t,y>∈F -1∧<x,t>∈G -1)
<x,y>∈G -1? F-1
定理 7.3
定理 7.3 设 R为 A上的关系，则
R? IA＝ IA? R＝ R
证明 (1)任取 <x,y>，
<x,y>∈ R? IA
t(<x,t>∈R∧( t,y)∈I A)
t(<x,t>∈R∧ t＝ y)
<x,y>∈R
<x,y>∈ R
<x,y>∈R∧y∈A
<x,y>∈R∧<y,y>∈I A)
<x,y>∈ R? IA
综上所述，有 R?IA＝ R
同理可证 IA?R＝ R
定理 7.4
定理 7.4 设 F,G,H是任意的关系，则
(1) F?(G∪ H)＝ F?G∪F?H
(2) (G∪H)?F＝ G?F∪H?F
(3) F?(G∩H)?F?G∩F?H
(4) (G∩H)?F?G?F∩ H?F
证明 (3) <x,y>∈ F?(G∩H)
t(<x,t>∈F∧( t,y)∈G∩H)
t(<x,t>∈F∧( t,y)∈G∧( t,y)∈H)
t((<x,t>∈F∧( t,y)∈G ) ∧ (<x,t>∈F∧( t,y)∈H ))
t(<x,t>∈F∧( t,y)∈G) ∧?t(<x,t>∈F∧( t,y)∈H)
<x,y>∈F?G ∧ <x,y>∈F?H
<x,y>∈ F?G∩F?H
定理 7.4的推论
由数学归纳法不难证明定理 7.4的结论对于有限多个关系的并和交也是成立的，即有
R?(R1∪R 2∪ … ∪R n)＝ R?R1∪R?R2∪ … ∪R?Rn
R1?∪R 2∪ … ∪R n)?R＝ R1?R∪R 2?R∪ … ∪R n?R
R?(R1∩R 2∩ … ∩R n)?R?R1∩R?R2∩ … ∩R?Rn
R1∩R 2∩ … ∩R n)?R?R1?R∩R 2?R∩ … ∩R n?R
定理 7.5
定理 7.5 设 F为关系,A,B为集合，则
(1) F↑(A∪B) ＝ F↑A∪F↑B
(2) F[A∪B] ＝ F[A]∪F[B]
(3) F↑(A∩B) ＝ F↑A∩F↑B
(4) F[A∩B]?F[A]∩F[B]
定理 7.5 (1)的证明
(1) F↑(A∪B) ＝ F↑A∪F↑B
证明 任取 <x,y>，
<x,y>∈F↑(A∪B)
<x,y>∈F ∧ x∈(A∪B)
<x,y>∈F ∧ (x∈A∨x∈B)
(<x,y>∈F∧x∈A) ∨ (<x,y>∈F∧x∈B)
<x,y>∈F ↑ A ∨ <x,y>∈F ↑ B
<x,y>∈F ↑ A∪F ↑ B
所以有 F↑(A∪B) ＝ F↑A∪F↑B 。
定理 7.5 (4)的证明
(4) F[A∩B]?F[A]∩F[B]
证明 任取 y，
y∈F[A∩B]
x(<x,y>∈F∧ x∈A∩B)
x(<x,y>∈F∧ x∈A∧ x∈B)
x((<x,y>∈F∧ x∈A)∧(< x,y>∈F∧ x∈B))
x(<x,y>∈F∧ x∈A) ∧?x(<x,y>∈F∧ x∈B)
y∈F[A] ∧ y∈F[B]
y∈F[A]∩F[B]
所以有 F[A∩B]?F[A]∩F[B]
关系的幂运算定义 7.10 设 R为 A上的关系,n为自然数，则 R的 n次幂定义为：
（ 1） R0＝ {<x,x>|x∈A} ＝ IA
（ 2） Rn+1＝ Rn? R
说明? 对于 A上的任何关系 R1和 R2都有R
1
0＝ R
2
0＝ I
A
即,A上任何关系的 0次幂都相等，都等于 A上的恒等关系 IA。
对于 A上的任何关系 R都有 R1＝ R,因为
R1＝ R0? R＝ IA? R＝ R
Rn的计算
给定 A上的关系 R和自然数 n,怎样计算 Rn呢？
若 n是 0或 1，结果是很简单的。下面考虑 n?2 的情况。
– 如果 R是用 集合表达式 给出的，可以通过 n-1次右复合 计算得到 Rn。
– 如果 R是用 关系矩阵 M给出的，则 Rn的关系矩阵是 Mn,即 n
个矩阵 M之积 。与普通矩阵乘法不同的是，其中的相加是逻辑加，即
1+1＝ 1,1+0＝ 0+1＝ 1,0+0＝ 0
– 如果 R是用 关系图 G给出的，可以直接由图 G得到 Rn的关系图 G'。 G'的顶点集与 G相同。考察 G的每个顶点 xi,如果 在
G中从 xi出发经过 n步长的路径到达顶点 xj,则在 G'中加一条从 xi到 xj的边 。当把所有这样的便都找到以后，就得到图 G'。
例 7.8
例 7.8 设 A＝ {a,b,c,d},R＝ {<a,b>,<b,a>,<b,c>,<c,d>},求
R的各次幂，分别用矩阵和关系图表示。
解答
0000
1000
0101
0010
M
0000
1000
0101
0010
0000
1000
0101
0010
M 2
0000
1000
0101
0010
0000
0000
1010
0101
MMM 23
1000
0100
0010
0001
M 0
0000
0000
1010
0101
000
000
011
100
例 7.8
因此 M4＝ M2,即 R4＝ R2。 因此可以得到
R2＝ R4＝ R6＝ …
R3＝ R5＝ R7＝ …
用关系图的方法得到 R0,R1,R2,R3,… 的关系图如下图所示。
0000
1000
0101
0010
0000
0000
0101
1010
MMM 34
0000
0000
1010
0101
幂运算的性质定理 7.6 设 A为 n元集,R是 A上的关系，则存在自然数 s和 t,
使得 Rs=Rt。
R为 A上的关系，对任何自然数 k,Rk都是 A× A的子集。证明又知 |A× A|=n2,|P(A× A)|=,2n2
即 A× A的不同子集仅 个。2n2
当列出 R的各次幂 R0,R1,R2,…,,… 时，2n2R
必存在自然数 s和 t使得 Rs=Rt。
说明? 该定理说明有穷集上只有有穷多个不同的二元关系。当 t足够大时,Rt必与某个 Rs(s<t)相等。
如例 7.8中的 R4=R2。
定理 7.7
定理 7.7 设 R是 A上的关系,m,n∈N,则
(1)Rm? Rn＝ Rm+n
(2)(Rm)n＝ Rmn
证明 (1)对于任意给定的 m∈N,施归纳于 n。
若 n=0,则有所以对一切 m,n∈N 有 Rm? Rn＝ Rm+n。
Rm? R0＝ Rm? IA＝ Rm＝ Rm+0
假设 Rm? Rn=Rm+n,则有
Rm? Rn+1＝ Rm?(Rn? R)＝ (Rm? Rn)?R＝ Rm+n+1，
定理 7.7
定理 7.7 设 R是 A上的关系,m,n∈N,则
(1)Rm? Rn＝ Rm+n
(2)(Rm)n＝ Rmn
证明 (2)对于任意给定的 m∈N,施归纳于 n。
若 n=0,则有所以对一切 m,n∈N 有 (Rm)n=Rmn。
(Rm)0＝ IA＝ R0＝ Rm× 0
假设 (Rm)n＝ Rmn,则有
(Rm)n+1＝ (Rm)n? Rm＝ Rmn+m＝ Rm(n+1)
定理 7.8
定理 7.8 设 R是 A上的关系，若存在自然数 s,t(s<t)使得 Rs=Rt,则
(1) 对任何 k∈N 有 Rs+k=Rt+k
(2) 对任何 k,i∈N 有 Rs+kp+i=Rs+i,其中 p=t-s
(3) 令 S={R0,R1,…,Rt-1},则对于任意的 q∈N 有 Rq∈S
证明 (1) R
s+k＝ Rs? Rk＝ Rt? Rk＝ Rt+k
(2)对 k归纳。
若 k=0,则有 Rs+0 p+i＝ Rs+i
假设 Rs+kp+i＝ Rs+i,其中 p＝ t-s,则
Rs+(k+1)p+i＝ Rs+kp+i+p＝ Rs+i? Rp=Rs+p+i
＝ Rs+t-s+i＝ Rt+i＝ Rs+i
由归纳法命题得证。
Rs+kp+i? Rp＝
定理 7.8
定理 7.8 设 R是 A上的关系，若存在自然数 s,t(s<t)使得 Rs=Rt,则
(1) 对任何 k∈N 有 Rs+k=Rt+k
(2) 对任何 k,i∈N 有 Rs+kp+i=Rs+i,其中 p=t-s
(3) 令 S={R0,R1,…,Rt-1},则对于任意的 q∈N 有 Rq∈S
证明 (3)任取 q∈N,若 q<t,显然有 Rq∈S,
若 q?t,则存在自然数 k和 i使得
q＝ s+kp+i
其中 0? i?p -1,p＝ t-s。 于是
Rq＝ Rs+kp+i＝ Rs+i
s+i?s+p -1 ＝ s+t-s-1＝ t-1
这就证明了 Rq∈S 。
定理 7.8的说明
有穷集 A上的关系 R的幂序列 R0,R1,… 是一个周期性变化的序列。就象正弦函数一样，利用它的周期性可以将 R的高次幂化简为 R的低次幂。
例 7.9 设 A={a,b,d,e,f},R={<a,b>,<b,a>,<d,e>,<e,f>,<f,d>}
。 求出最小的自然数 m和 n,使得 m<n且 Rm=Rn。
解答 由 R的定义可以看出 A中的元素可分成两组，即 {a,b}和
{d,e,f}。 它们在 R的右复合运算下有下述变化规律：
a→b→a→b …
d→e→f→d→e→f …
对于 a或 b,每个元素的变化周期是 2。对于 d,e,f,每个元素的变化周期是 3。因此必有 Rm=Rm+6,其中 6是 2和 3的最小公倍数。取 m=0,n=6即满足题目要求。
7.4 关系的性质
自反性
反自反性
对称性
反对称性
传递性自反性和反自反性定义 7.11 设 R为 A上的关系，
(1)若?x(x∈A→ <x,x>∈R),则称 R在 A上是 自反 (reflexivity)
的。
(2)若?x(x∈A→<x,x>?R),则称 R在 A上是 反自反
(irreflexivity)的。
例如 全域关系 EA,恒等关系 IA,小于等于关系 LA,整除关系
DA都是为 A上的 自反关系 。
包含关系 R是给定集合族 A上的 自反关系 。
小于关系 和 真包含关系 都是给定集合或集合族上的 反自反关系 。
例 7.10
例 7.10 设 A={1,2,3},R1,R2,R3是 A上的关系，其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,1>,<2,2>,<3,3>,<1,2>}
R3＝ {<1,3>}
说明 R1,R2和 R3是否为 A上的自反关系和反自反关系。
解答
R1既不是自反的也不是反自反的，
R2是自反的，
R3是反自反的。
对称性和反对称性定义 7.12 设 R为 A上的关系，
（ 1）若?x?y(x,y∈A∧<x,y>∈R→<y,x>∈R),则称 R为 A上对称 (symmetry)的关系。
（ 2）若?x?y(x,y∈A∧<x,y>∈R∧<y,x>∈R→x=y),则称 R
为 A上的 反对称 (antisymmetry)关系。
例如
A上的 全域关系 EA,恒等关系 IA和 空关系 都是 A上的 对称关系 。
恒等关系 IA和 空关系 也是 A上的 反对称 关系。
但全域关系 EA一般不是 A上的反对称关系，除非 A为单元集或空集。
例 7.11
例 7.11 设 A＝ {1,2,3},R1,R2,R3和 R4都是 A上的关系，其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,1>,<1,2>,<2,1>}
R3＝ {<1,2>,<1,3>}
R4＝ {<1,2>,<2,1>,<1,3>}
说明 R1,R2,R3和 R4是否为 A上对称和反对称的关系。
解答 R1既是对称也是反对称的。
R2是对称的但不是反对称的。
R3是反对称的但不是对称的。
R4既不是对称的也不是反对称的。
传递性定义 7.13 设 R为 A上的关系，若
x?y?z(x,y,z∈A∧<x,y>∈R∧<y,z>∈R→<x,z>∈R)
则称 R是 A上的 传递 (transitivity)关系。
例如
A上的 全域关系 EA,恒等关系 IA和 空关系 都是 A上的 传递关系 。
小于等于关系,整除关系 和 包含关系 也是相应集合上的 传递关系 。
小于关系 和 真包含关系 仍旧是相应集合上的传递关系。
例 7.12
例 7.12 设 A＝ {1,2,3},R1,R2,R3是 A上的关系，其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,2>,<2,3>}
R3＝ {<1,3>}
说明 R1,R2和 R3是否为 A上的传递关系。
解答
R1和 R3是 A上的传递关系，
R2不是 A上的传递关系。
关系性质的等价描述定理 7.9 设 R为 A上的关系，则
1） R在 A上自反当且仅当 IA? R
2） R在 A上反自反当且仅当 R∩I A＝?
3） R在 A上对称当且仅当 R＝ R-1
4） R在 A上反对称当且仅当 R∩R -1? IA
5） R在 A上传递当且仅当 R?R?R
说明? 利用该定理可以从关系的集合表达式来判断或证明关系的性质。
分析 关系性质的证明方法定理 7.9 (1)的证明
（ 1） R在 A上自反当且仅当 IA? R
必要性 。
任取 <x,y>,有
<x,y>∈I A
x,y∈A ∧ x ＝ y
<x,y>∈R
所以 IA? R
充分性 。
任取 x,有
x∈A
<x,x>∈I A
<x,x>∈R
所以 R在 A上是自反的。
定理 7.9 (2)的证明
（ 2） R在 A上反自反当且仅当 R∩I A＝?
充分性。
任取 x,有
x∈A
<x,x>∈I A
<x,x>?R (R∩I A=?)
所以 R在 A上是反自反的。
必要性。用反证法。
假设 R∩I A≠?，
必存在 <x,y>∈R∩I A。
由于 IA是 A上恒等关系，
可知 x∈A 且 <x,x>∈R 。
这与 R在 A上是反自反的相矛盾。
定理 7.9 (3)的证明
（ 3） R在 A上对称当且仅当 R＝ R-1
必要性。
任取 <x,y>,有
<x,y>∈R
<y,x>∈R
(因为 R在 A上对称 )
<x,y>∈R -1
所以 R＝ R-1
充分性。
任取 <x,y>，
由 R＝ R-1 得
<x,y>∈R
<y,x>∈R -1
<y,x>∈R
所以 R在 A上是对称的。
定理 7.9 (4)的证明
（ 4） R在 A上反对称当且仅当 R∩R -1? IA
必要性。
任取 <x,y>,有
<x,y>∈R∩R -1
<x,y>∈R ∧ <x,y>∈R -1
<x,y>∈R ∧ <y,x>∈R
x＝ y (R是反对称的 )
<x,y>∈I A
所以 R∩R -1?IA
充分性。
任取 <x,y>,则有
<x,y>∈R ∧ <y,x>∈R
<x,y>∈R ∧ <x,y>∈R -1
<x,y>∈R∩R -1
<x,y>∈I A (R∩R -1?IA)
x＝ y
所以 R在 A上是反对称的。
定理 7.9 (5)的证明
（ 5） R在 A上传递当且仅当 R?R?R
必要性 。任取 <x,y>,有
<x,y>∈R?R
t(<x,t>∈R∧< t,y>∈R)
<x,y>∈R (因为 R在 A上是传递的 )
所以 R?R?R。
充分性 。任取 <x,y>,<y,z>∈R,则
<x,y>∈R∧<y,z>∈R
<x,z>∈R?R
<x,z>∈R (因为 R?R?R)
所以 R在 A上是传递的。
例 7.13
例 7.13 设 A是集合,R1和 R2是 A上的关系，证明：
(1)若 R1,R2是自反的和对称的，则 R1∪R 2也是自反的和对称的。
(2)若 R1和 R2是传递的，则 R1∩R 2也是传递的。
例 7.13 (1)的证明
(1)若 R1,R2是自反的和对称的，则 R1∪R 2也是自反的和对称的。
证明 由于 R1和 R2是 A上的自反关系，故有
IA? R1 和 IA? R2
从而得到 IA? R1∪R 2。
根据定理 7.9可知 R1∪R 2在 A上是自反的。
再由 R1和 R2的对称性有
R1＝ R1-1 和 R2＝ R2-1
根据练习七第 18题的结果有
(R1∪R 2)-1＝ R1-1∪R 2-1＝ R1∪R 2
从而证明了 R1∪R 2也是 A上对称的关系。
例 7.13 (2)的证明
(2)若 R1和 R2是传递的，则 R1∩R 2也是传递的。
证明 由 R1和 R2的传递性有
R1? R1? R1 和 R2? R2? R2
再使用定理 7.4得
(R1∩R 2)?(R1∩R 2)
R1? R1∩R 1? R2∩R 2? R1∩R 2? R2
(R1∩R 2)∩R 1? R2∩R 2? R1
(将前面的包含式代入 )
R1∩R 2
从而证明了 R1∩R 2也是 A上的传递关系。
关系性质的特点自反性 反自反性 对称性 反对称性 传递性集合表达式 IA? R R∩I A＝? R＝ R-1 R∩R -1? IA R?R?R
关系矩阵 主对角线元素全是 1
主对角线元素全是 0
矩阵是对称矩阵若 rij＝ 1，
且 i≠j,则
rji＝ 0
对 M2中 1所在位置,M
中相应的位置都是 1
关系图 每个顶点都有环每个顶点都没有环如果两个顶点之间有边，一定是一对方向相反的边 (无单边 )
如果两点之间有边，一定是一条有向边 (无双向边 )
如果顶点 xi
到 xj有边，
xj到 xk有边
，则从 xi到
xk也有边例 7.14
例 7.14 判断下图中关系的性质，并说明理由。
（ 1）对称的，不是自反的，不是反自反的，不是反对称的，
不是传递的。
（ 2）是反自反的，不是自反的，是反对称的，不是对称的，
是传递的 。
（ 3） 是自反的，不是反自反的，是反对称的，不是对称的，
不是传递的。
关系的性质和运算之间的关系自反性 反自反性 对称性 反对称性 传递性
R1-1 √ √ √ √ √
R1∩R 2 √ √ √ √ √
R1∪R 2 √ √ √ × ×
R1－ R2 × √ √ √ ×
R1? R2 √ × × × ×
问题
如果存在一条从数据中心 a到 b的电话线,<a,b>就属于关系 R。
如何确定从一个中心是否有一条电话线 (可能不直接 )链接到另一个中心？
通过构造 包含 R的 最小 的 传递关系 来找出每一对有着联系的数据中心，这个关系叫做 R的 传递闭包 。
波士顿 芝加哥丹佛底特律圣地亚哥纽约
7.5 关系的闭包
闭包（ closure） 的定义
闭包的构造方法
闭包的性质
闭包的相互关系闭包的定义定义 7.14 设 R是非空集合 A上的关系,R的 自反 （ 对称 或 传递 ）
闭包 是 A上的关系 R′,使得 R′ 满足以下条件：
（ 1） R′ 是 自反 的（ 对称 的或 传递 的）
（ 2） R?R′
（ 3） 对 A上任何包含 R的 自反 （ 对称 或 传递 ）关系 R″ 有
R′? R″ 。
一般将 R的 自反闭包 记作 r(R),对称闭包 记作 s(R),传递闭包 记作 t(R)。
闭包的构造方法定理 7.10 设 R为 A上的关系，则有
（ 1） r(R)＝ R∪ R0
（ 2） s(R)＝ R∪ R-1
（ 3） t(R)＝ R∪ R2∪R 3∪ …
证明思路
(1)和 (2)：证明右边的集合满足闭包定义的三个条件。
(3) 采用集合相等的证明方法。
证明左边包含右边，即 t(R)包含每个 Rn。
证明右边包含左边，即 R∪ R2∪ … 具有传递的性质。
定理 7.10 (1)的证明
（ 1） r(R)＝ R∪R 0
证明 ① 由 IA＝ R
0? R∪R 0,可知 R∪R 0是自反的，
② R?R∪R 0。
③ 设 R″是 A上包含 R的自反关系，
则有 R?R″和 IA?R″。
任取 <x,y>,必有
<x,y>∈ R∪R 0
<x,y>∈R∪I A
<x,y>∈R ″∪R ″＝ R″
所以 R∪R 0? R″。
综上所述,r(R)＝ R∪R 0。
定理 7.10 (2)的证明
（ 2） s(R)＝ R∪R -1
证明 ① R?R∪R
-1。
② 证明 R∪R -1是对称的，
任取 <x,y>,有
<x,y>∈ R∪R -1
<x,y>∈R∨<x,y>∈R -1
<y,x>∈R -1∨<y,x>∈R
<y,x>∈ R∪R -1
所以 R∪R -1 是对称的 。
综上所述,s(R)＝ R∪R -1。
③ 设 R″ 是包含 R的对称关系，
任取 <x,y>,有
<x,y>∈ R∪R -1
<x,y>∈R∨<x,y>∈R -1
<x,y>∈R∨<y,x>∈R
<x,y>∈R ″ ∨<y,x>∈R ″
<x,y>∈R ″ ∨<x,y>∈R ″
<x,y>∈R ″
所以 R∪R -1?R″ 。
定理 7.10 (3)的证明
（ 3） t(R)＝ R∪R 2∪R 3∪ …
证明 先证 R∪R2∪ …? t(R)成立，为此只需证明对任意的正整数 n有 Rn? t(R)即可。用归纳法。
n＝ 1时，有 R1＝ R? t(R)。
假设 Rn?t(R)成立，那么对任意的 <x,y>有
<x,y>∈R n+1＝ Rn? R
t(<x,t>∈R n∧< t,y>∈R)
t(<x,t>∈t(R)∧< t,y>∈t(R))
<x,y>∈t(R) （ 因为 t(R)是传递的）
这就证明了 Rn+1? t(R)。
由归纳法命题得证。
定理 7.10 (3)的证明
（ 3） t(R)＝ R∪R 2∪R 3∪ …
证明 再证 t(R)?R∪R
2∪ … 成立，为此只须证明 R∪R 2∪ … 是传递的。
任取 <x,y>,<y,z>,则
<x,y>∈R∪R 2∪ … ∧ <y,z>∈R∪R 2∪ …
t(<x,y>∈R t) ∧?s(<y,z>∈R s)
t?s(<x,y>∈R t ∧ <y,z>∈R s)
t?s(<x,z>∈R t? Rs)
t?s(<x,z>∈R t+s)
<x,z>∈R∪R 2∪ …
从而证明了 R∪R 2∪ … 是传递的。
推论推论 设 R为有穷集 A上的关系，则存在正整数 r使得
t(R)=R∪R 2∪ … ∪R r
证明 由定理 7.6和 7.10(3)得证。
例题 求整数集合 Z上的关系 R＝ {<a,b> | a<b}的自反闭包和对称闭包。
解答 r(R)＝ R∪R 0＝ {<a,b>|a<b}∪{<a,b>|a ＝ b}
＝ {<a,b>|a?b}
s(R)＝ R∪R -1＝ {<a,b>|a<b}∪{<b,a>|b<a}
＝ {<a,b>|a≠b}
通过关系矩阵求闭包的方法设关系 R,r(R),s(R),t(R)的关系矩阵分别为 M,Mr,Ms和
Mt,则
Mr ＝ M＋ E 对角线上的值都改为 1
Ms ＝ M＋ M′ 若 aij＝ 1,则令 aji＝ 1
Mt ＝ M＋ M2＋ M3＋ … 沃舍尔算法其中 E是和 M同阶的单位矩阵,M′ 是 M的转置矩阵。
注意在上述等式中矩阵的元素相加时使用逻辑加。
通过关系图求闭包的方法设关系 R,r(R),s(R),t(R)的关系图分别记为 G,Gr,Gs，
Gt,则 Gr,Gs,Gt的顶点集与 G的顶点集相等。
除了 G的边以外，以下述方法 添加新的边 。
1)考察 G的每个顶点，如果 没有环就加上一个环 。最终得到的是 Gr。
2)考察 G的每一条边,如果有一条 xi到 xj的单向边,i≠j,则在 G中 加一条边 xj到 xi的反方向边 。最终得到 Gs。
3)考察 G的每个顶点 xi,找出从 xi出发的所有 2步,3步,…,n
步长的路径 （ n为 G中的顶点数）。
设路径的终点为 。
如果没有从 xi到 (l=1,2,…,k)的边，就加上这条边。当检查完所有的顶点后就得到图 Gt。
k21 jjj x,,x,x?
Ijx
例 7.15
例 7.15 设 A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}
,则 R和 r(R),s(R),t(R)的关系图如下图所示。其中 r(R)，
s(R),t(R)的关系图就是使用上述方法直接从 R的关系图得到的。
Warshall 算法输入,M（ R的关系矩阵）
输出,MT（ t(R)的关系矩阵 ）
1.MT←M
2.for k ← 1 to n do
3,for i ← 1 to n do
4,for j ← 1 to n do
5,MT[i,j]←M T[i,j]+MT[i,k]*MT[k,j]
注意：算法中矩阵加法和乘法中的元素相加都使用逻辑加。
Warshall 算法 举例例 设 A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，
求 t(R)。
0010
1000
0101
0010
M 0
0010
1000
0111
0010
M 1
分析 k＝ 1 时,MT[i,j]←M T[i,j]+MT[i,1]*MT[1,j]
MT[1,j]←M T[1,j]+MT[1,1]*MT[1,j]
MT[2,j]←M T[2,j]+MT[2,1]*MT[1,j] 将第 1行加到第 2行上
MT[3,j]←M T[3,j]+MT[3,1]*MT[1,j]
MT[4,j]←M T[4,j]+MT[4,1]*MT[1,j]
得到 M1。
Warshall 算法 举例
0010
1000
0101
0010
M 0
0010
1000
0111
0010
M 1
0111
1000
0111
0111
M 2
k＝ 1时，第 1列中只有 M[2,1]
＝ 1,将第 1行加到第 2行上。
k＝ 2时，第 2列中 M[1,2]＝
M[2,2]＝ M[4,2]＝ 1,将第 2
行分别加到第 1,2,4行上。
Warshall 算法 举例
0111
1000
0111
0111
M 2
1111
1000
1111
1111
M 3
1111
1111
1111
1111
M 4
k＝ 3时，第 3列中 M[1,3]＝ M[2,3]
＝ M[4,3]＝ 1,将第 3行分别加到第 1,2,4行上。
k＝ 4时，第 4列中 M[1,4]＝
M[2,4]＝ M[3,4]＝ M[4,4]＝ 1，
将第 4行分别加到第 1,2,3,4行上。
闭包的主要性质定理 7.11 设 R是非空集合 A上的关系，则
（ 1） R是自反的当且仅当 r(R)＝ R。
（ 2） R是对称的当且仅当 s(R)＝ R。
（ 3） R是传递的当且仅当 t(R)＝ R。
证明 （ 1）充分性。
因为 R＝ r(R),所以 R是自反的。
必要性。
显然有 R? r(R)。
由于 R是包含 R的自反关系，根据自反闭包定义有 r(R)?R。
从而得到 r(R)=R。
闭包的主要性质定理 7.12 设 R1和 R2是非空集合 A上的关系，且 R1? R2,则
（ 1） r(R1)? r(R2)
（ 2） s(R1)? s(R2)
（ 3） t(R1)? t(R2)
证明,(1)任取 <x,y>,有
<x,y>∈r(R 1)
<x,y>∈R 1∪I A
<x,y>∈R 1 ∨ <x,y>∈I A
<x,y>∈R 2 ∨ <x,y>∈I A
<x,y>∈R 2∪I A
<x,y>∈r(R 2)
命题命题 R是对称的，则 Rn也是对称的，其中 n是任何正整数。
证明
n=1,R1＝ R显然是对称的。
假设 Rn是对称的，则对任意的 <x,y>,有
<x,y>∈R n+1
<x,y>∈R n? R
t(<x,t>∈R n∧< t,y>∈R)
t(<t,x>∈R n∧<y,t>∈R)
<y,x>∈R?Rn
<y,x>∈R 1+n＝ Rn+1
所以 Rn+1是对称的。由归纳法命题得证。
关系性质与闭包运算之间的联系定理 7.13 设 R是非空集合 A上的关系，
（ 1）若 R是自反的，则 s(R)与 t(R)也是自反的。
（ 2）若 R是对称的，则 r(R)与 t(R)也是对称的。
（ 3）若 R是传递的，则 r(R)是传递的。
证明：只证（ 2）。
定理 7.13 (2)的证明
（ 2）若 R是对称的，则 r(R)与 t(R)也是对称的。
证明 r(R)是对 称的。
由于 R是 A上的对称关系，所以 R＝ R-1,同时 IA＝ IA-1。
r(R)-1 ＝ (R∪R 0)-1
＝ (R∪I A)-1
＝ R-1∪I A-1
＝ R∪I A
＝ r(R)
所以,r(R)是对称的。
定理 7.13 (2)的证明
（ 2）若 R是对称的，则 r(R)与 t(R)也是对称的。
下面证明 t(R)的对称性。
任取 <x,y>
<x,y>∈t(R)
n(<x,y>∈R n)
n(<y,x>∈R n) （ 因为 Rn是对称的）
<y,x>∈t(R)
所以,t(R)是 对称的。
定理 7.13的讨论
从这里可以看出，如果计算关系 R的自反、对称、传递的闭包,为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边,若令 tsr(R)表示 R的自反、对称、传递闭包，
则
tsr(R)=t(s(r(R)))
自反性 对称性 传递性
r(R) √ √ √
s(R) √ √ × (反例 )
t(R) √ √ √
反例 A={1,2,3}，
R={<1,3>} 是传递的
s(R)={<1,3>,<3,1>}
显然 s(R)不是传递的。
7.6 等价关系与划分定义 7.15 设 R为非空集合上的关系。如果 R是 自反的,对称的和 传递的,则称 R为 A上的 等价关系 (equivalent relation)。
设 R是一个等价关系，若 <x,y>∈R,称 x等价于 y,记做 x～
y。
举例 (1)平面上三角形集合中，三角形的相似关系。
(2)人群中的同性关系。
例 7.16
例 7.16 设 A＝ {1,2,…,8},如下定义 A上的关系 R：
R＝ {<x,y>|x,y∈A∧x≡y(mod 3)}
其中 x≡y(mod 3) 叫做 x与 y模 3相等,即 x除以 3的余数与 y除以 3
的余数相等。不难验证 R为 A上的等价关系，因为
x∈A,有 x≡x(mod 3)
x,y∈A,若 x≡y(mod 3),则有 y≡x(mod 3)
x,y,z∈A,若 x≡y(mod 3),y≡z(mod 3),则有 x≡z(mod 3)
等价类定义 7.16 设 R为非空集合 A上的等价关系,?x∈A,令
[x]R={y|y∈A∧xRy}
称 [x]R为 x关于 R的 等价类,简称为 x的 等价类,简记为 [x]
或 x 。
x的等价类是 A中所有与 x等价的元素构成的集合。
例 7.16中的等价类是：
[1]＝ [4]＝ [7]＝ {1,4,7}
[2]＝ [5]＝ [8]＝ {2,5,8}
[3]＝ [6]＝ {3,6}
整数集合 Z上的模 n等价关系设 x是任意整数,n为给定的正整数，则存在唯一的整数 q和 r,使得
x＝ qn+r
其中 0? r?n -1,称 r为 x除以 n的余数 。
例如 n＝ 3,那么－ 8除以 3的余数为 1，因为 -8＝ -3× 3+1
对于任意的整数 x和 y,定义 模 n相等关系～
x～ y? x≡y(mod n)
不难验证它是整数集合 Z上的等价关系。
将 Z中的所有整数根据它们除以 n的余数分类如下：
0的数，其形式为 nz,z∈Z
余数为 1的数，其形式为 nz+1,z∈Z
…
余数是 n-1的数，其形式为 nz+n-1,z∈Z
以上构成了 n个等价类，使用等价类的符号可记为
[i]＝ {nz+i|z∈Z},i=0,1,…,n-1
等价类的性质定理 7.14 设 R是非空集合 A上的等价关系，则
1）?x∈A,[x]是 A的非空子集。
2）?x,y∈A,如果 xRy,则 [x]＝ [y]。
3）?x,y∈A,如果 <x,y>?R,则 [x]与 [y]不交。
4） ∪{[ x]|x∈A} ＝ A。
证明 （ 1） 由等价类的定义可知,?x∈A 有 [x]?A。
又由于等价关系的自反性有 x∈[x],即 [x]非空。
定理 7.14
（ 2）?x,y∈A,如果 xRy,则 [x]=[y]。
任取 z,则有
z∈[x]
<x,z>∈R
<z,x>∈R (因为 R是对称的 )
<z,x>∈R ∧ <x,y>∈R
<z,y>∈R (因为 R是传递的 )
<y,z>∈R (因为 R是对称的 )
z∈[y] 。
所以 [x]?[y]。
同理可证 [y]?[x]。
因此,[x]=[y]。
定理 7.14
（ 3）?x,y∈A,如果 <x,y>?R,则 [x]与 [y]不交。
假设 [x]∩[y]≠?,
则存在 z∈[x]∩[y],
从而有 z∈[x]∧ z∈[y],
即 <x,z>∈R∧<y,z>∈R 成立。
根据 R的对称性和传递性，必有 <x,y>∈R,与 <x,y>?R矛盾，
即假设错误，原命题成立。
定理 7.14
（ 4） ∪{[ x]|x∈A} ＝ A。
先证 ∪{[ x]|x∈A}?A
任取 y,y∈∪{[x]|x∈A}
x(x∈A∧y∈[ x])
y∈A (因为 [x]?A)
从而有 ∪{[ x]|x∈A}? A。
再证 A?∪{[x]|x∈A}
任取 y,y∈A? y∈[y]∧y∈A
y∈∪{[x]|x∈A}
从而有 A?{[x]|x∈A} 成立。
∪{[ x]|x∈A} ＝ A。
商集定义 7.17 设 R为非空集合 A上的等价关系，以 R的所有等价类作为元素的集合称为 A关于 R的 商集 (quotient set),记做
A/R,即
A/R={[x]R|x∈A}
例 7.16中的商集为
{{1,4,7},{2,5,8},{3,6}}
整数集合 Z上模 n等价关系的商集是
{{nz+i|z∈Z}|i=0,1,…,n-1}
划分定义 7.18 设 A为非空集合，若 A的子集族 π(π?P(A),是 A的子集构成的集合 ) 满足下面的条件：
（ 1）π
2）?x?y(x,y∈π∧x≠y→x∩y ＝?)
3） ∪π=A
则称 π 是 A的一个 划分 (partitions)，称 π 中的元素为 A的 划分块 。
说明? 设集合 π 是 A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于 A,则称 π 是集合 A的划分 。
例 7.17
例 7.17 设 A＝ {a,b,c,d},给定 π 1,π 2,π 3,π 4,π 5,π 6,如下：
π 1={{a,b,c},{d}}
π 2={{a,b},{c},{d}}
π 3={{a},{a,b,c,d}}
π 4={{a,b},{c}}
π 5={?,{a,b},{c,d}}
π 6={{a,{a}},{b,c,d}}
判断哪一个是 A的划分
π 1和 π 2是 A的划分，其它都不是 A的划分。
因为 π 3中的子集 {a}和 {a,b,c,d}有交,∪ π 4≠A,π 5中含有空集，而 π 6根本不是 A的子集族。
商集与划分
商集就是 A的一个划分，并且不同的商集将对应于不同的划分。
反之，任给 A的一个划分 π,如下定义 A上的关系 R：
R={<x,y>|x,y∈A∧x 与 y在 π 的同一划分块中 }
则不难证明 R为 A上的等价关系，且该等价关系所确定的商集就是 π 。
由此可见,A上的等价关系与 A的划分是一一对应的 。
例 7.18
例 7.18 给出 A＝ {1,2,3}上所有的等价关系这些划分与 A上的等价关系之间的一一对应是：
π 1对应于全域关系 EA，
π 5的对应于恒等关系 IA，
π 2,π 3和 π 4分别对应于等价关系 R2,R3和 R4。 其中
R2={<2,3>,<3,2>}∪I A
R3={<1,3>,<3,1>}∪I A
R4={<1,2>,<2,1>}∪I A
例题例题 问集合 A＝ {a,b,c,d}上有多少个不同的等价关系？
解答 只要求出 A上的全部划分，即为等价关系。
划分为 一个块 的情况,1种，即 {a,b,c,d}
划分为 两个块 的情况,7种，即
{{a,b},{c,d}},{{a,c},{b,d}},{{a,d},{b,c}}
{{a},{b,c,d}},{{b},{a,c,d}},{{c},{a,b,d}}，
{{d},{a,b,c}}
划分为 三个块 的情况,6种，即
{{a,b},{c},{d}},{{a,c},{b},{d}},{{a,d},{b},{c}},
{{a},{b},{c,d}},{{a},{c},{b,d}},{{a},{d},{b,c}}
划分为 四个块 的情况,1种，即 {a},{b},{c},{d}}
因此，共有 15种不同的等价关系。
7.7 偏序 (partial order)关系定义 7.19 设 R为非空集合 A上的关系。如果 R是 自反 的,反对称的和 传递 的，则称 R为 A上的 偏序关系,记作? 。
设? 为偏序关系，如果 <x,y>∈?,则记作 x?y,读作 ―x小于或等于 y‖。
注意 这里的,小于或等于,不是指数的大小，而是 在偏序关系中的顺序性 。 x,小于或等于,y的含义是：依照这个序,x
排在 y的前边或者 x就是 y。 根据不同偏序的定义，对序有着不同的解释。
偏序关系举例集合 A上的恒等关系 IA 小于或等于关系整除关系 包含关系可比定义 7.20 设 R为非空集合 A上的偏序关系，定义
(1)?x,y∈A,x＜ y? x? y∧x≠y 。
(2)?x,y∈A,x与 y可比? x? y∨y? x。
其中 x＜ y读作 x―小于,y。 这里所说的,小于,是指在偏序中 x排在 y的前边。
在具有偏序关系的集合 A中任取两个元素 x和 y,可能有下述几种情况发生：
x＜ y(或 y＜ x),x＝ y,x与 y不是可比的。
例如 A＝ {1,2,3},? 是 A上的整除关系，则有
1＜ 2,1＜ 3，
1=1,2=2,3=3，
2和 3不可比。
全序关系定义 7.21 设 R为非空集合 A上的偏序关系，如果?x,y∈A,x与
y都是可比的,则称 R为 A上的 全序关系 (或 线序关系 )。
例如数集上的小于或等于关系是全序关系，因为任何两个数总是可比大小的。
整除关系一般来说不是全序关系，如集合 {1,2,3}上的整除关系就不是全序关系，因为 2和 3不可比。
偏序集定义 7.22 集合 A和 A上的偏序关系? 一起叫做 偏序集,记作
<A,? >。
例如整数集合 Z和数的小于或等于关系? 构成偏序集 <Z,?>
集合 A的幂集 P(A)和包含关系 R?构成偏序集 <P(A),R?>。
覆盖 (cover)
定义 7.23 设 <A,?> 为偏序集。x,y∈A,如果 x＜ y 且不存在 z∈A 使得 x＜ z＜ y,则称 y覆盖 x。
例如 {1,2,4,6}集合上的整除关系，
有 2覆盖 1,4和 6都覆盖 2。但 4不覆盖 1，因为有 1＜ 2＜ 4。
6也不覆盖 4，因为 4＜ 6不成立。
哈斯图 (Hasse diagram)
利用偏序关系的自反性、反对称性和传递性所得到的偏序集合图，称为 哈斯图 。
画偏序集 <A,?> 的哈斯图的方法
(1)用小圆圈代表元素。
(2)?x,y∈A,若 x＜ y,则将 x画在 y的下方。
(3)对于 A中的两个不同元素 x和 y,如果 y覆盖 x,就用一条线段连接 x和 y。
例 7.19
例 7.19 画出偏序集 <{1,2,3,4,5,6,7,8,9},R整除 >和
<P({a,b,c}),R?>的哈斯图。
例 7.20
例 7.20 已知偏序集 <A,R>的哈斯图如右图所示，试求出集合 A和关系 R的表达式。
解答
A={a,b,c,d,e,f,g,h}
R={ <b,d>,<b,e>,<b,f>,<c,d>,
<c,e>,<c,f>,<d,f>,<e,f>,
<g,h>}∪I A
偏序集中的特殊元素定义 7.24 设 <A,? >为偏序集,B?A,y∈B 。
1） 若?x(x∈B→ y? x)成立，则称 y为 B的 最小元 。
2）若?x(x∈B→x? y)成立，则称 y为 B的 最大元 。
3）若?x(x∈B∧x? y→x ＝ y)成立，则称 y为 B的 极小元 。
4）若?x(x∈B∧ y? x→x ＝ y)成立，则称 y为 B的 极大元 。
36
3
24
2
12
6
B 最大元 最小元 极大元 极小元
{2,3,6,12
,24,36}
{6,12}
{2,3,6}
{6}
无 无 24,26 2,3
12 6 12 6
6 无 6 2,3
6 6 6 6
特殊元素的性质
最小元是 B中最小的元素，它与 B中其它元素都可比。
极小元不一定与 B中元素可比，只要没有比它小的元素，
它就是极小元。
对于有穷集 B,极小元一定存在，但最小元不一定存在。
最小元如果存在，一定是唯一的。
极小元可能有多个，但不同的极小元之间是不可比的（无关系）。
如果 B中只有一个极小元，则它一定是 B的最小元。
哈斯图中，集合 B的极小元是 B中各元素中的最底层。
例 7.21
例 7.21 设偏序集 <A,?> 如右图所示，求 A的极小元、最小元、极大元、最大元。
解答极小元,a,b,c,g
极大元,a,f,h。
没有最小元与最大元说明 哈斯图中的孤立顶点既是极小元也是极大元。
例 7.22
例 7.22 设 X为集合,A＝ P(X)－ {?}－ {X},且 A≠?。
若 |X|＝ n,问：
（ 1）偏序集 <A,R?>是否存在最大元？
（ 2）偏序集 <A,R?>是否存在最小元？
（ 3）偏序集 <A,R?>中极大元和极小元的一般形式是什么？
并说明理由。
解答 <A,R?>不存在最小元和最大元，因为 n?2 。
考察幂集 P(X)的哈斯图，最底层的顶点是空集，记作第 0层
。由底向上，第 1层是单元集，第 2层是二元子集,… 由
|X|=n,则第 n－ 1层是 X的 n－ 1元子集，第 n层，也就是最高层只有一个顶点 X。 偏序集 <A,R?>与 <P(X),R?>相比，恰好缺少第 0层与第 n层 (因为 X是 n元集 )。因此 <A,R?>的极小元就是 X的所有单元集，即 {x},x∈X ； 而极大元恰好少一个元素，即 X-{x},x∈X 。
上界、下界定义 7.25 设 <A,?> 为偏序集,B?A,y∈A 。
（ 1） 若?x(x∈B→x? y)成立，则称 y为 B的 上界 。
（ 2）若?x(x∈B→ y?x) 成立，则称 y为 B的 下界 。
（ 3）令 C＝ {y|y为 B的上界 }，则称 C的最小元为 B的 最小上界或 上确界 。
（ 4）令 D＝ {y|y为 B的下界 }，则称 D的最大元为 B的 最大下界或 下确界 。
上界与下界举例
36
3
24
2
12
6
B 上界 下界 上确界 下确界
{2,3,6,12
,24,36}
{6,12}
{2,3,6}
{6}
无 无 无 无
12,24,36 2,3,6 12 6
6,12,24,36 无 6 无
6,12,24,36 2,3,6 6 6
考虑右图中的偏序集。令 B＝ {b
,c,d},则 B的下界和最大下界都不存在，上界有 d和 f,最小上界为 d。
上界与下界的性质
B的最小元一定是 B的下界，同时也是 B的最大下界。
B的最大元一定是 B的上界，同时也是 B的最小上界。
B的下界不一定是 B的最小元，因为它可能不是 B中的元素。
B的上界也不一定是 B的最大元。
B的上界、下界、最小上界、最大下界都可能不存在。如果存在，最小上界与最大下界是唯一的。
偏序关系的实例 —调 度问题给定有穷的任务集 T和 m台相同的机器,T上存在偏序关系?,
如果 t1<t2,那么任务 t1完成以后 t2才能开始工作 。
t∈T,
l(t)表示完成任务 t所需要的时间，
d(t)表示任务 t的截止时间，
l(t),d(t)∈Z +。
设开始时间为 0，
f:T→{0,1,…,D}表示任务集 T的一个调度方案，
其中 f(t)表示任务 t的开始时间。
D表示完成所有任务的最终时间。
偏序关系的实例 —调 度问题假设每项任务都可以安排在任何一台机器上进行工作，
如果 f满足下述三个条件，则称 T为 可行调度 。
(1)?t∈T,f(t)+l(t)?d(t)
（ 表示每项任务都要在截至时间内完成 ）
(2)?i,0?i?D,|{t∈T:f(t)?i ＜ f(t)+l(t)}|?m
（ 表示任何时刻同时工作的机器台数不超过 m）
(3)?t,t′∈ T,t＜ t′?f(t)+l(t)?f(t ′ )
（ 表示任务安排必须满足任务集的偏序约束 ）
求使得 D最小的可行调度。
例 7.23
设 m＝ 2,T＝ {t1,t2,…,t6},每项任务的截止时间都等于 7。去掉自反成分,T的偏序约束如右图所示。每个任务结点中的数字表示完成该任务所有的时间。
1
t6
1
t5
2
t4
1 2
1
t3 t2
t1
下图中给出了两个可行的调度方案。
t6 t4 t2 t1
t5 t3?
t4 t2 t1
t6 t5 t3?
D＝ 6
D＝ 5
本章主要内容
有序对与卡氏积
二元关系（包括空关系，恒等关系，全域关系等）及其表示
（关系矩阵，关系图）
关系的五种性质（自反性，反自反性，对称性，反对称性，
传递性）
二元关系的幂运算
关系的三种闭包（自反闭包，对称闭包，传递闭包）
等价关系和划分（包括等价类，商集，划分块等）
偏序关系（包括哈斯图，最大元，最小元，极大元，极小元
，上界，下界，最小上界，最大下界等）
本章学习要求
掌握：有序对及卡氏积的概念及卡氏积的性质
掌握：二元关系,A到 B的二元关系,A上的二元关系，关系的定义域和值域，关系的逆，关系的合成，关系在集合上的限制，集合在关系下的象等概念，掌握关系的定义域
、值域、逆、合成、限制、象等的主要性质
掌握：关系矩阵与关系图的概念及求法
掌握：集合 A上的二元关系的主要性质（自反性，反自反性，对称性，反对称性，传递性）的定义及判别法，对某些关系证明它们有或没有中的性质本章学习要求
掌握,A上二元关系的 n次幂的定义及主要性质
掌握 A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法
掌握：等价关系、等价类、商集、划分、等概念，以及等价关系与划分之间的对应
掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念作业习题七,
1,3,4,12,13,14,16,22,26、
31,32,39,42,46,48
关系性质的证明
通常的证明方法是利用定义证明。
R在 A上自反任取 x,有
x∈A? …………………………………?<x,x>∈R
R在 A上对称任取 <x,y>,有
<x,y>∈R? ……………………………?<y,x>∈R
R在 A上反对称任取 <x,y>,有
<x,y>∈R ∧ <x,y>∈R? ……………? x＝ y
R在 A上传递任取 <x,y>,<y,z>,有
<x,y>∈R ∧ <y,z>∈R? ……………? <x,z>∈R
有关关系性质的练习题
在正整数集合上定义关系 R：
<x,y>∈R,如果 x和 y的最大公因子是 1。
判断 R是否满足关系的五条性质？
设 A={a,b,c},试给出 A的一个二元关系 R,使其同时不满足五个性质。
N元素集合上有多少个自反的关系？
例题例题 在正整数集合上定义关系 R：
<x,y>∈R,如果 x和 y的最大公因子是 1。
判断 R是否满足关系的五条性质？
分析 按增序系统地列出所有的序对，然后观察。
<x,y> x＋ y 最大公因子 是否在 R中
<1,1> 2 1 是
<1,2> 3 1 是
<2,1> 3 1 是
<1,3> 4 1 是
<2,2> 4 2 否
<3,1> 4 1 是
…… … … …
例题解答 自反 否 <2,2>?R
反自反 否 <1,1>?R
对称 是 <x,y>∈R→<y,x>∈R
反对称 否 <1,2>∈R∧<2,1>∈R 但 1≠ 2
传递 否 <2,1>∈R∧<1,2>∈R 但 <2,2>?R
扩展 (1)从列出的若干序偶来考察是否属于关系。
(2)按一定规则列出序偶。
(3)一个范例即可证明不满足某种性质。
(4)证明某种性质成立，必须取出关系中的每个元素。
例题例题 设 A={a,b,c},试给出 A的一个二元关系 R,使其同时不满足五个性质。
分析 因为关系的各种性质的存在，都要求满足一定的条件
，要做的就是创造或破坏这些条件。
从 A× A出发，通过删除某些序偶，使其不满足那些性质。
解答 令 R＝ {<a,a>,<b,b>,<b,c>,<c,b>,<c,a>}
<c,c>?R 不满足自反性
<a,a>∈R 不满足反自反性
<c,a>∈R ∧ <a,c>?R 不满足对称性
<b,c>∈R∧<c,b>∈R∧b ≠ c 不满足反对称性
<b,c>∈R∧<c,a>∈R∧<b,a>?R 不满足传递性习题设 R＝ {<x,y>|x,y∈N 且 x+3y＝ 12}
(1)求 R的集合表达式
(2)求 dom R，
ran R
(3)求 R?R
(4)求 R↑{2,3,4,6}
(5)求 R[{3}]
(6)R3
解答：
{<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}
{0,3,6,9,12}，
{0,1,2,3,4}
{<3,3>,<12,4>}
{<3,3>,<6,2>}
{3}
{<3,3>}
习题
设 R是复数集合 C上的关系，且满足 xRy?x-y＝ a+bi,a和 b
为给定的非负整数，试确定 R的性质并证明之。
解答
（ 1）当 a＝ b＝ 0时，满足自反性、对称性、反对称性和传递性，不满足反自反性。
（ 2）当 a,b不全为 0时，只满足反自反性、反对称性。
习题例题 设 I为整数集,R＝ {<x,y>|x≡y(mod k)},证明 R是等价关系 。
证明 设任意 a,b,c∈I
(1)因为 a－ a＝ 0,所以 <a,a>∈R 。
(2)若 a≡b(mod k),a－ b＝ kt(t为整数 ),则
b－ a＝ -kt,所以 b≡a(mod k)。
(3)若 a≡b(mod k),b≡c(mod k),则
a－ b＝ kt,b－ c＝ ks(t和 s为整数 )，
a－ c＝ a－ b＋ b－ c＝ kt＋ ks＝ k(t＋ s)，
所以 a≡c(mod k)
因此,R是等价关系 。
