《離散數(shù)學(xué)課件》1-2集合的基本概念

1、1 集合論2集合論局部第6章 集合第7章 二元關(guān)系第8章 函數(shù)3/69康托集合論公理集合論德國數(shù)學(xué)家康托 (G. Cantor) 樸素集合論: 十九世紀七十年代悖論公理集合論: 在二十世紀初數(shù)學(xué)思想的最驚人的產(chǎn)物，在純粹理性的范疇中人類活動的最美的表現(xiàn)?？赡苁沁@個時代所能夸耀的最巨大的工作。4/69康托 Georg Cantor，184519181845年3月3日生于彼得堡。1856年全家遷居法蘭克福。先后就學(xué)于蘇黎世大學(xué)、哥廷根大學(xué)、法蘭克福大學(xué)和柏林大學(xué)，主要學(xué)習哲學(xué)、數(shù)學(xué)和物理。在柏林大學(xué)，他受到著名分析學(xué)家魏爾斯特拉斯的影響，對純粹數(shù)學(xué)產(chǎn)生了興趣。1867年，他以求不定方程ax2+by

2、2+cz2= 0的整數(shù)解其中，a、b、c為任意整數(shù)的博士論文獲哲學(xué)博士學(xué)位。5/69羅素Bertrand Arthur William Russell，1872-1970著名的英國數(shù)學(xué)家、邏輯學(xué)家。1890年劍撟大學(xué)學(xué)習數(shù)學(xué)和哲學(xué)。1901年開始與懷特海(Whitehead)合作，經(jīng)過10年的奮戰(zhàn)，寫成3卷本巨著?數(shù)學(xué)原理?。羅素還是2l世紀最有影響的哲學(xué)家之一。1920年應(yīng)邀來中國講學(xué)一年。1950年獲諾貝爾文學(xué)獎。1964年創(chuàng)設(shè)羅素和平基金會。6/69理發(fā)師難題西班牙的塞維利亞有一個理發(fā)師，這位理發(fā)師有一條極為特殊的規(guī)定：他只給那些“不給自己刮胡子的人刮胡子。7/69羅素悖論與第三次數(shù)學(xué)危

3、機 “數(shù)學(xué)大廈的基石竟然出現(xiàn)了明顯的“裂縫，那么人類消耗數(shù)千年心血建立起來的“數(shù)學(xué)殿堂，會不會倒塌呢？一時間，數(shù)學(xué)界眾說紛紜，這就是數(shù)學(xué)史上著名的“第三次數(shù)學(xué)危機?！榜押? 希爾伯特 蔡梅羅: 找到擺脫困境的方法8/69ZF公理系統(tǒng)數(shù)學(xué)家們創(chuàng)造了公理化集合論，明確提出形成集合的原那么，且規(guī)定只能按照這些確定的原那么形成集合，以防止的一些集合論的悖論。最著名的一個系統(tǒng)是由蔡梅羅 (Ernst Zermelo) 1908年提出，后經(jīng)弗蘭克爾 (Abraham A. Fraenkel) 等人改進而建立的。人們稱之為ZF系統(tǒng)。9/69第二次數(shù)學(xué)危機: 關(guān)于微積分在牛頓和萊布尼茨發(fā)現(xiàn)了微積分的年代里,

4、老是有那么幾個敵對分子跟他們作對,其中有一位愛爾蘭的大主教貝克萊就譏諷牛頓的“一剎那是“已死量的幽靈。還有一位意大利的數(shù)學(xué)教授格蘭蒂把 1/2=1-1+1-1+.=(1-1)+(1-1)+.=0這樣的式子看作是從虛無創(chuàng)造萬有等等不一而足. 10/69第一次數(shù)學(xué)危機: 發(fā)現(xiàn)了“無理數(shù) 畢達格拉斯的一個弟子發(fā)現(xiàn)邊長為1的正方形的對角線是不能用任何比例來表示的。對于畢氏學(xué)派來說, 這是天大的罪過,結(jié)果被扔進海里喂了鯊魚。11/69第六章 集合6.1 集合的根本概念6.1.1 集合的定義6.1.2 集合的表示6.1.3 集合的包含關(guān)系6.1.4 集合的特點12/696.1 集合的根本概念 集合是最根本

5、的數(shù)學(xué)概念之一，由于它太根本了，所以不能用更根本的概念來定義它。集合是不能精確定義的數(shù)學(xué)概念。但是，這并不影響我們?nèi)ダ斫馑驼莆账?3/69每一個人都知道許多集合邏輯值T, F可以組成一個集合, 記為T, F , 真值集。數(shù)0，1可以組成一個集合, 記為0,1 , 真值集。 數(shù)0, 1, 2, 3, 4, 5, 6, 7, 8, 9 可以組成一個集合, 阿拉伯數(shù)字集。數(shù)0，1, 3, 4可以組成一個集合。二十六個英文字母可以組成一個集合, 英文字母集例如：14/69一、集合與元素集合：某些確定的、能夠區(qū)分的對象的聚合。元素：組成一個集合的那些對象稱為這一集合的元素和成員。用大寫字母代表集合，

6、用小寫英文字母代表集合的元素。15/69常用的集合 N代表自然數(shù)集, 0,1,2, Z代表整數(shù)集, , -2, -1, 0, 1, 2, Q代表有理數(shù)集 R代表實數(shù)集 R+=xxR, x0是表示非負的實數(shù)集 R2=(x,y) x,y R是XOY坐標平面上點的集合。16/69集合與元素的關(guān)系如果 a是集合A 的一個元素，就叫做 a屬于集合A，這時記為 aA 。如果 a不是集合A中的一個元素，就叫做a不屬于A ，這時記為aA 。對于任給的一個對象a和任給的一個集合A，或者a屬于A，或者 a不屬于A，二者必居其一，不可得兼。隸屬關(guān)系的層次結(jié)構(gòu)例 A= a, b,c, d, d b,cAb,cAdAd

7、AdA 18/69二、集合的表示(1) 列舉出這個集合中的所有元素。 A=a,b,c B=1,3,5(2) 利用元素所具有的性質(zhì)來表示。 D=x x2-3x+2=0, xR E=x x是南京理工大學(xué)學(xué)生 一般地 ，S=aa具有性質(zhì) 表示 a S當且僅當 a具有性質(zhì) 。描述法枚舉法19/69羅素(B. Russell)悖論 S=AA是不以自身為元素的集合, 即AAS是集合嗎？如果我們假定S是集合，那么 S是自己的元素， S不是自己的元素，二者居其一且只居其一。容易說明我們假定S是集合是錯誤的。如果SS，那么與性質(zhì)矛盾；如果SS，那么S滿足性質(zhì)，矛盾。20/69定義1：A,B是二個集合， 對于任意

8、的x ，假設(shè)xA ，那么 xB， 我們說集合A是集合B的子集， 也說集合B包含集合A， 記為AB 。假設(shè)A不是B的子集, 記為AB。也說B不包含A 。三、集合的包含關(guān)系21/69例1，2 1，2，31，3 1，3，2，41 1，21 1，21 1，222/69例：是否存在這樣兩個集合， 其中一個既是另一個的子集， 又是它的元素？1 1， 1 1 1， 1 23/69空集設(shè)K是一個集合， K=xRx2+1=0 。我們都知道集合 K中什么元素也沒有。這樣沒有一個元素的集合稱為空集。我們用來表示空集合。24/69命題1 (p76) A是任意集合， 是空集，那么 AA A證明： 對于任意的x，假設(shè)xA

9、, 那么顯然有xA ，所以AA. 用反證法： 假設(shè) 不包含于A，那么存在x，x ，但 xA。顯然這與是空集矛盾。故A 。25/69定義2 (p76) A, B是兩個集合， 假設(shè)AB，且BA, 那么說A與B是相等的兩個集合，記為A=B 。假設(shè)AB且AB ，說A是B 的真子集，記為AB 。26/69命題2：空集是唯一的。證明：設(shè) 1，2 是兩個空集合。 由命題1， 12 且 21 故 1 = 2 27集合之間的關(guān)系 包含子集 A B x (xA xB) 不包含 A B x (xA xB) 相等 A = B A B B A 不相等 A B 真包含 A B A B A B 不真包含 A B 注意 和

10、是不同層次的問題28/69四、集合的特點僅考慮集合所包含的不同的元素，也就是說集合中元素重復(fù)出現(xiàn)沒有意義。例如： a,a,b,c,c, a,b,c 是相等的兩個集合?；ギ愋?9/69集合的特點集合中的元素沒有任何方式的順序。例如： a,b,c c,a,b 是相等的兩個集合。無序性30/69集合的特點對集合中的元素沒有任何的限制，也就是一個集合中的元素之間彼此獨立，可以毫不相干；一個集合也可以是另一個集合的元素。例如： a, 2, 華盛頓, 中國人 a, a, 都是兩個確定的集合。確定性集合的表示方法集合的特性集合與元素的關(guān)系集合與集合的關(guān)系3132/696.2 集合的根本運算6.2.1 集合的

11、并、交、差6.2.2 集合的對稱差6.2.3 文氏圖6.2.4 集合的冪集合6.2.5 多個集合的并與交33/69并運算：ABAB=x xA或xB其元素是所有的或者屬于集合A，或者屬于集合B的元素組成。 AB34/69交運算： ABAB=x xA且xB 其元素是所有的既屬于集合A，又屬于集合B的元素組成。 AB35/69差運算：ABAB=x xA且xB其元素是所有的屬于集合A，但不屬于集合B的元素組成。 AB36/69例 設(shè)A、B是兩個任意集合，那么以下兩條件等價AB=A B A證明： 對于任意的x B, 有x AB= A， 即x (xB xA) 于是B A。 顯然， A AB 。 對于任意的

12、x AB, 那么 x A或x B， 由于B A，故總有x A， 即證得AB A。 因此AB =A。37/69例 設(shè)A、B是兩個任意集合，那么以下兩條件等價AB=BB A證明： 對于任意的x B, 有 x B=A B， 于是x A, 因此證得 B A。 顯然， AB B 。 對于任意的x B, 那么由于B A，故 x A， 從而x AB ， 即證得B AB 。 因此 AB =B。38/69集合運算性質(zhì) 定理：設(shè)A、B、C是三個任意集合，那么： 冪等律 AA=A AA=A 交換律 AB= BA AB= BA結(jié)合律 ABC=ABC ABC=ABC分配律 ABC=ABAC ABC=ABAC39/69例

13、 試證：A(BC)=(AB)(AC)證明： 1、 對于任意的x，假設(shè)x A(BC)， 那么x A，或xBC 。 當x A，那么x AB 且x AC，于是x (AB)(AC) ； 當xBC，那么xB 且xC，就有 x AB, 且x AC， 于是 x (AB)(AC) 。 故 A(BC)(AB)(AC) 2、再證明：(AB)(AC) A(BC)假設(shè)x (AB)(AC)，那么 x AB, 且x AC 由x AB 得 xA 或xB； 1由x AC 得 xA 或xC 。 2于是，當xA，有x A(BC)；當xA，由(1)和(2)， xB 且xC，有xBC ，所以x A(BC)。故 (AB)(AC) A(

14、BC)綜上知， ABC=ABAC。41/69證明： 對于任意的x， x A(BC)， x AxBC x A xB xC x A xB x A xC x AB x AC x AB x AC 例 試證：A(BC)=(AB)(AC)42/69例1 (p78) (A-B)(A-C)=A在何條件下成立？ 解： 根據(jù)分析當且僅當 A(BC)=時,等式成立。 首先，假假設(shè)(A-B)(A-C)=A, 要證明A(BC)=。 用反證法。 假設(shè)ABC, 那么xABC, 所以 xA， xB ， xC 。 由xA，xB, 有 x A-B, 又由xA，xC, 有x A-C, 所以有 x (A-B)(A-C)=A。 矛盾說

15、明ABC=。分析：A的元素a既是B的元素、也是C的元素，那么等式不成立。43/69再證，假設(shè)A(BC)=, 那么(A-B)(A-C)=A成立。1、對于任意的x(A-B)(A-C), 那么有xA-B或xA-C, 即有x A且xB,或xA且xC,于是有xA, 所以 (A-B)(A-C)A。2、對于任意的xA, 假設(shè)xB，那么有xA-B, 進而x(A-B)； 假設(shè)xB, 那么xAB，由于A(BC)=, 那么 xC, 即有xA-C, 進而x(A-B)(A-C)； 所以有A(A-B)(A-C) 。綜合得到 (A-B)(A-C)=A成立。44/69二、對稱差： AB AB=xxA且xB,或xB且xA其元素

16、是所有的或者屬于A不屬于B，或者屬于B不屬于A。 AB由定義，不難知：AB = (AB)(BA)AA = A = A45/69命題1 (p79) AB = (AB)(AB) 證明：對于任何一個x, xAB xABxBA。xA xB xB xA xA xB xA xA xB xB xB xA xA xB xB xA xA xB xB xA x AB x AB x AB x AB x (AB)(AB)46/69命題3(p79)A B C = A B C 47/69命題3(p79) A B C = A B C 證： 記P=xA且xB 且xC,Q=xB且xA 且xC,S=xC且xA 且xB,T=xA且

17、xB 且xC, 那么容易驗證： (AB)C=PQST A(BC)=PQST 所以結(jié)論得證： (AB)C=A(BC)PQST48/69例2 (p80) AB=AC，證明B=C。 證明：因為 AB=AC 所以 A(AB)= A(AC ) 從而有 AAB = AAC 即 B=C 故 B=C49/69三、冪集 定義3： A是一個集合，存在一個集合，它是由A的所有子集為元素構(gòu)成的集合， 稱它為集合A的冪集合，記為(A) ， 也記為P(A) 、2A 。即(A) = x | xA 例 設(shè)A=0,1 ，那么 (A)=,0,1,0,1 設(shè)B=a,b,c ，那么 (B)=,a,b,c,a,b,a,c,b,c, a

18、,b,c50/69 例 P() = ， P() = , P(1,2,3)=,1,2,3,1,2,3計數(shù) 如果 |A| = n，那么 |P(A)| = 2n 51/69四、有限并與交設(shè)Pi (1ik)是k個任意集合,A1A2Ak= =x | xA1xA2xAk A1A2Ak= =x|xA1xA2xAk52/69推論 (p67)設(shè)A, Pi (1ik)是k+1個集合, 那么分配率對有限并、有限交都成立。集合根本運算的定義并 AB = x | xA xB 交 AB = x | xA xB 相對補 AB = x | xA xB 對稱差 AB = (AB)(BA) = (AB)(AB) 53冪集(A)

19、= x | xA 集合的運算小結(jié)54/696.3 全集和集合的補6.3.1 全集、集合的補集6.3.2 根本運算定理55/69 一、全集定義: 我們在研究某一個具體問題時，往往規(guī)定一個集合，使所涉及的集合都是它的子集合，稱這個集合為全集， 記為U (或E )。全集是個有相對性的概念，不同的問題，可以規(guī)定不同的全集。56/69 二、補運算： 、 A 定義：設(shè)A是一個集合,U 是全集合，我們稱集合UA為A的補集，記為或A ，即有： = xxA且xU UA57/69定理1 A是一個任意集合，那么 A = A AU= A58/69定理2 A是一個任意集合，那么 A= U A = 59/69定理3 =B當且僅當AB=U且AB=證明：“ 由定理1結(jié)論成立?！?設(shè)AB=U 且AB= ，那么 B =BU =B(A)=(BA)(B) =(B) = (A) (B) =(AB)=U=任一集合的補集合是唯一的。60/69推論：設(shè)A是任意一