離散數(shù)學(xué)及其應(yīng)用-第2版 課件 第3章集合

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

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

Z：代表整數(shù)集合，

Q：代表有理數(shù)集合，

R：代表實(shí)數(shù)集合，

C：代表復(fù)數(shù)集合。5集合的表示法（1）1.列舉法

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

例如，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.描述法

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

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

Z

3<x

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

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

。空集可以符號(hào)化表示為

={x|x

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

F，x

E

T。

103.2集合間的關(guān)系定義3.2.1設(shè)A，B為集合，當(dāng)且僅當(dāng)它們恰有完全相同的元素時(shí)，稱A與B相等，記作A=B。符號(hào)化表示為A=B

x(x

A

x

B)定義3.2.2

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

A

或A

B。可符號(hào)化表示為B

A

x（x

B

x

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

A

。11集合間的關(guān)系定義3.2.3

設(shè)A，B為集合，如果B

A且B

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

B

，亦即B

A?？煞?hào)化表示為B

A

x（x

B

x

A）

x（x

A

x

B）12集合的性質(zhì)對(duì)任何集合A都有A

A

。設(shè)A、B為集合，A

B

B

A

A=B。設(shè)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

為假，所以整個(gè)蘊(yùn)涵式x

x

A對(duì)一切x為真，因此

A

為真。

推論

空集是唯一的。

證明

假設(shè)存在空集

1和

2，根據(jù)定理3.2.1，有

1

2和

2

1

，根據(jù)集合相等的定義得

1=

2

。1516例題

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

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

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

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

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

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

計(jì)算以下冪集：，{}；{，{}}解：

P()={}

P({})={，{}}

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

例題例3.2.5證明A

B當(dāng)且僅當(dāng)P(A)

P(B)證明

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

P(A)

x

A?x

B(∵A

B)

x

P(B)，所以P(A)

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

A

{y}

P(A)?{y}

P(B)(∵P(A)

P(B))

y

B，所以A

B成立。20213.3集合的運(yùn)算集合的運(yùn)算并，交，補(bǔ)（絕對(duì)補(bǔ)），差（相對(duì)補(bǔ)－），和對(duì)稱差等。集合的并運(yùn)算定義3.3.1設(shè)A，B為集合，由A和B的所有元素組成的集合稱為A與B的并集，可表示為：

A

B={x|x

A

x

B}

其文氏圖：

22對(duì)于n個(gè)集合A1，A2….An的并集為:23集合的交運(yùn)算定義3.3.2設(shè)A，B為集合，由同時(shí)屬于集合A和集合B的元素組成的集合，稱為集合A與集合B的交集，可符號(hào)化表示為：A

B={x|x

A

x

B}。文氏圖：

對(duì)于n個(gè)集合A1，A2….An的交集為:24當(dāng)兩個(gè)集合的交集是空集時(shí)，稱它們是不交的。下面例子中的B和C是不交的，其文氏圖如下：集合運(yùn)算的性質(zhì)定理3.3.1

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

B=B

A（2）A

B=B

A定理3.3.2

設(shè)A，B，C為任意三個(gè)集合，則下列結(jié)合律成立。（1）（A

B）

C=A

（B

C）

（2）（A

B）

C=A

（B

C）證明

用邏輯等價(jià)的方法證明（2）對(duì)任意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集合運(yùn)算的性質(zhì)定理3.3.4

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

（A

B）=A

（2）A

（A

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

A

（A

B）

x

（A

B）

x

A

（x

A

x

B）

x

A

x

A

所以A

（A

B）=A成立。

26集合運(yùn)算的性質(zhì)定理3.3.3

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

（B

C）=（A

B）

（A

C）（2）A

（B

C）=（A

B）

（A

C）證明

用邏輯等價(jià)的方法證明。（1）對(duì)任意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集合的差運(yùn)算定義3.3.3設(shè)A，B為任意二個(gè)集合，由屬于A但不屬于B的元素構(gòu)成的集合，稱為A和B的差，又稱為集合B對(duì)于A的補(bǔ)集或相對(duì)補(bǔ)集，記為A?B?？煞?hào)化表示為：A

B={x|x

A

x

B}。其文氏圖如下：

A-B=A

~B29集合的補(bǔ)運(yùn)算定義3.3.4設(shè)E為全集，A

E，則稱E和A的差集為A的補(bǔ)集或絕對(duì)補(bǔ)集，記作

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

設(shè)A，B為任意二個(gè)集合，則有：（1）

（A

B）=

A

B（2）

（A

B）=

A

B證明設(shè)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集合的對(duì)稱差運(yùn)算定義3.3.5

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

B?？煞?hào)化表示為：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

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

B={1，3，5，6}。對(duì)稱差運(yùn)算滿足如下性質(zhì)：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結(jié)合律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補(bǔ)律A

~A=

，

A

~A=E3334例題例3.3.5證明

證明

對(duì)任意x,所以例題

35例3.3.5證明

證明

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

B當(dāng)且僅當(dāng)（A

B）=B或（A

B）=A。證明

首先證明當(dāng)（A

B）=B或（A

B）=A時(shí)，A

B。

對(duì)任一x

A，有x

A

B，當(dāng)（A

B）=B時(shí)，則有x

B；當(dāng)（A

B）=A時(shí)，有x

A

B，從而x

B。因而A

B。其次證明若A

B則有（A

B）=B或（A

B）=A。

對(duì)任一x

A

B，有x

A或x

B。若x

A，因?yàn)锳

B，則x

B，所以任一x

A

B均有x

B。因而A

B

B。又因?yàn)锽

A

B，所以（A

B）=B。

對(duì)任一x

A，若A

B，則有x

B，因而有x

A

B。所以A

A

B。又因?yàn)锳

B

A，所以（A

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

設(shè)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對(duì)于空集

，求(1)

+，(2)(

+)+，(3)((

+)+)+。解

(1)

+=

{

}={

}(2)(

+)+={

}+={

}

{{

}}={

，{

}}(3)((

+)+)+={

，{

}}+={

，{

}}

{{

，{

}}}={

，{

}，{

，{

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

1=

+={

}2=（

+）+={

，{

}}3=（（

+）+）+={

，{

}，{

，{

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

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

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

N（2）如果n

N，則n+=n

{n}

N（3）如果S

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

設(shè)P(n)（n

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

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

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

P(0)

(

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

n)(P(n))數(shù)學(xué)歸納法在論域?yàn)樽匀粩?shù)集的相關(guān)定理證明中有重要的作用。41例題例3.4.1

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

?0，上述命題成