《离散数学》课件-第3章

3.1集合的概念与表示

3.2集合的基本运算

*3.3容斥原理

3.4归纳证明

3.5集合的笛卡儿积

3.6二元关系

3.7集合上的二元关系及其特性

3.8关系的闭包运算

3.9等价关系

3.10序关系第3章集合与关系集合是一个原概念，很难严格定义，只能对它给予直观描述。所谓集合，就是若干(有穷或者无穷多)个具有某种共同性质的事物的全体。组成集合的单个事物称为该集合的元素(element)，或称为成员(member)。3.1集合的概念与表示

1.列举法

列举法是将集合中的元素在一对大括号“{}”中一一列举出来。例如，A={a，b，c}表示集合A由a、b、c三个元素组成。又如，D={0，1，2,…，99}表示集合D由前100个自然数组成。当集合中的元素较多且有一定规律时，为了避免书写麻烦,可以先列出集合中的一些元素，用省略号表示其他元素，如果是有限集合还要在最后列举出末尾元素。

需要注意的是，如果没有特别说明，集合中的元素不能重复列举且元素间无次序之分。

2.描述法

描述法使用自然语言或谓词描述集合中元素的共同特征。例如，A={x|x是中国的省份}，B={y|y=a或y=b}。当用谓词描述集合中元素的共同特征时，集合的表示形式为S={x|P(x)}，其中P(x)是一元谓词，对于变元x的论域D中的任一个体a，如果P(a)为真，那么a∈S，否则a∈S。

3.归纳定义法

外延性公理两个集合A、B相等，记为A=B，当且仅当它们有相同的元素。用与其等价的谓词公式可表示为

A=B

x(x∈A

x∈B)

若两个集合A和B不相等，通常记为A≠B。除相等关系外，包含也是集合间常见的一种关系。

定义3.1.1

设A、B是任意的两个集合，若集合A的每个元素都是集合B的元素，则称A为B的子集(subset)或称B包含A，记为A

B或B

A，用逻辑公式表示为

A

B

x(x∈A→x∈B)

如果集合A不是集合B的子集，通常记为A

B。

⊆⊇⊆⊆

定义3.1.2

如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集(propersubset)，记为A

B，用逻辑公式表示为

A

B

x(x∈A→x∈B)∧y(y∈B∧y∈A)(A

B)∧(A≠B)

通常在研究和讨论问题时，所涉及的事物或者对象总限定在一定范围内，为了方便起见，有必要引入两种特殊的集合：全集和空集。⊂

⊂

⊆

定义3.1.3

在一定范围内所有事物组成的集合称为该范围内的全集(universalset)，记为U，用逻辑公式表示为

U={x|P(x)∨

P(x)}

其中，P(x)是任意的谓词。

全集由所讨论的事物范围确定。如在讨论实数时，全体实数组成全集U=R，此时所提到的任一集合A必须是U的子集，而不能是{a，b，c}、{老虎，灯泡}等。又如，在初等数论中，全体整数组成全集U=Z。

定义3.1.4

不含任何元素的集合称为空集(emptyset)，记为，用逻辑公式表示为

={x|P(x)∧

P(x)}

其中，P(x)是任意的谓词。根据空集的定义，显然有||=0。

定理3.1.1

空集是任一集合的子集且是任何非空集合的真子集。

证明任取集合A，由于对任意的元素x，x∈恒为假，则有x(x∈→x∈A)为真，故有A成立。

若A不为空集，则存在元素

a∈A且a∈，故有A。证毕∅∅∅∅⊆∅∅∅∅⊂

定理3.1.2

设A、B、C是集合，若A

B且B

C，则A

C。

证明任取x∈A

，因为A

B，所以x∈B。又因为B

C，所以有x∈C。故有A

C。

证毕

定理3.1.3

集合A和集合B相等的充分必要条件是A和B互为子集。

证明⊆⊆⊆⊆⊆⊆

推论对于任意集合A，均有A

A。

定理3.1.4

空集是唯一的。

证明设有两个空集和′，根据定理3.1.1，有′且′，再根据定理3.1.3，故′=。

证毕

⊆∅∅∅∅⊆∅∅∅文氏图(Venndiagram)是一种可以直观地表示集合之间关系的图形化工具，它是英国数学家约翰·韦恩(JohnVenn)于1881年首先发明的。在文氏图中，用矩形表示全集U，在表示全集的矩形内部用圆、椭圆或其他几何图形表示集合，在表示集合的图形内部用点来表示集合中的元素。例如，图3.1.1表示了全集U的一个子集A和两个元素x和y，其中x画在集合A的椭圆内部，这表示元素x属于集合A，而y画在集合A的椭圆外部，这表示元素y属于U而不属于集合A。图3.1.1文氏图示意又如，图3.1.2所示的文氏图显示了集合A与集合B的四种不同关系。其中，图(a)表示集合A和B相等，图(b)表示集合B是A的真子集，图(c)表示集合A和B不等且交集不为空集，图(d)表示A和B的交集为空集。图3.1.2

定义3.1.5

给定集合A，以A的所有子集为元素组成的集合称为集合A的幂集(powerset)，记为ρ(A)。

1.集合的交

定义3.2.1

对于任意两个集合A和B，由所有属于集合A且属于集合B的元素组成的集合称为A和B的交集(intersection)，记为A∩B。

A∩B={x|x∈A∧x∈B}

集合交运算的文氏图表示如图3.2.1所示。3.2集合的基本运算图3.2.1

2.集合的并

定义3.2.2

对于任意两个集合A和B，由所有属于集合A或属于集合B的元素组成的集合称为A和B的并集(union)，记为A∪B。

A∪B={x|x∈A∨x∈B}

集合并运算的文氏图表示如图3.2.2所示。图3.2.2

3.集合的补

定义3.2.3

对于任意两个集合A和B，由所有属于集合A而不属于集合B的元素组成的集合称为集合B在A中的相对补集(complementofBwithrespecttoA)，记为A－B。

A－B={x|x∈A∧x∈B}

A－B也称为集合A与B的差。集合差运算的文氏图表示如图3.2.3所示。图3.2.3

定义3.2.4

如果U是包含集合A的全集，则属于U而不属于A的元素组成的集合称为集合A的补(complementofA)，记为。

=U－A={x|x∈U∧x∈A}

集合A的补集是集合A相对于全集U的补，也称A的绝对补。集合绝对补运算的文氏图表示如图3.2.4所示。图3.2.4

4.集合的对称差

定义3.2.5

对于任意两个集合A和B，由属于集合A而不属于集合B以及属于集合B而不属于集合A的所有元素组成的集合称为集合A与B的对称差(symmetricdifference)，记为A

B。

A

B=(A－B)∪(B－A)={x|(x∈A∧x∈B)∨(x∈B∧x∈A)}

集合对称差运算的文氏图表示如图3.2.5所示。图3.2.5

5.集合的环积

定义3.2.6

对于任意两个集合A和B，由属于集合A且属于集合B，以及既不属于集合A又不属于集合B的所有元素组成的集合，称为集合A与B的环积，记为AB。

A

B=

=

={x|(x∈A∧x∈B)∨(x∈A∧x∈B)}

集合的环积运算的文氏图表示如图3.2.6所示。图3.2.6以上定义的集合运算满足若干性质，表3.2.1给出了其中11条基本性质。表3.2.1

定理3.2.1

设A和B是全集U的任意子集，若AB，则

(a)

;

(b)B－A=B∩

;

(c)(B－A)∪A=B。

证明

因为A

B，就有(B∪A)=B，所以(B－A)∪A=B。⊆

⊆

⊆

集合的运算可用于解决有限集合的计数问题。根据集合运算的定义，显然有以下各式成立。

(a)|A1∪A2|≤|A1|+|A2|。

(b)|A1∩A2|≤min(|A1|，|A2|)。

(c)|A1－A2|≥|A1|－|A2|。

(d)|A1

A2|=|A1|+|A2|－2|A1∩A2|。*3.3容斥原理

加法原理：如果A1，A2，…，An是n个两两互不相交的集合，那么这n个集合的并集的元素个数为这n个集合中的元素个数之和。

|A1∪A2∪…∪An|=|A1|+|A2|+…+|An|

定理3.3.1

设A1和A2是有限集合，其元素个数分别为|A1|和|A2|，则|A1∪A2|=|A1|+|A2|－|A1∩A2|。

证明(1)若A1∩A2=，即|A1∩A2|=0，则根据加法原理有

|A1∪A2|=|A1|+|A2|

这时显然公式成立。∅

(2)若A1∩A2≠，根据

(A1－A2)∪(A1∩A2)=A1

且

(A1－A2)∩(A1∩A2)=

可得

|A1|=|A1－A2|+|A1∩A2|

同理有

|A2|=|A2－A1|+|A1∩A2|∅∅而A1∪A2可以表示A1－A2、A2－A1和A1∩A2这三个两两互不相交的集合的并集，所以有

|A1∪A2|=|A1－A2|+|A2－A1|+|A1∩A2|

=|A1|+|A2|－|A1∩A2|

证毕

定理3.3.1

也可以通过图3.3.1验证。图3.3.1例2以1开始或者以00结束的8位不同的二进制符号串有多少个？

以上计算公式可以用图3.3.2验证。图3.3.2

定理3.3.2(容斥原理)设A1，A2，…，An是有限集合，那么有

|A1∪A2∪…∪An|=

|Ai|－|Ai∩Aj|

+

|Ai∩Aj∩Ak|－…+(－1)n+1|A1∩A2∩…∩An|

证明用数学归纳法。

(1)当n=2时，结论成立，即

|A1∪A2|=|A1|+|A2|－|A1∩A2|

(2)假设当n=k－1(k≥3)时结论成立。

(3)现证明当n=k时结论也成立。

证毕3.4.1集合的归纳定义

有些集合很难用3.1节中所介绍的列举法和描述法进行定义，如命题合式公式集合、C语言程序集合等。为此，这里再介绍另一种

定义集合的方法——归纳定义(inductivedefinition)。

一个集合S的归纳定义由三部分组成：

(1)基础条款：指出某些事物属于S，其功能是给集合S指定初始元素，使得定义的集合S非空。3.4归纳证明

(2)归纳条款：指出由集合S中的已有元素构造新元素的方法。归纳条款的形式总是断言：如果事物x，y，…是集合S中的元素，那么用某些方法组合它们所得的新元素也在集合S中。它的功能是给出从已知元素构造其他元素的规则。

(3)极小性条款：断言一个事物除非能有限次应用基础条款和归纳条款构成，否则它不在集合S中。

集合归纳定义的极小性条款还有其他一些常见的形式，例如，“集合S是满足基础条款和归纳条款的最小集合”，“若T是S的子集，T又满足基础条款和归纳条款，那么T=S”。这些极小性条款虽然形式不同，但都指明了所定义的集合是满足基础条款和归纳条款的最小集合，即所谓的极小性。3.4.2自然数集合

自然数集合N被广泛运用，但是要给出一个严格的定义是比较困难的。这里介绍美国数学家约翰·冯·诺依曼(JohnVonNeumann)的定义方法，他巧妙地采用空集和后继集合的概念找到了自然数集合的一个构造。

设A是任意集合，A的后继集合记为A′，定义A′=

A∪{A}。自然数集合N可进行以下归纳定义：

(1)(基础)∈N；∅

(2)(归纳)如果A∈N，那么A′∈N；

(3)(极小性)如果S

N且满足条款(1)和(2)，那么S=N。自然数集合可以直观地表示为以为起点，另一端无限延伸的一条链，其结构如图3.4.1所示。习惯上，将自然数集合的最小元素用0标记，0的后继集合{}用1标记，1的后继集合{，{}}用2标记，以此类推，从而产生了人们所熟悉的自然数集合N={0,1,2,3，…}。进一步，可以在N上定义各种运算。例如，对于加法运算，任取n∈N，n+1=n′。

⊆∅∅∅∅∅图3.4.13.4.3归纳法

对于形如(x)P(x)的命题，如果其论域是归纳定义的集合，则用归纳法往往是较为有效的证明方法。

归纳法证明的一般步骤如下：

(1)基础步骤。对于基础条款中指定的每个初始元素t，证明命题P(t)为真。

(2)归纳步骤。证明如果事物x，y，…有P性质，那么用归纳条款指定的方法组合它们所得的新元素也具有P性质。3.4.4数学归纳法

数学归纳法(mathematicalinduction)被广泛地用来证明形如xP(x)的命题，其中x的论域常常是自然数集、正整数集等，例如，用来证明算法的复杂度，计算机程序的正确性，关于图和树等离散结构满足的等式或不等式。数学归纳法的有效性源于自然数集的归纳定义。

下面分别介绍数学归纳法第一原理和数学归纳法第二原理。

数学归纳法第一原理其实是自然数集合N上的一个推理规则，其形式如下：

为了证明n(P(n)→P(n+1))，根据谓词逻辑中的全称推广规则，只需任取n证明P(n)→P(n+1)成立即可，当然n必须是任意选取的。

用数学归纳法第一原理进行证明的一般步骤如下：

(1)(归纳基础)证明P(0)为真(可以用任何方法)。

(2)(归纳假设)任取n(n≥0)，假设P(n)为真。

(3)(归纳推理)由P(n)为真，推出P(n+1)也为真。当用数学归纳法第一原理进行证明时，首先证明P(0)为真，这时可以用任何有效的证明方法和规则；其次证明“若P(n)为真，则P(n+1)必为真”。这样因为有P(0)为真且有P(n)→P(n+1)为真，所以P(1)为真，由P(1)为真可得P(2)也为真，以此类推，即对任意的自然数k都有P(k)为真。

作为一个形象的例子，我们来考虑由一张牌开始，无穷向后延长的一列多米诺骨牌，每两张牌都等距直立放置。假设我们能够证明若任意的第k张牌被撞倒，则它将会撞倒第k+1张牌。现在我们撞倒第一张牌，第一张牌倒后第二张牌跟着被撞倒，第二张牌被撞倒后第三张牌也跟着被撞倒……如此下去，所有的牌都会被撞倒，如图3.4.2所示。图3.4.2数学归纳法第一原理的推理规则可以有各种变形。例如，如果我们希望证明对某整数k，谓词P对所有x≥k成立，这时，基础步骤必须换为证明P(k)，推理规则变为

例L形马赛克瓷砖由三块方砖构成，其形状如图3.4.3(a)所示。证明：可以用L形马赛克铺满去掉一个格子的任何具有2n×2n(n∈Z+)个格子的方形地板。图3.4.3

证明设P(n)是命题：可以用L形的马赛克瓷砖铺满去掉一个格子的任何具有2n×2n个格子的方形地板。

(1)(归纳基础)当n=1时，P(1)为真。因为如图3.4.3(b)所示，从2×2的地板中去掉这4个格子中的任意一个，都可以用一块L形的马赛克瓷砖将它铺满。

(2)(归纳假设)任取k∈Z+，假设P(k)为真，即可以用L形马赛克铺满去掉一个格子的任何具有2k×2k个格子的方形地板。

(3)(归纳推理)当n=k+1时，要考虑去掉一个格子的2k+1×2k+1规格的地板。

因为2k+1×2k+1=2×2k×2×2k=4×(2k×2k)，也就是说可以将2k+1×2k+1规格的地板分割成4块2k×2k规格的地板。如图3.4.4(a)所示，将该地板分成4块大小相同的2k×2k规格的地板，按顺时针方向依次编号为1＃、2＃、3＃、4＃。

由于这块2k+1×2k+1规格的地板中去掉了一个格子，不妨设去掉的这个格子在1＃中。根据归纳假设，1＃去掉1个格子后可以用L形马赛克铺满。还剩下2＃、3＃、4＃这三块2k×2k规格的地板。为了将其铺满，在这三块地板毗邻处暂时在每一块中去掉1个格子(如图3.4.4(b)所示)，根据归纳假设，可以用L形马赛克铺满2＃、3＃、4＃各去掉1个格子的地板，而去掉的这3个格子正好与一块L形马赛克瓷砖吻合，最后用一块L形马赛克将暂时去掉的3个格子铺满，故P(k+1)也为真。图3.4.4

例7

设m是正整数，现有m颗白珍珠和m颗黑珍珠，将这2m颗珍珠随意穿在一个圆环上，证明可以在圆环上找到一个位置，从这个位置出发顺时针方向依次收集圆环上的所有珍珠，使得在每一时刻收集到的白珍珠的数目总是大于等于黑珍珠的数目。

证明(1)当m=1时，圆环上有1颗白珍珠和1颗黑珍珠，如果我们从那颗白珍珠所在的位置开始收集，显然有收集到的白珍珠的数目总是大于等于黑珍珠的数目。

(2)假设当m=k(k>0)时，命题成立。

(3)当m=k+1时，圆环上有k+1颗白珍珠和k+1颗黑珍珠。我们可以证明在这2(k+1)颗珍珠中，必有1颗白珍珠和1颗黑珍珠按顺时针方向邻接。

令t为圆环上的任一颗白珍珠，如果t顺时针方向邻接的1颗珍珠t′是黑珍珠，那么就找到了这样一对珍珠(t，t′)；否则，t顺时针方向邻接的是1颗白珍珠。现令t=t′，重复上述过程，因为圆环上存在黑珍珠，所以必然能够找到这样一对珍珠(t，t′)，如图3.4.5所示。图3.4.5数学归纳法第二原理的形式如下：

定义3.5.1

两个元素a和b组成的具有固定次序的序列称为序偶(orderedpair)或二元组(ordered2-tuples)，记为〈a，b〉。对于序偶〈a，b〉，a称为第1元素，b称为第2元素。

有了序偶的概念，就可以将一趟列车的运行区间用一个序偶的形式表示，例如，K126=〈西安，长春〉。同样，平面上横坐标为x、纵坐标为y的点可以表示为〈x,y〉。3.5集合的笛卡儿积

定义3.5.2

两个序偶〈a，b〉和〈c，d〉相等，记为〈a，b〉=〈c，d〉，当且仅当a=c且b=d。

定义3.5.3

设A和B是两个集合，称集合

A×B={〈a,b〉|a∈A，b∈B}

为A和B的笛卡儿积(Cartesianproduct)或叉集(productset)。例如，R×R示实平面。任取〈x，y〉∈R×R，〈x，y〉表示实平面中的一个点。

定义3.5.4

设A1，A2,…，An是n个集合，称集合

A1×A2×…×An={〈a1，a2，…，an〉|ai∈Ai，1≤i≤n}为集合A1，A2,…，An的笛卡儿积。其中，〈a1，a2，…，an〉是由n个元素a1，a2,…，an组成的n元组(orderedn-tuples)，ai(1≤i≤n)是该n元组的第i个元素且ai∈Ai。若对一切i，Ai=A，则可简记为An。

n元组可以看成是一个二元组，规定〈a1，a2，…，an〉=〈〈a1，a2，…，an－1〉，an〉，其第一元素是n－1元组。例如，〈x，y，z〉代表〈〈x，y〉,z〉，而不代表〈x，〈y，z〉〉。

定理3.5.1

设A、B、C是任意集合，则有

(1)A×(B∪C)=(A×B)∪(A×C)。

(2)A×(B∩C)=(A×B)∩(A×C)。

(3)(A∪B)×C=(A×C)∪(B×C)。

(4)(A∩B)×C=(A×C)∩(B×C)。

证明

(1)①任取〈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)，所以A×(B∪C)(A×B)∪

(A×C)。⊆②任取〈x,y〉∈(A×B)∪(A×C)，则有〈x,y〉∈A×B或〈x,y〉∈A×C，即x∈A且y∈B或x∈A且y∈C，得到x∈A且(y∈B或y∈C)，从而由x∈A且y∈B∪C可得〈x,y〉∈A×

(B∪C)。

所以(A×B)∪(A×C)A×(B∪C)。

由以上①和②得知，A×(B∪C)=(A×B)∪(A×C)。

(3)〈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.5.2

如果Ai(i=1，2，…，n)都是有限集合，那么

|A1×A2×…×An|=|A1|·|A2|·…·|An|

证明(略)

以上定理就是3.3节曾经提到的关于集合计数的乘法原理。乘法原理还可以描述为：如果一项工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，以此类推，第t步有nt种不同的选择，则完成这项工作不同的选择共有n1×n2×…×nt种。3.6.1关系的定义

定义3.6.1

两个集合A和B的笛卡儿积A×B的任一子集R，称为集合A到B上的二元关系(arelationfromAtoB)。二元关系R是由序偶构成的集合，若〈x，y〉∈R，则称x与y有R关系，也记为xRy；否则，〈x，y〉∈R，称x与y没有R关系，也记为xRy。

3.6二元关系设R是集合A到B的二元关系。集合A称为R的前域(predomain)，集合B称为R的陪域(codomain)。集合{x|(

y)(〈x，y〉∈R)}称为R的定义域(domain)，记为domR。集合{y|(x)(〈x，y〉∈R)}称为R的值域(range)，记为ranR。显然，domR

A和ranR

B。

集合A到B的二元关系R的示意图如图3.6.1所示。⊆⊆图3.6.1

定义3.6.2

n个集合A1，A2，…，An的笛卡儿积A1×A2

×…×An的任一子集R称为A1，A2，…，An上的一个n元关系(relation)。

定义3.6.3

设R是A1×A2×…×An的子集，若R=，则称R为A1，A2，…，An上的空关系，若R=A1×A2×…×An，则称R为A1，A2，…，An上的全域关系。∅3.6.2关系的表示

二元关系是一种集合，除了可以采用集合的表示方法外，下面再介绍另外两种常用表示方法：关系矩阵(relationmetrix)和关系图(relationgraph)。

1.关系矩阵

给定两个有限集A={a1，a2，…，am}，B={b1，b2，…,

bn}。R为A到B上的一个二元关系，则可以用以下0－1矩阵MR=［rij］m×n来表示R：

其中:

2.关系图

设有限集合A={a1，a2，…，am}和B={b1，b2，…,

bn}，R为A到B上的一个二元关系。R的关系图的作法是：首先在平面上作m个结点分别代表a1，a2，…，am，然后另作n个结点分别代表b1，b2，…,bn。如果aiRbj，则画一条从结点ai到结点bj的有向弧，如图3.6.2所示。图3.6.2

例3

设X={x1，x2，x3，x4}，Y={y1，y2，y3}，R={〈x1，y1〉，〈x1，y3〉，〈x2，y2〉，〈x3，y1〉，〈x4，y2〉，〈x4，y3〉}。写出R的关系矩阵并画出其关系图。

解

R的关系矩阵和关系图如图3.6.3所示。图3.6.3

例4

设A={1，2，4，7，8}，B={2，3，5，7}，定义A到B的二元关系R={〈a，b〉|5能整除a+b}。分别用列举法、关系图和关系矩阵描述R。

解

R={〈2，3〉，〈7，3〉，〈8，2〉，〈8，7〉}。R的关系矩阵和关系图分别如图3.6.4所示。图3.6.43.6.3关系的运算

由于二元关系是以序偶为元素组成的集合，因此，所有的集合运算对于二元关系同样适用。设R和S都是集合A到B的二元关系，则有:

(1)R∪S={〈x，y〉|(xRy)∨(xSy)}。

(2)R∩S={〈x，y〉|(xRy)∧(xSy)}。

(3)R－S={〈x，y〉|(xRy)∧(xSy)}。

(4)={〈x，y〉|xRy}=A×B－R。

(5)R

S=(R－S)∪(S－R)。

定义3.6.4

设R为集合A到B的二元关系，S为集合B到C的二元关系，令

R

S={〈a，c〉|a∈A∧c∈C∧(b)

(b∈B∧〈a，b〉∈R∧〈b，c〉∈S)}

则称R

S为R与S的复合关系。

显然，R

S是一个从A到C的二元关系。图3.6.5描述了两个关系R和S进行复合运算的过程。R

S由这样的序偶〈a，c〉构成，即存在集合B中的元素b，有aRb和bRc，形象地说，就是“存在从元素a出发，经过B中某元素b到达c的有向路径”。∘

∘

∘

∘

图3.6.5

定理3.6.1

设R是从集合A到B的二元关系，S为B到C的二元关系，T为C到D的二元关系，则有

(R

S)T=R(S

T)

证明任取〈a,d〉∈(R

S)T，由复合运算的定义可知，存在c∈C使得

〈a，c〉∈R

S

且〈c，d〉∈T

又对于〈a，c〉∈R

S，存在b∈B使得

〈a，b〉∈R

且〈b，c〉∈S

由〈b，c〉∈S和〈c，d〉∈T可得〈b，d〉∈S

T，又由〈a，b〉∈R可得

〈a，d〉∈R(S

T)∘

∘

∘

∘

∘

∘

∘

∘

∘

∘

故有

(RS)TR(ST)

同理可证：

R(ST)(RS)T

综上所述，可得

(RS)T=R(ST)

证毕⊆∘

∘

∘

∘

∘

∘

∘

∘

⊆∘

∘

∘

∘

定义3.6.5

设R为集合A到B的二元关系，令R－1={〈b，a〉|〈a，b〉∈R}，则称R－1为R的逆关系。显然，R－1是集合B到A上的二元关系。

例10

设A={a，b，c，d}，B={1，2，3}，R={〈a，2〉，〈b，1〉，〈c，3〉，〈d，1〉}是从A到B的一个二元关系，求R、R－1的关系矩阵、关系图，并观察关系矩阵、关系图，分析R－1与R之间的联系。

解

R－1={〈2，a〉，〈1，b〉，〈3，c〉，〈1，d〉}，给出R与R－1的关系矩阵，再给出R与R－1的关系图，如图3.6.6所示。图3.6.6

定理3.6.2

设R、R1、R2均为从A到B的二元关系，则有

证明(2)任取a∈A，b∈B，则有

(4)任取a∈A，b∈B，则有

证毕

定理3.6.3

设R为A到B的二元关系，S是从B到C的二元关系，那么

(R

S)－1=S－1

R－1

证明(1)任取〈c,a〉∈(R

S)－1，则有〈a,c〉∈(R

S)，由关系复合运算的定义可知，存在b∈B，使得〈a，b〉∈R且〈b，c〉∈S，则有〈b，a〉∈R－1，〈c，b〉∈S－1。由〈c，b〉∈S－1和〈b，a〉∈R－1可得〈c，a〉∈S－1

R－1，故有(R

S)－1

S－1

R－1。⊆∘

∘

∘

∘

∘

∘

∘

(2)任取〈c，a〉∈S－1

R－1，由关系复合运算的定义可知，存在b∈B，使得〈c，b〉∈S－1且〈b，a〉∈R－1，即〈b，c〉∈S且〈a，b〉∈R，由此可得〈a，c〉∈R

S，即〈c,a〉∈(R

S)－1。

故有S－1

R－1(R

S)－1。

由(1)、(2)得到，(R

S)－1=S－1

R－1。⊆∘

∘

∘

∘

∘

∘

∘

3.7.1集合上的二元关系

定义3.7.1

集合A与A的笛卡儿积A×A的子集称为A上的二元关系。

例如，国家男子乒乓球队由7名选手组成，主教练要从现役国手中挑选三对男子双打选手参加世界乒乓球锦标赛。设集合A为国家乒乓球男队，共由7名运动员组成，令A={甲，乙，丙，丁，戊，己，庚}，A×A则包含了所有可能的男子双打配对组合，如图3.7.1所示。3.7集合上的二元关系及其特性图3.7.1主教练根据挑选男双队员的一些规则和经验，最终选择了甲与丙、己与戊、乙与丁这3对组合去参加世界乒乓球锦标赛。这样，R={〈甲，丙〉，〈己，戊〉，〈乙，丁〉}就构成A上的一个“双打配对”关系。

由于集合A上的二元关系的前域和陪域是同一个集合，因此其关系矩阵是方阵，其关系图可以将两组结点合并为一组。

定义3.7.2

设A是任一集合，称A上的二元关系{〈a，a〉|a∈A}为集合A上的相等关系，记为IA。

例1

设A={1，2，3，4，5}，A上的二元关系R={〈1，5〉，〈1，4〉,〈2，3〉，〈3，1〉，〈3，4〉，

〈4，4〉}。

(a)求A上的相等关系IA。

(b)写出R的关系矩阵。

(c)画出R的关系图。

解(a)IA={〈1，1〉，〈2，2〉，〈3，3〉，〈4，4〉，〈5，5〉}。

(b)

(c)R的关系图如图3.7.2所示。图3.7.2

定义3.7.3

设R是集合A上的二元关系，n∈Z+，称

为R的n次幂，记为Rn。

设R是集合A上的二元关系，约定R0={〈x，x〉|x∈A}

=IA。

定理3.7.1

设R是集合A上的二元关系，m，n∈N，那么有

(1)Rm

Rn=Rm+n。

(2)(Rm)n=Rmn。∘

∘

定理3.7.2

设R是集合A上的一个二元关系。若存在i，j∈N，i＜j且使Ri=Rj，则有

(1)对所有的k≥0，Ri+k=Rj+k。

(2)对所有的k，m≥0，Ri+md+k=Ri+k，其中d=j－i。

(3)记S={R0，R1，R2，…，Rj－1}，对于任意n∈N，均有Rn∈S。

证明(1)、(2)留作练习。

(3)任取n∈N，如果n＜j，那么根据S的定义，Rn∈S。假设n≥j，那么我们能将n表示为i+md+k，这里0≤k＜d。由(2)可知，Rn=Ri+md+k=Ri+k，因为i+k＜j，故Rn∈S。

证毕3.7.2二元关系的特性

1.自反性

定义3.7.4

设R是集合A上的二元关系，如果对于A中的每一元素a都有aRa，则称R在A上是自反的(reflexive)。

R是自反的(a)(a∈A→aRa)

例如，实数集上的“≤”关系是自反的，因为对于任意实数x，均有x≤x。

2.反自反性

定义3.7.5

设R是集合A上的二元关系，如果对于A中的每一元素a都有aRa，则称R在A上是反自反的(irreflexive)。R是反自反的(a)(a∈A→aRa)

例如，实数集上的“＞”关系是反自反的。

例3

设A={a,b,c,d}，A上的二元关系R1、R2和R3的关系图分别如图3.7.3(a)、(b)、(c)所示。这些关系中哪些是自反的？哪些是反自反的？图3.7.3

解

R1是自反的，R2是反自反的，R3既不是自反的也不是反自反的。

关于自反性与反自反性的特征总结如表3.7.1所示。表3.7.1

3.对称性

定义3.7.6

设R是集合A上的二元关系，如果对于任意a，b∈A，每当aRb必有bRa，则称R在A上是对称的(symmetric)。

R是对称的(a)(b)(a∈A∧b∈A∧aRb→bRa)

例如，三角形集合上的三角形相似关系是对称的。

4.反对称性

定义3.7.7

设R是集合A上的二元关系，如果对于任意a，b∈A，每当aRb且bRa，必有a=b，则称R在A上是反对称的(antisymmetric)。

R是反对称的(a)(b)(a∈A∧b∈A∧aRb∧bRa→a=b)(a)(b)(a∈A∧b∈A∧a≠b∧aRb→bRa)

例如，集合的关系是反对称的。⊆

例4

设A={a，b，c，d}，A上的二元关系R1、R2、R3和R4的关系图分别如图3.7.4(a)、(b)、(c)、(d)所示。这些关系中哪些是对称的?哪些是反对称的？

解

R1是对称的，R2是反对称的，R3既是对称的又是反对称的，R4既不是对称的又不是反对称的。

关于对称性与反对称性的特征总结如表3.7.2所示。图3.7.4表3.7.2

5.传递性

定义3.7.8

设R是集合A上的二元关系，若对于任意a,b,c∈A，当aRb且bRc时必有aRc，则称关系R在A上是传递的(transitive)。

R是传递的(a)(b)(c)(a∈A∧b∈A∧c

∈A∧aRb∧bRc→aRc)

例如，整数集上的关系≤、＜、＞、=都是传递的。

例5

设A={a,b,c,d}，A上的二元关系R1和R2的关系图分别如图3.7.5(a)、(b)所示，请问R是传递的吗？

解

R1是传递的，R2不是传递的。

表3.7.3给出了满足传递性的二元关系的定义和特征。图3.7.5表3.7.3

例7

设A={a，b，c}，构造A上的一个二元关系R，使其不满足自反性、反自反性、对称性、反对称性和传递性。

解令R={〈a，a〉，〈b，b〉，〈b，c〉，〈c，b〉，〈c，a〉}，R的关系图如图3.7.6所示。图3.7.6

定义3.8.1

设R是集合A上的二元关系，如果A上另外一个二元关系R′满足：

(1)R′是自反的(对称的、传递的)；

(2)R′R；

(3)对于A上的任何自反的(对称的、传递的)关系R″，若R″R，有R″R′，则称R′是R的自反(对称、传递)闭包。

3.8关系的闭包运算⊇⊇⊇

定理3.8.1

设R是集合A上的二元关系，则有

(1)R是自反的当且仅当r(R)=R。

(2)R是对称的当且仅当s(R)=R。

(3)R是传递的当且仅当t(R)=R。

证明(2)必要性。若R是对称的，令R′=R，显然，R′满足定义3.8.1中关于对称闭包的约束条件(1)、(2)、(3)，所以，s(R)=R′=R。

充分性。若s(R)=R，因为s(R)是对称的，所以R也是对称的。

同理可证(1)和(3)。

证毕

定理3.8.2

设R是集合A上的二元关系，那么有

(1)r(R)=R∪IA。

(2)s(R)=R∪R－1。

(3)t(R)=。

证明(1)令R′=R∪IA。

①任取x∈A，〈x，x〉∈IA，则〈x，x〉∈R∪IA，故R′是自反的。

②显然R′R。⊇③任取A上的自反关系R″，且R″R，现证明R″R′。

任取〈x，y〉∈R′，则有〈x，y〉∈R或〈x，y〉∈IA。

若〈x，y〉∈R，则有〈x，y〉∈R″。

若〈x，y〉∈IA，则x=y，又因为R″是自反的，所以〈x，y〉∈R″。

故有R″R′。

由此可知，r(R)=R′=R∪IA。⊇⊇

(2)令R′=R∪R－1。

①R′－1=(R∪R－1)－1=R－1∪R=R′，所以R′是对称的。

②显然R′R。

③任取A上的对称关系R″，且R″R，现证明R″R′。

任取〈x，y〉∈R′，由R′=R∪R－1知，得到〈x，y〉∈R或〈x，y〉∈R－1。

若〈x，y〉∈R，则〈x，y〉∈R″。

若〈x，y〉∈R－1，则〈y,

x〉∈R，〈y,

x〉∈R″，因为R″是对称的，所以〈x，y〉∈R″。故有R″R′。

由此可知，s(R)=R′=R∪R－1。⊇⊇⊇⊇

(3)令R′=。

①任取〈x，y〉∈R′，〈y，z〉∈R′，那么必存在正整数s、t，使得〈x，y〉∈Rs，〈y，z〉∈Rt，则有〈x，z〉∈Rs

Rt=Rs+t，所以〈x，z〉∈R′，即R′是传递的。

②R

=R′。∘

⊆③任取A上的传递关系R″，且R″R，现证明R″R′。

任取〈x，y〉∈R′，则存在某正整数k使得〈x，y〉∈Rk，而

，由复合运算的定义可知：A中存在元素x1，x2，…，xk－1，使得〈x，x1〉∈R，〈x1，x2〉∈R，…，〈xk－1，y〉∈R。因为R″R，所以有〈x，x1〉∈R″，〈x1，x2〉∈R″，…，〈xk－1，y〉∈R″。

又因为R″是传递的，所以〈x，y〉∈R″，从而有R″R′。

综上所述有t(R)=R′=。

证毕⊇⊇⊇⊇

例2

设A={a，b，c}，A上的二元关系R={〈a，b〉，〈b，c〉，〈c，a〉}，求r(R)、s(R)和t(R)，并给出各闭包的关系矩阵和关系图。

解

R的关系图如图3.8.1所示。图3.8.1

(a)求自反闭包r(R)。

r(R)=R∪IA={〈a，b〉，〈b，c〉，〈c，a〉，〈a，a〉，〈b，b〉，〈c，c〉}

r(R)的关系图如图3.8.2所示。图3.8.2

(b)求对称闭包s(R)。

s(R)=R∪R－1={〈a，b〉，〈b，c〉，〈c，a〉，〈b，a〉，〈c，b〉，〈a，c〉}

s(R)的关系图如图3.8.3所示。图3.8.3

(c)求传递闭包t(R)。

R={〈a，b〉，〈b，c〉，〈c，a〉}

R2={〈a，c〉，〈b，a〉，〈c，b〉}

R3={〈a，a〉，〈b，b〉，〈c，c〉}=IA=R0

因此有

R4=R，R5=R2，…，R3n+1=R，R3n+2=R2，R3n+3=R3

t(R)=R∪R2∪R3∪…=R∪R2∪R3

={〈a，b〉，〈b，c〉，〈c，a〉，〈a，c〉，〈b，a〉，〈c，b〉，〈a，a〉，〈b，b〉，〈c，c〉}

t(R)的关系图如图3.8.4所示。图3.8.4

定理3.8.3

设R是有限集合A上的二元关系且|A|=n，那么有

t(R)=R∪R2∪…∪Rn

证明已知t(R)=R∪R2∪…∪Rn∪…，现证明R∪R2∪…∪Rn=R∪R2∪…∪Rn∪…。

(1)显然有R∪R2∪…∪Rn

R∪R2∪…∪Rn∪…。

(2)证明R∪R2∪…∪Rn∪…R∪R2∪…∪Rn，为此，需要证明对于任何x，y∈A，如果〈x，y〉∈R∪R2∪…∪Rn

∪…，必存在正整数k≤n，使得〈x，y〉∈Rk。采用反证法：⊆⊆假设k是满足〈x，y〉∈Rk的最小正整数(因为〈x，y〉∈R∪R2∪…∪Rn∪…，必存在正整数s，使得〈x，y〉∈Rs)，且k＞n，则A中存在元素序列x=a0，a1，…，ak－1,ak=y，使得

〈x，a1〉,〈a1，a2〉，…，〈ak－1，y〉∈R

由于|A|=n，则a0，a1，…，ak－1,ak中必有相同者，不妨设ai=aj(0≤i＜j≤k)，于是〈x，a1〉,〈a1，a2〉，…，〈ai－1，ai〉，〈aj，aj+1〉，…，〈ak－1，y〉∈R，得到〈x，ai〉∈Ri，〈aj，y〉∈Rk－j，〈x，y〉∈Ri+(k－j)

，即〈x，y〉∈Rt，其中t=i+(k－j)=k－(j－i)＜k。这与k的最小性矛盾，于是k≤n。故有R∪R2∪…∪Rn∪…R∪R2∪…∪Rn成立。

定理3.8.4

设R是集合A上的二元关系，则有

(1)如果R是自反的，那么s(R)和t(R)也是自反的。

(2)如果R是对称的，那么r(R)和t(R)也是对称的。

(3)如果R是传递的，那么r(R)也是传递的。

证明过程留作练习。

集合A上的二元关系R的闭包运算可以进行复合运算，例如ts(R)=t(s(R))表示R的对称闭包的传递闭包，通常简称为R的对称传递闭包，而tsr(R)则表示R的自反对称传递闭包。R的传递闭包有时用R+表示，而R的自反传递闭包tr(R)用R*表示。

定理3.8.5

设R是集合A上的二元关系，则有

(1)sr(R)=rs(R)。

(2)tr(R)=rt(R)。

(3)ts(R)st(R)。

证明(1)已知(R∪IA)－1=R－1∪IA－1，IA－1=IA，因此

sr(R)=s(R∪IA)=(R∪IA)∪(R∪IA)－1=R∪IA∪R－1∪IA

=(R∪R－1)∪IA=s(R)∪IA=rs(R)⊇

(2)对于任意n∈N，有InA=IA且，因此

tr(R)=t(R∪IA)=

(R∪IA)i=

=t(R)∪IA

=rt(R)

(3)不难证明，如果R1

R2，那么s(R1)s(R2)且t(R1)t(R2)，因为s(R)R，所以有ts(R)t(R)，于是有sts(R)st(R)。

根据定理3.8.3(2)可知ts(R)是对称的，所以有sts(R)=ts(R)。

故有ts(R)st(R)成立。

证毕⊇⊇⊇⊇⊇⊇3.9.1集合的划分

在集合的研究中，除了集合的运算、集合之间的比较之外，有时要把一个集合分成若干子集加以讨论。3.9等价关系

定义3.9.1

给定非空集合A和集合簇π={A1，A2，…，Am}，如果

(1)Ai

A且Ai≠

(1≤i≤m);

(2)A=

;

(3)Ai∩Aj=

(1≤i，j≤m且i≠j)，

那么称π是A的一个划分(partition)。若π满足条件(1)、(2)，则称π是集合A的一个覆盖(cover)。

通俗地说，如果一组两两不相交的非空集合的并集等于A，那么以这组集合为元素的集合称为A的划分。

如果一组非空集合的并集等于A，那么以这组集合为元素的集合称为A的覆盖。⊆∅∅

定义3.9.2

一个集合A的划分π中的元素Ai称为该划分的块(block)。

定义3.9.3

设π为非空集合A的一个划分，若π为有限集合，则称划分的块数|π|为划分的秩。若π为无限集合，称π的秩是无限的。

对于有限集合A，秩为1的划分称为A的最小划分，秩为|A|的划分称为A的最大划分。3.9.2等价关系和等价类

定义3.9.4

设R是集合A上的一个二元关系，若R是自反、对称和传递的，则称R为等价关系(equivalencerelation)。

例3

A={a，b，c，d}，A上的二元关系R={〈a，a〉，〈a，b〉，〈b，a〉，〈b，b〉，〈c，c〉，〈c，d〉，〈d，c〉，〈d，d〉}，验证关系R是等价关系。

解(a)因为IA

R，所以R是自反的。

(b)因为R－1={〈a，a〉，〈b，a〉，〈a，b〉，〈b，b〉，〈c，c〉，〈d，c〉，〈c，d〉，〈d，d〉}=R，所以R是对称的。

(c)因为R

R={〈a，a〉，〈a，b〉，〈b，a〉，〈b，b〉，〈c，c〉，〈c，d〉，〈d，c〉，〈d，d〉}R，所以R是传递的。

综上所述，R是等价关系，其关系图如图3.9.1所示。⊆∘

图3.9.1

定义3.9.5

设R是非空集合A上的等价关系，对于任意a∈A，称集合［a］R={x|x∈A，xRa}为a关于R的等价类(equivalenceclass)，a称为等价类［a］R的代表元素。如果等价类个数有限，则R的不同等价类的个数叫做R的秩，否则秩是无限的。

等价类［a］R是所有与a具有R关系的元素构成的集合。由等价类的定义可知，［a］R是非空的，因为a∈［a］R。

定理3.9.1

设R是非空集合A上的等价关系,对于a，b∈A有aRb，当且仅当［a］R=［b］R。

证明充分性。若［a］R=［b］R，因为a∈［a］R，所以a∈［b］R，故aRb。

必要性。若aRb，对任意x∈［a］R，有xRa，由传递性可知xRb，即x∈［b］R，所以［a］R

［b］R，同理可证［b］R

［a］R。

故［a］R=［b］R。

证毕⊆⊆

定义3.9.6

设R是集合A上的等价关系，由R确定的所有等价类组成的集合，称为集合A上关于R的商集(quotientset)，记为A/R。

A/R={［x］R|x∈A}

例5

设A={1，2，3，4，5，8}，R是A上的“模3同余”关系。

(a)求关于R的所有等价类。

(b)求A/R。

解

R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，5〉，〈2，8〉,〈3，3〉,〈4，1〉，〈4，4〉，〈5,2〉，〈5，5〉,〈5，8〉，〈8，2〉,〈8，5〉,〈8，8〉}，R是一个等价关系，其关系图如图3.9.2所示。图3.9.2

定理3.9.2

设R是非空集合A上的等价关系，则有

(1)任取x∈A，［x］R≠。

(2)任取x,y∈A，或者［x］R=［y］R，或者［x］R∩

［y］R=。

(3)

=A

。

证明(1)任取x∈A，因为〈x，x〉∈R，所以x∈