第三章 集 合
3.1 集合论基础
3.2 集合运算及其性质
3.3 集合的笛卡儿积与无序积退出
3.1 集合论基础
1,集合与元素所谓集合,是指某些可辨别的不同对象的全体,将用大写字母 A,B,X,Y,··表示之 。
组成集合的对象称为集合的元素或成员,将用小写字母 a,b,x,y···表示之 。 a是 A的元素或 a
属于 A,记作 a?A； a不属于 A或 a不是 A的元素,
记作 a?A,或者?(a?A)。
集合的元素一旦给定，这一集合便完全确立。这一事实被形式地叙述为外延公理。
外延公理：两集合 A和 B相等，当且仅当它们有相同的元素。
若 A与 B相等，记为 A=B；否则，记为 A?B。
外延公理可形式表为：
A=B?(?x)(x?A?x?B)
或者
A=B?(?x)(x?A?x?B)?(?x)(x?B?x?B)
顺便指出，在应用外延公理证明集合 A与 B
相等时，只需考察：
对于任意元素 x，应有下式
x?B?x?B
成立即可。这就是说，证明两集合相等时可按此法行事。
表示一个特定集合，基本上有两种方法：
一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。如
A={a,e,i,o,u} (1)
表明集合 A是由字母 a,e,I,o和 u为元素构成的。
二是谓词法，用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素，确定了一个集合，因为这些元素都具有某种特殊性质。若 P(x)含有一个自由变元的谓词公式，则
{x|P(x)}定义了集合 S，并可表为
S={x|P(x)}
由此可见,P(c)为真当且仅当 c?S。从而有
x?S?x?P(x)
例如,(1)可表为
A={x|x是英文字母表中元音字母 }
在用性质来描述集合时，可表述为概括原理或子集合公理。
子集公理：
对于任给集合 A和性质 P，存在集合 B，使得 B中元素恰为 A中满足 P的那些元素。
子集公理可形式地表为
(?B)(?x)(x?B?x?A(x))
其中?(x)为不含 B自由出现。
子集公理的提出，避免了悖论，使集合论得以存在和发展。
应该指出的是：①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，
集合并不改变，即 {a,a,e,i,o,u}= { a,u,e,o,i}。
但有时对重复出现的元素都认为是集合的元素，
这种集合称为多重集。即 {a,a,e,i,o,u,u}?{a,
e,i,o,u}。本书中集合在不特别指明时，都指前者，即①中的集合。
② 集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。如，一本书，一支笔，集合 {1,2,3}可以组成集合 B={一本书，一支笔,{1,2,3}}。特别地，以集合为元素的集合称为集合族或集合类如 A={{1,2,3},{ 8,9,6}}。
③集合中元素之间可以有某种关联，也可以彼此毫无关系。
2,子集,全集与空集子集是描述一个集合与另一个集合之间的关系,其定义如下 。
定义 3.1.1 设 A和 B是任意两个集合,如果集合 A的每个元素,都是集合 B中的一个元素,
则称 A是 B的子集,或称 A被包含于 B中,或者说
B包含 A,并记为 A?B。
本定义也可表成
A?B?(?x)(x?A?x?B)
这表明，要证明 A?B，只需对任意元素 x，有下式
x?A?x?B
成立即可。
此外，若集合 B不包含集合 A，记为 A?B。/
定义 3.1.2 设 A和 B是两个集合，若 A?B且
A?B，则称 A是 B的真子集，记为 A?B，也称 B
真包含 A。该定义也可表为
A?B?(A?B?A?B)
定义 3.1.3 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为 U或 E。
它可形式地表为
U={x|P(x)P(x)}
其中 P(x)为任何谓词公式。
显然，全集 U即是第二章中的全总论域。
于是，每个元素 x都属于全集 U，即命题
(?x)(x?U)为真。由定义易知，对任意集合 A，
都有 A?U。
在实际应用中，常常把某个适当大的集合看成全集 U。
定义 3.1.4 没有任何元素的集合，称为空集，
记为?，它可形式地表为：
={x|P(x)P(x)}
其中 P(x)为任何谓词公式。
由定义可知，对任何集合 A，有A。这是因为任意元素 x，公式 xx?A总是为真。
注意,?与 {?}是不同的。 {?}是以?为元素的集合，而?没有任何元素，能用?构成集合的无限序列：
(1)?,{?},{{?}},···
该序列除第一项外，每项均以前一项为元素的集合。
(2)?,{?},{?,{?}},···
该序列除第一项外，每项均以前面各项为元素的集合。它即是冯 ·诺依曼在 1924年使用空集?
给出自然数的集合表示：
0:=?,1:={?},2:={?,{?}},···
定理 3.1.1 空集是唯一的定理 3.1.2 (ⅰ )对任一集合 A，有 A?A。
(ⅱ )若 A?B且 B?C，则 A?C。
3,集合的基数表示集合中元素多少或度量集合大小的数,
称作集合的基数或势 。 一个集合 A的基数,记为
|A|。
如果一个集合恰有 m个不同的元素,且 m是某个非负整数,称该集合是有限的或有穷的,
否则称这个集合为无限的或无穷的 。 例如,在本书中常用有穷集有：
Nm={0,1,2,··,m-1}
本书中常见的无穷集合有：
N={0,1,2,3,··}，即自然数集合。
Z={···,-2,-1,0,1,2,3,··}，即整数集合。
Z+={1,2,3,··}，即正整数集合。
Q=有理数集合。
R=实数集合。
C=复数集合。
4．集合的幂集一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族。
定义 3.1.5 设 A为一集合,A的幂集是一集合族，记为 P(A)，
P(A)={B|B?A}
由定义可知,P(A),A?P(A)。
5,文氏图文氏 (Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法 。 全集 U用一个矩形的内部表示,其他集合用矩形内的园面或一封闭曲线圈成的面积来表示 。
如果 A?B，则表示 A的圆面一般将完全落在表示 B的圆面内，如图 1中 (a)。如果 A与 B没有公共元素，那么表示 A的圆面将同表示 B的圆面分开，如图 3-1中 (b)。当 A和 B是两个任意的集合时，可能会是：有些元素在 A中但不在 B中，
有些元素在 B中却不在 A中，有些元素同时在 A
和 B中，有些元素则既不在 A中也不在 B中，因此用图 1中 (c)表示任意两个集合 A和 B。
图 3-1
最后给出集合的形式定义结束本节 。
定义 3.1.6 A为集合 =(?x)(x?A?A=?)。
这里等号,=”表示定义为的意义,是表示
,定义为,还是表示,一般相等,的意义,由上下文来区分 。
3.2 集合运算及其性质集合运算是指用已知的集合去生成新的集合 。 假设所有集合都是全集 U的子集,即这些集合是利用子集公理得到的 。 下面依次介绍常见的集合运算 。
1．并、交和差运算定义 3.2.1 设 A和 B是任意两个集合，
① A和 B的并是集合，记为 A∪ B，
A∪ B={x|x?A?x?B}
② A和 B的交是集合，记为 A∩B，
A∩B={x|x?A?x?B}
③ A和 B的差，或 B关于 A的相对补是集合，
记为 A-B，
A-B={x|x?A?x?B}
定义 3.2.2 若 A和 B是集合,且 A∩B=?,则称 A和 B是不相交的 。
如果 C是个集合族,且 C中任意两个不同元素都不相交,则称 C中集合是两个不相交的,或称 C是两两不相交的集合族 。
定理 3.2.1 任给集合 A,B和 C,则：
① A∪ B=B∪ A
② A∩B=B∩A
③ (A∪ B)∪ C=A∪ (B∪ C)
④ (A∩B)∩C=A∩(B∩C)
该定理表明,集合并和交运算满足交换律和结合律 。
定理 3.2.2 任给集合 A,B和 C,则
① A∪ (B∩C)=(A∪ B)∩(A∪ C)
② A∩(B∪ C)=(A∩B)∪ (A∩C)
该定理表明,集合运算并对交,交对并都是可分配的 。
定理 3.2.3 任给集合 A,B,C和 D,则
① 若 A?B,则 A∪ B=B,A∩B=A
② 若 A?B 和 C?D,则 A∪ C?B∪ D,
A∩C?B∩D
推论 3.2.3 ① A∪ U=U,② A∩U=A
定理 3.2.4 任给集合 A,B和 C,则
① A-(B∪ C)=(A-B)∩(A-C)
② A-(B∩C)=(A-B)∪ (A-C)
定义 3.2.3 设 A是含有元素为集合的集合,
或者集合族 。
① A的并是集合,记为 ∪ A，
∪ A={x|(?B)(B?A?x?B)}=∪ B
② A的交是集合,记为 ∩A，
∩A={x|(?B)(B?A?x?B)}=∩B
B? A
B? A
定义 3.2.4 集合 A的补是集合,记为 A’，
A’=U-A={x|x?U?x?A}
={x|x?A}
定理 3.2.5 任给集合 A,则
① A∪ A’=U，
② A∩A’=?。
定理 3.2.6 任给集合 A和 B,则
B=A’ iff A∪ B=U 且 A∩B=?
该定理表明了 ① 若 A的补是 B,则 B的补是
A,即 A和 B互补 。 ② 补的唯一性 。
推论 3.2.5 ① U’=?,②?’ =U
定理 3.2.7 任给集合 A,则 A”=A。
该定理表明了,A的补的补是 A。
定理 3.2.8 任给集合 A和 B,则
① (A∪ B)’=A’∩B’，
② (A∩B)’=A’∪ B’。
定义 3.2.5 任给集合 A和 B,A和 B的对称差是集合,记为 A?B，
A?B =(A-B)∪ (B-A)
={x|(x?A?x?B)?(x?B?x?A)}
定理 3.2.9 任给集合 A和 B,则
A?B=(A∪ B)∩(A’∪ B’)
=(A∪ B) - (A∩B)
推论 3.2.9 ① A’?B’=A?B
② A?B=B?A
③ A?A=?
2,集合代数与对偶原理本小节将形式地讨论由集合,集合变元,
集合运算和 圆 括号所构成的集合代数以及集合代数中的对偶原理 。
与命题逻辑相似,对于给定集合实行集合运算,可以生成新的集合 。 同用大写英文字母表示确定集合一样,也用大写字母表示不确定的集合,前者称为集合常元,后者称为集合变元 。 集合变元用以集合常元代替后,才表示确定的集合 。 下面将给出集合的合式公式定义 。
定义 3.2.6 可按下列规则生成集合合式公式
：
① 单个集合变元是集合合式公式。
② 若 A是集合合式公式，则 A’也是集合合式公式。
③ 若 A和 B是集合合式公式，则 (A∪ B)，
(A∩B),(A-B)和 (A?B)也都是集合合式公式。
④ 只有有限次使用①、②和③构成的符号串才是集合合式公式。
为方便计，简称集合合式公式为公式。
定义 3.2.7 用任意集合常元取代两个集合公式中的各个集合变元，若所得集合是相等的，
则称该二集合公式是相等的，简称等式。
因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合恒等式，或集合定律。它们刻划了集合运算的某些性质，
这些性质描述一个代数，称为集合代数。下面列出常用集合定律：
（ 1） 等幂律 A∪ A=A
A∩A=A
（ 2） 结合律 (A∪ B)∪ C=A∪ (B∪ C)
(A∩B)∩C=A∩(B∩C)
（ 3） 交换律 A∪ B=B∪ A
A∩B=B∩A
（ 4） 分配律 A∪ (B∩C)=(A∪ B)∩(A∪ C)
A∩(B∪ C)=(A∩B)∪ (A∩C)
（ 5） 幺律 A∪?=A
A∩U=A
（ 6） 零律 A∪ U=U
A∩?=?
（ 7） 补律 A∪ A’=U
A∩A’=?
（ 8） 吸收律 A∪ (A∩B)=A
A∩(A∪ B)=A
（ 9） 德 ·摩根律 (A∪ B)’=A’∩B’
(A∩B)’=A’∪ B’
（ 10） 对合律 (A’)’=A
下面介绍集合代数中的对偶原理，它与命题逻辑中对偶原理也很相似。
对偶原理 设 E是集合代数中等式，将 E中的 ∪,∩,U和?的每一个出现分别代以 ∩,∪
,?和 U后得到一等式 E*,称 E*为 E的对偶式。
显然,E也是 E*的对偶式，即 E与 E*互为对偶。
如果 E是一集合恒等式，则 E*也是一集合恒等式。
可见，上述的集合定律中，凡成对的定律都是为对偶的。
3.3 集合的笛卡 尔 积与无序积笛卡 尔 积与无序积在后面讨论关系和图论时,都有重要应用 。
首先引入有序对和无序对的概念 。
定义 3.3.1 两个元素 a,b组成二元组,若它们有次序之别,称为二元有序组,或有序对,
记为 <a,b>,称 a为第一分量,b为第一分量；若它们无次序区分,称为二元无序组,或无序对,
记为 (a,b)。
若 a?b时,<a,b>?<b,a>。 但 (a,b)=(b,a)。
定义 3.3.2 给定两个有序对 <x,y>和 <u,v>。
当且仅当 x=u和 y=v时，有序对 <x,y>和 <u,v>相等，亦即
<x,y>=<u,v> iff (x=u)?(y=v)
可将有序对推广到 n元有序组，它的第一分量是 (n-1)元有序组，并记为 <<x1,x2,··,xn-1>,xn>，
或记为 <x1,x2,··,xn-1,xn>。 类似地定义两个 n元有序组相等：
<x1,x2,··,xn-1,xn>=<y1,y2,··,yn-1,yn> iff
(x1=y1)?(x2=y2)?···?(xn-1=yn-1)?(xn=yn)
下面将使用有序对和无序对分别定义笛卡儿积和无序积。
定义 3.3.3 给定集合 A和 B,若有序对的第一分量是 A的元素，第二分量是 B的元素，所有这些有序对的集合，称为 A和 B的笛卡 尔 积，记为 A?B，
A?B={<x,y>|x?A?y?B}
定义 3.3.4 给定集合 A和 B,若无序对是由 A
中元素和 B中元素组成,所有这些无序对的集合
,称为 A和 B的无序积,记为 A&B。
A&B={(x,y)|x?A?y?B}
定理 3.3.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)
笛卡 尔 积的概念可以推广到 n个集合
A1,A2,··,An的笛卡 尔 积,它可表成：
Ai=(A1?A2?···?An-1)?An,n≥2。
用归纳法不难证明,若 Ai(1≤i≤n)是有穷集合,则 |A1?A2?···?An|=|A1|·|A2|·… ·| An|。
3.1 集合论基础
3.2 集合运算及其性质
3.3 集合的笛卡儿积与无序积退出
3.1 集合论基础
1,集合与元素所谓集合,是指某些可辨别的不同对象的全体,将用大写字母 A,B,X,Y,··表示之 。
组成集合的对象称为集合的元素或成员,将用小写字母 a,b,x,y···表示之 。 a是 A的元素或 a
属于 A,记作 a?A； a不属于 A或 a不是 A的元素,
记作 a?A,或者?(a?A)。
集合的元素一旦给定，这一集合便完全确立。这一事实被形式地叙述为外延公理。
外延公理：两集合 A和 B相等，当且仅当它们有相同的元素。
若 A与 B相等，记为 A=B；否则，记为 A?B。
外延公理可形式表为：
A=B?(?x)(x?A?x?B)
或者
A=B?(?x)(x?A?x?B)?(?x)(x?B?x?B)
顺便指出，在应用外延公理证明集合 A与 B
相等时，只需考察：
对于任意元素 x，应有下式
x?B?x?B
成立即可。这就是说，证明两集合相等时可按此法行事。
表示一个特定集合，基本上有两种方法：
一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。如
A={a,e,i,o,u} (1)
表明集合 A是由字母 a,e,I,o和 u为元素构成的。
二是谓词法，用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素，确定了一个集合，因为这些元素都具有某种特殊性质。若 P(x)含有一个自由变元的谓词公式，则
{x|P(x)}定义了集合 S，并可表为
S={x|P(x)}
由此可见,P(c)为真当且仅当 c?S。从而有
x?S?x?P(x)
例如,(1)可表为
A={x|x是英文字母表中元音字母 }
在用性质来描述集合时，可表述为概括原理或子集合公理。
子集公理：
对于任给集合 A和性质 P，存在集合 B，使得 B中元素恰为 A中满足 P的那些元素。
子集公理可形式地表为
(?B)(?x)(x?B?x?A(x))
其中?(x)为不含 B自由出现。
子集公理的提出，避免了悖论，使集合论得以存在和发展。
应该指出的是：①集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，
集合并不改变，即 {a,a,e,i,o,u}= { a,u,e,o,i}。
但有时对重复出现的元素都认为是集合的元素，
这种集合称为多重集。即 {a,a,e,i,o,u,u}?{a,
e,i,o,u}。本书中集合在不特别指明时，都指前者，即①中的集合。
② 集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。如，一本书，一支笔，集合 {1,2,3}可以组成集合 B={一本书，一支笔,{1,2,3}}。特别地，以集合为元素的集合称为集合族或集合类如 A={{1,2,3},{ 8,9,6}}。
③集合中元素之间可以有某种关联，也可以彼此毫无关系。
2,子集,全集与空集子集是描述一个集合与另一个集合之间的关系,其定义如下 。
定义 3.1.1 设 A和 B是任意两个集合,如果集合 A的每个元素,都是集合 B中的一个元素,
则称 A是 B的子集,或称 A被包含于 B中,或者说
B包含 A,并记为 A?B。
本定义也可表成
A?B?(?x)(x?A?x?B)
这表明，要证明 A?B，只需对任意元素 x，有下式
x?A?x?B
成立即可。
此外，若集合 B不包含集合 A，记为 A?B。/
定义 3.1.2 设 A和 B是两个集合，若 A?B且
A?B，则称 A是 B的真子集，记为 A?B，也称 B
真包含 A。该定义也可表为
A?B?(A?B?A?B)
定义 3.1.3 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为 U或 E。
它可形式地表为
U={x|P(x)P(x)}
其中 P(x)为任何谓词公式。
显然，全集 U即是第二章中的全总论域。
于是，每个元素 x都属于全集 U，即命题
(?x)(x?U)为真。由定义易知，对任意集合 A，
都有 A?U。
在实际应用中，常常把某个适当大的集合看成全集 U。
定义 3.1.4 没有任何元素的集合，称为空集，
记为?，它可形式地表为：
={x|P(x)P(x)}
其中 P(x)为任何谓词公式。
由定义可知，对任何集合 A，有A。这是因为任意元素 x，公式 xx?A总是为真。
注意,?与 {?}是不同的。 {?}是以?为元素的集合，而?没有任何元素，能用?构成集合的无限序列：
(1)?,{?},{{?}},···
该序列除第一项外，每项均以前一项为元素的集合。
(2)?,{?},{?,{?}},···
该序列除第一项外，每项均以前面各项为元素的集合。它即是冯 ·诺依曼在 1924年使用空集?
给出自然数的集合表示：
0:=?,1:={?},2:={?,{?}},···
定理 3.1.1 空集是唯一的定理 3.1.2 (ⅰ )对任一集合 A，有 A?A。
(ⅱ )若 A?B且 B?C，则 A?C。
3,集合的基数表示集合中元素多少或度量集合大小的数,
称作集合的基数或势 。 一个集合 A的基数,记为
|A|。
如果一个集合恰有 m个不同的元素,且 m是某个非负整数,称该集合是有限的或有穷的,
否则称这个集合为无限的或无穷的 。 例如,在本书中常用有穷集有：
Nm={0,1,2,··,m-1}
本书中常见的无穷集合有：
N={0,1,2,3,··}，即自然数集合。
Z={···,-2,-1,0,1,2,3,··}，即整数集合。
Z+={1,2,3,··}，即正整数集合。
Q=有理数集合。
R=实数集合。
C=复数集合。
4．集合的幂集一个集合的幂集是指该集合所有子集的集合，即是由这些子集所组成的集合族。
定义 3.1.5 设 A为一集合,A的幂集是一集合族，记为 P(A)，
P(A)={B|B?A}
由定义可知,P(A),A?P(A)。
5,文氏图文氏 (Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法 。 全集 U用一个矩形的内部表示,其他集合用矩形内的园面或一封闭曲线圈成的面积来表示 。
如果 A?B，则表示 A的圆面一般将完全落在表示 B的圆面内，如图 1中 (a)。如果 A与 B没有公共元素，那么表示 A的圆面将同表示 B的圆面分开，如图 3-1中 (b)。当 A和 B是两个任意的集合时，可能会是：有些元素在 A中但不在 B中，
有些元素在 B中却不在 A中，有些元素同时在 A
和 B中，有些元素则既不在 A中也不在 B中，因此用图 1中 (c)表示任意两个集合 A和 B。
图 3-1
最后给出集合的形式定义结束本节 。
定义 3.1.6 A为集合 =(?x)(x?A?A=?)。
这里等号,=”表示定义为的意义,是表示
,定义为,还是表示,一般相等,的意义,由上下文来区分 。
3.2 集合运算及其性质集合运算是指用已知的集合去生成新的集合 。 假设所有集合都是全集 U的子集,即这些集合是利用子集公理得到的 。 下面依次介绍常见的集合运算 。
1．并、交和差运算定义 3.2.1 设 A和 B是任意两个集合，
① A和 B的并是集合，记为 A∪ B，
A∪ B={x|x?A?x?B}
② A和 B的交是集合，记为 A∩B，
A∩B={x|x?A?x?B}
③ A和 B的差，或 B关于 A的相对补是集合，
记为 A-B，
A-B={x|x?A?x?B}
定义 3.2.2 若 A和 B是集合,且 A∩B=?,则称 A和 B是不相交的 。
如果 C是个集合族,且 C中任意两个不同元素都不相交,则称 C中集合是两个不相交的,或称 C是两两不相交的集合族 。
定理 3.2.1 任给集合 A,B和 C,则：
① A∪ B=B∪ A
② A∩B=B∩A
③ (A∪ B)∪ C=A∪ (B∪ C)
④ (A∩B)∩C=A∩(B∩C)
该定理表明,集合并和交运算满足交换律和结合律 。
定理 3.2.2 任给集合 A,B和 C,则
① A∪ (B∩C)=(A∪ B)∩(A∪ C)
② A∩(B∪ C)=(A∩B)∪ (A∩C)
该定理表明,集合运算并对交,交对并都是可分配的 。
定理 3.2.3 任给集合 A,B,C和 D,则
① 若 A?B,则 A∪ B=B,A∩B=A
② 若 A?B 和 C?D,则 A∪ C?B∪ D,
A∩C?B∩D
推论 3.2.3 ① A∪ U=U,② A∩U=A
定理 3.2.4 任给集合 A,B和 C,则
① A-(B∪ C)=(A-B)∩(A-C)
② A-(B∩C)=(A-B)∪ (A-C)
定义 3.2.3 设 A是含有元素为集合的集合,
或者集合族 。
① A的并是集合,记为 ∪ A，
∪ A={x|(?B)(B?A?x?B)}=∪ B
② A的交是集合,记为 ∩A，
∩A={x|(?B)(B?A?x?B)}=∩B
B? A
B? A
定义 3.2.4 集合 A的补是集合,记为 A’，
A’=U-A={x|x?U?x?A}
={x|x?A}
定理 3.2.5 任给集合 A,则
① A∪ A’=U，
② A∩A’=?。
定理 3.2.6 任给集合 A和 B,则
B=A’ iff A∪ B=U 且 A∩B=?
该定理表明了 ① 若 A的补是 B,则 B的补是
A,即 A和 B互补 。 ② 补的唯一性 。
推论 3.2.5 ① U’=?,②?’ =U
定理 3.2.7 任给集合 A,则 A”=A。
该定理表明了,A的补的补是 A。
定理 3.2.8 任给集合 A和 B,则
① (A∪ B)’=A’∩B’，
② (A∩B)’=A’∪ B’。
定义 3.2.5 任给集合 A和 B,A和 B的对称差是集合,记为 A?B，
A?B =(A-B)∪ (B-A)
={x|(x?A?x?B)?(x?B?x?A)}
定理 3.2.9 任给集合 A和 B,则
A?B=(A∪ B)∩(A’∪ B’)
=(A∪ B) - (A∩B)
推论 3.2.9 ① A’?B’=A?B
② A?B=B?A
③ A?A=?
2,集合代数与对偶原理本小节将形式地讨论由集合,集合变元,
集合运算和 圆 括号所构成的集合代数以及集合代数中的对偶原理 。
与命题逻辑相似,对于给定集合实行集合运算,可以生成新的集合 。 同用大写英文字母表示确定集合一样,也用大写字母表示不确定的集合,前者称为集合常元,后者称为集合变元 。 集合变元用以集合常元代替后,才表示确定的集合 。 下面将给出集合的合式公式定义 。
定义 3.2.6 可按下列规则生成集合合式公式
：
① 单个集合变元是集合合式公式。
② 若 A是集合合式公式，则 A’也是集合合式公式。
③ 若 A和 B是集合合式公式，则 (A∪ B)，
(A∩B),(A-B)和 (A?B)也都是集合合式公式。
④ 只有有限次使用①、②和③构成的符号串才是集合合式公式。
为方便计，简称集合合式公式为公式。
定义 3.2.7 用任意集合常元取代两个集合公式中的各个集合变元，若所得集合是相等的，
则称该二集合公式是相等的，简称等式。
因为集合公式相等，不依赖于取代集合变元的集合，故常称这些等式为集合恒等式，或集合定律。它们刻划了集合运算的某些性质，
这些性质描述一个代数，称为集合代数。下面列出常用集合定律：
（ 1） 等幂律 A∪ A=A
A∩A=A
（ 2） 结合律 (A∪ B)∪ C=A∪ (B∪ C)
(A∩B)∩C=A∩(B∩C)
（ 3） 交换律 A∪ B=B∪ A
A∩B=B∩A
（ 4） 分配律 A∪ (B∩C)=(A∪ B)∩(A∪ C)
A∩(B∪ C)=(A∩B)∪ (A∩C)
（ 5） 幺律 A∪?=A
A∩U=A
（ 6） 零律 A∪ U=U
A∩?=?
（ 7） 补律 A∪ A’=U
A∩A’=?
（ 8） 吸收律 A∪ (A∩B)=A
A∩(A∪ B)=A
（ 9） 德 ·摩根律 (A∪ B)’=A’∩B’
(A∩B)’=A’∪ B’
（ 10） 对合律 (A’)’=A
下面介绍集合代数中的对偶原理，它与命题逻辑中对偶原理也很相似。
对偶原理 设 E是集合代数中等式，将 E中的 ∪,∩,U和?的每一个出现分别代以 ∩,∪
,?和 U后得到一等式 E*,称 E*为 E的对偶式。
显然,E也是 E*的对偶式，即 E与 E*互为对偶。
如果 E是一集合恒等式，则 E*也是一集合恒等式。
可见，上述的集合定律中，凡成对的定律都是为对偶的。
3.3 集合的笛卡 尔 积与无序积笛卡 尔 积与无序积在后面讨论关系和图论时,都有重要应用 。
首先引入有序对和无序对的概念 。
定义 3.3.1 两个元素 a,b组成二元组,若它们有次序之别,称为二元有序组,或有序对,
记为 <a,b>,称 a为第一分量,b为第一分量；若它们无次序区分,称为二元无序组,或无序对,
记为 (a,b)。
若 a?b时,<a,b>?<b,a>。 但 (a,b)=(b,a)。
定义 3.3.2 给定两个有序对 <x,y>和 <u,v>。
当且仅当 x=u和 y=v时，有序对 <x,y>和 <u,v>相等，亦即
<x,y>=<u,v> iff (x=u)?(y=v)
可将有序对推广到 n元有序组，它的第一分量是 (n-1)元有序组，并记为 <<x1,x2,··,xn-1>,xn>，
或记为 <x1,x2,··,xn-1,xn>。 类似地定义两个 n元有序组相等：
<x1,x2,··,xn-1,xn>=<y1,y2,··,yn-1,yn> iff
(x1=y1)?(x2=y2)?···?(xn-1=yn-1)?(xn=yn)
下面将使用有序对和无序对分别定义笛卡儿积和无序积。
定义 3.3.3 给定集合 A和 B,若有序对的第一分量是 A的元素，第二分量是 B的元素，所有这些有序对的集合，称为 A和 B的笛卡 尔 积，记为 A?B，
A?B={<x,y>|x?A?y?B}
定义 3.3.4 给定集合 A和 B,若无序对是由 A
中元素和 B中元素组成,所有这些无序对的集合
,称为 A和 B的无序积,记为 A&B。
A&B={(x,y)|x?A?y?B}
定理 3.3.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)
笛卡 尔 积的概念可以推广到 n个集合
A1,A2,··,An的笛卡 尔 积,它可表成：
Ai=(A1?A2?···?An-1)?An,n≥2。
用归纳法不难证明,若 Ai(1≤i≤n)是有穷集合,则 |A1?A2?···?An|=|A1|·|A2|·… ·| An|。
