1.1-集合的基本概念.ppt

1、離 散 數(shù) 學(xué) (I),主講教師：李占山 計(jì)算機(jī)樓A338 E-mail:,課程安排,本學(xué)期講課學(xué)時：64 課程性質(zhì)：必修 離散數(shù)學(xué)孫吉貴等 -高等教育出版社 參考教材: 1離散數(shù)學(xué)-學(xué)習(xí)指導(dǎo)與習(xí)題解答孫吉貴等 -高等教育出版社 2集合論與圖論耿素云編著北京大學(xué)出版社 3離散數(shù)學(xué)-精講精解精練黃健斌編著西安電子科技大學(xué)出版社,離散數(shù)學(xué)(I),第一章 集合論基礎(chǔ) 第二章 命題邏輯 第三章 一階邏輯 第四章 圖與網(wǎng)絡(luò) 第五章 數(shù)論基礎(chǔ),第一章 集合論基礎(chǔ),1.1 集合的基本概念 1.2 關(guān) 系 1.3 映 射,集合論與第三次數(shù)學(xué)危機(jī),集合是一個原始概念,最初是從分析數(shù)學(xué)中產(chǎn)生的。1854年德國數(shù)學(xué)

2、家黎曼在研究傅氏級數(shù)時，得出結(jié)論說：“若f(x)在區(qū)間上除有限個第一類間斷點(diǎn)外是連續(xù)的，則在連續(xù)點(diǎn)，函數(shù)的三角函數(shù)收斂到函數(shù)值。”這時需要考慮這些連續(xù)點(diǎn)的整體，于是人們逐漸產(chǎn)生了點(diǎn)的集合的原始概念；對于集合概念的提出，起首要作用的人物是德國大數(shù)學(xué)家康托爾，他是數(shù)學(xué)史上公認(rèn)的集合論的創(chuàng)始人。1871年，他給出集合的第一個定義，且引入點(diǎn)集的極限點(diǎn)、閉集、開集、交集、并集等概念，1874年康托爾證明了代數(shù)數(shù)與有理數(shù)集的可數(shù)性和實(shí)數(shù)集的不可數(shù)性，1878年他又引入集合“勢”的概念。 康托爾的工作具有革命性，一時難以被多數(shù)數(shù)學(xué)家接受，但數(shù)學(xué)的歷史已有結(jié)論表明康托爾的集合論是分析數(shù)學(xué)與離散數(shù)學(xué)不可或缺的有

3、力工具。為此我們來了解一下康托爾與羅素,康托爾(Cantor),康托爾簡介,康托爾(Georg Cantor)1845年出生于俄羅斯的圣彼德堡，康托爾十多歲時就對數(shù)學(xué)產(chǎn)生了濃厚的興趣。1862年他在蘇黎世開始了他的大學(xué)學(xué)習(xí)，1863年又在柏林大學(xué)繼續(xù)學(xué)習(xí)，并得到著名數(shù)學(xué)家外爾斯特拉斯、庫默爾和克羅內(nèi)克的指導(dǎo)。特別是受了外爾斯特拉斯的影響而專攻純粹數(shù)學(xué)，1866年完成了一篇數(shù)論方面的博士論文后獲得博士學(xué)位。1869年康托爾得到了哈雷大學(xué)的一個職位，1879年任哈雷大學(xué)教授。1891年，康托爾組建德國數(shù)學(xué)家聯(lián)合會，任第一任主席。1904年，倫敦皇家學(xué)會授予他最高榮譽(yù)：西爾威斯特（slvester)

4、獎?wù)隆?康托爾這個人是數(shù)學(xué)界的奇才，他為數(shù)學(xué)的新奇思路和獨(dú)特創(chuàng)造以及豐富的想象力，成為當(dāng)時數(shù)學(xué)界有爭議的人物。但最終成為后世數(shù)學(xué)家學(xué)習(xí)與敬仰的模范?？低袪柕睦蠋熆肆_內(nèi)克是個“有窮論者”，他反對康托爾的“超窮數(shù)”的集合論觀點(diǎn)，他不僅對康托爾的學(xué)術(shù)工作粗暴攻擊，還竭力阻止康托爾去柏林大學(xué)工作，由于克羅內(nèi)克的權(quán)威地位，使得其他數(shù)學(xué)家也跟著攻擊康托爾的工作，使康托爾試圖在柏林大學(xué)得到一個更高待遇的計(jì)劃受挫。1918年死于精神病診所。,康托爾最著名的著作是1895-1897年出版的超窮理論基礎(chǔ)（兩卷集），康托爾指出，數(shù)學(xué)理論必須肯定實(shí)無窮，因?yàn)楹芏嘧罨镜臄?shù)學(xué)性質(zhì)，例如一切正整數(shù)，圓周上的一切點(diǎn)等，事實(shí)

5、上都是實(shí)無窮性的概念。而且不能把能有窮所具有的性質(zhì)強(qiáng)加于無窮。他的“一一對應(yīng)”的原理突破了傳統(tǒng)的“整體大于部分”的舊觀念，例如全體正整數(shù)與（其部分）全體正偶數(shù)一一對應(yīng)，正整數(shù)集與正偶數(shù)集等勢，相當(dāng)于傳統(tǒng)上的“個數(shù)相等”。 康托爾的集合論現(xiàn)在稱為樸素集合論，1871年他對集合給了一個樸素的限制寬松的定義；“把一定的并且彼此可以明確識別的事物（這種事物可以是直觀的對象，也可以是思維的對象）放在一起，稱為一個集合，這些事物中的每一個稱為該集合的一個元素。,羅素簡介,羅素（Bertrand Russell,1872-1970)生于一個以積極參與進(jìn)步運(yùn)動，熱烈地投身于自由事業(yè)而著名的英格蘭家庭。年幼就成

6、為孤兒的羅素由祖父撫養(yǎng)，并在家里接受教育。1890年他進(jìn)入劍橋的Trinity學(xué)院學(xué)習(xí)數(shù)學(xué)和論理學(xué)，并由于在幾何學(xué)方面的工作突出為他贏得了一個研究員位置。1910年Trinity學(xué)院任命他教授邏輯和數(shù)學(xué)原理的課程。羅素最偉大的工作是他提出的可以作為所有數(shù)學(xué)學(xué)科基礎(chǔ)的原理。他最著名的文章是與人合作的Principia Mathematica，這篇文章試圖用一組基本公理推導(dǎo)出所有的數(shù)學(xué)。此外，他還寫了包括哲學(xué)、物理和他的政治觀點(diǎn)的很多書籍，1950年羅素贏得諾貝爾文學(xué)獎。,大廈基兮矗云天， 數(shù)學(xué)砥柱兮兩撐竿。 集合論兮康托兒峰顛巔， 邏輯理兮舌戰(zhàn)群儒無辯。,1.1 集合的基本概念,什么是集合(Se

7、t)？ “所要討論的一類對象的整體”； “具有同一性質(zhì)單元的集體” ; “把一定的并且彼此可以明確識別的事物（這種事物可以是直觀的對象，也可以是思維的對象）放在一起，稱為一個集合。這些事物中的每一個稱為該集合的一個元素。 通常，用大寫的英文字母A, B, C,表示集合；,1、二十六個英文字母可以看成是一個集合； 2、所有的自然數(shù)看成是一個集合； 3、吉林大學(xué)計(jì)算機(jī)學(xué)院2009級的本科學(xué)生可以看成是一個集合； 4、這間教室中的所有座位可以看成是一個集合。,例如:,集合的元素(member或element),組成一個集合的那些對象或單元稱為這個集合的元素。 通常，用小寫的英文字母a, b, c,表

8、示集合中的元素,設(shè)A是一個集合，a是集合A中的元素，記以aA，讀作a屬于A；若a不是集合A中的元素，則記以aA，讀作a不屬于A。 例如：A是正偶數(shù)集合，則2A，8A，36A；而 3A，9A，17A,屬于(belong to),包含有限個元素的集合，稱為有限集或有窮集(finite set)； 包含無限個元素的集合，稱為無限集或無窮集(infinite set )。 例：所有英文字母組成的集合是有限集，整數(shù)集合是無限集。,有限集 、無限集,約定，存在一個沒有任何元素的集合，稱為空集(empty set) ，記為，有時也用來表示。 約定，所討論的對象的全體稱為全集(universal set)，記

9、作E或U，我們所討論的集合都是全集的子集 。全集是相對的。,空集、全集,設(shè)A是有窮集合， A中元素的個數(shù)稱為集合A的元素數(shù)，記為A。 例如，設(shè)A是所有英文字母組成的集合，則A=26。特別， | |=0,集合的元素數(shù),列舉法；將集合中的元素一一列舉，或列出足夠多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1,4,9,16,25,36。 描述法 ；通過描述集合中元素的共同特征來表示集合，例如： V= x|x是元音字母 ，B= x|x=a2 , a是自然數(shù),集合的表示法,文氏圖(Venn Diagram)用一個大的矩形表示全集，在矩形內(nèi)畫一些圓或其它的幾何圖形，來表示集合，有時

10、也用一些點(diǎn)來表示集合中的特定元素。 例如：集合V=a,e,i,o,u ，用文氏圖表示如下:,E,V,a,u,確定性； 互異性； 無序性； 多樣性；,集合的特征,任何一個對象，或者是這個集合的元素，或者不是，二者必居其一； 例如：A=x|x是自然數(shù)，且x100 B=x|x是年輕人 C=x|x是禿子,確定性,集合中任何兩個元素都是不同的，即集合中不允許出現(xiàn)重復(fù)的元素。 例如： 集合A=a,b,c,c,b,d，實(shí)際上，應(yīng)該是A=a,b,c,d,互異性,集合與其中的元素的順序無關(guān) 例如： 集合a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a，都是表示同一個集合。,無序性,集合中的元素可以是

11、任意的對象，相互獨(dú)立，不要求一定要具備明顯的共同特征。 例如：A=a,a,a,b,a, 1A=1,a,*,-3,a,b,x|x是汽車,地球,多樣性,設(shè)集合S=A|A是集合，且AA 若SS，則S是集合S的元素，但根據(jù)S的定義，有S S，與假設(shè)矛盾； 若SS，則S是不以自身為元素的集合，但根據(jù)S的定義，有SS，與假設(shè)矛盾；,羅素悖論(Russells paradox),當(dāng)兩個集合A和B的元素完全一樣，即A，B實(shí)際上是同一個集合時，則稱集合A，B相等，記以A=B。 例：設(shè)A=x|x是偶數(shù)，且0x10，B=2,4,6,8，則A=B。,【定義1】集合相等,設(shè)A，B是兩個集合，若A的元素都是B的元素，則稱

12、A是B的子集，也稱B包含A，或A包含于B，記以A B，或B A 。 若AB，且AB，則稱A是B的真子集(proper subset)，也稱B真包含A，或A真包含于B，記以AB，或B A 。,【定義2】子集(subset),設(shè)A=2,4,6,8 ，B= x|x是正偶數(shù)， C=x|x是整數(shù),則有A B，B C，AC,并且A B，B C，A C 。,例：,對任意集合A, 有A A。 空集是任意集合的子集，且空集是唯一的。 對于任意兩個集合A、B，A=B當(dāng)且僅當(dāng)AB且BA。,重要結(jié)論,是否存在集合A和B, 使得AB 且A B ？若存在，請舉一例。 設(shè)A=a ，B=a,a,b,c，則有:AB 且A B

13、再例如： 且 ,討論：,設(shè)A 是集合，A的所有子集為元素做成的集合稱為A的冪集，記以(A)或 2A。 (A)=S|S A 例： A=a,b,c ，則(A)=,a,b,c,a,b,a,c,b,c,a,b,c,【定義3】冪集(power set),若A為有窮集，|A|=n，則|2A | = Cn0 + Cn1 + + Cnn =2n 。 x(A)當(dāng)且僅當(dāng)xA。 設(shè)A、B是兩個集合，AB當(dāng)且僅當(dāng)(A)(B)；,冪集的性質(zhì),設(shè)C是一個集合。若C的元素都是集合，則稱C為集合族。 若集合族C可表示為C=SddD，則稱D為集合族C的標(biāo)志（索引）集。,【定義4】集合族、標(biāo)志集,顯然，2A是一個集合族。 設(shè)A1

14、, A2, A3, 是集合的序列，且兩兩之間互不相同，則集合A1, A2, A3, 是一個集合族，可表示為Ai| iN，其中,N是自然數(shù)集合，是該集合的標(biāo)志集合。,設(shè)A，B是兩個集合。所有屬于A或者屬于B的元素做成的集合，稱為A和B的并集，記以AB。即AB=x|xA或xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。,【定義5】集合的并集(Union),并集的文氏圖,A,B,AB,設(shè)A，B是兩個集合。由屬于A又屬于B的元素組成的集合，稱為A和B的交集，記以AB。即AB=x|xA且xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=c，d。,【定

15、義6】集合的交集(Intersection),交集的文氏圖,A,B,AB,設(shè)A1，A2，An是n個集合，則，A1A2An ，簡記為 A1A2An ，簡記為,并集和交集的推廣,設(shè)A1，A2，An是n個集合，則,容斥原理 (principle of inclusion-exclusion),稱為包含排斥原理，簡稱容斥原理。,設(shè)A，B是兩個集合。由屬于集合A而不屬于集合B的所有元素組成的集合，稱為A與B的差集，記以A-B，或AB。即A-B=x|xA且xB 例如，令A(yù)=a，b，c，d，B=c，d，e，f，于是A - B=a，b。,【定義7】集合的差集(Difference),差集的文氏圖,A,B,A-

16、B,E,設(shè)A是一個集合，全集E與A的差集稱為A的余集或補(bǔ)集，記以A。即A=E-A 例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。 特別，,【定義8】集合的補(bǔ)集(Complement),補(bǔ)集的文氏圖,A,A的補(bǔ)集,E,設(shè)A，B是兩個集合。則A與B的環(huán)和(對稱差),記以AB, 定義為AB=(A-B)(B-A)。 A與B的對稱差還有一個等價的定義，即AB=(AB)-(AB)。 例：令A(yù)=a，b，c，d，B=c，d，e，f，于是AB=a，b， e，f。,【定義9】集合的對稱差,對稱差的文氏圖,A,B,AB,E,設(shè)A，B是兩個集合，則A與B的環(huán)積定義為 A B = AB,【定義

17、10】集合的環(huán)積,A,B,E,我們將(a1,a2 , ,an)稱為有序n元組，其中，a1是其第一個元素， a2是其第二個元素， ，an是其第n個元素。 兩個有序n元組(a1,a2 , ,an)和(b1,b2 , ,bn)相等當(dāng)且僅當(dāng)ai=bi , i=1,2,n,【定義11】有序n元組(ordered n-tuple),對于有序n元組，當(dāng)n=2時，我們將其稱作有序二元組，也稱作有序?qū)?或序偶。 有序?qū)Φ奶攸c(diǎn)： 若ab,則(a,b)(b,a) 兩個有序?qū)?a,b)和(c,d)相等當(dāng)且僅當(dāng)a=c，b=d,【定義12】有序?qū)?ordered pairs),閱讀與欣賞 笛卡兒的夢 笛卡兒（159616

18、50年）法國著名的數(shù)學(xué)家，青年時期曾參加軍隊(duì)到荷蘭。1619年的冬天，萊茵河畔烏兒小鎮(zhèn)的軍用帳篷中。入夜， 萬簌俱靜，笛卡兒徹夜不眠，沉迷在深思之中，他望著天空，想著怎么用幾個數(shù)字來表示星星的位置呢？自己隨軍奔波，給家里去信怎么報告自己的位置呢？他完全進(jìn)入數(shù)學(xué)的世界，繼續(xù)進(jìn)行著數(shù)與形的冥想 他仿佛到了無人的曠野，他的排長站在他的面前說：“你不是想用數(shù)學(xué)來解釋自然界嗎？”排長說著抽出了兩支箭，拿在手里搭成一個十字架，箭頭一個向上，一個朝右。他將十字架舉過頭說：“你看，假如我們把天空的一部分看成是一個平面，這個天空就被分成四個部分。這兩支箭能射向無限遠(yuǎn)，天上隨便那顆星星，你只要向這兩支箭上分別引垂

19、線段，就會得到兩個數(shù)字，這星的位置就一清二楚了?！钡芽▋哼€不清楚又問道“負(fù)數(shù)又該怎樣表示呢？”排長笑道：“兩支箭的十字交叉處定為零，向上向右為正數(shù)，向下向左不就是負(fù)數(shù)了嗎？”笛卡兒高興地?fù)淞诉^去，卻撲通一聲跌入河中正在大喊，卻被人叫醒 ，天已大亮了。笛卡兒發(fā)瘋似地拿出本子和鉛筆，把夢中見到的全都畫了出來。后人傳說笛卡兒創(chuàng)立的直角坐標(biāo)系就是這樣從夢中得來的。 直角坐標(biāo)系的創(chuàng)立，為用代數(shù)方法研究幾何問題開辟了一條嶄新的道路，引起了數(shù)學(xué)的深刻革命。為了紀(jì)念笛卡兒，直角坐標(biāo)系也叫笛卡兒坐標(biāo)系。,設(shè)A，B是兩個集合，所有有序?qū)?x, y)做成的集合(其中xA，yB)，稱為A，B的直乘積(笛卡兒積)，記以AB。 AB=(x，y)xA且yB。,【定義13】笛卡兒積(Cartesian product),設(shè)A1,A2 , ,An是n個集合，由所有有序n元組(a1,a2,an)做成的集合(其中aiAi，i=1,2, ,n)，稱為