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？