集合与关系《应用离散数学》
第3章
21世纪高等教育计算机规划教材
目录
3.1 集合及其运算
3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分
3.5 偏序关系与拓扑排序3.6 函 数
3.7 集合的等势与基数3.8 多元关系及其应用
集合是现代数学中最重要的基本概念之一，数学概念的建立由于使用了集合而变得完善并且统一起来。

集合论已成为现代各个数学分支的基础，同时还渗透到各个科学技术领域，成为不可缺少的数学工具和表达语言。

对于计算机科学工作者来说，集合论也是必备的基础知识，它在开关理论、形式语言、编译原理等领域中有着广泛的应用。

本章首先介绍集合及其运算，然后介绍二元关系及其关系矩阵和关系图，二元关系的运算、二元关系的性质、二元关系的闭包，等价关系与划分、函数，最后介绍多元关系及其在数据库中的应用等。

3.1 集合及其运算
3.1.1 基本概念
集合是数学中最基本的概念之一，如同几何中的点、线、面等概念一样，是不能用其他概念精确定义的原始概念。

集合是什么呢？直观地说，把一些东西汇集到一起组成一个整体就叫做集合，而这些东西就是这个集合的元素或叫成员。

例3.1
（1）一个班级里的全体学生构成一个集合。

（2）平面上的所有点构成一个集合。

（3）方程 的实数解构成一个集合。

（4）自然数的全体（包含0）构成一个集合，用N表示。

（5）整数的全体构成一个集合，用Z表示。

（6）有理数的全体构成一个集合，用Q表示。

（7）实数的全体构成一个集合，用R表示。

（8）复数的全体构成一个集合，用C表示。

（9）正整数集合Z+，正有理数集合Q+，正实数集合R+。

（10）非零整数集合Z*，非零有理数集合Q*，非零实数集合R*。

（11）所有n 阶(n≥2)实矩阵构成一个集合，用M n(R)表示，即
而所有n 阶(n≥2)可逆实矩阵也构成一个集合，用 表示。

通常用大写英文字母表示集合的名称，用小写英文字母表示集合里的元素。

若元素a 属于集合A ，记作 ；若元素 a 不属于集合 A ，记作 。

并用 或 记集合 A中元素的个数。

集合的表示方法通常有下列两种。

1．列举法
列举法是列出集合中的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。

下面是用列举法表示的集合：
有时列出集合中所有元素是不现实或不可能的，如上面的B 和C ，但只要在省略号前或后列出一定数量的元素，能使人们一看就能了解哪些元素属于这个集合就可以。

2．描述法
描述法是用谓词描述出元素的公共特性，其形式为 ，表示 S 是使 为真的 x 的全体。

下面是用描述法表示的集合：
下面介绍表示集合的有关符号和方法。

在一个具体问题中，若一个集合包含我们讨论的每一个集合，则称它是全集，记作 E。

全集具有相对性，不同的问题有不同的全集，即使是同一个问题，也可以取不同的全集。

例如，当讨论有关整数的问题时，可以整数集作为全集，也可以把有理数集取作全集。

没有元素的集合叫做空集，记作 。

3.1.2 集合的运算
集合的基本运算有并、交、补、差和对称差，它们的定义如下。

以上集合之间的关系和运算可以用文氏图（Venn Diagram）形象、直观地描述。

文氏图通常用一个矩形表示全集 ，矩形中的点表示全集 E 中的元素， E 的子集用矩形区域内的圆形区域表示，图中阴影区域表示新组成的集合。

图3.1就是一些文氏图的实例。

图3.1 文氏图
由文氏图容易看出下列关系成立：
等等。

这说明使用文氏图能够对一些问题给出简单、直观的解释，这种解释对分析问题有很大帮助。

不过，文氏图只是起一种示意作用，可以启发我们发现集合之间的某些关系，但不能用文氏图来证明恒等式，因为这种证明是不严密的。

集合的并、交、差、补等具有许多性质，下面列出这些性质中最主要的几条。

定理3.1中的恒等式均可一一加以证明，下面我们选证其中的一小部分，其他的留给读者自己证明。

我们采用形式化的证明方法，在叙述中将大量用到数理逻辑的有关符号和等价公式。

上面给出的集合运算的一些恒等式，如交换律、结合律、分配律、等幂律、德·摩根律等都可以推广到多个集合中去，这里就不再列出具体的式子了。

3.1.3 集合的计算机表示
计算机表示集合的方式各种各样。

一种方式是把集合的元素无序地存储起来。

可是如果这样做，在做集合的运算时会浪费很多时间，因为这些运算需要大量的元素检索。

我们这里介绍一种利用位串表示集合的方法，集合的这种表示方法使计算集合的运算变得很容易。

位串是0个或多个字位的序列，而每个字位都有两个可能的值，即0或1，字位的这种取值来自二进制数字，因为0和1是用在数的二进制表示中的数字。

位串是计算机表示信息的基本方式。

3.2 二元关系及其运算3.2.1 笛卡尔积
证明 （这里只给出（1）的第一个等式的证明，其他的可类似地进行。

所用证明方法与证明两个集合相等一样，因为笛卡尔积也是集合。

）
因为
所以 。

由数学归纳法不难证明定理3.2对有限多个集合的并运算、交运算和差运算也是成立的。

3.2.2 二元关系及其表示
R 和S 的关系图如图3.2（a）和图3.2（b）所示。

图3.2 关系图
3.2.3 二元关系的运算
由于关系也是集合，所以对关系也可以进行并运算、交运算、补运算、差运算、对称差运算等集合的有关运算。

除了一般的集合运算外，关系本身还具有两种特殊的运算：复合运算和逆运算。

定义3.8 设 R 是从集合A 到集合B 的关系，S 是从集合 B 到集合 C 的关系，则从A 到 C 的关系称为 R 与 S 的复合关系。

即有
此例说明，复合关系不满足交换律，但复合关系满足结合律，即如下定理3.3。

定理3.3 设 R 是从集合 A 到集合 B 的关系， S 是从集合B 到集合 C 的关系， T 是从集合C 到集合 D 的关系，则
证明 （与定理3.2的证明方法类似，这里用的仍然是证明两个集合相等的方法。

）
根据定理3.3，利用数学归纳法容易证明下面结论。

3.3 二元关系的性质与闭包
3.3.1 二元关系的性质
有若干用于把集合上的关系进行分类的性质。

这里我们只介绍其中最重要的几个。

例3.14 对于下列五种二元关系，试判断哪些是自反的，哪些是反自反的，哪些是对称的，哪些是反对称的，哪些是传递的。

（1）实数集合R上的小于等于关系≤。

（2）集族上的包含于关系 。

（3）正整数集合Z+上的整除关系|。

（4）平面上直线集合L上的垂直关系⊥。

（5）平面上直线集合L上的平行关系 （认为直线不与自己平行）。

解
（1）是自反的，不是反自反的，不是对称的，是反对称的，是传递的。

（2）是自反的，不是反自反的，不是对称的，是反对称的，是传递的。

（3）是自反的，不是反自反的，不是对称的，是反对称的，是传递的。

（4）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。

（5）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。

关系的性质不仅像定理3.7所表述的那样反应在它的集合表达式上，也明显地反应在它的关系矩阵和关系图上。

表3.1列出了关系R 的五种性质在关系矩阵和关系图中的特点。

表3.1关系R的五种性质在关系矩阵和关系图中的特点
表3.2关系的五种性质和运算之间的联系。