第二部分集合論

1、1/28集合論是研究集合一般性質(zhì)的數(shù)學(xué)分支，創(chuàng)始人是集合論是研究集合一般性質(zhì)的數(shù)學(xué)分支，創(chuàng)始人是康托爾康托爾(G.Cantor 1845-1918)?，F(xiàn)代數(shù)學(xué)中，每個(gè)對?，F(xiàn)代數(shù)學(xué)中，每個(gè)對象象(數(shù)，函數(shù)等數(shù)，函數(shù)等)本質(zhì)上都是集合，即可以用某種集本質(zhì)上都是集合，即可以用某種集合來示義，數(shù)學(xué)的各個(gè)分支本質(zhì)上都是在研究某一合來示義，數(shù)學(xué)的各個(gè)分支本質(zhì)上都是在研究某一種對象集合的性質(zhì)，集合論的特點(diǎn)是研究對象的廣種對象集合的性質(zhì)，集合論的特點(diǎn)是研究對象的廣泛性，是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論表達(dá)工具。泛性，是計(jì)算機(jī)科學(xué)的基礎(chǔ)理論表達(dá)工具。2/283.1集合的基本概念集合的基本概念1.集合的定義集合的定義集合是

2、現(xiàn)代數(shù)學(xué)中最重要的基本概念之一。我們知集合是現(xiàn)代數(shù)學(xué)中最重要的基本概念之一。我們知道，在任何一個(gè)數(shù)學(xué)理論中，不可能對其中的每道，在任何一個(gè)數(shù)學(xué)理論中，不可能對其中的每個(gè)概念都嚴(yán)格定義，這樣的概念一般為數(shù)學(xué)理論個(gè)概念都嚴(yán)格定義，這樣的概念一般為數(shù)學(xué)理論中的原始概念，而稱其余的概念為它的派生概念。中的原始概念，而稱其余的概念為它的派生概念。如歐幾里得幾何學(xué)中，如歐幾里得幾何學(xué)中，“點(diǎn)點(diǎn)”和和“線線”是原始概是原始概念，而念，而“三角形三角形”和和“圓圓”則為派生概念。今天則為派生概念。今天我們介紹的我們介紹的“集合集合”也是一個(gè)不能嚴(yán)格定義的原也是一個(gè)不能嚴(yán)格定義的原始概念。但是為了理解上的方便，

3、我們?nèi)匀唤o一始概念。但是為了理解上的方便，我們?nèi)匀唤o一個(gè)不嚴(yán)格的定義。個(gè)不嚴(yán)格的定義。3/28定義定義3.1：任何被稱為任何被稱為“成員成員”或或“元素元素”的的對象的聚集稱為集合對象的聚集稱為集合(Set)。例如：自然數(shù)的全體例如：自然數(shù)的全體N，有理數(shù)的全體，有理數(shù)的全體Q，實(shí)，實(shí)數(shù)的全體數(shù)的全體R，復(fù)數(shù)的全體，復(fù)數(shù)的全體C，整數(shù)的全體，整數(shù)的全體Z，都是集合。都是集合。通常情況下，用帶通常情況下，用帶(或不帶或不帶)下標(biāo)的大寫英文字下標(biāo)的大寫英文字母表示集合，而用帶母表示集合，而用帶(或不帶或不帶)下標(biāo)的小寫英下標(biāo)的小寫英文字母表示集合的元素或成員。文字母表示集合的元素或成員。4/282

4、.集合的表示集合的表示集合是由它所包含的元素完全確定的，有多集合是由它所包含的元素完全確定的，有多種方法來表示一個(gè)集合。種方法來表示一個(gè)集合。(1).枚舉法：當(dāng)一個(gè)集合僅有有限個(gè)元素或元枚舉法：當(dāng)一個(gè)集合僅有有限個(gè)元素或元素之間有明顯的關(guān)系時(shí)，采用列出集合中全素之間有明顯的關(guān)系時(shí)，采用列出集合中全部元素或部分元素的方法，叫枚舉法。部元素或部分元素的方法，叫枚舉法。例：例：A=1,2,3,4，B=a, b, c, x, y, z，N =0,1,2,3, 。這種方法實(shí)際上是一種顯示表示法，優(yōu)點(diǎn)是這種方法實(shí)際上是一種顯示表示法，優(yōu)點(diǎn)是具有透明性，缺點(diǎn)是當(dāng)集合中元素比較多時(shí)具有透明性，缺點(diǎn)是當(dāng)集合中元

5、素比較多時(shí)會占據(jù)大量內(nèi)存。會占據(jù)大量內(nèi)存。5/28(2).描述法：一般用謂詞來概括集合中元素的描述法：一般用謂詞來概括集合中元素的特性，由謂詞特性，由謂詞P(x)所定義的集合常記為：所定義的集合常記為：A=x |P(x)。例：例：B=x | x R x2-1=0。謂詞表示法是一種隱式表示法，所表示的集謂詞表示法是一種隱式表示法，所表示的集合元素可以是很少的或無窮多個(gè)，從計(jì)算機(jī)合元素可以是很少的或無窮多個(gè)，從計(jì)算機(jī)的角度來看，是種的角度來看，是種“動(dòng)態(tài)動(dòng)態(tài)”的表示法，不用的表示法，不用占據(jù)大量內(nèi)存。占據(jù)大量內(nèi)存。(3).文氏圖法文氏圖法(Venn)：文氏圖解法是一種利用：文氏圖解法是一種利用平面

6、上的點(diǎn)的集合作成的對集合的圖解，一平面上的點(diǎn)的集合作成的對集合的圖解，一般用平面上的圓形或方形表示一個(gè)集合。般用平面上的圓形或方形表示一個(gè)集合。6/283.集合與元素的關(guān)系集合與元素的關(guān)系元素和集合之間的關(guān)系是元素和集合之間的關(guān)系是“隸屬關(guān)系隸屬關(guān)系”，即，即“屬于屬于”或或“不屬于不屬于”，“屬于屬于”記作記作，不屬于記作不屬于記作 。例：例：A=a，b，c，d，a A， b，c A，b A。例例3-1：在一個(gè)很偏僻的孤島上，住著：在一個(gè)很偏僻的孤島上，住著一些人家，島上只有一個(gè)理發(fā)師，該理一些人家，島上只有一個(gè)理發(fā)師，該理發(fā)師專給那些并且只給那些自己不刮臉發(fā)師專給那些并且只給那些自己不刮臉

7、的人刮臉。那么該給這位理發(fā)師刮臉？的人刮臉。那么該給這位理發(fā)師刮臉？7/28在離散數(shù)學(xué)中，我們僅討論界限清楚無二義在離散數(shù)學(xué)中，我們僅討論界限清楚無二義性的元素與集合的隸屬關(guān)系，即元素性的元素與集合的隸屬關(guān)系，即元素a要么要么屬于集合屬于集合A，要么不屬于集合，要么不屬于集合A，兩者必居，兩者必居其一。其一。4.集合的特性集合的特性(1).確定性：即確定性：即aA或或a A，兩者必居其一，兩者必居其一且僅居其一；且僅居其一；(2).互異性：集合中相同的元素被視為同一元互異性：集合中相同的元素被視為同一元素，即：素，即：1，1，2，2與與1，2相同；相同；(3).無序性：集合中的元素順序并不重要

8、，如無序性：集合中的元素順序并不重要，如1，2，3，4與與2，3，4，1相同。相同。8/285.集合之間的關(guān)系集合之間的關(guān)系定義定義3.2：設(shè)設(shè)A，B是兩個(gè)集合，如果是兩個(gè)集合，如果B中的每個(gè)元中的每個(gè)元素都是素都是A中的元素，則稱中的元素，則稱B是是A的子集合，簡稱子的子集合，簡稱子集集(Subset)，這時(shí)也稱，這時(shí)也稱B被被A包含，或包含，或A包含包含B，記，記作作B A，或，或A B，稱，稱“ ”或或“ ”為包含關(guān)系為包含關(guān)系(Inclusion Relation)。如果。如果B不被不被A包含，則記作包含，則記作B A。例：例：N Z Q R C, 但但Z N ;A=1，2，3，4，B

9、=1，2，C=2，3，D=2，3，則則B,C,D A; C D; D C; B C,D; C,D B; A B,C,D 對任意的集合對任意的集合A，都有，都有A A 。9/28定義定義3.3：設(shè)設(shè)A，B為集合，如果為集合，如果A B且且B A，則稱則稱A與與B相等，記作相等，記作A=B，如果，如果A與與B不相等，則記作不相等，則記作AB。相等的符號化表示為：相等的符號化表示為：A=B A B B A例：例：A=x|xN，且，且x4，B=0，1，2，3，4則則A=B。定義定義3.4：設(shè)設(shè)A，B為集合，如果為集合，如果B A且且BA，則稱則稱B是是A的真子集的真子集(Proper Subset)，

10、記作，記作B A，稱，稱“ ”為真包含關(guān)系為真包含關(guān)系(Properly Inclusion Relation)，如果如果B不是不是A的真子集，則記作的真子集，則記作B A10/28這時(shí)或者這時(shí)或者 ，或者，或者B=A，符號化表示為：，符號化表示為：例：例： ，但，但 ，0,1，2,3是是0,1,2,3的真子集，但的真子集，但1,4不是。不是。定義定義3.5：不含任何元素的集合叫做空集不含任何元素的集合叫做空集(Empty Set)，記作。空集符號化表示為：，記作?？占柣硎緸椋?x |x x。例：設(shè)例：設(shè) ，是方程，是方程 的實(shí)的實(shí)數(shù)解集，而該方程無實(shí)數(shù)解，所以數(shù)解集，而該方程無實(shí)數(shù)解，

11、所以A= 。CRQZNNN AB ABABAB01xRx|x2A012x11/28定理定理3.1：(1)：空集是一切集合的子集，：空集是一切集合的子集，(2)：空集是唯一的。空集是唯一的。例例3-2：確定下列命題的真值：確定下列命題的真值：(1)： ，(2)： ，(3)： ，(4)： 。12/28定義定義3.6：在一個(gè)具體問題中，如果涉及的集合都是在一個(gè)具體問題中，如果涉及的集合都是某個(gè)集合的子集，則稱這個(gè)集合問全集某個(gè)集合的子集，則稱這個(gè)集合問全集(Universal Ser)，用，用U或或E表示。表示。全集是唯一的，它包含了該問題所涉及的所有元素。全集是唯一的，它包含了該問題所涉及的所有元

12、素。例：例：(1)在平面幾何中，全集是由平面上全體點(diǎn)組成在平面幾何中，全集是由平面上全體點(diǎn)組成； (2)在人口研究中，全集是由世界上的所有人組成在人口研究中，全集是由世界上的所有人組成定義定義3.7：集合中的所有元素的個(gè)數(shù)稱為集合的基數(shù)集合中的所有元素的個(gè)數(shù)稱為集合的基數(shù)(Base Number)，記為，記為|A|；如果一個(gè)集合的基數(shù)是；如果一個(gè)集合的基數(shù)是有限的，則稱集合為有限集有限的，則稱集合為有限集(Finite Set)，如果一個(gè)，如果一個(gè)集合的基數(shù)是無限的，則稱集合為無限集集合的基數(shù)是無限的，則稱集合為無限集(Infinite Set)。13/28例例3-3：求集合：求集合A，B，C

13、，D的基數(shù)：的基數(shù)：A= ；B=1,2,3；C=1，2,3；D= 。解：解：|A|=0；|B|=3；|C|=2；|D|=1。定義定義3.8：含有含有n個(gè)元素的集合個(gè)元素的集合A稱為稱為n元集，它的含義元集，它的含義m個(gè)個(gè)(m n)元素的子集稱作它的元素的子集稱作它的m元子集。元子集。例例3-4：設(shè)：設(shè)A=1,2,3，求，求A的全部子集：的全部子集：解：將解：將A的全部子集按從小到大進(jìn)行分類：的全部子集按從小到大進(jìn)行分類： 0元子集：即空集，有元子集：即空集，有C03個(gè)：個(gè)： ； 1元子集：即單元素，有元子集：即單元素，有 C13個(gè)：個(gè)：1，2，3； 2元子集：有元子集：有C23個(gè)：個(gè)：1,2，

14、1,3，2,3； 3元子集：有元子集：有C33個(gè)：個(gè)：1,2,3。14/28集合集合A=1,2,3的全部子集共有的全部子集共有：一般來說，對于一般來說，對于n元集元集A，它的，它的m(0mn)元子集有元子集有個(gè)，所以它的不同子集總數(shù)為：個(gè)，所以它的不同子集總數(shù)為：定義定義3.9：設(shè)設(shè)A為集合，把為集合，把A的全體子集構(gòu)成的集合的全體子集構(gòu)成的集合叫做叫做A的冪集的冪集(Power Set)，記作，記作P(A)或或2A，符號化，符號化為：為：P(A)=x|x A。例：設(shè)例：設(shè)A=1,2,3，則，則P(A)= ，1，2，3，1,2，1,3，2,3，1,2,3，|P(A)|=2n81331CCCC3

15、3231303mnCnnnnnn2) 11 (CCC1015/28例例3-5：求下列冪集：求下列冪集：(1)：P()；(2)：P()；(3)：P(,)；(4)：P(1，2,3)。16/28為了更好的研究集合的性質(zhì)，我們定義了集合的幾為了更好的研究集合的性質(zhì)，我們定義了集合的幾個(gè)基本運(yùn)算。個(gè)基本運(yùn)算。定義定義3.10：設(shè)設(shè)A，B是兩個(gè)集合，則是兩個(gè)集合，則A與與B的并集的并集(Union)定義為：定義為： ，“”稱為稱為并運(yùn)算并運(yùn)算(Union Operation)。例：例：1,2,3,43,4,5=1,2,3,4,5，QN=Q。定義定義3.11：設(shè)設(shè)A，B是兩個(gè)集合，則是兩個(gè)集合，則A與與B的

16、交集的交集(Intersection)定義為：定義為： ，“”稱為交運(yùn)算稱為交運(yùn)算(Intersection Operation)。例：例：1,2,3,4 3,4,5=3,4，a, b = ， QN=N。|BxAxxBA|BxAxxBA17/28可以將以上定義推廣到可以將以上定義推廣到n個(gè)甚至無窮個(gè)集合的并集個(gè)甚至無窮個(gè)集合的并集或交集：或交集：例：例：1,22,30,1=0,1,2,3； 1,2 2,3 0,1= 。|21211212112121121211AxAxxAAAAxAxxAAAAxAxAxxAAAAAxAxAxxAAAAiiiinnininnini18/28定義定義3.12：設(shè)設(shè)

17、A，B是兩個(gè)集合，則是兩個(gè)集合，則A與與B的差集的差集(Subtraction)定義為：定義為： ；“-”稱為差運(yùn)算稱為差運(yùn)算(Subtraction Operation)，A-B也可也可叫做相對補(bǔ)集。叫做相對補(bǔ)集。例：例：1,2,3,4-3,4,5,6=1,2；1,2- =1,2； -1,2= ；1,2-1,2= 。定義定義3.13：設(shè)設(shè)U為全集，為全集，A是是U的子集，則集合的子集，則集合A的的補(bǔ)集補(bǔ)集(Complement)定義為：定義為：也可記為也可記為A，“-”，“”稱為補(bǔ)運(yùn)算稱為補(bǔ)運(yùn)算(Complement Operation)。例：例：U=1,2,3,4，A=1,2，A=3,4。

18、|BxAxxBA|AxUxxAUA19/28定義定義3.14：設(shè)設(shè)A，B是兩個(gè)集合，是兩個(gè)集合，A與與B的對稱差集的對稱差集(Symmetric Differences)定義為：定義為：“ ”稱為對稱差運(yùn)算稱為對稱差運(yùn)算(Symmetric Differences Operation)。例：例：1,2,3,4 3,4,5,6=1,2,5,6； a, b, c =a, b, c。定理定理3.2：集合恒等式：集合恒等式：1.等冪律：等冪律：A A=A，A A=A;2.結(jié)合律結(jié)合律：(AB)C=A(BC)，(A B) C=A (B C)；3.交換律：交換律：A B=B A，A B=B A；)()(ABBABA20/284.分配律：分配律：A(BC)=(A B) (A C)，A (B C)=(A B)(A C)；5.同一律：同一律：A =A，A U=A；6.零律：零律：A U=U，A = ；7.排中律：排中律： ；8.矛盾律：矛盾律： ；9.吸收律：吸收律：A(A B)=A， A (A B)=A；10.德摩根律：德摩根律：(AB)=A B，(A B)=AB11.雙重否定律：雙重否定律： ；12.補(bǔ)交轉(zhuǎn)換律：補(bǔ)交轉(zhuǎn)換律： 。UAAAAAA BABA21/28例例3-6：證：證：(3):A，B為集合，已知為集合，已知A-B=B-