第三章集合1背景：集合是現代數學的基礎。集合不僅可以用來表示數及其運算，還可以用于非數值計算信息的表示和處理，如數據的增加、刪除、修改、排序，以及數據間關系的描述。集合論在計算機語言、數據結構、編譯原理、數據庫與知識庫、形式語言及人工智能等許多領域得到廣泛的應用。集合的基本概念3.1 集合及其表示 3.2 集合間的關系 3.3 集合的運算 3.4 自然數 3.5 集合的特征函數33.1集合及其表示集合是由一些對象聚集在一起構成的。例如，全體整數全體中國人26個英文字母構成集合的對象可以是各種類型的事物。定義3.1.1集合中的對象叫集合的元素，或成員。4集合的表示法通常用大寫的英文字母來標記一些集合。例如，

N：代表自然數集合(包括0)，

Z：代表整數集合，

Q：代表有理數集合，

R：代表實數集合，

C：代表復數集合。5集合的表示法（1）1.列舉法

列舉法是列出集合的所有元素，元素之間用逗號隔開，并把它們用花括號括起來。

例如，A={a，b，c，d}，B={1，2，3，4}N={1，2，3，

}，C={2，4，6，

，2n，

}，Z={0，

1，

2，…}等。6集合的表示法（2）2.描述法

描述法不要求列出集合中的所有元素，只要把集合中的元素具有的性質或所滿足的條件描述出來即可。

可以用謂詞公式描述集合中的元素具有的性質或所滿足的條件。一般地，用B={x|P(x)}表示集合B是由具有性質P的元素x構成。例如，B={x|x

Z

3<x

6}，C={x|x是小于10的正整數}注意:謂詞P(x)的范圍一定要明確清楚，否則，集合無法構造。如：A={x|P(x)}，P(x)：x是公園里的美麗的花。}7集合的表示法(3)3.歸納法歸納法是通過歸納定義集合，主要由三部分組成：指出某些最基本的元素屬于集合；指出由基本元素構造新元素的方法；指出該集合的界限。如：集合A按歸納法定義如下：（1）0和1都是集合A的元素；（2）如果a、b是A的元素，則ab和ba也是A的元素；（3）有限次地使用（1）（2）后所得到的字符串都是A的元素。8集合的元素

集合中的元素可以具有共同性質，也可以表面上看起來不相干。如{2，Tom，計算機，廣州}在集合論中，規定元素之間是彼此相異的，并且是沒有次序關系的。例如，{3,4,5},{3,4,4,5,5},{5,3,4}都是同一個集合。例如，A={3,4,5},3A,6A9特殊集合定義3.1.2有限個元素構成的集合A，稱為有限集，其中包含的元素個數稱為該集合的元素數，記為|A|。無限個元素構成的集合稱為無限集。定義3.1.3不含任何元素的集合稱為空集，記為

。空集可以符號化表示為

={x|x

x}定義3.1.4所考慮的所有對象的集合，稱為全集，記為E。對于任一元素x，有x

F，x

E

T。

103.2集合間的關系定義3.2.1設A，B為集合，當且僅當它們恰有完全相同的元素時，稱A與B相等，記作A=B。符號化表示為A=B

x(x

A

x

B)定義3.2.2

設A,，B為兩個集合，如果B中的每個元素都是A中的元素，則稱B為A的子集合，簡稱子集。這時也稱B被A包含，或A包含B。記作B

A

或A

B。可符號化表示為B

A

x（x

B

x

A）如果B不被A包含，則記作B

A

。11集合間的關系定義3.2.3

設A，B為集合，如果B

A且B

A(即集合B的每一個元素都屬于A，但集合A中至少有一個元素不屬于B)，則稱B是A的真子集。這時也稱B被A真包含，或A真包含B。記作A

B

，亦即B

A。可符號化表示為B

A

x（x

B

x

A）

x（x

A

x

B）12集合的性質對任何集合A都有A

A

。設A、B為集合，A

B

B

A

A=B。設A、B、C為集合，A

B

B

C

A

C。證明①顯然成立。②A

B

B

A

x（x

A

x

B）

x（x

B

x

A）

x（（x

A

x

B）

（x

B

x

A））

x（x

A

x

B）

A=B13

③A

B

B

C

x（x

A

x

B）

x（x

B

x

C）

x（（x

A

x

B）

（x

B

x

C））

x（x

A

x

C）

A

C。14空集定理3.2.1

空集

是一切集合的子集。

證明

任給集合A，由子集的定義有

A

x（x

x

A）

由于x

為假，所以整個蘊涵式x

x

A對一切x為真，因此

A

為真。

推論

空集是唯一的。

證明

假設存在空集

1和

2，根據定理3.2.1，有

1

2和

2

1

，根據集合相等的定義得

1=

2

。1516例題

確定下列命題是否為真。解：(1)，(3)，(4)為真，(2)為假。17例題

求A={a，b，c}的全部子集。解：將A的子集從小到大分類：0元子集，即空集，只有1個：

。1元子集，即單元子集，有3個：{a}，{b}，{c}。2元子集，有3個：{a，b}，{a，c}，{b，c}。3元子集，有1個：{a，b，c}。18冪集定義3.2.4設A為集合，把A的全體子集構成的集合叫做A的冪集，記作P(A)（或2A），符號化表示為P(A)={x|x

A}。若A是n元集，則P(A)有2n個元素。

例如：A=={a，b，c}，A的冪集：P(A)={

，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}。19例題

計算以下冪集：，{}；{，{}}解：

P()={}

P({})={，{}}

P({，{}})={,{}，{{}},{，{}}}

例題例3.2.5證明A

B當且僅當P(A)

P(B)證明

（1）先證明必要性，對任意的x，有x

P(A)

x

A?x

B(∵A

B)

x

P(B)，所以P(A)

P(B)成立。（2）再證明充分性，對任意的y，有y

A

{y}

P(A)?{y}

P(B)(∵P(A)

P(B))

y

B，所以A

B成立。20213.3集合的運算集合的運算并，交，補（絕對補），差（相對補－），和對稱差等。集合的并運算定義3.3.1設A，B為集合，由A和B的所有元素組成的集合稱為A與B的并集，可表示為：

A

B={x|x

A

x

B}

其文氏圖：

22對于n個集合A1，A2….An的并集為:23集合的交運算定義3.3.2設A，B為集合，由同時屬于集合A和集合B的元素組成的集合，稱為集合A與集合B的交集，可符號化表示為：A

B={x|x

A

x

B}。文氏圖：

對于n個集合A1，A2….An的交集為:24當兩個集合的交集是空集時，稱它們是不交的。下面例子中的B和C是不交的，其文氏圖如下：集合運算的性質定理3.3.1

設A，B為集合，則下列交換律成立。（1）A

B=B

A（2）A

B=B

A定理3.3.2

設A，B，C為任意三個集合，則下列結合律成立。（1）（A

B）

C=A

（B

C）

（2）（A

B）

C=A

（B

C）證明

用邏輯等價的方法證明（2）對任意x,x

（A

B）

C

x

（A

B）

x

C

x

A

x

B

x

C

x

A

x

（B

C）

x

A

（B

C）所以（A

B）

C=A

（B

C）成立。25集合運算的性質定理3.3.4

設A，B為任意二個集合，則下列吸收律成立。（1）A

（A

B）=A

（2）A

（A

B）=A證明集合等式的證明還可以利用一些集合恒等式證明。（1）對任意x,x

A

（A

B）

x

（A

B）

x

A

（x

A

x

B）

x

A

x

A

所以A

（A

B）=A成立。

26集合運算的性質定理3.3.3

設A，B，C為任意三個集合，則下列分配律成立。（1）A

（B

C）=（A

B）

（A

C）（2）A

（B

C）=（A

B）

（A

C）證明

用邏輯等價的方法證明。（1）對任意x,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）成立。（2）證明同（1）。2728集合的差運算定義3.3.3設A，B為任意二個集合，由屬于A但不屬于B的元素構成的集合，稱為A和B的差，又稱為集合B對于A的補集或相對補集，記為A?B。可符號化表示為：A

B={x|x

A

x

B}。其文氏圖如下：

A-B=A

~B29集合的補運算定義3.3.4設E為全集，A

E，則稱E和A的差集為A的補集或絕對補集，記作

A，即：

A=E-A={x|x

E

x

A}。或：

A=E-A={x|x

A}。

其文氏圖如下：~E=

，~

=E，~（~A）=AA

~A=

，A

~A=E德.摩根定律定理3.3.5

設A，B為任意二個集合，則有：（1）

（A

B）=

A

B（2）

（A

B）=

A

B證明設E為全集，顯然有A

E=A，A

E=E成立。（1）

（A

B）={x|x

E

x

（A

B）}={x|x

E

(x

(A

B))}={x|x

E

（

（x

A）

（x

B）}={x|x

E

（x

A

x

B）}={x|（x

E

x

A

）

（x

E

x

B）}=

A

B（2）證明同（1）。30集合的對稱差運算定義3.3.5

設A，B為集合，由屬于A而不屬于B的所有元素和屬于B而不屬于A的所有元素組成的集合，稱為集合A與B的對稱差，記為A

B。可符號化表示為：A

B={x|（x

A

x

B）

（x

B

x

A）}文氏圖為：31

A

B=（A-B）

（B-A）=(A~B)(B~A)

例題例3.3.4

設集合A={1，2，3，4，5}，B={2，4，6}則A

B={1，3，5，6}。對稱差運算滿足如下性質：A

A=

A

=A

A

B=B

A（A

B）

C=A

（B

C）32集合恒等式名稱等式恒等律A

=A，

A

E=A支配律A

E=E，

A

=

冪等律A

A=A，

A

A=A雙重否定律~(~A)=A交換律A

B=B

A，

A

B=B

A結合律A

(B

C)=(A

B)

C，

A

(B

C)=(A

B)

C分配率A

(B

C)=(A

B)

(A

C)，

A

(B

C)=(A

B)

(A

C)德摩根律~(A

B)=~

B

~A，~(A

B)=~A

~

B吸收律A

(A

B)=A，

A

(A

B)=A補律A

~A=

，

A

~A=E3334例題例3.3.5證明

證明

對任意x,所以例題

35例3.3.5證明

證明

利用集合恒等式證明例題例3.3.6證明A

B當且僅當（A

B）=B或（A

B）=A。證明

首先證明當（A

B）=B或（A

B）=A時，A

B。

對任一x

A，有x

A

B，當（A

B）=B時，則有x

B；當（A

B）=A時，有x

A

B，從而x

B。因而A

B。其次證明若A

B則有（A

B）=B或（A

B）=A。

對任一x

A

B，有x

A或x

B。若x

A，因為A

B，則x

B，所以任一x

A

B均有x

B。因而A

B

B。又因為B

A

B，所以（A

B）=B。

對任一x

A，若A

B，則有x

B，因而有x

A

B。所以A

A

B。又因為A

B

A，所以（A

B）=A。36自然數自然數集合包含無限多元素，用空集和后繼集可以把所有自然數定義為集合。定義3.4.1

設A是一集合，A的后繼集A+為：A+=A

{A}例3.4.1

已知集合A={1，2，3}，求A的后繼集A+。解

A的后繼集

A+=A

{A}={1，2，3}

{{1，2，3}}={1，2，3，{1，2，3}}37例題例3.4.2對于空集

，求(1)

+，(2)(

+)+，(3)((

+)+)+。解

(1)

+=

{

}={

}(2)(

+)+={

}+={

}

{{

}}={

，{

}}(3)((

+)+)+={

，{

}}+={

，{

}}

{{

，{

}}}={

，{

}，{

，{

}}}若集合A有n個元素，則A的后繼集A+有n+1個元素。38自然數集0=

1=

+={

}2=（

+）+={

，{

}}3=（（

+）+）+={

，{

}，{

，{

}}}……因此有：1=0+，2=1+，3=2+，……。以這些集合為元素構成的集合{0，1，2，3，……}是自然數集合。定義3.4.2

用空集和后繼集(緊跟在n后面的自然數)可以把所有自然數定義為集合，即由此可見，任一個自然數都是一個集合的名稱。39自然數集定義3.4.3

自然數集N可以用如下的遞歸方式定義：（1）

N（2）如果n

N，則n+=n

{n}

N（3）如果S

N且S滿足條件(1)和(2)，則S=N上述定義中，(1)給出了自然數集的首個元素，(2)給出了歸納條件，(3)則規定了N的封閉性和極小性，即N是同時滿足條件(1)和(2)的最小集合。40第一數學歸納法定義3.4.4

設P(n)（n

N）是論域在自然數集上的性質（或謂詞），若能證明（1）P(0)為真（2）對任何n

N，P(n)?P(n+)，則對所有n

N，P(n)為真。這種證明方法稱為第一數學歸納法。步驟(1)稱為歸納基，是歸納法的基礎條件；步驟(2)稱為歸納步，一般假定若n=k時，P(k)成立，要證明出P(k+)也成立。上述方法可形式化表達為

P(0)

(

n)(P(n)→P(n+))?(

n)(P(n))數學歸納法在論域為自然數集的相關定理證明中有重要的作用。41例題例3.4.1

證明空集屬于除0以外的一切自然數。證明：采用數學歸納法1）n=0時，

?0，上述命題成