集 合 论
集合论是研究集合的一般性质的数学分支，它
研究集合不依赖于组成它的事物的特性的性质。
在现代数学中，每个对象（如数、函数等）本
质上都是集合，都可以用某种集合来定义。数学
的各个分支，本质上都是在研究这种或那种对象
的集合的性质。集合论已成为全部现代数学的理
论基础。
集合论的特点是研究对象的广泛性。它总结出
由各种对象构成的集合的共同性质，并用统一的
方法来处理。因此，集合论被广泛地应用于各种
科学和技术领域。
集 合 论
由于集合论的语言适合于描述和研究离散对象
及其关系，所以也是计算机科学与工程的理论基
础，在程序设计、关系数据库,排队论、开关理
论，形式语言和自动机理论等学科领域中都有
重要的应用。
本篇主要介绍：集合、二元关系和函数，
以及集合的基数问题。
集 合 论
第三章 集合与关系
§ 1集合的概念和表示法
§ 2集合的运算
§ 3序偶与笛卡尔积
§ 4关系及其表示
§ 5关系的性质
§ 6复合关系和逆关系
§ 7关系的闭包运算
§ 8集合的划分和覆盖
§ 9等价关系与等价类
§ 10相容关系
§ 11序关系
§ 1集合的概念和表示法
1、集合与元素
（ 1）集合：具有某种特殊性质的客体的聚合。
讨论：
① 一些不同的确定的对象之全体。
② 客体：是泛指一切，可以是具体的、抽象的
③ 元素（成员）：属于任何集合的任何客体。
④符号,用大写英文字母表示集合，用小写英文字母或
其它符号表示元素。
集合,A,B….
元素,a,b…,
§ 1集合的概念和表示法
⑤ 元素与集合间的关系,若 a是集合 S中的元素，则
可写成 a? S ；若 b不是集 S合中的元素，则可
写成 b? S 。
⑥ 集合 S的基数 (势 ),S中的元素个数。用 |S|表
示。
⑦ 有限集合：集合的基数（元素）是有限的。
无限集合：集合的基数（元素）是无限的。
§ 1集合的概念和表示法
⑧ 本书中常用集合符,
Im(m≥1) 有限个正数的集合 {1,2,3……m}
Nm(m≥0) 有限个自然数的集合 {0,1,2……m}
以上是有限集合,下面是无限集合：
N 自然数集合 {0,1,2……}
I+ 正整数集合 {1,2,3……}
I 整数集合 {…… -1,0,1,2……}
P 素数集合 {大于 1的正整数，只能被 1和自己整除 }
Q 有理数集合 {i/j,i,j均为整数且 j≠0}
R 实数集合 {有理数、无理数 }
C 复数集合 {a+bi,a,b可为实数 i= √-1 }
§ 1集合的概念和表示法
(2)集合的表示方法,
(a)枚举法 (列举法 )
把集合的元素列于花括号内。
例：
命题的真假值组成的集合,S={T,F}
自然数 0,1,2,3,4五个元素的集合,P={0,1,2,3,4}
(b)谓词公式描述法
所有集合均可用谓词公式来表示,S={x | p(x) }
§ 1集合的概念和表示法
例：大于 10的整数的集合,S1={x | x? I ∧ x>10}
偶整数集合,S2={x | ?y (y ?I ∧ x=2y)}
有限个元素集合：
S3={1,2,3,4,5}={x | x ?I ∧ (1 ≤ x ≤ 5) }
S4={F,T}={x | x=T ∨ x=F}
S5={1,4}={ x | (x2-5x+4=0) }
(c)同一集合可以用多种不同的形式表示。
(d)集合也可作为某一集合的元素。
例,S={a,{1,2},p,{q}}
§ 1集合的概念和表示法
(3)三个特殊集合：空集、全集合、集合族
,定义, 如果一个集合包含了所要讨论的每一个集合，
则称该集合为全集合，简称全集，用 E表示。
E={x | p(x) ∨ ? p(x)} p(x)为任何谓词公式
,定义, 不拥有任何元素的集合称为空集（或称零集），
用 ?表示
?={x | p(x) ∧ ? p(x) }={ }
注意,?≠ {?} 前者是空集，是没有元素的集合；后
者是以 ?作为元素的集合。
§ 1集合的概念和表示法
,定义, 集合中的元素均为集合，称这样的集合为集合
族。
例 A={{a},{b},{c,d}}
2、集合之间的关系
,公理, 给定二个集合 A和 B，当且仅当 A和 B具有同样
的元素（成员），则 A和 B才是相等的，记作 A=B
并规定：（ A=B） ??x (x? A ? x ? B)
例,{a,b,c}={b,a,a,c,c}
§ 1集合的概念和表示法
例,{a,b,c}={b,c,a}
例：设 P={{1,2},4},Q={1,2,4}，则 P?Q
,定义, 设 A,B是任意二个集合，如果集合 A的每一个
元素都是 B的一个元素，则称 A 是 B的子集，或者说 A
包含于 B，或者说 B包含 A，记作 A?B，或者 B?A。
并规定,A?B?B?A??x(x?A → x ?B)
§ 1集合的概念和表示法
例,A1={1,2,3} A2={0} A3={1,2,3,0} B={1,2,3,0}
则 A1,A2,A3均为 B的子集合，并记为
A1?B,A2?B,A3?B
,定义, 设 A,B是任意二个集合，若 A?B且 A≠B，则称
A是 B的真子集，记作 A?B（ A真包含于 B）
并规定,A?B?（ A?B ∧ A≠B）
§ 1集合的概念和表示法
注意：区分,?”和,?”的关系：
,?”关系是指集合和该集合中元素之间的关系。
例,S={a,{b},c} 则 a? S,{b}?S,c?S
而,?”关系是指二个集合之间的关系。
例,S1={a,b} S2={a,b,1,2} 则 S1? S2
若 A不包含于 B，则也可表示成 A?B
,定理, 设 E是全集,A是一个集合，则一定有 A?E。
证明,?x（ x? A → x ? E） 而 x? E始终为,T”，
所以 x? A → x ?E一定为,T”
故有 ?x（ x? A → x ? E）为,T”，则有 A?E
§ 1集合的概念和表示法
,定理, 设 A,B是任意二个集合，当且仅当 A?B和 B?
A才有 A=B。
证明：
(ⅰ )充分性：（ A=B） ?（ A?B ∧ B? A）
(A=B)??x (x ?A→ x ?B∧ x?B→ x ?A)
??x(x?A→ x ?B)∧ ?x(x?B→ x ?A)
?(A?B)∧ (B?A)
(ⅱ )必要性,A?B∧ B?A?A=B
(A?B)∧ (B?A)??x(x?A→ x ?B)∧ ?x(x?B→ x ?A)
?(A=B)
§ 1集合的概念和表示法
,推论, 对于任一集合 A，则有 A?A。
,定理, 设 A,B,C是任意集合，如果 A?B和 B?C，则
A?C 。
,推论, 若 A?B和 B?C，则 A?C 。
,定理, 设有空集 ?和任一集合 A，则 ??A
证明：设 x?A，要证明 ??A，只要证,?x(x??→ x ?A)
为,T”
∵ ?中没有元素，
∴ x??为假,?x（ x??→ x ?A）为,T”
,定理, ?是唯一的 。
§ 1集合的概念和表示法
证明：设有二个空集合 ?1和 ?2
∵ ?是任何集合的子集
∴ （ ?1??2∧ ?2 ??1） ?(?1=?2)
3、幂集和索引集合
（ 1）幂集：
例：给定 S1={a} 则子集为 ?,{a}
S2={1,{2}} 则子集为 ?,{1},{{2}},{1,{2}}
S3=? 则子集有 ?（而不是 {?}）
由此可见：给定一个集合 S，则 ?和 S一定是 S的子集。
§ 1集合的概念和表示法
,定义, 设 A是集合,A的所有子集（作为元素）的集
合称为 A的幂集。
记作 ρ(A)或 2A 且有,ρ(A)(=2A)={x | x ?A}
例：若 A1=?，则 ρ(A1)={?}
若 A2={a}，则 ρ(A2)={?,{a}}
若 A3={1,2}，则
ρ(A3)={?,{1},{2},{1,2}}
§ 1集合的概念和表示法
讨论定义：
(a)集合的元素个数称为集合的“基数”或叫“势”
|ρ(S)|=2 |s| 为幂集 ρ(S)的基数
(b) 若 A为有限集合，则 ρ(A)也为有限集合。
若 A为无限集合，则 ρ(A)也为无限集合。
(c)一定有 A?ρ(A),??ρ(A)，
即对非空集合，在幂集中至少有两个子集 ?和 A。
§ 1集合的概念和表示法
（ 2）索引集合
为了在计算机上表示集合，必须给每一个集合的元素加
上标记，以用来表示元素在集合中的位置。
例,S1={a,b} 假设集合 S1中,a,b的位置已经固定。
则用二进制下标法来表示 S的所有子集：
?={ }=B00,{a}=B10,{b}=B01,{a,b}=B11
这样 ρ(S1)={B00,B01,B10,B11}={Bi | i?J}
而其中 J={00,01,10,11} （索引集合或指标集合）
§ 1集合的概念和表示法
例：
已知集合 S={a1,a2,a3,a4,a5,a6},S的子集
有 26 个
可以分别表示成 B0,B1……B ( 26-1)
则 B7=B000111={a4,a5,a6}
B15=B001111={a3,a4,a5,a6}
B22=B010110={a2,a4,a5}等等
§ 2 集合的运算
1.交集（交运算）
,定义, 任何二个集合 A和 B的交集 A∩B是由 A和 B所共有的
全部元素构成的集合，
即,A∩B={x | x? A∧ x ?B}
例,A={a,b} B={a,c} A∩B={a}
,定理, 集合的相交运算是可交换的和可结合的，即对于任
何集合 A,B,C有
A∩B=B∩A，（ A∩B） ∩C=A∩（ B∩C）
证明：设 x是 A∩B中任一元素
则 x? A∩B?x? {x | x? A ∧ x? B}
?x ?{x | x? B ∧ x? A}?x? B∩A
∴ A∩B=B∩A
§ 2 集合的运算
,定理, 设 A是 E的任一子集，则有
（ 1） A∩A=A
（ 2） A∩?=?
（ 3） A∩E=A
,定义, A,B是二个集合，若 A∩B=?，则称 A和 B是
不相交的，或者说 A和 B没有相同的元素。
若 C是一个集合族 （集合族：元素均为集合的集合）使
C的任何二个元素都不相交，则称 C为不相交的集合
族。
例,A={{a},{b},{c}} A为不相交的集合族
§ 2 集合的运算
2.并集（并运算）
,定义, A,B是任意二个集合,A和 B的并集 A∪ B是由
A和 B的所有元素构成的集合，
即,A∪ B={x│ x?A∨ x?B}。
例,A={a,b,c} B={1,2,3} 则
A∪ B={a,b,c,1,2,3}
,定理, 集合的并运算是可交换的和可结合的，即对任
何 A,B,C有
A∪ B=B∪ A和（ A∪ B） ∪ C=A∪ （ B∪ C）
§ 2 集合的运算
,定理, 集合的并和交运算，每一个对另一个都是可分
配的。
即,(1)A∪ （ B∩C） =（ A∪ B） ∩（ A∪ C）
(2)A∩（ B∪ C） =（ A∩B） ∪ （ A∩C）
,定理, 设 A,B,C是全集 E的任意子集，则有：
(1)A∪ A=A
(2)A∪ ?=A
(3)A∪ E=E
§ 2 集合的运算
3.相对补集：
,定义, 设 A和 B是二个任意集合,B对 A的相对补集
（ A-B）是由 A中且不属于 B的所有元素组成的集合。
即：
A-B={x│x?A∧ x?B}={x│x?A∧ ?x?B} 。
例：设 A={0,1,2} B={2,3,4}
则 A-B={0,1} B-A={3,4}
∴ A-B≠B-A相对补集不满足交换律。
§ 2 集合的运算
,定理, 设 A,B,C,D是 E的子集，则有：
(1 )A-B?A，
(2 )若 A?B和 C?D，则 A∩C?B∩D，
(3 )若 A?B和 C?D，则 A∪ C?B∪ D，
(4 ) 若 A?A∪ B，则 B?A∪ B
(5 ) 若 A∩B?A，则 A∩B?B
(6 ) 若 A?B，则 A∪ B=B
(7 ) 若 A?B，则 A∩B=A
(8 )A-?=A
(9 )A∩(B-A)=?
(10)A∪ (B-A)=A∪ B
§ 2 集合的运算
(11)A-（ B∪ C） =（ A-B） ∩（ A-C）
(12)A-（ B∩C） =（ A-B） ∪ （ A-C）
4、绝对补集（补运算 ）
,定义, 设 E是全集，任一集合 A对 E的相对补集称为 A
的绝对补集（或称补集）记作 ~A（或 ?A）。即：
~A=E-A={x| x?E∧ x?A}={x| x?A}
§ 2 集合的运算
例：设 E={a,b,c,d} A={a,b} 则 ?A={c,d}
,定理） A是 E的任一子集，则有
(1)A∪ ?A=E
(2)A∩?A=?
,定理） 设 A,B是 E的二个子集，当且仅当 A∪ B=E
和 A∩B=?才有
B= ~A（或 A= ~ B）
§ 2 集合的运算
证明,(ⅰ ) 充分性：
B= ~A ?（ A∪ B=E） ∧ （ A∩B=?）
∵ B=~A
∴ A∪ B=A∪ ~A=E
A∩B=A∩~A=?成立
(ⅱ )必要性：
(A∪ B=E)∧ (A∩B=?)?B=?A
∵ B=E∩B=(A∪ ~A)∩B=(A∩B)∪ (~A∩B)
=?∪ （ ~A∩B）
=（ ~A∩A） ∪ （ ~A∩B） =~A∩（ A∪ B）
=~A∩E=~A
§ 2 集合的运算
补集的性质：
（ 1） ~（ ~A） =A
（ 2） ~（ A∪ B） =~A∩~B
（ 3） ~（ A∩B） =~A∪ ~B
（ 4） ~?=E
（ 5） A-B=A∩~B
例：设 A={2,5,6},B={2,3,4},C={1,3,4}，
E={1,2,3,4,5,6}
则 A-B={5,6}=A∩~B={2,5,6}∩{1,5,6}={5,6}
§ 2 集合的运算
5、环和 (对称差 )
,定义, 设 A,B是任意二集合,A和 B的环和记作 A⊕ B。
即：
A⊕ B=(A-B)∪ (B-A)=(A∩~B)∪ (B∩~A)
或者 x?(A⊕ B)?x?{x |x?A?x?B}
例：
设 A={2,5,6},B={2,3,4}
则 A?B={3,4,5,6}
§ 2 集合的运算
对称差的性质：
(1)A?B=B?A 可交换的
(2)(A?B)?C=A?(B?C) 可结合的
(3)A?B=(A-B)∪ (B-A)
=(A∩~B)∪ (B∩~A)=(A∪ B)∩(~A∪ ~B)
(4)A?A=?
(5)A??=A
(6)~A?~B=(~A∩~(~B))∪ (~B∩~(~A))
=(~A∩B)∪ (~B∩A)=(B-A)∪ (A-B)=A?B
(7)A∩(B?C)=(A∩B)?(A∩C) (∩对 ?是可以分配的 )
§ 2 集合的运算
6、文氏图
(1)文氏图的画法规则：
规定矩形表示 E。子集用圆画在 E中。
(2)文氏图应用：
（ a）表示集合和运算的关系
可用文氏图画出各种运算：
（ b）证明集合恒等式
例,A?（ B?C） =（ A?B） ?（ A?C）
§ 3 序偶与笛卡尔乘积
1.序偶：
,定义, 由二个具有给定次序的客体所组成的序列称为序偶。
记作 〈 x,y〉
例,X—Y二维平面上的一个点的坐标 〈 x,y〉 就是一个序
偶。
说明：在序偶中二个元素要有确定的排列次序。即：
若 a?b时，则 〈 a,b〉 ?〈 b,a〉
若 〈 x,y〉 =〈 a,b〉 ?（ x=a?y=b）
下面定义多重序元：
三重序元 〈 x,y,z〉 =〈〈 x,y〉, z〉
n重序元 〈 x1,…,x n〉 =〈〈〈〈 x1,x2〉, x3〉 … 〉, xn〉
§ 3 序偶与笛卡尔乘积
2.笛卡尔乘积
,定义, 设 A,B为二个任意集合，若序偶的第一个成员
（左元素）是 A的一个元素，序偶的第二个成员
（右元素）是 B的一个元素，则所有这样的序偶的
集合称为 A和 B的笛卡尔乘积。
记作,A?B={〈 x,y〉 |（ x?A） ?（ y?B） }
例：设 A={1,2} B={a,b}
则 A?B={〈 1,a〉, 〈 1,b〉, 〈 2,a〉, 〈 2,b〉 }
B?A={〈 a,1〉, 〈 a,2〉, 〈 b,1〉, 〈 b,2〉 }
∴ A?B?B?A 即,?”是不满足交换律。
§ 3 序偶与笛卡尔乘积
例：设 A={a,b},B={1,2},C={z}
则 (A?B)?C={〈 a,1〉,〈 a,2〉,〈 b,1〉,〈 b,2〉 }?{z}
={〈 a,1,z〉,〈 a,2,z〉,〈 b,1,z〉,〈 b,2,z〉 }
A? ( B?C ) ={a,b}?{〈 1,z〉,〈 2,z〉 }
={〈 a,〈 1,z〉 〉,〈 a,〈 2,z〉〉,〈 b,〈 1,z〉〉,〈 b,〈 2,z〉〉 }
∴ （ A?B） ?C?A?（ B?C）, ?”不满足结合律。
,定理, 若 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）
§ 3 序偶与笛卡尔乘积
证明：（ 2）设 〈 x,y〉 是 A?（ B?C）中的任一元素，
则,〈 x,y〉 ?A?（ B?C） ?
〈 x,y 〉 ?{〈 x,y 〉 |x?A?y?B?C}
? <x,y>?{<x,y>|x?A?y?B?y?C}
? <x,y>?{<x,y>|(x?A?y?B)?(x?A?y?C)}
? <x,y>?(A?B)?(A?C)
即 A?(B?C)=(A?B)?(A?C)
例：设 A={1},B={1,2},C={2,3}
则 A?（ B?C） ={1}?{1,2,3}
={〈 1,1〉, 〈 1,2〉, 〈 1,3〉 }
§ 3 序偶与笛卡尔乘积
（ A?B） ?（ A?C） ={1}?{1,2}?{1}?{2,3}
={〈 1,1〉, 〈 1,2〉, 〈 1,3〉 }
A?（ B?C） ={1}?{2}={〈 1,2〉 }
（ A?B） ?（ A?C）
={〈 1,1〉,〈 1,2〉 }?{〈 1,2〉,〈 1,3〉 }
={〈 1,2〉 }
n个集合的笛卡儿乘积的定义,
设 A={Ai},i?In
Ai=A1?A2?…… ?An
= （（（ A1?A2） ?A3） ?…… ） ?An
§ 4关系及其表示
序偶 〈 a,b〉 实际上反映了二个元素之间的关系，
关系反映了事物的结构。
1.关系：指事物之间（客体之间）的相互联系。
日常生活中：父子关系，母子关系，兄弟关系等均为二
个客体之间的关系。
而祖孙关系是三个客体之间的关系（父子关系和父子关
系的合成）。
n元笛卡尔积 A1× A2× ?? × An是 n元关系。
§ 4关系及其表示
,定义, 若
则是一个二元关系。 即：序偶作为元素的任何
集合 。
２．关系表示方法
（ 1）枚举法（直观法、列举法）
设 R表示二元关系，用 表示特定的序偶，
若,则也可写成：
x R y。
}|,{ 22112121 AxAxxxAA ???????
xRy
Ryx ???,Ryx ???,
?
§ 4关系及其表示
例：二元关系定义如图：
可写成：
由定义可见：关系是一个集合，
∴ 定义集合的方法都可以来定义关系。
（ 2）谓词公式表示法
前面讲述，一个集合可用谓词公式来表达，所以
关系也可用谓词公式来表达。
},4,3,2,1{ ????????? dcbaR
§ 4关系及其表示
例：实数集合 R上的,>”关系可表达为：
大于关系：,>”=
父子关系：,F”=
（ 3）关系矩阵表示法
规定：
(a)二元关系 <x,y>中的序偶中左元素表示行，右元素表
示列；
(b)若,则在对应位置记上,1”，否则为,0”。
)}(|,{ yxRyRxyx ???????
}|,{ 的父亲是 yxyx ??
iiRyx
§ 4关系及其表示
例 1：设
并定义为
列出关系矩阵：
例 2：设 X={a,b,c},Y={1,2},R2是Ｘ → Ｙ的关系，
}1,22,31,33,42,41,4{1 ?????????????R
?
?
?
?
?
?
?
?
?
?
?
?
?
1 1 1 0
1 1 0 0
1 0 0 0
0 0 0 0
1R
M
的关系是 ????? R},4,3,2,1{
§ 4关系及其表示
是Ｘ → Ｙ的全域关系，
}2,1,2,1,2,1,{2 ??????????????? ccbbaaYXR
2R
??3R
§ 4关系及其表示
（ 4）关系图表示法
规定：
(a)把Ｘ、Ｙ集合中的元素以点的形式全部画在平面上；
(b)若,则 xi和 yi之间画一箭头弧线，反之不画任何
联线。
例,是 X中的二元关系，
iiRyx
1},4,3,2,1{ RX ?
}1,22,31,33,42,41,4{1 ?????????????R
§ 4关系及其表示
用关系图表示：
３．关系的定义域和值域：
,定义,, 设 S是一个二元关系,D(s)是所有客体 x的集
合，对于一些 y来说，若有,则称 D(s)为
S的定义域（简称“域”），即
Syx ???,
§ 4关系及其表示
)},(|{)( SyxyxsD ?????
设 R(S)是所有客体 y的集合，对于一些 X来说，若有
Syx ???,，则称集合 R(S)是 S的值域（简称“值”）,即：
},(|{)( ?????? SyxxySR
例,X={1,2,3,4,5,6},R为 X到 Y的二元关系
},4,3,2,1{ ????????? dcbaR
,f}{a,b,c,d,eY ?
，则
},,,{)(},4,3,2,1{)( dcbaRRRD ??
一般情况，称 X为 R的 前域,称 Y为 R的 陪域 。
§ 4关系及其表示
４．关系和笛卡尔乘积
笛卡尔乘积的任何子集都可以定义一种二元关系。
例,X={1,2,3,4},Y={1,2}，则
}2,4,1,4,2,3,1,3,2,2,1,2,2,1,1,1{ ?????????????????? YX
§ 4关系及其表示
}3,42,41,42,31,31,2{}|,{1 ????????????????????? yxYyXxyxS
}2,41,1{}|,{ 22 ????????????? yxYyXxyxS
}2,21,1{}|,{3 ????????????? yxYyXxyxS
321,,SSS
均为二元关系。
５．三个特殊关系：空白关系，全域关系，恒等关系
,定义,, 集合 X2定义了 X集合中的一种关系，
通称为 X中的全域关系，用 Ex表示：
§ 4关系及其表示
},|,{ XyxyxXXE iix ??????
空集也是 的一个子集，它也定义了一种关系
称为空白关系；
XX ?
X集合中的恒等关系,}|,{ XxxxI iiix ????
在全域关系和恒等关系中前域 =定义域，陪域 =值域。
例：Ｘ =｛Ｔ，Ｆ｝则
},,,,{ ????????? FFTFFTTTE x
},,{
{}
?????
??
FFTTI x
同一域上的关系,可进行
集合的所有运算。
§ 5关系的性质
１．自反性,
,定义,,设Ｒ是Ｘ集合中的二元关系，对于每一个（所有的）
Xx?,有 xRx,则称Ｒ是自反关系,X中 R是自反的
)( x R xXxx ????
例：设 },,{ cbaX ?
},,,,{ ????????? baccbbaaR 是自反的关系。
R的关系矩阵
?
?
?
?
?
?
?
?
?
?
?
0 0 1
0 1 0
1 1 0
RM
§ 5关系的性质
,定义,, 设 R是 X中的二元关系，对于每一个,
有 x x，则称 R是反自反的关系，表示成,R是 X中的反自反的关
系 x x 。
Xx?
??? Xxx ( )
例：设 X={1,2,3},
}1,22,1{1 ?????S
}2,1{2 ???S
}1,2{3 ???S
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
000
100
000
,
000
000
010
,
000
100
010
321 SSS
MMM
§ 5关系的性质
}2,31,31,21,1{4 ?????????S
?
?
?
?
?
?
?
?
?
?
?
110
100
100
RM
２．对称性
,定义,,设 R是 X中的二元关系，对于每一个
来讲，如果每当有 xRy，则必有 yRx，则称 R是 X中的对称关
系,并表示成,R是 X中的对称关系
Xyx ?,
)( y R xx R yXyXxyx ????????
S4既不是自
反的，又不
是反自反的
§ 5关系的性质
例：设 X={1,2,3},R={<1,1><2,1><1,2><3,2><2,3>}
则 R是对称的关系
?
?
?
?
?
?
?
?
?
?
?
0 1 0
1 0 1
1 1 0
RM
,定义,,设 R是 X集合中的二元关系，对于每一个 Xyx ?,
来讲，如果每当 xRy和 yRx就必有 x=y，则称 R是反对称的关
系。
§ 5关系的性质
即当且仅当 )( yxy R xx R yXyXxyx ?????????
X中的 R才是反对称的。
讨论定义：（ 1）前件 yR xxR y ? 为,T”，
则 x=y也为,T”,则为反对称的；
（ 2） 前件 yR xxR y ? 为,F”，
则有三种情况：
后件（ x=y）不论是真还是假，命题公式为,T”。
下面举例说明：
§ 5关系的性质
例：设 X={a,b,c}
},,,{1 ??????? accbbaR
},,,,{2 ????????? ccbbaacaR
},,,{3 ??????? accbaaR 均是反对称的
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
100
001
100
,
001
010
101
,
100
001
010
321 RRR
MMM
§ 5关系的性质
例,X={a,b,c},下列关系不是对称的，也不是反对称的
},,,{1 ??????? cbabbaR
},,,,{2 ????????? cabccbaaR
§ 5关系的性质
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 1 0
0 0 1
1 0 1
,
0 0 0
1 0 1
0 1 0
21 RR
MM
X上的恒等关系 },,,{
3 ??????? ccbbaaR
是自反、对称、反对称的。
§ 5关系的性质
?
?
?
?
?
?
?
?
?
?
?
0 0 1
0 1 0
1 0 0
3R
M
X上的全域关系：
},,,,,,,,,{4 ??????????????????? bcaccbabcabaccbbaaR
是自反的，对称的
X上的空关系是反自反、对称、反对称的。
§ 5关系的性质
３．传递性,
,定义,,设 R是 X中的二元关系，对于每一个 Xzyx ?,,
来说，如果每当 yR zxR y ?,就必有 xRz
则称 R是可传递的，并表示成,X中 R可传递
)( x R zy R zx R yXzXyXxzyx ????????????
讨论定义：（ 1）前件 yR zxR y ? 为,T”，
则 xRz也为,T”,R是可传递的 ；
（ 2）前件为,F”，有三种情况
后件不论是真还是假，命题为,T”，则 R是可传递
的
§ 5关系的性质
例：设 X={a,b,c}，则下列关系均是可传递的
},,,,{1 ????????? cbcabaaaR
},{2 ??? baR
},,{3 ????? cabaR
??4R
§ 5关系的性质
下列关系是不可传递的：
},,,{4 ??????? accaaaR
},,,{5 ??????? accbbaR
§ 5关系的性质
４．确定二元关系性质举例
（ 1）设 X={1,2,3}，
}3,13,22,1{1 ???????R
反自反，反对称，可传递的；
}3,22,11,1{2 ???????R
反对称的；
§ 5关系的性质
}3,32,21,1{3 ???????R
自反，对称，反对称，可传递的；
xER ?4
自反，对称，可传递的；
??5R
反自反的，对称的，反对称的，
可传递的。
§ 5关系的性质
（ 2）若 ??X,则 X上的空关系 ?
自反的，反自反的，对称的，反对称的，可传递的。
§ 6复合关系和逆关系
１．关系的复合
,定义,,设 YX ? （ R关系）,ZY ? （ S关系），
于是可用 ZX ? （ R?S） 的关系，称 R?S
为 R和 S的复合关系，并规定为：
)},,(|,{ SzyRyxYyyZzXxzxSR ??????????????????
例：设 A={1,2,3,4,5},R,S均为 A→A 的关系，且
R={<1,2><3,4><2,2>},S={<4,2><2,5><3,1><1,3>}
则 R?S={<1,5><3,2><2,5>},S?R={<4,2><3,2><1,4>}
§ 6复合关系和逆关系
,RSSR ?? ? ∴,?”是不可交换的。
讨论：
（ 1） R?S为新的二元关系
（ 2） R?S?X× Z
（ 3）当 <x,y>∈R 与 <y,z>∈S,才有 <x,z>∈ R?S
§ 6复合关系和逆关系
,定理,,设 WZYX RRR ? ??? ??? ?? 321 则有：
321321321 )()( RRRRRRRRR ?????? ??
可见合成关系图
下面定义关系 R 的幂次
§ 6复合关系和逆关系
,定义, 给定集合 X,R是 X中的二元关系，设 Nn?
于是 R的 n次幂 nR 可以定义成：
（ 1） 0R =X集合中的恒等关系
（ 2） RRR nn ???1
例：设 R,S是
?I
中的二元关系，且
}|7,{},|2,{ ?? ???????? IxxxSIxxxR 则：
}|14,{},|14,{ ?? ???????? IxxxRSIxxxSR ??
§ 6复合关系和逆关系
},,,,,{2 ??????? bcabcaR
}|4,{2 ????? IxxxR }|49,{2 ????? IxxxS
}|8,{23 ?????? IxxxRRR ?
},,,,,{ ??????? accbbaR},,{ cbaX ?例：
xIccbbaaRRR ????????? },,,,,{23 ?
§ 6复合关系和逆关系
RRRR ?? ?34
nmikR aM ?? ][
若 |X|=n，则 X中的二元关系 R的幂次值是有限的。一般不用
求出超过 X的基数次幂。
２．复合关系的矩阵表示
设有三个集合：
ZYXzzzZyyyYxxxX SRpnm ? ??? ????? },,{},,{},,{ 212121 ???
而 |X|=m,|Y|=n,|Z|=p，则关系矩阵
pnkjS bM ?? ][
§ 6复合关系和逆关系
1)()()()()( 5515451435132512151115 ??????????? bababababaC
pmijSR cM ?? ][?SRSR MMM ?? ?
例：设 X={1,2,3,4,5},R,S均是 X中的二元关系，
R={<1,2><3,4><2,2>},S={<4,2><2,5><3,1><1,3>}
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 1
,
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 1 0 0
,
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 1 0 0 0
SRSR
MMM
?
)(
1 kjik
n
kij
bac ???
?
§ 6复合关系和逆关系
３．逆关系
,定义,,设 X,Y是二个集合，若 R是 X→Y 的关系，从
Y→X 的关系，称为 R的逆关系，用 },|,{~ RyxxyR ??????
表示，或用 cR 表示。
讨论定义：（ 1）只要将 R中每一个序偶中的元素全部调换位置，
就可得到 R的逆关系 R~
（ 2）设 R~ 的关系矩阵为
RM~ RM?
的转置矩阵；
（ 3）在 R的关系图中，只要把所有箭头改换方向就可得到
的关系图。（自回路箭头改变与否无关）R~
§ 6复合关系和逆关系
例,X={0,1,2},R={<0,0><0,1><1,2><2,2>},
R~ ={<0,0><1,0><2,1><2,2>},
,
011
100
100
,
001
001
110
~
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
RR
MM
§ 6复合关系和逆关系
,定理,,设 ZYX SR ? ??? ??,则可有,RSSR ~~~ ?? ?
证明：对于任一 ZzYyXx ???,,来讲，若有
xSRzzSRxy S zx R y )()( ~?? ???
同样 xRSzxRyySz )~~(~~ ???
∵ x,y,z分别为 X,Y,Z中的任一元素，
∴ RSSR ~~~ ?? ?
§ 6复合关系和逆关系
例：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 1 0 1 0
1 0 1 0 1
1 0 0 1 0
,
111
110
101
SR MM
，试求：
~,,,~~ SRSRSR MMMM ??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1 1 1 1 1
1 0 1 1 1
1 1 0 1 0
,
0 1 0
1 0 1
0 1 0
0 0 1
1 1 0
,
1 0 1
0 1 1
1 1 1
~~
SRSR
MMM
?
§ 6复合关系和逆关系
~~ ~~~~
0 1 1
1 1 1
0 1 1
1 0 1
1 1 1
,
0 1 1
1 1 1
0 1 1
1 0 1
1 1 1
SR
RSRS
SR
MMMMM
?
?
?
? ??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
,定理,,设 R是 X中的二元关系，当且仅当 RR ~?
则 R才是对称的。
§ 6复合关系和逆关系
证明：①充分性,R是对称的 RR ~??
对于任一 RbaRabRba ~,,,???????????
② 必要性,?? RR ~ R是对称的，
RR ~?? ∴ 对任一
RabRbaRba ???????????,~,,
∴ R一定是对称的
∴ RR ~?
§ 6复合关系和逆关系
,定理,,给定集合 X,Y,YX SRRR ??? ??,,,21,于是可有
RR ?~~)1(
SRSR ~~)2( ~ ?? ?
SRSR ~~)3( ~ ?? ?
XYYX ???~)4(
???~)5(
)(~,~~)(~)6( ~ RYXRRR ????
§ 6复合关系和逆关系
21
~
21
~~)7( RRRR ???
2121 ~~)8( RRRR ???
2121 ~~)9( RRRR ???
21
~
21
~~)10( RRRR ???
证明：（ 1）设 <a,b>是 R中的任一元素，则
RbaRabRba ~,~,,???????????
（ 10）设 YyXx ??,，对任一
~
1221
~
21 )()(,,RRRRyxRRyx ?????????? ?
§ 6复合关系和逆关系
由（ 2） SRSR ~~~ ?? ? ~ 12~ 21 )()((,RRRRyx ?????? ?
由（ 7）
21
~
21
~~ RRRR ???
)~~(,)~~()~~((,211221 RRyxRRRRyx ??????????? ?
21
~
21
~~ RRRR ????
§ 7关系的闭包运算
,定义,,给定集合 X,R是 X中的二元关系，若有另一
R’满足下列条件：
（ 1） R’是自反的（对称，可传递的）；
（ 2） RR ?'
（ 3）对于任一自反（对称，传递的）关系 R’’，若
RR ?'',则 ''' RR ?
则称 R’是 R的自反（对称，传递的）闭包，
并依次用 r(R),s(R),t(R)来表示之。
§ 7关系的闭包运算
讨论定义：
（ 1）已知一个集合中的二元关系 R，则
r(R),s(R),t(R)是唯一的，它是包含 R的最小的自反
（对称，传递）关系；
（ 2）若 R是自反（对称，传递）的，则
r(R),s(R),t(R)就是 R本身。
（ 3）若 R不是自反（对称，传递）的，则我们可
以补上最少序偶，使之变为自反、对称、传递关系，
从而得到 r(R),s(R),t(R)；
§ 7关系的闭包运算
例：设 X={a,b},R={<a,a><a,b>}，
r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},
t(R)={<a,a><a,b>}=R
例：求 t(R)需要特别小心，要进行多次添项。
设 X={a,b,c},R={<a,b><b,c><c,a>}，求 r(R),s(R),t(R)
解,r(R)= },,,,,,{ ????????????? ccbbaaaccbbaIR x?
s(R)= },,,,,,{~ ????????????? caacbccbabbaRR ?
t(R)={<a,b><b,c><c,a><a,c><b,a><c,b><a,a><b,b><c,c>}
§ 7关系的闭包运算
,定理,,给定集合 X,R是 X中的二元关系，于是可有：
（ 1）当且仅当 r(R)=R，则 R是自反的；
（ 2）当且仅当 s(R)=R，则 R是对称的；
（ 3）当且仅当 t(R)=R，则 R是可传递的。
xI
,定理,, R是 X中的二元关系 是 X中的恒等关系，
则有
xIRRr ??)(
证明：按定义证,（ 1） 设 xIRR ??',则 R’是自反的，
RR ?')2(
§ 7关系的闭包运算
（ 3）设有任一 R’’也是自反的，且
则
RRIR x ??? ''''
''')('' RRIRR x ??? ?
xIRR ??? '
,定理,,给定集合 X,R是 X中的二元关系，则有
RRRS ~)( ??
,定理,,设 X是一集合,R是 X中的二元关系，则：
)(,)( 12 ??? ??? IiRURRRt ii???
§ 7关系的闭包运算
例,X={a,b,c},R={<a,b><b,c><c,a>},|X|=3,
则
,
},,,{
},,,,{
4
3
2
RR
ccbbaaR
bcabcaRRR
?
???????
???????? ?
},,,,,,,,,{
)( 32
???????????????????
??
ccbbaabcabcaaccbba
RRRRt ??
,定理,,设 |X|=n,R是 X中的二元关系，则
kRRRRt ???? 2)( ? )0( nK ??
§ 7关系的闭包运算
例,X={a,b,c,d},R={<a,b><b,c><c,d>},
则 ?????????? 432 },,{},,,{ RdaRdbcaR
},,,,,,{
)( 432
????????????
??
dadbcadccbba
RRRRRt ???
,定理,,设 X是一集合,R是 X中的二元关系，则有：
（ 1） r(S(R))=S(r(R));
（ 2） r(t(R))=t(r(R));
（ 3） t(S(R)) ? S(t(R))。
§ 7关系的闭包运算
证明：（ 1） r(S(R))
)~~()(
~)~(
xx
x
IRIR
IRRRRr
???
???
?
??
)()(~)(
)~()(
RSrRrRr
IRIR xx
??
?
?
???
常用下列符号表示一些闭包：
“R加”,)(RtR ??,传递闭包，
nn
i
i RRRRR ????? 21
1
??
?
?
“R星”,)()(* RrtRtrR ??,自反可传递闭包，
??? n
i
i
x RIRtRR
1
0* )(
?
??
§ 7关系的闭包运算
例：设 X={a,b,c},R={<a,b><c,c>}
（ 1） rS(R)=r{<a,b><b,a><c,c>}
={<a,b><b,a><c,c><a,a><b,b>}
Sr (R)=s{<a,b><c,c><a,a><b,b>}
={<a,b><b,a><c,c><a,a><b,b>}
（ 2） rt(R)=r{<a,b><c,c>}={<a,b><c,c><a,a><b,b>}
tr(R)=t{<a,b><c,c><a,a><b,b>}={<a,b><c,c><a,a><b,b>}
（ 3） tS(R)=t{<a,b><c,c><b,a>}
={<a,b><c,c><b,a><a,a><b,b>}
St(R)=S{<a,b><c,c>}={<a,b><c,c><b,a>}
∴ t(S(R)) ? St(R)
§ 8集合的划分和覆盖
,定义,,给定一非空集合Ｓ，又设 },{
21 mAAAA ??
若（ 1） ),2,1(,miSA
i ???
（ 2） ?m
i
i SA
1?
?
则称 A为 S的覆盖。
例,S={a,b,c},A={{a,b},{b,c}},B={{a},{a,b},{c}}，
C={{a},{b},{c}},D={{a},{b},{a,c}}
均为 S的覆盖。
§ 8集合的划分和覆盖
例：四个半圆覆盖一正方形。
,定义,,给定一非空集合 S，设非空集合 },{
21 mAAAA ??
如果有,),2,1(,)1( miSA
i ???
??ji AA ?)2( 或
ji AA ?
?m
i
i SA
1
)3(
?
?
（ i,j=1,2…,m ）
§ 8集合的划分和覆盖
则称集合 A是集合 S的一个划分。
讨论定义：
（ 1）划分和覆盖主要差别在第（ 2）条；
（ 2）划分 A中的元素，称为划分的类，在定义中
mAAA ?21,
均是 A中的一个类，类的个数称为划分的秩；
（ 3）若 A为有限集合，则 A的秩是有限的，为 |A|，
若 A为无限集合，则划分的秩是无限的；
（ 4）集合的划分必定是一个覆盖，而覆盖不一定是划分；
（ 5）集合 S上的秩最大的划分称最大划分，最小的称最小划分。
§ 8集合的划分和覆盖
例：设 S={a,b,c}，下列
iA
均为 S的一个划分：
}},{},{{1 cbaA ? 类有二个 {a},{b,c},∴ || 1A =2（秩）；
}}{},,{{2 cbaA ? 类有二个 {a,b },{c},∴ || 2A =2（秩）；
}}{},,{{3 bcaA ? 类有二个 {a,c},{b},∴ || 3A =2（秩）；
}}{},{},{{4 cbaA ? 最大划分，秩为 3=|S|；
}},,{{5 cbaA ? 最小划分，秩为 1。
例：四个直角三角形
组成了正方形的一个划分
秩 =4
§ 8集合的划分和覆盖
,定义,,设 A和 A’是非空集合 S的二种划分，并可表示成：
,}{
1
?m
i
iAA
?
? ?n
i
jAA
1
}{'
?
? 若 A’的每一个类 jA
都是 A的某一个类
iA
的子集，则称划分 A’是划分 A的加细，
或讲 A’加细了 A，若 A’加细了 A且 'AA ?
则称 A’是 A的真加细。
讨论定义：
A’加细了 A，一定有 |A’|≥|A|（秩），
若 |A’|>|A|，则一定为真加细。
§ 8集合的划分和覆盖
例,S={a,b,c,d},S的划分,A={{a,b},{c,d}},
A’={{a}{b}{c,d}}，则 A’是 A的真加细
A’’={{a}{b}{c}{d}},则 A’’ 是 A的真加细
§ 9等价关系 与等价类
,定义,,设 X是一个集合,R是 X中的二元关系，若 R是自
反的，对称的和可传递的，则称 R是等价关系。
例：下列关系均为等价关系
（ 1）实数（或 I,N集上）集合上的,=”关系（相等）
（ 2） {人类 } 中的同姓关系
（ 3）命题集合上的等价关系
例：设 X={1,2,3,4,5,6,7}，
3,|,{
yxXyxyxR ?????? 为整数 }
§ 9等价关系 与等价类
试验证 R是等价关系，画出 R的关系图，列出 R的关系矩阵
解：（ 1） R={<1,1><1,4><1,7><2,2><2,5><3,3><3,6><4,1>
<4,4><4,7><5,5><5,2><6,6><6,3><7,7><7,4><7,1>}
（ 2） R的关系矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1 0 0 1 0 0 1
0 0 1 0 0 1 0
0 1 0 0 1 0 0
1 0 0 1 0 0 1
0 0 1 0 0 1 0
0 1 0 0 1 0 0
1 0 0 1 0 0 1
R
M
§ 9等价关系 与等价类
R满足自反、对称和可传递的,∴ R是一等价关系
,定义,,设 ??Im Iyx ?,
若对于某个整数 n有 (x-y)=n ? m,n
m
yx ?? （整数），
则称 x模 m等于 y，记作,)( m o d myx ?
,定理,,任何集合 IX ?
（ I的任何子集 X中）的模 m等价，是一个等价关系。
§ 9等价关系 与等价类
,定义,,设 R是 X集合中的等价关系，对于任何的
Xx? 来讲，可把集合 ? ? Xx R ? 规定成：
? ? }|{ yR xXyyx R ??? 并称是由 Xx? 生成的 R等价类。
讨论定义：
（ 1）等价类 ??
Rx
是一个集合，由定义中可见 ? ? Xx R ?
（ 2） ??Rx 中的元素是在等价关系 R中，所有与 x
具有关系的元素所组成的集合，且 ? ? ??
Rx
§ 9等价关系 与等价类
例：设 X={a,b,c,d},R是 X中的等价关系，
R={<a,a><b,b><a,b><b,a><c,c><d,d><c,d><d,c>}
则
RR ddcc ][},{][ ??
RR bbaa ][},{][ ??
,定理,,设 X是一个集合,R是 X中的等价关系，则
（ 1）若 Xx?,则 Rxx ][?
（ 2）对于所有的 Xyx ?,，或者 RR yx ][][ ? 或者 ??RR yx ][][ ?
（ 3） ?
Xx R
Xx
?
?][
§ 9等价关系 与等价类
例：设 X=N，关系 R={ )(|,yxXyXxyx ??????? 可被 3整除 }
是一等价关系,则 R可以找出三个等价类：
R]0[ ={0,3,6,9…},此集合中的元素除以 3的余数为,0”；
R]1[ ={1,4,7,10…},此集合中的元素除以 3的余数为,1”；
R]2[ ={2,5,8,11…},此集合中的元素除以 3的余数为,2”。
例,X为全班同学的集合，则班中同姓关系是一个等价关系，
（ 1）任何一个人均 ∈ 某一个等价类，王某某 ∈ [王 ] R
张某 ∈ [张 ]R…
§ 9等价关系 与等价类
（ 2）任何二个姓的等价类，只有二种可能
一种,[王 ] R= [王 ] R
二种,[王 ] R?[李 ]R=?
（ 3）全班同学的集合 =同姓关系等价类的并集 =[王 ] ?
R
[李 ]?
R
…
（ 4）所有等价类的集合，一定导致全班同学集合
的一个划分,A={[王 ]R,[李 ]R….}
§ 9等价关系 与等价类
,定理,,设 X是一非空集合,R是 X中的等价关系,R
等价类的集合 {[x]R| x∈ X}是 X的一个划分，且此集合
称为 X按 R的商集，用 RX 表示之。
例：设 X={x1,x2…..x n}
（ 1） X集合中的全域关系,XXR ??1,它是一个等价关系，
Xx R ?1][ |||][| 1 Xx R ?
∴ X按 R1的商集 1||},|]{[
11
??? RXXxxRX R
它形成了 X的一个最小划分
§ 9等价关系 与等价类
（ 2） X中的恒等关系
xIR ?2
??? }|]{[ 2
2
XxxRX R }][]{[ 221 RnR xx ? ),( 21 Xxxx n ??
它形成了 X的一个最大划分
例,X为全班同学的集合,|X|=n,(n∈N)
（ 1）同学关系 R1是一个等价关系,}{
1 XR
X ?
（ 2）按指纹的相同关系 R2是一个等价关系，
}][]{[ 221
2 RnR
xxRX ??
它形成了全班同学的最大划分
§ 9等价关系 与等价类
（ 3）同姓关系 R3是一等价关系
?3RX {[张 ] R3,[李 ]R3,… }
它形成了全班同学的既不是最大，又不是最小划分
§ 9等价关系 与等价类
,定理,, X是一非空集合,A为 X的一个划分，且
A={A1,A2,….A n}，则由 A导出的 X中的一个等价关系
)(1 iini AAR ??? ?
例,X＝ {a,b,c,d},A={{a,b},{c,d}}
则 R＝ ({a,b} × {a,b})?({c,d} × {c,d})
={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}
由此我们看到：集合 X上的等价关系与 X的划分之间有对
应关系。
§ 10相容 关系
,定义,,给定一个集合 X,R是 X中的二元关系，如果
R是自反、对称的，则称 R是相容关系。
例：设 X={ball,bed,dog,let,egg},5个英文单词
定义 X中一个二元关系：
R={ yxXyxyx,,|,???? 有相同的字母 }
则 R是自反的，对称的，但不可传递
∵ (ball R bed) ?(bed R egg) (ball R egg)??
则 R={<1,1><1,2><2,1><1,4><4,1><2,2><2,3><3,2> <2,4>
<4,2><2,5><5,2><3,3><3,5><5,3><4,4><4,5><5,4><5,5>}
§ 10相容 关系
§ 10相容 关系
,定义,,设 X是一个集合,R是 X中的相容关系，假定
A?X，若任一 x∈ A都与 A中的其它所有元素有相容关
系，而（ X-A）中没有一个元素与 A中的所有元素有相
容关系，则称子集 A为相容关系 R的一个最大相容类。
例：上例中 }5,4,2{},5,3,2{},4,2,1{
321 ??? AAA
均是 X中的最大相容类,且 321 AAAX ???
},,{ 321 AAA 定义了 X的一个覆盖。
同样已知 X集合的一个覆盖 },,{
321 AAA
§ 10相容 关系
则一定可以求出相对应的相容关系来：
332211 AAAAAAR ???? ??
讨论等价关系和相容关系后可得到结论：
集合 X上的相容关系 R的所有最大相容类集合
{A1,A2,….A m}构成集合 X的一个覆盖。即：
i
m
i
AX
1?
? ?
而集合 X上的等价关系 R的所有等价类集合构成 X的一个
划分
§ 10相容 关系
求最大相容类的方法：
关系图法：确定最大完全多边形
每个顶点都与其他所有顶点相联结的多边形。
(1)孤立结点是最大的完全多边形；
(2)二个相互联结的结点是最大完全多边形；
(3)三角形是三个结点的最大完全多边形；
§ 10相容 关系
(4)四个结点；
(5)五个结点 ;
画出简化相容关系的关系图后，
先结点最多的完全多边形，以后逐次减少。
§ 10相容 关系
例：已知相容关系图，求出最大相容类
§ 10相容 关系
}5,4{
}5,2{
}3,2{
}4,3,1{
4
3
2
1
?
?
?
?
X
X
X
X
}4,3{
}5,4,1{
}6,5,2,1{
3
2
1
?
?
?
X
X
X
最大相容类集合为
}}4,3}{5,4,1}{6,5,2,1{{} },5,4}{5,2}{3,2}{4,3,1{{ 21 ?? SS
§ 11序关系
,定义,,设 R是 P中的二元关系，如果 R是自反的，反
对称和可传递的，则称 R是 P中的偏序关系（或称偏
序），并用符号,≤”表示，而序偶 〈 P,≤〉 则称为
偏序集合。
讨论定义：
（ 1）,≤”不单纯意味着在实数中的 ≤关系，而是代表更为
普遍的关系（具有自反，反对称和可传递性的关系）；
（ 2）若 Pyx ?,，,x≤y”读作：
“x小于或等于 y”“y包含 x”“x在 y的前面”等；
§ 11序关系
（ 3） R是集合 P中的偏序关系，则 R~
也是 P中的偏序关系，即 R用,≤”表示,R~
则用,≥”表示；
（ 4）若 〈 P,≤〉 是一个偏序集合，则 〈 P,≥〉 也一定是
偏序集合，且偏序集合是一个序偶，左元素为集合 P，右
元素为偏序关系。
例：
（ 1）在领导机构的集合中“领导和被领导的关系”是
偏序关系；
（ 2）在 I（整数）集合中，,≤”、,≥”均是偏序关系；
§ 11序关系
例：
}8,6,3,2{4 ?I
4I 中的,≤”（整除） ={<2,2><2,6><2,8><3,6><3,3><6,6><8,8>}
而,≥”（整倍数） ={<2,2><6,2><8,2><3,3><6,3><6,6><8,8>}
均是偏序关系。
§ 11序关系
,定义,, R是集合 X中的二元关系，若 R是非自反的，
反对称的和可传递的，则称 R是拟序关系（串序），
并用符号,<”表示。而 〈 X,<〉 称为拟序集合。
讨论：
（ 1）拟序关系一定反对称的
（ 2）拟序关系也可用偏序关系来定义：
?
?
?
?????
?????
yxyxyx
yxyxyx
§ 11序关系
,定义,,设 〈 P,≤〉 是一个偏序集合，若对于每一个
Pyx ?,，或者 x≤y，或者 y≤x，即
)( xyyxPyPxyx ?????????,则,≤”
称为全序关系，而 〈 P,≤〉 称为全序集合（线序集合）。
,定义,,在偏序集合 〈 P,≤〉 中，若 Pyx ?,
且具有 x≤y或 y≤x，则称 x和 y是可以比较的，
否则称 x,y是不可比较的。
,推论,,在偏序集合中，一般情况下，一定是有的元素可以
比较的，有的元素是不可比较的。
在全序关系中，所有的元素均是可以比较的。
§ 11序关系
,定义,,若集合 X上的二元关系 R是全序关系，且 X的
任一非空子集，都有一个最小元素，则称 R为良序关
系，并称 <X,R>为良序集合。
讨论定义：
（ 1）良序关系比全序关系多了一个条件，即在全序关系中，
X集合的任一非空子集均有一个最小元素；
（ 2）每一个有限集合 X上的全序关系必定是良序关系。
例：设 A={1,2,3,4}
定义 A上的,≤” ={<1,1><1,2><1,3><1,4><2,2><2,3>
<2,4><3,3><3,4><4,4>}
§ 11序关系
２．偏序集合和哈斯图
,定义,,在偏序集合 〈 P,≤〉 中，若有 Pyx ?,
且 x≤y和 yx ?,又不存在其它元素 z能使 yzzx ???
则称元素 y盖住 x，盖住集记为 COV(P)=;,|,{ Pyxyx ??? Y盖住 x}
给定偏序集 〈 P,≤〉,它的盖住集是唯一的。我们可以画
出盖住集的关系图，称为 〈 P,≤〉 的哈斯图。
§ 11序关系
（ 2）若 Pyx ?,，且 x≤y和 yx ?,则把 x画在 y的下面；
（ 3） 若 y盖住 x，则在 x和 y之间画一条联线，并箭头向上，
若 y不盖住 x，但又存在,≤”关系，则必定通过 x和 y
之间的其它中间结点把 x和 y联结起来；
（ 4） 所有边的方向均是向上的，所以实际画时，
箭头均可省去。
例,(a)设 }4,3,2,1{
1 ?P
“≤”表示 P中元素的小于和等于关系，
（ 1）用,?”表示 P中的结点（具有自反性）；
画 〈 P,≤〉 的哈斯图的方法：
§ 11序关系
则 〈 P1,≤〉 是一偏序集合，全
序集合，良序集合
其哈斯图为：
(b)若设 }},,}{,{},{,{
2 cbabaaP ??
???,2P 是一偏序集合，
例：设 X={2,3,6,12,24,36}
“≤”定义为：若 ???? XyXx
x整除 y，则 x≤y，
〈 X,≤〉 是一偏序集合,
§ 11序关系
例,(a)设 X={a,b},ρ(X)=
}},{},{},{,{ baba?
??? ),( X? 是一偏序关系，
其哈斯图为：
(b)设 X={a,b,c}
的哈斯图为：
??? ),( X?
§ 11序关系
,定义, 设 <P,≤> 为一偏序集，且 Q?P
(1)若对每一个 q’ ∈ Q有 q≤ q’,则称 q∈ Q为 Q的最小元素。
(2)若对每一个 q’ ∈ Q有 q≥ q’,则称 q∈ Q为 Q的最大元素。
(3)若 q∈ Q，且不存在一个 q’ ∈ Q，使 q’ ? q且 q’ ≤ q，
则称 q为 Q的极小元素。
(4)若 q∈ Q，且不存在一个 q’ ∈ Q，使 q’ ? q且 q’ ≥ q，
则称 q为 Q的极大元素。
讨论：
(1) q∈ Q,?Q的极大，小，最大，小元，若有的话，必
定在 Q中。
§ 11序关系
(2)最大，最小元是 Q中所有元素比较而言的，
极大，极小元是对 Q中能够比较的元素而言的。
(3)Q中如有最大，最小元则一定是唯一的，极大，极
小元一定存在，且不一定是唯一的。
,定义, 给 <P,≤>,且 Q?P，若
(1)对每个 q’ ∈Q 有 q’ ≤q,则称 q∈P 为 Q的上界，其中最小
的一个，称为 Q的最小上界，记为 LUB(上确界 )。
(2)对每个 q’ ∈Q 有 q’ ≥q,则称 q∈P 为 Q的下界，其中最大
的一个，称为 Q的最大下界，记为 GLB(下确界 )。
§ 11序关系
讨论定义：
(1)上，下界是对 Q中所有元素比较而言的。
(2)Q若有上，下界，则不一定是唯一的。
(3)Q若有 LUB,GLB，则 Q一定有上，下界，且是唯
一的。
(4)Q的上，下界,LUB,GLB，则可能在 Q中，可能
不在 Q中，但一定在 P中。
§ 11序关系
例：设 X={a,b,c},??? ),(X?
是一偏序集合，
其哈斯图如右，
求下列子集的上界、下界、
最小上界和最大下界
§ 11序关系
子集 上界 LUB 下界 GLB
{{a}{c}} {a,c}{a,b,c} {a,c} ? ?
{{a}{b}{c}} {a,b,c} {a,b,c} ? ?
{{a,b}{c}} {a,b,c} {a,b,c} ? ?
{{a,b}{b,c}} {a,b,c} {a,b,c} {b},? {b}
{{a,c}{c}} {a,c}{a,b,c} {a,c} {c},? {c}
{{b}} {b}{a,b}{b,c}{a,b,c} {b} {b},? {b}
集合论是研究集合的一般性质的数学分支，它
研究集合不依赖于组成它的事物的特性的性质。
在现代数学中，每个对象（如数、函数等）本
质上都是集合，都可以用某种集合来定义。数学
的各个分支，本质上都是在研究这种或那种对象
的集合的性质。集合论已成为全部现代数学的理
论基础。
集合论的特点是研究对象的广泛性。它总结出
由各种对象构成的集合的共同性质，并用统一的
方法来处理。因此，集合论被广泛地应用于各种
科学和技术领域。
集 合 论
由于集合论的语言适合于描述和研究离散对象
及其关系，所以也是计算机科学与工程的理论基
础，在程序设计、关系数据库,排队论、开关理
论，形式语言和自动机理论等学科领域中都有
重要的应用。
本篇主要介绍：集合、二元关系和函数，
以及集合的基数问题。
集 合 论
第三章 集合与关系
§ 1集合的概念和表示法
§ 2集合的运算
§ 3序偶与笛卡尔积
§ 4关系及其表示
§ 5关系的性质
§ 6复合关系和逆关系
§ 7关系的闭包运算
§ 8集合的划分和覆盖
§ 9等价关系与等价类
§ 10相容关系
§ 11序关系
§ 1集合的概念和表示法
1、集合与元素
（ 1）集合：具有某种特殊性质的客体的聚合。
讨论：
① 一些不同的确定的对象之全体。
② 客体：是泛指一切，可以是具体的、抽象的
③ 元素（成员）：属于任何集合的任何客体。
④符号,用大写英文字母表示集合，用小写英文字母或
其它符号表示元素。
集合,A,B….
元素,a,b…,
§ 1集合的概念和表示法
⑤ 元素与集合间的关系,若 a是集合 S中的元素，则
可写成 a? S ；若 b不是集 S合中的元素，则可
写成 b? S 。
⑥ 集合 S的基数 (势 ),S中的元素个数。用 |S|表
示。
⑦ 有限集合：集合的基数（元素）是有限的。
无限集合：集合的基数（元素）是无限的。
§ 1集合的概念和表示法
⑧ 本书中常用集合符,
Im(m≥1) 有限个正数的集合 {1,2,3……m}
Nm(m≥0) 有限个自然数的集合 {0,1,2……m}
以上是有限集合,下面是无限集合：
N 自然数集合 {0,1,2……}
I+ 正整数集合 {1,2,3……}
I 整数集合 {…… -1,0,1,2……}
P 素数集合 {大于 1的正整数，只能被 1和自己整除 }
Q 有理数集合 {i/j,i,j均为整数且 j≠0}
R 实数集合 {有理数、无理数 }
C 复数集合 {a+bi,a,b可为实数 i= √-1 }
§ 1集合的概念和表示法
(2)集合的表示方法,
(a)枚举法 (列举法 )
把集合的元素列于花括号内。
例：
命题的真假值组成的集合,S={T,F}
自然数 0,1,2,3,4五个元素的集合,P={0,1,2,3,4}
(b)谓词公式描述法
所有集合均可用谓词公式来表示,S={x | p(x) }
§ 1集合的概念和表示法
例：大于 10的整数的集合,S1={x | x? I ∧ x>10}
偶整数集合,S2={x | ?y (y ?I ∧ x=2y)}
有限个元素集合：
S3={1,2,3,4,5}={x | x ?I ∧ (1 ≤ x ≤ 5) }
S4={F,T}={x | x=T ∨ x=F}
S5={1,4}={ x | (x2-5x+4=0) }
(c)同一集合可以用多种不同的形式表示。
(d)集合也可作为某一集合的元素。
例,S={a,{1,2},p,{q}}
§ 1集合的概念和表示法
(3)三个特殊集合：空集、全集合、集合族
,定义, 如果一个集合包含了所要讨论的每一个集合，
则称该集合为全集合，简称全集，用 E表示。
E={x | p(x) ∨ ? p(x)} p(x)为任何谓词公式
,定义, 不拥有任何元素的集合称为空集（或称零集），
用 ?表示
?={x | p(x) ∧ ? p(x) }={ }
注意,?≠ {?} 前者是空集，是没有元素的集合；后
者是以 ?作为元素的集合。
§ 1集合的概念和表示法
,定义, 集合中的元素均为集合，称这样的集合为集合
族。
例 A={{a},{b},{c,d}}
2、集合之间的关系
,公理, 给定二个集合 A和 B，当且仅当 A和 B具有同样
的元素（成员），则 A和 B才是相等的，记作 A=B
并规定：（ A=B） ??x (x? A ? x ? B)
例,{a,b,c}={b,a,a,c,c}
§ 1集合的概念和表示法
例,{a,b,c}={b,c,a}
例：设 P={{1,2},4},Q={1,2,4}，则 P?Q
,定义, 设 A,B是任意二个集合，如果集合 A的每一个
元素都是 B的一个元素，则称 A 是 B的子集，或者说 A
包含于 B，或者说 B包含 A，记作 A?B，或者 B?A。
并规定,A?B?B?A??x(x?A → x ?B)
§ 1集合的概念和表示法
例,A1={1,2,3} A2={0} A3={1,2,3,0} B={1,2,3,0}
则 A1,A2,A3均为 B的子集合，并记为
A1?B,A2?B,A3?B
,定义, 设 A,B是任意二个集合，若 A?B且 A≠B，则称
A是 B的真子集，记作 A?B（ A真包含于 B）
并规定,A?B?（ A?B ∧ A≠B）
§ 1集合的概念和表示法
注意：区分,?”和,?”的关系：
,?”关系是指集合和该集合中元素之间的关系。
例,S={a,{b},c} 则 a? S,{b}?S,c?S
而,?”关系是指二个集合之间的关系。
例,S1={a,b} S2={a,b,1,2} 则 S1? S2
若 A不包含于 B，则也可表示成 A?B
,定理, 设 E是全集,A是一个集合，则一定有 A?E。
证明,?x（ x? A → x ? E） 而 x? E始终为,T”，
所以 x? A → x ?E一定为,T”
故有 ?x（ x? A → x ? E）为,T”，则有 A?E
§ 1集合的概念和表示法
,定理, 设 A,B是任意二个集合，当且仅当 A?B和 B?
A才有 A=B。
证明：
(ⅰ )充分性：（ A=B） ?（ A?B ∧ B? A）
(A=B)??x (x ?A→ x ?B∧ x?B→ x ?A)
??x(x?A→ x ?B)∧ ?x(x?B→ x ?A)
?(A?B)∧ (B?A)
(ⅱ )必要性,A?B∧ B?A?A=B
(A?B)∧ (B?A)??x(x?A→ x ?B)∧ ?x(x?B→ x ?A)
?(A=B)
§ 1集合的概念和表示法
,推论, 对于任一集合 A，则有 A?A。
,定理, 设 A,B,C是任意集合，如果 A?B和 B?C，则
A?C 。
,推论, 若 A?B和 B?C，则 A?C 。
,定理, 设有空集 ?和任一集合 A，则 ??A
证明：设 x?A，要证明 ??A，只要证,?x(x??→ x ?A)
为,T”
∵ ?中没有元素，
∴ x??为假,?x（ x??→ x ?A）为,T”
,定理, ?是唯一的 。
§ 1集合的概念和表示法
证明：设有二个空集合 ?1和 ?2
∵ ?是任何集合的子集
∴ （ ?1??2∧ ?2 ??1） ?(?1=?2)
3、幂集和索引集合
（ 1）幂集：
例：给定 S1={a} 则子集为 ?,{a}
S2={1,{2}} 则子集为 ?,{1},{{2}},{1,{2}}
S3=? 则子集有 ?（而不是 {?}）
由此可见：给定一个集合 S，则 ?和 S一定是 S的子集。
§ 1集合的概念和表示法
,定义, 设 A是集合,A的所有子集（作为元素）的集
合称为 A的幂集。
记作 ρ(A)或 2A 且有,ρ(A)(=2A)={x | x ?A}
例：若 A1=?，则 ρ(A1)={?}
若 A2={a}，则 ρ(A2)={?,{a}}
若 A3={1,2}，则
ρ(A3)={?,{1},{2},{1,2}}
§ 1集合的概念和表示法
讨论定义：
(a)集合的元素个数称为集合的“基数”或叫“势”
|ρ(S)|=2 |s| 为幂集 ρ(S)的基数
(b) 若 A为有限集合，则 ρ(A)也为有限集合。
若 A为无限集合，则 ρ(A)也为无限集合。
(c)一定有 A?ρ(A),??ρ(A)，
即对非空集合，在幂集中至少有两个子集 ?和 A。
§ 1集合的概念和表示法
（ 2）索引集合
为了在计算机上表示集合，必须给每一个集合的元素加
上标记，以用来表示元素在集合中的位置。
例,S1={a,b} 假设集合 S1中,a,b的位置已经固定。
则用二进制下标法来表示 S的所有子集：
?={ }=B00,{a}=B10,{b}=B01,{a,b}=B11
这样 ρ(S1)={B00,B01,B10,B11}={Bi | i?J}
而其中 J={00,01,10,11} （索引集合或指标集合）
§ 1集合的概念和表示法
例：
已知集合 S={a1,a2,a3,a4,a5,a6},S的子集
有 26 个
可以分别表示成 B0,B1……B ( 26-1)
则 B7=B000111={a4,a5,a6}
B15=B001111={a3,a4,a5,a6}
B22=B010110={a2,a4,a5}等等
§ 2 集合的运算
1.交集（交运算）
,定义, 任何二个集合 A和 B的交集 A∩B是由 A和 B所共有的
全部元素构成的集合，
即,A∩B={x | x? A∧ x ?B}
例,A={a,b} B={a,c} A∩B={a}
,定理, 集合的相交运算是可交换的和可结合的，即对于任
何集合 A,B,C有
A∩B=B∩A，（ A∩B） ∩C=A∩（ B∩C）
证明：设 x是 A∩B中任一元素
则 x? A∩B?x? {x | x? A ∧ x? B}
?x ?{x | x? B ∧ x? A}?x? B∩A
∴ A∩B=B∩A
§ 2 集合的运算
,定理, 设 A是 E的任一子集，则有
（ 1） A∩A=A
（ 2） A∩?=?
（ 3） A∩E=A
,定义, A,B是二个集合，若 A∩B=?，则称 A和 B是
不相交的，或者说 A和 B没有相同的元素。
若 C是一个集合族 （集合族：元素均为集合的集合）使
C的任何二个元素都不相交，则称 C为不相交的集合
族。
例,A={{a},{b},{c}} A为不相交的集合族
§ 2 集合的运算
2.并集（并运算）
,定义, A,B是任意二个集合,A和 B的并集 A∪ B是由
A和 B的所有元素构成的集合，
即,A∪ B={x│ x?A∨ x?B}。
例,A={a,b,c} B={1,2,3} 则
A∪ B={a,b,c,1,2,3}
,定理, 集合的并运算是可交换的和可结合的，即对任
何 A,B,C有
A∪ B=B∪ A和（ A∪ B） ∪ C=A∪ （ B∪ C）
§ 2 集合的运算
,定理, 集合的并和交运算，每一个对另一个都是可分
配的。
即,(1)A∪ （ B∩C） =（ A∪ B） ∩（ A∪ C）
(2)A∩（ B∪ C） =（ A∩B） ∪ （ A∩C）
,定理, 设 A,B,C是全集 E的任意子集，则有：
(1)A∪ A=A
(2)A∪ ?=A
(3)A∪ E=E
§ 2 集合的运算
3.相对补集：
,定义, 设 A和 B是二个任意集合,B对 A的相对补集
（ A-B）是由 A中且不属于 B的所有元素组成的集合。
即：
A-B={x│x?A∧ x?B}={x│x?A∧ ?x?B} 。
例：设 A={0,1,2} B={2,3,4}
则 A-B={0,1} B-A={3,4}
∴ A-B≠B-A相对补集不满足交换律。
§ 2 集合的运算
,定理, 设 A,B,C,D是 E的子集，则有：
(1 )A-B?A，
(2 )若 A?B和 C?D，则 A∩C?B∩D，
(3 )若 A?B和 C?D，则 A∪ C?B∪ D，
(4 ) 若 A?A∪ B，则 B?A∪ B
(5 ) 若 A∩B?A，则 A∩B?B
(6 ) 若 A?B，则 A∪ B=B
(7 ) 若 A?B，则 A∩B=A
(8 )A-?=A
(9 )A∩(B-A)=?
(10)A∪ (B-A)=A∪ B
§ 2 集合的运算
(11)A-（ B∪ C） =（ A-B） ∩（ A-C）
(12)A-（ B∩C） =（ A-B） ∪ （ A-C）
4、绝对补集（补运算 ）
,定义, 设 E是全集，任一集合 A对 E的相对补集称为 A
的绝对补集（或称补集）记作 ~A（或 ?A）。即：
~A=E-A={x| x?E∧ x?A}={x| x?A}
§ 2 集合的运算
例：设 E={a,b,c,d} A={a,b} 则 ?A={c,d}
,定理） A是 E的任一子集，则有
(1)A∪ ?A=E
(2)A∩?A=?
,定理） 设 A,B是 E的二个子集，当且仅当 A∪ B=E
和 A∩B=?才有
B= ~A（或 A= ~ B）
§ 2 集合的运算
证明,(ⅰ ) 充分性：
B= ~A ?（ A∪ B=E） ∧ （ A∩B=?）
∵ B=~A
∴ A∪ B=A∪ ~A=E
A∩B=A∩~A=?成立
(ⅱ )必要性：
(A∪ B=E)∧ (A∩B=?)?B=?A
∵ B=E∩B=(A∪ ~A)∩B=(A∩B)∪ (~A∩B)
=?∪ （ ~A∩B）
=（ ~A∩A） ∪ （ ~A∩B） =~A∩（ A∪ B）
=~A∩E=~A
§ 2 集合的运算
补集的性质：
（ 1） ~（ ~A） =A
（ 2） ~（ A∪ B） =~A∩~B
（ 3） ~（ A∩B） =~A∪ ~B
（ 4） ~?=E
（ 5） A-B=A∩~B
例：设 A={2,5,6},B={2,3,4},C={1,3,4}，
E={1,2,3,4,5,6}
则 A-B={5,6}=A∩~B={2,5,6}∩{1,5,6}={5,6}
§ 2 集合的运算
5、环和 (对称差 )
,定义, 设 A,B是任意二集合,A和 B的环和记作 A⊕ B。
即：
A⊕ B=(A-B)∪ (B-A)=(A∩~B)∪ (B∩~A)
或者 x?(A⊕ B)?x?{x |x?A?x?B}
例：
设 A={2,5,6},B={2,3,4}
则 A?B={3,4,5,6}
§ 2 集合的运算
对称差的性质：
(1)A?B=B?A 可交换的
(2)(A?B)?C=A?(B?C) 可结合的
(3)A?B=(A-B)∪ (B-A)
=(A∩~B)∪ (B∩~A)=(A∪ B)∩(~A∪ ~B)
(4)A?A=?
(5)A??=A
(6)~A?~B=(~A∩~(~B))∪ (~B∩~(~A))
=(~A∩B)∪ (~B∩A)=(B-A)∪ (A-B)=A?B
(7)A∩(B?C)=(A∩B)?(A∩C) (∩对 ?是可以分配的 )
§ 2 集合的运算
6、文氏图
(1)文氏图的画法规则：
规定矩形表示 E。子集用圆画在 E中。
(2)文氏图应用：
（ a）表示集合和运算的关系
可用文氏图画出各种运算：
（ b）证明集合恒等式
例,A?（ B?C） =（ A?B） ?（ A?C）
§ 3 序偶与笛卡尔乘积
1.序偶：
,定义, 由二个具有给定次序的客体所组成的序列称为序偶。
记作 〈 x,y〉
例,X—Y二维平面上的一个点的坐标 〈 x,y〉 就是一个序
偶。
说明：在序偶中二个元素要有确定的排列次序。即：
若 a?b时，则 〈 a,b〉 ?〈 b,a〉
若 〈 x,y〉 =〈 a,b〉 ?（ x=a?y=b）
下面定义多重序元：
三重序元 〈 x,y,z〉 =〈〈 x,y〉, z〉
n重序元 〈 x1,…,x n〉 =〈〈〈〈 x1,x2〉, x3〉 … 〉, xn〉
§ 3 序偶与笛卡尔乘积
2.笛卡尔乘积
,定义, 设 A,B为二个任意集合，若序偶的第一个成员
（左元素）是 A的一个元素，序偶的第二个成员
（右元素）是 B的一个元素，则所有这样的序偶的
集合称为 A和 B的笛卡尔乘积。
记作,A?B={〈 x,y〉 |（ x?A） ?（ y?B） }
例：设 A={1,2} B={a,b}
则 A?B={〈 1,a〉, 〈 1,b〉, 〈 2,a〉, 〈 2,b〉 }
B?A={〈 a,1〉, 〈 a,2〉, 〈 b,1〉, 〈 b,2〉 }
∴ A?B?B?A 即,?”是不满足交换律。
§ 3 序偶与笛卡尔乘积
例：设 A={a,b},B={1,2},C={z}
则 (A?B)?C={〈 a,1〉,〈 a,2〉,〈 b,1〉,〈 b,2〉 }?{z}
={〈 a,1,z〉,〈 a,2,z〉,〈 b,1,z〉,〈 b,2,z〉 }
A? ( B?C ) ={a,b}?{〈 1,z〉,〈 2,z〉 }
={〈 a,〈 1,z〉 〉,〈 a,〈 2,z〉〉,〈 b,〈 1,z〉〉,〈 b,〈 2,z〉〉 }
∴ （ A?B） ?C?A?（ B?C）, ?”不满足结合律。
,定理, 若 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）
§ 3 序偶与笛卡尔乘积
证明：（ 2）设 〈 x,y〉 是 A?（ B?C）中的任一元素，
则,〈 x,y〉 ?A?（ B?C） ?
〈 x,y 〉 ?{〈 x,y 〉 |x?A?y?B?C}
? <x,y>?{<x,y>|x?A?y?B?y?C}
? <x,y>?{<x,y>|(x?A?y?B)?(x?A?y?C)}
? <x,y>?(A?B)?(A?C)
即 A?(B?C)=(A?B)?(A?C)
例：设 A={1},B={1,2},C={2,3}
则 A?（ B?C） ={1}?{1,2,3}
={〈 1,1〉, 〈 1,2〉, 〈 1,3〉 }
§ 3 序偶与笛卡尔乘积
（ A?B） ?（ A?C） ={1}?{1,2}?{1}?{2,3}
={〈 1,1〉, 〈 1,2〉, 〈 1,3〉 }
A?（ B?C） ={1}?{2}={〈 1,2〉 }
（ A?B） ?（ A?C）
={〈 1,1〉,〈 1,2〉 }?{〈 1,2〉,〈 1,3〉 }
={〈 1,2〉 }
n个集合的笛卡儿乘积的定义,
设 A={Ai},i?In
Ai=A1?A2?…… ?An
= （（（ A1?A2） ?A3） ?…… ） ?An
§ 4关系及其表示
序偶 〈 a,b〉 实际上反映了二个元素之间的关系，
关系反映了事物的结构。
1.关系：指事物之间（客体之间）的相互联系。
日常生活中：父子关系，母子关系，兄弟关系等均为二
个客体之间的关系。
而祖孙关系是三个客体之间的关系（父子关系和父子关
系的合成）。
n元笛卡尔积 A1× A2× ?? × An是 n元关系。
§ 4关系及其表示
,定义, 若
则是一个二元关系。 即：序偶作为元素的任何
集合 。
２．关系表示方法
（ 1）枚举法（直观法、列举法）
设 R表示二元关系，用 表示特定的序偶，
若,则也可写成：
x R y。
}|,{ 22112121 AxAxxxAA ???????
xRy
Ryx ???,Ryx ???,
?
§ 4关系及其表示
例：二元关系定义如图：
可写成：
由定义可见：关系是一个集合，
∴ 定义集合的方法都可以来定义关系。
（ 2）谓词公式表示法
前面讲述，一个集合可用谓词公式来表达，所以
关系也可用谓词公式来表达。
},4,3,2,1{ ????????? dcbaR
§ 4关系及其表示
例：实数集合 R上的,>”关系可表达为：
大于关系：,>”=
父子关系：,F”=
（ 3）关系矩阵表示法
规定：
(a)二元关系 <x,y>中的序偶中左元素表示行，右元素表
示列；
(b)若,则在对应位置记上,1”，否则为,0”。
)}(|,{ yxRyRxyx ???????
}|,{ 的父亲是 yxyx ??
iiRyx
§ 4关系及其表示
例 1：设
并定义为
列出关系矩阵：
例 2：设 X={a,b,c},Y={1,2},R2是Ｘ → Ｙ的关系，
}1,22,31,33,42,41,4{1 ?????????????R
?
?
?
?
?
?
?
?
?
?
?
?
?
1 1 1 0
1 1 0 0
1 0 0 0
0 0 0 0
1R
M
的关系是 ????? R},4,3,2,1{
§ 4关系及其表示
是Ｘ → Ｙ的全域关系，
}2,1,2,1,2,1,{2 ??????????????? ccbbaaYXR
2R
??3R
§ 4关系及其表示
（ 4）关系图表示法
规定：
(a)把Ｘ、Ｙ集合中的元素以点的形式全部画在平面上；
(b)若,则 xi和 yi之间画一箭头弧线，反之不画任何
联线。
例,是 X中的二元关系，
iiRyx
1},4,3,2,1{ RX ?
}1,22,31,33,42,41,4{1 ?????????????R
§ 4关系及其表示
用关系图表示：
３．关系的定义域和值域：
,定义,, 设 S是一个二元关系,D(s)是所有客体 x的集
合，对于一些 y来说，若有,则称 D(s)为
S的定义域（简称“域”），即
Syx ???,
§ 4关系及其表示
)},(|{)( SyxyxsD ?????
设 R(S)是所有客体 y的集合，对于一些 X来说，若有
Syx ???,，则称集合 R(S)是 S的值域（简称“值”）,即：
},(|{)( ?????? SyxxySR
例,X={1,2,3,4,5,6},R为 X到 Y的二元关系
},4,3,2,1{ ????????? dcbaR
,f}{a,b,c,d,eY ?
，则
},,,{)(},4,3,2,1{)( dcbaRRRD ??
一般情况，称 X为 R的 前域,称 Y为 R的 陪域 。
§ 4关系及其表示
４．关系和笛卡尔乘积
笛卡尔乘积的任何子集都可以定义一种二元关系。
例,X={1,2,3,4},Y={1,2}，则
}2,4,1,4,2,3,1,3,2,2,1,2,2,1,1,1{ ?????????????????? YX
§ 4关系及其表示
}3,42,41,42,31,31,2{}|,{1 ????????????????????? yxYyXxyxS
}2,41,1{}|,{ 22 ????????????? yxYyXxyxS
}2,21,1{}|,{3 ????????????? yxYyXxyxS
321,,SSS
均为二元关系。
５．三个特殊关系：空白关系，全域关系，恒等关系
,定义,, 集合 X2定义了 X集合中的一种关系，
通称为 X中的全域关系，用 Ex表示：
§ 4关系及其表示
},|,{ XyxyxXXE iix ??????
空集也是 的一个子集，它也定义了一种关系
称为空白关系；
XX ?
X集合中的恒等关系,}|,{ XxxxI iiix ????
在全域关系和恒等关系中前域 =定义域，陪域 =值域。
例：Ｘ =｛Ｔ，Ｆ｝则
},,,,{ ????????? FFTFFTTTE x
},,{
{}
?????
??
FFTTI x
同一域上的关系,可进行
集合的所有运算。
§ 5关系的性质
１．自反性,
,定义,,设Ｒ是Ｘ集合中的二元关系，对于每一个（所有的）
Xx?,有 xRx,则称Ｒ是自反关系,X中 R是自反的
)( x R xXxx ????
例：设 },,{ cbaX ?
},,,,{ ????????? baccbbaaR 是自反的关系。
R的关系矩阵
?
?
?
?
?
?
?
?
?
?
?
0 0 1
0 1 0
1 1 0
RM
§ 5关系的性质
,定义,, 设 R是 X中的二元关系，对于每一个,
有 x x，则称 R是反自反的关系，表示成,R是 X中的反自反的关
系 x x 。
Xx?
??? Xxx ( )
例：设 X={1,2,3},
}1,22,1{1 ?????S
}2,1{2 ???S
}1,2{3 ???S
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
000
100
000
,
000
000
010
,
000
100
010
321 SSS
MMM
§ 5关系的性质
}2,31,31,21,1{4 ?????????S
?
?
?
?
?
?
?
?
?
?
?
110
100
100
RM
２．对称性
,定义,,设 R是 X中的二元关系，对于每一个
来讲，如果每当有 xRy，则必有 yRx，则称 R是 X中的对称关
系,并表示成,R是 X中的对称关系
Xyx ?,
)( y R xx R yXyXxyx ????????
S4既不是自
反的，又不
是反自反的
§ 5关系的性质
例：设 X={1,2,3},R={<1,1><2,1><1,2><3,2><2,3>}
则 R是对称的关系
?
?
?
?
?
?
?
?
?
?
?
0 1 0
1 0 1
1 1 0
RM
,定义,,设 R是 X集合中的二元关系，对于每一个 Xyx ?,
来讲，如果每当 xRy和 yRx就必有 x=y，则称 R是反对称的关
系。
§ 5关系的性质
即当且仅当 )( yxy R xx R yXyXxyx ?????????
X中的 R才是反对称的。
讨论定义：（ 1）前件 yR xxR y ? 为,T”，
则 x=y也为,T”,则为反对称的；
（ 2） 前件 yR xxR y ? 为,F”，
则有三种情况：
后件（ x=y）不论是真还是假，命题公式为,T”。
下面举例说明：
§ 5关系的性质
例：设 X={a,b,c}
},,,{1 ??????? accbbaR
},,,,{2 ????????? ccbbaacaR
},,,{3 ??????? accbaaR 均是反对称的
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
100
001
100
,
001
010
101
,
100
001
010
321 RRR
MMM
§ 5关系的性质
例,X={a,b,c},下列关系不是对称的，也不是反对称的
},,,{1 ??????? cbabbaR
},,,,{2 ????????? cabccbaaR
§ 5关系的性质
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 1 0
0 0 1
1 0 1
,
0 0 0
1 0 1
0 1 0
21 RR
MM
X上的恒等关系 },,,{
3 ??????? ccbbaaR
是自反、对称、反对称的。
§ 5关系的性质
?
?
?
?
?
?
?
?
?
?
?
0 0 1
0 1 0
1 0 0
3R
M
X上的全域关系：
},,,,,,,,,{4 ??????????????????? bcaccbabcabaccbbaaR
是自反的，对称的
X上的空关系是反自反、对称、反对称的。
§ 5关系的性质
３．传递性,
,定义,,设 R是 X中的二元关系，对于每一个 Xzyx ?,,
来说，如果每当 yR zxR y ?,就必有 xRz
则称 R是可传递的，并表示成,X中 R可传递
)( x R zy R zx R yXzXyXxzyx ????????????
讨论定义：（ 1）前件 yR zxR y ? 为,T”，
则 xRz也为,T”,R是可传递的 ；
（ 2）前件为,F”，有三种情况
后件不论是真还是假，命题为,T”，则 R是可传递
的
§ 5关系的性质
例：设 X={a,b,c}，则下列关系均是可传递的
},,,,{1 ????????? cbcabaaaR
},{2 ??? baR
},,{3 ????? cabaR
??4R
§ 5关系的性质
下列关系是不可传递的：
},,,{4 ??????? accaaaR
},,,{5 ??????? accbbaR
§ 5关系的性质
４．确定二元关系性质举例
（ 1）设 X={1,2,3}，
}3,13,22,1{1 ???????R
反自反，反对称，可传递的；
}3,22,11,1{2 ???????R
反对称的；
§ 5关系的性质
}3,32,21,1{3 ???????R
自反，对称，反对称，可传递的；
xER ?4
自反，对称，可传递的；
??5R
反自反的，对称的，反对称的，
可传递的。
§ 5关系的性质
（ 2）若 ??X,则 X上的空关系 ?
自反的，反自反的，对称的，反对称的，可传递的。
§ 6复合关系和逆关系
１．关系的复合
,定义,,设 YX ? （ R关系）,ZY ? （ S关系），
于是可用 ZX ? （ R?S） 的关系，称 R?S
为 R和 S的复合关系，并规定为：
)},,(|,{ SzyRyxYyyZzXxzxSR ??????????????????
例：设 A={1,2,3,4,5},R,S均为 A→A 的关系，且
R={<1,2><3,4><2,2>},S={<4,2><2,5><3,1><1,3>}
则 R?S={<1,5><3,2><2,5>},S?R={<4,2><3,2><1,4>}
§ 6复合关系和逆关系
,RSSR ?? ? ∴,?”是不可交换的。
讨论：
（ 1） R?S为新的二元关系
（ 2） R?S?X× Z
（ 3）当 <x,y>∈R 与 <y,z>∈S,才有 <x,z>∈ R?S
§ 6复合关系和逆关系
,定理,,设 WZYX RRR ? ??? ??? ?? 321 则有：
321321321 )()( RRRRRRRRR ?????? ??
可见合成关系图
下面定义关系 R 的幂次
§ 6复合关系和逆关系
,定义, 给定集合 X,R是 X中的二元关系，设 Nn?
于是 R的 n次幂 nR 可以定义成：
（ 1） 0R =X集合中的恒等关系
（ 2） RRR nn ???1
例：设 R,S是
?I
中的二元关系，且
}|7,{},|2,{ ?? ???????? IxxxSIxxxR 则：
}|14,{},|14,{ ?? ???????? IxxxRSIxxxSR ??
§ 6复合关系和逆关系
},,,,,{2 ??????? bcabcaR
}|4,{2 ????? IxxxR }|49,{2 ????? IxxxS
}|8,{23 ?????? IxxxRRR ?
},,,,,{ ??????? accbbaR},,{ cbaX ?例：
xIccbbaaRRR ????????? },,,,,{23 ?
§ 6复合关系和逆关系
RRRR ?? ?34
nmikR aM ?? ][
若 |X|=n，则 X中的二元关系 R的幂次值是有限的。一般不用
求出超过 X的基数次幂。
２．复合关系的矩阵表示
设有三个集合：
ZYXzzzZyyyYxxxX SRpnm ? ??? ????? },,{},,{},,{ 212121 ???
而 |X|=m,|Y|=n,|Z|=p，则关系矩阵
pnkjS bM ?? ][
§ 6复合关系和逆关系
1)()()()()( 5515451435132512151115 ??????????? bababababaC
pmijSR cM ?? ][?SRSR MMM ?? ?
例：设 X={1,2,3,4,5},R,S均是 X中的二元关系，
R={<1,2><3,4><2,2>},S={<4,2><2,5><3,1><1,3>}
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 1
,
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 1 0 0
,
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 1 0 0 0
SRSR
MMM
?
)(
1 kjik
n
kij
bac ???
?
§ 6复合关系和逆关系
３．逆关系
,定义,,设 X,Y是二个集合，若 R是 X→Y 的关系，从
Y→X 的关系，称为 R的逆关系，用 },|,{~ RyxxyR ??????
表示，或用 cR 表示。
讨论定义：（ 1）只要将 R中每一个序偶中的元素全部调换位置，
就可得到 R的逆关系 R~
（ 2）设 R~ 的关系矩阵为
RM~ RM?
的转置矩阵；
（ 3）在 R的关系图中，只要把所有箭头改换方向就可得到
的关系图。（自回路箭头改变与否无关）R~
§ 6复合关系和逆关系
例,X={0,1,2},R={<0,0><0,1><1,2><2,2>},
R~ ={<0,0><1,0><2,1><2,2>},
,
011
100
100
,
001
001
110
~
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
RR
MM
§ 6复合关系和逆关系
,定理,,设 ZYX SR ? ??? ??,则可有,RSSR ~~~ ?? ?
证明：对于任一 ZzYyXx ???,,来讲，若有
xSRzzSRxy S zx R y )()( ~?? ???
同样 xRSzxRyySz )~~(~~ ???
∵ x,y,z分别为 X,Y,Z中的任一元素，
∴ RSSR ~~~ ?? ?
§ 6复合关系和逆关系
例：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 1 0 1 0
1 0 1 0 1
1 0 0 1 0
,
111
110
101
SR MM
，试求：
~,,,~~ SRSRSR MMMM ??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1 1 1 1 1
1 0 1 1 1
1 1 0 1 0
,
0 1 0
1 0 1
0 1 0
0 0 1
1 1 0
,
1 0 1
0 1 1
1 1 1
~~
SRSR
MMM
?
§ 6复合关系和逆关系
~~ ~~~~
0 1 1
1 1 1
0 1 1
1 0 1
1 1 1
,
0 1 1
1 1 1
0 1 1
1 0 1
1 1 1
SR
RSRS
SR
MMMMM
?
?
?
? ??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
,定理,,设 R是 X中的二元关系，当且仅当 RR ~?
则 R才是对称的。
§ 6复合关系和逆关系
证明：①充分性,R是对称的 RR ~??
对于任一 RbaRabRba ~,,,???????????
② 必要性,?? RR ~ R是对称的，
RR ~?? ∴ 对任一
RabRbaRba ???????????,~,,
∴ R一定是对称的
∴ RR ~?
§ 6复合关系和逆关系
,定理,,给定集合 X,Y,YX SRRR ??? ??,,,21,于是可有
RR ?~~)1(
SRSR ~~)2( ~ ?? ?
SRSR ~~)3( ~ ?? ?
XYYX ???~)4(
???~)5(
)(~,~~)(~)6( ~ RYXRRR ????
§ 6复合关系和逆关系
21
~
21
~~)7( RRRR ???
2121 ~~)8( RRRR ???
2121 ~~)9( RRRR ???
21
~
21
~~)10( RRRR ???
证明：（ 1）设 <a,b>是 R中的任一元素，则
RbaRabRba ~,~,,???????????
（ 10）设 YyXx ??,，对任一
~
1221
~
21 )()(,,RRRRyxRRyx ?????????? ?
§ 6复合关系和逆关系
由（ 2） SRSR ~~~ ?? ? ~ 12~ 21 )()((,RRRRyx ?????? ?
由（ 7）
21
~
21
~~ RRRR ???
)~~(,)~~()~~((,211221 RRyxRRRRyx ??????????? ?
21
~
21
~~ RRRR ????
§ 7关系的闭包运算
,定义,,给定集合 X,R是 X中的二元关系，若有另一
R’满足下列条件：
（ 1） R’是自反的（对称，可传递的）；
（ 2） RR ?'
（ 3）对于任一自反（对称，传递的）关系 R’’，若
RR ?'',则 ''' RR ?
则称 R’是 R的自反（对称，传递的）闭包，
并依次用 r(R),s(R),t(R)来表示之。
§ 7关系的闭包运算
讨论定义：
（ 1）已知一个集合中的二元关系 R，则
r(R),s(R),t(R)是唯一的，它是包含 R的最小的自反
（对称，传递）关系；
（ 2）若 R是自反（对称，传递）的，则
r(R),s(R),t(R)就是 R本身。
（ 3）若 R不是自反（对称，传递）的，则我们可
以补上最少序偶，使之变为自反、对称、传递关系，
从而得到 r(R),s(R),t(R)；
§ 7关系的闭包运算
例：设 X={a,b},R={<a,a><a,b>}，
r(R)={<a,a><a,b><b,b>},s(R)={<a,a><a,b><b,a>},
t(R)={<a,a><a,b>}=R
例：求 t(R)需要特别小心，要进行多次添项。
设 X={a,b,c},R={<a,b><b,c><c,a>}，求 r(R),s(R),t(R)
解,r(R)= },,,,,,{ ????????????? ccbbaaaccbbaIR x?
s(R)= },,,,,,{~ ????????????? caacbccbabbaRR ?
t(R)={<a,b><b,c><c,a><a,c><b,a><c,b><a,a><b,b><c,c>}
§ 7关系的闭包运算
,定理,,给定集合 X,R是 X中的二元关系，于是可有：
（ 1）当且仅当 r(R)=R，则 R是自反的；
（ 2）当且仅当 s(R)=R，则 R是对称的；
（ 3）当且仅当 t(R)=R，则 R是可传递的。
xI
,定理,, R是 X中的二元关系 是 X中的恒等关系，
则有
xIRRr ??)(
证明：按定义证,（ 1） 设 xIRR ??',则 R’是自反的，
RR ?')2(
§ 7关系的闭包运算
（ 3）设有任一 R’’也是自反的，且
则
RRIR x ??? ''''
''')('' RRIRR x ??? ?
xIRR ??? '
,定理,,给定集合 X,R是 X中的二元关系，则有
RRRS ~)( ??
,定理,,设 X是一集合,R是 X中的二元关系，则：
)(,)( 12 ??? ??? IiRURRRt ii???
§ 7关系的闭包运算
例,X={a,b,c},R={<a,b><b,c><c,a>},|X|=3,
则
,
},,,{
},,,,{
4
3
2
RR
ccbbaaR
bcabcaRRR
?
???????
???????? ?
},,,,,,,,,{
)( 32
???????????????????
??
ccbbaabcabcaaccbba
RRRRt ??
,定理,,设 |X|=n,R是 X中的二元关系，则
kRRRRt ???? 2)( ? )0( nK ??
§ 7关系的闭包运算
例,X={a,b,c,d},R={<a,b><b,c><c,d>},
则 ?????????? 432 },,{},,,{ RdaRdbcaR
},,,,,,{
)( 432
????????????
??
dadbcadccbba
RRRRRt ???
,定理,,设 X是一集合,R是 X中的二元关系，则有：
（ 1） r(S(R))=S(r(R));
（ 2） r(t(R))=t(r(R));
（ 3） t(S(R)) ? S(t(R))。
§ 7关系的闭包运算
证明：（ 1） r(S(R))
)~~()(
~)~(
xx
x
IRIR
IRRRRr
???
???
?
??
)()(~)(
)~()(
RSrRrRr
IRIR xx
??
?
?
???
常用下列符号表示一些闭包：
“R加”,)(RtR ??,传递闭包，
nn
i
i RRRRR ????? 21
1
??
?
?
“R星”,)()(* RrtRtrR ??,自反可传递闭包，
??? n
i
i
x RIRtRR
1
0* )(
?
??
§ 7关系的闭包运算
例：设 X={a,b,c},R={<a,b><c,c>}
（ 1） rS(R)=r{<a,b><b,a><c,c>}
={<a,b><b,a><c,c><a,a><b,b>}
Sr (R)=s{<a,b><c,c><a,a><b,b>}
={<a,b><b,a><c,c><a,a><b,b>}
（ 2） rt(R)=r{<a,b><c,c>}={<a,b><c,c><a,a><b,b>}
tr(R)=t{<a,b><c,c><a,a><b,b>}={<a,b><c,c><a,a><b,b>}
（ 3） tS(R)=t{<a,b><c,c><b,a>}
={<a,b><c,c><b,a><a,a><b,b>}
St(R)=S{<a,b><c,c>}={<a,b><c,c><b,a>}
∴ t(S(R)) ? St(R)
§ 8集合的划分和覆盖
,定义,,给定一非空集合Ｓ，又设 },{
21 mAAAA ??
若（ 1） ),2,1(,miSA
i ???
（ 2） ?m
i
i SA
1?
?
则称 A为 S的覆盖。
例,S={a,b,c},A={{a,b},{b,c}},B={{a},{a,b},{c}}，
C={{a},{b},{c}},D={{a},{b},{a,c}}
均为 S的覆盖。
§ 8集合的划分和覆盖
例：四个半圆覆盖一正方形。
,定义,,给定一非空集合 S，设非空集合 },{
21 mAAAA ??
如果有,),2,1(,)1( miSA
i ???
??ji AA ?)2( 或
ji AA ?
?m
i
i SA
1
)3(
?
?
（ i,j=1,2…,m ）
§ 8集合的划分和覆盖
则称集合 A是集合 S的一个划分。
讨论定义：
（ 1）划分和覆盖主要差别在第（ 2）条；
（ 2）划分 A中的元素，称为划分的类，在定义中
mAAA ?21,
均是 A中的一个类，类的个数称为划分的秩；
（ 3）若 A为有限集合，则 A的秩是有限的，为 |A|，
若 A为无限集合，则划分的秩是无限的；
（ 4）集合的划分必定是一个覆盖，而覆盖不一定是划分；
（ 5）集合 S上的秩最大的划分称最大划分，最小的称最小划分。
§ 8集合的划分和覆盖
例：设 S={a,b,c}，下列
iA
均为 S的一个划分：
}},{},{{1 cbaA ? 类有二个 {a},{b,c},∴ || 1A =2（秩）；
}}{},,{{2 cbaA ? 类有二个 {a,b },{c},∴ || 2A =2（秩）；
}}{},,{{3 bcaA ? 类有二个 {a,c},{b},∴ || 3A =2（秩）；
}}{},{},{{4 cbaA ? 最大划分，秩为 3=|S|；
}},,{{5 cbaA ? 最小划分，秩为 1。
例：四个直角三角形
组成了正方形的一个划分
秩 =4
§ 8集合的划分和覆盖
,定义,,设 A和 A’是非空集合 S的二种划分，并可表示成：
,}{
1
?m
i
iAA
?
? ?n
i
jAA
1
}{'
?
? 若 A’的每一个类 jA
都是 A的某一个类
iA
的子集，则称划分 A’是划分 A的加细，
或讲 A’加细了 A，若 A’加细了 A且 'AA ?
则称 A’是 A的真加细。
讨论定义：
A’加细了 A，一定有 |A’|≥|A|（秩），
若 |A’|>|A|，则一定为真加细。
§ 8集合的划分和覆盖
例,S={a,b,c,d},S的划分,A={{a,b},{c,d}},
A’={{a}{b}{c,d}}，则 A’是 A的真加细
A’’={{a}{b}{c}{d}},则 A’’ 是 A的真加细
§ 9等价关系 与等价类
,定义,,设 X是一个集合,R是 X中的二元关系，若 R是自
反的，对称的和可传递的，则称 R是等价关系。
例：下列关系均为等价关系
（ 1）实数（或 I,N集上）集合上的,=”关系（相等）
（ 2） {人类 } 中的同姓关系
（ 3）命题集合上的等价关系
例：设 X={1,2,3,4,5,6,7}，
3,|,{
yxXyxyxR ?????? 为整数 }
§ 9等价关系 与等价类
试验证 R是等价关系，画出 R的关系图，列出 R的关系矩阵
解：（ 1） R={<1,1><1,4><1,7><2,2><2,5><3,3><3,6><4,1>
<4,4><4,7><5,5><5,2><6,6><6,3><7,7><7,4><7,1>}
（ 2） R的关系矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1 0 0 1 0 0 1
0 0 1 0 0 1 0
0 1 0 0 1 0 0
1 0 0 1 0 0 1
0 0 1 0 0 1 0
0 1 0 0 1 0 0
1 0 0 1 0 0 1
R
M
§ 9等价关系 与等价类
R满足自反、对称和可传递的,∴ R是一等价关系
,定义,,设 ??Im Iyx ?,
若对于某个整数 n有 (x-y)=n ? m,n
m
yx ?? （整数），
则称 x模 m等于 y，记作,)( m o d myx ?
,定理,,任何集合 IX ?
（ I的任何子集 X中）的模 m等价，是一个等价关系。
§ 9等价关系 与等价类
,定义,,设 R是 X集合中的等价关系，对于任何的
Xx? 来讲，可把集合 ? ? Xx R ? 规定成：
? ? }|{ yR xXyyx R ??? 并称是由 Xx? 生成的 R等价类。
讨论定义：
（ 1）等价类 ??
Rx
是一个集合，由定义中可见 ? ? Xx R ?
（ 2） ??Rx 中的元素是在等价关系 R中，所有与 x
具有关系的元素所组成的集合，且 ? ? ??
Rx
§ 9等价关系 与等价类
例：设 X={a,b,c,d},R是 X中的等价关系，
R={<a,a><b,b><a,b><b,a><c,c><d,d><c,d><d,c>}
则
RR ddcc ][},{][ ??
RR bbaa ][},{][ ??
,定理,,设 X是一个集合,R是 X中的等价关系，则
（ 1）若 Xx?,则 Rxx ][?
（ 2）对于所有的 Xyx ?,，或者 RR yx ][][ ? 或者 ??RR yx ][][ ?
（ 3） ?
Xx R
Xx
?
?][
§ 9等价关系 与等价类
例：设 X=N，关系 R={ )(|,yxXyXxyx ??????? 可被 3整除 }
是一等价关系,则 R可以找出三个等价类：
R]0[ ={0,3,6,9…},此集合中的元素除以 3的余数为,0”；
R]1[ ={1,4,7,10…},此集合中的元素除以 3的余数为,1”；
R]2[ ={2,5,8,11…},此集合中的元素除以 3的余数为,2”。
例,X为全班同学的集合，则班中同姓关系是一个等价关系，
（ 1）任何一个人均 ∈ 某一个等价类，王某某 ∈ [王 ] R
张某 ∈ [张 ]R…
§ 9等价关系 与等价类
（ 2）任何二个姓的等价类，只有二种可能
一种,[王 ] R= [王 ] R
二种,[王 ] R?[李 ]R=?
（ 3）全班同学的集合 =同姓关系等价类的并集 =[王 ] ?
R
[李 ]?
R
…
（ 4）所有等价类的集合，一定导致全班同学集合
的一个划分,A={[王 ]R,[李 ]R….}
§ 9等价关系 与等价类
,定理,,设 X是一非空集合,R是 X中的等价关系,R
等价类的集合 {[x]R| x∈ X}是 X的一个划分，且此集合
称为 X按 R的商集，用 RX 表示之。
例：设 X={x1,x2…..x n}
（ 1） X集合中的全域关系,XXR ??1,它是一个等价关系，
Xx R ?1][ |||][| 1 Xx R ?
∴ X按 R1的商集 1||},|]{[
11
??? RXXxxRX R
它形成了 X的一个最小划分
§ 9等价关系 与等价类
（ 2） X中的恒等关系
xIR ?2
??? }|]{[ 2
2
XxxRX R }][]{[ 221 RnR xx ? ),( 21 Xxxx n ??
它形成了 X的一个最大划分
例,X为全班同学的集合,|X|=n,(n∈N)
（ 1）同学关系 R1是一个等价关系,}{
1 XR
X ?
（ 2）按指纹的相同关系 R2是一个等价关系，
}][]{[ 221
2 RnR
xxRX ??
它形成了全班同学的最大划分
§ 9等价关系 与等价类
（ 3）同姓关系 R3是一等价关系
?3RX {[张 ] R3,[李 ]R3,… }
它形成了全班同学的既不是最大，又不是最小划分
§ 9等价关系 与等价类
,定理,, X是一非空集合,A为 X的一个划分，且
A={A1,A2,….A n}，则由 A导出的 X中的一个等价关系
)(1 iini AAR ??? ?
例,X＝ {a,b,c,d},A={{a,b},{c,d}}
则 R＝ ({a,b} × {a,b})?({c,d} × {c,d})
={<a,a>,<a,b>,<b,a>,<b,b>,<c,c>,<c,d>,<d,c>,<d,d>}
由此我们看到：集合 X上的等价关系与 X的划分之间有对
应关系。
§ 10相容 关系
,定义,,给定一个集合 X,R是 X中的二元关系，如果
R是自反、对称的，则称 R是相容关系。
例：设 X={ball,bed,dog,let,egg},5个英文单词
定义 X中一个二元关系：
R={ yxXyxyx,,|,???? 有相同的字母 }
则 R是自反的，对称的，但不可传递
∵ (ball R bed) ?(bed R egg) (ball R egg)??
则 R={<1,1><1,2><2,1><1,4><4,1><2,2><2,3><3,2> <2,4>
<4,2><2,5><5,2><3,3><3,5><5,3><4,4><4,5><5,4><5,5>}
§ 10相容 关系
§ 10相容 关系
,定义,,设 X是一个集合,R是 X中的相容关系，假定
A?X，若任一 x∈ A都与 A中的其它所有元素有相容关
系，而（ X-A）中没有一个元素与 A中的所有元素有相
容关系，则称子集 A为相容关系 R的一个最大相容类。
例：上例中 }5,4,2{},5,3,2{},4,2,1{
321 ??? AAA
均是 X中的最大相容类,且 321 AAAX ???
},,{ 321 AAA 定义了 X的一个覆盖。
同样已知 X集合的一个覆盖 },,{
321 AAA
§ 10相容 关系
则一定可以求出相对应的相容关系来：
332211 AAAAAAR ???? ??
讨论等价关系和相容关系后可得到结论：
集合 X上的相容关系 R的所有最大相容类集合
{A1,A2,….A m}构成集合 X的一个覆盖。即：
i
m
i
AX
1?
? ?
而集合 X上的等价关系 R的所有等价类集合构成 X的一个
划分
§ 10相容 关系
求最大相容类的方法：
关系图法：确定最大完全多边形
每个顶点都与其他所有顶点相联结的多边形。
(1)孤立结点是最大的完全多边形；
(2)二个相互联结的结点是最大完全多边形；
(3)三角形是三个结点的最大完全多边形；
§ 10相容 关系
(4)四个结点；
(5)五个结点 ;
画出简化相容关系的关系图后，
先结点最多的完全多边形，以后逐次减少。
§ 10相容 关系
例：已知相容关系图，求出最大相容类
§ 10相容 关系
}5,4{
}5,2{
}3,2{
}4,3,1{
4
3
2
1
?
?
?
?
X
X
X
X
}4,3{
}5,4,1{
}6,5,2,1{
3
2
1
?
?
?
X
X
X
最大相容类集合为
}}4,3}{5,4,1}{6,5,2,1{{} },5,4}{5,2}{3,2}{4,3,1{{ 21 ?? SS
§ 11序关系
,定义,,设 R是 P中的二元关系，如果 R是自反的，反
对称和可传递的，则称 R是 P中的偏序关系（或称偏
序），并用符号,≤”表示，而序偶 〈 P,≤〉 则称为
偏序集合。
讨论定义：
（ 1）,≤”不单纯意味着在实数中的 ≤关系，而是代表更为
普遍的关系（具有自反，反对称和可传递性的关系）；
（ 2）若 Pyx ?,，,x≤y”读作：
“x小于或等于 y”“y包含 x”“x在 y的前面”等；
§ 11序关系
（ 3） R是集合 P中的偏序关系，则 R~
也是 P中的偏序关系，即 R用,≤”表示,R~
则用,≥”表示；
（ 4）若 〈 P,≤〉 是一个偏序集合，则 〈 P,≥〉 也一定是
偏序集合，且偏序集合是一个序偶，左元素为集合 P，右
元素为偏序关系。
例：
（ 1）在领导机构的集合中“领导和被领导的关系”是
偏序关系；
（ 2）在 I（整数）集合中，,≤”、,≥”均是偏序关系；
§ 11序关系
例：
}8,6,3,2{4 ?I
4I 中的,≤”（整除） ={<2,2><2,6><2,8><3,6><3,3><6,6><8,8>}
而,≥”（整倍数） ={<2,2><6,2><8,2><3,3><6,3><6,6><8,8>}
均是偏序关系。
§ 11序关系
,定义,, R是集合 X中的二元关系，若 R是非自反的，
反对称的和可传递的，则称 R是拟序关系（串序），
并用符号,<”表示。而 〈 X,<〉 称为拟序集合。
讨论：
（ 1）拟序关系一定反对称的
（ 2）拟序关系也可用偏序关系来定义：
?
?
?
?????
?????
yxyxyx
yxyxyx
§ 11序关系
,定义,,设 〈 P,≤〉 是一个偏序集合，若对于每一个
Pyx ?,，或者 x≤y，或者 y≤x，即
)( xyyxPyPxyx ?????????,则,≤”
称为全序关系，而 〈 P,≤〉 称为全序集合（线序集合）。
,定义,,在偏序集合 〈 P,≤〉 中，若 Pyx ?,
且具有 x≤y或 y≤x，则称 x和 y是可以比较的，
否则称 x,y是不可比较的。
,推论,,在偏序集合中，一般情况下，一定是有的元素可以
比较的，有的元素是不可比较的。
在全序关系中，所有的元素均是可以比较的。
§ 11序关系
,定义,,若集合 X上的二元关系 R是全序关系，且 X的
任一非空子集，都有一个最小元素，则称 R为良序关
系，并称 <X,R>为良序集合。
讨论定义：
（ 1）良序关系比全序关系多了一个条件，即在全序关系中，
X集合的任一非空子集均有一个最小元素；
（ 2）每一个有限集合 X上的全序关系必定是良序关系。
例：设 A={1,2,3,4}
定义 A上的,≤” ={<1,1><1,2><1,3><1,4><2,2><2,3>
<2,4><3,3><3,4><4,4>}
§ 11序关系
２．偏序集合和哈斯图
,定义,,在偏序集合 〈 P,≤〉 中，若有 Pyx ?,
且 x≤y和 yx ?,又不存在其它元素 z能使 yzzx ???
则称元素 y盖住 x，盖住集记为 COV(P)=;,|,{ Pyxyx ??? Y盖住 x}
给定偏序集 〈 P,≤〉,它的盖住集是唯一的。我们可以画
出盖住集的关系图，称为 〈 P,≤〉 的哈斯图。
§ 11序关系
（ 2）若 Pyx ?,，且 x≤y和 yx ?,则把 x画在 y的下面；
（ 3） 若 y盖住 x，则在 x和 y之间画一条联线，并箭头向上，
若 y不盖住 x，但又存在,≤”关系，则必定通过 x和 y
之间的其它中间结点把 x和 y联结起来；
（ 4） 所有边的方向均是向上的，所以实际画时，
箭头均可省去。
例,(a)设 }4,3,2,1{
1 ?P
“≤”表示 P中元素的小于和等于关系，
（ 1）用,?”表示 P中的结点（具有自反性）；
画 〈 P,≤〉 的哈斯图的方法：
§ 11序关系
则 〈 P1,≤〉 是一偏序集合，全
序集合，良序集合
其哈斯图为：
(b)若设 }},,}{,{},{,{
2 cbabaaP ??
???,2P 是一偏序集合，
例：设 X={2,3,6,12,24,36}
“≤”定义为：若 ???? XyXx
x整除 y，则 x≤y，
〈 X,≤〉 是一偏序集合,
§ 11序关系
例,(a)设 X={a,b},ρ(X)=
}},{},{},{,{ baba?
??? ),( X? 是一偏序关系，
其哈斯图为：
(b)设 X={a,b,c}
的哈斯图为：
??? ),( X?
§ 11序关系
,定义, 设 <P,≤> 为一偏序集，且 Q?P
(1)若对每一个 q’ ∈ Q有 q≤ q’,则称 q∈ Q为 Q的最小元素。
(2)若对每一个 q’ ∈ Q有 q≥ q’,则称 q∈ Q为 Q的最大元素。
(3)若 q∈ Q，且不存在一个 q’ ∈ Q，使 q’ ? q且 q’ ≤ q，
则称 q为 Q的极小元素。
(4)若 q∈ Q，且不存在一个 q’ ∈ Q，使 q’ ? q且 q’ ≥ q，
则称 q为 Q的极大元素。
讨论：
(1) q∈ Q,?Q的极大，小，最大，小元，若有的话，必
定在 Q中。
§ 11序关系
(2)最大，最小元是 Q中所有元素比较而言的，
极大，极小元是对 Q中能够比较的元素而言的。
(3)Q中如有最大，最小元则一定是唯一的，极大，极
小元一定存在，且不一定是唯一的。
,定义, 给 <P,≤>,且 Q?P，若
(1)对每个 q’ ∈Q 有 q’ ≤q,则称 q∈P 为 Q的上界，其中最小
的一个，称为 Q的最小上界，记为 LUB(上确界 )。
(2)对每个 q’ ∈Q 有 q’ ≥q,则称 q∈P 为 Q的下界，其中最大
的一个，称为 Q的最大下界，记为 GLB(下确界 )。
§ 11序关系
讨论定义：
(1)上，下界是对 Q中所有元素比较而言的。
(2)Q若有上，下界，则不一定是唯一的。
(3)Q若有 LUB,GLB，则 Q一定有上，下界，且是唯
一的。
(4)Q的上，下界,LUB,GLB，则可能在 Q中，可能
不在 Q中，但一定在 P中。
§ 11序关系
例：设 X={a,b,c},??? ),(X?
是一偏序集合，
其哈斯图如右，
求下列子集的上界、下界、
最小上界和最大下界
§ 11序关系
子集 上界 LUB 下界 GLB
{{a}{c}} {a,c}{a,b,c} {a,c} ? ?
{{a}{b}{c}} {a,b,c} {a,b,c} ? ?
{{a,b}{c}} {a,b,c} {a,b,c} ? ?
{{a,b}{b,c}} {a,b,c} {a,b,c} {b},? {b}
{{a,c}{c}} {a,c}{a,b,c} {a,c} {c},? {c}
{{b}} {b}{a,b}{b,c}{a,b,c} {b} {b},? {b}
