1、集合關(guān)系函數(shù)集合論第1頁(yè)第1頁(yè)第4章 集合 集合理論是一門(mén)研究數(shù)學(xué)基礎(chǔ)學(xué)科，它試圖從一個(gè)比“數(shù)”更簡(jiǎn)樸概念集合(sets)出發(fā)，定義數(shù)及其運(yùn)算，進(jìn)而發(fā)展到整個(gè)數(shù)學(xué)。集合理論產(chǎn)生于16世紀(jì)末。當(dāng)初，只是由于微積分學(xué)需要，人們僅對(duì)數(shù)集進(jìn)行了研究。第2頁(yè)第2頁(yè)第4章 集合 19世紀(jì)末，即 18761883年間， 康托爾（George Cantor 184519,德國(guó)數(shù)學(xué)家） 對(duì)任意元素集合進(jìn)行了系統(tǒng)研究?？低袪柋还J(rèn)為集合理論創(chuàng)始人。 第3頁(yè)第3頁(yè)第4章 集合 人們稱(chēng)康托爾開(kāi)創(chuàng)集合理論為樸素集合論，由于他沒(méi)有對(duì)集合論作完全公理化描述，從而造成了理論不一致（產(chǎn)生了悖論）。為填補(bǔ)樸素集合理論不足，20世

2、紀(jì)初出現(xiàn)了各種公理化集合論體系,為數(shù)學(xué)奠定了一個(gè)良好基礎(chǔ)。第4頁(yè)第4頁(yè)第4章 集合 更故意義是，從此集合基本概念不斷進(jìn)一步人心，被廣泛地應(yīng)用于數(shù)學(xué)理論和其它學(xué)科基礎(chǔ)研究和實(shí)際應(yīng)用中，集合論原理和辦法成為名副其實(shí)數(shù)學(xué)基本技術(shù)。集合論主要研究集合性質(zhì)、關(guān)系、運(yùn)算、無(wú)窮序數(shù)與無(wú)窮基數(shù)以及它公理系統(tǒng)和相應(yīng)邏輯性質(zhì)。在這一領(lǐng)域中有大量未處理問(wèn)題，并且還在不斷地提出新問(wèn)題，這表明集合論是一門(mén)充斥生命力學(xué)科。第5頁(yè)第5頁(yè)第4章 集合 事實(shí)上，集合不但可用來(lái)表示數(shù)及其運(yùn)算，更能夠用于非數(shù)值信息及離散結(jié)構(gòu)表示和處理。像數(shù)據(jù)刪節(jié)、插入、排序，數(shù)據(jù)間關(guān)系描述，數(shù)據(jù)組織和查詢(xún)都很難用老式數(shù)值計(jì)算來(lái)處理，但能夠用集合運(yùn)

3、算來(lái)實(shí)現(xiàn)。集合論被廣泛應(yīng)用在計(jì)算機(jī)科學(xué)中，如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)、知識(shí)庫(kù)、編譯原理、形式語(yǔ)言、程序設(shè)計(jì)、人工智能、信息檢索、CAD等。第6頁(yè)第6頁(yè)第4章 集合本章內(nèi)容提綱： 1、集合概念及其表示 2、集合之間關(guān)系 3、集合運(yùn)算 4、集合運(yùn)算定律及證實(shí) 5、文氏圖第7頁(yè)第7頁(yè)4.1 集合及其表示4.1.1 集合基本概念 所謂集合，就是把人們直觀或想象中一些擬定能夠區(qū)別對(duì)象匯合在一起構(gòu)成一個(gè)整體。構(gòu)成集合各個(gè)對(duì)象，稱(chēng)為這個(gè)集合元素或組員。第8頁(yè)第8頁(yè)4.1 集合及其表示 例4.1 指出下列敘述中哪些是集合，哪些不是集合？ （1）中國(guó)人集合； （2）百貨商店里好看花布集合； （3）1000以?xún)?nèi)

4、素?cái)?shù)集合； （4）26個(gè)英文字母構(gòu)成集合； （5）這個(gè)班里高個(gè)子學(xué)生集合； （6）直線y2x-5上點(diǎn)集合。第9頁(yè)第9頁(yè)4.1 集合及其表示 解 （1）（3）（4）（6）是集合；（2）不是集合，由于對(duì)每一個(gè)布，沒(méi)有擬定原則說(shuō)它是“好看”還是“不好看”；（5）也不是集合，由于在“高個(gè)子”與“不是高個(gè)子”之間沒(méi)有明確界線，但是，假如我們給出一個(gè)完全擬定原則（如身高不小于1.80米），合乎這個(gè)原則算是“高個(gè)子”，不然不算，那么對(duì)于這個(gè)班里每一個(gè)學(xué)生，總能夠明確地?cái)喽ㄊ欠窈虾踹@個(gè)原則，這時(shí)“這個(gè)班里高個(gè)子學(xué)生”就構(gòu)成一個(gè)集合。 第10頁(yè)第10頁(yè)4.1 集合及其表示 通常，用大寫(xiě)字母A，B，C，表示集合，

5、用小寫(xiě)字母a，b，c，表示元素。用下列字母表示慣用集合： N 自然數(shù)集合（包括0）； Nm 小于m自然數(shù)集合,即0,1,m-1； I 整數(shù)集合； I+ 正整數(shù)集合； I_ 負(fù)整數(shù)集合；R 實(shí)數(shù)集合； R+ 正實(shí)數(shù)集合；R_ 負(fù)實(shí)數(shù)集合； Q 有理數(shù)集合；C 復(fù)數(shù)集合。第11頁(yè)第11頁(yè)4.1 集合及其表示 設(shè)a為任一個(gè)對(duì)象，A為任意一個(gè)集合，則在a和A之間有且僅有下列兩種情況中一個(gè)出現(xiàn)：a為A元素，記作“aA”，并稱(chēng)為“a屬于A”或“A含有a”；a不為A元素，記作“aA”，并稱(chēng)“a不屬于A”。 當(dāng)a1A，a2A，.，anA時(shí)，常簡(jiǎn)寫(xiě)為a1，a2，.，anA。第12頁(yè)第12頁(yè)4.1 集合及其表示

6、定義4.1 設(shè)A為任一集合，用|A|(或#A)表示A含有不同元素個(gè)數(shù)，也稱(chēng)為集合A基數(shù)，有： （1）若|A|=0，則稱(chēng)A為空集合，記為； （2）若A包含所討論問(wèn)題全部元素，則稱(chēng)A為全集合，記為U； （3）若|A|0，則稱(chēng)A為非空集合； （4）若|A|為某自然數(shù)，則稱(chēng)A為有限集合； （5）若|A|為無(wú)窮，則稱(chēng)A為無(wú)限集合。第13頁(yè)第13頁(yè)4.1 集合及其表示4.1.2 集合表示辦法 1. 列舉法 這種辦法是將集合中元素一一列舉出來(lái)，或者列出足夠多元素以反應(yīng)集合中組員特性，并用花括號(hào)將元素括起來(lái)，其表示形如 Aa1，a2，an 或 A =a1，a2，a3, 比如， A=a,b,c,d,x,y,z，

7、B=0,1,2,3,4,5,6,7,8,9就是用列舉法表示集合。第14頁(yè)第14頁(yè)4.1 集合及其表示2. 描述法 這種辦法是用一個(gè)條件來(lái)描述集合中元素含有共同性質(zhì)。這個(gè)條件能夠是一句話或一個(gè)或多個(gè)表示方式。其表示形式如 A =x P(x) 或 A =x：P(x) 其中P(x)表示“x滿(mǎn)足性質(zhì)P”或“x含有性質(zhì)P”。 比如，前面列出慣用集合N和Nm，能夠用列舉法分別表示為 N=n|n是自然數(shù) Nm=n|nN且0nm第15頁(yè)第15頁(yè)4.1 集合及其表示 例4.2 設(shè)全集合是整數(shù)集I，試用列舉法表示集合 A=x|x-10 x-240且-5x6 解 A=-1,0,1,2,3,4,5,6 第16頁(yè)第16

8、頁(yè)4.1 集合及其表示4.1.3 集合之間關(guān)系 關(guān)于集合概念，尚有一點(diǎn)需要闡明，經(jīng)常有一些集合，其元素本身也是集合。比如A=1,2,3,4等，對(duì)于這種情形，主要是把集合a和元素a區(qū)別開(kāi)來(lái)，如集合3是集合A元素，而3不是A元素。第17頁(yè)第17頁(yè)4.1 集合及其表示 定義4.2 設(shè)A，B為任意兩個(gè)集合，則有： （1）對(duì)于每個(gè)aA皆有aB，那么稱(chēng)A為B子集或B包括A，也稱(chēng)B為A母集，記作AB或BA。 （2）若AB且BA，則稱(chēng)A和B相等，記作A=B；不然，稱(chēng)A和B不相等，并記作AB。 （3）若AB且AB，則稱(chēng)A為B真子集或B真包括A，記作AB或BA。第18頁(yè)第18頁(yè)4.1 集合及其表示 比如 設(shè)A=a

9、,b,c,B=a,b,c,d,C=a,b,則 AB, CA, CBACBabcdefghij第19頁(yè)第19頁(yè)4.1 集合及其表示 定理4.1 設(shè)A，B和C為任意三個(gè)集合，則有 （1）A； （2）AA； （3）若AB且BC，則AC； （4）若AB且BC，則AC。 定理4.2 空集是惟一。第20頁(yè)第20頁(yè)4.1 集合及其表示 練習(xí) 設(shè)A=a,b,c,a,a,b，試指出下列論斷是否正確？ (1)aA ( ) (8)bA ( ) (2)aA ( ) (9)a,bA ( ) (3)aA ( ) (10)a,bA ( ) (4)A ( ) (11)cA ( ) (5)A ( ) (12)cA ( ) (6

10、)bA ( ) (13)cA ( ) (7)bA ( ) (14)a,b,cA ( )第21頁(yè)第21頁(yè)4.1 集合及其表示 例4.3 列出集合A=1,2所有子集。 解 由于是任何集合子集，因此是A子集。由A中任意一個(gè)元素所構(gòu)成集合是A子集，因此1和2是A子集。由A中任意兩個(gè)元素所構(gòu)成集合是A子集，因此1,2是A子集。由于A中只有兩個(gè)元素，故A再?zèng)]有其它子集。 由上可知，A有四個(gè)子集：，1，2，1,2。 第22頁(yè)第22頁(yè)4.1 集合及其表示 例4.4 設(shè)有集合A,B,C和D, 下述論斷是否正確？闡明理由。 （1）若AB,BC,則AC 解 正確。由于BC，因此集合B每一個(gè)元素也是集合C元素，由AB

11、知A是B一個(gè)元素，因此A也是C一個(gè)元素，故AC。 （2）若AB,BC,則AC 解 錯(cuò)誤。舉反比如下：設(shè)A=a，B=a,b，C=a,b,c，顯然AB，BC，但A不是C子集。由于aA，但aC。 第23頁(yè)第23頁(yè)4.1 集合及其表示 （3）若AB,BC,則AC （4）若AB,BC,則AC 解 （3）和（4）都是錯(cuò)誤。舉反比如下：設(shè)A=a，B=a,b，C=a,b,c。顯然若AB，BC，但AC。由于集合C中沒(méi)有元素a。又A不是C子集，由于集合A中元素a不是C元素。 第24頁(yè)第24頁(yè)4.1 集合及其表示4.1.4 冪集 定義4.3 設(shè)A為任意集合，令P(A)=x|xA，稱(chēng)P(A)為A冪集（有時(shí)也記為2A，

12、或稱(chēng)為冪集公理）。 從定義中可看出，集合A冪集事實(shí)上是以A所有子集為元素構(gòu)成集合。第25頁(yè)第25頁(yè)4.1 集合及其表示例4.5 求下列集合冪集。 （1）A= ； （2）B=； （3）C=,； （4）D=a,b,c。解（1）P(A)=； （2）P(B)=,； （3）P(C)=,； （4）P(D)=,a,b,c,a,b,a,c,b,c,a,b,c。 第26頁(yè)第26頁(yè)4.1 集合及其表示定理4.3 若A為有限集，則|P(A)|=2|A| 。 定理4.4 設(shè)A，B為任意兩個(gè)集合，則有（1）P(A)；（2）AP(A)；（3）若AB，則P(A)P(B)。第27頁(yè)第27頁(yè)4.1 集合及其表示 練習(xí) 證實(shí)：對(duì)

13、任意集合S，有 ,PPP(S)。 證實(shí)： S P(S) 又P(S) PP(S) 又 P(S) PP(S) ,PP(S) ,PPP(S)第28頁(yè)第28頁(yè)4.1 集合及其表示悖論 比如 羅素悖論，設(shè)：A=S|S是集合，且SS，則A不是集合。 證實(shí)：用反證法，設(shè)A是集合，則有且僅有下列兩情況之一出現(xiàn)， (1)AA，則由A定義知AA； (2)AA，則由A定義知AA。 因此，總有AA當(dāng)且僅當(dāng)AA，這是一個(gè)矛盾，從而A不是集合。第29頁(yè)第29頁(yè)4.1 集合及其表示 思考1 在一個(gè)小鎮(zhèn)上，有一個(gè)剪發(fā)師公開(kāi)宣布：他給并且只給小鎮(zhèn)上所有不給自己剪發(fā)人剪發(fā)，現(xiàn)在要問(wèn)：這位剪發(fā)師頭由誰(shuí)來(lái)理？ 分析： (1)假如剪發(fā)

14、師頭由別人給他理，即剪發(fā)師自己不給自己剪發(fā)，那么按要求這位剪發(fā)師頭應(yīng)當(dāng)由自己理； (2)假如剪發(fā)師頭由他自己理，按要求他只給那些不給自己剪發(fā)人剪發(fā)，那么剪發(fā)師頭不能由他自己理，即剪發(fā)師頭應(yīng)當(dāng)由別人給他理； 這就產(chǎn)生了矛盾：剪發(fā)師頭既不能由別人理，也不能由自己理，這位剪發(fā)師要求是一個(gè)悖論。第30頁(yè)第30頁(yè)4.1 集合及其表示 思考2(“鱷魚(yú)兩難”)一條鱷魚(yú)從一位母親手中搶走了一個(gè)小孩，鱷魚(yú)對(duì)孩子母親說(shuō)：“請(qǐng)你回答，我會(huì)不會(huì)吃掉你孩子？答對(duì)了，我就把孩子不加傷害地還給你；不然，就別怪我不客氣了！”聰明母親機(jī)智地回答說(shuō)：“你是要吃掉我孩子。”試問(wèn)鱷魚(yú)是否能把孩子還給母親？ 分析： 假如鱷魚(yú)交回孩子，

15、母親就說(shuō)錯(cuò)了，母親說(shuō)錯(cuò)了，它當(dāng)然能夠吃掉孩子；可是假如它吃掉孩子，母親就說(shuō)對(duì)了，它又得把孩子毫無(wú)傷害地交還出來(lái)；無(wú)論如何，都與它自己允諾相矛盾。第31頁(yè)第31頁(yè)4.2 集合運(yùn)算4.2.1 集合運(yùn)算定義 定義4.4 設(shè)A，B為任意兩個(gè)集合。令 AB=x|xA或xB AB=x|xA和xB AB=x|xA且xB AB=x|xA或xB且xAB =(AB)-(AB) 分別稱(chēng)AB，AB，AB和AB為A與B并、交、差和對(duì)稱(chēng)差。還稱(chēng)差UA為A對(duì)于某全集U補(bǔ)集，并用A來(lái)表示。假如AB=，我們稱(chēng)A和B不相交。 第32頁(yè)第32頁(yè)4.2 集合運(yùn)算 例4.6 若取U0，1，2，3，4，5， A1，2，5，B2，4時(shí)，則

16、有 AB1，2，4，5 AB2 AB1，5 AB1，4，5 A0，3，4 B0，1，3，5第33頁(yè)第33頁(yè)4.2 集合運(yùn)算 定理4.5 設(shè)A，B和C為任意三個(gè)集合，則有 (1)AAB且BAB； (2)ABA且ABB； (3)ABA； (4)ABAB； (5)若AB，則BA； (6)若AC且BC，則ABC； (7)若AB且AC，則ABC。第34頁(yè)第34頁(yè)4.2 集合運(yùn)算 定理4.6 設(shè)A，B為任意兩個(gè)集合，則下列條件互相等價(jià)： (1)AB； (2)ABB； (3)ABA。第35頁(yè)第35頁(yè)4.2 集合運(yùn)算4.2.2 集合運(yùn)算定律 定理4.7 設(shè)A、B、C是全集合U任意子集，有： (1)等冪律 AA

17、A， AAA (2)結(jié)合律 (AB)CA(BC)， (AB)CA(BC)第36頁(yè)第36頁(yè)4.2 集合運(yùn)算 (3)互換律 ABBA， ABBA (4)分派律 A(BC)(AB)(AC)， A(BC)(AB)(AC) (5)同一律 AA， AUA (6)零一律 AUU， A第37頁(yè)第37頁(yè)4.2 集合運(yùn)算 (7)互補(bǔ)律 AAU， AA (8)吸取律 A(AB)A， A(AB)A (9)德摩根律 (AB)AB， (AB)AB U， U (10)對(duì)合律 (A)A第38頁(yè)第38頁(yè)4.2 集合運(yùn)算例4.7 證實(shí)A(B-C)=(AB)-(AC)證實(shí) （1）A(B-C)=A(BC) 定理4.5(4) =ABC

18、 結(jié)合律 （2）(AB)-(AC)=(AB)(AC) 定理4.5(4) =(AB)(AC) 德摩根律 =(ABA)(ABC) 分派律 =(ABC) 互補(bǔ)律，零一律 =ABC 同一律由（1）（2）知，A(B-C)=(AB)-(AC)。 第39頁(yè)第39頁(yè)4.2 集合運(yùn)算例4.8 證實(shí)A(BC)=(AB)(AC)證實(shí) (AB)(AC)=(AB)(AC)- (AB)(AC) =(A(BC)-(ABC) =A(BC)-(BC) =A(BC) 第40頁(yè)第40頁(yè)4.2 集合運(yùn)算 例4.9 證實(shí)對(duì)任意集合A，B，C，等式(A-B)(A-C)=A成立充要條件是ABC=。 證實(shí) (1)證必要性。 設(shè)(A-B)(A-C)=A，由于(A-B)(A-C)= (AB)(AC)=A(BC)=A(BC)= A-(BC)，因此A-(BC)=A，即對(duì)任意xA，必有xA-(BC)，因而必有xBC，因此A(BC)=ABC=。 第41頁(yè)第41頁(yè)4.2 集合運(yùn)算 (2)證充足性