离散数学之集合论

第二篇 集合与关系

集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。

随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。

现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。

本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。

第2-1章 集合及其运算

§2-1-1 集合的概念及其表示

一、集合的概念

“集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作

69

a?A，读作“a属于A”。否则，若a不属于A，就记为a?A，读作“a不属于A”。

一个集合，若其组成集合的元素个数是有限的，则称作“有限集”，否则就称作“无限集”。

集合的表示方法有两种：一种是列举法又称穷举法，它是将集合中的元素全部列出来，元素之间用逗号“，”隔开，并用花括号“{ }”在两边括起来，表示这些元素构成整体。

例2-1-1.1 A＝｛a , b , c , d｝； B＝｛1 ，2 ，3 ，?｝ ；

D＝｛桌子，台灯，钢笔，计算机，扫描仪，打印机｝；E?{a,a2,a3,?}。

集合的另一种表示方法叫做谓词法又叫叙述法，它是利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合的方法。设x为某类对象的一般表示，P(x)为关于x的一个命题，我们用{xP(x)}表示“使P(x)成立的对象x所组成的集合”，其中竖线“|”前写的是对象的一般表示，右边写出对象应满足（具有）的属性。

例2-1-1.2 全体正奇数集合表示为 S1?{xx是正奇数}，

所有偶自然数集合可表示为 E?{m2m且m?N} 其中 2|m表示2能整除m。

[0,1]上的所有连续函数集合表示为 C[0,1]?{f(x)f(x)在[0，1]上连续} 集合的元素也可以是集合。例如S?{a,{1,2},p,{q}}，

{1,2}?S，但必须注意：q?{q}，而q?S，同理1?{1,2}，

S

a {1，2} p 1

2

{q} q

而1?S。

两个集合相等是按下述原理定义的。外延性原理：两个集合相等，当且仅当两个集合有相同的元素。两个集合A，B相等，记作A?B，两个集合不相等，记作A?B。

集合中的元素是无次序的，集合中的元素也是彼此不相同的。 例如： {1,2,4}?{1,4,2},{1,2,4}?{1,2,2,4},

{{1,2}，4}?{1,2,4},{1,3,5,?}?{xx是正奇数}。

集合中元素可以是任何事物（如例2-1-1.1）。不含任何元素的集合称为空集，记为Φ。例如，方程 x2?1?0的实根的集合是空集。

二、集合与集合间的关系

70

“集合”、“元素”、元素与集合间的“属于”关系是三个没有精确定义的原始概念，对它们仅给出了直观的描述，以说明它们各自的含义。现利用这三个概念定义集合间的相等关系，集合的包含关系，集合的子集和幂集等概念。

定义2-1-1.1 设A，B是任意两个集合，如果A中的每一个元素都是B的元素，则称A是B的子集，或A包含于B内，或B包含A。记作A?B，或B?A。

即 A?B??x(x?A?x?B)

可等价地表示为 A?B??x(x?B?x?A)。

例2-1-1.3 设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则 N?Q?R?C，

{1}?N,{1,1.2,9.9}?Q,{2,?}?R。

如果A不是B的子集，则记为A?B（读作A不包含在B内），显然， A?B??x((x?A)?(x?B))。 集合间的包含关系“?”具有下述性质：

2-1-1. 自反性 A?A；

2. 传递性 (A?B)?(B?C)?(A?C)。 证明：采用逻辑演绎的方法证明。

⑴ A?B P ⑵ ?x((x?A)?(x?B)) T(1)E ⑶ (a?A)?(a?B) US(2) ⑷ B?C P ⑸ ?x((x?B)?(x?C)) T(4)E ⑹ (a?B)?(a?C) US(5) ⑺ (a?A)?(a?C) T(3)(6)I ⑻ ?x((x?A)?(x?C)) UG(8) ⑼ A?C T(8)E

71

定义2-1-1.2 如果集合A的每一元素都属于集合B，而集合B中至少有一元素不属于A，则称A为B的真子集，记作A?B。

即 A?B??x((x?A)?(x?B))??x((x?B)?(x?A))

例如：{a,b}是{a,b,c}的真子集；N是Q的真子集，Q是R的真子集；R是C的真子集。

注意符号“∈”和“?”在概念上的区别，“∈”表示元素与集合间的“属于”关系，“?”表示集合间的“包含”关系。

定理2-1-1.1 集合A＝B的充分必要条件是：A?B且B?A。（外延性原则） 证明：必要性， 即证：A?B?(A?B)?(B?A)

A?B?(?x((x?A)?(x?B)))?(?x((x?B)?(x?A)))?(A?B)?(B?A)

充分性，即证：(A?B)?(B?A)?A?B

A?B??x((x?A)?(x?B))?A?B?(A?B)?(A?B)?F

或 A?B??x((x?B)?(x?A))?B?A?(B?A)?(B?A)?F # 定理2-1-1.2 对于任一集合A，??A，且空集是唯一的。

证明： 假设??A为假，则至少存在一个元素x，使x??且x?A，因为空集?不包含任何元素，所以这是不可能的。

设??与?都是空集，由上述可知，????且????，根据定理2-1-1.1知????，所以，空集是唯一的。

注意：??{?}，??{xP(x)??P(x)} P(x)是任一谓词。

例2-1-1.4 设 A?{2,3},B为方程 x2?5x?6?0的根组成的集合，则 A＝

B 。

定理2-1-1.1指出了一个重要原则：要证明两个集合相等，即要证明每一个集合中的任一元素均是另一集合的元素。这种证明是靠逻辑推理理论，而不是靠直观。证明两个集合相等是应该掌握的方法。

定义2-1-1.3 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全

72

集，记作E。对于任一x?A，因A?E，所以x?E，

也即 ?x(x?E) 恒为真 故 E?{xP(x)??P(x)} ， P(x)为任一谓词。

注意：全集的概念相当于论域，只包含与讨论有关的所有对象，并不一定包含一切对象与事物。例如：在初等数论中，全体整数组成了全集；方程x2?1?0的解集合，在全集为实数集时为空集，而全集为复数集时解集合就不再是空集，此时解集合为

{i,?i}，i2?1。

三、幂集

定义2-1-1.4 给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。记为P (A)（或记为2A）。即 P (A)＝{X|X?A}。

例2-1-1.5 A = {0 , 1 , 2 }，则 P (A) ＝ {Φ , {0} , {1} , {2} , {0 , 1} , {0 , 2} , {1 , 2} , {0 , 1 , 2 } }；

P (Φ)＝{Φ}；P ({a})={Φ,{a}}；P ({Φ}) = {Φ,{Φ}}。

定理2-1-1.3 设A?{a1,a2,?,an}，则 |P (A)|＝2n。 其中：|P (A)|表示集合P (A)中元素的个数。

证明：集合A的m (m = 0 , 1 , 2 ,? , n )个元素组成的子集个数为从n个元素中取m

m个元素的组合数，即Cn，故P (A)的元素个数为：

nm|P (A)|＝C?C???C??Cn

0n1nnnm?0n根据二项式定理 (x?y)??Cxynmnmm?0n?mm 令x = y = 1得 2??Cn

nm?0n故 |P (A)|＝2n。

四、集合的数码表示

在中学学习集合时，特别强调了集合中元素的无序性，但是，为了用计算机表示集合及其幂集，需要对集合中元素规定次序，即给集合中元素附上排列指标，以指明一个元素关于集合中其他元素的位置。如A 2= {计算机，打印机}是二个元素的集合，令“计算机”为集合A的第一个元素，“打印机”为集合A 2的第二个元素。改记为A 2 = { x 1 ,

73

x 2 } ，则P (A 2)的四个元素，可记为，??S00，{x1}?S10，{x2}?S01，{x1,x2}?S11，其中S的下标，从左到右分别记为第一位，第二位，它们的取值是1还是0由第一个和第二个元素是否在该子集中出现来决定，如果第i个元素出现在该子集中，那么S下标的第i位取值为1，否则取值为0（i = 0 , 1）。即令J = {00 , 01 , 10 , 11 } = { i | i 是二位二进制数，00 ≤ i ≤11 }，则P (A 2) ＝ { S i | i∈J }。类似地，三个元素集合 A 3 = { x1 , x 2 , x 3 }的幂集P (A 3) ＝ { S i | i∈J , J = { i | i二进制数，000 ≤ i ≤ 111} }，因此，

S010 = {x 2 } ， S101 = {x 1 , x 3 }。上述幂集中元素表示法实际上是一种编码，可以推广到n个元素的集合A n的幂集上，P (A n)的2 n个元素可以表示为

n

n

Si ，i∈J={i| i是二进制数，0 0 ? 0 ≤ i ≤ 1 1 ? 1 }

如果A6?{x1,x2,x3,x4,x5,x6}，P (A 6)的26个元素记为 S0,S1,?,S26?1，此时S的下标是十进制整数，如何求出S7,S12是A 6的那些元素组成的子集呢？将下标转换为二进制的整数，不足六位的在左边补入需要个数的零，使之成为六位的二进制整数，由排列的六位二进制整数推断出，含有那些元素。凡第i位为0，表示x i不在此子集中，凡第i位为1表示x i在此子集中，故

这种方法可以推广到一般情况，B7?B111?B000111?{x4,x5,x6}，B12?B001100?{x3,x4}。即将十进制整数转换为二进制整数，在左边补入需要个数的零使之成为n位的二进制数，若第i位为0，表示x i不在此子集中，若第i位为1表示x i在此子集中。

子集的这种编码法，不仅给出了一个子集含那些元素的判别方法，还可以用计算机表示集合、存贮集合以供使用。

§2-1-2 集合的基本运算

集合的运算，就是以集合为对象，按照确定的规则得到另外一些新集合的过程。给定集合A，B，可以通过集合的并（∪）、交（∩）、相对补（－）、绝对补（ˉ）和对称差（⊕）等运算产生新的集合。

一、集合并（∪）运算

定义2-1-2.1 设A ，B为任意两集合，所有属于集合A或属于集合B的元素组成

74

的集合，称为集合A和B的并集。记作 A∪B

A?B?{x(x?A)?(x?B)}

A B 并集的文氏（英国数学家Johan Wenn (1834~1883)）图

例2-1-2.1 设A = {1 , 2 , 3 , 4 }，B = {2 , 4 , 5 , 6 }

则 A∪B = {1 , 2 , 3 , 4 , 5 , 6 }。注意：集合是由互不相同元素组成的，在A∪B中2，4各写一次，不能重写。

由集合并运算的定义知，并运算具有如下性质： 定理2-1-2.1 设A，B，C为任意三个集合，则 ⑴ 幂等律 A∪A=A； ⑵ 交换律 A∪B = B∪A；

⑶ 结合律 (A∪B)∪C = A∪(B∪C)； ⑷ 同一律 A∪Φ= A； ⑸ 零 律 A∪E = E； ⑹ A?A∪B，B?A∪B； ⑺ A∪B = B ? A?B。

证明：性质⑴，⑵，⑷，⑸，⑹由定义2-1-2.1立即可以得到。 ⑶的证明

(A∪B)∪C ＝ {x | x∈(A∪B)∪C } = { x | (x∈A∪B)∨(x∈B) }

＝ { x | ((x∈A)∨(x∈B))∨(x∈B)}={ x|(x∈A)∨((x∈B)∨(x∈C))} = { x |( x∈A)∨(x∈B∪C)} = { x | x∈A∪(B∪C)} = A∪(B∪C) 。

⑺的证明：必要性证明 ?x(x?A)??x(x?A?B)??x(x?B) 所以 A?B。 充分性证明 由⑹知B?A∪B，现证明 A∪B?B ?x(x?A?B)??x(x?B) 所以有 A∪B = B。

例2-1-2.2 设 A?B，C?D，则 A∪C?B∪D

证明： A?C?{xx?A?C}?{x(x?A)?(x?C)}A?B,C?DA?BA?B?B?{x(x?B)?(x?D)}

＝{xx?B?D}?B?D 即 A∪C?B∪D成立。

75

同理可证 A?B?A?C?B?C。

因为集合的并运算满足结合律，对n个集合A1 , A2 ,?, A n 的并集A1?A2???An定义为至少属于A1 , A2 ,?, A n之一的那些元素构成的集合。A1?A2???An通常缩写成?Ai。

i?1nA1?A2???An????An?{x?n?N,x?An}其中N是自然数集合。

n?1?一般地，?Ak?{x?k?I,x?Ak}。

k?I集合的并运算，就是把给定集的那些元素放到一起合并成一个集合，在这个合并中相同的元素只要一个。如设A1?{1,2,3},A2?{3,8},A3?{2,3,6}则

?Ai?13i?{1,2,3,6,8}。

二、集合的交（∩）运算

定义2-1-2.2 设任意两个集合A 和B，由集合A和B共同元素组成的集合，称为集合A和B的交集，记作 A∩B。

A B A?B?{x(x?A)?(x?B)}。

交集的文图

例2-1-2.3 设A?{a,b,c,d,e},B?{a,c,e,f} 则 A?B?{a,c,e}。 例2-1-2.4 设A = {X高等学校的本科学生}，B = {X高等学校计算机专业的学生}，则

A∩B = {X高等学校计算机专业的本科学生}

例2-1-2.5 设A是所有能被k整除的整数集合，B是所有能被l 整除的整数集合，则A∩B是所有能被k与l最小公倍数整除的整数集合。

由集合交运算的定义知，集合交运算具有如下性质： 定理2-1-2. 2 设A , B , C是任意三个集合，则 (1) 幂等律 A∩A = A ； (2) 交换律 A∩B = B∩A ；

(3) 结合律 (A∩B)∩C = A∩(B∩C) ；

76

(4) 零 律 Φ∩A = Φ； (5) 同一律 E∩A = A ； (6) A∩B?A , A∩B?B ； (7) A∩B = A?A?B。

证明：根据定义2-1-2.2，性质(1) , (2) , (4) , (5) , (6)立即可以得到。 性质（3）的证明：

(A∩B)∩C = { x | x∈(A∩B)∩C } = { x|(x∈A∩B)∧(x∈C)}

= {x|((x∈A)∧(x∈B))∧(x∈C)} = {x | (x∈A)∧((x∈B)∧(x∈C)} = {x|(x∈A)∧(x∈B∩C)} = {x | x∈A∩(B∩C)} = A∩(B∩C)

性质（7）的证明：

?x(x?A)??x(x?A?B)??x(x?B) 即得A∩B = A ? A?B 必要性的证明：

A?B?A充分性得证明：由性质（6）知A∩B?A , 现证 A?A∩B 采用逻辑演绎推理法

(1) ?x(x?A) P(附加前提) （2） a?A US(1) (3) A?B P (4) ?x((x?A)?(x?B)) T(3)E (5) (a?A)?(a?B) US(4) (6) a?B T(2 , 5) I (7) (a?A)?(a?B) T(2 , 6) I (8) ?x((x?A)?(x?B)) UG(7) (9) ?x(x?A?B) T(8)E （10） A?A∩B CP

若集合A , B没有共同的元素，则可记为A∩B = Φ,这时称A , B不相交。 由集合的交运算具有结合律，同样可以定义n个集合A 1 , A 2 ,?, A n的交集，也可以定义集序列A 1 , A 2 ,?, A n ,?的交集，分别记为

77

A1?A2???An??Ai?{xi?{1,2,?,n},x?Ai}

i?1nA1?A2???An????An?{xn?{1,2,?,n,?},x?An}

n?1?一般地，集合族{A k}k∈I 中各集的交记成

?Ak?Ik其定义为

?Ak?Ik?{x?l?I,x?Al}。

若序列A 1 , A 2 ,?, A n ,?任意两集合A i , A j (i?j) 不相交，则称 A 1 , A 2 ,?, A n ,?是两两不相交的集序列。

三、交运算与并运算之间的联系

定理2-1-2.3 （分配律） 设A , B , C为任意三个集合，则 （1）交运算对并运算的分配律

A?(B?C)?(A?B)?(A?C)

（2）并运算对交运算的分配律

A?(B?C)?(A?B)?(A?C)

证明：（1）A∩(B∪C) = {x |x∈A∩(B∪C)} = {x |(x∈A)∧(x∈B∪C)}

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

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

= {x |x∈(A∩B)∪(A∩C)} = (A∩B)∪(A∩C)

当然可以仿照（1）的证明方法证明（2）的成立，现在采用（1）来证明（2），注意到 A?A∪B，A∩C?A，由（1）可得

(A∪B)∩(A∪C) =( (A∪B)∩A)∪((A∪B)∩C) = A∪(A∩C)∪(B∩C) = A∪(B∩C) 。 同理可以利用（2）证得（1）成立（读者自行完成），于是（1）成立?（2）的成立。

定理2-1-2.4 （吸收律）设A , B为任意两集合，则 （1） A∪(A∩B) = A ； （2）A∩(A∪B) = A ； 证明： 由分配律可得

（1） A∪(A∩B) = (A∩E)∪(A∩B) = A∩(E∪B) = A∩E = A

（2） A∩(A∪B) = (A∪Φ)∩(A∪B ) = A∪(Φ∩B) = A∪Φ = A ﹟

78

四、集合的补运算

定义2-1-2.3 设A , B为任意两集合，由属于A而不属于B的一切元素构成的集合，称为A与B的差运算（又称B对于A的补运算，或相对补），记为A-B，A-B称为A与B的差集（或B对于A的补集）。

A?B?{x(x?A)?(x?B)}?{x(x?A)??(x?B)} 若A = E ，对任意集合B关于E的补集E-B ，称为集合B的绝对补，记作B 。

A B E A E B?E?B?{x(x?E)?(x?B)}

例2-1-2.6 设A = {1 , 2 , 3 , 4 , 5} ， B = {1 , 2 , 4 , 7 , 9 } ，则 A-B = {3 , 5 }。

例2-1-2.7 设A是素数集合，B是奇数集合，则A-B = {2}。

例2-1-2.8 设E = {X高校计算机专业学生}，A = {X高校校计算机专业本科学生}，

则A= {X高校计算机专业研究生}。

由集合补运算的定义知，补（差）集合有如下性质 定理2-1-2.5 设A , B , C 为任意三集合，则 （1） 对合律 A?A； （2） E??； （3） ??E；

（4） 排中律 A?A?E； （5） 矛盾律 A?A??； （6） （De . Morgan定理）

① A?B?A?B , ② A?B?A?B ；

（7） ① A?B?A?B ， ② A?B?A?(A?B)； （8） A?(B?C)?(A?B)?(A?C)；

（9）若A?B，当且仅当 ① B?A ； ② (B?A)?A?B。 证明：由补运算的定义立即可得性质（1）～（5）。

79

A-B

A

（6）的证明： ①

A?B?{xx?A?B}?{xx?A?B}?{x(x?A)?(x?B)}?{x(x?A)?(x?B)}?{xx?A?B}?A?B

②的证法与①类似，请读者自行证明。 （7）的证明：

① A?B?{x(x?A)?(x?B)}?{x(x?A)?(x?B)}?{xx?A?B}?A?B； ② A?(A?B)?A?A?B?A?(A?B)?(A?A)?(A?B)?A?B?A?B。 （8）的证明：

(A?B)?(A?C)?(A?B)?(A?C)?(A?B)?(A?C)

?(A?B?A)?(A?B?C)?A?B?C?A?(B?C)。 （9）的证明： 证明①

必要性 ?x(x?B)??x(x?B)??x(x?A)??x(x?A) 即 B?A； 充分性 ?x(x?A)??x(x?A)??x(x?B)??x(x?B) 即 A?B。 证明②

必要性 (B?A)?A?(B?A)?A?(B?A)?(A?A)?B?A?B； 充分性 A?A?(B?A)?(B?A)?A?B。﹟ 五、集合的对称差运算

定义2-1-2.4 设A , B为任意两集合，由“属于A而不属于B”或“属于B而不属于A”的一切元素构成的集合，称为A , B的对称差,记作A⊕B。

A B E A?BA?BB?AA?B?(A?B)?(B?A)?{x(x?A)?(x?B)}?{x((x?A)?(x?B))?(x?A?B)}A?B 对称差运算的性质

定理2-1-2.6 设A , B , C为任意三集合，则 （1） A?B?B?A； （2） A???A； （3） A?A??；

80

（4） A?B?(A?B)?(A?B)； （5） (A?B)?C＝A?(B?C)；

（6）交关于对称差的分配律 A?(B?C)?(A?B)?(A?C)； （7） 若A?B?A?C，则 B = C 。 证明：

由对称差的定义立即可得（1），（2），（3），（4）的证明。 （5）的证明

(A?B)?C?((A?B)?(A?B))?C?((A?B)?(A?B)?C)?(((A?B)?(A?B))?C)?((A?B)?(A?B)?C)?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)A?(B?C)?A?((B?C)?(B?C))?(A?((B?C)?(B?C)))?(A?((B?C)?(B?C)))?(A?(B?C)?(B?C))?((A?B?C)?(A?B?C))?(A?B?C)?(A?B?C)?(A?B?C)?(A?B?C)所以 (A?B)?C＝A?(B?C)。

（6）的证明

(A?B)?(A?C)?((A?B)?(A?C))?((A?B)?(A?C))?((A?B)?(A?C))?((A?B)?(A?C))?(A?B?C)?(A?B?C)?A?((B?C)?(B?C))?A?(B?C)（7）的证明

(A?B)?(A?C)?A?(A?B)?A?(A?C)?(A?A)?B?(A?A)?C

???B???C?B?C

从对称差定义或文图容易看出

A?B?(A?B)?(A?B)?(A?B)?(A?B)?(A?B)，

A?B?(A?B)?(A?B)。

81

§2-1-3 集合中元素的计数

一、两个基本原理

加法原理：若一个事件以m种方式出现（这些方式构成集合A），另一个事件以n种方式出现（这些方式构成集合B），这两个事件完成一件即能达到目的（构成集合A∪B），则达到目的的方式数为m+n。

例2-1-3.1 假设从城市A到城市B有铁路两条，公路三条，航线一条，那么按加法原理，从城市A到城市B有2＋3＋1＝6种走法。

乘法原理：若一个事件以m种方式出现（这些方式构成集合A），另一个事件以n种方式出现（这些方式构成集合B），这两个事件同时完成才能达到目的（构成集合A∩B），则达到目的的方式数为m n。

例2-1-3.2 一位学生想从图书馆借离散数学和C# 语言书各一本，书架上有三种不同作者的离散数学书，有两种不同作者的C# 语言书，那么这位学生共有3×2＝6种不同的选法。

二、排列、组合

中学里已学过的计数公式是排列组合公式。从n个元素的集合中每次取m个的排列和组合的公式分别为：

Pnmn!n!m ，Cn? P?n(n?1)?(n?m?1)??(n?m)!m!m!(n?m)!mn对排列Pnm：若m = n时称为全排列，m < n时称为选排列。排列和组合的最基本恒等式有：

mPnm?m!Cnmn?m,Cn?Cnmmm?1,Cn?Cn?1?Cn?1

例2-1-3.3 将computer的字母全部取出进行全排列，其中c不在第一位，r不在末位，问共有多少种排法？

解：computer字母的全排列数为P88?8!，其中c排在第一位的排法共有7！种，r排在末位的排法共有7！，除去这些不合要求的排法，还有8！-（7！＋7！）= 30240种，然而这还不是答案，因为c在第一位的7！种排法中r可能排至末位的7！中c可能排在第一位，即c在第一位，r在末位的排法被减去了两次，实际上应该只减一次，故把不应该减的加回去才能得到正确的答案。所求的答案为：

。 P88?2P77?P66?30960（种）

82

这种分析问题的方法称为“多退少补法”，这种思想在“包含排斥原理”中还要用到。

例2-1-3.4 将1 , 2 , 3三个数字排成2行3列的矩阵，要求同行和同列上都没有相同的数字，问这样的数字矩阵有多少？（实际上这就是集合{1 , 2 , 3 }到自身上的一些双射或置换，这些双射不允许一个元素以自身为像）

解： 先排矩阵的第一行共有P33?3!?6种排法，如果不管题目的要求，第二行也有6种排法，由乘法原理，知共有6×6＝36种矩阵。这些矩阵包含了有一列数字相同的情况，有两列因而就有三列数字相同的情况，按题目要求这些矩阵都应该除去，这些矩阵

112的个数可如下计算：一列数字相同其余两列数字不同的矩阵数有C3C3P2种；有两列数

字相同从而就有三列数字相同的矩阵数有3！＝6个，因此所求的矩阵个数为

112P33?P33?C3C3P2?P33?12。

m是从n个元素中任意取m个元素（不重复抽取）的排列与组合，但是有些Pnm与Cn实际问题需要在n个元素中重复抽取若干个元素来排列，如用0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9这十个数字来编制代码，，每个号码就可以重复使用某个数字。一般地，从n个元素的集合中抽取m个元素，允许重复的排列数为：nm。实际上可以设想有m个位子，每个位子都可以放上n个元素中的任一个，允许

m

重复，由乘法原理即知有n×n×?×n = n m 种排法。 例2-1-3.5 求电子计算机中的6位二进制数。

解：电子计算机中的数码第一位数不能为0，故首位必须为1，后面五位每位都可选0或1，固有25?32种排法，因而6位二进制数有32个。

例2-1-3.6 考试时有25个正确或错误的问题，学生也可能不作答，问有多少种不同的考试结果？

解：对每一问题的回答有三种情况：正确、错误和不作答，因而考试结果共有325个。

m关于重复组合数Hn的计算问题。先从一个实例来研究它的计算公式，从{1 , 2 , 3}

中每次取出两个（允许重复抽取）的组合按自然数顺序写出来（即枚举）为：

11 , 12 , 13 , 22 , 23 , 33 (a)

现将各种组合分别加上01，就得到

12 , 13 , 14 , 23 , 24 , 34 (b)

83

一般来说序偶具有以下特点：

定义2-2-1.1序偶可以看成是两个具有固定次序的客体组成的有序对，常常用它来表达两个客体之间的关系，它与一般集合不同的是序偶具有确定的次序。在集合中{ a , b } = { b , a }，但对序偶< a , b > ≠ < b , a >（这里a≠b）。

2.两个序偶相等，< x , y > = < u , v >, 当且仅当 x = u ， y = v 。

3.序偶< a , b >中两个元素不一定来自同一集合，它们可以代表不同类型的事物。如a代表操作码，b代表地址码，则序偶< a , b >代表一条单地址指令；当然也可以用b代表操作码，a代表地址码，则序偶< a , b >也代表一条单地址指令。但上述约定，已经确定，序偶的次序就不能再变化了。

在实际问题中，有时会用到有序3元组，有序4元组，?，有序n元组。 定义2-2-1.2 一个有序n元组（n≥3）是一个序偶，其中第一个元素是一个有序n-1元组，第二个元素是一个客体。一个有序n元组记作< x1 , x 2 , ?, x n >，

即< x1 , x 2 , ?, x n > = << x1 , x 2 ,? , x n-1 > , x n >。

由序偶相等的定义，<< x , y > , z > = << u , v> , w > 当且仅当 < x , y > = < u , v> , z = w, 也即

x = u , y = v , z = w。应该注意的是：当x ≠ y时，< x , y , z > ≠ < y , x , z > 。<< x , y > , z > ≠ >，因为 >不是三元组。

<< x1 , x 2 ,? , x n-1 > , x n > = << y1 , y 2 ,? , y n-1 > , y n >

?(x1 = y1)∧(x 2 = y2 )∧(x n-1 = yn-1)∧(x n = y n )。 二、笛卡尔积

定义2-2-1.3 设A , B为任意两个集合，则称集合

B。 {?x,y?(x?A)?(y?B)}为A , B的笛卡尔积，记为A×即 A×B = {?x,y?(x?A)?(y?B)}。

注意：2-1-1.A×B与A , B的次序有关，一般地 A×B≠B×A，即交换律不成立。 2.若A?S , B?S 则 A?B,A?B,A?B,A?B,A都是S的子集，但是

A?B?S。

3.对任意集合A ,有 A?????A??。

4.笛卡尔积不满足结合律，即(A?B)?C?A?(B?C) 实际上，当A ≠ Φ , B ≠ Φ , C ≠ Φ 时，

89

(A?B)?C = { << a , b> , c >| (a∈A )∧( b∈B)∧(c∈C) }； A?(B?C) = {< a ,< b , c >> |(a∈A )∧( b∈B)∧(c∈C)}

按有序对相等的定义知，笛卡尔积的结合律不成立。

根据笛卡尔积中元素相等的定义，可知，A?B?C和A?(B?C)，A?(B?C)是彼此不相等的集合，但是为了方便起见，通常约定一般笛卡尔积从左到右加括号，即

(((A?B)?C)?D)。在这个约定下，省去括号而简写为 A?B?C?D。

例2-2-1.1 设A = {1 , 2 , 3 } , B = {a , b } , C = {0} , D = Φ，则 A×B = {<1 , a > , <1 , b > , <2 , a > , <2 , b > , <3 , a > , <3 , b > }； B×A = {< a , 1 > , < a , 2 > , < a , 3 > , < b , 1 > , < b , 2 > , < b , 3 > }； A×C = {< 1 , 0 > , < 2 , 0 > , < 3 , 0 > }； C×A={< 0 , 1 > , < 0 , 2 > , < 0 , 3 > }； A×D = Φ , B×D = Φ。 笛卡尔积运算的性质

定理2-2-1.1 设A , B , C为任意三个集合，则笛卡尔积运算对集合的并、交、差运算分别满足分配律，即

（1） A × ( B ∪ C ) = ( A × B ) ∪ ( A × C ) ； （2） ( A ∪ B ) × C = ( A × C ) ∪ ( B × C ) ； （3） A × ( B ∩ C ) = ( A × B ) ∩ ( A × C ) ； （4） ( A ∩ B ) × C = ( A × C ) ∩ ( B × C ) ； （5） A× ( B - C ) = ( A × B ) - ( A × C ) ； （6） ( A - B ) × C = ( A × C ) - ( B × C )。 证明： 用命题演算的方法证明。 (1)的证明：对于任意< x , y >

< 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 )。

90

（2）的证明与（1）类似，请读者自行完成。 （3）的证明：对于任意< x , y >

< 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 )。 （4）的证明与（3）类似，请读者自行完成。 （5）的证明：对于任意< x , y >

< 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 )。 （6）的证明与（5）类似，请读者自行完成。﹟ 定理2-2-1.2 设A , B , C为任意三个集合，C≠Φ，则 （1）A?B的充要条件是A×C?B×C； （2）A?B的充要条件是C×A?C ×B。 证明：（1）的证明：

必要性：即证 A?B?A×C?B×C 任意< x , y >

< x , y >∈A×C ?(x∈A)∧(y∈C) ?(x∈B)∧(y∈C) ?< x , y >∈B×C 所以，A×C?B×C。

充分性：即证 A×C?B×C ? A?B

?x?A，c?C

< x , c >∈A×C?< x , c >∈B×C ?( x ∈ B)∧( c ∈ C )， 所以，A?B。 同理可以证明（2）。

91

定理2-2-1.3 设A , B , C , D为四个非空集合，则

A?B?C?D 当且仅当 A?C,B?D。

证明：必要性，即证明 A?B?C?D?A?C,B?D

?a?A,?b?B

?a,b??A?B??a,b??C?D?(a?C)?(b?D)

所以，A?C,B?D。

充分性，即证明 A?C,B?D?A?B?C?D 对于任意 ?a,b?

?a,b??A?B?(a?A)?(b?B)?(a?C)?(b?D)??a,b??C?D

所以，A?B?C?D。

定义2-2-1.4 设A 1 , A 2 ,… , A n是集合（n≥2），它们的n阶笛卡尔积，记作 A 1 × A 2 ×?×A n，其中

A 1 × A 2 ×?×A n＝{< x 1 , x 2 ,? , x n >|( x 1∈A1)∧(x 2∈A 2)∧?∧(x n∈A

n)}

当A 1 = A 2 = ? = A n时，它们的笛卡尔积简记为An 。 例如：设A={a,b}，则

A3 = { < a , a , a > , < a , a , b > ,< a , b , a > , < a , b , b > , < b , b , b > ,

< b , b , a > , < b , a , b > , < b , a , a > }。

§2-2-2 二元关系

一、二元关系的基本概念

所谓二元关系就是在集合中两个元素之间的某种相关性。例如A , B , C三人进行一种比赛，如果任何两个人之间都要比赛一场，那么总共要比赛三场，假设这三场比赛的结果是：B胜A，A胜C，B胜C，把这个结果记为{ , , }，其中表示x胜y。它表示了集合{A , B , C}中元素之间的一种胜负关系。再如，A , B , C三个人和α,β,γ，δ四项工作，已知A可做α和δ工作，B可做δ工作，C可做α和β工作，那么任何工作之间的对应关系可以记作

92

R = { , < A , β > , < B , δ > , < C , α > , < C , β > }

这是人的集合{A , B , C}到工作集合{α,β,γ,δ}之间的关系。

定义2-2-2.1 任一序偶的集合确定了一个二元关系R ，R中任一序偶可记作∈R或xRy。不在R中的任一序偶可记作?R或x y。

定义2-2-2.2 设A , B为集合，A×B的任意子集所定义的二元关系R，称作从A到B的二元关系当A = B时，R称作A上的二元关系。

即 R?A?B，R?{?x,y?x?A1?A,y?B1?B}。

称A1为二元关系R的前域，记为 A1?dom?R{x?y?B,?x,y??R}； 称B1为二元关系R的值域，记为 B1?rangeR?{y?x?A,?x,y??R}； R的前域和值域一起称作R的域，记作FLD = domR∪rangeR 从关系的定义可以看出：domR?A , rangeR?B。

今后把A×B的两个平凡子集称作A×B和Ф分别称作A到B的全关系和空关系，其中EA?{?x,y?(x?A)?(y?A)}?A?A。称IA?{?x,x?x?A}为恒等关系。

当A = B时，关系R是A×B的子集，这时称R为在A上的二元关系。

但是我们注意到：R?A×B?(A∪B)×(A∪B) = Z×Z ( 这里Z = A∪B )，因此任一关系总可以限定某一集合上进行讨论。

如果|A| = n，那么|A×A| = n2，A×A的子集有2n个，每一个子集代表一个A上的关系，所以A上有2n个不同的二元关系。例如A = { 0 , 1 , 2 }，则A上可以定义

2223?512个不同的关系。

例2-2-2.1 设A = { 1 , 2 } , B = { 2 , 3 , 4 } , R = { < 1 , 2 > , < 1 , 4 > , < 2 , 2 > } , 则domR = { 1 , 2 } , rangeR = { 2 , 4 } 。即 1R2 , 1R4 , 2R2， 但13 , 23 , 24。

例2-2-2.2 设R表示实数集，R1?{?x,y?xy?1}，R2?{?x,y?x2?y2?9}，

R3?{?x,y?y2?x}是R×R的三个子集，它们所代表的关系如下：

2双曲线xy?1在第一、三象限的点的横坐标与纵坐标符合关系R 1。

圆心在坐标原点，半径为3的圆内和圆上的点的横坐标与纵坐标符合关系R 2。 抛物线y2?x上和线的外侧之点的横坐标与纵坐标符合关系R 3。

93

例2-2-2.3 设A = {2 , 3 , 4 } , B = { 2 , 3 , 4 , 5 , 6 } , R = { < x , y >| x∈A , y∈B , x整除y }, 则

R = { < 2 , 2 > , < 2 , 4 > , < 2 , 6 > , < 3 , 3 > , < 3 , 6 > , < 4 , 4 > }。 S={ < x , y >| x∈A , y∈B , x > y+2 } = Ф。

二、二元关系的表示 1.关系的矩阵表示

设给定两个集合A?{a1,a2,?,am}和B?{b1,b2,?,bn}，R为从A到B的二元关系，则对应于关系R有一个关系矩阵MR?[rij]m?n，其中

rij??1,?ai,bj??R;?? (i?1,2,?,m;0,?a,b??R.?ij?j?1,2,?,n)

例2-2-2.4 设A = { 1 , 2 , 3 , 4 },写出集合A上大于关系“>”的关系矩阵。 解：> = { < 2 , 1 > , < 3 , 1 > , < 3 , 2 > , < 4 , 1 > , < 4 , 2 > , < 4 , 3 > }， 故

?0??1M???1??1?例2-2-2.3中的R关系矩阵为

001100010??0?。 ?0?0???10101???MR??01001?

?00100???2.关系的图形表示

设A?{a1,a2,?,am},B?{b1,b2,?,bn},R?A×B。在平面上用“°”或“· ”分别标出A , B中元素的点（称为结点）。如果?ai,bj??R，则自结点ai至结点bj作一条有向弧，箭头指向bj，如果?ai,bj??R，则结点ai与bj之间没有弧线连接，采用这种方法连接起来的图称为R的关系图。

例如，例2-2-2.3中R的关系图为

94

2 3 4 2 3 4 5 6

例2-2-2.5 设A = { 1 , 2 , 3 , 4 } , R?A×A , R = { < 1 , 1 > , < 1 , 3 > , < 2 , 3 > , < 4 , 4 > }，R的关系图为：

1 2

注意：关系图中点的位置，变得长短可以任意。

三、关系的运算

1．关系的并、交、补、差、对称差和包含运算

因为两个集合的笛卡尔积的子集是二元关系，故二元关系就有并、交、补、差、对称差和包含等运算。如R , S是集合A上的两个二元关系，< x , y >∈R∪S表示< x , y >∈A或< x , y >∈S ； < x , y >∈R∩S表示< x , y >∈A且< x , y >∈S , xRy表示xy ,

?x,y??R?S表示?x,y??R且?x,y??S。

4 3

例2-2-2.6 设A＝{1 , 2 , 3 , 4 }, 若H = {|

x?y是整数 }, S = {< x , y >| 2x?y是整数 }。求 H∪S , H∩S , H, S－H , H－S , S⊕H。 3解： H = {< 1 , 1 > , < 1 , 3 > , < 2 , 2 > , < 2 , 4 > , < 3 , 3 > , < 3 , 1 > , < 4 , 4 > , < 4 , 2 > }；S = { < 4 , 1 > }。

H∪S={< 1 , 1 > , < 1 , 3 > , < 2 , 2 > , < 2 , 4 > , < 3 , 3 > , < 3 , 1 > , < 4 , 4 > , < 4 , 2 > , < 4 , 1 >}； H∩S = Ф；

H＝A×A－H = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > , < 3 , 2 > , < 3 , 4 > , < 4 , 3 > , < 1 , 4 > , <

4 , 1 > }；

S－H = S = {< 4 , 1 >}；H－S = H ；S⊕H = H∪S。

定理2-2-2.1 若R和S是从集合A到集合B的两个关系，则R、S的并、交、补、差仍是A到B的关系。

95

证明：因为 R?A×B , S?A×B，

故 R∪S?A×B , R∩S?A×B , S= A×B-S?A×B , R-S = R∩S?A×B。 2、关系的复合运算

在日常生活中，如果关系R表示：a是b的兄弟，关系S表示：b是c的父亲，这时会得出关系T：a是c的叔叔或伯伯，称关系T是由关系R和S复合而得到的新关系；又如关系R1表示：a是b的父亲，关系S1表示：b是c的父亲，则得出关系T1：a是c的祖父，关系T1是由关系R1和S1复合而得到的新关系。

定义2-2-2.3 设R?A×B , S?B×C是两个二元关系，称A到C的关系R?S为R与S的复合关系，表示为：

R?S?{?a,c?(a?A)?(c?C)??b((b?B)?(?a,b??R)?(?b,c?)?S)}。 从R和S求R?S称为关系的合成运算。

当A = B时，规定R0?IA，R1?R，?，Rn?1?Rn?R，（R为自然数）。 例2-2-2.7 设A = { a , b } , B = { 1 , 2 , 3 , 4 } , C = { 5 , 6 , 7 } , R = { < a , 1 > , < a , 2 > , < b , 3 > } , S = { < 2 , 6 > , < 3 , 7 > , < 4 , 5 > }。 则 R?S?{?a,6?,?b,7?}，S?R??。

R与S的关系图如下列点与虚线图，R?S关系图的有向边为下图的实线弧。

1 a b 2 3 4 5 6 7

例2-2-2.8 设A = { 1 , 2 , 3 , 4 } , A上的关系

R = { < 1 , 1 > , < 1 , 2 > , < 2 , 4 > } , S = { < 1 , 4 > , < 2 , 3 > , < 2 , 4 > , < 3 , 2 > }， 求R?S, S?R, R2, R3。

解：R?S = { < 1 , 4 > , < 1 , 3 > } , S?R= { < 3 , 4 > } ,

R2=R?R = { < 1 , 1 > , < 1 , 2 > , < 1 , 4 >} ,

R3?R2?R?{?1,1?,?1,2?,?1,4?}。

例2-2-2.9 设R , S是自然数集合N上的两个二元关系，其定义为

96

1

R?{?x,y?(x?N)?(y?N)?(y?x2)} S?{?x,y?(x?N)?(y?N)?(y?x?1)} 则R?S?{?x,y?(x?N)?(y?N)?(y?x2?1)}

S?R?{?x,y?(x?N)?(y?N)?(y?(x?1)2}。

由此可知，R?S?S?R，即复合关系是不可交换的，但是复合关系满足结合律。 定理2-2-2.2 设 R?A?B，S?B?C，T?C?D，则 (R?S)?T?R?(S?T) 证明： ?x,y??(R?S)?T??c((c?C)?(?x,c??R?S)?(?c,y??T)) ??c((c?C)??b((b?B)?(?x,b??R)?(?b,c??S))?(?c,y??T)) ??b((b?B)?(?x,b??R)??c((c?C)?(?b,c??S)?(?c,y??T))) ??b((b?B)?(?x,b??R)?(?b,y??S?T)) ??x,y??R?(S?T) 所以，(R?S)?T?R?(S?T)。

推论：设 m , n为非负整数，则 Rm?Rn?Rm?n，(Rm)n?Rmn。 定理2-2-2.3 设R?A?B，S?B?C，T?B?C，U?C?D则有 （1） R?(S?T)?(R?S)?(R?T)； （2） (S?T)?U?(S?U)?(T?U)； （3） R?(S?T)?(R?S)?(R?T)； （4） (S?T)?U?(S?U)?(T?U)。 证明：（1）的证明，任取?x,y?

?x,y??R?(S?T)??z((z?B)?(?x,z??R)?(?z,y??(S?T)))??z((z?B)?(?x,z??R)?((?z,y??S)?(?z,y??T))) ??z((z?B)?((?x,z??R)?(?z,y??S))?((?x,z??R)?(?z,y??T)))

?(?x,y??R?S)?(?x,y??R?T)??x,y??(R?S)?R?T所以，R?(S?T)?(R?S)?(R?T)。

97

同理可证（2）。

（3）的证明，任取?x,y?

?x,y??R?(S?T)??z((z?B)?(?x,z??R)?(?z,y??(S?T)))??z((z?B)?((?x,z??R)?(?z,y??S)?(?z,y??T)))??z((z?B)?((?x,z??R)?(?z,y??S)?(?x,z??R)?(?z,y??T))) ?(?x,y??R?S)?(?x,y??R?T)??x,y??(R?S)?(R?T)所以，R?(S?T)?(R?S)?(R?T)。 同理可证（4）。

现在讨论复合关系的关系矩阵的求法。

设 A?{a1,a2,?,am}，B?{b1,b2,?,bn}，C?{c1,c2,?,cp}，

R?A?B，S?B?C，

MR?(rij)m?n ，rij??1,?ai,bj??R；?? 0,?a,b??R。?ij???1,?bj,ck??S；?? ??0,?bj,ck??S。MS?(sjk)n?p， sij复合关系R?S的关系矩阵MR?S构造如下：

如果?ai,ck??R?S，必然存在bj?B使(?ai,bj??R)?(?bj,ck??S)，则MR中故只要MR的第i行，MS的第k列中至少有一个这样的j使rij?1rij?1且MS中sjk?1，

且sjk?1，则在MR?S的第i行k列位置上记1，否则记0。如此考察

i?1,2,?,m,k?1,2,?,p，即确定了MR?S中的元素。即

MR?S?MR?MS?(dik)m?p，其中 dik??(rij?sjk)

j?1n“∨”表示逻辑加：1∨1＝1，1∨0＝1，0∨1＝1，0∨0＝0。 “∧”表示逻辑乘：1∧1＝1，1∧0＝0，0∧1＝0，0∧0＝0。 如例2-2-2.7

?0??1100??0?，MR??M?S?0010??0????1?

01000??0??010???，则 。 M?R?S???1?001??0??98

3、关系的逆运算

定义2-2-2.4 给定二元关系R?A?B，则{?y,x??x,y??R}?B?A称为R的逆关系，记为Rc。

例2-2-2.10 设R?{?x,y?(x?N)?(y?N)?(y?x?1)}是自然数集N上的二元关系，则

Rc?{?y,x?(y?N)?(x?N)?(y?x?1)}

?{?1,0?,?2,1?,?3,2?,?,?x?1,x?,?}。Rc的关系R的逆关系Rc的关系图恰好是关系R的关系图中，将有向弧的方向反置；

关系矩阵恰好是MR的转置矩阵。

关系逆运算的主要性质

定理2-2-2.4 设R , S 都是A到B的二元关系，则下列各式成立： （1）(Rc)c?R； （2） (R?S)c?Rc?Sc； （3）(R?S)c?Rc?Sc； （4）(A?B)c?B?A； （5）R?(A?B)?R； （6）(R)c?Rc； （7）(R?S)c?Rc?Sc。

证明： （1）?x,y??(Rc)c??y,x??Rc??x,y??R，故得证(Rc)c?R。 （2）?x,y??(R?S)c??y,x??R?S?(?y,x??R)?(?y,x??S) ?(?x,y??Rc)?(?x,y??Sc)??x,y??Rc?Sc，

故得证(R?S)c?Rc?Sc。 同理可证（3）。

（4）?x,y??(A?B)c??y,x??A?B??x,y??B?A，故得证(A?B)c?B?A。 （5）由补的定义立即得证。

（6）?x,y??(R)c??y,x??R??y,x??R??x,y??Rc??x,y??Rc 即得证(R)c?Rc。

（7）?x,y??(R?S)c??y,x??R?S?(?y,x??R)?(?y,x??S)

99

?(?y,x??R)?(?y,x??S)?(?x,y??Rc)?(?x,y??(S)c) ?(?x,y??Rc)?(?x,y??Sc)??x,y??Rc?Sc， 即得证(R?S)c?Rc?Sc。

或者 (R?S)c?(R?S)c?Rc?(S)c?Rc?Sc?Rc?Sc。 ＃

定理2-2-2.5 设R是A到B的二元关系，S是B到C的二元关系，则(R?S)c?Sc?Rc。 证明：?x,y??(R?S)c??y,x??R?S??b(b?B)?(?y,b??R)?(?b,x??S) ??b(b?B)?(?b,y??Rc)?(?x,b??Sc)??x,y?Sc?Rc， 即得证(R?S)c?Sc?Rc。

四、关系的性质

通过上述讨论，我们已经看到在集合X上可以定义很多不同的关系，但真正有实际意义的只是其中的一小部分，它们一般都是有着某些性质的关系，下面我们讨论集合 X上的二元关系R的一些特殊性质。

1、关系性质的概念

设R是X上的二元关系，R的主要性质有以下5种：自反性，对称性，传递性，反自反性和反对称性。

定义2-2-2.5 设R为定义在集合X上的二元关系，

（1）如果对于任意x∈X , 都有< x , x >∈R , 则称X上的二元关系R具有自反性。

即 R在X上是自反的??x((x?X)??x,x??R)。

（2）如果对于任意x , y∈X ，当?x,y??R时，就有?y,x??R，则称集合X上的二元关系R具有对称性。

即 R在X上是对称的??x?y((x?X)?(y?X)?(?x,y??R)?(?y,x??R))。 （3）如果对任意x,y,z?X，当?x,y??R,?y,z??R时，就有?x,z??R，则称R在X上具有传递性。

即 R在X上是传递的?

?x?y?z((x?X)?(y?X)?(?z?X?)?(?x,y??R)?(?y,z??R)?(?x,z??R))。

（4）如果对于任意的x?X，都有?x,x??R，则称集合X上二元关系R具有反自

100

反性。

即 R在X上是反自反的??x((x?X)?(?x,x??R))。

（5）如果对任意的x,y?X，当?x,y??R,?y,x??R必有x?y，则称R在X上具有反对称性。

即 R在X上是反对称的?

?x?y((x?X)?(y?X)?(?x,y??R)?(?y,x??R)?(x?y))。

反对称的定义也可以表示为

?x?y((x?X)?(y?X)?(?x,y??R)?(x?y)?(?y,x??R))

事实上：

(?x,y??R)?(?y,x??R)?(x?y)??(x?y)??((?x,y??R)?(?y,x??R))?(x?y)??(?x,y??R)??(?y,x??R)??((x?y)?(?x,y??R))?(?y,x??R) ?(?x,y?R?)?(x?y)?(?y,x??R)2、关系性质举例

例2-2-2.11 设A为任意集合，

① A上的恒等关系IA具有自反性、对称性和传递性，但不具有反自反性； ② 实数集合R上的小于等于关系“?”具有自反性、反对称性和传递性，但不具有称性；

③ 平面三角形上的全等关系“?”具有自反性、对称性、传递性，但不具有反自反性；

④ 设A是人的集合，R是A上的二元关系，?x,y??R，当且仅当x是y的祖先，显然祖先关系R是传递的。

⑤ 平面三角形上的相似关系“～”具有对称性；

例2-2-2.12 设A = { 1 , 2 }，A上的关系R = { < 1 , 2 > } , S = { < 1 , 1 > , < 1 , 2 > } ，则R具有反自反性；S既不具有自反性，也不具有反自反性；

又如，数的大于关系，日常生活中的父子关系等都是反自反的关系。

??x?y例2-2-2.13 设A = { 2 , 3 , 5 , 7 }，R???x,y?是整数?，则R在A上是自

2??反和对称的。

101

x?x?0，所以?x,x??R，故 R是自反的。 2x?yy?x又设 x,y?A，如果?x,y??R，即是整数，则也必是整数，即?y,x??R，

22证明： ?x?A 由于

因此，R是对称的。

例2-2-2.14 设A = { 1 , 2 , 3 }，R 1 = { < 1 , 2 > , < 2 , 2 > }，R 2 ={ <1,2>}， R

3

= { < 1 , 2 > , < 2 , 3 > , < 1 , 3 > , < 2 , 1 > }，

R4?{?1,1?,?1,2?,?3,2?,?2,3?,?3,3?}，

R5?IA?{?1,1?,?2,2?,?3,3?}，则

① R 1和R 2是传递的。

② 对于R 3，因为?1,2??R3,?2,1??R3 ，但?1,1??R3，（?2,2??R3），故R3不是传递的。

③ 对于R4由于2?A，但?2,2??R4故R4不是自反的，又1?A，而?1,1??R4，故R4不是反自反的，因此R4既不是自反的也不是反自反的。

④ R5在A上既是对称的又是反对称的。

例2-2-2.15 设兄弟三人组成一个集合A = { a , b , c } ，在A上的兄弟关系R的性质为： 性质 关系 兄弟关系 自反性 否 对称性 是 传递性 否 反自反性 是 反对称性 否 注意：兄弟关系不具有反自反性，是因为自己与自己不构成兄弟关系；

兄弟关系不具有传递性，是因为如果?a,b??R，由对称性知?b,a??R，但

?a,a??R；兄弟关系不具有反对称性，是因为?a,b??R且?b,a??R，但a?b。

例2-2-2.16 设集合A = { 1 , 2 , 3 , 4 }，A上的二元关系

R = {<1 , 1> , <1 , 3> , <2 , 2> , <3 , 3> , <3 , 1> , <3 , 4> , <4 , 3> , <4 , 4>}，讨论R的性质。

解： 性质 关系

自反性 对称性 102

传递性 反自反性 反对称性 R 是 是 否 否 否 注意：关系R不具有传递性，是因为?1,3??R,?3,4??R，但是?1,4??R。 关系R不具有反自反性，是因为?1,1??R。

关系R不具有反对称性，是因为?1,3??R,?3,1??R，但 1?3。 3、关系性质在关系图及关系矩阵中的特征

R性质 R表示 集合表示 自反性 对称性 R?Rc 传递性 R?R?R 2在MR中1所反自反性 反对称性 IA?R R?IA?? R?Rc?IA 矩阵表示 主对角线元矩阵为对称在位置，在主对角线如果rij=1且 素全是1 矩阵 MR中相应元素全是0 i≠j则rij=0 位置也为1 如果两个结每个结点都有环 点之间有边，一定是一对方向相反的边 如果结点xi到xj之间有如果两个结图表示 边，xj到xk每个结点点之间有之间有边，则都无环 xi到xk之间也有边 边，一点是一条有向边 传递关系的特征比较复杂，不易从关系矩阵和关系图中直接判断。

五、关系的闭包运算

在§2-2-2的例子告诉我们，集合上的二元关系可能具有一种或多种性质，如整数集上的整除关系，实数集上的“≤”关系都同时具有自反性、反对称性和传递性，但实数集上的“<”关系就不具有自反性。自然想到能否通过一定的方法使这个关系具有自反性呢？一般来说，是否有方法使给定的关系具有所希望的性质呢？本节就来研究这个问题。

1、闭包的定义

103

定义2-2-2.6 设R是集合A上的二元关系，如果有另一个关系R?满足下列条件： （1）R?是自反的（或对称的，或传递的）， （2）R?R?，

（3）若还有A上的二元关系R??也符合条件（1）和（2），则必有R??R??，则分别称R?为R的自反闭包，对称闭包和传递闭包，分别记为r(R)，s(R)，t(R)。

由闭包定义可知，R?是包含R且具有自反性或对称性或传递性的最小关系。 2、关系R的闭包求法

定理2-2-2.6 设R是集合A上的二元关系，则 （1） R是自反的当且仅当r(R)?R； （2） R是对称的当且仅当s(R)?R； （3） R是传递的当且仅当t(R)?R。 证明：（1）必要性证明，

若R是自反的，令R??R则R?是自反的且R?R?。对任意R??，若R??是自反的且

R???R则有R???R?(?R)。故R??R就是R的自反闭包，即 r(R)?R。

充分性的证明，若r(R)?R，则由r(R)具有自反性知R是自反关系。 同理可证（2），（3）。 ﹟ 定理2-2-2.7 设R是集合A上的二元关系，则 （1） r(R)?R?IA； （2） s(R)?R?Rc；

（3） t(R)?R?R?R?????Ri??R?

23i?1?证明：（1）令R??R?IA，显然 R??R，?x?A??x,x??IA?R?IA?R?，所以，R?具有自反性。设R??包含R且具有自反性的任一关系，即R???R且R???IA，因此R???R?IA?R?，由定义即知r(R)?R?IA。

（2）令R??R?Rc，显然R??R，现证R?具有对称性，事实上：任意x,y?A

104

(?x,y??R??R?Rc)?(?x,y??R)?(?x,y??Rc)?(?y,x??Rc)?(?y,x??R)?(?y,x??R?Rc?R?) 设R??是包含R且具有对称性的关系，现证R???R?，事实上：对任意?x,y??R?

?x,y??R??R?Rc?(?x,y??R)?(?x,y?Rc)?(?x,y??R)?(?y,x??R)R???R?(?x,y??R??)?(?y,x??R??)??x,y??R??R??对称

所以，s(R)?R?Rc。

（3）为证明?R?t(R)，① 证明?Ri?t(R)。

ii?1i?1??对任意自然数i用数学归纳法证明Ri?t(R)。 当i = 1时，由传递闭包的定义即知R?t(R)。 假设i = k时，Rk?t(R)成立。 当i = k +1时，

?x,y??Rk?1?Rk?1?R??z((z?A)?(?x,z??Rk?1)?(?z,y??R))??z((z?A)?(?x,z??t(R))?(?z,y??t(R)))?即说明 Rk?1t(R)传递性

?x,y??t(R)i? ?t(R)。由归纳原理知，任意自然数i，R?t(R)，因此?Ri?t(R)。

i?1② t(R)??Ri。

i?1?因为R??R，现证明?Ri具有传递性，对任意?x,y?，?y,z?

ii?1i?1??(?x,y???R)?(?y,z???Ri)ii?1i?1????m?n((m?N)?(n?N)?(?x,y??Rm)?(?y,z??Rn)) ??x,z??R?R?Rmnm?n??Rii?1??Ri?1?i具有传递性，而t(R)是包含R具有传递性的最小关系，所以，t(R)??Ri。

i?1??由①和②即知t(R)??Ri??R?。 ﹟

i?1例2-2-2.17 设集合A?{1,2,3}，A上的二元关系R?{?1,2?,?2,3?,?3,1?}，则

105

r(R)?R?IA?{?1,1?,?1,2?,?2,2?,?2,3?,?3,1?,?3,3?}；

s(R)?R?Rc?{?1,2?,?2,1?,?2,3?,?3,2?,?3,1?,?1,3?}； 由于R2?{?1,3?,?2,1?,?3,2?}，R3?{?1,1?,?2,2?,?3,3?}，

R4?R,R5?R2,?

一般有R3n?1?R,R3n?2?R2,R3n?R3故 t(R)??Ri?R?R2?R3?A?A。

i?1?(n?1,2,?)

在计算Ri时，一般来说是较麻烦的，但是可以发现有一定的规律，也即存在着求t(R)的简单的方法。

定理2-2-2.8 设R是集合A上的二元关系，A?n，则存在正整数k ，k?n使得

t(R)?R?R2???Rk。 证明：R?t(R)??Ri。

?i?1?对任意x,y?A，若?x,y??R?，故存在最小正整数k使?x,y??Rk，即存在A的元素序列a1,a2,?,ak?1使?x,a1??R,?a1,a2??R,?,?ak?1,y??R。

若k?n，则a1,a2,?,ak?1,y这k个元素中至少有两个相同，即有

① 某个i?k?1使ai?y，于是有?x,a1??R,?x,a2??R,?,?ai?1,y??R故

?x,y??Ri，且i?k；

② 某 i?j,i,j?k使ai?aj，于是有

?x,a1??R,?,?ai?1,ai??R,?ai,aj?1??R,?,?ak?1,y??R。因此，

?x,ai??Ri，?ai,y??Rk?j，即?x,y??Ri?k?j，而i?k?j?k?(j?i)?k。 无论是①还是②都与?x,y??Rk时k的最小性矛盾，所以k?n。

即?x,y??R时，必有k?n，?x,y??R，故R?t(R)??Ri，k?n。 ﹟

?k?i?1k例2-2-2.18 用关系矩阵求复合关系的方法，求例2.4.1中的R?。

106

?010??010??010??001?????????M?001M?MM?001001?100解：R??，R2??????， RR?100??100??010??100?????????MR3?001??010??100????????MR2MR??100??001???010?。

?010??100??001????????010??001??100??111???????????001???100???010???111?， ?100??010??001??111?????????于是MR??MR?MR2?MR3故R??A?A。

传递闭包的Warshall算法：

前面已经看到按复合关系定义求Ri是麻烦的，即使对有限集合采用定理2.4.2的方法仍是比较麻烦的，特别当有限集合元素比较多时计算量是很大的。1962年Warshall提出了一个求R?的有效计算方法：设R是n个元素集合上的二元关系，MR是R的关系矩阵，

第一步：置新矩阵M，M?MR； 第二步：置i，i?1；

第三步：对j(1?j?n)，若M的第j行i列处为1，则对k?1,2,?,n作如下计算： 将M的第j行第k列元素与第i行第k列元素进行逻辑加，然后将结果送到第j行k列处，即 M[j,k]?M[j,k]?M[i,k]； 第四步：i?i?1；

第五步：若i?n，转到第三步，否则停止。

Warshall算法为计算机解决集合分类问题奠定了基础。

例2-2-2.19 设A = { 1 , 2 , 3 , 4 , 5 } , R = { < 1 , 1 > , < 1 , 2 > , < 2 , 4 > , < 3 , 5 > , < 4 , 2 > }，

用Warshall方法求R?。

107

?1??0解：MR??0??0?0?1000??0010?0001?， M?MR，

?1000?0000??i?1。i = 1时，M的第一列中只有M[1 , 1] = 1，将M的第一行上元素与其本身作逻辑

和，然后把结果送到第一行，得：

?1??0M??0??0?0?1000??0010?0001?，

?1000?0000??i?1?1。i?2时，M的第二列中有两个1，即M[1,2]?M[4,2]?1，分别将M的第一

行和第四行与第二行对应元素作逻辑和，将结果分别送到第一行和第四行，得

?1??0M??0??0?0?1010??0010?0001?。

?1010?0000??i?2?1。i?3时，M的第三列全为0，M不变。

i?3?1。i?4时，M的第四列中有三个1，即M[1,4]?M[2,4]?M[4,4]?1，分别将

M的第一行，第二行，第四行与第四行对应元素作逻辑和，将结果分别送到M的第一、二、四行得

?1??0M??0??0?0?1010??1010?0001?。

?1010?0000??i?4?1。i?5时，M[3,5]?1，将M的第三行与第五行对应元素作逻辑和送到M的

第三行，由于这里第五行全为0，故M不变。

i?5?1，这时i?6?5，停止。即得

108

MR??1??0??0??0?0?1010??1010?0001?

?1010?0000??故 R??{?1,1?,?1,2?,?1,4?,?2,2?,?2,4?,?3,5?,?4,2?,?4,4?}。

3、闭包的复合

关系R的自反（对称，传递）闭包还可以进一步复合而成自反（对称，传递）等闭包，它们之间有如下定理。

定理2-2-2.9 设R1,R2是集合A上的两个二元关系，且R1?R2，则 （1）r(R1)?r(R2)；（2）s(R1)?s(R2)；（3）t(R1)?t(R2)。 证明： （1）r(R1)?R1?IA?R2?IA?r(R2)，即 r(R1)?r(R2)。

cc （2）?R1?R2，?R1c?R2，则有s(R1)?R1?R1c?R2?R2?s(R2)

即s(R1)?s(R2)。

（3）任意?x,y??t(R1)??R1i，则存在正整数s ，使得?x,y??R1s，

i?1?因此存在e1,e2,?,es?1?A，使得?x,e1??R1,?e1,e2??R1,?,?es?1,y??R1，由

s，所以R1?R2，则有?x,e1??R2,?e1,e2??R2,?,?es?1,y??R2，即?x,y??R2?i?x,y???R2?t(R2)，这说明t(R1)?t(R2)。

i?1定理2-2-2.10 设R是集合A上的二元关系， （1）若R是自反的，则s(R),t(R)是自反的； （2）若R是对称的，则r(R),t(R)是对称的； （3）若R是传递的，则r(R)是传递的。

证明：（1）因为R是自反的，所以?x?A，?x,x??R，由自反闭包和传递闭包的定义知，R?s(R)且R?t(R)，因此 ?x,x??s(R),?x,x??t(R)。故s(R)和t(R)是自反的。

109

（2）首先证明r(R)是对称的。

?x,y?A，若?x,y??r(R)?R?IA，即?x,y??R或?x,y??IA，

① 若?x,y??R，由R的对称性知?y,x??R，又因为R?r(R)，有?y,x??r(R)，所以r(R)是对称的；

② 若?x,y??IA，则x?y，由于r(R)是自反闭包，所以?y,x??r(R)； 由①，②知：若?x,y??r(R)就有?y,x??r(R)，所以r(R)是对称的。

再证明t(R)是对称的

?x,y?A，若?x,y??t(R)??Ri，则?s使得?x,y??Rs，即存在e1,e2,?,es?1使

i?1?得?x,e1??R,?e1,e2??R,?,?es?2,es?1??R,?es?1,y??R，由R的对称性知，

?y,es?1??R,?es?1,es?2??R,?,?e2,e1??R,?e1,x??R，即?y,x??R??Ri，

si?1?所以?y,x???Ri?t(R)，说明t(R)具有对称性。

i?1?（3）?a,b,c?A，若?a,b??r(R)?R?IA,?b,c??r(R)?R?IA，

① 若?a,b??R,?b,c??R，由R的传递性知?a,c??R?r(R)，即

?a,c??r(R)，所以r(R)具有传递性。

② 若?a,b??R,?b,c??IA，有b?c，即?a,c??R?r(R)，所以r(R)具有传递性。

③ ?a,b??IA,?b,c??R，有a?b，即?a,c??R?r(R)，所以r(R)具有传递性。

④ ?a,b??IA,?b,c??IA，有a?b?c，即?a,c??R?r(R)，所以r(R)具有传递性。

综上所述，r(R)具有传递性。 ＃ 定理2-2-2.11 设X是集合，R是X上的二元关系，则

110

（1）rs(R)?sr(R)； （2）rt(R)?tr(R)； （3）st(R)?ts(R)。

证明：令IX表示X上的恒等关系。

c（1）sr(R)?s(IX?R)?(IX?R)?(IX?R)c?(IX?R)?(IX?Rc)

?IX?R?Rc?IX?s(R)?r(s(R))?rs(R)

（2）tr(R)?t(IX?R)??(IX?R)??(IX??R)?IX???Rj

iji?1i?1j?1i?1j?1??i?i?IX??Ri?IX?t(R)?rt(R)

i?1?st(R)?sts(R)，（3）因为R?s(R)，由定理2-2-2.9知t(R)?ts(R)，再由定理2-2-2.10

知ts(R)具有对称性，所以sts(R)?ts(R)，即st(R)?ts(R)。

§2-2-3 等价关系与集合的划分

在对集合的研究中，有时需要将一个集合分成若干个子集加以讨论。 一、集合的划分

定义 2-2-3.1 设集合A??，S={A1,A2,?,Am}，其中A1,A2,?,Am都是A的子集， 若(1) 当 i?j, i,j = 1,2,?,m时，Ai ? Aj = ?；(2) 则称S为A的一个划分（分类，分划）。 例如，A={a,b,c}，考虑下列子集：

P={{a},{b,c}}，Q={{a,b,c}}，R={{a},{b},{c}}，S={{a,b},{b,c}}，T={{a},{a,c}} 由定义2-2-3.1知，P,Q,R都是集合A的划分，而S,T不是集合A的划分。分划Q中的元素是由集合A的全部元素组成的一个分块（A的子集），则称Q为集合A的最小划分。分划R是由集合A中每个元素构成一个单元素分块（A的子集），组成的分划，称R为集合A的最大分划。

需要注意：集合的分划不是唯一的，但已知一个集合却很容易构造出一种划分。 定义2-2-3.2 设A={A1,A2,?,Am}与B={B1,B2,?,Bn}是集合X的两个不同的划分，

111

?Ai?1mi?A。

称S={Ai ? Bj ?(Ai?A)? (Bj?B) ?(Ai?Bj??, i=1,2,?,m;j=1,2,?,n)}为A与B的交叉划分。

例如，设X表示所有生物的集合。A={A1,A2}，其中A1表示所有植物的集合，A2表示所有动物的集合，则A是集合X的一种分划；B={B1,B2}，其中B1表示史前生物，B2表示史后生物，则B也是集合X的一种划分。

A , B的交叉划分S={A1 ? B1 , A1 ? B2 , A2 ? B1 , A2 ? B2}，其中A1 ? B1表示史前植物，A1 ? B2表示史后植物，A2 ? B1表示史前动物，A2 ? B2表示史后动物。

定理 2-2-3.1 设A={A1,A2,?,Am}与B={B1,B2,?,Bn}是集合X的两个不同的划分， 则A，B的交叉划分是集合X的一种划分。 证明： A，B的交叉划分

S={A1?B1 , A1?B2 , ?, A1?Bn ,

A2?B1, A2?B2,?, A2?Bn ,?, Am?B1 , Am?B2 , ?, Am?Bn}

(1) S中任意两个元素都不相交

任取S中两个元素Ai ? Bh , Aj ? Bk ，(Ai ? Bh ) ?( Aj ? Bk)有三种情况： ① 若i?j , h=k , 因为Ai ? Aj = ?，所以 (Ai ? Bh ) ?( Aj ? Bk) = ? ? Bh ? Bk = ?。 ② 若i = j , h ? k ,因为 Bh ? Bk = ?，所以

(Ai ? Bh ) ?( Aj ? Bk) = ? ? Ai ? Aj = ?。

③ 若i ? j , h ? k，因为Ai ? Aj = ?，Bh ? Bk = ?，所以

(Ai ? Bh ) ?( Aj ? Bk) = ? ? ? = ?。 综上所述，在交叉划分中，任取两元素，其交为 (Ai ? Bh ) ?( Aj ? Bk) = ? (2) 交叉划分中所有元素的并等于X

(A1?B1) ? (A1?B2) ? ?? (A1?Bn ) ? (A2?B1) ? (A2?B2) ??? (A2?Bn) ??? (Am?B1 ) ? (Am?B2) ? ?? (Am?Bn)

= (A1? (B1?B2???Bn)) ?(A2?( B1?B2???Bn))

???(Am ? (B1?B2???Bn))

= (A1? X) ?(A2?X) ???(Am ?X) = (A1?A2???Am) ?X = X ?X = X。

112

定义 2-2-3.3 给定集合X的任意两个划分A={A1,A2,?,Am}与B={B1,B2,?,Bn}，若对每个Ai均有Bj使得Ai ? Bj，则称分划A为分划B的加细。

定理 2-2-3.2 任何两种分划的交叉分划都是原各分划的一种加细。 由交叉分划的定义和集合交的性质，容易证明定理成立。 二、等价关系与等价类

定义 2-2-3.4 设集合A上的二元关系R，同时具有自反性、对称性和传递性，则称R是A上的等价关系。

例 2-2-3.1 设Z为整数集，k是Z中任意固定的正整数，定义Z上的二元关系R为：任一a，b?Z，?R的充要条件是a，b被k除余数相同，即k整除a-b，亦即a-b=kq，其中q?Z。即R={?(a?Z)?(c?Z) (q?Z)?(a-b=kq)}，则R是Z上的等价关系。

证明：(1) R是Z上自反关系。?a?Z，因为a-a=k?0，0?Z，所以?R。 (2) R是Z上对称关系。如果 ?R，则a-b=kq (q?Z)，故b - a =k(-q) (-q?Z),于是?R。

(3) R是Z上对称关系。如果 ?R且 ?R，则a-b=kq1，b-c=kq2，

(其中q1， q2 ?Z)，故a-c=(a-b)+(b-c)=k(q1+q2)，(q1+q2 ?Z)，因此， ?R。

所以，R是Z上的等价关系，称为Z上的模k等价关系。 例 2-2-3.2 设A={0,1,2,3,5,6,8}，R为Z上的模3等价关系，则 R={<0,0>,<1,1>,<2,2>,<3,3>,<5,5>,<6,6>,<8,8>,<0,3>,<3,0>,<0,6>,

<6,0>,<2,5>,<5,2>,<2,8>,<8,2>,<3,6>,<6,3>,<5,8>,<8,5>}，R的关系图见图2-2-3.1。

3 5 0 6 图2-2-3.1

2 8

定义 2-2-3.5 设R是集合A上的等价关系，A??，对每一a?A，A的子集 {x ? (x?A)?(?R)}

称为R的一个等价类。记为[a]R，称为由元素a产生的R等价类。在不因起混淆时简记为[a]。

由于等价关系是自反的，显然a?[a]，故等价类是A的非空子集。 例 2-2-3.3 当k=3时，例 2-2-3.1中的模3的等价关系的等价类有：

113

[0]={?,-6,-3,0,3,6,?}, [1]={?,-5,-2,1,4,7,?}， [2]={?,-4,-1,2,5,8,?}。 在例 2-2-3.2中模3的等价类有：

[0]={0,3,6}，[1]={1}，[2]={2,5,8}。显然，[0]=[3]=[6]，[2]=[5]=[8]。

定理2-2-3.1 设R是集合A上的等价关系，则(1)对任意a,b∈A，或者[a]=[b]或者 [a]?[b]=?；(2) ?[a]?A。

a?A证明：若A=?，则R为空关系，决定的等价类也是?，结论显然成立。下面设A??非空。

(1) 任意给定a,b?A，若[a]?[b]=?，则已得证。若[a]?[b]??，则存在A的元素 x?[a] ? [b] ，于是x?[a]且x?[b]，故有xRa且xRb，R是对称的，故aRx且xRb，又R是传递的，故aRb。因此，任一y?[a]必有yRa，而aRb，故yRb，即y?[b]，因此得到[a]?[b]。同理可证[b]?[a]。

(2) ?[a]?A显然。

a?A定理2-2-3.2 设R是集合A上的等价关系，对于a , b?A，则

aRb当且仅当 [a]R=[b]R 。 证明：必要性。若aRb，任意c?[a]R 则

aRc ? cRa(R的对称性) ? cRb (已知aRb和R的传递性) ? c?[b]R 所以，[a]R ? [b]R。 反之，若任意c?[b]R ，则

bRc ? cRb(R的对称性) ? cRa (已知aRb，由R的对称性有bRa，结合R的传递性) ? c?[a]R，所以，[b]R ? [a]R。即有 [a]R=[b]R。 充分性。若[a]R=[b]R，因为a ?[a]R ? a ?[b]R ? aRb 。

定义 2-2-3.5 设R为集合X上的等价关系，称等价类集合{[a]R ?a?X}为X关于R的商集，记作 X/R。

例如，例 2-2-3.3中的商集Z/R = {[0]R , [1]R , [2]R}。 注意到定理2-2-3.1和定理2-2-3.2的结论，我们有

定理 2-2-3.3 集合X上的等价关系R，决定了X的一个划分，该划分就是商集X/R。 证明：设R为集合A上的等价关系，a为集合A中的某固定元素，把与a有等价关系的元素放在一起构成一个子集，该子集就是有a产生的等价类[a]R，所有这样的子

114

集就构成商集X/R。

下面证明商集X/R就是X的一个分划。 (1) 在X/R＝{[x]R?x ?X}中，?[x]R?X。

x?X(2) ?x?X，由于R具有自反性，必有 xRx，即x?[x]R，因此，X中的每一个元素确属于一个分块。

(3) A的每个元素只能属于一个块。

反证，若a? [b]R，a? [c]R，且[b]R ? [c]R，则 bRa，cRa，由对称性可知，aRc，再由传递性知，bRc，由定理2-2-3.2必有[b]R = [c]R，这与题设矛盾。

故X/R是X上的一个划分。

定理 2-2-3.4 集合X上的一个划分确定X中元素间的一种等价关系。 证明：设S = {S1 , S2 ,?, S m}是集合X的一个划分，定义X上一个关系 R={ ? a,b 同属于一个分块}，下面证明R是X上的一个等价关系。 (1) R是自反的。?a?X 因为 a与a在同一分块中，所以?a,a??R。

(2) R是对称的。若?a,b??R，即a , b在同一分块中，所以b, a 也在同一分块中，即?b,a??R。

(3) R是传递的。若?a,b??R,?b,c??R，即a , b在同一块，b , c也在同一块，由于Si?Sj??,i?j,i,j?1,2,?,m，所以a , c也在同一块内，即?a,c??R。

由R的定义知，S就是X/R。

定理 2-2-3.5 设R1与R2都是集合X上的等价关系，则 R1=R2当且仅当X/R1=X/R2。

证明：X/R1?{[x]R1x?X}，X/R2?{[x]R2x?X} 必要性，若R1=R2，对任意的a?X有

[a]R1?{xx?X,aR1x}?{xx?X,aR2x}?[a]R2

故，{[a]R1a?X}?{[a]R2a?X}，即X/R1=X/R2。

充分性，假设X/R1=X/R2，则对任意[a]R1?X/R1，必存在[c]R2?X/R2，使得

[a]R1?[c]R2，故

115

?a,b??R1?(a?[a]R1)?(b?[a]R1)?(a?[a]R2)?(b?[a]R2)??a,b?R2 所以，R1?R2，同理有，R2?R1。因此，R1?R2。

例 2-2-3.4 设X={a , b , c , d , e}，试求分划S={{a,b},{c},{d,e}}确定的等价关系。 解：用如下办法产生一个等价关系R：

R1={a , b}×{a , b}={ , , , } R2={c}×{c}={}

R3={d , e}×{d , e}={ , , , } R=R1×R2={ , , , , , ,

, , }。

§2-2-4 相容关系与集合的覆盖

定理 2-2-3.3，定理 2-2-3.4，定理 2-2-3.5说明了集合的分划与等价关系是紧密相关的，但等价关系的传递性是个较麻烦的问题，在实际问题中往往有些关系不具有传递性，例如朋友关系、父子关系等就不具有传递性，又如关系数据库中考虑元组运算时还要排除传递性。本节介绍一种应用广泛的新的关系－相容关系。

一、集合的覆盖

定义 2-2-4.1 设X是非空集合，S={S1 , S2 ,? , Sm}，其中Si都是X的非空子集，如果?Si?X，则称S是集合X的一个覆盖。

i?1m例 2-2-4.1 设X={1,2,3,4,5}，

则S1={{1} , {2 , 3} , {2 , 4 , 5}}，S2={{1} , {3 , 4} , {2 , 4 , 5}}等都是集合X的覆盖。

注意：覆盖不是划分，而划分一定是覆盖。 二、相容关系与相容类

定义 2-2-4.2 设R为集合X上的二元关系，如果R具有自反性和对称性，则称R为X上的相容关系。

例 2-2-4.2 设X={boy , girl , computer , artificial , intelligence}，

R={?x , y?X且x , y至少有一个相同的字母}

则R是X上的相容关系。

证明：简记X中的元素依次为1，2，3，4，5，则

R={<1 , 1> , <2 ,2> , <3 ,3> , <4 ,4> , <5 ,5> , <1 ,3> , <3 ,1> , <2 ,3> , <3 ,2> , <2 ,4> ,

116

<4 ,2> , <3 ,4> , <4 ,3> , <2 ,5> , <5 ,2> , <3 ,5> , <5 ,3> , <4 ,5> , <5 ,4> }

R的关系矩阵如下：

?1??0MR??1??0?0?0100??1111?1111?

?1111?1111??MR的左主对角线上全是1并且关于左主对角线是对称的，可见关系R是相容关系。 根据相容关系的关系矩阵共同特征，为了减少储存量，并使书写简化，可采用梯子形状标出左主对角线以下元素，也可以反映出相容关系的关系矩阵。

由于R的关系图上每一点都有指向自身的弧，可以略去不画，R又具有对称性，因此两点之间如果有一点指向另一点的弧，必有方向相反的另一弧存在，此时就简化为一条无箭头的1 边，故相容关系的简化关系图就表现为，无自身回路的五向图，见图2-2-4.1。

定义 2-2-4.3 设R是集合X上的相容关系，C是X的非空子集，如果?a,b?C都有aRb，则称C是由R产生的相容类。

例如，例2-2-4.2中的相容关系R产生的相容类为： {1}，{2,3,4,5}，{2,3}，{3,4}，{4,5}，{2,4,5}等 易知，X={1}?{2,3,4,5}，X={1}?{2,4,5}?{3,4}。

可见{{1},{2,3,4,5}}和{{1}，{2,4,5}，{3,4}}等都是集合X的覆盖，因此由R产生的覆盖并不唯一，反过来可知，几个不同的覆盖可以决定一个相容关系。

另外，相容类{2,3}，{2,4,5}，{3,4}等还可以加入与类中元素符合相容关系的其它元素构成新的相容类，如，{2,3}可以加入元素4或5；{2,4,5}可以加入元素3；{3,4}可以加入元素2或5。但是C的相容类{1 , 3} , {2 , 3 , 4 , 5}就不能再添加元素构成新的相容类了。

定义 2-2-4.4 设R是集合X上相容关系，C是由R产生的相容类，如果C不能真包含在其它任何相容类中，则称C为R的最大相容类。记为CR , max。

我们知道，关系图中两点x,y之间右边相联，表明xRy，而最大相容类中的每两点都有边相联，其它的点均不与这些点有边相联，因此，最大相容类中的元素在关系图中

117

0

1 1 0 1 1 0 1 1 1

5 4 2 图2-2-4.1

3 形成一个点或者一条边或者一个最大完全多边形。所谓完全多边形就是其每个顶点都与其它顶点连接的多边形。

例 2-2-4.3 设给定的相容关系图为图2-2-4.2，求它的最大相容类。

解：最大相容类为：

{a1 , a2 , a4 , a6}，{a3 , a4 , a6}，{a4 , a5}，{a7}。 定理 2-2-4.1 设R是有限集合A上的相容关系，C是一个相容类，则存在一个最大相容类CR , max，使得C?CR , max。

证明：设A={ a1 , a2 , ?,an }，构造相容类序列

C0 ? C1 ? C2 ? ?,其中C0=C

且Ci?1?Ci?{aj}，其中j是满足aj?Ci，aj与Ci中各元素都有相容关系的最小足标元素。

由于A中元素个数?A?=n，所以至多经过n-?C?步，就使这个过程终止，而此序列的最后一个相容类就是包含相容类C的最大相容类。

A中任一元素a，它可以组成相容类{a}，从定理2-2-4.1可知，{a}必包含在一个最大相容类CR , max之中，因此所有最大相容类组成的集合必是A的覆盖。

定义 2-2-4.5 设R是集合A上的相容关系，R的所有最大相容类组成的集合称为A的完全覆盖。记作CR(A)。

集合A的覆盖不唯一，因此给定相容关系R，可以作成不同的相容类集合，它们都是集合A的覆盖。但是给定相容关系R，只能对应唯一的完全覆盖。如例 2-2-4.3中A上的相容关系，有唯一的完全覆盖：{{a1 , a2 , a4 , a6}，{a3 , a4 , a6}，{a4 , a5}，{a7}}。

定理 2-2-4.2 设C={C1 , C2 ,? , Cr}是集合A的覆盖，由C决定的关系

R=(C1×C1)?(C2×C2)???(Cr×Cr)是A的一个相容关系。

证明：(1) R的自反性。因为A=C1?C2 ??? Cr，故对任一a?A，必有i使a?Ci，则?a,a??Ci?Ci?R。

(2) ?x,y?A,若?x,y??R，由R=(C1×C1)?(C2×C2)???(Cr×Cr)知，?Ci使

a4 a6 a7 图2-2-4.2 a5 a3 a2 a1

?x,y??Ci?Ci(i?1,2,?,r)，即x,y?Ci，则?y,x??Ci?Ci?R，即R是对称的。 因此，R是A上的相容关系。

118