第 二 篇 集 合 论 北京理工大学 郑军

集合论溯源 十六世纪末 起源 十九世纪 德国数学家康托创立古典 集合论 1900年前后 出现各种悖论 1908年 策莫罗建立集合论的公理系统 十六世纪末 起源 十九世纪 德国数学家康托创立古典 集合论 1900年前后 出现各种悖论 1908年 策莫罗建立集合论的公理系统 目前 集合论公理系统有两种形式: 策莫罗-弗兰克尔-柯很形式（ZFC） 贝尔内斯-诺伊曼-葛德尔形式（BNG） 在计算机领域得到广泛应用

古典集合论 康托称集合是“一些确定的、不同的东西的总体，这些东西，人们能够意识到，并且能够判断一个给定的东西是否属于这个总体”。

理发师悖论 在一个小岛上有唯一的一位理发师。他宣称：我为岛上所有不为自己理发的人理发，而不给那些为自己理发的人理发。”。 请问：理发师的头发由谁来理呢？

罗素悖论 Ï Î 令集合S为包含所有不以自身为元素的那些集合，即S={x| x x} 假定S Î S ，那么S 应满足条件x Ï x，因此S Ï S。 自相矛盾 假定S Ï S ，那么S 已经满足条件x Ï x，因此S Î S。 又自相矛盾

ZFC公理 包括九个公理 外延公理 空集公理 无序对公理 正则公理 替换公理 方幂集公理 集公理 无限公理 选择公理

外延公理 假定A和B都是集合，如果任何一个事物属于 A也一定属于B，属于B 也一定属于A ，那么A和B是同一个集合，或称两个集合A和B相等。

空集公理 存在一个不包括任何元素的集合。 正则公理 任何一个非空集合A一定包含一个元素a，A的任何一个元素都不是 a 的元素。

计 算 机 应用领域 集合论是学习计算机科学必备的基础知识 , 计算机领域 集合论是学习计算机科学必备的基础知识 , 计算机领域 计 算 机 应用领域 的大多数基本概念和理论都可以采用集合论的有关术语来描述和论证, 集合论被广泛地应用于形式语言、编译理论、信息检索、数据结构、算法分析、程序设计、人工智能等领域 。

第 三 章 集合与关系

3.1 集合的概念和表示法 集合与元素 集合的势 集合的表示法 集合相等 子集、全集、空集 幂集及在计算机中的表示 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学

具有某种性质的客体所汇成的一个整体叫集合。 3.1 集合的概念 集合的概念和表示法 具有某种性质的客体所汇成的一个整体叫集合。 通常用大写字母 A, B, C, … (或带有下标的字母 A1 , B1 , C1 , … )表示集合的名称。 特殊的集合采用特殊的记号。 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学

例 z 整数集 常用的集合符号 + z 非负整数集 有理数集 素数集 实数集 复数集

“伊拉克战争”美国部署在海湾地区的航空母舰的集合 两条平行线的“交点”的集合 例 英文字母表 鲁迅《狂人日记》中所有 的汉字 我校2004级的全体学生 “伊拉克战争”美国部署在海湾地区的航空母舰的集合 两条平行线的“交点”的集合

元素 属于给定集合的任何客体为该集合的成员或元素。 通常用小写字母表示。 若元素a属于集合A , 记作aA (亦称为A包含a；a在A 之中；a是A的成员） 若元素a不属于集合A , 记作 aA (或aA ) (亦称为A不包含a；a不在A 之中；a不是A的成员） 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学

例 j: 北京 C:中国 U:联合国成员国 A={ a, b, c, d }

关于集合概念的说明 集合中的元素可以是具体的(直观上可以触摸的、可观测的)，也可以是抽象的(想象的)； 集合中的元素是确定的，可以明确区分不同的元素，即集合中的元素是不相同的(相同的元素看作是一个)； 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学

关于集合概念的说明 元素与集合间的属于关系是确定的.对于某个元素a与某个集合A ,要么aA,要么aA ,二者必居其一，绝无其他情况产生； 集合中的元素可以是集合,且是无序的； 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学 由元素构成的集合是一个已经形成的整体,而不是正在形成的整体。

集合 S 中不同元素的数目称为 S 的基数或势记为|S|或#S. 基数（势） 集合 S 中不同元素的数目称为 S 的基数或势记为|S|或#S. |S|是有限的集合为有穷集合 （无限为无穷集合）。

将集合的元素列举出来 例3 V ={a, e, i, o, u} Zm={1, 2, … , m} N ={0, 1, 2, …} 集合的说明方法之一——枚举法 将集合的元素列举出来 例3 V ={a, e, i, o, u} Zm={1, 2, … , m} N ={0, 1, 2, …}

即 所必需满足的条件。 例4 集合的说明方法之二——叙述法 p(x)表示任何谓词 若p(b)为真,则bS } { 是中国的直辖市 x S =

例 可以是集合集合的元素

任意两个集合 A 和 B 相等的充要条件是 A、B 具有同样的成员.记作 A = B.否则，记作 A ≠ B.

例

任意两集合A、B,若 A 的每一个元素都是 B 的一个元素,则称 B 包含 A, 或说 A 是 B 的子集，A 包含于 B.记作 包含（子集） 任意两集合A、B,若 A 的每一个元素都是 B 的一个元素,则称 B 包含 A, 或说 A 是 B 的子集，A 包含于 B.记作 传递性 自反性

如果集合 A 的每一个元素都属于B,但集合 B 中至少有一个元素不属于 A ,则称 A 为 B 的真子集，记作 传递性

例

元素与集合之间的关系. 即属于和不属于. 成员关系隶属关系: 包含关系： 两个集合间的关系. 小结 例:A = {a, {a}}与{a}的关系 隶属关系:不同层次上的两个集合 包含关系: 同一层次上的两个集合

集合A和集合B相等的充要条件是这两个集合互为子集。 定理 集合A和集合B相等的充要条件是这两个集合互为子集。 反之,若AB 且 BA,假设AB ,则根据定义A和B 的元素不完全相同, 设有某一元素xÎA 但 xÎB ,而前提条件为AB ,产生矛盾; 或设有某一元素xÎB 但 xÎA , 与条件 BA矛盾,故两集合元素相同, A=B 。 证明: 设任意两个集合A和B相等, 则根据定义A和B 有相同的元素, 故（x) (xÎA® xÎB) 为真, 且 （x) (xÎB® xÎA) 为真, 即AB 且 B  A

在一个具体问题中，如果所有集合均为某个集合的子集，则称该集合为全集,记为E.

一般情况下,全集取得小一些, 问题的描述和处理会简单些。 关于全集的说明 全集相当于论域 若A 为论域中任一集合, 则 全集是有相对性的 不同的问题有不同的全集，即使是同一个问题也可以取不同的全集. 一般情况下,全集取得小一些, 问题的描述和处理会简单些。 例如: 研究平面上直线相交关系

空集 不包含任何元素的集合是空集,记为 对于任意一个集合A, 空集是唯一的.

例 f ¹ } { 用空集可构成一些有用的集合, }}}, ... { , }, }}, f

由空集和子集的定义可以看到,任何一个非空集合 A, 至少有两个不同的子集 A和f ,即AA和f  A,称A和f为A的平凡子集. 集合中的每个元素都能确定该集合的一个子集, 即若 a  A , 则 {a}  A.

给定集合 A，由集合 A 的所有子集组成的集合, 称为集合 A 的幂集，记为 P(A).

例 则 则

例(续)

C3 C3 C3 C3 幂集小结 = S { a , b , c } = f P ( S ) { , { a }, { b }, { c }} 将 S3 的子集分类: 0元子集: f 1元子集: {a} , {b} , {c} 2元子集: {a , b} , {a, c} , {b , c} 3元子集: {a , b , c} n元集、m元子集 C3 C3 1 C3 2 C3 3

Cn Cn Cn Cn Cn Cn Cn Cn Cn Cn 幂集小结 S = {1 , 2 , 3 , ... , n} 将 S 的子集分类: 0元子集: f 1元子集: {1} , {2} , ... , {n} 2元子集: {1 , 2} , {1, 3} , ... ,{n-1, n} 3元子集: {1 , 2 , 3} , {1 , 2 , 4} , ... , {n- 2 , n-1 , n} n元子集: {1 , 2 , ... , n} |P(S)| = + + + ... + = Cn Cn 1 Cn 2 Cn 3 Cn n n Cn k Cn Cn 1 Cn 2 Cn n k=0

. .   如果有限集合 A有n个元素,则其幂集有2n 个元素。 Cn Cn Cn 定理 因为 (x+y)n = xk yn-k |P(S)| = + + + ... + = Cn 1 2 n k k=0 . .  k=0 n 因为 (x+y)n = xk yn-k 令 x = y =1, 2n = Cn k  k=0 n Cn k

为在计算机上表示有限集合S 的幂集的元素，一般需要: 给S中各元素规定某种次序, 如 a1 , …, an . 集合在计算机中的表示 为在计算机上表示有限集合S 的幂集的元素，一般需要: 给S中各元素规定某种次序, 如 a1 , …, an . 用一个 n 位的二进制数表示该集合的任意子集 A . 当 ai ∈ A 时，该二进制数的第 i 位为 1 , 否则为 0.

例 第一个元素， 第二个元素 其中

例(续) 其中 } , 1 { i 2 - = n ... 11 00  J 二进制数，

3.2 集合的运算 3.2集合的运算 集合的交 集合的并 集合的补 集合的对称差

1.集合的交 (1)定义:共同元素 文氏图 若 即 A和B 没有公共元素, 则称A和B不相交.

(2) 集合交的性质 交换律 结合律

2. 集合的并 (1) 定义: 属于A或属于B 文氏图

(2) 集合并的性质: 交换律 结合律

(2) 集合并的性质(续): 分配律 吸收律

例 试证 文氏图相等

多个集合的交(并) m i A 1 2 = È È ... Ç Ç ... 例 } 8 , 4 { 2 1 3 = A

3. 集合的相对补(B对A的补, A和B的差) (1)定义: 属于A 不属于B

例

(2) 集合补的性质

例 对任意两个集合A, B,试证 对于任意的x 证明 因为 x 是任意的,所以有 的真值为T, 因此

4. 集合的绝对补 (1)定义: A关于全集E的补

(2) 集合绝对补的性质

(2) 集合绝对补的性质(续) 且 的充分必要条件为 例 若 则

5. 集合的对称差 (1)定义: 或属于A或属于B 文氏图

(2) 集合对称差的性质

例 试证 文氏图相等

小 结 A,B,C为E的任何子集,则有 对合律 幂等律 结合律 交换律 分配律

小 结（续） 吸收律 摩根律 同一律 零 律 否定律

小 结 (续) 为 的任何子集,则有

小 结（续）

3.3 包含排斥原理 定理: 设A, B为有限集合, 其元素个数分别为|A| , |B|, 则

例 设在20名学生中, 有12人是足球队员, 10人是篮球队员, 兼是两队球员的人数为5名, 请问既不是足球队员也不是篮球队员的学生有几人? 解: 设足球队员的集合为A, 篮球队员的集合为B, 则 |A|=12 , |B|=10, |AB| =5 . 又因为|~A~B |+|A  B |=20, 则|~A~B | = 20 - (|A|+|B|-|AB|) =20 - (12+10-5) = 3

C

È È ... È A A A 1 2 n n A Ç Ç... - + + ... 2 1 ) (

3.4 序偶与笛卡尔积 3.4序偶与笛卡尔积 序偶 笛卡尔乘积 三个定理

序偶 具有确定次序的两个元素的集合，记为 例

> < x , , ... 序偶(续) n 元组也可以定义为一个序偶 =<< > >=< < 2 1 =<< - > >=< < n y x , , ... 2 1

笛卡尔乘积 也是一集合,元素为序偶. 约定： 或 若 则

例1 已知 求 解：

笛卡尔乘积(续) 不是三元组

笛卡尔乘积(续) 为了与 n 元组一致，我们约定： 特别地 = A A  = ) ( } , { x Î Ù > < 2 1 = - ) ( } , { x Î Ù > < <<  ••• ••• 特别地 n A = •••  

例2 做一个市场调查，被调查的人群按照如下规则分类： 性别S：男(m); 女(f) 学历L：初中(e); 高中(h); 大学(c) ; 大学以上(g) 即 S ={m,f}, L={e,h,c,g} 则S  L包含了所有人群的分类(8类）

例3 一个软件厂商为其所开发的软件提供了三个属性： 开发语言：L = {c, f, j} 内存：M = {8, 16, 32} 操作系统： O = {u, d} 则 L  M O包括了该软件的所有分类（18类）。

结论 = | A A A | | A | = | | A A A | A × | | A | | A |   •••   •••  | | A A A   •••  | A × | | A |  •••  | A | 1 2 n 1 2 n n = | A  A  •••  A | | A | n

定理 定理1 设 A, B, C 为任意三个集合, 则有

例 试证 (A  B )  C = (A  C)  (B  C) 证明: 若 < x, y > (A  B) C  ( x (A  B) )  ( y  C )  ( xA  x B )  ( y  C )  ( xA  yC )  (x B  y  C )  (< x, y >AC)(< x, y >BC)  < x, y >(( AC) (BC)) 因此, (A  B )  C = (A  C)  (B  C)

定理3：若A, B, C, D 为四个非空集合，则 的充分必要条件为 定理(续) 定理2：若 ,则 定理3：若A, B, C, D 为四个非空集合，则 的充分必要条件为

3.5 关系及其表示 3.5 关系及其表示 二元关系 X 到Y 的关系 前域、值域 关系的表示

y R x Y) R (x 任一序偶的集合,确定了一个 二元关系R. 关系(二元关系) 任一序偶的集合,确定了一个 二元关系R. 若任一序偶< x, y>在 R中，则记为< x , y>R 或 xRy ; 否则记为< x , y>R 或 y R x Y) R (x

X  Y 的任何子集,都定义一种关系 R，称作 X 到 Y 的关系. 若 X=Y,则 R 为集合 X 上的关系. 空关系: 全域关系: 恒等关系: IX 是 X 上的二元关系，且满足 如果集合X 有n个元素, 则其恒等关系也有n个元素. }. , { X x I Î > < =

例1 从X到Y的关系 R是A中的小于关系 实数中的平方关系 集合A上的恒等关系 X = { 1 , 2 , 3 } Y = { r , s {< 1,r >,< 2,s >,< 3,r >} 从X到Y的关系 } 3 , 2 1 { = A R是A中的小于关系 > < R )} ( ) , { 2 x y R Q = Ù Î > < 实数中的平方关系 = } 3 , 2 1 { A 集合A上的恒等关系

例2 已知有五个城市的航班服务，下表是从ci到cj的航线的票价， 解： R =   C1 C2 C3 C4 C5 1400 1000 1500 2000 1900 1600 2200 1100 1800 2500 1200 From To 解：  R = {<c1,c2>, <c1,c3>, <c3,c1>, <c4,c3>, <c5,c2>} R是定义在城市的集合A={c1,c2,c3,c4,c5}上的关系，ci R cj当且仅当从ci到cj的票价小于1500.

问题： ？ n 个元素的集合上, 可以定义多少个关系？ 因为一个集合 X 上的关系是 X  X 的子集，而

若存在y,使<x,y>S的所有x的集合, 称为S的前域(定义域), 记为D(S)或Dom(S).

若存在x,使<x,y>S的所有y的集合,称为S的值域，记为 R(S)或Ran(S).

例3 = = X { 1 , 2 , 3 } Y { r , s } R = {< 1,r >,< 2,s >,< 3,r >} Dom ( R ) = { 1 , 2 , 3 } = X Ran ( R ) = { r , s } = Y A R Ran Ì = } 3 , 2 { ) ( 1 R是X中的小于关系 > < Dom 设 R 是从 X 到 Y 的关系，则 Dom(R)X Ran(R)Y

定理 若R和S是从集合X到集合Y的两个关系，则R、S的并、交、补、差、对称差仍是X到Y的关系。

例4 已知： A 是一所学校所有学生的集合，B是该校所有课程的集合。 R1：包含所有的序偶<a,b>, 其中学生a 学习了课程b; R2：包含所有的序偶<a,b>, 其中学生a需要学习课程b。 求：R1∪R2 , R1R2 , R1R2 ？

例4（续） 解：R1∪R2 包含所有的序偶<a,b>, 其中学生a学习了课程b, 或a需要学习b. R1  R2 包含所有的序偶<a,b>, 其中学生a学习了课程b，并且他需要学习b. R1 R2 包含所有的序偶<a,b>, 其中学生a学习了课程b，但是他并不需要学习b; 或a需要学习课程b，但是他没有学习.

关系的表示方法——关系矩阵 两个有穷集合 } , { x X = y Y 且R是从X到Y的二元关系，若 则称 是R的关系矩阵. ••• 2 1 m x X = n y Y ••• 且R是从X到Y的二元关系，若 则称 是R的关系矩阵.

例5 已知 试求 解:

设R是有限集合X到集合Y上的一个二元关系. 关系的表示方法——关系图 设R是有限集合X到集合Y上的一个二元关系. 以X和Y中的元素为图中的结点,如果<xi ,yj>是R的元素,则以xi 为起点, 以yj 为终点,作有向边所构成的图.

例6 已知 试求关系图. 1 2 3 4 解：

例7 R={<a,a>,<b,b> <c,a>,<c,b>,<c,c> 解： 已知 R={<a,a>,<b,b> <c,a>,<c,b>,<c,c> <d,b>,<d,d>} a b d c ú û ù ê ë é = 1 R M 求关系及关系矩阵

小 结 关系（二元关系） 从X到Y的关系、X上的关系 关系的域（前域）、值域 关系的集合运算仍然是关系 关系的表示方式：集合表达式、 关系矩阵、关系图

3.6 关系的性质 3. 6 关系的性质 自反性 反自反性 对称性 反对称性 传递性

1.自反性 在 MR 中, rii = 1. 即关系矩阵中主对角线上所有元素都是1. 在关系图中每个结点都有自回路. 在实数集合中，小于等于关系是自反的，小于关系是反自反的。 平面上三角形的全等关系是自反的。 日常生活中父子关系是反自反的。 应该注意的是一个关系不是自反的，也不一定是反自反的。

例: 已知X={a,b,c}, 下面关系哪些是自反的?  

2.反自反性 在 MR 中, rii = 0. 即关系矩阵中主对角线上所有元素都是0. 在关系图中任一结点均无自回路.

例: 已知X={a,b,c}, 下面关系哪些是反自反的?   

？ 问题： 一个关系不是自反的，就一定是反自反的吗？ 不一定。 如：A={1,2,3}, S={<1,1>,<1,2>,<2,3>,<3,3>} 则 S 既不是自反的也不是反自反的。

3.对称性 在 MR 中,若 rij = 1, 则必有rji = 1. 即关系矩阵是对称的. 在关系图中结点间若有边,必是往返两条.

例: 已知X={a,b,c}, 下面关系哪些是对称的?  

4. 反对称性 在 MR 中,若 i  j, 且 rij = 1, 则 rji = 0. 即关系矩阵中以主对角线对称的元素不能同时为1(但可同时为0). 在关系图中若两点间有边,只会是一条,没有返回边.

例: 已知X={a,b,c}, 下面关系哪些是反对称的?     

？ 问题： 一个关系不是对称的，就一定是反对称的吗？ 不一定。 如：A={1,2,3}, S={<1,2>,<1,3>, <3,1>} 则 S 既不是对称的也不是反对称的。 N={<1,1>,<2,2>,<3,3>} N即是对称的，也是反对称的。

5. 传递性 在 MR 中,若 rij = 1, rjk = 1则 rik = 1. 在关系图中, 若从结点 a 到结点 b 有长度大于 1 的路,则从 a 到 b 必有长度为 1 的路存在.

例: 已知X={a,b,c}, 下面关系哪些是传递的?    

R1 R1 是自反的、反对称、传递的。

R2 R2 是反对称的。

R3

R4 R4 是对称的。

R5 R5 是自反的、对称的、传递的。

R6 R6 是反自反的、反对称、传递的。

R7 R7 是反自反、反对称的。

R8 R8 是反自反、反对称、传递的。

表 1   自反性 反自反性 对称性 反对称性 传递性 R1  R2 R3 R4 R5 R6 R7 R8 序关系 等价关系

小 结 在关系矩阵中 自反性 主对角线上的所有元素都是1. 反自反性 主对角线上的所有元素都是0. 对称性 关系矩阵是对称的. 小 结 在关系矩阵中 自反性 主对角线上的所有元素都是1. 反自反性 主对角线上的所有元素都是0. 对称性 关系矩阵是对称的. 反对称性 以主对角线对称的元素不能同时为1. 传递性 对 M2 中1所在的位置 , M中 相应的位置都是1.

小结(续) 在关系图中 自反性 每点必有自回路. 反自反性 任一结点均无自回路. 对称性 结点间若有边,必是往返两条. 自反性 每点必有自回路. 反自反性 任一结点均无自回路. 对称性 结点间若有边,必是往返两条. 反对称性 若两点间有边, 只会是一条, 没有返回边. 传递性 若从结点 a 到结点 b 有长度大于 1 的路,则从 a 到 b 必有长度为 1 的路存在.

？ 问题 n 个元素的集合上，可以有多少个自反的关系？ 因为一个集合 X 上的关系是 X  X 的子集, X  X 共有 n2 个元素. R 如果是自反的, 则对于任意 xX, <x,x>R, 而另外 n(n-1) 个元素可能在或不在 R 中，所以共有 2n(n-1) 个关系.

3.7 复合关系和逆关系 复合关系 逆关系 例如: F:父子关系 F1: {<老李,大李>} , F2: {<大李,小李>} F1 º F2 : 祖孙关系 B : 兄弟关系 B º F : 叔侄关系 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学 例如: 整数集合Z上的大于关系 逆关系为 Z上的小于关系

复合关系 Ù Î > < = Z z X x S R º , { 设 R 是从 X 到 Y 的关系, S 是从 Y 到 Z 的关系, 则 R º S 称为 R 和 S 的复合关系(合成关系), 表示为 Ù Î > < = Z z X x S R º , { 显然 R º S 是从 X 到 Z 的关系。

º º 例1 已知 求:R º S 和 S º R 解: } 1 , 4 2 3 { > < = S R S R º R ¹

例1(续) 关系图 Z X Z X Y Z X S R ¾ ® º

º º º º 定理1 已知集合 X, Y, Z, W 则有 复合对集合并运算有分配律; 复合对集合交运算没有分配律. ) ( R a È 2 3 1 ) ( R a º È = º 4 3 2 ) ( R b È = º 3 1 2 ) ( R c Ç Í º 4 3 2 ) ( R d Ç Í 复合对集合并运算有分配律; 复合对集合交运算没有分配律.

定理2 已知集合 X, Y, Z, W 则有 ) ( 3 2 1 R º = 结合律

关系的幂运算 = R 设 R 为集合 A 上的关系，R 的 n 次幂R(n) 可以定义如下： 1 , ) 2 ( ³ = n R - n R o R = o ) ( 1 显然, R(0) 是 A 上的恒等关系。 2 ••• n -1 n

定理3 = R 设 R 为 A 上的关系，m,n 是自然数，则下面的等式成立： ) ( n m R + = o 在关系图中，xRy 表示从结点 x 到 y 有一条长度为 1 的有向路径，xRny 则表示从结点 x 到结点 y 有一条长度为 n 的有向路径。

例2 已知 且有 求关系的幂运算。

R1 , ) 4 ( 1 f = R ...

R2 ... , ) 3 ( 2 6 R = 即 ... , 1 2 ) ( 3 = + k R i

R3 ... = ) 4 ( 3 R

R4 对于有穷集 A 和 A 上的关系 R， R 的不同次幂只有有限个. ... , R = 1 , = i k R ... ... , R ) 1 ( 4 3 R = ... , ) ( 4 R = 1 , ) ( 4 2 = + i k R ... 对于有穷集 A 和 A 上的关系 R， R 的不同次幂只有有限个.

例3 用关系图求关系的幂运算 解：

} z Z 复合关系的矩阵表示 }, , { y Y ... = x X = M 其中 逻辑乘 逻辑加 p o 2 1 n m S R 逻辑加() 0  0 = 0 0  1 = 1 1  0 = 1 1  1 = 1 S R M o = 逻辑乘() 0  0 = 0 0  1 = 0 1  0 = 0 1  1 = 1 其中 逻辑乘 逻辑加

例4 用关系矩阵求关系的幂运算 2 ) ( R M =  1 ú û ù ê ë é = 1  1 1

例4（续） 2 ) ( 3 R M =  ú û ù ê ë é = 1 

逆关系 设 R 为 X 到 Y 的二元关系,如将 R 中每一序偶的元素顺序互换,所得到的集合称为 R 的逆关系.记作 Rc.

定理4 设 R, R1, R2都是从 X 到 Y 的二元关系，则 C R = ) ( R = X×Y - R , 其中

定理4 R = ) ( 设 R, R1, R2都是从 X 到 Y 的二元关系，则 C R = ) ( R = X×Y - R , 其中 <x,y>(R)c  <y,x>R  <y,x>R  <x,y >Rc  <x,y>Rc 因为R1- R2 = R1 R2 故 (R1- R2)c = (R1 R2)c = R1c  (R2)c = R1c  R2c = R1c - R2c

定理 定理5 则 R S = ) ( 定理6 R 为 X 上的二元关系,则 a) R 为对称的充分必要条件是 R = Rc  定理6 R 为 X 上的二元关系,则 a) R 为对称的充分必要条件是 R = Rc b) R 为反对称的充分必要条件是

例5 已知：集合 A={1,2,3}, 令关系 R={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>} S={<1,1>,<1,2>,<2,2>,<3,2>,<3,3>} 求：R∩S、Rc、 AA={<1,1>,<1,2>,<1,3>,<2,1>, <2,2>,<2,3>,<3,1>, <3,2>,<3,3>} R∩S ={<1,1>,<1,2>, <2,2>,<3,3>} Rc ={<1,1>,<2,1>,<3,1>,<2,2>,<3,3>} 解:

3.8 关系的闭包运算 自反(对称、传递)闭包定义 闭包求法（定理） Warshall 算法 闭包性质 集合是集合论中的一个原始概念，原始概念是不能被精确定义的，因为我们没有比它更原始的概念，因此我们只给出集合这个概念的非形式的描述，来说明这个概念的含义。这正如同欧几里德几何中的点不加定义，而作为原始概念一样。 实际上，集合就在我们身边：正在上课的同学

对给定的关系,用扩充一些序偶的办法得到具有某些特性的新关系，这就是闭包运算。 闭包运算概念 对给定的关系,用扩充一些序偶的办法得到具有某些特性的新关系，这就是闭包运算。 闭包运算是一种一元运算。

自反（对称、传递）闭包 设 R 是 X 上的二元关系, 若有另一个关系 R’ ，满足： a) R’是自反(对称、传递）的; b) R R’; c) 对任意的自反（对称、传递）关系R’’,若R R’’,则必有R’ R’’； 则称 R’ 是 R 的自反（对称、传递）闭包,记作 r(R) (s(R) 、t(R) ) 。

自反（对称、传递）闭包 X 上的关系 R的自反闭包, 对称闭包, 传递闭包, 就是包含 R 的 X 上最小的 自反关系. 对称关系. 传递关系.

定理1 R 是 X 上的二元关系, 则 R是自反的充要条件是 R是对称的充要条件是 R是传递的充要条件是

È R t R ... È = R È = ... n k £ I R r È = ) ( 定理2 R 是 X 上的二元关系，则 R s È C R s È = ) ( n 是集合X 的势 + ¥ = È R t i ) ( 1 R ... È = ) 2 ( ) ( 2 k R È = ... n k £

例1 已知集合X与关系R，试求r(R) s(R) t(R). 解： C R s È = ) ( } , { > < = b c a

例1（续）

例2 已知集合 X 和关系 R, 试求 t(R). 解:

例2（续）

例3 已知集合 X 与关系 R,试求 r(R) s(R) t(R). 解：

例3（续）

例3（续）

1) 置新矩阵 A : = M； 2) i: = 1； 3) 对所有 j ,若 A[j,i] = 1，则对 4) i:= i+1; Warshall 算法 1) 置新矩阵 A : = M； 2) i: = 1； 3) 对所有 j ,若 A[j,i] = 1，则对 n k , 2 1 ... = 4) i:= i+1; 5)若 i ≤ n，则转3)，否则停止。

例4 用Warshall算法求传递闭包 i=1时，j=4

例4 用Warshall算法求传递闭包 i=1时，j=4

例4（续） i=2时，j=1,4

例4（续） i=2时，j=1,4

例4（续） i=3时，j=1,2,4

例4（续） i=3时，j=1,2,4

例4（续） i=4时，j=1,2,3,4

例4（续） i=4时，j=1,2,3,4

例5 试证对称关系的传递闭包也是对称关系 证明： 例5 试证对称关系的传递闭包也是对称关系 证明： 若 <a,b>  t(R), 则有 i, 使得 <a,b>R(i), 即存在 c1,c2,…,ci-1  X, <a,c1>  R, <c1,c2>  R, … , <ci-1,b>  R 因为 R 是对称的，有 <b,ci-1>  R, … , <c1,a>  R, 得到 <b,a>  R(i) , 即 <b,a>  t(R). 得证.

例6 反对称关系的传递闭包总是反对称关系? 解：不一定，例如： 是对称的.

闭包的性质 定理3 设 R 是 X 上的二元关系， 若 R 是自反的, 则 s(R) 和 t(R) 是自反的； 若 R 是对称的, 则 r(R) 和 t(R) 是对称的； 若 R 是传递的, 则 r(R) 是传递的； rs(R) = sr(R)； rt(R) = tr(R)； ts(R)  st(R).

试证 性质 rs(R) = sr(R) 证明： 设 Ix 是 X 上的恒等关系

)) ( I È ) ( I È ) ( I È ( R I È = (  R   R  R 试证 性质 rt(R) = tr(R) 证明： 说明1 ) ( ( i X R I È = ¥ i 1 )) ( ( ) 1 j i X  R I = ¥ È ) ( 1 j i X   R I = ¥ È ) ( 1 i X  R I ¥ = È i 得证.

试证 性质 st(R)  ts(R) 证明： 可证若R2 R1, 则 s(R2)  s(R1), t(R2)  t(R1) 说明2 根据闭包的定义，可得 R s(R) 所以 t(R) ts(R) , st(R) sts(R) 又因为对称关系的传递闭包是对称的，所以ts(R)是对称的， 而一个关系R是对称的充要条件是R=s(R),所以 sts(R)= ts(R)， 从而st(R)  ts(R) . 得证.

 R  R  R  R 定理 设 R 是 X 上的二元关系，则 ) ( I R IX È 证明：用数学归纳法, 对 n 归纳. 1 i ) ( n X  R I R IX = È 证明：用数学归纳法, 对 n 归纳. n=1, 结论显然存在; 假设 1 i ) ( n X  R I R = È ) ( (n+1) X R I  =  (n) 1 i )) ( (i) n X  R I = È  ) R I  = X I  )) ( R I  1 i ) (i) n  R È

 R  R  R  R ( R ) 定理 设 R 是 X 上的二元关系，则 ( IX È R ) = I È ( ) n ( IX È R ) ( n ) = I È  R ( ( i ) ) X i = 1 证明：用数学归纳法, 对 n 归纳. n=1, 结论显然存在; 假设 n È = È  R ( I R ) ( n ) I ( ( i ) ) X X i = 1 = ) ( (n+1) X R I  I 1 i = È  R  R ) ( n i = X = X I È R ) ( i  R n 1 n+1 2 n+1 = X I È ) ( i ( R ) i = 1 返回

说明2 若 R2 R1, 则 s(R2)  s(R1) 因为s(R1) 对称且R1  s(R1), 由于 R2 R1，所以R2  s(R1)； 由s(R2)的定义，s(R2)是包含R2的最小的对称关系；所以s(R2)  s(R1)。 同理可说明若 R2 R1, 则 t(R2)  t(R1) 返回

3.9 集合的划分和覆盖 3. 9 集合的覆盖与划分 覆盖 划分 加细与真加细 交叉划分 划分的求法

 S A 覆盖与划分 令 A 为给定非空集合,S={S1,…,Sm},其中 且 , 则称 S 是 A 的覆盖. 若还满足条件 i 1 且 , 则称 S 是 A 的覆盖.  S A = 若还满足条件 则称 S 是 A 的划分. 划分是覆盖的特殊情形. 划分的元素 Si 称为划分的类.

例1 令 Z=所有整数的集合 A1=所有偶数的集合 A2=所有奇数的集合 则 {A1,A2}是 Z 的一个 划分。

例2 已知 下面哪些集合是 A 的覆盖或划分？ 是覆盖 是覆盖 不是覆盖 是划分 是划分 是划分

两个特殊的划分 最小划分： 是由作为类的集合本身构成. 最大划分： 是由包含单个元素的类组成. 最小划分 最大划分

加细与真加细 设 A 和 B 是同一集合 X 的两种划分,且有 , } { A ... = , } { B ... = 2 1 m A ... = , } { 2 1 n B ... = 若 A 的每一个类都是 B 的某一类的子集,即 , 则称 A 是 B 的加细。 若 A 是 B 的加细,且 BA, 则称 A 是 B 的真加细。

例3：已知 X={a,b,c,d} A={{a,b},{c,d}} 下面的 Bi 哪些是 A的加细？ 真加细 加细 }} { }, {{ 3 d c b a B = 真加细 }} { }, , {{ 4 d c b a B = 不是加细 }} { }, , {{ 5 d c b a B = 不是加细 }} , { }, {{ 6 c b d a B = 不是加细 对划分A 的加细,实质上是对 A 的类 Ai 进行再划分。 3.9 集合的覆盖与划分北京

B={B1,B2,…,Bs} 是同一个集合 X 的两种划分，则其中所有 Ai  Bj   组成的集合，称为是原来两种划分的交叉划分。 若 A={A1,A2,…,Ar} 与 B={B1,B2,…,Bs} 是同一个集合 X 的两种划分，则其中所有 Ai  Bj   组成的集合，称为是原来两种划分的交叉划分。

例4 X =所有生物的集合 其交叉划分为 P =所有植物的集合 { PE, PF, A =所有动物的集合 AE, AF } 则 {P,A} 是 X 的一种划分。 其中 PE表示史前植物 PF表示史后植物 AE表示史前动物 AF表示史后动物 E =所有史前生物 F =所有史后生物 则{E,F}也是 X 的一种划分。

定理1 若 A, B 是同一集合 X 的两种划分,则其交叉划分也是原集合的一种划分。 交叉划分（续） 定理1 若 A, B 是同一集合 X 的两种划分,则其交叉划分也是原集合的一种划分。 定理2 任何两种划分的交叉划分，都是原来划分的一种加细。

一般说来, 能由全集 E 的一些子集的集合, 求得 E 的一种划分。 划分的一种求法 一般说来, 能由全集 E 的一些子集的集合, 求得 E 的一种划分。 设 A, B, C  E, 由 A, ~A, B, ~ B, C, ~ C 可生成 23 个 不同的交集。

互不相交,称为完全交集或极小项. ) 7 , 1 ( ... = i I

设 A1,A2,…,An 是 E 的 n 个子集，则有 2n 个极小项，且 划分的一种求法（续） 显然有 i I E 7 1 = È ... 设 A1,A2,…,An 是 E 的 n 个子集，则有 2n 个极小项，且

定理3 设 A1, A2 , … , An 是 E 的 n 个子集, 由Ai 所生成 的全部极小项的集合，构 成 E 的一种划分。 划分的一种求法（续） 定理3 设 A1, A2 , … , An 是 E 的 n 个子集, 由Ai 所生成 的全部极小项的集合，构 成 E 的一种划分。

3.10 等价关系与等价类 3. 10 等价关系与等价类 等价关系 等价类 商集 等价关系与划分

等价关系 设 R 为定义在集合 A 上的一个关系, 若 R 是 a) 自反的 b) 对称的 c) 传递的 则 R 称为等价关系。 在学生的集合中，属于同一个班级的关系； 三角形中的相似关系； 在扑克牌中同花色的关系、同点数的关系等。

例1 已知 X={1,2,…,7}和I 是整数集合, 求 R. 解:

例1（续）

模 m 等价关系 I 为整数集合, I+为正整数集合，对任何 m I+ , 若有 则称 R 是模 m 等价关系（同余关系）, m 为等价的模数.记为 定理1 I 是整数集合,任何集合 X I 中的模 m 同余关系都是一种等价关系.

等价类 设 R 为集合 A 上的等价关系, 对任何 a A, [a]R = {x | xA  aRx} 集合 A 中与 a 有等价关系 R 的所有元素构成 [a]R , 简记为[a].

例2 已知 试画出 R 的等价关系图, 并求出各元素的 R 等价类. 解：

定理2 X 为一集合, R 是 X 中的等价关系,若 aX, 则 a[a]R . 等价类的性质 定理2 X 为一集合, R 是 X 中的等价关系,若 aX, 则 a[a]R . 定理3 R 是 X 中的等价关系,则对所有 a,bX, R 等价类总是非空的。 a) 若 aRb, 则 b) 若 , 则 b R a __

R 是非空集合 A 上的等价关系, 其等价类的集合{[a]R | aA}称作 A 关于 R 的商集，记作 A/R. 商集的元素个数（即Ａ在Ｒ下的等价类个数）称为等价关系Ｒ的秩。

例3 设 I 是整数集合, R 是模3同余的关系, 试求：集合 I 对 R 的商集 I/R . 解： 由 I 的各元素生成的 R等价类为 } , 6 3 { ] [ ... - = R } , 7 4 1 2 5 { ] [ ... - = R } , 8 5 2 1 4 { ] [ ... - = R

等价关系与划分 定理4 集合 A 上的一个等价关系R, 决定了 A 的一个划分，该划分就是商集 A/R 。 (a R b 当且仅当 a 和 b 在同一个分块中）. 划分和等价关系在本质上是相同的

例4 已知X={a,b,c,d,e}, C={{a,b},{c},{d,e}} 试写出由 C 导出的 X 中的等价关系 R ,并给出关系矩阵和关系图. 解：

例4（续）

5 2 3 4 1 例5 设 A={1,2,3}, 求出A上所有的等价关系 解: 先求A的各种划分 1 2 3 设对应于 i 的等价关系为Ri ,则： R1={<1,1>,<2,2>,<3,3>} = IA R2={<1,2>,<2,1>} ∪ IA R3={<1,3>,<3,1>} ∪ IA R4={<2,3>,<3,2>} ∪ IA R5={<1,2>,<1,3>,<2,1>,<2,3>, <3,1>,<3,2>} ∪ IA

定理 设R1和R2是非空集合 A 上的等价关系, 则 R1= R2 当且仅当 A/R1 = A/R2 .

小结 等价关系的概念 等价关系与划分 R 是集合 A 上的一个等价关系，则下列命题是等价的： 1、<a,b>  R

3.12 序关系 偏序关系和偏序集 y 盖住 x 哈斯图 链 (反链) 全序关系 (线序关系) 极大元 (极小元) 最大元（最小元） 3.12 序关系 偏序关系和偏序集 y 盖住 x 哈斯图 链 (反链) 全序关系 (线序关系) 极大元 (极小元) 最大元（最小元） 上界 (下界) 上确界 (下确界) 良序 3. 12 序关系

偏序关系和偏序集 设 R 为定义在集合 A 上的一个关系, 若 R 是 a) 自反的 b) 反对称的 c) 传递的

例1 证明在实数集R上, 是偏序关系. 证明 对于任何 a  R，有 a a 成立，故  是自反的； 对于任何 a,b  R, 如果有 a  b 且 b a 成立，则必有 a=b ,故  是反对称的； 如果有 a b, b c 成立，则必有 ac, 故  是传递的。 因此是偏序关系。

例2 已知 A={2,3,6,8},  ={<x,y>|x整除y} 验证  是偏序关系. 解：

y 盖住 x 在偏序集合 <A,  > 中，如果 x , y A, x  y, x  y, 且没有其它元素 z,满足x  z, z  y, 则称元素 y 盖住元素 x . 并且记 COVA={<x,y>| x, y A; y 盖住 x} 对于给定偏序集合 <A,  > ，它的盖住关系是唯一的。

哈斯图 对于给定偏序集合 <A,  >，其哈斯图做图规则如下： （1）用小圆圈代表元素； （2）如果 x  y 且 x  y，则将代表 y 的小圆圈画在代表 x 的小圆圈之上； （3）如果 <x,y>COVA, 则在 x 与 y 之间用直线连接。

例3 A 是 m=12 的因子集合, 为整除关系, 求 COVA，并画出哈斯图. 解:  = {<1,2>, <1,3>, <1,4>, <1,6>, <1,12>, <2,4>, <2,6>, <2,12>, <3,6>, <3,12>, <4,12>,<6,12>} ∪ IA COVA={<1,2>,<1,3>,<2,4>, <2,6>, <3,6>, <4,12>, 6,12> }

哈斯图与关系图 哈斯图是简化的关系图 (1)自反性：每个顶点都有自回路，省去自回路。 (2)反对称性：从小到大安置顶点，可省略箭头。 (3)传递性：由于有(ａ，ｂ)，(ｂ，ｃ)∈R 则 (ａ，ｃ)∈R，故只画（ａ，ｂ），（ｂ，ｃ）对应的边，省略边（ａ，ｃ）。

例4 画出哈斯图 2018/12/8

例5 A1={1,2,3,4} A2={φ,{a},{a,b}, 为小于等于关系 {a,b,c}} 为包含关系 不同的偏序集, 哈斯图可以有同样的结构

链（反链） 设 <A,  > 是一偏序集合，在 A 的一个子集中，如果每两个元素都是有(无)关系的，则称这个子集是链(反链)。 约定：若 A 的子集只有单个元素,则它既是链又是反链.

例6 已知 A={a,b,c,d,e} > < , { b e a d c R } = 验证 <A,R> 是偏序集，画出哈斯图，举例说明链和反链。 解： ú û ù ê ë é = 1 R M 关系矩阵对角线都为1，且rij 和rji 不同时为1，所以 R 是自反的和反对称的。

例6（续） 哈斯图 关系图 {a}、{a,b,c,e}和{a,d,e} 是链 {a}、{b,d}和{c,d} 是反链 COVA={<a,b>,<a,d>, <b,c>, <c,e>,<d,e>} R是传递的。

全序（线序） 在偏序集 <A,  > 中，如果 A 是一个链，则称 <A,  > 为全序集合 (线序集合)，二元关系  为全序关系 (线序关系)。

极大元（极小元） 设 <A,  > 是一个偏序集合, 且 B 是 A 的子集,若有某个元素 b  B, B 中没有任何元素 x 满足 b  x 且 b  x 则称 b 为 B 的极大元 (x  b) (极小元）.

例7 已知 偏序关系哈斯图如下 B 的极大元集： B 的极小元集： 例7 已知 偏序关系哈斯图如下 B 的极大元集： B 的极小元集： 极大元与极小元不唯一 当 B=A 时，其极大元集是{14,21,15}，极小元集是{2,7,3,5}

最大元（最小元） 设 <A,  > 是一个偏序集合, 且 B 是 A 的子集,若有某个元素 b B, 对于B 中每一个元素 x 有 xb , , 则称 b 为 B 的最大元 (b x) (最小元). 定理1： 令<A,  > 为偏序集且 BA，若 B 有最大(最小)元,则必是唯一的.

例8 B={{a}, φ}， 最大元：{a} 最小元：φ B’={{a},{b}}， 最大元：无 最小元：无

) 成立, ( x y B £ ® Î " ) 成立, ( y x B £ ® Î " ) 成立, ( y x B = ® £ Ù Î " 小结 < A, >是偏序集,BA,若 yB, 使得 则y是B的最小元; ) 成立, ( x y B £ ® Î " ) 成立, ( y x B £ ® Î " 则y是B的最大元; ) 成立, ( y x B = ® £ Ù Î " 则y是B的极小元; ) 成立, ( y x B = ® £ Ù Î " 则y是B的极大元。

上界（下界） 设 <A,  > 是一个偏序集合, 对于 BA, 若有 aA, 且对 B 的任意元素 x 都满足 x  a (a  x), 则称 a 为子集 B 的上界 (下界).

例9 B={a,b,c,d,e,f,g} 上界： h,i,j,k 下界：无 B’={h,i,j,k} 上界： 无 B’’={h,i,f,g} 上界、下界 不唯一 上界： k 下界：a

上确界（下确界） 设 <A,  > 是一个偏序集合且 B  A, a 为Ｂ 的任一上界，若对Ｂ 的所有上界 y ，都有a  y 则称 a 为 B 的最小上界 (上确界). 同样，若ｂ为Ｂ 的任一下界，若对Ｂ的所有下界 y ，都有 y  b 则称 b 为 B 的最大下界 (下确界).

例10 B={a,b,c,d,e,f,g} 上界： h,i,j,k 无上（下）确界 下界：无 B’={h,i,j,k} 上界： 无 B’’={h,i,f,g} 上确界： k 下确界：a 上界： k 下界：a

) ( y x B £ ® Î " 小结 < A,  >是偏序集，B  A, 若 y  A, 使得 成立,则 y 是 B 的下界; ) ( y x B £ ® Î " 成立,则 y 是 B 的 上界; 令C = { y | y 为 B 的下界}，则称 C 的最大元为 B 的最大下界; 令 D = { y | y 为 B 的上界}，则称 D 的最小元为 B 的最小上界。

良序 任意偏序集合, 假如它的每一个非空子集存在最小元素，这种偏序集称为良序的。 定理2：每一个良序集合，一定是全序集合。 定理3：每一个有限的全序集合，一定是良序集合。

上界： 6,12,24,36 上确界：6 下(确)界： 无 练习1 <{2,3,6,12,24,36},整除关系> 练习1 <{2,3,6,12,24,36},整除关系> 画出哈斯图,并求 B = {2,3,6} 上、下(确)界 上界： 6,12,24,36 上确界：6 下(确)界： 无

练习2 <{1,2,…,12}, R整除>, 画出哈斯图,并求 B = {2,3,6} 上、下(确)界 上界： 6,12 上确界：6 下(确)界： 1

练习3 已知哈斯图, 求 B={c,d,e}的 上、下(确)界 下界： a,b 下确界：无