1
4.3 关系的性质
? 自反性
? 反自反性
? 对称性
? 反对称性
? 传递性
2
自反性与反自反性
定义 设 R为 A上的关系,
(1) 若 ?x(x∈ A→< x,x>?R),则称 R在 A上是 自反 的,
(2) 若 ?x(x∈ A→< x,x>?R),则称 R在 A上是 反自反 的,
实例,
反关系,A上的全域关系 EA,恒等关系 IA
小于等于关系 LA,整除关系 DA
反自反关系：实数集上的小于关系
幂集上的真包含关系
3
实例
例 1 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>}
R2自反,
R3反自反,
R1既不是自反也不是反自反的
4
对称性与反对称性
定义 设 R为 A上的关系,
(1) 若 ?x?y(x,y∈ A∧ <x,y>∈ R→< y,x>∈ R),则称 R
为 A上 对称 的关系,
(2) 若 x?y(x,y∈ A∧ <x,y>∈ R∧ <y,x>∈ R→ x=y),
则称 R为 A上的 反对称 关系,
实例,
对称关系,A上的全域关系 EA,恒等关系 IA和空
关系 ?
反对称关系：恒等关系 IA,空关系是 A上的反对
称关系,
5
实例
例 2 设 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 不对称、也不反对称,
6
传递性
定义 设 R为 A上的关系,若
?x?y?z(x,y,z∈ A∧ <x,y>∈ R∧ <y,z>∈ R→< x,z>∈ R),
则称 R是 A上的 传递 关系,
实例,
A上的全域关系 EA,恒等关系 IA和空关系 ?
小于等于关系,小于关系，整除关系，包含关系,
真包含关系
7
实例
例 3 设 A＝ {1,2,3},R1,R2,R3是 A上的关系,其中
R1＝ {<1,1>,<2,2>}
R2＝ {<1,2>,<2,3>}
R3＝ {<1,3>}
R1 和 R3 是 A上的传递关系
R2不是 A上的传递关系
8
关系性质的充要条件
设 R为 A上的关系,则
(1) R在 A上 自反 当且仅当 IA ?R
(2) R在 A上 反自反 当且仅当 R∩IA=?
(3) R在 A上 对称 当且仅当 R=R?1
(4) R在 A上 反对称 当且仅当 R∩R?1?IA
(5) R在 A上 传递 当且仅当 R?R?R
9
关系性质判别
自反 反自反 对称 反对称 传递
表达式 IA?R R∩IA=? R=R?1 R∩R?1? IA R?R?R
关系
矩阵
主对
角线
元素
全是 1
主对角
线元素
全是 0
矩阵是对称
矩阵
若 rij＝ 1,且
i≠j,则 rji＝
0
对 M2中 1
所在位置,
M中相应
位置都是 1
关系图 每个
顶点
都有
环
每个顶
点都没
有环
如果两个顶
点之间有边,
是一对方向
相反的边
(无单边 )
如果两点
之间有边,
是一条有
向边 (无双
向边 )
如果顶点
xi 连通到
xk,则从 xi
到 xk 有边
10
实例
例 8 判断下图中关系的性质,并说明理由,
(2)反自反，不是自反的；反对称，不是对称的；
是传递的,
(1)不自反也不反自反；对称,不反对称；不传递,
(3)自反，不反自反；反对称，不是对称；不传递,
11
自反性证明
证明模式 证明 R在 A上自反
任取 x,
x?A ? ……………..….……,? <x,x>?R
前提 推理过程 结论
例 4 证明若 IA ?R, 则 R在 A上自反,
证 任取 x,
x?A ? <x,x> ?IA ? <x,x>?R
因此 R 在 A 上是自反的,
12
对称性证明
证明模式 证明 R在 A上对称
任取 <x,y>
<x,y>?R ?……………..….……,? <y,x>?R
前提 推理过程 结论
例 5 证明若 R=R?1,则 R在 A上对称,
证 任取 <x,y>
<x,y>?R ? <y,x>?R ?1 ? <x,y>?R
因此 R 在 A 上是对称的,
13
反对称性证明
证明模式 证明 R在 A上反对称
任取 <x,y>
<x,y>?R?<y,x>?R ? ………..………,? x=y
前提 推理过程 结论
例 6 证明若 R∩R?1?IA,则 R在 A上反对称,
证 任取 <x,y>
<x,y>?R ?<y,x>?R ? <x,y>?R ?<x,y>?R ?1
? <x,y>?R∩R ?1 ? <x,y>?IA ? x=y
因此 R 在 A 上是反对称的,
14
传递性证明
证明模式 证明 R在 A上传递
任取 <x,y>,<y,z>
<x,y>?R?<y,z>?R ?…..………,? <x,z>?R
前提 推理过程 结论
例 7 证明若 R?R?R,则 R在 A上传递,
证 任取 <x,y>,<y,z>
<x,y>?R ?<y,z>?R ? <x,z>?R?R ? <x,z>?R
因此 R 在 A 上是传递的,
15
运算与性质的关系
自反性 反自反性 对称性 反对称性 传递性
R1?1 √ √ √ √ √
R1∩R2 √ √ √ √ √
R1∪ R2 √ √ √ × ×
R1?R2 × √ √ √ ×
R1°R2 √ × × × ×
16
4.4 关系的闭包
? 闭包定义
? 闭包的构造方法
? 集合表示
? 矩阵表示
? 图表示
? 闭包的性质
17
闭包定义
定义 设 R是非空集合 A上的关系,R的 自反（对
称 或 传递）闭包 是 A上的关系 R?,使得 R?满足以
下条件,
（ 1） R?是自反的（对称的或传递的）
（ 2） R?R?
（ 3）对 A上任何包含 R的自反（对称或传递）
关系 R?? 有 R??R??,
一般将 R 的自反闭包记作 r(R),对称闭包记作
s(R),传递闭包记作 t(R),
18
闭包的构造方法
定理 1 设 R为 A上的关系,则有
(1) r(R) = R∪ R0
(2) s(R) = R∪ R?1
(3) t(R) = R∪ R2∪ R3∪ …
说明,
? 对于有穷集合 A (|A|=n) 上的关系,(3)中的并最多
不超过 Rn,
? 若 R是自反的，则 r(R)=R; 若 R是对称的，则
s(R)=R; 若 R是传递的，则 t(R)=R,
19
闭包的构造方法（续）
设关系 R,r(R),s(R),t(R)的关系矩阵分别为 M,Mr,
Ms 和 Mt,则
Mr = M + E
Ms = M + M’
Mt = M + M2 + M3 + …
E 是和 M 同阶的单位矩阵,M’是 M 的转置矩阵,
注意在上述等式中矩阵的元素相加时使用逻辑加,
20
闭包的构造方法（续）
设关系 R,r(R),s(R),t(R)的关系图分别记为 G,Gr,Gs,
Gt,则 Gr,Gs,Gt 的顶点集与 G 的顶点集相等, 除了 G
的边以外,以下述方法添加新边,
考察 G的每个顶点,如果没有环就加上一个环，最
终得到 Gr, 考察 G的每条边,如果有一条 xi 到 xj 的单
向边,i≠j,则在 G中加一条 xj 到 xi 的反方向边，最终
得到 Gs,考察 G的每个顶点 xi,找从 xi 出发的每一条路
径，如果从 xi 到路径中任何结点 xj 没有边，就加上
这条边, 当检查完所有的顶点后就得到图 Gt,
21
实例
例 1 设 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(R)
s(R) t(R)