第四章 二元关系
二元关系是一个很重要的概念, 它在很多数学领域中
都有应用, 在计算机科学的如下理论都离不开关系,
逻辑设计, 数据结构, 编译原理, 软件工程
数据库理论, 计算理论, 算法分析, 操作系统 等
本章主要介绍：
关系的概念及表示方法
关系的性质
关系的运算,关系的复合,求逆关系,关系的闭包,
三种关系, 等价关系,相容关系,次序关系。
4-1 序偶与集合的笛卡尔积
实际上“序偶”概念以前已经用过。例如，用序
偶表示平面直角坐标系中一个点 (a,b)。设 x表示
上衣,y表示裤子,(x,y)可以表示一个人的着装。
一,序偶与有序 n元组
1.定义,由两个对象 x,y组成的序列称为有序二
元组，也称之为序偶，记作 <x,y>；称 x,y分
别为序偶 <x,y>的第一，第二元素。
注意，序偶 <x,y>与集合 {x,y}不同：
序偶 <x,y>：元素 x和 y有 次序；
集合 {x,y}：元素 x和 y的次序是无关紧要的。
2.定义,设 <x,y>,<u,v>是两个序偶，如果
x=u和 y=v，则称 <x,y>和 <u,v>相等，
记作 <x,y>=<u,v>.
3,定义,有序 3元组是一个序偶,其第一个元素也是个序偶。
有序 3元组 << a,b>,c>可以简记成 <a,b,c>。
但 <a,<b,c>>不是 有序 3元组。
4.定义,有序 n元组是一个序偶,其第一个元素本身是个有
序 n-1元组,记作 <<x1,x2,?,xn-1>,xn>。且可以简记成
<x1,x2,?,xn-1,xn>。
5,定义, <x1,x2,?,xn>=<y1,y2,·?,yn>
?( x1= y1)? ( x2= y2) ?? ?( xn= yn)
二,集合的 笛卡尔积
例如“斗兽棋”的 16颗棋子，
可看成是由两种颜色的集合 A和 8种动物的集合 B组成的。
A={红,蓝 }
B={象,狮,虎,豹,狼,狗,猫,鼠 }
每个棋子可以看成一个序偶，斗兽棋可记成集合 A?B,
{ <红,象 >,<红,狮 >,<红,虎 >,<红,豹 >,<红,狼 >,<红,狗 >,<红,猫 >,<红,鼠 >,
<蓝,象 >,<蓝,狮 >,<蓝,虎 >,<蓝,豹 >,<蓝,狼 >,<蓝,狗 >,<蓝,猫 >,<蓝,鼠 > }
虎象 狮 豹 狼 鼠猫狗
虎象 狮 豹 狼 鼠猫狗
1.定义,设 A,B是集合，由 A的元素为第一元素，
B的元素为第二元素组成序偶的集合，称为 A
和 B的笛卡尔积，记作 A× B，即
A?B={<x,y>|x?A∧ y?B}
例 1 设 A={0,1},B={a,b}，求 A?B, B?A，
A?A 。
解,A?B={<0,a>,<0,b>,<1,a>,<1,b>}
B?A={<a,0 >,<b,0>,<a,1>,<b,1>}
A?A={<0,0>,<0,1>,<1,0>,<1,1>}
可见 A× B≠B× A
所以，集合的笛卡尔积运算不满足交换律。
另外
(A?B)?C={<<a,b>,c>|<a,b>?A?B ?c?C}
A?(B?C)={<a,<b,c>>|a?A ?<b,c>?B?C},
因 <a,<b,c>>不是有序三元组,
所以 (A?B)?C?A?(B?C)。
故 ?也不满足结合律。
2.性质
1) 如果 A,B都是有限集，且 |A|=m,|B|=n，则
|A?B |=mn,
证明：由笛卡尔积的定义及排列组合中的乘法原
理，直接推得此定理。
2) A?Φ=Φ?B=Φ
3) ?对 ∪ 和 ∩满足分配律。
设 A,B,C是任意集合，则
⑴ A?(B∪ C)= (A?B)∪ (A?C)；
⑵ A?(B∩C)= (A?B)∩(A?C)；
⑶ (A∪ B)?C= (A?C)∪ (B?C)；
⑷ (A∩B)?C= (A?C)∩(B?C)
证明⑴,任取 <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) 所以⑴式成立。
其余可以类似证明。
4)若 C??,则
A?B?(A?C?B?C) ?(C?A?C?B).
证明, 必要性,设 A?B，求证 A?C?B?C
任取 <x,y>?A?C ?x?A?y?C
?x?B?y?C (因 A?B)
?<x,y>?B?C 所以,A?C?B?C,
充分性,若 C??,由 A?C?B?C 求 证 A?B
取 C中元素 y,任取 x?A?x?A?y?C
?<x,y>?A?C
?<x,y>?B?C (由 A?C?B?C )
?x?B?y?C?x?B 所以,A?B.
所以 A?B?(A?C?B?C)
类似可以证明 A?B ?(C?A?C?B).
5) 设 A,B,C,D为非空集合，则
A?B?C?D?A?C∧ B?D.
证明, 首先,由 A?B?C?D 证明 A?C∧ B?D.
任取 x?A，任取 y?B，所以
x?A?y?B
?<x,y>?A× B
?<x,y>?C× D (由 A?B?C?D )
?x?C?y?D 所以,A?C∧ B?D.
其次,由 A?C,B?D,证明 A?B?C?D
任取 <x,y>?A× B
<x,y>?A× B ? x?A?y?B
? x?C?y?D (由 A?C,B?D)
?<x,y>?C× D 所以,A?B?C?D 证毕,
6)约定
(…(A 1?A2)?… ?An-1)?An)=A1?A2?… ?An
特别 A?A?… ?A = An
设 R是实数集合，则 R2表示 笛卡尔坐标平面，
R3表示 三维空间,Rn表示 n维空间。
3.应用
1)令 A1={x|x是 学号 } A2={x|x是 姓名 } A3={男,女 }
A4={x|x是 出生日期 } A5={x|x是 班级 } A6 ={x|x是 籍贯 }
则 A1?A2?A3 ?A4?A5 ?A6中一个元素：
<001,王强，男,1981:02:16，计 2001-1，辽宁 >
这就是学生档案数据库的一条信息，所以学生
的档案就是 A1?A2?A3 ?A4?A5 ?A6的一个子集。
n 个
2) 令
A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,
w,x,y,z} 是英文字母表
一个 英文单词可以看成有序 n元组：如
at=<a,t>,boy=<b,o,y>,data=<d,a,t,a>,
computer=<c,o,m,p,u,t,e,r>
于是可以说：
at?A2,boy?A3,data?A4,computer?A8,…
于是英文词典中的 单词集合 可以看成是
A∪ A2∪ … ∪ An 的一个子集。
作业 第 105页 ⑵
4-2 关系及其表示法
关系是一个非常普遍的概念，如数值的大于关
系、整除关系，人类的父子关系、师生关系、同
学关系等。下面讨论如何从中抽象出关系的定义
和如何表示关系。
一,例子
1,大写英字母与五单位代码的对应关系 R1:
令 α={A,B,C,D,…Z}
β={30,23,16,22,…,21} 是 五单位代码集合
β={11000,10011,01110,10010,…,10001}
R1={<A,30>,<B,23>,<C,16>,...,<Z,21>}?α× β
2.令Ａ ={1,2,3,4},A中元素间的 ≤关系 R2,
R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,
<2,4>,<3,3>,<3,4>,<4,4>}?A× A
二, 基本概念
1.关系的定义
定义 1:设 A、Ｂ是集合，如果Ｒ ?A× B，则称 R是
一个 从 A到 B的二元关系。如果 R?A× A，则
称 R是 A上 的二元 关系。 二元 关系简称为关系。
定义 2:任何序偶的集合，都称之为一个二元关系。
如,R={<1,a>,<书,车 >,<人,树 >}
<x,y>?R ?xRy 也称之为 x与 y有Ｒ关系。
后缀表示 中缀表示
<x,y>?R ?xRy 也称之为 x与 y没有Ｒ关系。
例 3,R是实数集合,R上的几个熟知的关系：
从例 3中可以看出 关系是序偶 (点 )的集合 (构
成线、面 )。
x2+y2=4≤
≥
=
x
y
2.关系的定义域与值域
定义域 (domain), 设 R?A× B，由所有 <x,y>?R
的第一个元素组成的集合，称为 R的定义域，
记作 dom R，即
dom R={x|?y(<x,y>?R)}
值域 (range), 设 R?A× B，由所有 <x,y>?R的第
二个元素组成的集合，称为 R的值域，
记作 ran R，即
ran R={y|?x(<x,y>?R)}
上述 R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,
<2,4>,<3,3>,<3,4>,<4,4>}
dom R2 ={1,2,3,4}
ran R2 ={1,2,3,4}
三, 关系的表示方法
1,枚举法,
即将关系中所有序偶一一列举出，写在大括号
内。如前的 R2 ={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,
<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} 。
2.谓词公式法,
即用谓词公式表示序偶的第一元素与第二元素
间的关系。例如
R={<x,y>|x<y}
3.有向图法,
R?A× B,用两组小圆圈 (称为 结点 )分别表示 A
和 B的元素，当 <x,y>?R时，从 x到 y引一条有
向弧 (边 )。这样得到的图形称为 R的关系图。
如 R?A× A,即 R是集合 A中关系时,可能有
<x,x>?R,则从 x到 x画一条有向环 (自回路 )。
例 设 A={1,2,3,4},B={a,b,c},R3 ?A× B，
R3={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}
则 R3的关系图如下：
例 设 A={1,2,3,4},R4 ?A× A，
R4={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}
则 R4的关系图如右上图。
1。
2。
3。
4。
。
。
。
A B
a
b
c
1。 。
4。 。
2
3
R4,R3,
4.矩阵表示法,
有限集合之间的关系也可以用矩阵来表示，这种表示
法便于用计算机来处理关系。
设 A={a1,a2,?,am},B={b1,b2,?,bn}是个有限集，
R?A× B，定义 R的 m× n阶 矩阵
MR=(rij)m× n，其中
rij=
R3={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}
R4={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}
上例中 MR = MR4=
1 若 <ai,bj>∈ R
0 若 <ai,bj>∈ R (1≤i≤m,1≤j≤n)
3
1 0 1
0 1 0
1 0 0
0 0 1 4× 3
1
2
3
4
a b c
1 0 0 1
0 0 1 0
1 1 0 0
1 0 0 1
4× 4
1
2
3
4
1 2 3 4
四,三个特殊关系
1.空关系 Φ：
因为 Φ?A× B,(或 Φ?A× A)，所以 Φ也
是一个从 A到 B(或 A上 )的关系，称之为 空
关系 。即无任何元素的关系，它的关系图
中只有结点,无任何边；它的矩阵中全是 0。
2.完全关系 (全域关系 )：
A× B(或 A× A)本身也是一个从 A到 B(或
A上 ) 的关系，称之为完全关系。即含有全
部序偶的关系。它的矩阵中全是 1。
3,A上的 恒等关系 IA：
IA?A× A，且 IA ={<x,x>|x∈ A}称之为 A
上的恒等关系。
例如 A={1,2,3},则 IA ={<1,1>,<2,2>,<3,3>}
A上的 Φ、完全关系及 IA的关系图及矩阵如
下：
MIA =
1 0 0
0 1 0
0 0 1 3× 3
1。
2。 。 3
1。
2。 。 3
1 1 1
1 1 1
1 1 1 3× 3
1。
。2。 3
0 0 0
0 0 0
0 0 0 3× 3
MΦ= MA× A=
Φ A× A IA
五, 关系的集合运算
由于关系就是集合，所以集合的 ∩,∪,
-,?和 ~运算对关系也适用。
例如,A是学生集合,R是 A上的同乡关系，
S是 A上的同姓关系，则
R∪ S：或同乡或同姓关系
R∩S：既同乡又同姓关系
R-S,同乡而不同姓关系
R?S：同乡而不同姓,或同姓而不同乡关系
~R：不是同乡关系,这里 ~R=(A× A)-R
作业 第 109页 ⑵、⑸ c)d)
4-3 关系的性质
本节将研究关系的一些性质, 它们在关系的研究
中起着重要的作用 。 这是本章最重要的一节 。
本节中所讨论的关系都是集合 A中的关系 。
关系的性质主要有：自反性, 反自反性, 对称
性, 反对称性和传递性 。
一,自反性
定义,设 R是集合 A中的关系, 如果对于任意 x∈ A都
有 <x,x>∈ R (xRx),则称 R是 A中自反关系 。 即
R是 A中自反的 ??x(x?A?xRx)
例如在实数集合中,“?”是自反关系, 因为, 对任
意实数 x,有 x ? x.
从关系有向图看自反性,每个结点都有环。
从关系矩阵看自反性：主对角线都为 1。
令 A={1,2,3}给定 A上八个关系如下：
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
可见这八个关系中 R1,R3,R4是自反的。
二,反自反性
定义, 设 R是集合 A中的关系，如果对于任
意的 x∈ A都有 <x,x>?R,则称 R为 A中的反
自反关系。即
R是 A中反自反的 ??x(x?A?<x,x>?R)
从关系有向图看反自反性,每个结点都无环。
从关系矩阵看反自反性：主对角线都为 0。
如实数的大于关系 >，父子关系是反自反的。
注意,一个不是自反的关系，不一定就是反
自反的，如前边 R6,R7非自反,也非反自反。
下面 R2,R5,R8、均是反自反关系 。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
三,对称性
定义,R是集合 A中关系,若对任何 x,y∈ A,如
果有 xRy,必有 yRx,则称 R为 A中的对称关系。
R是 A上对称的
??x?y((x?A?y?A?xRy) ?yRx)
从关系有向图看对称性,在两个不同的结点
之间，若有边的话，则有方向相反的两条边。
从关系矩阵看对称性：以主对角线为对称
的矩阵。
邻居关系是对称关系，朋友关系是对称关系。
下边 R3,R4,R6, R8均是对称关系。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
四,反对称性
定义,设 R为集合 A中关系,若对任何 x,y∈ A,如果有
xRy,和 yRx,就 有 x=y,则称 R为 A中反对称关系 。
R是 A上反对称的
??x?y((x?A?y?A?xRy?yRx) ?x=y)
??x?y((x?A?y?A?x?y?xRy)?y x) (P112)
由 R的关系图看反对称性,两个不同的结点之间
最多有一条边。
从关系矩阵看反对称性,以主对角线为对称的
两个元素中最多有一个 1。
另外对称与反对称不是完全对立的,有些关系
它既是对称也是反对称的,如空关系和恒等关系。
R
下边 R1,R2,R4,R5,R8均是反对称关系。
R4,R8既是对称也是反对称的。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
五, 传递性
定义,R是 A中关系，对任何 x,y,z∈ A,如果有 xRy,和 yRz,就
有 xRz,则称 R为 A中传递关系。
即 R在 A上传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
实数集中的 ≤、＜，集合 ?,?是传递的。
从关系关系图和关系矩阵中不易看清是否有传递性。有
时，必须直接根据传递的定义来检查。
检查时要特别注意使得传递定义表达式的前件为 F的时候
此表达式为 T，即是传递的。
即若 <x,y>∈ R与 <y,z>∈ R有一个是 F时 (即定义的前件为
假 ),R是传递的。
例如 A={1,2},下面 A中关系 R是传递的,
通过带量词的公式在论域展开式说明
R在 A上传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
??x?y?z((xRy?yRz)?xRz) (为了简单做些删改 )
??y?z((1Ry?yRz)?1Rz)??y?z((2Ry?yRz)?2Rz)
?(?z((1R1?1Rz)?1Rz)??z((1R2?2Rz)?1Rz)
?(?z((2R1?1Rz)?2Rz) ?(?z((2R2?2Rz)?2Rz))
?(((1R1?1R1)?1R1)?((1R1?1R2)?1R2)) ?
(((1R2?2R1)?1R1)?((1R2?2R2)?1R2)) ?
(((2R1?1R1)?2R1)?((2R1?1R2)?2R2)) ?
(((2R2?2R1)?2R1)) ? ((2R2?2R2)?2R2))
? (((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))?
(((F?F)?F)?((F?T)?F))?(((F?F)?F))?((F?F)?F))?T
1? ?2
下边 R1,R3,R4,R5,R8均是传递的关系 。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
本节要求,
1.准确掌握这五个性质的定义。
2.熟练掌握五个性质的判断和证明。
R是 A中 自反 的 ??x(x?A?xRx)
R是 A中 反自反 的 ??x(x?A?<x,x>?R)
R是 A上 对称 的 ??x?y((x?A?y?A?xRy) ?yRx)
R是 A上 反对称 的
??x?y((x?A?y?A?xRy?yRx)?x=y)
??x?y((x?A?y?A?x?y?xRy)?y x)
R在 A上 传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
上述定义表达式都是 蕴涵式,所以判断关系 R性质时要特
别注意使得性质定义表达式的前件为 F的时候此表达式
为 T，即 R是满足此性质的。 (自反和反自反性除外 )
R
自反性
反自反性
对称性
传递性
反对称性
每个结点都有环 主对角线全是 1
每个结点都无环 主对角线全是 0
不同结点间如果有边,
则有方向相反的两条
边,
是以对角线为对称
的矩阵
不同结点间,最多有一
条边,
以主对角线为对称
的位置不会同时为 1
如果有边 <a,b>,<b,c>,
则也有边 <a,c>,
或者定义的前件为假,
如果 aij=1,且 ajk=1,
则 aik=1
从 关 系的矩 阵从 关 系的有向 图性 质 判定,
下面归纳这八个关系的性质,Y-有 N-无
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
自反性 反自反性 对称性 反对称性 传递性
R1 Y N N Y Y
R2 N Y N Y N
R3 Y N Y N Y
R4 Y N Y Y Y
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R5 R6 R7 R8
自反性 反自反性 对称性 反对称性 传递性
R5 N Y N Y Y
R6 N N Y N N
R7 N N N N N
R8 N Y Y Y Y
练习 1:令 I是整数集合,I上关系 R定义为：
R={<x,y>|x-y可被 3整除 }，求证 R是自反、对称和传递的。
证明, ⑴证自反性,任取 x∈ I,(要证出 <x,x>?R )
因 x-x=0,0可被 3整除,所以有 <x,x>∈ R,故 R自反。
⑵证对称性,任取 x,y∈ I,设 <x,y>∈ R,(要证出 <y,x>?R )
由 R定义得 x-y可被 3整除,即 x-y=3n(n∈ I)，
y-x=-(x-y)=-3n=3(-n),因 -n∈ I,∴ <y,x>∈ R,
所以 R对称。
⑶ 证传递性,任取 x,y,z∈ I,设 xRy,yRz,(要证出 xRz)
由 R定义得 x-y=3m,y-z=3n (m.n∈ I)
x-z= (x-y)+(y-z)=3m+3n=3(m+n),因 m+n∈ I,
所以 xRz,所以 R传递。 证毕
练习 2,设 R是集合 A上的一个自反关系,求证：
R是对称和传递的，当且仅当
<a,b>和 <a,c>在 R中,则有 <b,c>也在 R中。
证明, 必要性, 已知 R是对称和传递的。
设 <a,b>?R 又 <a,c>?R,(要证出 <b,c>?R )
因 R对称的故 <b,a>?R,又已知 <a,c>?R 由传递性
得 <b,c>?R。所以有如果 <a,b>和 <a,c>在 R中,则有
<b,c>也在 R中。
充分性, 已知任意 a,b,c?A,如 <a,b>和 <a,c>在 R
中,则有 <b,c>也在 R中。
先证 R对称,任取 a,b?A 设 <a,b>?R,(要证出
<b,a>?R ) 因 R是自反的,所以 <a,a>?R，由
<a,b>?R且 <a,a>?R，根据已知条件得 <b,a>?R,
所以 R是对称的。
再证 R传递,任取 a,b,c?A 设 <a,b>?R，
<b,c>?R。 (要证出 <a,c>?R )
由 R是对称的,得 <b,a>?R,由
<b,a>?R且 <b,c>?R，根据已知条件得
<a,c>?R, 所以 R是传递的。
作业 第 113页
⑴、⑶、⑷
4-4 关系的复合
二元关系除了可进行集合并、交、补等运算外，
还可以进行一些新的运算，先介绍由两个关系生
成一种新的关系，即关系的复合运算。
例如，有 3个人 a,b,c,A={a,b,c}，
R是 A上 兄妹 关系，
S是 A上 母子 关系，
<a,b>∈ R∧ <b,c>∈ S
即 a是 b的哥哥,b是 a的妹妹 ;
b是 c的母亲,c是 b的儿子。
则 a和 c间就是 舅舅和外甥 的关系,记作 R?S,
称它是 R和 S的复合关系 。
SR?
a b cR S
1.定义,设是 R从 X到 Y的关系,S是从 Y到 Z的关
系，则 R和 S的复合关系记作 R?S 。定义为：
R?S ={<x,z>|x?X?z?Z??y(y?Y
?<x,y>?R?<y,z>?S)}
显然,R?S 是从 X到 Z的关系。
2.复合关系的计算方法 (俗称过河拆桥法 )
A={1,2,3} B={1,2,3.4} C={1,2,3,4,5}
R?A× B S?B× C
⑴ 枚举法
R={<1,2>,<2,3>,<2,4>,<3,1>}
S={<1,2>,<2,1>,<2,3>,<3,4>,<4,2>,<4,5>} 则
R?S={<1,1>,<1,3>,<2,4>,<2,2>,<2,5>,<3,2>}
⑵有向图法
⑶关系矩阵法
令 A={a1,a2,…,a m} B={b1,b2,…,b n}
C={c1,c2,…,c t} R?A× B S?B× C
。
。
。
。
C
1
2
3
。 4
1。
2。
3。
A
1。
2。
3。
A
。
。
。
B
1
2
3
。 4
R S
5。
。
。
。
C
1
2
3
。 4
5
SR?
c11=(a11∧ b11)∨ (a12∧ b21)∨,..∨ (a1n∧ bn1)
= (a1k∧ bk1) (其中 ∧ 是逻辑乘,∨ 是逻辑加 )
cij=(ai1∧ b1j)∨ (ai2∧ b2j)∨,..∨ (ain∧ bnj)
= (aik∧ bkj) (1≤i≤m,1≤j≤t)
MS MR
<a1,b1><a1,b2>...<al,bn>
<a2,b1><a2,b2>...<a2,bn>...,..
<am,b1><am,b2>...<am,bn>
(aij)
<b1,c1><b1,c2>...<bl,ct>
<b2,c1><b2,c2>...<b2,ct>...,..
<bn,c1><bn,c2>...<bn,ct>
(bij)
<a1,c1>...<al,ct>
<a2,c1>...<a2,ct>...,..
<am,c1>...<am,ct>
M
SR?
(cij)
0 1 0 0
0 0 1 1
1 0 0 0 3× 4
。 1 0 0 0 01 0 1 0 0
0 0 0 1 0
0 1 0 0 1
=
4× 5
1 0 1 0 0
0 1 0 1 1
1 0 0 0 0 3 × 5
k=1
n∨
k=1
n∨
⑷ 谓词公式法
设 I是实数集合,R和 S都是 I上的关系，定义如下：
R={<x,y>| y=x2+3x}
S={<x,y>| y=2x+3}
所以 R?S ={<x,y>| y=2x2+6x+3}
三,性质
关系复合运算不满足交换律，但是
1.满足结合律, R?A× B S?B× C T?C× D 则
TS)(RT)S(R ???? ?
x x2+3x 2(x2+3x)+3 = 2x2+6x+3R S
证明：任取 <a,d>∈ R (S T)
??b(b∈ B∧ <a,b>∈ R∧ <b,d>∈ S T)
??b(b∈ B∧ <a,b>∈ R∧ ?c(c∈ C∧ <b,c>∈ S∧ <c,d>∈ T))
??b?c(b∈ B∧ <a,b>∈ R∧ (c∈ C∧ <b,c>∈ S∧ <c,d>∈ T))
??c?b(c∈ C∧ (b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∧ <c,d>∈ T))
??c (c∈ C∧ ?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∧ <c,d>∈ T)
??c (c∈ C∧ <a,c>∈ R S)∧ <c,d>∈ T)
?<a,d>∈ (R S) T
TS)(RT)S(R ???? ?
A B
C D
R
T
所以
可以用下图形象表示,
2,R?A× B S?B× C T?B× C
⑴ R (S∪ T)=(R S)∪ (R T)
⑵ R (S∩T)?(R S)∩(R T)
证明 ⑴ 任取 <a,c>∈ R (S∪ T)
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∪ T)
??b(b∈ B∧ <a,b>∈ R∧ (<b,c>∈ S∨ <b,c>∈ T))
??b((b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T))
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T)
?<a,c>∈ R S∨ <a,c>∈ R T
?<a,c>∈ (R S)∪ (R T)
所以 R (S∪ T)=(R S)∪ (R T)
证明⑵ 任取 <a,c>∈ R (S∩T)
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∩T)
??b(b∈ B∧ <a,b>∈ R∧ (<b,c>∈ S∧ <b,c>∈ T))
??b((b∈ B∧ <a,b>∈ R∧ <b,c>∈ S) ∧
(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T))
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T)
?<a,c>∈ R S ∧ <a,c>∈ R T
?<a,c>∈ (R S)∩(R T)
所以 R (S∩T)?(R S)∩(R T)
?x(A(x)∧ B(x)) ??xA(x)∧ ?xB(x)
3,R是从 A到 B的关系，则
R IB=IA R=R
此式的证明很容易，从略。下面列举一例
来验证。
令 A={1,2,3},B={a,b,c,d}
从这两个图看出它们的复合都等于 R。
1。
2。
3。
AIA
。
。
。
B
a
b
c
。 d
R
1。
2。
3。
AR
IB
。
。
。
a
b
c
。 d
。
。
。
B
a
b
c
。 d
1。
2。
3。
A B
4,关系的乘幂
令 R是 A上关系，由于复合运算可结合，所以
关系的复合可以写成乘幂形式。即
R R=R2,R2 R=R R2 =R3,…
一般地
R0 =IA，
Rm Rn = Rm+n
(Rm)n =Rmn (m,n为非负整数 )
例如 R是 A上关系，如上图所示,可见
<a,c>?R2,表明在 R图上有从 a到 c有两条边的路径,
a b c;<a,d>?R3,表明在 R图上有从 a到 d有三条
边的路径,a b c d。,..如果 <x,y>?Rk,表明在
R图上有从 x到 y有 k条边 (长为 k)的路径 。 (x,y?A)
a
d
b
c
R:
4-5 逆关系
逆关系 (反关系 )也是我们经常遇到的概念，例
如 ≤与 ≥就是互为逆关系。
一,定义
R是从 A到 B的关系，如果将 R中的所有序偶的
两个元素的位置互换，得到一个从 B到 A的关系，
称之为 R的逆关系，记作 RC，或 R-1。
RC={<y,x>|<x,y>?R}
<y,x>∈ RC ?<x,y>?R
二, 计算方法
1,R={<1,2>,<2,3>,<3,4>,<4,5>}
RC ={<2,1>,<3,2>,<4,3>,<5,4>}
2,RC的有向图：是将 R的有向图的所有边的方向
颠倒一下即可。
3,RC的矩阵 M =(MR)T 即为 R矩阵的转置。如
三,性质
令 R,S都是从 X到 Y的关系，则
1,(RC)C = R
2,(R∪ S)C = RC∪ SC 。
3,(R∩S)C = RC∩SC 。
4,(R－ S)C = RC－ SC 。
RC
1 0 11 0 1 00 0 0 1
1 0 1 1
MR=
3× 4
0 0 0
1 0 1
0 1 1
MR =c
4× 3
证明 1.：任取 <y,x>?(R∪ S)C，则
<y,x>?(R∪ S)C ? <x,y>?R∪ S
? <x,y>?R∨ <x,y>?S
? <y,x>?RC∨ <y,x>?SC
?<y,x>? RC∪ SC
所以 (R∪ S)C = RC∪ SC,其它类似可证。
5,R?S ? RC?SC 。
证明, 充分性,已知 RC? SC,则任取 <x,y>∈ R
?<y,x>?RC? <y,x>?SC ? <x,y>?S ∴ R?S
必要性,已知 R? S，则任取 <y,x>∈ RC
? <x,y>?R?<x,y>?S ?<y,x>?SC ∴ RC?SC
6.(~R)C=~RC
证明,任取 <y,x>∈ (~R)C ?<x,y>∈ ~R?<x,y>?R
?<y,x>?RC ?<y,x>∈ ~RC ∴,(~R)C=~RC
7.令 R是从 X到 Y的关系,S是 Y到 Z的关系，则
(R S)C= SC RC 。 (注意 ≠RC SC )
证明, 任取 <z,x>∈ (R S)C
?<x,z>?R S
??y(y∈ Y∧ <x,y>∈ R∧ <y,z>∈ S)
??y(y∈ Y∧ <z,y>∈ SC∧ <y,x>∈ RC)
?<z,x>?SC RC 所以 (R S)C= SC RC
8,R是 A上关系，则
⑴ R是对称的，当且仅当 RC =R
⑵ R是反对称的，当且仅当 R∩RC ?IA。
证明,⑴ 充分性，已知 RC =R (证出 R对称 )
任取 x,y?A 设 <x,y>?R,则 <y,x>?RC,而 RC =R
所以有 <y,x>?R,所以 R对称。
必要性，已知 R 对称,(证出 RC =R)
先证 RC?R,任取 <y,x>∈ RC,则 <x,y>?R,因 R对称
所以有 <y,x>∈ R，所以 RC?R。
再证 R? RC,任取 <x,y>?R,因 R对称，所以有
<y,x>∈ R，则 <x,y>∈ RC,所以 R?RC。
最后得 RC =R 。
证明⑵ 充分性，已知 R∩RC ?IA,(证出 R反对称 )
任取 x,y?A 设 <x,y>?R 且 <y,x>∈ R，
<x,y>?R∧ <y,x>∈ R?<x,y>?R∧ <x,y>∈ RC，
? <x,y>?R∩RC ? <x,y>? IA (因 R∩RC ?IA )
?x=y 所以 R反对称。
必要性，已知 R反 对称,(证出 R∩RC ?IA)
任取 <x,y>?R∩RC
<x,y>?R∩RC?<x,y>?R∧ <x,y>?RC
?<x,y>?R∧ <y,x>?R
?x=y (因 R反对称 )
?<x,y>?IA 所以 R∩RC ?IA 。
第 4-3和 4-4节的 要求,
熟练掌握求复合关系和逆关系的计算方法
及性质。
作业,第 118页⑴、⑵ a)b)、⑶、⑸
4-6 关系的闭包运算
关系的闭包是个很有用的概念，特别是传递闭
包。关系的闭包是通过关系的复合和求逆构成的
一个新的关系。这里要介绍关系的自反闭包、对
称闭包和传递闭包。
一,例子
给定 A中关系 R，如图所示，
分别求 A上另一个关系 R’，使
得它是包含 R的“最小的” (序偶
尽量少 )分别具有自反 (对称、传递 )性的关系。 这
个 R’就分别是 R的 自反 (对称、传递 )闭包。
1。
2。 。 3
这三个关系图分别是 R的 自反、对称、传递闭包。
二,定义,给定 A中关系 R,若 A上另一个关系 R’，
满足：⑴ R?R’；
⑵ R’是自反的 (对称的、传递的 )；
⑶ R’是,最小的,，即对于任何 A上自反 (对称、
传递 )的关系 R”,如果 R?R”,就有 R’?R”。
则称 R’是 R的 自反 (对称、传递 )闭包。记作 r(R)、
(s(R), t(R)) (reflexive,symmetric,transitive)
1。
2。 。 3
1。
2。 。 3
1。
2。 。 3
实际上 r(R),(s(R), t(R)) 就是包含 R的“最小”
的 自反 (对称、传递 )关系。
三,计算方法
定理 1.给定 A中关系 R,则 r(R)=R∪ IA。
证明：令 R’=R∪ IA,显然 R’是自反的和 R?R’，下
面证明 R’是“最小的”：如果有 A上自反关系
R”且 R?R”,又 IA?R”,所以 R∪ IA?R”,即 R’?R”。
所以 R’就是 R的自反闭包。即 r(R)=R∪ IA 。
定理 2.给定 A中关系 R,则 s(R)=R∪ RC 。
证明方法与 1.类似。
定理 3.给定 A中关系 R,则 t(R)=R∪ R2∪ R3∪,.,。
证明：令 R’= R∪ R2∪ R3∪,..,
⑴ 显然有 R?R’ ；
⑵证 R’是传递的：任取 x,y,z?A,设有 <x,y>?R’
<y,z>?R’,由 R’定义得必存在整数 i,j使得
<x,y>?Ri,<y,z>?Rj,根据关系的复合得
<x,z>?Ri+j,又因 Ri+j ?R’,所以 <x,z>?R’,∴ R’传递 。
⑶ 证 R’是“最小的”：如果有 A上传递关系 R”且
R?R”,（ 证出 R’?R”）任取 <x,y>?R’,则由 R’定义
得必存在整数 i,使得 <x,y>?Ri,根据关系的复合得
A中必存在 i-1个元素 e1,e2,...,ei-1,使得 (见 49页 )
<x,e1>?R∧ <e1,e2>?R∧,..∧ <ei-1,y>?R。因 R?R”,
∴ 有 <x,e1>?R”∧ <e1,e2>?R”∧,..∧ <ei-1,y>?R”。
由于 R”传递，所以有 <x,y>?R”。 ∴ R’?R”。
综上所述,R’就是 R的传递闭包，即
t(R)=R∪ R2∪ R3∪ …= ∪ Rii=1∞
用上述 公式计算 t(R),要计算 R的无穷大次幂,好
象无法实现似的。其实则不然，请看下例,
A={1,2,3} A中关系 R1,R2,R3,如下：
R1={<1,2>,<1.3>,<3,2>}
R2 ={<1,2>,<2.3>,<3,1>}
R3 ={<1,2>,<2.3>,<3,3>}
={<1,2>} = =Φ 所以
t(R1)= ∪ ∪ = R1
={<1,3>,<2,1>,<3,2>} ={<1,1>,<2,2>,<3,3>}
=IA,= R2,..
t(R2)= R2∪ ∪
={<1,3>,<2,3>,<3,3>} =
t(R3)= R2∪
2R
1
3R
1
4R
1
1R
1
2R
1
3R
1
2R
2
3R
2
4R
2
3R
2
2R
2
3R
2
3R
3
2R
3
2R
3
2R
3
定理 4.给定 A中关系 R,如果 A是有限集合,|A|=n
则 t(R)=R∪ R2∪,..∪ Rn 。
证明：令 R’=R∪ R2∪ R3∪,..,R”=R∪ R2∪,..∪ Rn
下面证明 R’=R”,
显然有 R”?R’。下面证明 R’?R”：
任取 <x,y>?R’,由 R’定义得必存在 最小的 正整数 i 使
得 <x,y>?Ri,(下面证明 i≤n)如果 i＞ n,
根据关系的复合得 A中必存在 i-1个元素 e1,e2,...,ei-1，
使得 <x,e1>?R∧ <e1,e2>?R∧,..∧ <ei-1,y>?R。
上述元素序列, x=e0,e1,e2,...,ei-1,y=ei中共有 i+1个元
素,i+1>n,而 A 中只有 n个元素，所以上述元素中
至少有两个相同，设 ej=ek (j<k),于是 R的关系图中
会有下面这些边：
从此图中删去回路中 k-j(k-j≥1)条边后得
<x,y>∈ Ri-(k-j),i-(k-j)<i,与 i是 最小的 矛盾。
所以 i≤n,所以 <x,y>∈ R”,于是 R’?R”。
最后得 R’=R”，所以
t(R)=R∪ R2∪,..∪ Rn 定理证毕。
。
。 。 。 。 。 。 。x e
1 ej-1 ej =ek
ej+1。
。
。
。
。
ej+2
ek-1
ek-2
ek+1 ek+2…..,…..,ei-1 y
求 t(R)的矩阵 Warshall算法,|X|=n,R?X× X,
令 MR=A R2的矩阵为 A2,… R k的矩阵为 Ak,于是
t(R)的 矩阵记作 MR+=A+A2+…+A k +… (+是逻辑加 )
⑴ 置新矩阵 A,=MR ;
⑵ 置 i=1;
⑶ 对所有 j,如果 A[j,i] =1,则对 k=1,2,…,n
A[j,k]:=A[j,k]+A[i,k]; /*第 j行 +第 i行,送回第 j行 */
⑷ i加 1;
⑸ 如果 i≤n,则转到步骤 ⑶，否则停止。
下面举例，令 X={1,2,3,4},
X中关系 R图如右图所示。
运行该算法 求 t(R)的矩阵,
1。
2。
。
。
4
3
i=1 (i---列,j---行 )
A[4,1]=1
1行 +4行 →4 行
i=2 A[1,2]=1,1行 +2行 →1 行
A[2,2]=1,2行 +2行 →2 行 A不变
A[4,2]=1,4行 +2行 →4 行,4行全 1,A不变
i=3 A[1,3]=1,1行 +3行 →1 行,3行全 0,A不变
A[2,3]=1,2行 +3行 →2 行,3行全 0,A不变
A[4,3]=1,4行 +3行 →4 行,3行全 0,A不变
i=4 A[1,4]=1,1行 +4行 →1 行
A[4,4]=1,4行 +4行 →4 行 A不变,
最后 A=Mt(R)
?
?
?
?
?
?
?
?
?
?
?
?
1101
0000
0110
1010
A=MR= A=
?
?
?
?
?
?
?
?
?
?
?
?
1111
0000
0110
1010
A的初值,
A=
?
?
?
?
?
?
?
?
?
?
?
?
1111
0000
0110
1110
A=
?
?
?
?
?
?
?
?
?
?
?
?
1111
0000
0110
1111
四,性质
定理 5,R是 A上关系，则
⑴ R是自反的，当且仅当 r(R)=R.
⑵ R是对称的，当且仅当 s(R)=R.
⑶ R是传递的，当且仅当 t(R)=R.
证明略，因为由闭包定义即可得。
定理 6,R是 A上关系，则
⑴ R是自反的，则 s(R)和 t(R)也自反。
⑵ R是对称的，则 r(R)和 t(R)也对称。
⑶ R是传递的，则 r(R)也传递。
证明, ⑴ 因为 R自反,由定理 5得 r(R)=R,即
R∪ IA=R,r(s(R))=s(R)∪ IA=(R∪ RC)∪ IA
= (R∪ IA)∪ RC=r(R)∪ RC =R∪ RC =s(R)∴ s(R)自反
类似可以证明 t(R)也自反。
证明 ⑵, 证明 t(R)对称,
(t(R))C=(R∪ R2∪,..∪ Rn∪,..)C
= RC∪ (R2)C ∪,..∪ (Rn)C∪,..
= RC∪ (RC)2 ∪,..∪ (RC)n∪,.,
=R∪ R2∪,..∪ Rn∪,.,(∵ R对称,∴ RC =R)
=t(R) 所以 t(R)也对称。
类似可以证明 r(R)也对称。
证明 ⑶, 证明 r(R)传递,先用归纳法证明下面结论,
(R∪ IA)i= IA∪ R∪ R2∪,..∪ Ri
① i=1时 R∪ IA= IA∪ R 结论成立。
②假设 i≤k 时结论成立，即
(R∪ IA)k= IA∪ R∪ R2∪,..∪ Rk
(R2)c=(R R)c
=Rc Rc
=(Rc)2
③ 当 i=k+1时
(R∪ IA)k+1=(R∪ IA)k (R∪ IA)
= (IA∪ R∪ R2∪,..∪ Rk） (IA∪ R)
= (IA∪ R∪ R2∪,..∪ Rk)∪ (R∪ R2∪,..∪ Rk+1)
= IA∪ R∪ R2∪,..∪ Rk∪ Rk+1
所以结论成立,
t(r(R))=t(R∪ IA)
= (R∪ IA)∪ (R∪ IA)2∪ (R∪ IA)3∪,..
=(IA∪ R)∪ (IA∪ R∪ R2)∪ (IA∪ R∪ R2∪ R3)∪,..
= IA∪ R∪ R2∪ R3∪,..= IA∪ t(R)
= IA∪ R (R传递 t(R)=R)
=r(R) 所以 r(R)也传递。
。
。
定理 7：设 R1,R2是 A上关系，如果 R1?R2,则
⑴ r(R1)? r(R2) ⑵ s(R1)? s(R2) ⑶ t(R1)?t(R2)
证明⑴ r(R1)=IA∪ R1?IA∪ R2= r(R2)
⑵,⑶类似可证。
定理 8：设 R是 A上关系，则
⑴ sr(R)=rs(R) ⑵ tr(R)=rt(R) ⑶ st(R)?ts(R)
证明,⑴ sr(R)=r(R)∪ (r(R)c=(R∪ IA)∪ (R∪ IA)c
= (R∪ IA)∪ (Rc∪ IAc) =R∪ IA∪ Rc∪ IA
= (R∪ Rc)∪ IA= s(R)∪ IA=rs(R)
⑵ 的证明用前边证明的结论：
(R∪ IA)k= IA∪ R∪ R2∪,..∪ Rk
很容易证明，这里从略。
⑶ 因 R?s(R) 由定理 7得 t(R)?ts(R) st(R)?sts(R)
因 s(R)对称，有定理 6得 ts(R) 也对称，由定理 5得
sts(R)=ts(R) 所以有 st(R)?ts(R) 。 证明完毕。
通常将 t(R) 记成 R+,tr(R)记成 R*,即
t(R)= R+=R∪ R2∪,..∪ Rn∪ …=
tr(R)=rt(R) =R*= R0∪ R∪ R2∪,..∪ Rn∪ …=
练习,给定 A中关系 R
如图所示：分别画出 r(R)、
s(R), t(R),sr(R),rs(R)、
tr(R),rt(R),st(R), ts(R)
的图。
1。
2。
。
。
4
3
∪ Rii=1∞
∪ Rii=0∞
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
r(R) s(R) t(R)
sr(R)
rs(R)
tr(R)
rt(R)
st(R)
ts(R)
本节重点掌握闭包的定义、计算方法和性
质。
作业 第 127页 ⑴、⑸、⑺、⑻
4-7 集合的划分与覆盖
图书馆的图书，要分成许多类存放，学校的学生
要按照专业分成许多班,… 即对集合的元素划分
一,定义 设 X是一个非空集合,A={A1,A2,...,An},
Ai?Φ Ai?X (i=1,2,...,n),如果满足
A1∪ A2∪,..∪ An =X (i=1,2,...,n)
则称 A为集合 X的 覆盖 。
设 A={A1,A2,...,An}是 X一个覆盖,且 Ai?Aj=Φ
(i?j,1≤i,j≤n)则称 A是 X的 划分。 每个 Ai均称为这
个划分的一个划分 (类 )。
例 X={1,2,3},A1={{1,2,3}},A2={{1},{2},{3}},
A3={{1,2},{3}},A4={{1,2},{2,3}},A5={{1},{3}}
A1,A2,A3,A4 是覆盖。 A1,A2,A3也是划分。
划分,一定是覆盖；但覆盖,不一定是划分 。
二,最小划分与最大划分
最小划分,划分块最少的划分。即只有一个划分
块的划分，这个划分块就是 X本身。如 A1 。
最大划分,划分块最多的划分。即每个划分块里
只有一个元素的划分。如 A2 。
A1,A2,A3是一种划分,其中 A1是最小划分,A2是最
大划分。
三,交叉划分
例 X是东大学生集合,A和 B都是 X的划分：
A={M,W},M?X,W?X,M={男生 },W={女生 }
B={L,N},L?X,N?X,L={辽宁人 },N={非 辽宁人 }
C={L∩M,L∩W,N∩M,N∩W }
称 C是 X的交叉划分。
M W
L
N
L∩M L∩W
N∩M N∩W
辽宁男生 辽宁女生 非辽宁男生 非辽宁女生
定义,若 A={A1,A2,...,Am}与 B={B1,B2,...,Bn}都是集合 X
的划分,则其中所有的 Ai?Bj,组成的集合 C,称为 C是 A与
B两种划分的交叉划分, (此定理的证明不讲 )
证明,{ A1,A2,...,Am}与 {B1,B2,...,Bn}的交叉划分是
C={A1?B1,A1?B2,...,A1?Bn,
A2?B1,A2?B2,...,A2?Bn,...,
Am?B1,Am?B2,...,Am?Bn}
在 C中任取元素,Ai?Bh?X (∵ Ai?X,Bj?X)
(A1?B1)∪ (A1?B2)∪,..∪ (A1?Bs)∪ (A2?B1)∪ …
∪ (A2?Bs)∪,.,∪ (Ar?B1)∪ (Ar?B2)∪,..∪ (Ar?Bs)
=(A1?( B1∪ B2∪ B3∪,..Bs))∪
(A2?( B1∪ B2∪ B3∪,.,∪ Bs))∪,.,∪
(Ar?( B1∪ B2∪ B3∪,.,∪ Bs))
= (A1∪ A2∪ A3∪,..∪ Ar) ?( B1∪ B2∪ B3∪,.,∪ Bs)
=X?X=X
再验证 C中任意两个元素不相交：
在 C中任取两个不同元素 Ai?Bh和 Aj?Bk,考察
(Ai?Bh) ? (Aj?Bk) (i=j和 h=k不同时成立 )
= (Ai?Aj)?(Bh?Bk)
i＝ j,h≠k (Ai?Aj)?(Bh?Bk) =Ai??=?
i≠j,h≠k (Ai?Aj)?(Bh?Bk)=???=?
i≠j,h=k (Ai?Aj)?(Bh?Bk)=?? Bh =?
综上所述,C是 X的划分。
作业,第 130页 (1)
4-8 等价关系与等价类
等价关系是很重要的关系，它是我们遇到最多的
关系，例如，数值相等关系 =、命题间的等价关
系 ?、三角形相似 ∽ 和全等关系 ≌, …..
一,等价关系
1.定义,设 R是 A上关系,若 R是自反的、对称的和
传递的，则称 R是 A中的等价关系。若
a,b?A，且 aRb，则称 a与 b等价。
例子，集合 A={1,2,3,4,5,6,7},R是 A上的模 3同
余关系，即
R={<x,y>|x-y可被 3整除 (或 x/3与 y/3的 余数相同 )}
即 <x,y>∈ R? x(mod 3)=y(mod3)
例如 4(mod 3)=7(mod3) 3(mod 3)=6(mod3)
R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<3,3>,<3,6>,<4,1>,
<4,4>,<4,7>,<5,2>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>}
2.等价关系的有向图
1)完全关系 (全域关系 A× A)图，下面分别是当 A中只有
1,2,3个元素时的完全关系图。
1。
2。
1。
2。 3。1。
A={1} A={1,2} A={1,2,3}
2.等价关系的有向图,
上边 的模 3同余关系
R的图：
从关系图可看
出,R是自反、
对称、传递的
关系，所以 R是等价关系。
等价关系 R的有向图可能由若干个独立子图 (R图的一部
分 )构成的，每个独立子图都是完全关系图 。
上述关系 R图就是由三个独立的完全图构成的。
下面给出八个关系如图所示，根据等价关系有向图的
特点，判断哪些是等价关系，
2。
5。
1。
4。 7。
3。
6。
A={1,2,3}下面是 A中关系：
1。
2。 。
1。
2。 。 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1
R5 R6
1。
2。 。
1。
2。 。 33
R3 R4
R7 R8
思考题, A={1,2,3},可构造多少个 A中不同的等价
关系？可以根据等价关系有向图的特点来考虑。
如果等价关系 R中有
a)三个独立子图的情形，则 ( )个等价关系 。
b)二个独立子图的情形，则 ( )个等价关系 。
c)一个独立子图的情形，则 ( )个等价关系 。
一共有 ( )个 中不同的等价关系。
二, 等价类
我们经常用等价关系对集合进行划分，得到的划分块
称之为等价类。
1.定义, R是 A上的等价关系,a∈A,由 a确定的集合 [a]R:
[a]R={x|x∈A∧<a,x>∈R}
称集合 [a]R为由 a形成的 R等价类。简称 a等价类。
可见 x∈[a] R ?<a,x>∈ R
上例,A={1,2,3,4,5,6,7},R是 A上的模 3同余关系，
[1]R={1,4,7}= [4]R = [7]R ----余数为 1的等价类
[2]R={2,5}= [5]R ----余数为 2的等价类
[3]R={3,6}= [6]R ----余数为 0的等价类
思考题,此例为什么只有三个等价类？
2,由等价关系图求等价类, R图中每个独立子图上的结点，
构成一个等价类。不同的等价类个数 =独立子图个数。
上述三个等价关系各有几个等价类？说出对应的
各个等价类。
1。
2。 。 3
R2
1。
2。 。 3
R1
。
R3
。
。1
2 3
从上述模 3同余关系例子中，可以归纳出等价类的性质：任
何两个等价类要么相等，要么不相交；那么在什么情况下相
等？那么在什么情况下不相交？
3.等价类性质
R是 A上等价关系，任意 a,b,c∈ A
⑴ 同一个等价类中的元素，彼此有等价关系 R。
即任意 x,y∈ [a]R,必有 <x,y>∈ R
证明,任取 x,y∈ [a]R，由等价类定义得,<a,x>∈ R,
<a,y>∈ R,由 R对称得,<x,a>∈ R,又由 R传递得 <x,y>∈ R。
⑵ [a]R∩[b]R=Φ,当且 仅当 <a,b>?R。
证明,设 <a,b>?R,假设 [a]R∩[b]R≠Φ,则存在 x∈ [a]R∩[b]R，
∴ x∈ [a]R∧ x∈ [b]R,∴ <a,x>∈ R,<b,x>∈ R,由 R对称得
<x,b>∈ R又由 R传递得 <a,b>∈ R,产生矛盾。
若 [a]R∩[b]R=Φ,而 <a,b>∈ R,由等价类定义得 b∈ [a]R,
又因为 bRb,所以 b∈ [b]R,所以 b∈ [a]R∩[b]R，产生矛盾。
⑶ [a]R=[b]R 当且 仅当 <a,b>∈ R。
证明：若 <a,b>∈ R，则任何 x∈ [a]R,有 <a,x>∈R, 由对
称性得 <b,a>∈R, 再由传递性得 <b,x>∈R,∴x∈ [b]R，
所以 [a]R?[b]R。 类似可证 [b]R?[a]R。 ∴ [a]R=[b]R。
如果 [a]R=[b]R，由于有 aRa,所以 a∈ [a]R, a∈ [b]R,
所以有 <b,a>∈ R,由对称性得 <a,b>∈R.
⑷,A中任何元素 a,a必属于且仅属于一个等价类。
证明,A中任何元素 a,由于有 aRa,所以 a∈ [a]R, 如果
a∈ [b]R, 所以有 <a,b>∈ R.由性质⑶得 [a]R=[b]R 。
⑸,任意两个等价类 [a]R,[b]R，
要么 [a]R=[b]R,要么 [a]R∩[b]R=Φ。
(因为要么 <a,b>∈ R,要么 <a,b>?R。 )
⑹ R的所有等价类构成的集合是 A的一个划分。
(由性质⑷⑸即得。 ) (这个划分称之为 商集 )
三, 商集
商”和除法有关，比如把 一块蛋糕 平均分成四份，从
两种不同的角度看这件事：
从算术角度看, 1用 4除,每份 1/4,这就是“商”,于是,
1=1/4+1/4+1/4+1/4
从集合角度看,
集合 A用模 3同余关系 R划分，得到三个等价类，所以
A {{1,4,7},{2,5},{3,6}}={[1]R,[2]R,[3]R}----商集
定义, R是 A上等价关系，由 R的所有等价类构成的集合
称之为 A关于 R的商集。记作 A/R。即
A/R={[a]R |a∈ A}
用刀分 }{
用 R分
生 日 日
快 快乐 乐 生
例如 A={1,2,3,4,5,6,7},R上模 3同余关系，则
A/R= {[1]R,[2]R,[3]R} ={{1.4.7},{2,5},{3,6}}
练习 X={1,2,3},X上关系 R1,R2, R3,如上图所示。
X/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}}
X/R2={[1]R2,[2]R2}={{1},{2,3}}
X/R1={[1]R3}={{1,2,3}}
1。
2。 。 3
R2
1。
2。 。 3
R1
。
R3
。
。1
2 3
定理, 集合 A上的等价关系 R，决定了 A的一个划分，该划
分就是商集 A/R.
证明：由等价类性质可得,
1) A/R中任意元素 [a]R，有 [a]R?A,
2) 设 [a]R,[b]R是 A/R的两个不同元素，有 [a]R?[b]R=Φ
3) 因为 A中每个元素都属于一个等价类，所以所有等
价类的并集必等于 A。
所以商集 A/R是 A的一个划分。
定理,设 R1和 R2是非空集合 A上的等价关系，则
A/R1=A/R2 当且仅当 R1=R2 。
(这个定理显然成立。 )
四, 由划分确定等价关系
例如,X={1,2,3,4},
A={{1,2},{3},{4}},A是 X
的一个划分，求 X上一个
等价关系 R,使得 X/R=A。
显然 R的图如右图所示：
R={1,2}2∪ {3}2∪ {4}2 。
一般地 A={A1,A2,…,A n}是 X的一个划分，则构造一个 X中
的等价关系 R,使得 X/R=A。
R= A1∪ A2∪,…,∪ An 其中 Ai= Ai× Ai，
下面证明 R是 X中的等价关系。
等价关系 集合的划分
A/R
？
2。
1。 3。
4。
2 2 2 2
定理, 集合 X的一个划分可以确定 X上 的一个等价关系。
证明：假设 A={A1,A2,...,An}是 X的一个划分，如下构造
X 上 的一个等价关系 R,
R= A1∪ A2∪,…,∪ An 其中 Ai = Ai× Ai,(i=1,2…n).
1) 证 R自反,任取 a∈ X,因为 A是 X的划分，必存在
Ai?A使 x?Ai,于是 <a,a>∈ Ai× Ai,又 Ai× Ai ?R∴ 有 aRa。
2) 证 R对称, 任取 a,b∈ X,设 aRb,必存在 Ai?A使得
<a,b>∈ Ai× Ai,于是 a,b?Ai,?bRa,R是对称的。
3) 证 R传递, 任取 a,b,c∈ X,设 aRb,bRc,必存在 Ai?A使
得 <a,b>∈ Ai× Ai,<b,c>∈ Ai× Ai,
(不可能有另一个划分块 Ak?A使得 <b,c>∈ Ak× Ak,因为
如果这样，就使得,既 b∈ Ai又 b?Ak,与 A是划分矛盾。 )
于是 a,b,c?Ai,所以 <a,c>∈ Ai× Ai, 又 Ai× Ai ?R∴ 有 aRc
所以 R传递。 最后得 R是集合 X中的关系。
2 2 2 2
本节重点：
等价关系概念、证明。
等价类概念、性质。
求商集。
作业,第 134页
⑴、⑵、⑷、⑹、⑺
4-9 相容关系
相容关系是另一种常见关系,如朋友关
系、同学关系等。
这些关系的共性是自反的、对称的。
一,定义,给定集合 X上的关系 r,若 r是自反的、
对称的,则 r是 A上 相容关系。
例子,X 是由一些英文单词构成的集合。
X={fly,any,able,key,book,pump,fit},X上关系 r:
r={<α,β>|α∈ X,β∈ X且 α与 β含有相同字母 }
r的有向图：
看出有自反、
对称性。而
不传递。
any。
。 ablefly。
key。
。 book
pump。
fit。
y
b
k
l
y
f y
二, 简化图和简化矩阵
图的简化,⑴不画环；
⑵两条对称边用一条无向直线代替。
令 x1=fly,x2= any,x3= able,x4=key,x5=book,x6= pump,
x7= fit,X={x1,x2,x3,x4,x5,x6,x7},r的简化图为：
矩阵的简化,因为 r的矩阵是对称阵且主对角线全是 1，
用下三角矩阵 (不含主对角线 )代替 r的矩阵。如上图所示。
x2。
x1。 。 x3
x4。
x5。
x6。
x7。
x1 x2 x3 x4 x5 x6
x7
x6
x5
x4
x3
x2 1
1
1
1
1
11
1 1
0
0 0
0 0 0 0
0 0 0
0
0
三,相容类及最大相容类
在等价关系中讨论了等价类，这里要讨论相容类。
定义, 设 r是集合 X上的相容关系,C?X,如果对于 C中任
意两个元素 x,y有 <x,y>∈ r,称 C是 r的一个 相容类 。
上例中 {x1,x2},{x3,x4},{x1,x2,x3},{x2,x3,x4},{x1,x2,x4},
{x3,x4,x5},{x1,x3,x4},{x1,x2,x3,x4},{x1,x7},{x6} 都是相容类。
上述相容类中，有些相容类间有真包含关系。
下面定义最大相容类。
定义, 设 r是集合 X上的相容关系,C是 r的一个相容类，
如果 C不能被其它 相容类所真包含，则称 C是一个 最大
相容类。
也可以说,C是一个相容类,如果 C中加入任意一个新
元素，就不再是相容类,C就是一个 最大相容类。
{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}都是 最大相容类。
从简化图找最大相容类, ------找最大完全多边形。
最大完全多边形,含有结点最多的多边形中，每个结点
都与其它结点相联结。
一个孤立顶点 --------完全 0边形；
两个结点间有连线 (非三角形中的一边 ) ---完全 1边形；
三角形 ------完全 3边形；完全 4边形,… 如下图所示：
在相容关系简化图中,每个最大完全多边形的结点集合
构成一个最大相容类。
上例中最大相容类 {x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}
分别对应最大完全四、三、一、零边形。
。 。 。x
1。 。 。
。 。 。 。
给定 X上相容关系 r’,如图所示,
r’的最大相容类,{x1,x2,x5},
{x2,x3,x5},{x3,x4,x5},
{x1,x4,x5},
四, 完全覆盖,
定义,r是中的相容关系，由 r的所有 最大相容类为元素
构成的集合，称之为 X的完全覆盖。记作 Cr(X)。
Cr(X)={{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}}
Cr’(X)={{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5}}
本节要求,相容关系、相容类概念，画图，求完全覆盖。
作业 第 139页 (2)
x2。 x3 。
x1。 x4。
x5。
4-10 次序关系
次序关系也是常遇到的重要关系，例如：
数值的 ≤、＜,≥、＞关系；
集合的 ?,?关系；
图书馆的图书按书名的字母次序排序；
词典中的字 (词 )的排序；
计算机中文件按文件名排序；
程序按语句次序执行； …….
本节讨论几种次序关系。
一, 偏序关系 (partial order relation)
1,定义, R是 A上自反、反对称和传递的关系，则称 R
是 A上的偏序关系。并称 <A,R>是偏序集。
例如数值的 ≤,≥关系和集合的 ?都是偏序关系。
因为数值 ≤是熟知的偏序关系，所以用符号,≤”表
示任意偏序关系，但要 注意 !!“≤”不一定是“小于或等
于”的含义 。
例 1 A={1,2,4,6},≤是 A中的整
除关系，其关系图如右图，显然
≤是自反、反对称和传递的，即
它是个偏序。
2,x与 y是可比较的, <A,≤>是偏序集,x,y∈ A,如果要
么 x≤y,要么 y≤x,则称 x与 y是可比较的。
上例中 1,2,4或 1,2,6间是可比较的。而 4与 6间是不可比较的
2。
1。
。
6
4
二,全序 (线序、链 )
定义, <A,≤>是偏序集，任何 x,y∈ A,如果 x与 y都是可比
较的，则称 ≤是全序关系 (线序、链 )。
例 2 B={1,2,4,8},≤表示整除关系，
则 ≤是全序关系，如图：
全序关系一定是偏序关系，但是偏序不一定是全序。
偏序关系的有向图，不能直观地反映出元素之间的次序，
所以下面介绍另外一种图 ---Hasse图。通过这个图，就能
够清晰地反映出元素间的层次。
下面介绍 Hasse图。
2。
1。
。
8
4
三,偏序集的哈斯图 (Hasse图 )
<A,≤>是偏序集,x,y∈ Ａ
1.元素 y盖住元素 x：如果 x≤y,且 x≠y,且不存在 z∈ A,使
得 z≠x∧ z≠y∧ x≤z∧ z≤y,则称 元素 y盖住元素 x。
元素 y盖住 x?x≤y∧ x≠y∧ ??z(z∈ A∧ z≠x∧ z≠y∧ x≤z∧ z≤y)
即元素 y盖住元素 x?不存在 z∈ A,使得 z介于 x与 y之间。
上例中 4没有盖住 1，因为中间有个 2,1≤2≤4.
2.偏序集 Hasse图的画法, 令 <A,≤>是偏序集，
1.用,”表示 A中元素。
2.如果 x≤y,且 x≠y,则结点 y要画在结点 x的上方。
3,如果 x≤y,且 y盖住 x,x与 y之间连一直线。
4,一般先从最下层结点 (全是射出的边与之相连 (不考虑
环 ))，逐层向上画，直到最上层结点 (全是射入的边与之
相连 )。 (采用抓两头，带中间的方法 )
。
例如，前边两个例子：
它们的Ｈ asse图分别如下：
可见右图，是全序，它的Ｈ asse图是一条直线，所以
全序 也叫 线序,或 链 。是从它的 Hasse图得名。
下面作 练习,教材第 146页 (7)
2。
1。
。
6
4 2。
1。
。
8
4
１ 。
２ 。
４ 。６ 。
１ 。
２ 。
４ 。
８ 。
4。
1。
3。2。
3。
4。
1。
2。
１ 。 ２ 。
４ 。3。
4。
２ 。
1。
3。
全序
练习：
C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}
≤ 是 C,D上 整除关系, <Ｃ,≤>,<Ｄ,≤>的 Hasse图：
以及 A={a,b,c} <P(A),?>的 Hasse图：
练习：
C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}
≤ 是 C,D上 整除关系, <Ｃ,≤>,<Ｄ,≤>的 Hasse图：
以及 A={a,b,c} <P(A),?>的 Hasse图：
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。 30。
3。
１ 。
2。 5。
１ 0。 １ 5。6。
{a,b,c}。
{b}。
Φ。
{a}。 {c}。
{a,c}。 {b,c}。{a,b}。
<C,≤> <D,≤> <P(A),? >
四,偏序集中的重要元素
在格和布尔代数中，要用到下面一些术语。
设 <A,≤>是偏序集,B是 A的非空子集。
一,极小元与极大元
y是 B的 极小元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ x≤y))
(在 B中没有比 y更小的元素了,y就是 极小元 )
y是 B的 极大元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ y≤x))
(在 B中没有比 y更大的元素了,y就是 极大元 )
举例,给定 <A,≤>的 Hasse图如图所示：
从 Hasse图找
极小 (大 )元：子集
中处在最下 (上 )层
的元素是极小 (大 )
元。
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。
子集 B 极小元 极大元
{2,3}
{1,2,3}
{6,12,24}
C
2,3 2,3
1 2,3
6 24
1 24,36
二,最小元与最大元
y是 B的 最小元 ??y(y∈ B∧ ?x(x∈ B?y≤x))
(最小元 y是 B中元素，该元素比 B中所有元素都小 )
y是 B的 最大元 ??y(y∈ B∧ ?x(x∈ B?x≤y))
(最大元 y是 B中元素，该元素比 B中 所有元素都大 )
举例,给定 <A,≤>的 Hasse图如图所示：
从 Hasse图找 最小 (大 )元：子集中如果只有唯一的极
小 (大 )元，则这个
极小 (大 )元，就是
最小 (大 )元。否则
就没有最小 (大 )元。
下面介绍 最小 (大 )元的唯一定理。
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。子集 B 最小元 最大元
{2,3}
{1,2,3}
{6,12,24}
C
无 无
1 无
6 24
1 无
定理, <A,≤>是偏序集,B是 A的非空子集，如果 B有
最小元 (最大元 )，则最小元 (最大元 )是唯一的。
证明,假设 B有两个最小元 a,b,则
因为 a是 最小元,b∈ B，根据 最小元定义，有 a≤b;
类似地，因为 b是 最小元,a∈ B，根据 最小元定义，有
b≤a。因为 ≤有反对称性，所以有 a=b。
同理可证 最大元的唯一性。
小结, <A,≤>是偏序集,B是 A的非空子集，则
⑴ B的 极小 (大 )元总是存在的，就是子集中处在最下 (上 )
层的元素是极小 (大 )元。
⑵ B的 最小元 (最大元 )有时可能不存在，只有有唯一的极
小 (大 )元，则这个极小 (大 )元就是最小 (大 )元。否则就没
有最小 (大 )元。
3.上界与下界 (Upper Bound and Lower Bound)
y是 B的 上界 ??y(y∈ A∧ ?x(x∈ B?x≤y))
(上界 y是 A中元素，该元素比 B中所有元素都大 )
y是 B的 下界 ??y(y∈ A∧ ?x(x∈ B?y≤x))
(下界 y是 A中元素，该元素比 B中 所有元素都小 )
举例,给定 <A,≤>的 Hasse图如图所示：
从 Hasse图找 上 (下 )界,注意 是在 A中找！
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。
子集 B 上界 下界
{2,3}
{1,2,3}
{6,12,24}
C
1
6,12,24,36 1
24 6,2,3,1
1无
6,12,24,36
4,最小上界 (上确界 )和最大下界 (下确界 )
(Least Upper Bound and Greatest Lower Bound)
定义,y是 B的上界，并且对 B的所有上界 x,都有 y≤x,则
称 y是 B的 最小上界 (上确界 )，记作 LUB B=y 。
(即 y是上界中最小的。如果 B有上确界，则是唯一的 )
y是 B的下界，并且对 B的所有下界 x,都有 x≤y,则
称 y是 B的 最大下界 (下确界 )，记作 GLB B=y 。
(即 y是下界中最大的。如果 B有上确界，则是唯一的 )
举例,给定 <A,≤>的 Hasse图如图所示：
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。
子集 B 上界 下界
{2,3}
{1,2,3}
{6,12,24}
C
1
6,12,24,36 1
24 1,2,3,6
1无
6,12,24,36
上确界 下确界
6
6
24
无
1
1
6
1
* 五,良序
定义, <A,≤>是偏序集，如果对 A的任何非空子集 B,都
有最小元，则称 ≤是 A上的良序，并称 <A,≤>为良序集。
例如 N是自然数集合,I是整数集合,≤是小于或等于
关系,<N,≤>就是 良序集。而 <I,≤>不是良序集。
定理,所有 良序集，一定是全序集。
证明,设 <A,≤>为良序集,任取 x,y∈ A,构成子集 {x,y},它
有最小元，该最小元或是 x,或是 y,于是有 x≤y或 y≤x,所
以 <A,≤>是全序集。
定理, 有限的 全序集，一定是良序集。
证明：设 A={a1,a2,…a n},<A,≤>是全序集，假设它不是良
序，必存在非空子集 B?A,B中无最小元，因 B是有限集，
必存在 x,y∈ B,使得 x y,与 ≤是全序矛盾,∴ <A,≤>是良
序集。
≤
本节要求：
掌握偏序,全序的概念，
会画 Hasse图，
会求重要元素。
作业 第 145页 (1),(6),(7)
本章小结 枚举法
有向图
矩阵
*等价关系 有向
图
等
价
类
商
集
划
分
偏序关系
相
容
类
最
大
相
容
类
完
全
覆
盖
简
化
图
全
序
哈
斯
图
重
要
元
素
计算方法
运算性质
二
元
关
系
概念及表示方法
性
质*
自反
对称
传递
反对称
反自反
相容关系
运
算
复合
求逆
闭包
谓词
*
*
第四章 习题课
第 104页⑴ b) A={0,1} B={1,2} 求 A2× B。
A?B={<x,y>|x?A∧ y?B}
A2 =A× A={<0,0>,<0,1>,<1,0>,<1,1> }
A2× B={<<0,0>,1>,<<0,1>,1>,<<1,0>,1>,<<1,1>,1>,
<<0,0>,2>,<<0,1>,2>,<<1,0>,2>,<<1,1>,2> }
第 109页⑴ X={a,b,c} Y={s} X到 Y的所有关系：
X× Y={<a,s>,<b,s>,<c,s>}
X× Y的任何一个子集都是一个 从 X到 Y的关系。如果
|X|=m |Y|=n则有 2mn个从 X到 Y的关系,故,有 23=8个关系,
R0=Φ
R1={<a,s>} R2={<b,s>} R3={<c,s>}
R4={<a,s>,<b,s>} R5={<a,s>,<c,s>} R6={<b,s>,<c,s>}
R7={<a,s>,<b,s>,<c,s>}
⑵ 设 |A|=n, 有多少个 A上的关系？
因为 R?A× A,所以 A× A有多少个子集就有多少个 A上关
系,由集合的幂集就是该集合的子集构成的,所以 A上关系
个数就是 A× A 的幂集 P(A× A)的元素个数 |P(A× A)|,
而 2|A× A|=2nn= 。所以有 个不同的 A上关系。
第 113页⑴ A={1,2,3},A上五个关系如下,(T略有改动 )
2n2
。。
。
1
32 。。
。
1
32 。。
。
1
32 。。
。
1
32 。。
。
1
32
R S T Φ A× A
R
A× A
Φ
T
S
自反 反自反 对称 反对称 传递
N N N Y Y
Y N Y N YY N N Y Y
N Y Y Y Y
Y N Y N Y
2n2
上述五个关系中，
哪些是等价关系？如果是等价关系，求其商集。
哪些是相容关系？如果是相容关系，求其完全覆盖。
哪些是偏序关系？如是偏序关系,画 Hasse图,并求Ａ的极
小 (大 )元、最小 (大 )元、上界与下界、上确界和下确界。
等价关系, S和 A× A，对应的商集分别是：
A/S={{1,2},{3}} A/A× A={{1,2,3}}
相容关系, S和 A× A，对应的完全覆盖分别是：
CS(A)={{1,2},{3}} CA× A(A)={{1,2,3}}
偏序关系, T
Ａ的极小元、最小元、下界、下确界都是,1
Ａ的极大元、最大元、上界、上确界都是,3 1。
2。
3。
第 118页⑴ R和 S都是 A上关系，
a) R和 S都自反,一定自反。
因为任取 a∈ A,由于 R和 S都自反,所以 <a,a>∈ R 及
<a,a>∈ S 故 <a,a>∈ ∴ 自反，
b) R和 S都反自反,不一定反自反。举反例：
c) R和 S都对称,不一定对称。
d) R和 S都传递,不一定传递。
R So
R So
R So
R So
R So
R So
。１ 。 ２ 。１ 。 ２ 。１ 。 ２Ｒ Ｓ R So
。 a
。 c
。 a
。 cb。
。 a
。 cb。
R S
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。
R S R So
R So
⑵ S是Ｘ上关系。
a)证明Ｓ传递，当且仅当 (可用此定理判定传递 )
证明,充分性,已知
任取 x,y,z∈ X,且有 <x,y>∈ S,<y,z>∈ S,根据关系的复合得
<x,z>∈,由已知得 <x,z>∈ S,所以Ｓ传递。
必要性,已知Ｓ传递，
任取 <x,y>∈,根据关系的复合得
?z(z∈ X∧ <x,z>∈ S∧ <z,y>∈ S),由Ｓ传递得 <x,y>∈ S
所以
b)证明Ｓ自反，当且仅当 IX?S。 (可用此定理判定自反 )
证明,充分性,已知 IX?S，
任取 x∈ X,有 <x,x>∈ IX,由已知得 <x,x>∈ S,所以Ｓ自反。
必要性,已知Ｓ自反，
任取 <x,y>∈ IX,得 x=y,而 S自反，所以 <x,y>∈ S∴ IX?S
S S?Ｓo
S S?Ｓo
S So
S So
S S?Ｓo
⑶ S是Ｘ上关系，证明Ｓ是自反和传递，则 =S。 其
逆为真吗？
证明,由⑵ a)得Ｓ传递，则,只证明 S?
任取 <x,y>∈ S,又已知Ｓ自反，所以 <x,x>∈ S,于是有
<x,x>∈ S∧ <x,y>∈ S，由关系的复合得 <x,y>∈
所以有 S?,最后得 ＝Ｓ。
其逆不一定为真。例如 S如图所示：
它满足 ＝Ｓ，但Ｓ不自反。
⑸ R是 A上关系，
a)R自反,Rc也自反。
因为任取 x∈ A,因 R自反，所以 <x,x>∈ R,∴ <x,x>∈ Rc
b) R对称,Rc也对称。
因为 R对称，所以 Rc =R ∴ Rc也对称。
S So
S S?Ｓo S So
S So
S So S So
S So
。 a
。 cb。
Ｓ
c) R传递,Rc也传递。
方法 1,任取 x,y,z∈ A,且有 <x,y>∈ Rc,<y,z>∈ Rc,于是
<y,x>∈ R,<z,y>∈ R，因 R传递,∴ <z,x>∈ R,于是有
<x,z>∈ Rc,∴ Rc传递。
方法 2,t(Rc)=Rc∪ (Rc)2∪ (Rc)3∪ …
= Rc∪ (R2)c∪ (R3)c∪ …
= (R∪ R2∪ R3∪ …) c
= (t(R))c=Rc (因为 R传递，所以 t(R)=R )
所以 Rc传递。
(R2)c＝ (R?R)c=(Rc?Rc)= (Rc)2
归纳：关系性质证明方法
设 R是 A上关系，
一,证明 R的自反性：
方法 1 用自反定义证：任取 x∈ A,证出 <x,x>∈ R.
方法 2 用恒等关系 IA证,证出 IA ?R,( P119 (2) b) )
方法 3 用自反闭包证,证出 r(R)=R,即 R∪ IA=R.
二,证明 R的反自反性：
方法 1 用反自反定义证：任取 x∈ A,证出 <x,x>?R.
三,证明 R的对称性：
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R,证出 <y,x>∈ R.
方法 2 用求逆关系证,证出 Rc=R.
方法 3 用对称闭包证,证出 s(R)=R,即 R∪ Rc =R.
四,证明 R的反对称性：
方法 1 用定义 1证：
任取 x,y∈ A,设 <x,y>∈ R,<y,x>∈ R.证出 x=y。
方法 2用定义 2证：
任取 x,y∈ A,x≠y,设 <x,y>∈ R,证出 <y,x>?R.
方法 3 用定理证,证出 R∩Rc ? IA, (见 教材 P118)
五,证明 R的传递性：
方法 1 用传递定义证：
任取 x,y,z∈ A,设 <x,y>∈ R,<y,z>∈ R,证出 <x,z>∈ R.
方法 2 用传递闭包证,证出 t(R)=R,
即 R∪ R2∪ R3∪,.,=R.
方法 3用定理证,证出 ( P119 (2) a) )
下面证明第 113页 (4)
R R?Ro
P113(4)R和 S都 A上是自反、对称、传递的，求证 R∩S也
是自反、对称和传递的。
证明,一,证明 R∩S的自反性
方法 1 用自反定义证：任取 x∈ A,(证出 <x,x>∈ R∩S)
因 R和 S都自反，所以有 <x,x>∈ R,<x,x>∈ S，于是有
<x,x>∈ R∩S，所以 R∩S也自反。
方法 2 用恒等关系 IA证,(证出 IA ?R∩S)
因 R和 S都自反，所以 IA ?R, IA ?S，所以 IA ?R∩S
所以 R∩S也自反。
方法 3 用自反闭包证：
(证出 r(R∩S)=R∩S,即 (R∩S)∪ IA= R∩S)
因 R和 S都自反，所以 r(R)=R,r(S)=S,
r(R∩S)=(R∩S)∪ IA= (R∪ IA)∩(S∪ IA)= r(R)∩r(S)=R∩S
所以 R∩S也自反。
二,证明 R∩S 的对称性：
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R∩S,(证出 <y,x>∈ R∩S,)
则 <x,y>∈ R,<x,y>∈ S,因为 R和 S对称，所以有
<y,x>∈ R,<y,x>∈ S,于是 <y,x>∈ R∩S 。 ∴ R∩S 对称。
方法 2 用求逆关系证,(证出 (R∩S )c=R∩S,)
因为 R和 S对称，所以有 Rc=R,Sc=S,而
(R∩S )c=Rc∩S c= R∩S, ∴ R∩S 对称。
方法 3 用对称闭包证：
(证出 s(R∩S )=R∩S,即 (R∩S )∪ (R∩S )c =R∩S,)
因为 R和 S对称，所以 s(R)=R,s(S)=S
s(R∩S )= (R∩S )∪ (R∩S )c =(R∩S )∪ (Rc∩S c)
=(R∪ Rc)∩ (R∪ Sc)∩ (S∪ Sc)∩ (S∪ Rc)
=(s(R)∩ (R∪ Sc))∩ (s(S)∩ (S∪ Rc))
=(R∩ (R∪ Sc))∩ (S∩ (S∪ Rc))=R∩ S (吸收律 )
∴ R∩S 对称。
五,证明 R的传递性：
方法 1 用传递定义证：任取 x,y,z∈ A,
设 <x,y>∈ R∩S,<y,z>∈ R∩S,(证出 <x,z>∈ R∩S )
<x,y>∈ R∩S ∧ <y,z>∈ R∩S
? <x,y>∈ R∧ <x,y>∈ S∧ <y,z>∈ R∧ <y,z>∈ S
? (<x,y>∈ R∧ <y,z>∈ R)∧ (<x,y>∈ S ∧ <y,z>∈ S)
? <x,z>∈ R∧ <x,z>∈ S （因为 R,S传递）
? <x,z>∈ R∩S 所以 R∩S 传递。
方法 2 用传递闭包证,证出 t(R∩S )=R∩S,
即 (R∩S )∪ (R∩S )2∪ (R∩S )3∪,.,=R∩S,
方法 3用定理证,证出
用 方法 2,方法 3证明此题的传递性有很大难度。
R?(S∩T)?(R?S)∩(R?T)
希望同学们灵活掌握证明关系性质的方法 。
(R∩S ) (R∩S ) ?(R∩S )o
P127(1)R的有向图如图所示，求 r(R),s(R),t(R)。
(5)R1和 R2是 A上关系，且 R2 ?R1，求证
a) r(R2)?r(R1),b) s(R2)?s(R1),c) t(R2)?t(R1)。
证明, a) r(R2)=R2∪ IA?R1∪ IA=r(R1),
b) s(R2)= R2∪ (R2)c?R1∪ (R1)c =s(R1),
(因为 R2 ?R1, 所以 (R2)c?(R1)c )
c) 先用归纳法证明 (R2)i?(R1)i,
⑴ i=1时,R2 ?R1 显然结论成立
⑵假设 i≤k时，结论成立，即 (R2)i?(R1)i；
⑶ i=k+1时,(R2)k+1= (R2)k R2?(R1)k R1=(R1)k+1,
t(R2) =R2∪ (R2)2∪,..∪ (R2)k∪,..
? R1∪ (R1)2∪,..∪ (R1)k∪ …= t(R1)。 c)的另一证法,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。r(R) s(R) t(R)
。 。
c) 因为 R2?R1,又 R1?t(R1),所以 R2?t(R1)。 于是有
t(R2)和 t(R1)都是包含 R2的传递关系，而 t(R2)是包含 R2的
最小的传递关系，所以 t(R2)?t(R1)。
(7),R1和 R2是 A上关系，求证
a) r(R1∪ R2)=r(R1)∪ r(R2),
b) s(R1∪ R2)= s(R1)∪ s(R2),
c) t(R1)∪ t(R2) ? t(R1∪ R2),
证明, a) r(R1∪ R2)= (R1∪ R2)∪ IA= (R1∪ IA) ∪ (R2∪ IA)
=r(R1)∪ r(R2),
b) s(R1∪ R2)= (R1∪ R2)∪ (R1∪ R2)c
=(R1∪ R2)∪ (R1)c∪ (R2)c =(R1∪ (R1)c )∪ (R2∪ (R2)c)
=s(R1)∪ s(R2),
c)因 R1? (R1∪ R2)且 R2?(R1∪ R2)，由题 (5)得
t(R1)?t(R1∪ R2),t(R2)?t(R1∪ R2)，所以有
t(R1)∪ t(R2) ? t(R1∪ R2)。
(8),R是 A上关系,R*=tr(R),求证,
a) (R+)+=R+ b) R R*=R+=R* R c) (R*)*=R*
R+ = t(R)=R∪ R2∪ R3∪ …=
R*=rt(R)= IA∪ R∪ R2∪ R3∪,.,=
证明, a) (R+)+=t(t(R)),因为 t(R)是传递的，所以
t(t(R))=t(R),即 (R+)+=R+ 。
b) R R*=R (IA∪ R∪ R2∪ R3∪,.,) ∵ 复合对并可分配，
=R∪ R2∪ R3∪ …= R +。
类似可证 R* R= R+
c) (R*)*=tr(tr(R))=trtr(R)=trrt(R) (∵ tr(R)=rt(R))
=trt(R) (∵ rt(R)是自反的,∴ rrt(R)=rt(R))
=ttr(R)
=tr(R) (∵ tr(R)是传递的,∴ ttr(R)=tr(R))
=R*
。 。
。 。
。
∪ Rii=1∞
∪ Rii=0∞
第 130页 (1).X是集合，且 |X|=4,X有多少个不同的划分？
解,
第 134页 (2),X是集合，且 |X|=4,X上有多少个不同的等
价关系？
解, 此题的答案与上题一样。因为每个划分对应一个等价
关系。
划分块数 各块元素个数 相应划分个数 总数
1 4 C44 = 1
1 3 C41 = 4
2 2 1/2C42 = 32
3 1 1 2 C42 = 6
4 1 1 1 1 C44 =1
15
(4),R是 A上关系,设
S={<a,b>|?c∈ A∧ <a,c>∈ R∧ <c,b>∈ R}
求证若 R是等价关系，则 S也是等价关系。
证明, a)证 S自反,任取 a∈ A,∵ R是自反的,∴ 有
<a,a>∈ R,由 S定义得 <a,a>∈ S,(S定义中 c就是 a)∴ S自反,
b)证 S对称, 任取 a,b∈ A，且有 <a,b>∈ S,由 S定义得
?c∈ A∧ <a,c>∈ R∧ <c,b>∈ R,由 R对称得
?c∈ A∧ <b,c>∈ R∧ <c,a>∈ R,由 S定义得 <b,a>∈ S,S对称,
c)证 S传递,任取 a,b,c∈ A,有 <a,b>∈ S,<b,c>∈ S,由 S定义得
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,
由 S定义得 <a,c>∈ S,所以 S传递, 所以 S是 A上等价关系,
(6),R是 A上对称和传递的关系，证明如果 ?a∈ A,?b∈ A,
使得 <a,b>∈ R,则 R是一个等价关系,
证明,任取 a∈ A,有已知得 ?b∈ A,使得 <a,b>∈ R,由 R对称
得 <b,a>∈ R,又由 R传递得,<a,a>∈ R,R自反,∴ R是等价
关系,
(1)(7).R和 S都是 A上等价关系,下面哪个是 A上等价关系?
证明或举反例说明,
a) R∪ S b) R∩S c) ~R (即 A× A-R)
d) R-S e)R2 f) r(R-S)
解,a) c) d) f)不是, 请看反例,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。S R∪ S
。 a
。 cb。 ~R
。 a
。 cb。 R’
。 a
。 cb。 R’-S
。 a
。 cb。 r(R’-S)
b),R∩S是等价关系,前面已经证明过,(第 113页题 (4))
e).① 证 R2自反,任取 a∈ A,因为 R自反,所以 <a,a>∈ R,根据
关系的复合得,<a,a>∈ R R,即 <a,a>∈ R2,所以 R2自反。
② 证 R2对称,(R2)c=(Rc)2=R2 (由 R对称得 Rc=R) ∴ R2对称
③ 证 R2传递，任取 a,b,c∈ A,设有 <a,b>∈ R2,<b,c>∈ R2,
根据关系的复合得,
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,∴ <a,c>∈ R2
所以 R2传递。最后得 R2是等价关系。
第 139页 (2), X={x1,x2,x3,x4,x5,x6},R是 X上相容关系，
其简化关系矩阵如下：求 X的完全覆盖。
解, R的简化图为：
CR(X)={{x1,x2,x3,},{x1,x3,x6},{x3,x4,x5},{x3,x5,x6}}
o
x2 1
x3 1 1
x4 0 0 1
x5 0 0 1 1
x6 1 0 1 0 1
x1 x2 x3 x4 x5
x1 。 。 x2
x6 。
x5 。 。 x4
。 x3
第 145页 (1),给定集合 {3,5,15},{1,2,3,6,12},{3,9,27,54}，
≤为整除关系，分别画出上述集合上的 ≤的关系图，
Hasse图，并指出哪些是全序关系。
全序
。
。 。
。
。 。。
。
1
2 36
1215
53
。
。 。
。
27
54
9
3
。
。 。
。
。 。
。
。
1
2 3
6
1215
53
。
。
。
。
27
54
9
3
(6), P={x1,x2,x3,x4,x5},P上偏序关系的
Hasse图如图所示，求子集 {x1,x2,x3}，
{x2,x3,x4},{x3,x4,x5}和 P的极小 (大 )元、
最小 (大 )元、上界、下界、最小上界和
最大下界 (上确界和下确界 )。
。
。 。
。。
x1
x2 x3
x4 x5
子 集 极小元 极大元 最小元 最大元 上界 下界 上确界 下确界
{x1,x2,x3} x2,x3 x1 无 x1 x1 x4 x1 x4
{x2,x3,x4} x4 x2,x3 x4 无 x1 x4 x1 x4
{x3,x4,x5} x4,x5 x3 无 x3 x1,x3 无 x3 无
P x4,x5 x1 无 x1 x1 无 x1 无
第四章 二元关系
到此结束
二元关系是一个很重要的概念, 它在很多数学领域中
都有应用, 在计算机科学的如下理论都离不开关系,
逻辑设计, 数据结构, 编译原理, 软件工程
数据库理论, 计算理论, 算法分析, 操作系统 等
本章主要介绍：
关系的概念及表示方法
关系的性质
关系的运算,关系的复合,求逆关系,关系的闭包,
三种关系, 等价关系,相容关系,次序关系。
4-1 序偶与集合的笛卡尔积
实际上“序偶”概念以前已经用过。例如，用序
偶表示平面直角坐标系中一个点 (a,b)。设 x表示
上衣,y表示裤子,(x,y)可以表示一个人的着装。
一,序偶与有序 n元组
1.定义,由两个对象 x,y组成的序列称为有序二
元组，也称之为序偶，记作 <x,y>；称 x,y分
别为序偶 <x,y>的第一，第二元素。
注意，序偶 <x,y>与集合 {x,y}不同：
序偶 <x,y>：元素 x和 y有 次序；
集合 {x,y}：元素 x和 y的次序是无关紧要的。
2.定义,设 <x,y>,<u,v>是两个序偶，如果
x=u和 y=v，则称 <x,y>和 <u,v>相等，
记作 <x,y>=<u,v>.
3,定义,有序 3元组是一个序偶,其第一个元素也是个序偶。
有序 3元组 << a,b>,c>可以简记成 <a,b,c>。
但 <a,<b,c>>不是 有序 3元组。
4.定义,有序 n元组是一个序偶,其第一个元素本身是个有
序 n-1元组,记作 <<x1,x2,?,xn-1>,xn>。且可以简记成
<x1,x2,?,xn-1,xn>。
5,定义, <x1,x2,?,xn>=<y1,y2,·?,yn>
?( x1= y1)? ( x2= y2) ?? ?( xn= yn)
二,集合的 笛卡尔积
例如“斗兽棋”的 16颗棋子，
可看成是由两种颜色的集合 A和 8种动物的集合 B组成的。
A={红,蓝 }
B={象,狮,虎,豹,狼,狗,猫,鼠 }
每个棋子可以看成一个序偶，斗兽棋可记成集合 A?B,
{ <红,象 >,<红,狮 >,<红,虎 >,<红,豹 >,<红,狼 >,<红,狗 >,<红,猫 >,<红,鼠 >,
<蓝,象 >,<蓝,狮 >,<蓝,虎 >,<蓝,豹 >,<蓝,狼 >,<蓝,狗 >,<蓝,猫 >,<蓝,鼠 > }
虎象 狮 豹 狼 鼠猫狗
虎象 狮 豹 狼 鼠猫狗
1.定义,设 A,B是集合，由 A的元素为第一元素，
B的元素为第二元素组成序偶的集合，称为 A
和 B的笛卡尔积，记作 A× B，即
A?B={<x,y>|x?A∧ y?B}
例 1 设 A={0,1},B={a,b}，求 A?B, B?A，
A?A 。
解,A?B={<0,a>,<0,b>,<1,a>,<1,b>}
B?A={<a,0 >,<b,0>,<a,1>,<b,1>}
A?A={<0,0>,<0,1>,<1,0>,<1,1>}
可见 A× B≠B× A
所以，集合的笛卡尔积运算不满足交换律。
另外
(A?B)?C={<<a,b>,c>|<a,b>?A?B ?c?C}
A?(B?C)={<a,<b,c>>|a?A ?<b,c>?B?C},
因 <a,<b,c>>不是有序三元组,
所以 (A?B)?C?A?(B?C)。
故 ?也不满足结合律。
2.性质
1) 如果 A,B都是有限集，且 |A|=m,|B|=n，则
|A?B |=mn,
证明：由笛卡尔积的定义及排列组合中的乘法原
理，直接推得此定理。
2) A?Φ=Φ?B=Φ
3) ?对 ∪ 和 ∩满足分配律。
设 A,B,C是任意集合，则
⑴ A?(B∪ C)= (A?B)∪ (A?C)；
⑵ A?(B∩C)= (A?B)∩(A?C)；
⑶ (A∪ B)?C= (A?C)∪ (B?C)；
⑷ (A∩B)?C= (A?C)∩(B?C)
证明⑴,任取 <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) 所以⑴式成立。
其余可以类似证明。
4)若 C??,则
A?B?(A?C?B?C) ?(C?A?C?B).
证明, 必要性,设 A?B，求证 A?C?B?C
任取 <x,y>?A?C ?x?A?y?C
?x?B?y?C (因 A?B)
?<x,y>?B?C 所以,A?C?B?C,
充分性,若 C??,由 A?C?B?C 求 证 A?B
取 C中元素 y,任取 x?A?x?A?y?C
?<x,y>?A?C
?<x,y>?B?C (由 A?C?B?C )
?x?B?y?C?x?B 所以,A?B.
所以 A?B?(A?C?B?C)
类似可以证明 A?B ?(C?A?C?B).
5) 设 A,B,C,D为非空集合，则
A?B?C?D?A?C∧ B?D.
证明, 首先,由 A?B?C?D 证明 A?C∧ B?D.
任取 x?A，任取 y?B，所以
x?A?y?B
?<x,y>?A× B
?<x,y>?C× D (由 A?B?C?D )
?x?C?y?D 所以,A?C∧ B?D.
其次,由 A?C,B?D,证明 A?B?C?D
任取 <x,y>?A× B
<x,y>?A× B ? x?A?y?B
? x?C?y?D (由 A?C,B?D)
?<x,y>?C× D 所以,A?B?C?D 证毕,
6)约定
(…(A 1?A2)?… ?An-1)?An)=A1?A2?… ?An
特别 A?A?… ?A = An
设 R是实数集合，则 R2表示 笛卡尔坐标平面，
R3表示 三维空间,Rn表示 n维空间。
3.应用
1)令 A1={x|x是 学号 } A2={x|x是 姓名 } A3={男,女 }
A4={x|x是 出生日期 } A5={x|x是 班级 } A6 ={x|x是 籍贯 }
则 A1?A2?A3 ?A4?A5 ?A6中一个元素：
<001,王强，男,1981:02:16，计 2001-1，辽宁 >
这就是学生档案数据库的一条信息，所以学生
的档案就是 A1?A2?A3 ?A4?A5 ?A6的一个子集。
n 个
2) 令
A={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,
w,x,y,z} 是英文字母表
一个 英文单词可以看成有序 n元组：如
at=<a,t>,boy=<b,o,y>,data=<d,a,t,a>,
computer=<c,o,m,p,u,t,e,r>
于是可以说：
at?A2,boy?A3,data?A4,computer?A8,…
于是英文词典中的 单词集合 可以看成是
A∪ A2∪ … ∪ An 的一个子集。
作业 第 105页 ⑵
4-2 关系及其表示法
关系是一个非常普遍的概念，如数值的大于关
系、整除关系，人类的父子关系、师生关系、同
学关系等。下面讨论如何从中抽象出关系的定义
和如何表示关系。
一,例子
1,大写英字母与五单位代码的对应关系 R1:
令 α={A,B,C,D,…Z}
β={30,23,16,22,…,21} 是 五单位代码集合
β={11000,10011,01110,10010,…,10001}
R1={<A,30>,<B,23>,<C,16>,...,<Z,21>}?α× β
2.令Ａ ={1,2,3,4},A中元素间的 ≤关系 R2,
R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,
<2,4>,<3,3>,<3,4>,<4,4>}?A× A
二, 基本概念
1.关系的定义
定义 1:设 A、Ｂ是集合，如果Ｒ ?A× B，则称 R是
一个 从 A到 B的二元关系。如果 R?A× A，则
称 R是 A上 的二元 关系。 二元 关系简称为关系。
定义 2:任何序偶的集合，都称之为一个二元关系。
如,R={<1,a>,<书,车 >,<人,树 >}
<x,y>?R ?xRy 也称之为 x与 y有Ｒ关系。
后缀表示 中缀表示
<x,y>?R ?xRy 也称之为 x与 y没有Ｒ关系。
例 3,R是实数集合,R上的几个熟知的关系：
从例 3中可以看出 关系是序偶 (点 )的集合 (构
成线、面 )。
x2+y2=4≤
≥
=
x
y
2.关系的定义域与值域
定义域 (domain), 设 R?A× B，由所有 <x,y>?R
的第一个元素组成的集合，称为 R的定义域，
记作 dom R，即
dom R={x|?y(<x,y>?R)}
值域 (range), 设 R?A× B，由所有 <x,y>?R的第
二个元素组成的集合，称为 R的值域，
记作 ran R，即
ran R={y|?x(<x,y>?R)}
上述 R2={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2,3>,
<2,4>,<3,3>,<3,4>,<4,4>}
dom R2 ={1,2,3,4}
ran R2 ={1,2,3,4}
三, 关系的表示方法
1,枚举法,
即将关系中所有序偶一一列举出，写在大括号
内。如前的 R2 ={ <1,1>,<1,2>,<1,3>,<1,4>,<2,2>,
<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} 。
2.谓词公式法,
即用谓词公式表示序偶的第一元素与第二元素
间的关系。例如
R={<x,y>|x<y}
3.有向图法,
R?A× B,用两组小圆圈 (称为 结点 )分别表示 A
和 B的元素，当 <x,y>?R时，从 x到 y引一条有
向弧 (边 )。这样得到的图形称为 R的关系图。
如 R?A× A,即 R是集合 A中关系时,可能有
<x,x>?R,则从 x到 x画一条有向环 (自回路 )。
例 设 A={1,2,3,4},B={a,b,c},R3 ?A× B，
R3={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}
则 R3的关系图如下：
例 设 A={1,2,3,4},R4 ?A× A，
R4={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}
则 R4的关系图如右上图。
1。
2。
3。
4。
。
。
。
A B
a
b
c
1。 。
4。 。
2
3
R4,R3,
4.矩阵表示法,
有限集合之间的关系也可以用矩阵来表示，这种表示
法便于用计算机来处理关系。
设 A={a1,a2,?,am},B={b1,b2,?,bn}是个有限集，
R?A× B，定义 R的 m× n阶 矩阵
MR=(rij)m× n，其中
rij=
R3={ <1,a>,<1,c>,<2,b>,<3,a>,<4,c>}
R4={ <1,1>,<1,4>,<2,3>,<3,1>,<3,4>,<4,1>,<4,2>}
上例中 MR = MR4=
1 若 <ai,bj>∈ R
0 若 <ai,bj>∈ R (1≤i≤m,1≤j≤n)
3
1 0 1
0 1 0
1 0 0
0 0 1 4× 3
1
2
3
4
a b c
1 0 0 1
0 0 1 0
1 1 0 0
1 0 0 1
4× 4
1
2
3
4
1 2 3 4
四,三个特殊关系
1.空关系 Φ：
因为 Φ?A× B,(或 Φ?A× A)，所以 Φ也
是一个从 A到 B(或 A上 )的关系，称之为 空
关系 。即无任何元素的关系，它的关系图
中只有结点,无任何边；它的矩阵中全是 0。
2.完全关系 (全域关系 )：
A× B(或 A× A)本身也是一个从 A到 B(或
A上 ) 的关系，称之为完全关系。即含有全
部序偶的关系。它的矩阵中全是 1。
3,A上的 恒等关系 IA：
IA?A× A，且 IA ={<x,x>|x∈ A}称之为 A
上的恒等关系。
例如 A={1,2,3},则 IA ={<1,1>,<2,2>,<3,3>}
A上的 Φ、完全关系及 IA的关系图及矩阵如
下：
MIA =
1 0 0
0 1 0
0 0 1 3× 3
1。
2。 。 3
1。
2。 。 3
1 1 1
1 1 1
1 1 1 3× 3
1。
。2。 3
0 0 0
0 0 0
0 0 0 3× 3
MΦ= MA× A=
Φ A× A IA
五, 关系的集合运算
由于关系就是集合，所以集合的 ∩,∪,
-,?和 ~运算对关系也适用。
例如,A是学生集合,R是 A上的同乡关系，
S是 A上的同姓关系，则
R∪ S：或同乡或同姓关系
R∩S：既同乡又同姓关系
R-S,同乡而不同姓关系
R?S：同乡而不同姓,或同姓而不同乡关系
~R：不是同乡关系,这里 ~R=(A× A)-R
作业 第 109页 ⑵、⑸ c)d)
4-3 关系的性质
本节将研究关系的一些性质, 它们在关系的研究
中起着重要的作用 。 这是本章最重要的一节 。
本节中所讨论的关系都是集合 A中的关系 。
关系的性质主要有：自反性, 反自反性, 对称
性, 反对称性和传递性 。
一,自反性
定义,设 R是集合 A中的关系, 如果对于任意 x∈ A都
有 <x,x>∈ R (xRx),则称 R是 A中自反关系 。 即
R是 A中自反的 ??x(x?A?xRx)
例如在实数集合中,“?”是自反关系, 因为, 对任
意实数 x,有 x ? x.
从关系有向图看自反性,每个结点都有环。
从关系矩阵看自反性：主对角线都为 1。
令 A={1,2,3}给定 A上八个关系如下：
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
可见这八个关系中 R1,R3,R4是自反的。
二,反自反性
定义, 设 R是集合 A中的关系，如果对于任
意的 x∈ A都有 <x,x>?R,则称 R为 A中的反
自反关系。即
R是 A中反自反的 ??x(x?A?<x,x>?R)
从关系有向图看反自反性,每个结点都无环。
从关系矩阵看反自反性：主对角线都为 0。
如实数的大于关系 >，父子关系是反自反的。
注意,一个不是自反的关系，不一定就是反
自反的，如前边 R6,R7非自反,也非反自反。
下面 R2,R5,R8、均是反自反关系 。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
三,对称性
定义,R是集合 A中关系,若对任何 x,y∈ A,如
果有 xRy,必有 yRx,则称 R为 A中的对称关系。
R是 A上对称的
??x?y((x?A?y?A?xRy) ?yRx)
从关系有向图看对称性,在两个不同的结点
之间，若有边的话，则有方向相反的两条边。
从关系矩阵看对称性：以主对角线为对称
的矩阵。
邻居关系是对称关系，朋友关系是对称关系。
下边 R3,R4,R6, R8均是对称关系。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
四,反对称性
定义,设 R为集合 A中关系,若对任何 x,y∈ A,如果有
xRy,和 yRx,就 有 x=y,则称 R为 A中反对称关系 。
R是 A上反对称的
??x?y((x?A?y?A?xRy?yRx) ?x=y)
??x?y((x?A?y?A?x?y?xRy)?y x) (P112)
由 R的关系图看反对称性,两个不同的结点之间
最多有一条边。
从关系矩阵看反对称性,以主对角线为对称的
两个元素中最多有一个 1。
另外对称与反对称不是完全对立的,有些关系
它既是对称也是反对称的,如空关系和恒等关系。
R
下边 R1,R2,R4,R5,R8均是反对称关系。
R4,R8既是对称也是反对称的。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
五, 传递性
定义,R是 A中关系，对任何 x,y,z∈ A,如果有 xRy,和 yRz,就
有 xRz,则称 R为 A中传递关系。
即 R在 A上传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
实数集中的 ≤、＜，集合 ?,?是传递的。
从关系关系图和关系矩阵中不易看清是否有传递性。有
时，必须直接根据传递的定义来检查。
检查时要特别注意使得传递定义表达式的前件为 F的时候
此表达式为 T，即是传递的。
即若 <x,y>∈ R与 <y,z>∈ R有一个是 F时 (即定义的前件为
假 ),R是传递的。
例如 A={1,2},下面 A中关系 R是传递的,
通过带量词的公式在论域展开式说明
R在 A上传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
??x?y?z((xRy?yRz)?xRz) (为了简单做些删改 )
??y?z((1Ry?yRz)?1Rz)??y?z((2Ry?yRz)?2Rz)
?(?z((1R1?1Rz)?1Rz)??z((1R2?2Rz)?1Rz)
?(?z((2R1?1Rz)?2Rz) ?(?z((2R2?2Rz)?2Rz))
?(((1R1?1R1)?1R1)?((1R1?1R2)?1R2)) ?
(((1R2?2R1)?1R1)?((1R2?2R2)?1R2)) ?
(((2R1?1R1)?2R1)?((2R1?1R2)?2R2)) ?
(((2R2?2R1)?2R1)) ? ((2R2?2R2)?2R2))
? (((F?F)?F)?((F?T)?T))?(((T?F)?F)?((T?F)?T))?
(((F?F)?F)?((F?T)?F))?(((F?F)?F))?((F?F)?F))?T
1? ?2
下边 R1,R3,R4,R5,R8均是传递的关系 。
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
R5 R6 R7 R8
本节要求,
1.准确掌握这五个性质的定义。
2.熟练掌握五个性质的判断和证明。
R是 A中 自反 的 ??x(x?A?xRx)
R是 A中 反自反 的 ??x(x?A?<x,x>?R)
R是 A上 对称 的 ??x?y((x?A?y?A?xRy) ?yRx)
R是 A上 反对称 的
??x?y((x?A?y?A?xRy?yRx)?x=y)
??x?y((x?A?y?A?x?y?xRy)?y x)
R在 A上 传递
??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)
上述定义表达式都是 蕴涵式,所以判断关系 R性质时要特
别注意使得性质定义表达式的前件为 F的时候此表达式
为 T，即 R是满足此性质的。 (自反和反自反性除外 )
R
自反性
反自反性
对称性
传递性
反对称性
每个结点都有环 主对角线全是 1
每个结点都无环 主对角线全是 0
不同结点间如果有边,
则有方向相反的两条
边,
是以对角线为对称
的矩阵
不同结点间,最多有一
条边,
以主对角线为对称
的位置不会同时为 1
如果有边 <a,b>,<b,c>,
则也有边 <a,c>,
或者定义的前件为假,
如果 aij=1,且 ajk=1,
则 aik=1
从 关 系的矩 阵从 关 系的有向 图性 质 判定,
下面归纳这八个关系的性质,Y-有 N-无
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1 R3 R4
自反性 反自反性 对称性 反对称性 传递性
R1 Y N N Y Y
R2 N Y N Y N
R3 Y N Y N Y
R4 Y N Y Y Y
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R5 R6 R7 R8
自反性 反自反性 对称性 反对称性 传递性
R5 N Y N Y Y
R6 N N Y N N
R7 N N N N N
R8 N Y Y Y Y
练习 1:令 I是整数集合,I上关系 R定义为：
R={<x,y>|x-y可被 3整除 }，求证 R是自反、对称和传递的。
证明, ⑴证自反性,任取 x∈ I,(要证出 <x,x>?R )
因 x-x=0,0可被 3整除,所以有 <x,x>∈ R,故 R自反。
⑵证对称性,任取 x,y∈ I,设 <x,y>∈ R,(要证出 <y,x>?R )
由 R定义得 x-y可被 3整除,即 x-y=3n(n∈ I)，
y-x=-(x-y)=-3n=3(-n),因 -n∈ I,∴ <y,x>∈ R,
所以 R对称。
⑶ 证传递性,任取 x,y,z∈ I,设 xRy,yRz,(要证出 xRz)
由 R定义得 x-y=3m,y-z=3n (m.n∈ I)
x-z= (x-y)+(y-z)=3m+3n=3(m+n),因 m+n∈ I,
所以 xRz,所以 R传递。 证毕
练习 2,设 R是集合 A上的一个自反关系,求证：
R是对称和传递的，当且仅当
<a,b>和 <a,c>在 R中,则有 <b,c>也在 R中。
证明, 必要性, 已知 R是对称和传递的。
设 <a,b>?R 又 <a,c>?R,(要证出 <b,c>?R )
因 R对称的故 <b,a>?R,又已知 <a,c>?R 由传递性
得 <b,c>?R。所以有如果 <a,b>和 <a,c>在 R中,则有
<b,c>也在 R中。
充分性, 已知任意 a,b,c?A,如 <a,b>和 <a,c>在 R
中,则有 <b,c>也在 R中。
先证 R对称,任取 a,b?A 设 <a,b>?R,(要证出
<b,a>?R ) 因 R是自反的,所以 <a,a>?R，由
<a,b>?R且 <a,a>?R，根据已知条件得 <b,a>?R,
所以 R是对称的。
再证 R传递,任取 a,b,c?A 设 <a,b>?R，
<b,c>?R。 (要证出 <a,c>?R )
由 R是对称的,得 <b,a>?R,由
<b,a>?R且 <b,c>?R，根据已知条件得
<a,c>?R, 所以 R是传递的。
作业 第 113页
⑴、⑶、⑷
4-4 关系的复合
二元关系除了可进行集合并、交、补等运算外，
还可以进行一些新的运算，先介绍由两个关系生
成一种新的关系，即关系的复合运算。
例如，有 3个人 a,b,c,A={a,b,c}，
R是 A上 兄妹 关系，
S是 A上 母子 关系，
<a,b>∈ R∧ <b,c>∈ S
即 a是 b的哥哥,b是 a的妹妹 ;
b是 c的母亲,c是 b的儿子。
则 a和 c间就是 舅舅和外甥 的关系,记作 R?S,
称它是 R和 S的复合关系 。
SR?
a b cR S
1.定义,设是 R从 X到 Y的关系,S是从 Y到 Z的关
系，则 R和 S的复合关系记作 R?S 。定义为：
R?S ={<x,z>|x?X?z?Z??y(y?Y
?<x,y>?R?<y,z>?S)}
显然,R?S 是从 X到 Z的关系。
2.复合关系的计算方法 (俗称过河拆桥法 )
A={1,2,3} B={1,2,3.4} C={1,2,3,4,5}
R?A× B S?B× C
⑴ 枚举法
R={<1,2>,<2,3>,<2,4>,<3,1>}
S={<1,2>,<2,1>,<2,3>,<3,4>,<4,2>,<4,5>} 则
R?S={<1,1>,<1,3>,<2,4>,<2,2>,<2,5>,<3,2>}
⑵有向图法
⑶关系矩阵法
令 A={a1,a2,…,a m} B={b1,b2,…,b n}
C={c1,c2,…,c t} R?A× B S?B× C
。
。
。
。
C
1
2
3
。 4
1。
2。
3。
A
1。
2。
3。
A
。
。
。
B
1
2
3
。 4
R S
5。
。
。
。
C
1
2
3
。 4
5
SR?
c11=(a11∧ b11)∨ (a12∧ b21)∨,..∨ (a1n∧ bn1)
= (a1k∧ bk1) (其中 ∧ 是逻辑乘,∨ 是逻辑加 )
cij=(ai1∧ b1j)∨ (ai2∧ b2j)∨,..∨ (ain∧ bnj)
= (aik∧ bkj) (1≤i≤m,1≤j≤t)
MS MR
<a1,b1><a1,b2>...<al,bn>
<a2,b1><a2,b2>...<a2,bn>...,..
<am,b1><am,b2>...<am,bn>
(aij)
<b1,c1><b1,c2>...<bl,ct>
<b2,c1><b2,c2>...<b2,ct>...,..
<bn,c1><bn,c2>...<bn,ct>
(bij)
<a1,c1>...<al,ct>
<a2,c1>...<a2,ct>...,..
<am,c1>...<am,ct>
M
SR?
(cij)
0 1 0 0
0 0 1 1
1 0 0 0 3× 4
。 1 0 0 0 01 0 1 0 0
0 0 0 1 0
0 1 0 0 1
=
4× 5
1 0 1 0 0
0 1 0 1 1
1 0 0 0 0 3 × 5
k=1
n∨
k=1
n∨
⑷ 谓词公式法
设 I是实数集合,R和 S都是 I上的关系，定义如下：
R={<x,y>| y=x2+3x}
S={<x,y>| y=2x+3}
所以 R?S ={<x,y>| y=2x2+6x+3}
三,性质
关系复合运算不满足交换律，但是
1.满足结合律, R?A× B S?B× C T?C× D 则
TS)(RT)S(R ???? ?
x x2+3x 2(x2+3x)+3 = 2x2+6x+3R S
证明：任取 <a,d>∈ R (S T)
??b(b∈ B∧ <a,b>∈ R∧ <b,d>∈ S T)
??b(b∈ B∧ <a,b>∈ R∧ ?c(c∈ C∧ <b,c>∈ S∧ <c,d>∈ T))
??b?c(b∈ B∧ <a,b>∈ R∧ (c∈ C∧ <b,c>∈ S∧ <c,d>∈ T))
??c?b(c∈ C∧ (b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∧ <c,d>∈ T))
??c (c∈ C∧ ?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∧ <c,d>∈ T)
??c (c∈ C∧ <a,c>∈ R S)∧ <c,d>∈ T)
?<a,d>∈ (R S) T
TS)(RT)S(R ???? ?
A B
C D
R
T
所以
可以用下图形象表示,
2,R?A× B S?B× C T?B× C
⑴ R (S∪ T)=(R S)∪ (R T)
⑵ R (S∩T)?(R S)∩(R T)
证明 ⑴ 任取 <a,c>∈ R (S∪ T)
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∪ T)
??b(b∈ B∧ <a,b>∈ R∧ (<b,c>∈ S∨ <b,c>∈ T))
??b((b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T))
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T)
?<a,c>∈ R S∨ <a,c>∈ R T
?<a,c>∈ (R S)∪ (R T)
所以 R (S∪ T)=(R S)∪ (R T)
证明⑵ 任取 <a,c>∈ R (S∩T)
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S∩T)
??b(b∈ B∧ <a,b>∈ R∧ (<b,c>∈ S∧ <b,c>∈ T))
??b((b∈ B∧ <a,b>∈ R∧ <b,c>∈ S) ∧
(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T))
??b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ S)∨
?b(b∈ B∧ <a,b>∈ R∧ <b,c>∈ T)
?<a,c>∈ R S ∧ <a,c>∈ R T
?<a,c>∈ (R S)∩(R T)
所以 R (S∩T)?(R S)∩(R T)
?x(A(x)∧ B(x)) ??xA(x)∧ ?xB(x)
3,R是从 A到 B的关系，则
R IB=IA R=R
此式的证明很容易，从略。下面列举一例
来验证。
令 A={1,2,3},B={a,b,c,d}
从这两个图看出它们的复合都等于 R。
1。
2。
3。
AIA
。
。
。
B
a
b
c
。 d
R
1。
2。
3。
AR
IB
。
。
。
a
b
c
。 d
。
。
。
B
a
b
c
。 d
1。
2。
3。
A B
4,关系的乘幂
令 R是 A上关系，由于复合运算可结合，所以
关系的复合可以写成乘幂形式。即
R R=R2,R2 R=R R2 =R3,…
一般地
R0 =IA，
Rm Rn = Rm+n
(Rm)n =Rmn (m,n为非负整数 )
例如 R是 A上关系，如上图所示,可见
<a,c>?R2,表明在 R图上有从 a到 c有两条边的路径,
a b c;<a,d>?R3,表明在 R图上有从 a到 d有三条
边的路径,a b c d。,..如果 <x,y>?Rk,表明在
R图上有从 x到 y有 k条边 (长为 k)的路径 。 (x,y?A)
a
d
b
c
R:
4-5 逆关系
逆关系 (反关系 )也是我们经常遇到的概念，例
如 ≤与 ≥就是互为逆关系。
一,定义
R是从 A到 B的关系，如果将 R中的所有序偶的
两个元素的位置互换，得到一个从 B到 A的关系，
称之为 R的逆关系，记作 RC，或 R-1。
RC={<y,x>|<x,y>?R}
<y,x>∈ RC ?<x,y>?R
二, 计算方法
1,R={<1,2>,<2,3>,<3,4>,<4,5>}
RC ={<2,1>,<3,2>,<4,3>,<5,4>}
2,RC的有向图：是将 R的有向图的所有边的方向
颠倒一下即可。
3,RC的矩阵 M =(MR)T 即为 R矩阵的转置。如
三,性质
令 R,S都是从 X到 Y的关系，则
1,(RC)C = R
2,(R∪ S)C = RC∪ SC 。
3,(R∩S)C = RC∩SC 。
4,(R－ S)C = RC－ SC 。
RC
1 0 11 0 1 00 0 0 1
1 0 1 1
MR=
3× 4
0 0 0
1 0 1
0 1 1
MR =c
4× 3
证明 1.：任取 <y,x>?(R∪ S)C，则
<y,x>?(R∪ S)C ? <x,y>?R∪ S
? <x,y>?R∨ <x,y>?S
? <y,x>?RC∨ <y,x>?SC
?<y,x>? RC∪ SC
所以 (R∪ S)C = RC∪ SC,其它类似可证。
5,R?S ? RC?SC 。
证明, 充分性,已知 RC? SC,则任取 <x,y>∈ R
?<y,x>?RC? <y,x>?SC ? <x,y>?S ∴ R?S
必要性,已知 R? S，则任取 <y,x>∈ RC
? <x,y>?R?<x,y>?S ?<y,x>?SC ∴ RC?SC
6.(~R)C=~RC
证明,任取 <y,x>∈ (~R)C ?<x,y>∈ ~R?<x,y>?R
?<y,x>?RC ?<y,x>∈ ~RC ∴,(~R)C=~RC
7.令 R是从 X到 Y的关系,S是 Y到 Z的关系，则
(R S)C= SC RC 。 (注意 ≠RC SC )
证明, 任取 <z,x>∈ (R S)C
?<x,z>?R S
??y(y∈ Y∧ <x,y>∈ R∧ <y,z>∈ S)
??y(y∈ Y∧ <z,y>∈ SC∧ <y,x>∈ RC)
?<z,x>?SC RC 所以 (R S)C= SC RC
8,R是 A上关系，则
⑴ R是对称的，当且仅当 RC =R
⑵ R是反对称的，当且仅当 R∩RC ?IA。
证明,⑴ 充分性，已知 RC =R (证出 R对称 )
任取 x,y?A 设 <x,y>?R,则 <y,x>?RC,而 RC =R
所以有 <y,x>?R,所以 R对称。
必要性，已知 R 对称,(证出 RC =R)
先证 RC?R,任取 <y,x>∈ RC,则 <x,y>?R,因 R对称
所以有 <y,x>∈ R，所以 RC?R。
再证 R? RC,任取 <x,y>?R,因 R对称，所以有
<y,x>∈ R，则 <x,y>∈ RC,所以 R?RC。
最后得 RC =R 。
证明⑵ 充分性，已知 R∩RC ?IA,(证出 R反对称 )
任取 x,y?A 设 <x,y>?R 且 <y,x>∈ R，
<x,y>?R∧ <y,x>∈ R?<x,y>?R∧ <x,y>∈ RC，
? <x,y>?R∩RC ? <x,y>? IA (因 R∩RC ?IA )
?x=y 所以 R反对称。
必要性，已知 R反 对称,(证出 R∩RC ?IA)
任取 <x,y>?R∩RC
<x,y>?R∩RC?<x,y>?R∧ <x,y>?RC
?<x,y>?R∧ <y,x>?R
?x=y (因 R反对称 )
?<x,y>?IA 所以 R∩RC ?IA 。
第 4-3和 4-4节的 要求,
熟练掌握求复合关系和逆关系的计算方法
及性质。
作业,第 118页⑴、⑵ a)b)、⑶、⑸
4-6 关系的闭包运算
关系的闭包是个很有用的概念，特别是传递闭
包。关系的闭包是通过关系的复合和求逆构成的
一个新的关系。这里要介绍关系的自反闭包、对
称闭包和传递闭包。
一,例子
给定 A中关系 R，如图所示，
分别求 A上另一个关系 R’，使
得它是包含 R的“最小的” (序偶
尽量少 )分别具有自反 (对称、传递 )性的关系。 这
个 R’就分别是 R的 自反 (对称、传递 )闭包。
1。
2。 。 3
这三个关系图分别是 R的 自反、对称、传递闭包。
二,定义,给定 A中关系 R,若 A上另一个关系 R’，
满足：⑴ R?R’；
⑵ R’是自反的 (对称的、传递的 )；
⑶ R’是,最小的,，即对于任何 A上自反 (对称、
传递 )的关系 R”,如果 R?R”,就有 R’?R”。
则称 R’是 R的 自反 (对称、传递 )闭包。记作 r(R)、
(s(R), t(R)) (reflexive,symmetric,transitive)
1。
2。 。 3
1。
2。 。 3
1。
2。 。 3
实际上 r(R),(s(R), t(R)) 就是包含 R的“最小”
的 自反 (对称、传递 )关系。
三,计算方法
定理 1.给定 A中关系 R,则 r(R)=R∪ IA。
证明：令 R’=R∪ IA,显然 R’是自反的和 R?R’，下
面证明 R’是“最小的”：如果有 A上自反关系
R”且 R?R”,又 IA?R”,所以 R∪ IA?R”,即 R’?R”。
所以 R’就是 R的自反闭包。即 r(R)=R∪ IA 。
定理 2.给定 A中关系 R,则 s(R)=R∪ RC 。
证明方法与 1.类似。
定理 3.给定 A中关系 R,则 t(R)=R∪ R2∪ R3∪,.,。
证明：令 R’= R∪ R2∪ R3∪,..,
⑴ 显然有 R?R’ ；
⑵证 R’是传递的：任取 x,y,z?A,设有 <x,y>?R’
<y,z>?R’,由 R’定义得必存在整数 i,j使得
<x,y>?Ri,<y,z>?Rj,根据关系的复合得
<x,z>?Ri+j,又因 Ri+j ?R’,所以 <x,z>?R’,∴ R’传递 。
⑶ 证 R’是“最小的”：如果有 A上传递关系 R”且
R?R”,（ 证出 R’?R”）任取 <x,y>?R’,则由 R’定义
得必存在整数 i,使得 <x,y>?Ri,根据关系的复合得
A中必存在 i-1个元素 e1,e2,...,ei-1,使得 (见 49页 )
<x,e1>?R∧ <e1,e2>?R∧,..∧ <ei-1,y>?R。因 R?R”,
∴ 有 <x,e1>?R”∧ <e1,e2>?R”∧,..∧ <ei-1,y>?R”。
由于 R”传递，所以有 <x,y>?R”。 ∴ R’?R”。
综上所述,R’就是 R的传递闭包，即
t(R)=R∪ R2∪ R3∪ …= ∪ Rii=1∞
用上述 公式计算 t(R),要计算 R的无穷大次幂,好
象无法实现似的。其实则不然，请看下例,
A={1,2,3} A中关系 R1,R2,R3,如下：
R1={<1,2>,<1.3>,<3,2>}
R2 ={<1,2>,<2.3>,<3,1>}
R3 ={<1,2>,<2.3>,<3,3>}
={<1,2>} = =Φ 所以
t(R1)= ∪ ∪ = R1
={<1,3>,<2,1>,<3,2>} ={<1,1>,<2,2>,<3,3>}
=IA,= R2,..
t(R2)= R2∪ ∪
={<1,3>,<2,3>,<3,3>} =
t(R3)= R2∪
2R
1
3R
1
4R
1
1R
1
2R
1
3R
1
2R
2
3R
2
4R
2
3R
2
2R
2
3R
2
3R
3
2R
3
2R
3
2R
3
定理 4.给定 A中关系 R,如果 A是有限集合,|A|=n
则 t(R)=R∪ R2∪,..∪ Rn 。
证明：令 R’=R∪ R2∪ R3∪,..,R”=R∪ R2∪,..∪ Rn
下面证明 R’=R”,
显然有 R”?R’。下面证明 R’?R”：
任取 <x,y>?R’,由 R’定义得必存在 最小的 正整数 i 使
得 <x,y>?Ri,(下面证明 i≤n)如果 i＞ n,
根据关系的复合得 A中必存在 i-1个元素 e1,e2,...,ei-1，
使得 <x,e1>?R∧ <e1,e2>?R∧,..∧ <ei-1,y>?R。
上述元素序列, x=e0,e1,e2,...,ei-1,y=ei中共有 i+1个元
素,i+1>n,而 A 中只有 n个元素，所以上述元素中
至少有两个相同，设 ej=ek (j<k),于是 R的关系图中
会有下面这些边：
从此图中删去回路中 k-j(k-j≥1)条边后得
<x,y>∈ Ri-(k-j),i-(k-j)<i,与 i是 最小的 矛盾。
所以 i≤n,所以 <x,y>∈ R”,于是 R’?R”。
最后得 R’=R”，所以
t(R)=R∪ R2∪,..∪ Rn 定理证毕。
。
。 。 。 。 。 。 。x e
1 ej-1 ej =ek
ej+1。
。
。
。
。
ej+2
ek-1
ek-2
ek+1 ek+2…..,…..,ei-1 y
求 t(R)的矩阵 Warshall算法,|X|=n,R?X× X,
令 MR=A R2的矩阵为 A2,… R k的矩阵为 Ak,于是
t(R)的 矩阵记作 MR+=A+A2+…+A k +… (+是逻辑加 )
⑴ 置新矩阵 A,=MR ;
⑵ 置 i=1;
⑶ 对所有 j,如果 A[j,i] =1,则对 k=1,2,…,n
A[j,k]:=A[j,k]+A[i,k]; /*第 j行 +第 i行,送回第 j行 */
⑷ i加 1;
⑸ 如果 i≤n,则转到步骤 ⑶，否则停止。
下面举例，令 X={1,2,3,4},
X中关系 R图如右图所示。
运行该算法 求 t(R)的矩阵,
1。
2。
。
。
4
3
i=1 (i---列,j---行 )
A[4,1]=1
1行 +4行 →4 行
i=2 A[1,2]=1,1行 +2行 →1 行
A[2,2]=1,2行 +2行 →2 行 A不变
A[4,2]=1,4行 +2行 →4 行,4行全 1,A不变
i=3 A[1,3]=1,1行 +3行 →1 行,3行全 0,A不变
A[2,3]=1,2行 +3行 →2 行,3行全 0,A不变
A[4,3]=1,4行 +3行 →4 行,3行全 0,A不变
i=4 A[1,4]=1,1行 +4行 →1 行
A[4,4]=1,4行 +4行 →4 行 A不变,
最后 A=Mt(R)
?
?
?
?
?
?
?
?
?
?
?
?
1101
0000
0110
1010
A=MR= A=
?
?
?
?
?
?
?
?
?
?
?
?
1111
0000
0110
1010
A的初值,
A=
?
?
?
?
?
?
?
?
?
?
?
?
1111
0000
0110
1110
A=
?
?
?
?
?
?
?
?
?
?
?
?
1111
0000
0110
1111
四,性质
定理 5,R是 A上关系，则
⑴ R是自反的，当且仅当 r(R)=R.
⑵ R是对称的，当且仅当 s(R)=R.
⑶ R是传递的，当且仅当 t(R)=R.
证明略，因为由闭包定义即可得。
定理 6,R是 A上关系，则
⑴ R是自反的，则 s(R)和 t(R)也自反。
⑵ R是对称的，则 r(R)和 t(R)也对称。
⑶ R是传递的，则 r(R)也传递。
证明, ⑴ 因为 R自反,由定理 5得 r(R)=R,即
R∪ IA=R,r(s(R))=s(R)∪ IA=(R∪ RC)∪ IA
= (R∪ IA)∪ RC=r(R)∪ RC =R∪ RC =s(R)∴ s(R)自反
类似可以证明 t(R)也自反。
证明 ⑵, 证明 t(R)对称,
(t(R))C=(R∪ R2∪,..∪ Rn∪,..)C
= RC∪ (R2)C ∪,..∪ (Rn)C∪,..
= RC∪ (RC)2 ∪,..∪ (RC)n∪,.,
=R∪ R2∪,..∪ Rn∪,.,(∵ R对称,∴ RC =R)
=t(R) 所以 t(R)也对称。
类似可以证明 r(R)也对称。
证明 ⑶, 证明 r(R)传递,先用归纳法证明下面结论,
(R∪ IA)i= IA∪ R∪ R2∪,..∪ Ri
① i=1时 R∪ IA= IA∪ R 结论成立。
②假设 i≤k 时结论成立，即
(R∪ IA)k= IA∪ R∪ R2∪,..∪ Rk
(R2)c=(R R)c
=Rc Rc
=(Rc)2
③ 当 i=k+1时
(R∪ IA)k+1=(R∪ IA)k (R∪ IA)
= (IA∪ R∪ R2∪,..∪ Rk） (IA∪ R)
= (IA∪ R∪ R2∪,..∪ Rk)∪ (R∪ R2∪,..∪ Rk+1)
= IA∪ R∪ R2∪,..∪ Rk∪ Rk+1
所以结论成立,
t(r(R))=t(R∪ IA)
= (R∪ IA)∪ (R∪ IA)2∪ (R∪ IA)3∪,..
=(IA∪ R)∪ (IA∪ R∪ R2)∪ (IA∪ R∪ R2∪ R3)∪,..
= IA∪ R∪ R2∪ R3∪,..= IA∪ t(R)
= IA∪ R (R传递 t(R)=R)
=r(R) 所以 r(R)也传递。
。
。
定理 7：设 R1,R2是 A上关系，如果 R1?R2,则
⑴ r(R1)? r(R2) ⑵ s(R1)? s(R2) ⑶ t(R1)?t(R2)
证明⑴ r(R1)=IA∪ R1?IA∪ R2= r(R2)
⑵,⑶类似可证。
定理 8：设 R是 A上关系，则
⑴ sr(R)=rs(R) ⑵ tr(R)=rt(R) ⑶ st(R)?ts(R)
证明,⑴ sr(R)=r(R)∪ (r(R)c=(R∪ IA)∪ (R∪ IA)c
= (R∪ IA)∪ (Rc∪ IAc) =R∪ IA∪ Rc∪ IA
= (R∪ Rc)∪ IA= s(R)∪ IA=rs(R)
⑵ 的证明用前边证明的结论：
(R∪ IA)k= IA∪ R∪ R2∪,..∪ Rk
很容易证明，这里从略。
⑶ 因 R?s(R) 由定理 7得 t(R)?ts(R) st(R)?sts(R)
因 s(R)对称，有定理 6得 ts(R) 也对称，由定理 5得
sts(R)=ts(R) 所以有 st(R)?ts(R) 。 证明完毕。
通常将 t(R) 记成 R+,tr(R)记成 R*,即
t(R)= R+=R∪ R2∪,..∪ Rn∪ …=
tr(R)=rt(R) =R*= R0∪ R∪ R2∪,..∪ Rn∪ …=
练习,给定 A中关系 R
如图所示：分别画出 r(R)、
s(R), t(R),sr(R),rs(R)、
tr(R),rt(R),st(R), ts(R)
的图。
1。
2。
。
。
4
3
∪ Rii=1∞
∪ Rii=0∞
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
1。
2。
。
。
4
3
r(R) s(R) t(R)
sr(R)
rs(R)
tr(R)
rt(R)
st(R)
ts(R)
本节重点掌握闭包的定义、计算方法和性
质。
作业 第 127页 ⑴、⑸、⑺、⑻
4-7 集合的划分与覆盖
图书馆的图书，要分成许多类存放，学校的学生
要按照专业分成许多班,… 即对集合的元素划分
一,定义 设 X是一个非空集合,A={A1,A2,...,An},
Ai?Φ Ai?X (i=1,2,...,n),如果满足
A1∪ A2∪,..∪ An =X (i=1,2,...,n)
则称 A为集合 X的 覆盖 。
设 A={A1,A2,...,An}是 X一个覆盖,且 Ai?Aj=Φ
(i?j,1≤i,j≤n)则称 A是 X的 划分。 每个 Ai均称为这
个划分的一个划分 (类 )。
例 X={1,2,3},A1={{1,2,3}},A2={{1},{2},{3}},
A3={{1,2},{3}},A4={{1,2},{2,3}},A5={{1},{3}}
A1,A2,A3,A4 是覆盖。 A1,A2,A3也是划分。
划分,一定是覆盖；但覆盖,不一定是划分 。
二,最小划分与最大划分
最小划分,划分块最少的划分。即只有一个划分
块的划分，这个划分块就是 X本身。如 A1 。
最大划分,划分块最多的划分。即每个划分块里
只有一个元素的划分。如 A2 。
A1,A2,A3是一种划分,其中 A1是最小划分,A2是最
大划分。
三,交叉划分
例 X是东大学生集合,A和 B都是 X的划分：
A={M,W},M?X,W?X,M={男生 },W={女生 }
B={L,N},L?X,N?X,L={辽宁人 },N={非 辽宁人 }
C={L∩M,L∩W,N∩M,N∩W }
称 C是 X的交叉划分。
M W
L
N
L∩M L∩W
N∩M N∩W
辽宁男生 辽宁女生 非辽宁男生 非辽宁女生
定义,若 A={A1,A2,...,Am}与 B={B1,B2,...,Bn}都是集合 X
的划分,则其中所有的 Ai?Bj,组成的集合 C,称为 C是 A与
B两种划分的交叉划分, (此定理的证明不讲 )
证明,{ A1,A2,...,Am}与 {B1,B2,...,Bn}的交叉划分是
C={A1?B1,A1?B2,...,A1?Bn,
A2?B1,A2?B2,...,A2?Bn,...,
Am?B1,Am?B2,...,Am?Bn}
在 C中任取元素,Ai?Bh?X (∵ Ai?X,Bj?X)
(A1?B1)∪ (A1?B2)∪,..∪ (A1?Bs)∪ (A2?B1)∪ …
∪ (A2?Bs)∪,.,∪ (Ar?B1)∪ (Ar?B2)∪,..∪ (Ar?Bs)
=(A1?( B1∪ B2∪ B3∪,..Bs))∪
(A2?( B1∪ B2∪ B3∪,.,∪ Bs))∪,.,∪
(Ar?( B1∪ B2∪ B3∪,.,∪ Bs))
= (A1∪ A2∪ A3∪,..∪ Ar) ?( B1∪ B2∪ B3∪,.,∪ Bs)
=X?X=X
再验证 C中任意两个元素不相交：
在 C中任取两个不同元素 Ai?Bh和 Aj?Bk,考察
(Ai?Bh) ? (Aj?Bk) (i=j和 h=k不同时成立 )
= (Ai?Aj)?(Bh?Bk)
i＝ j,h≠k (Ai?Aj)?(Bh?Bk) =Ai??=?
i≠j,h≠k (Ai?Aj)?(Bh?Bk)=???=?
i≠j,h=k (Ai?Aj)?(Bh?Bk)=?? Bh =?
综上所述,C是 X的划分。
作业,第 130页 (1)
4-8 等价关系与等价类
等价关系是很重要的关系，它是我们遇到最多的
关系，例如，数值相等关系 =、命题间的等价关
系 ?、三角形相似 ∽ 和全等关系 ≌, …..
一,等价关系
1.定义,设 R是 A上关系,若 R是自反的、对称的和
传递的，则称 R是 A中的等价关系。若
a,b?A，且 aRb，则称 a与 b等价。
例子，集合 A={1,2,3,4,5,6,7},R是 A上的模 3同
余关系，即
R={<x,y>|x-y可被 3整除 (或 x/3与 y/3的 余数相同 )}
即 <x,y>∈ R? x(mod 3)=y(mod3)
例如 4(mod 3)=7(mod3) 3(mod 3)=6(mod3)
R={<1,1>,<1,4>,<1,7>,<2,2>,<2,5>,<3,3>,<3,6>,<4,1>,
<4,4>,<4,7>,<5,2>,<6,3>,<6,6>,<7,1>,<7,4>,<7,7>}
2.等价关系的有向图
1)完全关系 (全域关系 A× A)图，下面分别是当 A中只有
1,2,3个元素时的完全关系图。
1。
2。
1。
2。 3。1。
A={1} A={1,2} A={1,2,3}
2.等价关系的有向图,
上边 的模 3同余关系
R的图：
从关系图可看
出,R是自反、
对称、传递的
关系，所以 R是等价关系。
等价关系 R的有向图可能由若干个独立子图 (R图的一部
分 )构成的，每个独立子图都是完全关系图 。
上述关系 R图就是由三个独立的完全图构成的。
下面给出八个关系如图所示，根据等价关系有向图的
特点，判断哪些是等价关系，
2。
5。
1。
4。 7。
3。
6。
A={1,2,3}下面是 A中关系：
1。
2。 。
1。
2。 。 33
1。
2。 。
1。
2。 。
1。
2。 。
1。
2。 。 33 33
R2R1
R5 R6
1。
2。 。
1。
2。 。 33
R3 R4
R7 R8
思考题, A={1,2,3},可构造多少个 A中不同的等价
关系？可以根据等价关系有向图的特点来考虑。
如果等价关系 R中有
a)三个独立子图的情形，则 ( )个等价关系 。
b)二个独立子图的情形，则 ( )个等价关系 。
c)一个独立子图的情形，则 ( )个等价关系 。
一共有 ( )个 中不同的等价关系。
二, 等价类
我们经常用等价关系对集合进行划分，得到的划分块
称之为等价类。
1.定义, R是 A上的等价关系,a∈A,由 a确定的集合 [a]R:
[a]R={x|x∈A∧<a,x>∈R}
称集合 [a]R为由 a形成的 R等价类。简称 a等价类。
可见 x∈[a] R ?<a,x>∈ R
上例,A={1,2,3,4,5,6,7},R是 A上的模 3同余关系，
[1]R={1,4,7}= [4]R = [7]R ----余数为 1的等价类
[2]R={2,5}= [5]R ----余数为 2的等价类
[3]R={3,6}= [6]R ----余数为 0的等价类
思考题,此例为什么只有三个等价类？
2,由等价关系图求等价类, R图中每个独立子图上的结点，
构成一个等价类。不同的等价类个数 =独立子图个数。
上述三个等价关系各有几个等价类？说出对应的
各个等价类。
1。
2。 。 3
R2
1。
2。 。 3
R1
。
R3
。
。1
2 3
从上述模 3同余关系例子中，可以归纳出等价类的性质：任
何两个等价类要么相等，要么不相交；那么在什么情况下相
等？那么在什么情况下不相交？
3.等价类性质
R是 A上等价关系，任意 a,b,c∈ A
⑴ 同一个等价类中的元素，彼此有等价关系 R。
即任意 x,y∈ [a]R,必有 <x,y>∈ R
证明,任取 x,y∈ [a]R，由等价类定义得,<a,x>∈ R,
<a,y>∈ R,由 R对称得,<x,a>∈ R,又由 R传递得 <x,y>∈ R。
⑵ [a]R∩[b]R=Φ,当且 仅当 <a,b>?R。
证明,设 <a,b>?R,假设 [a]R∩[b]R≠Φ,则存在 x∈ [a]R∩[b]R，
∴ x∈ [a]R∧ x∈ [b]R,∴ <a,x>∈ R,<b,x>∈ R,由 R对称得
<x,b>∈ R又由 R传递得 <a,b>∈ R,产生矛盾。
若 [a]R∩[b]R=Φ,而 <a,b>∈ R,由等价类定义得 b∈ [a]R,
又因为 bRb,所以 b∈ [b]R,所以 b∈ [a]R∩[b]R，产生矛盾。
⑶ [a]R=[b]R 当且 仅当 <a,b>∈ R。
证明：若 <a,b>∈ R，则任何 x∈ [a]R,有 <a,x>∈R, 由对
称性得 <b,a>∈R, 再由传递性得 <b,x>∈R,∴x∈ [b]R，
所以 [a]R?[b]R。 类似可证 [b]R?[a]R。 ∴ [a]R=[b]R。
如果 [a]R=[b]R，由于有 aRa,所以 a∈ [a]R, a∈ [b]R,
所以有 <b,a>∈ R,由对称性得 <a,b>∈R.
⑷,A中任何元素 a,a必属于且仅属于一个等价类。
证明,A中任何元素 a,由于有 aRa,所以 a∈ [a]R, 如果
a∈ [b]R, 所以有 <a,b>∈ R.由性质⑶得 [a]R=[b]R 。
⑸,任意两个等价类 [a]R,[b]R，
要么 [a]R=[b]R,要么 [a]R∩[b]R=Φ。
(因为要么 <a,b>∈ R,要么 <a,b>?R。 )
⑹ R的所有等价类构成的集合是 A的一个划分。
(由性质⑷⑸即得。 ) (这个划分称之为 商集 )
三, 商集
商”和除法有关，比如把 一块蛋糕 平均分成四份，从
两种不同的角度看这件事：
从算术角度看, 1用 4除,每份 1/4,这就是“商”,于是,
1=1/4+1/4+1/4+1/4
从集合角度看,
集合 A用模 3同余关系 R划分，得到三个等价类，所以
A {{1,4,7},{2,5},{3,6}}={[1]R,[2]R,[3]R}----商集
定义, R是 A上等价关系，由 R的所有等价类构成的集合
称之为 A关于 R的商集。记作 A/R。即
A/R={[a]R |a∈ A}
用刀分 }{
用 R分
生 日 日
快 快乐 乐 生
例如 A={1,2,3,4,5,6,7},R上模 3同余关系，则
A/R= {[1]R,[2]R,[3]R} ={{1.4.7},{2,5},{3,6}}
练习 X={1,2,3},X上关系 R1,R2, R3,如上图所示。
X/R1={[1]R1,[2]R1,[3]R1}={{1},{2},{3}}
X/R2={[1]R2,[2]R2}={{1},{2,3}}
X/R1={[1]R3}={{1,2,3}}
1。
2。 。 3
R2
1。
2。 。 3
R1
。
R3
。
。1
2 3
定理, 集合 A上的等价关系 R，决定了 A的一个划分，该划
分就是商集 A/R.
证明：由等价类性质可得,
1) A/R中任意元素 [a]R，有 [a]R?A,
2) 设 [a]R,[b]R是 A/R的两个不同元素，有 [a]R?[b]R=Φ
3) 因为 A中每个元素都属于一个等价类，所以所有等
价类的并集必等于 A。
所以商集 A/R是 A的一个划分。
定理,设 R1和 R2是非空集合 A上的等价关系，则
A/R1=A/R2 当且仅当 R1=R2 。
(这个定理显然成立。 )
四, 由划分确定等价关系
例如,X={1,2,3,4},
A={{1,2},{3},{4}},A是 X
的一个划分，求 X上一个
等价关系 R,使得 X/R=A。
显然 R的图如右图所示：
R={1,2}2∪ {3}2∪ {4}2 。
一般地 A={A1,A2,…,A n}是 X的一个划分，则构造一个 X中
的等价关系 R,使得 X/R=A。
R= A1∪ A2∪,…,∪ An 其中 Ai= Ai× Ai，
下面证明 R是 X中的等价关系。
等价关系 集合的划分
A/R
？
2。
1。 3。
4。
2 2 2 2
定理, 集合 X的一个划分可以确定 X上 的一个等价关系。
证明：假设 A={A1,A2,...,An}是 X的一个划分，如下构造
X 上 的一个等价关系 R,
R= A1∪ A2∪,…,∪ An 其中 Ai = Ai× Ai,(i=1,2…n).
1) 证 R自反,任取 a∈ X,因为 A是 X的划分，必存在
Ai?A使 x?Ai,于是 <a,a>∈ Ai× Ai,又 Ai× Ai ?R∴ 有 aRa。
2) 证 R对称, 任取 a,b∈ X,设 aRb,必存在 Ai?A使得
<a,b>∈ Ai× Ai,于是 a,b?Ai,?bRa,R是对称的。
3) 证 R传递, 任取 a,b,c∈ X,设 aRb,bRc,必存在 Ai?A使
得 <a,b>∈ Ai× Ai,<b,c>∈ Ai× Ai,
(不可能有另一个划分块 Ak?A使得 <b,c>∈ Ak× Ak,因为
如果这样，就使得,既 b∈ Ai又 b?Ak,与 A是划分矛盾。 )
于是 a,b,c?Ai,所以 <a,c>∈ Ai× Ai, 又 Ai× Ai ?R∴ 有 aRc
所以 R传递。 最后得 R是集合 X中的关系。
2 2 2 2
本节重点：
等价关系概念、证明。
等价类概念、性质。
求商集。
作业,第 134页
⑴、⑵、⑷、⑹、⑺
4-9 相容关系
相容关系是另一种常见关系,如朋友关
系、同学关系等。
这些关系的共性是自反的、对称的。
一,定义,给定集合 X上的关系 r,若 r是自反的、
对称的,则 r是 A上 相容关系。
例子,X 是由一些英文单词构成的集合。
X={fly,any,able,key,book,pump,fit},X上关系 r:
r={<α,β>|α∈ X,β∈ X且 α与 β含有相同字母 }
r的有向图：
看出有自反、
对称性。而
不传递。
any。
。 ablefly。
key。
。 book
pump。
fit。
y
b
k
l
y
f y
二, 简化图和简化矩阵
图的简化,⑴不画环；
⑵两条对称边用一条无向直线代替。
令 x1=fly,x2= any,x3= able,x4=key,x5=book,x6= pump,
x7= fit,X={x1,x2,x3,x4,x5,x6,x7},r的简化图为：
矩阵的简化,因为 r的矩阵是对称阵且主对角线全是 1，
用下三角矩阵 (不含主对角线 )代替 r的矩阵。如上图所示。
x2。
x1。 。 x3
x4。
x5。
x6。
x7。
x1 x2 x3 x4 x5 x6
x7
x6
x5
x4
x3
x2 1
1
1
1
1
11
1 1
0
0 0
0 0 0 0
0 0 0
0
0
三,相容类及最大相容类
在等价关系中讨论了等价类，这里要讨论相容类。
定义, 设 r是集合 X上的相容关系,C?X,如果对于 C中任
意两个元素 x,y有 <x,y>∈ r,称 C是 r的一个 相容类 。
上例中 {x1,x2},{x3,x4},{x1,x2,x3},{x2,x3,x4},{x1,x2,x4},
{x3,x4,x5},{x1,x3,x4},{x1,x2,x3,x4},{x1,x7},{x6} 都是相容类。
上述相容类中，有些相容类间有真包含关系。
下面定义最大相容类。
定义, 设 r是集合 X上的相容关系,C是 r的一个相容类，
如果 C不能被其它 相容类所真包含，则称 C是一个 最大
相容类。
也可以说,C是一个相容类,如果 C中加入任意一个新
元素，就不再是相容类,C就是一个 最大相容类。
{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}都是 最大相容类。
从简化图找最大相容类, ------找最大完全多边形。
最大完全多边形,含有结点最多的多边形中，每个结点
都与其它结点相联结。
一个孤立顶点 --------完全 0边形；
两个结点间有连线 (非三角形中的一边 ) ---完全 1边形；
三角形 ------完全 3边形；完全 4边形,… 如下图所示：
在相容关系简化图中,每个最大完全多边形的结点集合
构成一个最大相容类。
上例中最大相容类 {x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}
分别对应最大完全四、三、一、零边形。
。 。 。x
1。 。 。
。 。 。 。
给定 X上相容关系 r’,如图所示,
r’的最大相容类,{x1,x2,x5},
{x2,x3,x5},{x3,x4,x5},
{x1,x4,x5},
四, 完全覆盖,
定义,r是中的相容关系，由 r的所有 最大相容类为元素
构成的集合，称之为 X的完全覆盖。记作 Cr(X)。
Cr(X)={{x1,x2,x3,x4},{x3,x4,x5},{x1,x7},{x6}}
Cr’(X)={{x1,x2,x5},{x2,x3,x5},{x3,x4,x5},{x1,x4,x5}}
本节要求,相容关系、相容类概念，画图，求完全覆盖。
作业 第 139页 (2)
x2。 x3 。
x1。 x4。
x5。
4-10 次序关系
次序关系也是常遇到的重要关系，例如：
数值的 ≤、＜,≥、＞关系；
集合的 ?,?关系；
图书馆的图书按书名的字母次序排序；
词典中的字 (词 )的排序；
计算机中文件按文件名排序；
程序按语句次序执行； …….
本节讨论几种次序关系。
一, 偏序关系 (partial order relation)
1,定义, R是 A上自反、反对称和传递的关系，则称 R
是 A上的偏序关系。并称 <A,R>是偏序集。
例如数值的 ≤,≥关系和集合的 ?都是偏序关系。
因为数值 ≤是熟知的偏序关系，所以用符号,≤”表
示任意偏序关系，但要 注意 !!“≤”不一定是“小于或等
于”的含义 。
例 1 A={1,2,4,6},≤是 A中的整
除关系，其关系图如右图，显然
≤是自反、反对称和传递的，即
它是个偏序。
2,x与 y是可比较的, <A,≤>是偏序集,x,y∈ A,如果要
么 x≤y,要么 y≤x,则称 x与 y是可比较的。
上例中 1,2,4或 1,2,6间是可比较的。而 4与 6间是不可比较的
2。
1。
。
6
4
二,全序 (线序、链 )
定义, <A,≤>是偏序集，任何 x,y∈ A,如果 x与 y都是可比
较的，则称 ≤是全序关系 (线序、链 )。
例 2 B={1,2,4,8},≤表示整除关系，
则 ≤是全序关系，如图：
全序关系一定是偏序关系，但是偏序不一定是全序。
偏序关系的有向图，不能直观地反映出元素之间的次序，
所以下面介绍另外一种图 ---Hasse图。通过这个图，就能
够清晰地反映出元素间的层次。
下面介绍 Hasse图。
2。
1。
。
8
4
三,偏序集的哈斯图 (Hasse图 )
<A,≤>是偏序集,x,y∈ Ａ
1.元素 y盖住元素 x：如果 x≤y,且 x≠y,且不存在 z∈ A,使
得 z≠x∧ z≠y∧ x≤z∧ z≤y,则称 元素 y盖住元素 x。
元素 y盖住 x?x≤y∧ x≠y∧ ??z(z∈ A∧ z≠x∧ z≠y∧ x≤z∧ z≤y)
即元素 y盖住元素 x?不存在 z∈ A,使得 z介于 x与 y之间。
上例中 4没有盖住 1，因为中间有个 2,1≤2≤4.
2.偏序集 Hasse图的画法, 令 <A,≤>是偏序集，
1.用,”表示 A中元素。
2.如果 x≤y,且 x≠y,则结点 y要画在结点 x的上方。
3,如果 x≤y,且 y盖住 x,x与 y之间连一直线。
4,一般先从最下层结点 (全是射出的边与之相连 (不考虑
环 ))，逐层向上画，直到最上层结点 (全是射入的边与之
相连 )。 (采用抓两头，带中间的方法 )
。
例如，前边两个例子：
它们的Ｈ asse图分别如下：
可见右图，是全序，它的Ｈ asse图是一条直线，所以
全序 也叫 线序,或 链 。是从它的 Hasse图得名。
下面作 练习,教材第 146页 (7)
2。
1。
。
6
4 2。
1。
。
8
4
１ 。
２ 。
４ 。６ 。
１ 。
２ 。
４ 。
８ 。
4。
1。
3。2。
3。
4。
1。
2。
１ 。 ２ 。
４ 。3。
4。
２ 。
1。
3。
全序
练习：
C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}
≤ 是 C,D上 整除关系, <Ｃ,≤>,<Ｄ,≤>的 Hasse图：
以及 A={a,b,c} <P(A),?>的 Hasse图：
练习：
C={1,2,3,6,12,24,36},D={1,2,3,5,6,10,15,30}
≤ 是 C,D上 整除关系, <Ｃ,≤>,<Ｄ,≤>的 Hasse图：
以及 A={a,b,c} <P(A),?>的 Hasse图：
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。 30。
3。
１ 。
2。 5。
１ 0。 １ 5。6。
{a,b,c}。
{b}。
Φ。
{a}。 {c}。
{a,c}。 {b,c}。{a,b}。
<C,≤> <D,≤> <P(A),? >
四,偏序集中的重要元素
在格和布尔代数中，要用到下面一些术语。
设 <A,≤>是偏序集,B是 A的非空子集。
一,极小元与极大元
y是 B的 极小元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ x≤y))
(在 B中没有比 y更小的元素了,y就是 极小元 )
y是 B的 极大元 ??y(y∈ B∧ ??x(x∈ B∧ x≠y∧ y≤x))
(在 B中没有比 y更大的元素了,y就是 极大元 )
举例,给定 <A,≤>的 Hasse图如图所示：
从 Hasse图找
极小 (大 )元：子集
中处在最下 (上 )层
的元素是极小 (大 )
元。
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。
子集 B 极小元 极大元
{2,3}
{1,2,3}
{6,12,24}
C
2,3 2,3
1 2,3
6 24
1 24,36
二,最小元与最大元
y是 B的 最小元 ??y(y∈ B∧ ?x(x∈ B?y≤x))
(最小元 y是 B中元素，该元素比 B中所有元素都小 )
y是 B的 最大元 ??y(y∈ B∧ ?x(x∈ B?x≤y))
(最大元 y是 B中元素，该元素比 B中 所有元素都大 )
举例,给定 <A,≤>的 Hasse图如图所示：
从 Hasse图找 最小 (大 )元：子集中如果只有唯一的极
小 (大 )元，则这个
极小 (大 )元，就是
最小 (大 )元。否则
就没有最小 (大 )元。
下面介绍 最小 (大 )元的唯一定理。
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。子集 B 最小元 最大元
{2,3}
{1,2,3}
{6,12,24}
C
无 无
1 无
6 24
1 无
定理, <A,≤>是偏序集,B是 A的非空子集，如果 B有
最小元 (最大元 )，则最小元 (最大元 )是唯一的。
证明,假设 B有两个最小元 a,b,则
因为 a是 最小元,b∈ B，根据 最小元定义，有 a≤b;
类似地，因为 b是 最小元,a∈ B，根据 最小元定义，有
b≤a。因为 ≤有反对称性，所以有 a=b。
同理可证 最大元的唯一性。
小结, <A,≤>是偏序集,B是 A的非空子集，则
⑴ B的 极小 (大 )元总是存在的，就是子集中处在最下 (上 )
层的元素是极小 (大 )元。
⑵ B的 最小元 (最大元 )有时可能不存在，只有有唯一的极
小 (大 )元，则这个极小 (大 )元就是最小 (大 )元。否则就没
有最小 (大 )元。
3.上界与下界 (Upper Bound and Lower Bound)
y是 B的 上界 ??y(y∈ A∧ ?x(x∈ B?x≤y))
(上界 y是 A中元素，该元素比 B中所有元素都大 )
y是 B的 下界 ??y(y∈ A∧ ?x(x∈ B?y≤x))
(下界 y是 A中元素，该元素比 B中 所有元素都小 )
举例,给定 <A,≤>的 Hasse图如图所示：
从 Hasse图找 上 (下 )界,注意 是在 A中找！
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。
子集 B 上界 下界
{2,3}
{1,2,3}
{6,12,24}
C
1
6,12,24,36 1
24 6,2,3,1
1无
6,12,24,36
4,最小上界 (上确界 )和最大下界 (下确界 )
(Least Upper Bound and Greatest Lower Bound)
定义,y是 B的上界，并且对 B的所有上界 x,都有 y≤x,则
称 y是 B的 最小上界 (上确界 )，记作 LUB B=y 。
(即 y是上界中最小的。如果 B有上确界，则是唯一的 )
y是 B的下界，并且对 B的所有下界 x,都有 x≤y,则
称 y是 B的 最大下界 (下确界 )，记作 GLB B=y 。
(即 y是下界中最大的。如果 B有上确界，则是唯一的 )
举例,给定 <A,≤>的 Hasse图如图所示：
６ 。
１ 。 ３ 。
12。
２ 。
24。 36。
子集 B 上界 下界
{2,3}
{1,2,3}
{6,12,24}
C
1
6,12,24,36 1
24 1,2,3,6
1无
6,12,24,36
上确界 下确界
6
6
24
无
1
1
6
1
* 五,良序
定义, <A,≤>是偏序集，如果对 A的任何非空子集 B,都
有最小元，则称 ≤是 A上的良序，并称 <A,≤>为良序集。
例如 N是自然数集合,I是整数集合,≤是小于或等于
关系,<N,≤>就是 良序集。而 <I,≤>不是良序集。
定理,所有 良序集，一定是全序集。
证明,设 <A,≤>为良序集,任取 x,y∈ A,构成子集 {x,y},它
有最小元，该最小元或是 x,或是 y,于是有 x≤y或 y≤x,所
以 <A,≤>是全序集。
定理, 有限的 全序集，一定是良序集。
证明：设 A={a1,a2,…a n},<A,≤>是全序集，假设它不是良
序，必存在非空子集 B?A,B中无最小元，因 B是有限集，
必存在 x,y∈ B,使得 x y,与 ≤是全序矛盾,∴ <A,≤>是良
序集。
≤
本节要求：
掌握偏序,全序的概念，
会画 Hasse图，
会求重要元素。
作业 第 145页 (1),(6),(7)
本章小结 枚举法
有向图
矩阵
*等价关系 有向
图
等
价
类
商
集
划
分
偏序关系
相
容
类
最
大
相
容
类
完
全
覆
盖
简
化
图
全
序
哈
斯
图
重
要
元
素
计算方法
运算性质
二
元
关
系
概念及表示方法
性
质*
自反
对称
传递
反对称
反自反
相容关系
运
算
复合
求逆
闭包
谓词
*
*
第四章 习题课
第 104页⑴ b) A={0,1} B={1,2} 求 A2× B。
A?B={<x,y>|x?A∧ y?B}
A2 =A× A={<0,0>,<0,1>,<1,0>,<1,1> }
A2× B={<<0,0>,1>,<<0,1>,1>,<<1,0>,1>,<<1,1>,1>,
<<0,0>,2>,<<0,1>,2>,<<1,0>,2>,<<1,1>,2> }
第 109页⑴ X={a,b,c} Y={s} X到 Y的所有关系：
X× Y={<a,s>,<b,s>,<c,s>}
X× Y的任何一个子集都是一个 从 X到 Y的关系。如果
|X|=m |Y|=n则有 2mn个从 X到 Y的关系,故,有 23=8个关系,
R0=Φ
R1={<a,s>} R2={<b,s>} R3={<c,s>}
R4={<a,s>,<b,s>} R5={<a,s>,<c,s>} R6={<b,s>,<c,s>}
R7={<a,s>,<b,s>,<c,s>}
⑵ 设 |A|=n, 有多少个 A上的关系？
因为 R?A× A,所以 A× A有多少个子集就有多少个 A上关
系,由集合的幂集就是该集合的子集构成的,所以 A上关系
个数就是 A× A 的幂集 P(A× A)的元素个数 |P(A× A)|,
而 2|A× A|=2nn= 。所以有 个不同的 A上关系。
第 113页⑴ A={1,2,3},A上五个关系如下,(T略有改动 )
2n2
。。
。
1
32 。。
。
1
32 。。
。
1
32 。。
。
1
32 。。
。
1
32
R S T Φ A× A
R
A× A
Φ
T
S
自反 反自反 对称 反对称 传递
N N N Y Y
Y N Y N YY N N Y Y
N Y Y Y Y
Y N Y N Y
2n2
上述五个关系中，
哪些是等价关系？如果是等价关系，求其商集。
哪些是相容关系？如果是相容关系，求其完全覆盖。
哪些是偏序关系？如是偏序关系,画 Hasse图,并求Ａ的极
小 (大 )元、最小 (大 )元、上界与下界、上确界和下确界。
等价关系, S和 A× A，对应的商集分别是：
A/S={{1,2},{3}} A/A× A={{1,2,3}}
相容关系, S和 A× A，对应的完全覆盖分别是：
CS(A)={{1,2},{3}} CA× A(A)={{1,2,3}}
偏序关系, T
Ａ的极小元、最小元、下界、下确界都是,1
Ａ的极大元、最大元、上界、上确界都是,3 1。
2。
3。
第 118页⑴ R和 S都是 A上关系，
a) R和 S都自反,一定自反。
因为任取 a∈ A,由于 R和 S都自反,所以 <a,a>∈ R 及
<a,a>∈ S 故 <a,a>∈ ∴ 自反，
b) R和 S都反自反,不一定反自反。举反例：
c) R和 S都对称,不一定对称。
d) R和 S都传递,不一定传递。
R So
R So
R So
R So
R So
R So
。１ 。 ２ 。１ 。 ２ 。１ 。 ２Ｒ Ｓ R So
。 a
。 c
。 a
。 cb。
。 a
。 cb。
R S
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。
R S R So
R So
⑵ S是Ｘ上关系。
a)证明Ｓ传递，当且仅当 (可用此定理判定传递 )
证明,充分性,已知
任取 x,y,z∈ X,且有 <x,y>∈ S,<y,z>∈ S,根据关系的复合得
<x,z>∈,由已知得 <x,z>∈ S,所以Ｓ传递。
必要性,已知Ｓ传递，
任取 <x,y>∈,根据关系的复合得
?z(z∈ X∧ <x,z>∈ S∧ <z,y>∈ S),由Ｓ传递得 <x,y>∈ S
所以
b)证明Ｓ自反，当且仅当 IX?S。 (可用此定理判定自反 )
证明,充分性,已知 IX?S，
任取 x∈ X,有 <x,x>∈ IX,由已知得 <x,x>∈ S,所以Ｓ自反。
必要性,已知Ｓ自反，
任取 <x,y>∈ IX,得 x=y,而 S自反，所以 <x,y>∈ S∴ IX?S
S S?Ｓo
S S?Ｓo
S So
S So
S S?Ｓo
⑶ S是Ｘ上关系，证明Ｓ是自反和传递，则 =S。 其
逆为真吗？
证明,由⑵ a)得Ｓ传递，则,只证明 S?
任取 <x,y>∈ S,又已知Ｓ自反，所以 <x,x>∈ S,于是有
<x,x>∈ S∧ <x,y>∈ S，由关系的复合得 <x,y>∈
所以有 S?,最后得 ＝Ｓ。
其逆不一定为真。例如 S如图所示：
它满足 ＝Ｓ，但Ｓ不自反。
⑸ R是 A上关系，
a)R自反,Rc也自反。
因为任取 x∈ A,因 R自反，所以 <x,x>∈ R,∴ <x,x>∈ Rc
b) R对称,Rc也对称。
因为 R对称，所以 Rc =R ∴ Rc也对称。
S So
S S?Ｓo S So
S So
S So S So
S So
。 a
。 cb。
Ｓ
c) R传递,Rc也传递。
方法 1,任取 x,y,z∈ A,且有 <x,y>∈ Rc,<y,z>∈ Rc,于是
<y,x>∈ R,<z,y>∈ R，因 R传递,∴ <z,x>∈ R,于是有
<x,z>∈ Rc,∴ Rc传递。
方法 2,t(Rc)=Rc∪ (Rc)2∪ (Rc)3∪ …
= Rc∪ (R2)c∪ (R3)c∪ …
= (R∪ R2∪ R3∪ …) c
= (t(R))c=Rc (因为 R传递，所以 t(R)=R )
所以 Rc传递。
(R2)c＝ (R?R)c=(Rc?Rc)= (Rc)2
归纳：关系性质证明方法
设 R是 A上关系，
一,证明 R的自反性：
方法 1 用自反定义证：任取 x∈ A,证出 <x,x>∈ R.
方法 2 用恒等关系 IA证,证出 IA ?R,( P119 (2) b) )
方法 3 用自反闭包证,证出 r(R)=R,即 R∪ IA=R.
二,证明 R的反自反性：
方法 1 用反自反定义证：任取 x∈ A,证出 <x,x>?R.
三,证明 R的对称性：
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R,证出 <y,x>∈ R.
方法 2 用求逆关系证,证出 Rc=R.
方法 3 用对称闭包证,证出 s(R)=R,即 R∪ Rc =R.
四,证明 R的反对称性：
方法 1 用定义 1证：
任取 x,y∈ A,设 <x,y>∈ R,<y,x>∈ R.证出 x=y。
方法 2用定义 2证：
任取 x,y∈ A,x≠y,设 <x,y>∈ R,证出 <y,x>?R.
方法 3 用定理证,证出 R∩Rc ? IA, (见 教材 P118)
五,证明 R的传递性：
方法 1 用传递定义证：
任取 x,y,z∈ A,设 <x,y>∈ R,<y,z>∈ R,证出 <x,z>∈ R.
方法 2 用传递闭包证,证出 t(R)=R,
即 R∪ R2∪ R3∪,.,=R.
方法 3用定理证,证出 ( P119 (2) a) )
下面证明第 113页 (4)
R R?Ro
P113(4)R和 S都 A上是自反、对称、传递的，求证 R∩S也
是自反、对称和传递的。
证明,一,证明 R∩S的自反性
方法 1 用自反定义证：任取 x∈ A,(证出 <x,x>∈ R∩S)
因 R和 S都自反，所以有 <x,x>∈ R,<x,x>∈ S，于是有
<x,x>∈ R∩S，所以 R∩S也自反。
方法 2 用恒等关系 IA证,(证出 IA ?R∩S)
因 R和 S都自反，所以 IA ?R, IA ?S，所以 IA ?R∩S
所以 R∩S也自反。
方法 3 用自反闭包证：
(证出 r(R∩S)=R∩S,即 (R∩S)∪ IA= R∩S)
因 R和 S都自反，所以 r(R)=R,r(S)=S,
r(R∩S)=(R∩S)∪ IA= (R∪ IA)∩(S∪ IA)= r(R)∩r(S)=R∩S
所以 R∩S也自反。
二,证明 R∩S 的对称性：
方法 1 用对称定义证：
任取 x,y∈ A,设 <x,y>∈ R∩S,(证出 <y,x>∈ R∩S,)
则 <x,y>∈ R,<x,y>∈ S,因为 R和 S对称，所以有
<y,x>∈ R,<y,x>∈ S,于是 <y,x>∈ R∩S 。 ∴ R∩S 对称。
方法 2 用求逆关系证,(证出 (R∩S )c=R∩S,)
因为 R和 S对称，所以有 Rc=R,Sc=S,而
(R∩S )c=Rc∩S c= R∩S, ∴ R∩S 对称。
方法 3 用对称闭包证：
(证出 s(R∩S )=R∩S,即 (R∩S )∪ (R∩S )c =R∩S,)
因为 R和 S对称，所以 s(R)=R,s(S)=S
s(R∩S )= (R∩S )∪ (R∩S )c =(R∩S )∪ (Rc∩S c)
=(R∪ Rc)∩ (R∪ Sc)∩ (S∪ Sc)∩ (S∪ Rc)
=(s(R)∩ (R∪ Sc))∩ (s(S)∩ (S∪ Rc))
=(R∩ (R∪ Sc))∩ (S∩ (S∪ Rc))=R∩ S (吸收律 )
∴ R∩S 对称。
五,证明 R的传递性：
方法 1 用传递定义证：任取 x,y,z∈ A,
设 <x,y>∈ R∩S,<y,z>∈ R∩S,(证出 <x,z>∈ R∩S )
<x,y>∈ R∩S ∧ <y,z>∈ R∩S
? <x,y>∈ R∧ <x,y>∈ S∧ <y,z>∈ R∧ <y,z>∈ S
? (<x,y>∈ R∧ <y,z>∈ R)∧ (<x,y>∈ S ∧ <y,z>∈ S)
? <x,z>∈ R∧ <x,z>∈ S （因为 R,S传递）
? <x,z>∈ R∩S 所以 R∩S 传递。
方法 2 用传递闭包证,证出 t(R∩S )=R∩S,
即 (R∩S )∪ (R∩S )2∪ (R∩S )3∪,.,=R∩S,
方法 3用定理证,证出
用 方法 2,方法 3证明此题的传递性有很大难度。
R?(S∩T)?(R?S)∩(R?T)
希望同学们灵活掌握证明关系性质的方法 。
(R∩S ) (R∩S ) ?(R∩S )o
P127(1)R的有向图如图所示，求 r(R),s(R),t(R)。
(5)R1和 R2是 A上关系，且 R2 ?R1，求证
a) r(R2)?r(R1),b) s(R2)?s(R1),c) t(R2)?t(R1)。
证明, a) r(R2)=R2∪ IA?R1∪ IA=r(R1),
b) s(R2)= R2∪ (R2)c?R1∪ (R1)c =s(R1),
(因为 R2 ?R1, 所以 (R2)c?(R1)c )
c) 先用归纳法证明 (R2)i?(R1)i,
⑴ i=1时,R2 ?R1 显然结论成立
⑵假设 i≤k时，结论成立，即 (R2)i?(R1)i；
⑶ i=k+1时,(R2)k+1= (R2)k R2?(R1)k R1=(R1)k+1,
t(R2) =R2∪ (R2)2∪,..∪ (R2)k∪,..
? R1∪ (R1)2∪,..∪ (R1)k∪ …= t(R1)。 c)的另一证法,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。r(R) s(R) t(R)
。 。
c) 因为 R2?R1,又 R1?t(R1),所以 R2?t(R1)。 于是有
t(R2)和 t(R1)都是包含 R2的传递关系，而 t(R2)是包含 R2的
最小的传递关系，所以 t(R2)?t(R1)。
(7),R1和 R2是 A上关系，求证
a) r(R1∪ R2)=r(R1)∪ r(R2),
b) s(R1∪ R2)= s(R1)∪ s(R2),
c) t(R1)∪ t(R2) ? t(R1∪ R2),
证明, a) r(R1∪ R2)= (R1∪ R2)∪ IA= (R1∪ IA) ∪ (R2∪ IA)
=r(R1)∪ r(R2),
b) s(R1∪ R2)= (R1∪ R2)∪ (R1∪ R2)c
=(R1∪ R2)∪ (R1)c∪ (R2)c =(R1∪ (R1)c )∪ (R2∪ (R2)c)
=s(R1)∪ s(R2),
c)因 R1? (R1∪ R2)且 R2?(R1∪ R2)，由题 (5)得
t(R1)?t(R1∪ R2),t(R2)?t(R1∪ R2)，所以有
t(R1)∪ t(R2) ? t(R1∪ R2)。
(8),R是 A上关系,R*=tr(R),求证,
a) (R+)+=R+ b) R R*=R+=R* R c) (R*)*=R*
R+ = t(R)=R∪ R2∪ R3∪ …=
R*=rt(R)= IA∪ R∪ R2∪ R3∪,.,=
证明, a) (R+)+=t(t(R)),因为 t(R)是传递的，所以
t(t(R))=t(R),即 (R+)+=R+ 。
b) R R*=R (IA∪ R∪ R2∪ R3∪,.,) ∵ 复合对并可分配，
=R∪ R2∪ R3∪ …= R +。
类似可证 R* R= R+
c) (R*)*=tr(tr(R))=trtr(R)=trrt(R) (∵ tr(R)=rt(R))
=trt(R) (∵ rt(R)是自反的,∴ rrt(R)=rt(R))
=ttr(R)
=tr(R) (∵ tr(R)是传递的,∴ ttr(R)=tr(R))
=R*
。 。
。 。
。
∪ Rii=1∞
∪ Rii=0∞
第 130页 (1).X是集合，且 |X|=4,X有多少个不同的划分？
解,
第 134页 (2),X是集合，且 |X|=4,X上有多少个不同的等
价关系？
解, 此题的答案与上题一样。因为每个划分对应一个等价
关系。
划分块数 各块元素个数 相应划分个数 总数
1 4 C44 = 1
1 3 C41 = 4
2 2 1/2C42 = 32
3 1 1 2 C42 = 6
4 1 1 1 1 C44 =1
15
(4),R是 A上关系,设
S={<a,b>|?c∈ A∧ <a,c>∈ R∧ <c,b>∈ R}
求证若 R是等价关系，则 S也是等价关系。
证明, a)证 S自反,任取 a∈ A,∵ R是自反的,∴ 有
<a,a>∈ R,由 S定义得 <a,a>∈ S,(S定义中 c就是 a)∴ S自反,
b)证 S对称, 任取 a,b∈ A，且有 <a,b>∈ S,由 S定义得
?c∈ A∧ <a,c>∈ R∧ <c,b>∈ R,由 R对称得
?c∈ A∧ <b,c>∈ R∧ <c,a>∈ R,由 S定义得 <b,a>∈ S,S对称,
c)证 S传递,任取 a,b,c∈ A,有 <a,b>∈ S,<b,c>∈ S,由 S定义得
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,
由 S定义得 <a,c>∈ S,所以 S传递, 所以 S是 A上等价关系,
(6),R是 A上对称和传递的关系，证明如果 ?a∈ A,?b∈ A,
使得 <a,b>∈ R,则 R是一个等价关系,
证明,任取 a∈ A,有已知得 ?b∈ A,使得 <a,b>∈ R,由 R对称
得 <b,a>∈ R,又由 R传递得,<a,a>∈ R,R自反,∴ R是等价
关系,
(1)(7).R和 S都是 A上等价关系,下面哪个是 A上等价关系?
证明或举反例说明,
a) R∪ S b) R∩S c) ~R (即 A× A-R)
d) R-S e)R2 f) r(R-S)
解,a) c) d) f)不是, 请看反例,
R
。 a
。 cb。
。 a
。 cb。
。 a
。 cb。S R∪ S
。 a
。 cb。 ~R
。 a
。 cb。 R’
。 a
。 cb。 R’-S
。 a
。 cb。 r(R’-S)
b),R∩S是等价关系,前面已经证明过,(第 113页题 (4))
e).① 证 R2自反,任取 a∈ A,因为 R自反,所以 <a,a>∈ R,根据
关系的复合得,<a,a>∈ R R,即 <a,a>∈ R2,所以 R2自反。
② 证 R2对称,(R2)c=(Rc)2=R2 (由 R对称得 Rc=R) ∴ R2对称
③ 证 R2传递，任取 a,b,c∈ A,设有 <a,b>∈ R2,<b,c>∈ R2,
根据关系的复合得,
(?d∈ A∧ <a,d>∈ R∧ <d,b>∈ R)∧ (?e∈ A∧ <b,e>∈ R∧ <e,c>∈ R),
由于 R传递,所以有 <a,b>∈ R,<b,c>∈ R,∴ <a,c>∈ R2
所以 R2传递。最后得 R2是等价关系。
第 139页 (2), X={x1,x2,x3,x4,x5,x6},R是 X上相容关系，
其简化关系矩阵如下：求 X的完全覆盖。
解, R的简化图为：
CR(X)={{x1,x2,x3,},{x1,x3,x6},{x3,x4,x5},{x3,x5,x6}}
o
x2 1
x3 1 1
x4 0 0 1
x5 0 0 1 1
x6 1 0 1 0 1
x1 x2 x3 x4 x5
x1 。 。 x2
x6 。
x5 。 。 x4
。 x3
第 145页 (1),给定集合 {3,5,15},{1,2,3,6,12},{3,9,27,54}，
≤为整除关系，分别画出上述集合上的 ≤的关系图，
Hasse图，并指出哪些是全序关系。
全序
。
。 。
。
。 。。
。
1
2 36
1215
53
。
。 。
。
27
54
9
3
。
。 。
。
。 。
。
。
1
2 3
6
1215
53
。
。
。
。
27
54
9
3
(6), P={x1,x2,x3,x4,x5},P上偏序关系的
Hasse图如图所示，求子集 {x1,x2,x3}，
{x2,x3,x4},{x3,x4,x5}和 P的极小 (大 )元、
最小 (大 )元、上界、下界、最小上界和
最大下界 (上确界和下确界 )。
。
。 。
。。
x1
x2 x3
x4 x5
子 集 极小元 极大元 最小元 最大元 上界 下界 上确界 下确界
{x1,x2,x3} x2,x3 x1 无 x1 x1 x4 x1 x4
{x2,x3,x4} x4 x2,x3 x4 无 x1 x4 x1 x4
{x3,x4,x5} x4,x5 x3 无 x3 x1,x3 无 x3 无
P x4,x5 x1 无 x1 x1 无 x1 无
第四章 二元关系
到此结束
