第 3章 集合第 3章 集合
3.1 集合的基本概念
3.2 集合的运算
3.3 集合恒等式
3.4 集合的覆盖与划分
3.5 笛卡尔积返回总目录第 3章 集合第 3章 集 合
3.1集合的基本概念一些确定的、能区分的对象的全体是集合，通常用大写的英文字母表示。组成集合的对象叫做集合的元素或成员，常用小写的英文字母表示。
集合的元素必须是确定的。所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。
集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。例如集合?1,2,3,3?和?1,2,3?是同一集合。
第 3章 集合集合的元素是任意的对象，对象是可以独立存在的具体的或抽象的客体。它可以是独立存在的数、字母、人或其它物体，也可以是抽象的概念，当然也可以是集合。例如集合
1,2,?3?,?1,2的元素?3?和?1,2?就是集合。
集合的元素又是无序的，即?1,2,3?和?3,1,2?是同一集合。
设 S是集合,a是 S的一个元素，记为 a?S，读做,a属于
S”,也可读做,a在 S中,。如果 a不是 S的元素，记为 a?S，
读做,a不属于 S,,也可读做,a不在 S中,。
例如：
① 26个英文字母组成一个集合，任一英文字母是该集合的元素。
②直线上的所有点组成实数集合 R，每一个实数是集合 R
的元素。
③陕西科技大学全体学生组成一个集合，该校的每一个学生是这个集合的元素。
第 3章 集合
3.1.1集合的表示法集合有三种表示法。
第一种表示法是列举法：在花括号,” 中列举出该集合的元素，元素之间用逗号隔开。
例如：
I5=?1,2,3,4,5?
I+=?1,2,3,
I =?0,1,-1,2,-2,
S=?T,F?
第二种表示法是描述法：用谓词界定集合的元素。
例如：
Q=?x | x是有理数?
R=?x | x是实数?
C=?x | x是复数?
A=?x | x?I∧ 0＜ x∧ x＜ 5?
第 3章 集合若用 P(x)表示 x是有理数，那么 Q又可表示为：
Q=?x | P(x)?
一般地说，集合可用描述法表示为：
S=?x | A(x)? 其中,A(x)是谓词显然，当 a?S 时，则 A(a)为真；反之，当 A(a)为真，则
a?S。即 a?S的充分必要条件是 A(a)为真。
在中学的教科书中将自然数定义为：
N=?1,2,3,
这是对的。在离散数学中，认为自然数是由 0 开始的，即
N=?0,1,2,3,
我们把这种由 0 开始的自然数集叫做扩展的自然数集。
离散数学中使用扩展的自然数集。本书的自然数集是指扩展的自然数集。
第 3章 集合具有有限个元素的集合叫有限集，否则叫无限集。有限集元素的个数称为该集合的基数，也叫集合的势。有限集 A的基数记为 |A|。
例如：设 A=?a,b,c?,A 是有限集,A的基数 |A|=3。
无限集也有基数的概念。无限集的基数比有限集的基数要复杂的多，本书将在 5.3节中介绍。
扩展的自然数集 N=?0,1,2,3,是无限集。整数集合 I、
有理数集合 Q、实数集合 R和复数集合 C都是常见的无限集。
第 3章 集合
3.1.2子集和集合的相等定义 3.1.1 设 A,B是任意的集合，当 A的每一元素都是 B的元素时，则称 A是 B的子集，也称 A包含在 B内或 B包含 A。记为 A?B或 B?A。
当 A不是 B的子集时，记为 A?B。
A?B用谓词公式表示为,A?B?(?x)(x?A→ x?B)
A?B用谓词公式表示为,A?B?(?x)(x?A∧ x?B)
例如：设 A=?1?,B=?1,2?,C=?1,2,3?则
A?A
A?B,B?C,A?C
C?B
可以证明，集合的包含有下列性质：
①自反性。即对任意集合 A,A?A。
② 传递性。即对任意集合 A,B,C，当 A?B和 B?C
时,A?C。
第 3章 集合定义 3.1.2 设 A,B是集合，如果 A?B且 B?A，则称 A
与 B相等。记为 A=B。如果 A与 B不相等，记为 A≠B。
集合相等也可用谓词公式表示为：
A=B?A?B∧ B?A
(?x)(x?A→ x?B)∧ (?x)(x?B→ x?A)
(?x)(x?A? x?B)
例如：设 A=?1,2?,B=?1,?2,C=?2,1? 则
A=C,A≠B
由集合相等的定义可以看出，集合相等有下列性质：
①自反性,即对任意集合 A,A=A。
②对称性,即对任意集合 A,B，当 A=B时,B=A。
③传递性,即对任意集合 A,B,C，当 A=B和 B=C时，
A=C。
第 3章 集合定义 3.1.3 设 A,B是集合，如果 A?B且 A≠B，则称 A是
B的真子集。记为 A?B。如果 A不是 B的真子集，记为 A?B。
真子集用谓词公式表示为：
A?B?A?B∧ A≠B
(?x)(x?A→ x?B)∧ (?x)(x?B∧ x?A)
例如：设 A=?a?,B=?a,b?,C=?a,b,c?则
A?B,B?C,A?C
A?A
又如，自然数集是整数集合的真子集，也是有理数集合和实数集合的真子集，即 N?I,N?Q,N?R。
第 3章 集合定义 3.1.4 不包含任何元素的集合叫空集。记为?。
空集可以表示为：
=?x | P(x)∧?P(x)? 其中,P(x)为任意谓词空集?是不包含任何元素的集合，所以,|?|=0。
定理 3.1.1 空集是任意集合的子集。
证明,设 A是任意集合。对任意对象 x，由空集的定义知,x为假，由条件联结词的定义知,x→ x?A为真。
根据全称推广规则有
(?x)( x→ x?A)
为真，故A
第 3章 集合根据定理 3.1.1，空集是任意集合的子集，即A；对任意集合 A,A?A。一般地说，任意集合 A至少有两个子集，一个是空集?，另一个是它本身 A。
推论 空集是惟一的。
证明,设有两个空集?1和?2，由定理 3.1.1有?12
和?21，根据集合相等的定义知,?1=?2。
第 3章 集合
3.1.3幂集合定义 3.1.5 设 A是集合,A的所有子集构成的集合称为
A的幂集合，记为 P (A)，即
P (A) =?S | S?A?
【 例 3.1】 设 A=?a,b,c?,?是空集，试求
P (A),P (P (?))。
解,P (A)=,?a?,?b?,?c?,?a,b?,?a,c?,?b,c?,?a,b,c
P (?)=
P (P (?)) =,
第 3章 集合定理 3.1.2 设 A为有限集合，则 |P (A)|=2|A|
证明,设 |A|=n,A的子集有：
不含元素的子集?一个，即 个。
含一个元素的子集 n个，即 个。
含两个元素的子集 个。
含 n个元素的子集 个。
|P (A)|= + +? + =2n=2|A|
在例 3.1中，
|A|=3,|P (A)|=8=23 =2|A|
|?|=0,|P (?)|=1=20 =2|?|
|P (?)|=1,| P (P (?))|=2=21 =2|P (?)|
0nC
1nC
2nC
nnC
0nC 1nC nnC
第 3章 集合定义 3.1.6 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集。记为 E。
全集是相对的，不同的问题有不同的全集。即使是同一问题也可以取不同的全集。
集合的另一种表示法是文氏图（ Venn Diagram）。人们常用文氏图描述集合运算和它们之间的关系。集合的文氏图画法如下：
用矩形表示全集 E，在矩形中画一些圆表示其它集合，不同的圆代表不同的集合。如果没有特别说明，任何两个圆彼此相交。例如,A?B的文氏图如图
3.1所示。
返回章目录第 3章 集合
3.2集合的运算定义 3.2.1 设 A,B是任意的集合，由 A中的元素或 B中的元素组成的集合，称为 A和 B的并集，记为 A∪ B。
A∪ B=?x |x?A∨ x?B?
并集的定义如图 3.2所示。
从并集的定义可以得到：
A?A∪ B,B?A∪ B
第 3章 集合定义 3.2.2 设 A,B是集合，由 A与 B的公共元素组成的集合，称为 A和 B的交集，记为 A∩B。
A∩B=?x |x?A∧ x?B?
交集的定义如图 3.3所示。
从交集的定义可以得到：
A∩B?A,A∩B?B
如果 A与 B无公共元素，即 A∩B=?，则称 A和 B是互不相交的。
例如，令 A=?a,b,c?,B=?d,e?，则 A∩B=?,A和 B是互不相交的。
第 3章 集合定义 3.2.3 设 A,B是集合，属于 A的而不属于 B的元素组成的集合，称为 B对于 A的补集，也叫 B对于 A的相对补集。记为 A-B。
A-B=?x |x?A∧ x?B?
相对补集定义如图 3.4所示。
例如，令 A=,,B=?，则
A-B=,-?=,
又如，令 C=?a?,D=?a,b?，则
C-D =?a?-?a,b?=?
C-C=?
第 3章 集合定义 3.2.4 设 A是集合,A对于全集 E的相对补集，称为 A的绝对补集，记为 ~A。
~A=E-A=?x |x?E∧ x?A?=?x | x?A?
~A的定义如图 3.5所示。
例如，令全集 E=?1,2,3,4?,A=?1,2,3?，则
~A=?1,2,3,4?-?1,2,3?=?4?
第 3章 集合
【 例 3.5】 设 A,B是任意的集合，求证,A-B= A∩(~B)
证明,x?A-B?x?A∧ x?B?x?A∧ x?~B? x?A∩~B
即 A-B?A∩~B。
x?A∩~B?x?A∧ x?~B?x?A∧ x?B?x?A-B
故 A∩~B?A-B
所以,A-B= A∩(~B)。
A-B=A∩(~B)是一个重要的公式，在集合的运算中经常用到，它的意义在于将相对补运算转换绝对补和交运算。
第 3章 集合定义 3.2.5 设 A,B是集合，由 A中元素或 B中元素，
但不是 A与 B的公共元素组成的集合，称为 A和 B的对称差，
记为 A B。
A B=?x |x?Ax?B?=(A∪ B)-(A∩B)
A B的定义如图 3.6所示。
例如，令 A=?1,2,3,4?，
B=?1,2,5,6?，则
A B=A∪ B-A∩B
=?1,2,3,4,5,6?-?1,2?
=?3,4,5,6?
第 3章 集合
【 例 3.7】 设 A,B是任意的集合，求证,
A B=(A-B)∪ (B-A)=(A∩~B)∪ (B∩~A)。
证明,先证 A B=(A-B)∪ (B-A)。
x?A B?x?Ax?B
(x?A∧?x?B)∨ (?x?A∧ x?B)
(x?A∧ x?B)∨ (x?A∧ x?B)
x?A-B∨ x?B-A
x?(A-B)∪ (B-A)
所以,A B=(A-B)∪ (B-A)。
再证 (A-B)∪ (B-A)=(A∩~B)∪ (B∩~A)。
由例 3.5很容易得到此结论。这里从略。
第 3章 集合利用例 3.7中的公式可以证明对称差 A B下列的性质。
设 A,B是任意的集合。
① A A=?
证明,A A=(A-A)∪ (A-A) ==?
② A? = A
证明,A?=(A-?)∪ (?-A)=A∪?=A
③ A E=~ A
证明,A E=(A-E)∪ (E-A)=?∪ ~ A=~ A
第 3章 集合为了使集合的表达式更加简洁，我们对集合运算的优先顺序规定如下：
绝对补的运算级别比其它的 4个运算高，先进行绝对补运算，再进行其它的 4个运算；其它的 4个运算的运算顺序由括号决定。
用文氏图不仅可以表示集合的运算和它们之间的关系，
而且还可以很方便地解决有限集合的计数问题。
第 3章 集合用文氏图解决有限集合的计数问题的方法是：
每一条性质定义一个集合，画一个圆表示这个集合。
如果没有特别说明，任何两个圆画成相交的。将已知集合的元素数填入表示该集合的区域内。通常从 n个集合的交集填起，根据计算的结果逐步将数字填入其它各空白区域内。
如果交集的值是未知的，可以设为 x。根据题目的条件，列出方程或方程组，求出所需的结果。
第 3章 集合
【 例 3.9】 某班有 50名学生，第一次考试中 26人成绩为优，第二次考试中 21人成绩为优，已知两次考试中都不为优的共 17人。问两次考试中都为优的有多少人？
解,设 A,B分别表示第一次和第二次考试中成绩为优的学生集合。画出文氏图，如图 3.7所示。首先填 A∩B
中的人数，这正是要求的，设为 x。 A-B中的人数是 26-x，
B-A中的人数是 21-x，分别填入对应的区域。并列出如下方程：
(26-x)＋ x＋ (21-x)＋ 17=50
解得,x=14
返回章目录第 3章 集合
3.3 集合恒等式为了方便，下面列出一些常用的集合恒等式。它们是集合运算的主要公式，描述了集合运算的一般规律。这些恒等式都可以用集合相等的定义证明，但由于篇幅的限制，只证明其中的一部分。
恒等式中 A,B,C是任意的集合。
1.双重否定律 ~ (~A)=A
2.交换律 A∪ B=B∪ A
A∩B=B∩A
A B= B A
第 3章 集合
3.结合律 A∪ (B∪ C)= (A∪ B)∪ C
A∩(B∩C)= (A∩B)∩C
(A B) C=A (B C)
4.分配律 A∪ (B∩C)= (A∪ B)∩(A∪ C)
A∩(B∪ C)= (A∩B)∪ (A∩C)
A∩(B C)= (A∩B) (A∩C)
5.德摩根律 ~ (A∩B)= ~A∪ ~B
~ (A∪ B)= ~A∩~B
6.幂等律 A∪ A=A
A∩A= A
第 3章 集合
7.吸收律 A∪ (A∩B )=A
A∩(A∪ B )=A
8.零 律 A∪ E= E
A∩?=?
9.同一律 A∪?=A
A∩E=A
10.排中律 A∪ ~A=E
11.矛盾律 A∩~A=?
第 3章 集合
12.其它算律 ~?=E
~E=?
A-(B∪ C)=(A-B)∩(A-C)
A-(B∩C)=(A-B)∪ (A-C)
A A=?
A?=A
A E=~ A
A-B=A∩~B
A-B=A-(A∩B)
第 3章 集合
【 例 3.11】 用命题定律中的合取对异或的分配律
p∧ (q r)?(p∧ q) (p∧ r)
证明集合恒等式,A∩(B C)=(A∩B) (A∩C)
证明,x?A∩(B C)
x?A∧ x?B C
x?A∧ (x?B x?C)
(x?A∧ x?B) (x?A∧ x?C) (合取对异或分配律 )
x?(A∩B) x?(A∩C)
x?(A∩B) (A∩C)
A∩(B C)?(A∩B) (A∩C)
第 3章 集合
x?(A∩B) (A∩C)
x?A∩B x?A∩C
(x?A∧ x?B) (x?A∧ x?C)
x?A∧ (x?B x?C) (合取对异或的分配律 )
x?A∧ x?B C
x?A∩(B C)
(A∩B) (A∩C)?A∩(B C)
所以 A∩(B C)= (A∩B) (A∩C)
第 3章 集合
【 例 3.12】 用命题定律中的吸收律 A∨ (A∧ B)?A和
A∧ (A∨ B)?A
证明集合恒等式：
⑴ A∩(A∪ B)=A ⑵ A∪ (A∩B)= A
证明,仅证明⑴，⑵可类似的证明。
x?A∩(A∪ B )?x?A∧ x?A∪ B?x?A∧ (x?A∨ x?B)
x?A (吸收律 )
A∩(A∪ B)?A
x?A?x?A∧ (x?A∨ x?B) (吸收律 )
x?A∧ x?A∪ B? x?A∩(A∪ B )
A?A∩(A∪ B)
所以 A∩(A∪ B)=A
第 3章 集合
【 例 3.13】 用命题定律 p p?0,0 p?p，
1 pp，证明集合恒等式：
⑴ A A=? ⑵ A? =A ⑶ A E=~ A
证明,⑴证明 A A=?
x?A A? x?A x?A?0?x 所以 A A=?
⑵ 证明 A?=A
x?A x?A x x?A 0? x?A 所以
A?=A
⑶ 证明 A E=~ A
x?A E?x?A x?E? x?A 1
x?A?x?A?x?~A
所以 A E=~ A
第 3章 集合
【 例 3.14】 用命题定律中的德摩根律?(A∨ B)A∧?B，
(A∧ B)A∨?B证明集合恒等式：
⑴ ~ (A∪ B)= ~A∩~B ⑵ ~ (A∩B)= ~A∪ ~B
证明,⑴先证 ~ (A∪ B)?~A∩~B
x?~(A∪ B)?x?A∪ Bx?A∪ B
(x?A∨ x?B )
x?A∧?x?B (德摩根律 )
x?A∧ x?B
x?~A∧ x?~B
x?~A∩~B
~(A∪ B)?~A∩~B
第 3章 集合再证 ~A∩~B?~(A∪ B)
x?~A∩~B?x?~A∧ x?~B
x?A∧ x?B
x?A∧?x?B
(x?A∨ x?B) (德摩根律 )
x?A∪ B
x?A∪ B
x?~ (A∪ B)
~A∩~B?~ (A∪ B)
所以 ~ (A∪ B)= ~A∩~B
类似地可证明⑵。
第 3章 集合
【 例 3.17】 设 A,B是任意集合，用已知的集合恒等式证明,A-B=A-(A∩B)
证明,A-B=A∩~B
=?∪ (A∩~B)
= (A∩~ A)∪ (A∩~B)
=A∩(~ A∪ ~B)
=A∩~ (A∩B)
=A-(A∩B)
由于并运算满足结合律，故约定以下的符号：
由于交运算满足结合律，故约定以下的符号：
n
n
i
i AAAA 21
1
n
n
i
i AAAA 21
1
第 3章 集合除以上的恒等式外，还有一些关于集合运算的重要结果。例如：
A∩B?A
A∩B?B
A?A∪ B
B?A∪ B
A-B?A
A B?A∪ B
A?B?A∪ B=B?A∩B=A?A-B=?
A B=A C?B=C
返回章目录第 3章 集合
3.4集合的覆盖与划分定义 3.4.1 设 A是非空集合,π=?S1,S2,?,Sm?，
Si≠?,i=1,?,m，且满足：
⑴?Si?π,Si?A
⑵ S1∪ S2∪? ∪ Sm = A
则称 π是 A的一个覆盖。
定义 3.4.2 设 A是非空集合,π=?S1,S2,?,Sm?，
Si≠?,i=1,?,m,π是 A的一个覆盖，满足 Si∩Sj=?,i≠j，
则称 π是 A的一个划分。称 Si,i=1,?,m，是 A的划分块。
定义中的,Si∩Sj=?,i≠j” 是指 π中的元素两两互不相交。
第 3章 集合
【 例 3.20】 设 A=?a,b,c?，以下是 A的子集构成的集合：
S=a,b?,?b,c
Q=a?,?a,b?,?a,c
D=a?,?b,c
G=a,b,c
E=a?,?b?,?c
F=a?,?a,c
试确定哪些集合是 A的覆盖？哪些集合是 A的划分？
哪些集合既不是覆盖，也不是划分？
解,S和 Q是 A的覆盖，但不是划分； D,G和 E是 A的覆盖，也是划分； F不是 A的覆盖，也不是划分。
第 3章 集合集合 G=a,b,c是单元素集，它有一个元素?a,b,c?。
对单元素集a,b,c，认为它的元素的并集就是?a,b,c?，
同时也认为它的元素是两两互不相交的。所以集合 G=
a,b,c是 A的划分。
在 A的所有划分中基数最大的划分叫做 A的最大划分，
基数最小的划分叫做 A的最小划分。在例 3.20中,E是 A的最大划分,G是 A的最小划分。
第 3章 集合
【 例 3.21】 设 A=?1,2,3?，试确定 A的所有划分。
解,有一个划分块的划分是,1,2,3
有两个划分块的划分是,1?,?2,3
2?,?1,3
3?,?1,2
有三个划分块的划分是,1?,?2?,?3
图 3.9是 A的所有划分的示意图。 (a)表示有一个划分块的划分1,2,3。 (b),(c)和 (d)表示有两个划分块的划分1?,?2,3,2?,?1,3和3?,?1,2。 (e) 表示有三个划分块的划分1?,?2?,?3。
第 3章 集合定理 3.4.1 设 A=?A1,A2,?,Ar?与 B=?B1,B2,?,
Bs?是 C的两种划分，则集合 X=?Ai∩Bj | i=1,?,r,j=1,?,s，
Ai∩Bj≠也是 C的划分。
证明,
⑴ 先证 Ai∩Bj?C
由 A,B是 C的划分知,Ai?C,Bj?C，所以 Ai∩Bj?C。
第 3章 集合
⑵ 再证,
(A1∩B1)∪ (A1∩B2)∪? ∪ (A1∩Bs)∪
(A2∩B1)∪ (A2∩B2)∪? ∪ (A2∩Bs)∪
(Ar∩B1)∪ (Ar∩B2)∪? ∪ (Ar∩Bs)
=(A1∩(B1∪ B2∪? ∪ Bs))∪?
∪ (Ar∩(B1∪ B2∪? ∪ Bs))
=(A1∪ A2∪? ∪ Ar)∩(B1∪ B2∪? ∪ Bs)
=C∩C
=C
CBA
r
i
s
j
ji?
)(
1 1
第 3章 集合
⑶ 最后证 X中的元素是两两互不相交的。
在 X中取任意两个不同元素,Ai∩Bh与 Aj∩Bk，分三种情况讨论：
①设 i≠j,h=k
(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)
=?∩(Bh∩Bk)=?
② 设 i≠j,h≠k
(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)
=?∩?=?
③ 设 i=j,h≠k
(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)
=(Ai∩Aj)∩?=?
第 3章 集合定义 3.4.3 定理 3.4.1中定义的集合 X叫做原来两种划分
A和 B的交叉划分。
定义 3.4.4 设 A=?A1,A2,?,Ar?与 B =?B1,B2,?,
Bs?是 C的两种划分，如果?Ai?A,?Bk?B，使得 Ai?Bk。
则称 A是 B的加细，也称 A是 B的细分。
定理 3.4.2 任何两种划分的交叉划分都是原来两种划分的一种加细。
证明,设 A=?A1,A2,?,Ar?与 B=?B1,B2,?,Bs?
是 C的两种划分。
X=?Ai∩Bj | i=1,?,r,j=1,?,s,Ai∩Bj≠是 A和 B的交叉划分。
因为 Ai∩Bj?Ai,Ai∩Bj?Bj，所以 X是 A的一种加细，也是 B的一种加细。
返回章目录第 3章 集合
3.5 笛卡尔积定义 3.5.1两个个体 x,y的有序序列，称为二重组，也称为有序对或序偶。记为?x,y?。 x,y分别叫做二重组的第一分量和第二分量。
所谓有序序列是指调换第一分量和第二分量位置后，
就和原来的含义不同了。
定义 3.5.2 设?x,y?与?a,b?是两个二重组，如果 x=a且
y=b，则称二重组?x,y?与?a,b?相等，记为?x,y?=?a,b?。
二重组?x,y?与?a,b?相等，用逻辑的方法表示为
(?x,y?=?a,b?)?(x=a)∧ (y=b)。
由定义可以看出，当 x≠y时,?x,y?≠?y,x?。
例如，平面上的点 P1=?2,1?和点 P2=?1,2?是两个不同的点，它们都是二重组。
第 3章 集合定义 3.5.3 二重组x1,x2,?,xn-1?,xn?叫做 n重组。记为
x1,x2,?,xn?,xi叫做该 n重组的第 i个分量 i=1,?,n。
由定义可看出：三重组?x1,x2,x3?定义为x1,x2?,x3?，
其中第一分量是二重组；四重组?x1,x2,x3,x4?定义为
x1,x2,x3?,x4?，其中第一分量是三重组； 。
根据三重组的定义，第一分量是二重组，第二分量是一个个体的序偶x1,x2?,x3?是 3重组。而第一分量是一个个体，第二分量是二重组的序偶?x1,?x2,x3不是三重组。
这个结论对任意的 n(n=3,4,5,? )重组也是对的。例如，
x1,x2,x3?,x4?是四重组，而?x1,?x2,x3,x4不是四重组；
x1,x2,x3,x4?,x5?是五重组，而?x1,?x2,x3,x4,x5不是五重组。? 。
第 3章 集合定义 3.5.4 设?x1,x2,?,xn?与?y1,y2,?,y n?是两个 n重组，
如果 xi=yi,i=1,?,n，则称这两个 n重组相等，记为
x1,x2,?,xn?=?y1,y2,?,y n?。
n重组?x1,x2,?,xn?与?y1,y2,?,y n?相等，用逻辑的方法表示为 (?x1,x2,?,xn?=?y1,y2,?,y n?)
(x1= y1)∧ (x2= y2)∧? ∧ (xn= yn)。
定义 3.5.5 设 A,B是集合，集合a,b?| a?A∧ b?B?叫做 A,B的笛卡尔积，也叫 A,B的叉乘积，直积。记为：
A× B。
如果 A,B都是有限集,|A|= n,|B|= m，根据排列组合原理,|A× B|=nm=|A||B|。
第 3章 集合
【 例 3.22】 设 A=?a,b?,B=?1,2,3?，
⑴试求 A× B和 B× A
⑵ 验证 |A× B|=|A||B|和 |B× A|=|B||A|
解,⑴求 A× B和 B× A
A× B=a,1?,?a,2?,?a,3?,?b,1?,?b,2?,?b,3
B× A=1,a?,?1,b?,?2,a?,?2,b?,?3,a?,?3,b
⑵ 验证 |A× B|=|A||B|和 |B× A|=|B||A|
|A× B|=6=2× 3=|A||B|
|B× A|=6=3× 2=|B||A|
第 3章 集合如果把 × 看成运算，笛卡尔积有以下的性质：
①设 A为任意的集合，则 A×? =?× A=?
② 一般地说,× 不满足交换律：即 A× B≠B× A。
在例 3.22中,A× B≠B× A
③ 一般地说,× 不满足结合律：
即 (A× B)× C≠A× (B× C)
第 3章 集合定理 3.5.1 设 A,B,C是集合，则
⑴ A× (B∪ C) =(A× B)∪ (A× C)
⑵ A× (B∩C) =(A× B)∩(A× C)
⑶ (A∪ B)× C =(A× C)∪ (B× C)
⑷ (A∩B)× C =(A× C)∩(B× C)
证明,仅证明⑴,可类似地证明⑵、⑶、⑷。
a,bA× (B∪ C)
a?A∧ b?B∪ C
a?A∧ ( b?B∨ b?C)
(a?A∧ b?B)∨ (a?A∧ b?C)
a,bA× B∨?a,bA× C
a,b(A× B)∪ (A× C)
故 A× (B∪ C)=(A× B)∪ (A× C)
第 3章 集合定理 3.5.2 设 A,B,C是集合,C≠?，则
⑴ A?B的充分必要条件是 A× C?B× C
⑵ A?B的充分必要条件是 C× A?C× B
证明,仅证明⑴,可类似地证明⑵。
设 A?B，下证 A× C? B× C
a,bA× C?a?A∧ b?C
a?B∧ b?C
a,bB× C
所以 A× C?B× C
设 A× C?B× C，下证 A?B
因为 C≠?，所以存在 b?C
a?A?a?A∧ b?Ca,bA× C
a,bB× C?a?B∧ b?C?a?B
所以 A?B
第 3章 集合定理 3.5.3 设 A,B,C,D是非空集合，则
A× B?C× D的充分必要条件是 A?C且 B?D。
证明,设 A× B?C× D,下证 A?C且 B?D
a?A∧ b?Ba,bA× B
a,bC× D
a?C∧ b?D
所以 A?C且 B?D
设 A?C且 B?D，下证 A× B?C× D
a,bA× B?a?A∧ b?B
a?C∧ b?D
a,bC× D
所以 A× B?C× D
第 3章 集合定义 3.5.6 叉乘积 A1× A2×? × An定义为
(A1× A2×? × An-1)× An，
即 A1× A2×? × An
=a1,a2,?,an?| a1?A1∧ a2?A2∧? ∧ an?An?
由定义可以看出：
当 n=3时,A1× A2× A3定义为 (A1× A2)× A3
A1× A2× A3=a1,a2,a3?| a1?A1∧ a 2?A2∧ a3?A3?
当 n=4时,A1× A2× A3× A4定义为 (A1× A2× A3)× A4
A1× A2× A3× A4
=a1,a2,a3,a4?| a1?A1∧ a2?A2∧ a3?A3∧ a4?A4?
约定 An=的叉乘积个 An AAA
第 3章 集合
【 例 3.24】 设 A=?1,2?,B=?a,b?,A=?x,y?，求：
A× B× C,A× (B× C)。
解,A× B× C=(A× B)× C
=1,a?,?1,b?,?2,a?,?2,b×?x,y?
=1,a?,x?,1,b?,x?,2,a?,x?,2,b?,x?,
1,a?,y?,1,b?,y?,2,a?,y?,2,b?,y
=1,a,x?,?1,b,x?,?2,a,x?,?2,b,x?,
1,a,y?,?1,b,y?,?2,a,y?,?2,b,y
A× (B× C)=?1,2?×a,x?,?a,y?,?b,x?,?b,y
=1,?a,x,?1,?a,y,?1,?b,x,?1,?b,y
2,?a,x,?2,?a,y,?2,?b,x,?2,?b,y
显然 A× B× C≠A× (B× C)。
返回总目录返回章目录
3.1 集合的基本概念
3.2 集合的运算
3.3 集合恒等式
3.4 集合的覆盖与划分
3.5 笛卡尔积返回总目录第 3章 集合第 3章 集 合
3.1集合的基本概念一些确定的、能区分的对象的全体是集合，通常用大写的英文字母表示。组成集合的对象叫做集合的元素或成员，常用小写的英文字母表示。
集合的元素必须是确定的。所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。
集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。例如集合?1,2,3,3?和?1,2,3?是同一集合。
第 3章 集合集合的元素是任意的对象，对象是可以独立存在的具体的或抽象的客体。它可以是独立存在的数、字母、人或其它物体，也可以是抽象的概念，当然也可以是集合。例如集合
1,2,?3?,?1,2的元素?3?和?1,2?就是集合。
集合的元素又是无序的，即?1,2,3?和?3,1,2?是同一集合。
设 S是集合,a是 S的一个元素，记为 a?S，读做,a属于
S”,也可读做,a在 S中,。如果 a不是 S的元素，记为 a?S，
读做,a不属于 S,,也可读做,a不在 S中,。
例如：
① 26个英文字母组成一个集合，任一英文字母是该集合的元素。
②直线上的所有点组成实数集合 R，每一个实数是集合 R
的元素。
③陕西科技大学全体学生组成一个集合，该校的每一个学生是这个集合的元素。
第 3章 集合
3.1.1集合的表示法集合有三种表示法。
第一种表示法是列举法：在花括号,” 中列举出该集合的元素，元素之间用逗号隔开。
例如：
I5=?1,2,3,4,5?
I+=?1,2,3,
I =?0,1,-1,2,-2,
S=?T,F?
第二种表示法是描述法：用谓词界定集合的元素。
例如：
Q=?x | x是有理数?
R=?x | x是实数?
C=?x | x是复数?
A=?x | x?I∧ 0＜ x∧ x＜ 5?
第 3章 集合若用 P(x)表示 x是有理数，那么 Q又可表示为：
Q=?x | P(x)?
一般地说，集合可用描述法表示为：
S=?x | A(x)? 其中,A(x)是谓词显然，当 a?S 时，则 A(a)为真；反之，当 A(a)为真，则
a?S。即 a?S的充分必要条件是 A(a)为真。
在中学的教科书中将自然数定义为：
N=?1,2,3,
这是对的。在离散数学中，认为自然数是由 0 开始的，即
N=?0,1,2,3,
我们把这种由 0 开始的自然数集叫做扩展的自然数集。
离散数学中使用扩展的自然数集。本书的自然数集是指扩展的自然数集。
第 3章 集合具有有限个元素的集合叫有限集，否则叫无限集。有限集元素的个数称为该集合的基数，也叫集合的势。有限集 A的基数记为 |A|。
例如：设 A=?a,b,c?,A 是有限集,A的基数 |A|=3。
无限集也有基数的概念。无限集的基数比有限集的基数要复杂的多，本书将在 5.3节中介绍。
扩展的自然数集 N=?0,1,2,3,是无限集。整数集合 I、
有理数集合 Q、实数集合 R和复数集合 C都是常见的无限集。
第 3章 集合
3.1.2子集和集合的相等定义 3.1.1 设 A,B是任意的集合，当 A的每一元素都是 B的元素时，则称 A是 B的子集，也称 A包含在 B内或 B包含 A。记为 A?B或 B?A。
当 A不是 B的子集时，记为 A?B。
A?B用谓词公式表示为,A?B?(?x)(x?A→ x?B)
A?B用谓词公式表示为,A?B?(?x)(x?A∧ x?B)
例如：设 A=?1?,B=?1,2?,C=?1,2,3?则
A?A
A?B,B?C,A?C
C?B
可以证明，集合的包含有下列性质：
①自反性。即对任意集合 A,A?A。
② 传递性。即对任意集合 A,B,C，当 A?B和 B?C
时,A?C。
第 3章 集合定义 3.1.2 设 A,B是集合，如果 A?B且 B?A，则称 A
与 B相等。记为 A=B。如果 A与 B不相等，记为 A≠B。
集合相等也可用谓词公式表示为：
A=B?A?B∧ B?A
(?x)(x?A→ x?B)∧ (?x)(x?B→ x?A)
(?x)(x?A? x?B)
例如：设 A=?1,2?,B=?1,?2,C=?2,1? 则
A=C,A≠B
由集合相等的定义可以看出，集合相等有下列性质：
①自反性,即对任意集合 A,A=A。
②对称性,即对任意集合 A,B，当 A=B时,B=A。
③传递性,即对任意集合 A,B,C，当 A=B和 B=C时，
A=C。
第 3章 集合定义 3.1.3 设 A,B是集合，如果 A?B且 A≠B，则称 A是
B的真子集。记为 A?B。如果 A不是 B的真子集，记为 A?B。
真子集用谓词公式表示为：
A?B?A?B∧ A≠B
(?x)(x?A→ x?B)∧ (?x)(x?B∧ x?A)
例如：设 A=?a?,B=?a,b?,C=?a,b,c?则
A?B,B?C,A?C
A?A
又如，自然数集是整数集合的真子集，也是有理数集合和实数集合的真子集，即 N?I,N?Q,N?R。
第 3章 集合定义 3.1.4 不包含任何元素的集合叫空集。记为?。
空集可以表示为：
=?x | P(x)∧?P(x)? 其中,P(x)为任意谓词空集?是不包含任何元素的集合，所以,|?|=0。
定理 3.1.1 空集是任意集合的子集。
证明,设 A是任意集合。对任意对象 x，由空集的定义知,x为假，由条件联结词的定义知,x→ x?A为真。
根据全称推广规则有
(?x)( x→ x?A)
为真，故A
第 3章 集合根据定理 3.1.1，空集是任意集合的子集，即A；对任意集合 A,A?A。一般地说，任意集合 A至少有两个子集，一个是空集?，另一个是它本身 A。
推论 空集是惟一的。
证明,设有两个空集?1和?2，由定理 3.1.1有?12
和?21，根据集合相等的定义知,?1=?2。
第 3章 集合
3.1.3幂集合定义 3.1.5 设 A是集合,A的所有子集构成的集合称为
A的幂集合，记为 P (A)，即
P (A) =?S | S?A?
【 例 3.1】 设 A=?a,b,c?,?是空集，试求
P (A),P (P (?))。
解,P (A)=,?a?,?b?,?c?,?a,b?,?a,c?,?b,c?,?a,b,c
P (?)=
P (P (?)) =,
第 3章 集合定理 3.1.2 设 A为有限集合，则 |P (A)|=2|A|
证明,设 |A|=n,A的子集有：
不含元素的子集?一个，即 个。
含一个元素的子集 n个，即 个。
含两个元素的子集 个。
含 n个元素的子集 个。
|P (A)|= + +? + =2n=2|A|
在例 3.1中，
|A|=3,|P (A)|=8=23 =2|A|
|?|=0,|P (?)|=1=20 =2|?|
|P (?)|=1,| P (P (?))|=2=21 =2|P (?)|
0nC
1nC
2nC
nnC
0nC 1nC nnC
第 3章 集合定义 3.1.6 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集。记为 E。
全集是相对的，不同的问题有不同的全集。即使是同一问题也可以取不同的全集。
集合的另一种表示法是文氏图（ Venn Diagram）。人们常用文氏图描述集合运算和它们之间的关系。集合的文氏图画法如下：
用矩形表示全集 E，在矩形中画一些圆表示其它集合，不同的圆代表不同的集合。如果没有特别说明，任何两个圆彼此相交。例如,A?B的文氏图如图
3.1所示。
返回章目录第 3章 集合
3.2集合的运算定义 3.2.1 设 A,B是任意的集合，由 A中的元素或 B中的元素组成的集合，称为 A和 B的并集，记为 A∪ B。
A∪ B=?x |x?A∨ x?B?
并集的定义如图 3.2所示。
从并集的定义可以得到：
A?A∪ B,B?A∪ B
第 3章 集合定义 3.2.2 设 A,B是集合，由 A与 B的公共元素组成的集合，称为 A和 B的交集，记为 A∩B。
A∩B=?x |x?A∧ x?B?
交集的定义如图 3.3所示。
从交集的定义可以得到：
A∩B?A,A∩B?B
如果 A与 B无公共元素，即 A∩B=?，则称 A和 B是互不相交的。
例如，令 A=?a,b,c?,B=?d,e?，则 A∩B=?,A和 B是互不相交的。
第 3章 集合定义 3.2.3 设 A,B是集合，属于 A的而不属于 B的元素组成的集合，称为 B对于 A的补集，也叫 B对于 A的相对补集。记为 A-B。
A-B=?x |x?A∧ x?B?
相对补集定义如图 3.4所示。
例如，令 A=,,B=?，则
A-B=,-?=,
又如，令 C=?a?,D=?a,b?，则
C-D =?a?-?a,b?=?
C-C=?
第 3章 集合定义 3.2.4 设 A是集合,A对于全集 E的相对补集，称为 A的绝对补集，记为 ~A。
~A=E-A=?x |x?E∧ x?A?=?x | x?A?
~A的定义如图 3.5所示。
例如，令全集 E=?1,2,3,4?,A=?1,2,3?，则
~A=?1,2,3,4?-?1,2,3?=?4?
第 3章 集合
【 例 3.5】 设 A,B是任意的集合，求证,A-B= A∩(~B)
证明,x?A-B?x?A∧ x?B?x?A∧ x?~B? x?A∩~B
即 A-B?A∩~B。
x?A∩~B?x?A∧ x?~B?x?A∧ x?B?x?A-B
故 A∩~B?A-B
所以,A-B= A∩(~B)。
A-B=A∩(~B)是一个重要的公式，在集合的运算中经常用到，它的意义在于将相对补运算转换绝对补和交运算。
第 3章 集合定义 3.2.5 设 A,B是集合，由 A中元素或 B中元素，
但不是 A与 B的公共元素组成的集合，称为 A和 B的对称差，
记为 A B。
A B=?x |x?Ax?B?=(A∪ B)-(A∩B)
A B的定义如图 3.6所示。
例如，令 A=?1,2,3,4?，
B=?1,2,5,6?，则
A B=A∪ B-A∩B
=?1,2,3,4,5,6?-?1,2?
=?3,4,5,6?
第 3章 集合
【 例 3.7】 设 A,B是任意的集合，求证,
A B=(A-B)∪ (B-A)=(A∩~B)∪ (B∩~A)。
证明,先证 A B=(A-B)∪ (B-A)。
x?A B?x?Ax?B
(x?A∧?x?B)∨ (?x?A∧ x?B)
(x?A∧ x?B)∨ (x?A∧ x?B)
x?A-B∨ x?B-A
x?(A-B)∪ (B-A)
所以,A B=(A-B)∪ (B-A)。
再证 (A-B)∪ (B-A)=(A∩~B)∪ (B∩~A)。
由例 3.5很容易得到此结论。这里从略。
第 3章 集合利用例 3.7中的公式可以证明对称差 A B下列的性质。
设 A,B是任意的集合。
① A A=?
证明,A A=(A-A)∪ (A-A) ==?
② A? = A
证明,A?=(A-?)∪ (?-A)=A∪?=A
③ A E=~ A
证明,A E=(A-E)∪ (E-A)=?∪ ~ A=~ A
第 3章 集合为了使集合的表达式更加简洁，我们对集合运算的优先顺序规定如下：
绝对补的运算级别比其它的 4个运算高，先进行绝对补运算，再进行其它的 4个运算；其它的 4个运算的运算顺序由括号决定。
用文氏图不仅可以表示集合的运算和它们之间的关系，
而且还可以很方便地解决有限集合的计数问题。
第 3章 集合用文氏图解决有限集合的计数问题的方法是：
每一条性质定义一个集合，画一个圆表示这个集合。
如果没有特别说明，任何两个圆画成相交的。将已知集合的元素数填入表示该集合的区域内。通常从 n个集合的交集填起，根据计算的结果逐步将数字填入其它各空白区域内。
如果交集的值是未知的，可以设为 x。根据题目的条件，列出方程或方程组，求出所需的结果。
第 3章 集合
【 例 3.9】 某班有 50名学生，第一次考试中 26人成绩为优，第二次考试中 21人成绩为优，已知两次考试中都不为优的共 17人。问两次考试中都为优的有多少人？
解,设 A,B分别表示第一次和第二次考试中成绩为优的学生集合。画出文氏图，如图 3.7所示。首先填 A∩B
中的人数，这正是要求的，设为 x。 A-B中的人数是 26-x，
B-A中的人数是 21-x，分别填入对应的区域。并列出如下方程：
(26-x)＋ x＋ (21-x)＋ 17=50
解得,x=14
返回章目录第 3章 集合
3.3 集合恒等式为了方便，下面列出一些常用的集合恒等式。它们是集合运算的主要公式，描述了集合运算的一般规律。这些恒等式都可以用集合相等的定义证明，但由于篇幅的限制，只证明其中的一部分。
恒等式中 A,B,C是任意的集合。
1.双重否定律 ~ (~A)=A
2.交换律 A∪ B=B∪ A
A∩B=B∩A
A B= B A
第 3章 集合
3.结合律 A∪ (B∪ C)= (A∪ B)∪ C
A∩(B∩C)= (A∩B)∩C
(A B) C=A (B C)
4.分配律 A∪ (B∩C)= (A∪ B)∩(A∪ C)
A∩(B∪ C)= (A∩B)∪ (A∩C)
A∩(B C)= (A∩B) (A∩C)
5.德摩根律 ~ (A∩B)= ~A∪ ~B
~ (A∪ B)= ~A∩~B
6.幂等律 A∪ A=A
A∩A= A
第 3章 集合
7.吸收律 A∪ (A∩B )=A
A∩(A∪ B )=A
8.零 律 A∪ E= E
A∩?=?
9.同一律 A∪?=A
A∩E=A
10.排中律 A∪ ~A=E
11.矛盾律 A∩~A=?
第 3章 集合
12.其它算律 ~?=E
~E=?
A-(B∪ C)=(A-B)∩(A-C)
A-(B∩C)=(A-B)∪ (A-C)
A A=?
A?=A
A E=~ A
A-B=A∩~B
A-B=A-(A∩B)
第 3章 集合
【 例 3.11】 用命题定律中的合取对异或的分配律
p∧ (q r)?(p∧ q) (p∧ r)
证明集合恒等式,A∩(B C)=(A∩B) (A∩C)
证明,x?A∩(B C)
x?A∧ x?B C
x?A∧ (x?B x?C)
(x?A∧ x?B) (x?A∧ x?C) (合取对异或分配律 )
x?(A∩B) x?(A∩C)
x?(A∩B) (A∩C)
A∩(B C)?(A∩B) (A∩C)
第 3章 集合
x?(A∩B) (A∩C)
x?A∩B x?A∩C
(x?A∧ x?B) (x?A∧ x?C)
x?A∧ (x?B x?C) (合取对异或的分配律 )
x?A∧ x?B C
x?A∩(B C)
(A∩B) (A∩C)?A∩(B C)
所以 A∩(B C)= (A∩B) (A∩C)
第 3章 集合
【 例 3.12】 用命题定律中的吸收律 A∨ (A∧ B)?A和
A∧ (A∨ B)?A
证明集合恒等式：
⑴ A∩(A∪ B)=A ⑵ A∪ (A∩B)= A
证明,仅证明⑴，⑵可类似的证明。
x?A∩(A∪ B )?x?A∧ x?A∪ B?x?A∧ (x?A∨ x?B)
x?A (吸收律 )
A∩(A∪ B)?A
x?A?x?A∧ (x?A∨ x?B) (吸收律 )
x?A∧ x?A∪ B? x?A∩(A∪ B )
A?A∩(A∪ B)
所以 A∩(A∪ B)=A
第 3章 集合
【 例 3.13】 用命题定律 p p?0,0 p?p，
1 pp，证明集合恒等式：
⑴ A A=? ⑵ A? =A ⑶ A E=~ A
证明,⑴证明 A A=?
x?A A? x?A x?A?0?x 所以 A A=?
⑵ 证明 A?=A
x?A x?A x x?A 0? x?A 所以
A?=A
⑶ 证明 A E=~ A
x?A E?x?A x?E? x?A 1
x?A?x?A?x?~A
所以 A E=~ A
第 3章 集合
【 例 3.14】 用命题定律中的德摩根律?(A∨ B)A∧?B，
(A∧ B)A∨?B证明集合恒等式：
⑴ ~ (A∪ B)= ~A∩~B ⑵ ~ (A∩B)= ~A∪ ~B
证明,⑴先证 ~ (A∪ B)?~A∩~B
x?~(A∪ B)?x?A∪ Bx?A∪ B
(x?A∨ x?B )
x?A∧?x?B (德摩根律 )
x?A∧ x?B
x?~A∧ x?~B
x?~A∩~B
~(A∪ B)?~A∩~B
第 3章 集合再证 ~A∩~B?~(A∪ B)
x?~A∩~B?x?~A∧ x?~B
x?A∧ x?B
x?A∧?x?B
(x?A∨ x?B) (德摩根律 )
x?A∪ B
x?A∪ B
x?~ (A∪ B)
~A∩~B?~ (A∪ B)
所以 ~ (A∪ B)= ~A∩~B
类似地可证明⑵。
第 3章 集合
【 例 3.17】 设 A,B是任意集合，用已知的集合恒等式证明,A-B=A-(A∩B)
证明,A-B=A∩~B
=?∪ (A∩~B)
= (A∩~ A)∪ (A∩~B)
=A∩(~ A∪ ~B)
=A∩~ (A∩B)
=A-(A∩B)
由于并运算满足结合律，故约定以下的符号：
由于交运算满足结合律，故约定以下的符号：
n
n
i
i AAAA 21
1
n
n
i
i AAAA 21
1
第 3章 集合除以上的恒等式外，还有一些关于集合运算的重要结果。例如：
A∩B?A
A∩B?B
A?A∪ B
B?A∪ B
A-B?A
A B?A∪ B
A?B?A∪ B=B?A∩B=A?A-B=?
A B=A C?B=C
返回章目录第 3章 集合
3.4集合的覆盖与划分定义 3.4.1 设 A是非空集合,π=?S1,S2,?,Sm?，
Si≠?,i=1,?,m，且满足：
⑴?Si?π,Si?A
⑵ S1∪ S2∪? ∪ Sm = A
则称 π是 A的一个覆盖。
定义 3.4.2 设 A是非空集合,π=?S1,S2,?,Sm?，
Si≠?,i=1,?,m,π是 A的一个覆盖，满足 Si∩Sj=?,i≠j，
则称 π是 A的一个划分。称 Si,i=1,?,m，是 A的划分块。
定义中的,Si∩Sj=?,i≠j” 是指 π中的元素两两互不相交。
第 3章 集合
【 例 3.20】 设 A=?a,b,c?，以下是 A的子集构成的集合：
S=a,b?,?b,c
Q=a?,?a,b?,?a,c
D=a?,?b,c
G=a,b,c
E=a?,?b?,?c
F=a?,?a,c
试确定哪些集合是 A的覆盖？哪些集合是 A的划分？
哪些集合既不是覆盖，也不是划分？
解,S和 Q是 A的覆盖，但不是划分； D,G和 E是 A的覆盖，也是划分； F不是 A的覆盖，也不是划分。
第 3章 集合集合 G=a,b,c是单元素集，它有一个元素?a,b,c?。
对单元素集a,b,c，认为它的元素的并集就是?a,b,c?，
同时也认为它的元素是两两互不相交的。所以集合 G=
a,b,c是 A的划分。
在 A的所有划分中基数最大的划分叫做 A的最大划分，
基数最小的划分叫做 A的最小划分。在例 3.20中,E是 A的最大划分,G是 A的最小划分。
第 3章 集合
【 例 3.21】 设 A=?1,2,3?，试确定 A的所有划分。
解,有一个划分块的划分是,1,2,3
有两个划分块的划分是,1?,?2,3
2?,?1,3
3?,?1,2
有三个划分块的划分是,1?,?2?,?3
图 3.9是 A的所有划分的示意图。 (a)表示有一个划分块的划分1,2,3。 (b),(c)和 (d)表示有两个划分块的划分1?,?2,3,2?,?1,3和3?,?1,2。 (e) 表示有三个划分块的划分1?,?2?,?3。
第 3章 集合定理 3.4.1 设 A=?A1,A2,?,Ar?与 B=?B1,B2,?,
Bs?是 C的两种划分，则集合 X=?Ai∩Bj | i=1,?,r,j=1,?,s，
Ai∩Bj≠也是 C的划分。
证明,
⑴ 先证 Ai∩Bj?C
由 A,B是 C的划分知,Ai?C,Bj?C，所以 Ai∩Bj?C。
第 3章 集合
⑵ 再证,
(A1∩B1)∪ (A1∩B2)∪? ∪ (A1∩Bs)∪
(A2∩B1)∪ (A2∩B2)∪? ∪ (A2∩Bs)∪
(Ar∩B1)∪ (Ar∩B2)∪? ∪ (Ar∩Bs)
=(A1∩(B1∪ B2∪? ∪ Bs))∪?
∪ (Ar∩(B1∪ B2∪? ∪ Bs))
=(A1∪ A2∪? ∪ Ar)∩(B1∪ B2∪? ∪ Bs)
=C∩C
=C
CBA
r
i
s
j
ji?
)(
1 1
第 3章 集合
⑶ 最后证 X中的元素是两两互不相交的。
在 X中取任意两个不同元素,Ai∩Bh与 Aj∩Bk，分三种情况讨论：
①设 i≠j,h=k
(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)
=?∩(Bh∩Bk)=?
② 设 i≠j,h≠k
(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)
=?∩?=?
③ 设 i=j,h≠k
(Ai∩Bh)∩(Aj∩Bk)=(Ai∩Aj)∩(Bh∩Bk)
=(Ai∩Aj)∩?=?
第 3章 集合定义 3.4.3 定理 3.4.1中定义的集合 X叫做原来两种划分
A和 B的交叉划分。
定义 3.4.4 设 A=?A1,A2,?,Ar?与 B =?B1,B2,?,
Bs?是 C的两种划分，如果?Ai?A,?Bk?B，使得 Ai?Bk。
则称 A是 B的加细，也称 A是 B的细分。
定理 3.4.2 任何两种划分的交叉划分都是原来两种划分的一种加细。
证明,设 A=?A1,A2,?,Ar?与 B=?B1,B2,?,Bs?
是 C的两种划分。
X=?Ai∩Bj | i=1,?,r,j=1,?,s,Ai∩Bj≠是 A和 B的交叉划分。
因为 Ai∩Bj?Ai,Ai∩Bj?Bj，所以 X是 A的一种加细，也是 B的一种加细。
返回章目录第 3章 集合
3.5 笛卡尔积定义 3.5.1两个个体 x,y的有序序列，称为二重组，也称为有序对或序偶。记为?x,y?。 x,y分别叫做二重组的第一分量和第二分量。
所谓有序序列是指调换第一分量和第二分量位置后，
就和原来的含义不同了。
定义 3.5.2 设?x,y?与?a,b?是两个二重组，如果 x=a且
y=b，则称二重组?x,y?与?a,b?相等，记为?x,y?=?a,b?。
二重组?x,y?与?a,b?相等，用逻辑的方法表示为
(?x,y?=?a,b?)?(x=a)∧ (y=b)。
由定义可以看出，当 x≠y时,?x,y?≠?y,x?。
例如，平面上的点 P1=?2,1?和点 P2=?1,2?是两个不同的点，它们都是二重组。
第 3章 集合定义 3.5.3 二重组x1,x2,?,xn-1?,xn?叫做 n重组。记为
x1,x2,?,xn?,xi叫做该 n重组的第 i个分量 i=1,?,n。
由定义可看出：三重组?x1,x2,x3?定义为x1,x2?,x3?，
其中第一分量是二重组；四重组?x1,x2,x3,x4?定义为
x1,x2,x3?,x4?，其中第一分量是三重组； 。
根据三重组的定义，第一分量是二重组，第二分量是一个个体的序偶x1,x2?,x3?是 3重组。而第一分量是一个个体，第二分量是二重组的序偶?x1,?x2,x3不是三重组。
这个结论对任意的 n(n=3,4,5,? )重组也是对的。例如，
x1,x2,x3?,x4?是四重组，而?x1,?x2,x3,x4不是四重组；
x1,x2,x3,x4?,x5?是五重组，而?x1,?x2,x3,x4,x5不是五重组。? 。
第 3章 集合定义 3.5.4 设?x1,x2,?,xn?与?y1,y2,?,y n?是两个 n重组，
如果 xi=yi,i=1,?,n，则称这两个 n重组相等，记为
x1,x2,?,xn?=?y1,y2,?,y n?。
n重组?x1,x2,?,xn?与?y1,y2,?,y n?相等，用逻辑的方法表示为 (?x1,x2,?,xn?=?y1,y2,?,y n?)
(x1= y1)∧ (x2= y2)∧? ∧ (xn= yn)。
定义 3.5.5 设 A,B是集合，集合a,b?| a?A∧ b?B?叫做 A,B的笛卡尔积，也叫 A,B的叉乘积，直积。记为：
A× B。
如果 A,B都是有限集,|A|= n,|B|= m，根据排列组合原理,|A× B|=nm=|A||B|。
第 3章 集合
【 例 3.22】 设 A=?a,b?,B=?1,2,3?，
⑴试求 A× B和 B× A
⑵ 验证 |A× B|=|A||B|和 |B× A|=|B||A|
解,⑴求 A× B和 B× A
A× B=a,1?,?a,2?,?a,3?,?b,1?,?b,2?,?b,3
B× A=1,a?,?1,b?,?2,a?,?2,b?,?3,a?,?3,b
⑵ 验证 |A× B|=|A||B|和 |B× A|=|B||A|
|A× B|=6=2× 3=|A||B|
|B× A|=6=3× 2=|B||A|
第 3章 集合如果把 × 看成运算，笛卡尔积有以下的性质：
①设 A为任意的集合，则 A×? =?× A=?
② 一般地说,× 不满足交换律：即 A× B≠B× A。
在例 3.22中,A× B≠B× A
③ 一般地说,× 不满足结合律：
即 (A× B)× C≠A× (B× C)
第 3章 集合定理 3.5.1 设 A,B,C是集合，则
⑴ A× (B∪ C) =(A× B)∪ (A× C)
⑵ A× (B∩C) =(A× B)∩(A× C)
⑶ (A∪ B)× C =(A× C)∪ (B× C)
⑷ (A∩B)× C =(A× C)∩(B× C)
证明,仅证明⑴,可类似地证明⑵、⑶、⑷。
a,bA× (B∪ C)
a?A∧ b?B∪ C
a?A∧ ( b?B∨ b?C)
(a?A∧ b?B)∨ (a?A∧ b?C)
a,bA× B∨?a,bA× C
a,b(A× B)∪ (A× C)
故 A× (B∪ C)=(A× B)∪ (A× C)
第 3章 集合定理 3.5.2 设 A,B,C是集合,C≠?，则
⑴ A?B的充分必要条件是 A× C?B× C
⑵ A?B的充分必要条件是 C× A?C× B
证明,仅证明⑴,可类似地证明⑵。
设 A?B，下证 A× C? B× C
a,bA× C?a?A∧ b?C
a?B∧ b?C
a,bB× C
所以 A× C?B× C
设 A× C?B× C，下证 A?B
因为 C≠?，所以存在 b?C
a?A?a?A∧ b?Ca,bA× C
a,bB× C?a?B∧ b?C?a?B
所以 A?B
第 3章 集合定理 3.5.3 设 A,B,C,D是非空集合，则
A× B?C× D的充分必要条件是 A?C且 B?D。
证明,设 A× B?C× D,下证 A?C且 B?D
a?A∧ b?Ba,bA× B
a,bC× D
a?C∧ b?D
所以 A?C且 B?D
设 A?C且 B?D，下证 A× B?C× D
a,bA× B?a?A∧ b?B
a?C∧ b?D
a,bC× D
所以 A× B?C× D
第 3章 集合定义 3.5.6 叉乘积 A1× A2×? × An定义为
(A1× A2×? × An-1)× An，
即 A1× A2×? × An
=a1,a2,?,an?| a1?A1∧ a2?A2∧? ∧ an?An?
由定义可以看出：
当 n=3时,A1× A2× A3定义为 (A1× A2)× A3
A1× A2× A3=a1,a2,a3?| a1?A1∧ a 2?A2∧ a3?A3?
当 n=4时,A1× A2× A3× A4定义为 (A1× A2× A3)× A4
A1× A2× A3× A4
=a1,a2,a3,a4?| a1?A1∧ a2?A2∧ a3?A3∧ a4?A4?
约定 An=的叉乘积个 An AAA
第 3章 集合
【 例 3.24】 设 A=?1,2?,B=?a,b?,A=?x,y?，求：
A× B× C,A× (B× C)。
解,A× B× C=(A× B)× C
=1,a?,?1,b?,?2,a?,?2,b×?x,y?
=1,a?,x?,1,b?,x?,2,a?,x?,2,b?,x?,
1,a?,y?,1,b?,y?,2,a?,y?,2,b?,y
=1,a,x?,?1,b,x?,?2,a,x?,?2,b,x?,
1,a,y?,?1,b,y?,?2,a,y?,?2,b,y
A× (B× C)=?1,2?×a,x?,?a,y?,?b,x?,?b,y
=1,?a,x,?1,?a,y,?1,?b,x,?1,?b,y
2,?a,x,?2,?a,y,?2,?b,x,?2,?b,y
显然 A× B× C≠A× (B× C)。
返回总目录返回章目录
