1.1 集合及其运算

集合理论是计算机理论的重要基础，也是形式语言和自动机理论的基础。

一些没有重复的对象的全体称为集合，而这些被包含的对象称为该集合的元素。集合中元素可以按任意顺序进行排列。一般来说，使用大写英文字母表示一个集合。

使用∅代表空集，表示该集合未包含任何元素。

若集合A包含元素x（也称元素x在集合A中），则记为x∈A。

若集合A未包含元素x（也称元素x不在集合A中），则记为x∉A。

若一个集合包含的元素是有限的，则称该集合为有穷集合。若一个集合包含的元素是无限的，则称该集合为无穷集合。

对于任意的有穷集合A，使用|A|表示该集合包含的元素的个数，显然，|∅|=0。

对于具体的集合，可以使用明确的、形式化的方法进行描述。

对于元素个数较少的有穷集合，可以采用列举法，即将集合的所有元素全部列出，放在一对花括号中。例如，集合A={0,1,2,3,4,5,6,7,8,9}，表示集合A由0,1,2,3,4,5,6,7,8, 9共10个元素组成。

对于集合元素较多的有穷集合和无穷集合，可以使用集合形成模式{x | P（x）}进行描述（也称为命题法）；其中，x表示集合中的任一元素，P（x）是一个谓词，对x进行限定。{x|P（x）}表示由满足P（x）的一切x构成的集合。可以使用自然语言或数学表示法来描述谓词P（x）。

例如，{n|n是偶数}或{n|n mod 2=0}，都表明了由所有偶数组成的集合。

定义1.1 子集的定义。

对于两个集合A和B，若集合A的元素都是集合B的元素，则称集合A包含于集合B中（或称集合B包含集合A），记为A⊆B，并且称集合A是集合B的子集。

若 A⊆B，且集合 B中至少有一个元素不属于集合 A，则称集合 A 真包含于 B中（或称集合B真包含集合A），记为A⊂B，此时，称集合A是集合B的真子集。

两个集合相等，当且仅当A⊆B且B⊆A。注意：不是A⊂B且B⊂A。

定义1.2 集合之间的运算。

集合A与集合B的并（或称为集合A与集合B的和），记为A∪B，是由集合A的所有元素和集合B的所有元素合并在一起组成的集合：

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

集合A与集合B的交，记为A∩B，是由集合A和集合B的所有公共元素组成的集合：

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

集合 A与集合 B的差，记为 A−B，是由属于集合 A但不属于集合 B的所有元素组成的集合：

A−B={x|x∈A且x∉B}

若B⊆A，则将A−B称为集合B（关于集合A）的补，集合A称为集合B的全集（论域）。

思考：什么情况下，A∪B=A，A∩B=A，A−B=A？

定义1.3 幂集的定义。

设A为一个集合，那么A的幂集为A的所有子集组成的集合，记为2A，即

2A={B|B⊆A}

例1.1 幂集的例子。

集合A={1,2,3}，则A的幂集为

当集合A为有穷集时，如果集合A包含的元素个数为n，那么集合2A的元素个数（集合A的所有子集的个数）为2A，这就是称2A为集合A的幂集的原因。当集合A为无穷集时，仍然使用2A表示集合A的幂集，它也是无穷集。

注意：

任何集合A的幂集2A的元素都是集合。

空集∅是任何集合的子集，也是任何集合A的幂集2A的子集。

定义1.4 笛卡儿乘积的定义。

集合A和B的笛卡儿乘积使用A×B表示（也简记为AB），它是集合

{（a,b）|a∈A 且b∈B}

A×B的元素称为有序偶对（a,b），总是A的元素在前，B的元素在后。

A×B与B×A一般不相等。

例如，设A={a,b,c}，B={0,1}，则

A×B={（a,0）,（a,1）,（b,0）,（b,1）,（c,0）,（c,1）}

而

B×A={（0,a）,（0,b）,（0,c）,（1,a）,（1,b）,（1,c）}

思考：什么情况下，A×B=B×A？