離散數(shù)學(xué)第13講

第二部分集合論

對(duì)于從事計(jì)算機(jī)科學(xué)工作的人們來(lái)說(shuō)，集合論是必不可少的基礎(chǔ)知識(shí)。例如有限狀態(tài)機(jī)、形式語(yǔ)言等都離不開子集、冪集、集合的分類等概念。集合成員表和范式在邏輯設(shè)計(jì)、定理證明中也都有重要應(yīng)用。本部分從集合的直觀概念出發(fā)，介紹了集合論中的一些基本概念和基本理論，其中包括集合、關(guān)系、函數(shù)等。離散數(shù)學(xué)第13講本講基本知識(shí)點(diǎn)：1、集合的基本概念2、集合的運(yùn)算3、集合基本恒等式2第六章集合代數(shù)6.1集合的基本概念直觀定義：一些事物匯集到一起組成的一個(gè)整體稱為集合，而這些事物就是這個(gè)集合的元素或成員。集合通常用大寫字母來(lái)標(biāo)記，如N、Z、Q、R、C。集合表示方法：列元素法A={1,2,3,4,5}謂詞表示法B={x|x∈N∧1≤x≤5}3第六章集合代數(shù)集合的特征互異性{1,2,3,2,4}={1,2,3,4}無(wú)序性{4,2,1,3}={1,2,3,4}元素和集合之間的關(guān)系屬于（∈）或不屬于（

）

如：對(duì)于A={1,{2,3},{{4}}}，1∈A,{2,3}∈A,3

A.可以用樹形圖表示這種關(guān)系?？紤]：4,{4},{{4}}呢?4第六章集合代數(shù)如：A1{2,3}{{4}}

23{4}4本書規(guī)定：對(duì)于任何集合A，都有A

A。5第六章集合代數(shù)定義6.1設(shè)A，B為集合，如果B中的每個(gè)元素都是A中的元素，則稱B是A的子集合，簡(jiǎn)稱子集。也稱B被A包含，或B包含于A，或A包含B，記作B

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

A。包含的符號(hào)化表示為：B

A

x(x∈Bx∈A)例如：N

Z

Q

R

C,而CR.顯然：對(duì)于任何集合A，都有A

A。6第六章集合代數(shù)定義6.2設(shè)A，B為集合，如果A

B且B

A，則稱A與B相等，記作A=B。如果A與B不相等，則記作A≠B。相等的符號(hào)化表示為：A=B

A

B

∧B

A7第六章集合代數(shù)定義6.3設(shè)A，B為集合，如果B

A且B≠A，則稱B是A的真子集,也稱B被A真包含，或B真包含于A，或A真包含B，記作B

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

B。真子集的符號(hào)化表示為：B

A

A≠B∧B

A例如：N

Z

Q

R

C,而CC.顯然：對(duì)于任何集合A，都有A

A。8第六章集合代數(shù)定義6.4不含任何元素的集合叫做空集，記作φ?？占姆?hào)化表示為：φ

{x|x≠x}如：C={x|x∈Z+∧x<0}.定理6.1空集是一切集合的子集。證明：對(duì)于任何集合A，有子集定義有φ

A

x(x∈φx∈A)右邊的蘊(yùn)涵式為真，所以φ

A也為真。推論：空集是唯一的。證明：如不唯一，設(shè)存在空集φ1和φ2，由定理6.1得

φ1

φ2和φ2

φ1根據(jù)集合相等的定義得，φ1=φ2。9第六章集合代數(shù)含有n個(gè)元素的集合簡(jiǎn)稱為n元集，它的含有m(m≤n)個(gè)元素的子集叫做它的m元子集。任給一個(gè)n元集，它的0元子集的個(gè)數(shù)為：Cn0,即φ；它的1元子集的個(gè)數(shù)為：Cn1,即單元集；它的2元子集的個(gè)數(shù)為：Cn2；……它的n元子集的個(gè)數(shù)為：Cnn.顯然：任一n元集A的子集總數(shù)為：

Cn0+Cn1+Cn2…+Cnn=2n請(qǐng)通過(guò)列出集合S={a,b,c}的所有子集來(lái)驗(yàn)證此結(jié)論。10第六章集合代數(shù)定義6.5設(shè)A為集合，把A的全部子集構(gòu)成的集合叫做A的冪集，記作P(A)或2A。冪集的符號(hào)化表示為P(A)＝｛x|x

A｝例如：若B={1，2，c,d}，則P(B)=???定義6.6在一個(gè)具體問(wèn)題中，若所涉及的集合都是某個(gè)集合的子集，則稱這個(gè)集合為全集，記作E。11第六章集合代數(shù)6.2集合的運(yùn)算定義6.7設(shè)A，B集合，A與B的并集A∪B，交集A∩B，B對(duì)A的相對(duì)補(bǔ)集A-B，分別定義如下：A∪B={x|x∈A∨

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

x∈B}A-B={x|x∈A∧

x

B}如：A={1,2,3},B={3,4,5}，C={6,7}則A∪B、A∩B、A-B、C∩B、C-B、C-C分別為？？？?jī)蓚€(gè)集合的并交運(yùn)算可推廣至n個(gè)集合：A1∪A2∪…∪An={x|x∈A1∨x∈A2∨…∨

x∈An

}A1∩A2∩

…∩An={x|x∈A1∧x∈A2∧

…∧

x∈An

}文氏圖是用來(lái)描述集合關(guān)系與運(yùn)算的很好的工具，請(qǐng)參見課本P96。12第六章集合代數(shù)定義6.8設(shè)A，B集合，A與B的對(duì)稱差集A○B(yǎng)，分別定義如下：A○B(yǎng)=(A–B)∪(B-A)或A○B(yǎng)=(A∪B)-(A∩B)+++定義6.9設(shè)A集合，E為全集，A的絕對(duì)補(bǔ)集定義為：~A=E–A={x|x∈E∨

x

A}13第六章集合代數(shù)利用文氏圖可以解決一些有限集的計(jì)數(shù)問(wèn)題參見例6.2、6.3練習(xí)：某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。已知會(huì)打網(wǎng)球的6個(gè)人都會(huì)打籃球或排球。求不會(huì)打球的人數(shù)。14假設(shè)只會(huì)打籃球和排球的人數(shù)為x，只會(huì)打籃球和網(wǎng)球的人數(shù)為y，只會(huì)打網(wǎng)球和排球的人數(shù)為z：x+2=6x=4z+2=5z=3y+2+z=6y=1不會(huì)打球的人數(shù)為：25-14-12+x+2=5

排球12網(wǎng)球6籃球14人2xyzx15練習(xí)2：對(duì)60個(gè)人的調(diào)查表明有25人閱讀《每周新聞》雜志，26人閱讀《時(shí)代》雜志，26人閱讀《財(cái)富》雜志，9人閱讀《每周新聞》和《財(cái)富》，11人閱讀《每周新聞》和《時(shí)代》，8人閱讀《時(shí)代》和《財(cái)富》，還有8人什么雜志也不讀。（1）求閱讀全部三種雜志的人數(shù)（2）分別求只閱讀《每周新聞》、《時(shí)代》和《財(cái)富》雜志的人數(shù)。16解：(1)(5+x)+(7+x)+(9+x)+(9-x)+(11-x)+(8-x)+x+8=60解得x=3(2)分別是8，10，12人x8-x8人9-x

11-x25-(11-x)-(9-x)-x=5+x時(shí)代26財(cái)富26每周新聞25人26-(11-x)-(8-x)-x=7+x26-(9-x)-(8-x)-x=9+x17第六章集合代數(shù)6.3集合恒等式P99-100列出的23條恒等式是這部分進(jìn)行運(yùn)算、證明的重要依據(jù)，望注意掌握。集合代數(shù)中恒等式證明的兩種思路：(1)設(shè)A1、A2為集合公式，欲證A1=A2，只須證A1

A2∧A2

A1為真。也即證

x∈A1=>x∈A2和

x∈A2=>x∈A1

(2)利用已知的恒等式代入。

總體上還是采用命題邏輯中的等值式，在敘述上采用半形式化的方法，其中

表示當(dāng)且僅當(dāng)，意即“等價(jià)”。18第六章集合代數(shù)例6.6證明A-(B∪C)=(A-B)∩(A-C).證明：對(duì)于

xx∈A-(B∪C)

x∈A∧x

(B∪C)

x∈A∧

(x∈B∨x∈C)

x∈A∧(

x∈B∧

x∈C)