应用离散数学第3章-集合与关系

集合与关系《应用离散数学（第2版）》第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)实矩阵构成一个集合，用Mn(R)表示，即

而所有n阶(n≥2)可逆实矩阵也构成一个集合，用

表示。

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

，记作

；若元素

a不属于集合

A，记作

。并用

或

记集合

A中元素的个数。

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

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

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

2．描述法

描述法是用谓词描述出元素的公共特性，其形式为

，表示

S是使

为真的

x的全体。下面是用描述法表示的集合：

下面介绍表示集合的有关符号和方法。

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

E。全集具有相对性，不同的问题有不同的全集，即使是同一个问题，也可以取不同的全集。例如，当讨论有关整数的问题时，可以整数集作为全集，也可以把有理数集取作全集。

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

。3.1.2集合的运算

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

以上集合之间的关系和运算可以用文氏图（VennDiagram）形象、直观地描述。文氏图通常用一个矩形表示全集

，矩形中的点表示全集

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 关系的五种性质和运算之间的联系3.3.2二元关系的闭包

关系图如图3.3所示。图3.3闭包的关系图3.4等价关系与划分

在日常生活或者科学研究中，我们常常需要对一些事物或某个集合上的元素按照某种方式进行分类。如进行举重比赛时，需要将运动员按重量级别进行分类，每一个运动员必定属于某一个重量级别，而任何一个运动员不能同时属于两个不同的重量级别。又如，对一些几何图形构成的集合，按面积相等关系将它们进行分类，即面积相等的几何图形属于一类，这样，每个几何图形必定属于一类，而且不同类没有公共点。

这种对某个集合上的元素按照某种方式进行分类就叫作集合的划分，它是一个非常重要而且应用非常广泛的概念。

集合的划分与一种重要的二元关系即等价关系密切相关，等价关系具有十分良好的性质和广泛的应用，因而成为最重要的二元关系之一。定义3.14设R是集合A上的关系，如果R是自反的、对称的、传递的，则称R是等价关系。设R是一个等价关系，若

，称

a等价于

b。例3.17（1）在全体中国人组成的集合上定义“同姓”关系，它具备自反、对称、传递的性质，因此是一个等价关系。（2）平面上直线集合L上的“平行或恒等”关系是等价关系，而L上的“垂直”关系不是等价关系，因为它既不是自反的，也不是传递的。（3）平面上三角形的“全等”关系、“相似”关系等都是等价关系。（4）“朋友”关系不是等价关系，因为它不是传递的。（5）集合的“包含于”关系不是等价关系，因为它不是对称的。

所以R为A上的等价关系。该关系的关系图如图3.5所示。

不难看到，上述关系图被分为三个互不连通的部分，每部分中的数两两都等价（有关系），不同部分中的数则不等价（没有关系）。这种通过等价关系给出的每一部分叫做等价类，下面给出等价类和由等价类构成的商集的严格定义。图3.5一个等价关系的关系图定理3.9指出，集合A上的等价关系R所形成的等价类，它们两两互不相交而且覆盖住整个集合A。这种将一个集合划分为若干个不相交的子集的并叫做集合的划分，下面给出集合划分的精确定义。定义3.16设A是一个非空集合，

是它的非空子集，如果它们满足下列条件：图3.6集合的划分定义3.17设R是非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集，记作A/R，即

根据定理3.9，一个商集就是原集合的一个划分，并且不同的商集将对应不同的划分。反之，我们有如下的定理。3.5偏序关系与拓扑排序3.5.1偏序关系图3.7偏序集的哈斯图定义3.19假设

a和b是偏序集

上的两个元素。如果或

我们就说a

和b是可比较的。否则就说

和b是不可比较的，并记作

。若偏序集

的每一对元素都是可比较的，则称

X为全序集，相应的偏序就称为全序。全序集也叫做线性序集或叫做链。

虽然偏序集可能不是全序集，但它的子集仍有可能是全序集。很明显，全序集的每一个子集都是全序集。

偏序集的子集S可以有多于一个的极小元和极大元。如果S是无限集合，那么S可能没有极小元和极大元，例如，偏序集<R，≤>没有极小元和极大元。如果S是有限集合，那么S一定至少有一个极小元和一个极大元。即有下面的定理3.11。

下界、上界、下确界和上确界都可能不存在，即使对有限集合也是这样；下界和上界可以有多个，但下确界和上确界如果存在则唯一。而且如果a是集合S的最小（大）元，则a也是S的下（上）确界；反之，如果a是集合S的下（上）确界且

，则a也是S的最小（大）元。

有些书将下确界叫做最大下界，并记作

，而不是

，将上确界叫做最小上界，并记作

，而不是

。图3.8根据哈斯图求上、下确界3.5.3拓扑排序

拓扑排序与安排任务有关。假设一个项目由20个任务构成。某些任务只能在其他任务结束之后才能进行。怎样能够找到完成这些任务的一个顺序？为了建立这个问题的数学模型，我们首先建立一个任务集合上的偏序

，使得

，当且仅当直到任务a结束后任务b才能开始；然后构造与这个偏序相容的一个全序R，就得到一个与这个偏序相容的完成这20个任务的顺序，从而安排好这个项目。这种从一个偏序构造一个与其相容的全序的过程就叫做拓扑排序。

这个排序所使用的步骤如图3.9所示。图3.9拓扑排序例3.27一个计算机公司的开发项目需要完成7个任务。其中的某些任务只能在其他任务结束后才能开始。建立任务上的偏序如下：如果任务y在x结束后才能开始，则任务xp

任务y。这7个任务关于这个偏序的哈斯图如图3.10所示，求一个全序使得可以按照这个全序执行这些任务以完成这个项目。解

可以通过执行一个拓扑排序得到7个任务的排序。排序的步骤显示如图3.11所示。这个排序的结果是

，给出了执行任务的一种可能次序。图3.10一个项目开发的哈斯图图3.11一个项目开发的工作安排3.6函

数3.6.1基本概念

函数（也叫映射）是数学中重要的概念，是一种具有特殊性质的二元关系。我们这里所讨论的函数不仅仅是定义在数集之上，而是可以定义在任意集合之上，它是初等数学中函数概念的推广。

从定义可以得知，函数是一种特殊的关系，它与一般关系比较具备如下特征：（1）在函数中，序偶的第一个元素一定是互不相同的，但关系中序偶的第一个元素可以相同。（2）函数是二元关系，当然也是集合。一个从X

到Y的函数，它作为集合，其元素个数一定是

；但从X到

Y的二元关系，作为集合，其元素个数确可以是从0到

中的任何一个正整数。（3）

的任何子集都是从X

到

Y的二元关系，因此从X

到

Y的不同二元关系有

个，但从

X到Y的不同函数仅有

个。3.6.2复合函数

我们知道，关系复合后可以得到一个新的关系。函数复合后也得到一个新的函数—复合函数。3.6.3逆函数

我们用复合关系直接定义了复合函数，那么逆函数（反函数）能否通过逆关系来直接定义呢？3.7集合的等势与基数

通俗地讲，集合的基数是量度集合所含元素多少的量。集合的基数越大，所含的元素就越多。为了讲清楚无限集合的基数，我们先讲集合的等势概念。定理3.20有理数集合Q与自然数集合N等势，但实数集合与自然数集合N不等势。证明比较复杂，这里从略。

一般地，我们把与有限集合等势的集合称为有限可数集（有限可列集），把与自然数集合N等势的集合称为无限可数集（无限可列集），把与实数集合R等势的集合称为连续集。有限可数集和无限可数集又通称为可数集（可列集），非可数集合统称为不可数集合（不可列集合）。定义3.27设想把一切集合进行分类，凡彼此等势的归于一类，不等势的归于不同的类，对于每一类集合，我们给予一个标志来度量其元素的多少，称这个标志为这类集合的基数。对有限集，其基数就是集合中元素的个数n；对于与自然数集合等势的集合，其基数用

（读作“阿列夫零”）表示；对于与实数集合等势的集合，其基数用

（读作“阿列夫”）表示。一般，集合A的基数，记为Card(A)或｜A｜。

下面的康托定理说明不存在最大的基数，即有比实数集合R的基数

更大的基数存在。3.8多元关系及其应用3.8.1多元关系

在两个以上集合的元素中常常也会产生某种关系。例如，学生的姓名、专业以及成绩之间的关系，一个航班的航空公司、航班号、出发地、目的地、起飞时间和到达时间之间的关系。

本节研究两个以上集合的元素之间的关系，这种关系叫多元关系，并且可以用这种多元关系表示计算机数据库中的数据。这种表示在我们对数据库中的数据进行查询时非常有用，例如，哪个航班在下午3点到4点之间降落在杭州萧山国际机场？杭电主修软件工程或网络工程的哪些二年级学生平均成绩高于80分？联想公司的哪些雇员为这个公司工作不到5年但月报酬超过20000人民币？

将定义3.4进行推广，可以定义有序n元组和n个集合的笛卡儿积。3.8.2关系数据库

数据库（Database）是按照数据结构来组织、存储和管理数据的仓库。

用户可以通过数据库管理系统所提供的语言使用数据库中存放的数据。这种使用包括下列几个方面。（1）数据的检索：从数据库中取出满足一定条件要求的数据。（2）数据的插入：将一些数据存储到数据库中供以后使用。（3）数据的修改：修改数据库中指定的数据。（4）数据的删除：删除数据库内指定的数据。

数据库使用操作所需要的时间依赖于这些信息的存储方式。插入数据、删除数据、修改数据、检索数据，以及从一些重叠的数据库中组合数据的操作，在一个大型数据库中每天要执行几百万次。由于这些操作的重要性，已经开发了数据库表示的各种方法。这里讨论其中的一种基于关系概念的方法，叫做关系数据模型。

数据库内的数据都按一定格式组织与存放，实体是数据库中数据的基本存放单位，如教师简历、工资单、学生概况、课程概貌、合同执行情况、物资供销情况等均是实体。在关系数据库中，实体按二维表的形式存放。二维表的每一行叫一个记录，它代表一个完整的数据，m行表示实体包含m个记录。n列表示实体有n个属性，属性的取值叫做字段，n个属性表示每个记录都有n个字段，如职工简历这个实体就有姓名、性别、年龄等属性，而一个记录中的字段“男”就是“性别”属性的一个取值。一个包含m行n列的实体，即一张有m行n列的二维表，实际上就是一个包含m个有序n元组的n元关系。例3.36（1）一个学生概况实体S，它有4个属性：学号、姓名、年龄、所属系名，分别用S#、SN、SA及SD表示，这个实体存放10个学生的概况，即有10个记录，它可以用有10行4列的二维表表示，如表3.3所示。（2）一个课程概貌实体C，它有3个属性：课程号、课程名、先修课程号，分别用C#、CN及PC#表示，这个实体存放6门课的概貌，即有6个记录，它可以用有6行3列的二维表表示，如表3.4所示。S#SNSASD

C#CNPC＃01AB20CS

01OS0202AC21MA

02PL0503AD22MA

03DB0604AE21CS

04ML0505AF20CS

05MC0606AG20CS

06DS0407AH22MA

08AI23MA

09AJ21CS

10AK19MA

表3.3实体S

表3.4实体C

在实体中，如果根据某个属性的取值就能检索每个记录，我们就叫这个属性为主键码。这就是说，当实体中没有两个记录在这个属性有相同的值时，这个属性就是主键码。在例3.36中，S#属性就是实体S的主键码，而SD属性则不是主键码。

因为主键码用于唯一地标识实体中的记录，当新的记录被加到这个实体时，主键码要继续保持有效是非常重要的。因此，应该做检测以保证在主键码中每个新记录与二维表中所有其他的记录不同。例如，使用学号作为学生概况实体的主键码是有意义的，因为没有两个学生有同样的学号。一个大学不应该使用姓名属性作为主键码，因为有可能两个学生有同样的姓名。

用户使用关系数据库实际上就是对一些二维表进行检索、插入、修改和删除等操作，也就是对一些多元关系进行这些操作。3.8.3数据库的检索

用户对关系数据库进行检索不外乎选择某个二维表中满足某些条件的一些行和一些列组成一个新的二维表。例如，对表3.3表示的二维表，要求给出年龄大于20岁的学生的学号与姓名就是一种检索操作，它要求在表3.3中选择满足SA>20的那些行，再由这些行中选出属性学号与姓名。

这种检索操作的结果还是一张二维表，这个新的二维表有两个属性以及一些满足SA>20的记录。由此可见，检索是由一张表到另一张表的操作，从数学的观点看，检索是一种一元运算，它根据一个多元关系得出另一个多元关系。

下面我们来定义两种一元检索运算，一种叫投影运算，另一种叫选择运算，然后由这两种运算对关系数据库进行各种各样的检索。例3.37在学生概貌实体S中取出学生姓名是投影运算

sn(S)，在课程概貌实体C中取出课程号和课程名是投影运算

c#,cn(C)。在学生概貌实体S中取出年龄大于20岁的数学系的学生概貌是选择运算

sa>20^sd=ma(S)，在课程概貌实体C中取出先修课程号为05的课程概况是选择运算

pc#=05(C)。运算结果

sn(S)、

c#,cn(C)、

sa>20^sd=ma(S)和

pc#=05(C)如表3.5、表3.6、表3.7和表3.8所示。SN

C#CN

S#SNSASD

C#CNPC#AB

01OS

02AC21MA

02PL05AC

02PL

03AD22MA

04ML05AD

03DB

07AH22MA

AE

04ML

08AI23MA

AF

05MC

AG

06DS

AH

AI

AJ

AK

表3.5

sn(S)

表3.6

c#,cn(C)

表3.7

sa

20

sd=ma(S)

表3.8

pc#=05(C)

联合应用投影运算

和选择运算

就可以在关系数据库检索出所要求的任意行与任意列的内容，例如，本小节前面的给出年龄大于20岁的学生的学号与姓名就是运算

sn

SA>20(S)，取出所有计算机系的学生的名单是运算

sn

sd=cs(S)。

C#CNPC

C#CNPC07PP05

01OS0208RP07

02PL05

03DB06

04ML05

05MC06

06DS04

07PP05

08RP07表3.9增设的课程

表3.10实体C∪C'3.8.4插入、删除与修改

所谓插入操作就是在实体中增加一些记录，换句话说，就是在多元关系中增加一些有序元组，这种操作相当于集合的并运算。而所谓删除操作就是在实体中除去一些记录，换句话说，就是在关系中除去一些有序元组，这种操作相当于集合的差运算。例3.38设某系开设课程之概况由表3.4表示的实体C表示，现增设两门课，其概况如表3.9所示，请将此两门课之概况插入实体C中。解

表3.