第一章集合的基本概念ppt

1、離散數(shù)學(xué)教程（集合論與圖論）,離散數(shù)學(xué)：計(jì)算機(jī)科學(xué)與技術(shù)的數(shù)學(xué)基礎(chǔ)課 內(nèi)容：集合論，圖論，組合數(shù)學(xué)，代數(shù)結(jié)構(gòu)，數(shù)理邏輯 集合論:（第1-4章） 圖論:（第5-9章） 組合數(shù)學(xué):（第10-12章）,教師介紹,教師：吳永輝 博士 副教授 簡(jiǎn)歷： 1984-1988 上海科技大學(xué)計(jì)算機(jī)系 本科 1988-1991 復(fù)旦大學(xué)計(jì)算機(jī)系 碩士 1991-2003 華東師范大學(xué)計(jì)算機(jī)系 工作 1998-2001 復(fù)旦大學(xué)計(jì)算機(jī)系 博士 2003- 復(fù)旦大學(xué)計(jì)算機(jī)系 工作 答疑E-mail: ,集合論與圖論課件制作軟件,Microsoft PowerPoint MathType Equation,集合論與圖論

2、課程大綱,課程性質(zhì)與目的 教學(xué)內(nèi)容與要求 使用教材、參考書籍 命題說明和題型,課程性質(zhì)、目的與基本要求,課程性質(zhì) 本課程講授計(jì)算機(jī)科學(xué)與技術(shù)的數(shù)學(xué)基礎(chǔ)課離散數(shù)學(xué)的部分主要內(nèi)容：集合論、圖論與組合數(shù)學(xué)初步，是計(jì)算機(jī)專業(yè)的主干課程之一。 本課程前行課程為線性代數(shù)，數(shù)學(xué)分析(上)。 課程目的 使學(xué)生掌握集合論、圖論與組合數(shù)學(xué)初步的基本內(nèi)容，并對(duì)證明的思想和方法深入理解和體會(huì)，初步培養(yǎng)學(xué)生的思維過程的數(shù)學(xué)化。,基本要求： 掌握集合論、組合學(xué)和圖論的基本概念，清楚了解引入基本概念的實(shí)際背景、各概念間相互關(guān)系；掌握基本定理以及有關(guān)理論題的證明技巧；掌握解決計(jì)數(shù)問題的基本方法和技巧；掌握?qǐng)D論中各算法設(shè)計(jì)的思

3、想、正確性證明以及算法的應(yīng)用。為進(jìn)一步學(xué)習(xí)計(jì)算機(jī)其他課程打下堅(jiān)實(shí)的基礎(chǔ)。,教學(xué)方式,本課程以課堂講授為主。,考核方式,平時(shí)作業(yè)； 集合論、組合數(shù)學(xué)和圖論3次課堂練習(xí)； 期中，期末的兩次筆試考試。,教學(xué)內(nèi)容與要求-集合論,第一章 集合的基本概念 掌握：集合的基本概念，集合的運(yùn)算。了解：集合論的悖論。掌握證明兩個(gè)集合相等的基本法和公式法。 第二章 關(guān)系 掌握：關(guān)系的性質(zhì)、運(yùn)算和關(guān)系的閉包，以及等價(jià)關(guān)系和偏序關(guān)系。了解：關(guān)系在關(guān)系數(shù)據(jù)庫(kù)中的應(yīng)用。掌握證明的類型。,第三章 函數(shù) 掌握：函數(shù)的基本概念，復(fù)合函數(shù)和逆函數(shù)。了解：集合的特征函數(shù)。 第四章 無限集 掌握：基數(shù)及基數(shù)的比較，判斷可列集與不可列集

4、的方法。了解：集合的遞歸定義。,教學(xué)內(nèi)容與要求-組合數(shù)學(xué)初步,第十章 鴿籠原理 掌握：利用鴿籠原理解決組合數(shù)學(xué)中一些存在性問題的技巧。 第十一章 排列與組合 掌握：集合的排列與組合，多重集的排列與組合等計(jì)數(shù)方法，有序劃分和無序劃分。 第十二章 生成函數(shù)與遞推關(guān)系 掌握：用生成函數(shù)和遞推關(guān)系解決組合計(jì)數(shù)問題的方法，以及求解遞推關(guān)系的生成函數(shù)方法。了解：求解遞推關(guān)系的特征根方法。,教學(xué)內(nèi)容與要求-圖論,第五章 圖的基本概念 掌握：圖的基本術(shù)語，路、回路和連通的基本概念，求最短路的算法及算法正確性證明，歐拉圖和哈密頓圖的基本概念、判別方法以及有關(guān)定理。 第六章 平面圖與圖的著色 掌握：平面圖的基本概

5、念、平面圖的特征和歐拉公式，掌握?qǐng)D的點(diǎn)著色和平面圖的面著色概念。了解：圖的邊著色概念。 第七章 樹 掌握：樹的基本性質(zhì)和生成樹、割集、有根樹的概念，求最小生成樹和最優(yōu)樹 的算法及算法的正確性證明。了解：樹的計(jì)數(shù)問題。,教學(xué)內(nèi)容與要求-圖論,第八章 連通度、網(wǎng)絡(luò)與匹配 教學(xué)時(shí)間：10學(xué)時(shí)；掌握：點(diǎn)連通度和邊連通度的基本概念，掌握最大網(wǎng)絡(luò)流算法及算法正確性證明，掌握匹配的基本概念和判別方法，掌握獨(dú)立集和覆蓋的基本概念和有關(guān)定理及證明方法。了解：佩特里網(wǎng)及其圖的表示。,使用教材,離散數(shù)學(xué)教程，朱洪等著。上?？茖W(xué)技術(shù)文獻(xiàn)出版社，1996。,參考書籍,一、基礎(chǔ) 1 Bernard Kolman, etc

6、. Discrete Mathematical Structure, Third Edition. 1997. 清華大學(xué)出版社, Prentice Hall. (中、英文版) 2 左孝凌, 李為檻, 劉永才. 離散數(shù)學(xué) 理論 分析 題解。 1988，上?？萍嘉墨I(xiàn)出版社。 3 左孝凌, 李為檻, 劉永才. 離散數(shù)學(xué)。 1988，上?？萍嘉墨I(xiàn)出版社。,二、提高 4 Kenneth H. Rosen. Discrete Mathematics and its Applications. (4th, 5th Edition). 機(jī)械工業(yè)出版社, McGraw-Hill. (中、英文版) 本書第4版是全

7、球500多所大學(xué)的指定教材，獲得了極大的成功。中文版也已被國(guó)內(nèi)大學(xué)廣泛采用為教材。第5版在前四版的基礎(chǔ)上做了大量的改進(jìn)，使其成為更有效的教學(xué)工具。,參考課件,1 Discrete Mathematics and Its Applications課件,在線學(xué)習(xí)網(wǎng)站,1北京大學(xué)計(jì)算機(jī)系離散數(shù)學(xué)教程網(wǎng)上教室 2北京郵電大學(xué)離散數(shù)學(xué)在線課件 3國(guó)立交通大學(xué)離散數(shù)學(xué)電腦輔助教學(xué)CAI（臺(tái)灣） .tw/is83039/discret/discrete.html,在線計(jì)算機(jī)和數(shù)學(xué)類書庫(kù),計(jì)算機(jī)和數(shù)學(xué)類書庫(kù) 吉林大學(xué)的“藏經(jīng)閣”elmo站: ,理論計(jì)算機(jī)科學(xué)經(jīng)典網(wǎng)站

8、,國(guó)內(nèi)： 國(guó)際： /suresh/theory/theory-home.html,命題說明和題型,1 填空題：基本概念的理解和掌握 2 判斷題：概念的掌握與應(yīng)用 3 計(jì)算、證明題：概念的綜合應(yīng)用，數(shù)學(xué)方法的運(yùn)用,集合論,集合論是現(xiàn)代數(shù)學(xué)的基礎(chǔ),它已深入到各種科學(xué)和技術(shù)領(lǐng)域中,被廣泛應(yīng)用到數(shù)學(xué)和計(jì)算機(jī)科學(xué)的各分支中去。 集合論的創(chuàng)始人：康托爾(Cantor,1845-1918)，1874年，“關(guān)于所有實(shí)代數(shù)數(shù)所成集合的一個(gè)性質(zhì)”的論文。 理論中出現(xiàn)了悖論。為解決悖論，在20世紀(jì)初開始了集合論公理學(xué)方向的研究,它是數(shù)理邏輯的中心問題之一。（本書

9、避免用集合的公理化方法，直觀地介紹樸素集合論。 ）,集合論部分提高參考書籍,沈恩紹 集論與邏輯-面向計(jì)算機(jī)科學(xué) 科學(xué)出版社 集合論部分內(nèi)容與常規(guī)教材相似，強(qiáng)調(diào)公理化,圖論,圖論提供了一個(gè)自然的結(jié)構(gòu)，由此產(chǎn)生的數(shù)學(xué)模型幾乎適合于所有科學(xué)（自然科學(xué)與社會(huì)科學(xué)）領(lǐng)域，只要這個(gè)領(lǐng)域研究的主題是“對(duì)象”與“對(duì)象”之間的關(guān)系。,圖論部分提高參考書籍,Bela Bollobas. Modern Graph Theory (現(xiàn)代圖論). 科學(xué)出版社 2) AB, BC AC; 3) AB, BC AC; 4) AB, BC AC; 5) aA, AB aB. /*集合論題集，經(jīng)典習(xí)題，集合基礎(chǔ)*/,五 定義1

10、.4（全集）：在取定一個(gè)集合U以后，對(duì)于U的任何子集而言，稱U為全集。,定理1.2： （1）A (2) AA (3) AU,1.2 集合的子集證明的方法,證明：（1）A (2) AA (3) AU （1）反證法：假設(shè)結(jié)論不成立，導(dǎo)出矛盾結(jié)果。 不是A的子集，導(dǎo)致矛盾 （2，3）基本法：由子集定義 x左x右，則左右,證明：（1）A 假設(shè)不是A的子集，則至少有一個(gè)元素x，使得x且xA。又因?yàn)槭强占?，它沒有元素，所以對(duì)任何x，必有x，導(dǎo)致矛盾。因此是集合A的子集。,反證法的證明步驟,（1）假設(shè)命題的結(jié)論不成立； （2）進(jìn)行一系列的推理； （3）推理過程中出現(xiàn)下列情況中的一種： 1）與已知條件矛盾；

11、2）與公理矛盾； 3）與已知定理矛盾； （4）由于上述矛盾的出現(xiàn)，可以斷言，原來的假定“結(jié)論不成立”是錯(cuò)誤的 （5）肯定原來命題是正確的。,反證法的思想 / 思維過程,“結(jié)論不成立”與“結(jié)論成立”必有一個(gè)正確。 “結(jié)論不成立”會(huì)導(dǎo)致出現(xiàn)錯(cuò)誤，推理過程、已知條件、公理和已知定理沒有錯(cuò)誤，惟一有錯(cuò)誤的是一開始接假定的“結(jié)論不成立”，所以“結(jié)論不可能不成立”，即“結(jié)論成立”。,1.2 集合的子集,六 定義1.5（冪集）： A的所有子集組成的集合稱為A的冪集。記為P(A)。 例 1.1（已知A，求冪集） 定理 1.3 | P(A) |=2|A| 證明方法：組合的方法,求冪集 代數(shù)法,P13 習(xí)題1.1

12、3 設(shè)A=a, a，問： (1) aP(A)? aP(A)? (2) aP(A)? aP(A)? (3) 又設(shè)A=a, b，重復(fù)(1)、(2)。 解: (1, 2)首先求P(A)，代數(shù)法： 代入：設(shè)x=a ，則A=a, x； P(A)=, a, x, a, x； 回代： P(A)=, a, a, a, a,P(A)=, a, a, a, a a P(A) a P(A) aP(A) aP(A) 同理，用代入法，設(shè)x=b ，則A=a, x； 回代： P(A)=, a, b , a, b，則a P(A)，a P(A)， aP(A)，aP(A),1.3 笛卡爾積,一 定義1.6（有序?qū)Γ?兩個(gè)對(duì)象按一

13、定次序組成一對(duì)，稱為有序?qū)?a, b)。 （a, b)=(c, d) a=c和b=d。,二 定義1.7（有序n元組） n個(gè)對(duì)象的序列a1, a2, ,an組成一組稱為有序n元組，記為(a1, a2, ,an)，其中ai稱為第i個(gè)分量。 兩個(gè)有序n元組相等每個(gè)對(duì)應(yīng)分量相等。,1.3 笛卡爾積,三定義1.8（直積） 兩個(gè)集合A和B，定義A和B的笛卡爾積為AB=(a, b) | aA, bB，又稱AB為A和B的直積。,1.3 笛卡爾積,四 定義1.9（笛卡爾積） n個(gè)集合A1, A2, , An , A1 A2An=(a1, a2, ,an) | aiAi, i=1, n。 若對(duì)所有i，Ai=A,

14、則A1 A2An記為An。,1.4 集合的運(yùn)算,一 定義1.10 (并，交，差，補(bǔ)，對(duì)稱差) (1) AB=x | xA或xB (2) AB=x | xA且xB (3) A-B=x | xA且xB (4) =U-A (5) AB=(A-B)(B-A),例 集合運(yùn)算：A=1,2,3,4,5, B=1,2,4,6, C=7,8, U=1,2,3,4,5,6, 7,8,9,10 AB=1,2,3,4,5,6, AB=1,2,4, AC=, A-B=3,5, A-C=A,1.4 集合的運(yùn)算,證明兩個(gè)集合相等，可用如下辦法： 基本法 集合相等的充要條件是兩個(gè)集合互為子集；即，左式右式，右式左式。所以證明

15、：x左式x右式；x右式x左式。 經(jīng)典實(shí)例：例1.4，例1.5，例1.6證明 理論基礎(chǔ)：定理1.1和定義1.1, 1.2 公式法 由集合運(yùn)算的基本性質(zhì)，通過推演，進(jìn)行證明。 經(jīng)典實(shí)例：例1.7，例1.8 證明 理論基礎(chǔ)：定理1.4和定義1.10,基本法,例1.4 A(BC)=(AB)(AC) 證明： 1）A(BC)(AB)(AC) 任一xA(BC)x(AB)(AC) 2）(AB)(AC)A(BC) 任一x(AB)(AC)xA(BC),基本法,例1.5 若AB, 則(AB)=A, AB=B. 證明： 1）證(AB)=A思想： (AB)A； A(AB) 2）證AB=B思想： ABB; BAB,例1.

16、6證明:,1.4 集合的運(yùn)算,三 定理1.4 (集合運(yùn)算的基本性質(zhì)) (1) 冪等律 AA=A AA=A (2) 交換律 AB=BA AB=BA (3) 結(jié)合律 A(BC)=(AB)C A(BC)=(AB)C (4) 分配律 A(BC)=(AB)(AC) A(BC)=(AB)(AC),1.4 集合的運(yùn)算,(5) 恒等律 AU=U AU=A A=A A= (6) 取補(bǔ)律,1.4 集合的運(yùn)算,(7) 雙重補(bǔ),1.4 集合的運(yùn)算,(8) 狄摩根律,證明類似于例1.4，例1.5，例1.6證明,判斷題，為真給出證明，為假給出反例： 若AB=AC，則B=C。 /*北京大學(xué)1994考研*/,解：錯(cuò)誤。 如果

17、A為空集，則有AB=AC，即使BC，原式成立。,公式法,原則： 1）根據(jù)集合運(yùn)算的定義，將集合運(yùn)算表達(dá)式中-和轉(zhuǎn)換為和； 2）將補(bǔ)運(yùn)算作用到單一集合上； 3）左式右式；右式左式；左式中間式，右式中間式； 4）根據(jù)定義1.10和定理1.4轉(zhuǎn)換,例：(AB)-C=(A-C)(B-C),例1.7 證明(AB)-(AC)=A(B-C) 證明思想：將集合運(yùn)算表達(dá)式中-轉(zhuǎn)換,例1.8 證明AB=(AB)-(AB) 證明思想：將集合運(yùn)算表達(dá)式中-和轉(zhuǎn)換,P()= . /*北京理工大學(xué)1999考研*/,判斷題，為真給出證明，為假給出反例： （1）x-x （2）(AB)C= (AC)(BC) /*(1)北京大學(xué)

18、1994考研, (2)上海交通大學(xué)2001考研*/,解：錯(cuò)誤。 x-x=x 顯然，x不成立。,冪集證明基本法、冪集的定義,證明：P(A)P(B)P(AB)，并說明等號(hào)成立的條件。 /*上海交通大學(xué)1999考研*/,判斷下式是否成立，如果成立，則證明；否則舉出反例。 P(A)P(B)=P(AB) /*上海交通大學(xué)2001考研*/,1.4 集合的運(yùn)算,四 定義1.11 (多個(gè)集合的并和交) 設(shè)集合A1, , An，定義： A1An= x | 至少有某個(gè)i，1in，xAi ，稱為A1, , An的并； A1An= x | xAi，對(duì)一切i=1,n成立，稱為A1, , An的交。,1.4 集合的運(yùn)算,

19、五、多個(gè)集合的運(yùn)算，除對(duì)并（交）的結(jié)合律、交換律成立以外，還有 (1) 分配律 B(A1A2An)=(BA1) (BA2) (BAn) B(A1 A2 An)= (BA1) (BA2)(BAn) (2) 狄摩根律,1.4 集合的運(yùn)算,六、廣義并、廣義交 1. 定義（廣義并） 設(shè)為一個(gè)集合族，稱由中全體元素的元素組成的集合成為的廣義并集，記作 ，稱為廣義并運(yùn)算符，讀作“大并”。 =x|z (z 并且xz) 例：=a, b, c, d, d, e, f =a, b, c, d, e, f.,1.4 集合的運(yùn)算,2. 定義（廣義交） 設(shè)為一個(gè)非空集合族，稱由中全體元素的公共元素組成的集合成為的廣義交

20、集，記作 ，稱為廣義交運(yùn)算符，讀作“大交”。 =x|z (如果z，則xz) 例：設(shè)=1, 2, 3, 1, a, b, 1, 6, 7 =1,3. 在廣義并與廣義交的運(yùn)算中，集合族中的元素仍看成集合族。 例，給出下列集合族： 1=a, b, c, d, 2=a, b, 3=a, 4=, , 5=a (a), 6= 1=abc, d, 1=abc, d, 2=a, b, 2=a, b, 3=a, 3=a, 4=, 4=, 5=a, 5=a, 6=, 6無意義.,設(shè), 為集合族, 試證明: (1)若, 則 ; (2)若, 則 ; (3)若, 且 , 則 ; (4)若, 則; (5)若, 則.,證明

21、: (1)對(duì)于任意的x, x, 則存在A, A并且xA, 所以A, 則x. 所以. /*證明方法:基本法*/,(2)因?yàn)? 由廣義并集定義, .,(3)由于, 所以, 故與均有意義. 對(duì)于任意的x, x當(dāng)且僅當(dāng)對(duì)于任意的y, 如果y, 則xy. 所以, 如果y, 則xy. 所以x. 所以.,(4), (5)的證明比較簡(jiǎn)單,請(qǐng)自行完成.,1.5 羅素悖論,命題：能區(qū)別真假的陳述語句。 例：我是學(xué)生。 今天不下雨。 上述兩個(gè)都是命題。因?yàn)樗鼈兌寄芘袆e真假。 例：祝你一帆風(fēng)順！ 你明天下午出去嗎？ 上述兩個(gè)都不是命題。,1.5 羅素悖論,一 悖論 一個(gè)命題Q，如果從Q為真，可以推導(dǎo)出Q為假；又從Q為

22、非真推導(dǎo)出Q為真，命題Q是一個(gè)悖論。,二 說謊悖論和理發(fā)師悖論 1，說謊悖論 我正在說謊 我們要問: 這個(gè)人是在說謊還是在講真話?,如果他在說謊, 這表明他的斷言“我正在說謊”是謊話,也就是說他在講真話。 即他說謊, 推出他是講真話(即沒有說謊)。 另一方面, 如果他講真話, 這表明他的斷言“我正在說謊”是真話, 也就是說他正說謊話, 即他講真話, 推出他在說謊(即沒有講真話)。 通過以上分析讓我們看到, 以命題出現(xiàn)的斷言“我正在說謊”就是一個(gè)悖論,因?yàn)槲覀儫o法斷言它的真?zhèn)巍?2理發(fā)師悖論 一個(gè)村上，有一個(gè)理發(fā)師宣布他給而且只給所有自己不替自己理發(fā)的人理發(fā)。 現(xiàn)在要問: 誰給這個(gè)理發(fā)師理發(fā)?,

23、如果理發(fā)師的頭由別人給他理, 也就是說理發(fā)師自己不替自己理發(fā), 那么按照規(guī)定, 這位理發(fā)師應(yīng)該給自己理發(fā)。 另一方面, 如果理發(fā)師的頭由自己理,那么按照規(guī)定, 理發(fā)師不能給自己理發(fā)。 因此上述也是一個(gè)悖論：理發(fā)師的頭由別人來理, 不行；理發(fā)師的頭由自己理, 也不行。,理發(fā)師悖論的數(shù)學(xué)化表示： 設(shè)S=自己給自己理發(fā)的人 若理發(fā)師S，即理發(fā)師是自己給自己理發(fā)的人，但由理發(fā)師所宣布的，他不該給自己理發(fā)，則理發(fā)師S； 若理發(fā)師S，即理發(fā)師不是自己給自己理發(fā)的人，但由理發(fā)師所宣布的，他應(yīng)該給自己理發(fā)，則理發(fā)師S；,羅素將理發(fā)師悖論表示為數(shù)學(xué)悖論,羅素將理發(fā)師悖論表示為數(shù)學(xué)悖論： 設(shè)S=集合A | AA，

24、問SS還是SS？顯然S。,3 悖論欣賞 古希臘哲學(xué)問題：鱷魚兩難 中國(guó)民間故事：師徒打官司 柏拉圖與蘇格拉底悖論,古希臘哲學(xué)問題：鱷魚兩難,一條鱷魚從一位母親手中搶走了一個(gè)小孩。 鱷魚對(duì)孩子的母親說：“請(qǐng)你回答，我會(huì)不會(huì)吃掉你的孩子，答對(duì)了，我就把孩子不加傷害地還給你；否則，就別怪我不客氣了！” 孩子的母親回答：“你是要吃掉我的孩子的?！?鱷魚是否將孩子還給母親？,中國(guó)民間故事：師徒打官司,一位律師收徒弟，協(xié)議規(guī)定：“學(xué)成之后，打贏一場(chǎng)官司交給律師一兩銀子，打輸一場(chǎng)官司就不交?！?弟子滿師后，打贏官司卻一直不交錢給老律師，老律師告到縣衙，和弟子打官司。 這場(chǎng)官司該如何裁決？,柏拉圖與蘇格拉底悖

25、論,柏拉圖說：“蘇格拉底老師下面的話是假話?！?蘇格拉底說：“柏拉圖上面的話是對(duì)的?！?柏拉圖、蘇格拉底二人的話是真話還是假話？,4 何謂集合？ 1897年，康托爾： 一個(gè)集合就是指我們觀察到的或者在我們思維中的一些確定的、不同事物的總體；這些事物稱為該集合的元素。,1）某些集合是集合自身的元素 如：所有不是蘋果的東西的集合 /*它本身就不是蘋果，它必須是此集合自身的元素*/ 2）問題：一個(gè)由一切不是集合本身的元素組成的集合，這個(gè)集合是它本身的元素嗎？,1.5 羅素悖論,羅素悖論 1）羅素將集合分成兩類： 一類是集合A本身是A的一個(gè)元素，即AA；如上例； 另一類是集合A本身不是A的一個(gè)元素，即

26、AA；例如26個(gè)英語字母組成的集合A，由于A本身不是一個(gè)字母，所以AA。,2）構(gòu)造一個(gè)集合S：S=A|AA，即，S是由滿足條件AA的那些A組成的一個(gè)新的集合。 問: S是不是它自己的一個(gè)元素? 即SS, 還是SS？,分析： 如果SS, 因?yàn)榧蟂由所有滿足條件AA的集合組成, 由于SS, 所以S滿足對(duì)于集合S中元素的定義，即S是集合S的元素，也就是說 SS。 如果SS, 因?yàn)镾中任一元素A都有AA, 又由于SS,根據(jù)集合S的規(guī)定，知S不是集合S的元素, 也就是說SS。,2）羅素悖論 既不是SS，也不是SS。,羅素悖論的出現(xiàn),說明樸素集合論有問題,從而使數(shù)學(xué)的基礎(chǔ)發(fā)生了動(dòng)搖（第3次數(shù)學(xué)危機(jī)）,

27、引起了一些著名數(shù)學(xué)家的極大重視。,在現(xiàn)代數(shù)學(xué)中為了防止這類悖論的出現(xiàn), 產(chǎn)生各種公理化的集合論和不同的學(xué)派： 1）蔡梅羅(Zermelo) 創(chuàng)立集合論的一個(gè)公理系統(tǒng)；經(jīng)過費(fèi)蘭克爾(A. Fraenkel)改進(jìn)，形成著名的ZF系統(tǒng)； 2）羅素也發(fā)表了他的集合論公理系統(tǒng)類型論； 3）以后，John von Nenmann, P. Bernays, Godel等相繼建立了其他類型的公理系統(tǒng)；,沈恩紹 集論與邏輯 科學(xué)出版社,經(jīng)典例題之一集合運(yùn)算,1. 某學(xué)院學(xué)生選課情況如下：260人選藝術(shù)課，208人選生物課，160選計(jì)算機(jī)課，76人選藝術(shù)與生物課，48人選藝術(shù)與計(jì)算機(jī)課，62人選生物與計(jì)算機(jī)課，3

28、0人三門全選，150人三門都不選。問 1）共有多少名學(xué)生？ 2）有多少學(xué)生選藝術(shù)與生物課，但不選計(jì)算機(jī)課？ 3）有多少學(xué)生選藝術(shù)與計(jì)算機(jī)課，但不選生物課？,經(jīng)典例題之一集合運(yùn)算,4）有多少學(xué)生選生物與計(jì)算機(jī)課，但不選藝術(shù)課？ 5）有多少學(xué)生選藝術(shù)課，但不選生物或計(jì)算機(jī)課？ 6）有多少學(xué)生選生物課，但不選藝術(shù)或計(jì)算機(jī)課？ 7）有多少學(xué)生選計(jì)算機(jī)課，但不選藝術(shù)或生物課？,集合運(yùn)算解題思想,容斥原理： 1）設(shè)A1, A2為有限集，則 |A1A2|=|A1|+|A2|-|A1A2|。 2）設(shè)A1, A2,An為有限集，則,3）設(shè)U為全集，A1, A2,An為U的有限子集，則,集合運(yùn)算解題思想,容斥原理

29、（包含排斥）應(yīng)用 1）討論的范圍是什么？即那些是全集中的元素？-某學(xué)院的學(xué)生全體構(gòu)成全集； 2）將全集中的元素進(jìn)行分類-按學(xué)生選課的情況進(jìn)行分類：選修藝術(shù)課為具有性質(zhì)PA，選修生物課為具有性質(zhì)PB，選修計(jì)算機(jī)課為具有性質(zhì)PC，具有上述性質(zhì)的集合記為A, B, C； 3）列出計(jì)算公式； 4）用文氏圖輔助運(yùn)算。,求解-按題意給出已知條件,解：設(shè)A=選修藝術(shù)課學(xué)生，B=選修生物課學(xué)生，C=選修計(jì)算機(jī)課學(xué)生。 則|A|=260, |B|=208, |C|=160, |AB|=76, |AC|=48, |BC|=62, |ABC|=30,求解-a)學(xué)生總數(shù),求解-答案,答案 a) 622 b) 46 c

30、) 18 d) 32 e) 166 f) 100 g) 80,2. 求1到250這250個(gè)整數(shù)中，至少能被2，3，5之一整除的數(shù)的個(gè)數(shù)。,解：設(shè)A, B, C表示1到250這250個(gè)整數(shù)中，能分別被2，3，5整除的數(shù)的集合。則有： |A|=125, |B|=83, |C|=50 |AB|=41, |AC|=25, |BC|=16, |ABC|=8, 那么，|ABC |=|A|+|B|+|C|-|AB|- |AC|-|BC|+|ABC|=184,3. 75名兒童到游樂場(chǎng)去玩。他們可以騎旋轉(zhuǎn)木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這3種東西都玩過，其中55人至少乘坐過其中的兩種。若每樣乘坐一次

31、的費(fèi)用是0.5元，游樂場(chǎng)總共收入70元，試用容斥原理確定，在75名兒童中有多少兒童沒有乘坐其中任何一種。,經(jīng)典例題之二證明方法,反證法 引用已知的結(jié)論來簡(jiǎn)化證明步驟 證明兩個(gè)集合相等常用的方法,證明方法1,1) 反證法。 設(shè)A為一個(gè)集合，B為A的補(bǔ)集合，則AB=。 證明：設(shè)AB，則存在非空元素xAB，故xA且xB，此與B為A的補(bǔ)集合矛盾。所以AB=。,證明方法2,2)引用已知的結(jié)論來簡(jiǎn)化證明步驟。 對(duì)任意的集合A，A。 證明： 反證法，假設(shè)存在一個(gè)集合A，使得A。即存在元素x，但xA。這與是空集矛盾。 空集合是唯一的。 證明：設(shè)1和2都是空集合，由上題， 12且2 1，則1=2。,證明方法3,3）證明兩個(gè)集合相等常用的方法 基本法，公式法 習(xí)題1.3 基本法 習(xí)題1.11 公式法,證明方法練習(xí),1）設(shè)A為一個(gè)集合，B為A的補(bǔ)集，則 AB=。 證明：反證法。設(shè)AB，則存在x AB，所以xA，并且 xB，矛盾。,證明方法練習(xí),2）證明AB=BA。 證明：分兩部分證明。首先證明左式是右式的