離散數(shù)學(xué)省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

離散數(shù)學(xué)

DiscreteMathematics主講教師：歐陽(yáng)丹彤ouyd@助課教師：劉杰liu_jie@計(jì)算機(jī)學(xué)院智能信息處理研究室第1頁(yè)離散數(shù)學(xué)是當(dāng)代數(shù)學(xué)一個(gè)主要分支，也是計(jì)算機(jī)科學(xué)與技術(shù)一級(jí)學(xué)科及其相關(guān)專業(yè)必修基礎(chǔ)理論關(guān)鍵課程。是學(xué)習(xí)后續(xù)專業(yè)課程不可缺乏數(shù)學(xué)工具。《中國(guó)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程》中將其列為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)14個(gè)知識(shí)領(lǐng)域之一。形成于七十年代早期，是伴隨計(jì)算機(jī)科學(xué)發(fā)展而逐步建立。1、課程性質(zhì)第2頁(yè)研究對(duì)象：離散量結(jié)構(gòu)及相互關(guān)系。離散量:邏輯量、圖、樹(shù)、整數(shù)、布爾代數(shù)連續(xù)量:溫度、壓力、體積、電壓——計(jì)算機(jī)中離散處理可見(jiàn)，離散數(shù)學(xué)充分描述了計(jì)算機(jī)學(xué)科離散性特點(diǎn)。離散數(shù)學(xué)是一門理論性較強(qiáng)，應(yīng)用性較廣課程。1、課程性質(zhì)第3頁(yè)掌握離散數(shù)學(xué)基本概念和基本原理離散數(shù)學(xué)所包括概念、方法和理論，大量地出現(xiàn)在“編譯原理”、“數(shù)據(jù)結(jié)構(gòu)”、“操作系統(tǒng)”、“數(shù)據(jù)庫(kù)系統(tǒng)”、“算法分析”、“定理機(jī)器證實(shí)”、“人工智能”等眾多領(lǐng)域，為學(xué)習(xí)這些課程做了必要知識(shí)準(zhǔn)備

。如：謂詞邏輯成為程序語(yǔ)義理論和程序正確性證實(shí)主要研究工具；平面圖理論被用于印刷電路板設(shè)計(jì)；圖論概念和理論廣泛用于AI、DS等；布爾代數(shù)為開(kāi)關(guān)理論研究提供了分析工具，并造成了數(shù)字邏輯理論建立；代數(shù)系統(tǒng)理論被用于對(duì)數(shù)據(jù)結(jié)構(gòu)研究，產(chǎn)生了抽象數(shù)據(jù)類型理論；代數(shù)系統(tǒng)理論成為編碼理論數(shù)學(xué)基礎(chǔ)。2、課程目標(biāo)第4頁(yè)離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)與分析、組合數(shù)學(xué)和程序設(shè)計(jì)等課程緊密相關(guān)以問(wèn)題求解步驟來(lái)詳細(xì)說(shuō)明5門課程緊密相關(guān)性：利用離散數(shù)學(xué),組合數(shù)學(xué)等知識(shí)完成待解問(wèn)題數(shù)學(xué)建模利用數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)知識(shí)選擇、結(jié)構(gòu)恰當(dāng)數(shù)據(jù)結(jié)構(gòu)，編寫很好計(jì)算機(jī)算法對(duì)算法關(guān)鍵點(diǎn)，利用離散數(shù)學(xué)、組合數(shù)學(xué)知識(shí)進(jìn)行正確性證實(shí)（此步驟是可選擇）利用算法分析、離散數(shù)學(xué)、組合數(shù)學(xué)等知識(shí)對(duì)算法進(jìn)行時(shí)空復(fù)雜性分析利用離散數(shù)學(xué)、算法設(shè)計(jì)、組合數(shù)學(xué)和運(yùn)籌學(xué)等知識(shí)對(duì)算法進(jìn)行優(yōu)化（此步驟是可選擇）(在算法基礎(chǔ)上)使用程序設(shè)計(jì)技巧編寫程序，使用程序測(cè)試技術(shù)測(cè)試程序，在計(jì)算機(jī)上完成問(wèn)題求解。第5頁(yè)數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、算法設(shè)計(jì)與分析、組合數(shù)學(xué)和程序設(shè)計(jì)等課程緊密相關(guān)

數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、算法、組合數(shù)學(xué)和匯編語(yǔ)言程序是圖靈獎(jiǎng)取得者、著名計(jì)算機(jī)科學(xué)家、數(shù)學(xué)家D.E.Knuth教授曠世之作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》主要內(nèi)容。第6頁(yè)2、課程目標(biāo)提供良好數(shù)學(xué)訓(xùn)練（1）提升邏輯思維、抽象思維能力

（2）提升嚴(yán)密推理能力

（3）提升數(shù)學(xué)語(yǔ)言描述能力（4）提升判斷對(duì)錯(cuò)能力—獨(dú)立工作能力分析問(wèn)題與處理問(wèn)題能力第7頁(yè)定義與定理多

離散數(shù)學(xué)是建立在大量定義之上邏輯推理學(xué)科，所以對(duì)概念了解是我們學(xué)習(xí)這門課程關(guān)鍵。在學(xué)習(xí)這些概念基礎(chǔ)上，要尤其注意概念之間聯(lián)絡(luò)，而描述這些聯(lián)絡(luò)實(shí)體則是大量定理與性質(zhì)。方法性強(qiáng)

離散數(shù)學(xué)許多證實(shí)題中，方法性是非常強(qiáng)，假如掌握了題證實(shí)方法，很輕易就能夠證出來(lái)，反之則事倍功半。所以在學(xué)習(xí)該課程中要善于總結(jié)，勤于思索，這也是培養(yǎng)分析問(wèn)題、處理問(wèn)題能力與抽象思維能力一個(gè)過(guò)程。

3、課程特點(diǎn)第8頁(yè)

4、怎樣學(xué)好離散數(shù)學(xué)？掌握概念：在模棱兩可地方多下功夫，弄懂、弄透。

認(rèn)真完成作業(yè)一道題做完，還要提出以下幾個(gè)問(wèn)題：（1）是否必定一定對(duì)。（2）是否有更簡(jiǎn)練方法。（3）推理是否嚴(yán)密。（4）語(yǔ)言是否流暢。第9頁(yè)5、離散數(shù)學(xué)教學(xué)內(nèi)容第一章集合論基礎(chǔ)（集合論）第二章命題邏輯第三章謂詞邏輯第四章圖與網(wǎng)絡(luò)（圖論）第五章數(shù)論基礎(chǔ)（數(shù)論）六--八章抽象代數(shù)

----離散Ⅱ數(shù)理邏輯

離散Ⅰ第10頁(yè)第一章集合論基礎(chǔ)

§1.1集合基本概念§1.2關(guān)系§1.3映射第11頁(yè)集合論發(fā)展史集合論(SetTheory)是當(dāng)代數(shù)學(xué)基礎(chǔ)．它起源可追溯到16世紀(jì)末，主要是對(duì)數(shù)集進(jìn)行卓有成效研究．集合論實(shí)際發(fā)展是由19世紀(jì)70年代德國(guó)數(shù)學(xué)家康托爾(GCantor)在無(wú)窮序列和分析相關(guān)課題理論研究中創(chuàng)建．Cantor對(duì)含有任意特征無(wú)窮集合進(jìn)行了深入探討，提出了關(guān)于基數(shù)、序數(shù)、超窮數(shù)和良序集等理論，奠定了集合論深厚基礎(chǔ)．所以，Cantor被譽(yù)為集合論創(chuàng)始人．他創(chuàng)建集合論是實(shí)數(shù)理論，以至整個(gè)微積分理論體系基礎(chǔ)。第12頁(yè)集合論創(chuàng)始人康托爾德國(guó)數(shù)學(xué)家

(GeorgCantor

1845－1918)第13頁(yè)1845年3月3日出生于俄國(guó)一個(gè)丹麥—猶太血統(tǒng)家庭。1856年與父母一起遷到德國(guó)法蘭克福。1863年進(jìn)入柏林大學(xué)，轉(zhuǎn)到純粹數(shù)學(xué)。

1866年取得博士學(xué)位。1874年在《數(shù)學(xué)雜志》上發(fā)表了關(guān)于無(wú)窮集合理論第一篇革命性文章。數(shù)學(xué)史上普通認(rèn)為這篇文章發(fā)表標(biāo)志著集合論誕生。Cantor

生平第14頁(yè)1879年任哈雷大學(xué)教授。1891年組建德國(guó)數(shù)學(xué)家聯(lián)合會(huì)，被選為第一任主席。1904年被倫敦皇家學(xué)會(huì)授予當(dāng)初數(shù)學(xué)界最高榮譽(yù)——西爾威斯特（Sylvester）獎(jiǎng)?wù)隆?/p>

第15頁(yè)1884年春天起患了嚴(yán)重憂郁癥，極度沮喪，神態(tài)不安，精神病時(shí)時(shí)發(fā)作，不得不經(jīng)常住到精神病院療養(yǎng)所去。變得很自卑，甚至懷疑自己工作是否可靠。他請(qǐng)求哈雷大學(xué)當(dāng)局把他數(shù)學(xué)教授職位改為哲學(xué)教授職位。1918年在哈雷大學(xué)從屬精神病院逝世，享年73歲。第16頁(yè)

克羅內(nèi)克（L.Kronecker

1823－1891）Cantor老師，對(duì)Cantor表現(xiàn)出了無(wú)微不至關(guān)心。他用各種用得上尖刻語(yǔ)言，粗暴地、連續(xù)不停地攻擊Cantor達(dá)十年之久。他甚至在柏林大學(xué)學(xué)生面前公開(kāi)攻擊Cantor。橫加阻撓Cantor在柏林得到一個(gè)薪金較高、聲望更大教授職位。使得Cantor想在柏林得到職位而改進(jìn)其地位任何努力都遭到挫折。

對(duì)Cantor不一樣評(píng)價(jià)第17頁(yè)法國(guó)數(shù)學(xué)家龐加萊（H.Poincare1854－1912）：我個(gè)人，而且還不只我一人，認(rèn)為主要之點(diǎn)在于，切勿引進(jìn)一些不能用有限個(gè)文字去完全定義好東西。集合論是一個(gè)有趣“病理學(xué)情形”，后一代將把（Cantor）集合論看成一個(gè)疾病，而人們已經(jīng)從中恢復(fù)過(guò)來(lái)了。第18頁(yè)德國(guó)數(shù)學(xué)家魏爾（C.H.Hermann

Weyl，1885－1955）:關(guān)于基數(shù)等級(jí)觀點(diǎn)是霧上之霧。菲利克斯.克萊因（F.Klein，1849－1925）:不贊成集合論思想。數(shù)學(xué)家H．A．施瓦茲—Cantor摯友因?yàn)榉磳?duì)集合論而同Cantor斷交。第19頁(yè)這對(duì)我來(lái)說(shuō)是最值得欽佩數(shù)學(xué)理智之花，也是在純粹理性范圍中人類活動(dòng)所取得最高成就之一。沒(méi)有些人能把我們從康托爾為我們創(chuàng)造樂(lè)園中驅(qū)趕出去。——希爾伯特超限算術(shù)是數(shù)學(xué)思想最驚人產(chǎn)物，在純粹理性范圍中人類活動(dòng)最美表現(xiàn)之一。——羅素由康托爾工作所帶來(lái)哲學(xué)革命可能甚至比數(shù)學(xué)本身還偉大?！s代因第20頁(yè)Cantor主要研究結(jié)果經(jīng)過(guò)一一對(duì)應(yīng)關(guān)系建立了集合之間等勢(shì)概念，奠定了無(wú)限集分類基礎(chǔ)。最著名著作--《超窮理論基礎(chǔ)》:數(shù)學(xué)理論必須必定實(shí)無(wú)窮，因?yàn)楹芏嘧罨緮?shù)學(xué)性質(zhì)，比如一切正整數(shù)，圓周上一切點(diǎn)等，實(shí)際上都是實(shí)無(wú)窮性概念。而且不能把有窮所含有性質(zhì)強(qiáng)加于無(wú)窮。他“一一對(duì)應(yīng)”原理突破了傳統(tǒng)“整體大于部分”舊觀念，比如全體正整數(shù)與（其部分）全體正偶數(shù)一一對(duì)應(yīng)，正整數(shù)集與正偶數(shù)集等勢(shì)。第21頁(yè)引進(jìn)了可數(shù)集概念，證實(shí)了有理數(shù)全體及代數(shù)數(shù)（有理多項(xiàng)式根）全體都是可數(shù)集合。利用對(duì)角線方法證實(shí)了實(shí)數(shù)集是不可數(shù)集，從而間接推導(dǎo)出超越數(shù)（非代數(shù)數(shù)實(shí)數(shù)）比代數(shù)數(shù)多，同時(shí)也說(shuō)明了無(wú)限集可按大小區(qū)分為不一樣類。Cantor主要研究結(jié)果第22頁(yè)Cantor主要研究結(jié)果證實(shí)了n維空間與一維直線之間存在一一對(duì)應(yīng)。系統(tǒng)研究了序數(shù)理論，提出了良序原理。證實(shí)了集冪集比原集有更大基數(shù)。提出了連續(xù)統(tǒng)假設(shè)。第23頁(yè)集合論發(fā)展史（繼續(xù)）伴隨集合論發(fā)展，以及它與數(shù)學(xué)哲學(xué)親密聯(lián)絡(luò)所作討論，1900年前后，出現(xiàn)了許多悖論，有力沖擊了或者說(shuō)動(dòng)搖了集合論發(fā)展．（數(shù)學(xué)史上三次危機(jī)

無(wú)理數(shù)發(fā)覺(jué)──第一次數(shù)學(xué)危機(jī)無(wú)窮小是零嗎？──第二次數(shù)學(xué)危機(jī)悖論產(chǎn)生——第三次數(shù)學(xué)危機(jī)）第24頁(yè)著名羅素悖論：1902年，受到“剪發(fā)師悖論”啟發(fā)而提出。

剪發(fā)師悖論：“一個(gè)剪發(fā)師宣稱，他不給自己刮臉人刮臉，但給全部不自己刮臉人刮臉。”人們問(wèn)：“剪發(fā)師先生，您自己臉誰(shuí)刮？”（悖論不是謬論，悖論中充滿著令人驚奇內(nèi)容——悖論能夠推導(dǎo)出自相矛盾結(jié)論，人們卻難以指出悖論非法理由。公元前6世紀(jì)，希臘人伊比孟德說(shuō)：“我說(shuō)這句話時(shí)正在說(shuō)謊?！币廖虇?wèn)聽(tīng)眾，他上面說(shuō)那句話是真話還是假話？該怎么回答伊翁呢？“下面句子是錯(cuò)，上面句子是正確。”問(wèn)“下面句子是錯(cuò)”為真還是為假？)第25頁(yè)伯特蘭·羅素（1872-1970）

英國(guó)著名哲學(xué)家、數(shù)學(xué)家、邏輯學(xué)家、

散文作家、社會(huì)活動(dòng)家

第26頁(yè)1872年5月，生于英國(guó)曼摩茲郡特雷克，幼年時(shí)父母雙亡，是祖母將他撫育成人。1890年進(jìn)劍橋大學(xué)三一學(xué)院學(xué)習(xí)1893年獲數(shù)學(xué)榮譽(yù)學(xué)士學(xué)位一級(jí)。接著改學(xué)哲學(xué)1894年獲道德哲學(xué)榮譽(yù)學(xué)士學(xué)位一級(jí)畢業(yè)后曾游學(xué)德國(guó)學(xué)經(jīng)濟(jì)，受馬克思主義影響，回國(guó)后，在倫敦大學(xué)政治和經(jīng)濟(jì)學(xué)院任講師。l903年發(fā)表《數(shù)學(xué)原理》一書，并以論文《幾何學(xué)基礎(chǔ)》獲三一學(xué)院研究員職位。1908年當(dāng)選為皇家學(xué)會(huì)會(huì)員。羅素生平第27頁(yè)1910年發(fā)表《哲學(xué)文集》;1917年發(fā)表《哲學(xué)問(wèn)題》。1914年加入工黨。第一次世界大戰(zhàn)期間，因參加和平主義者活動(dòng)，被處罰金，革職入獄。在獄中，撰寫了《數(shù)學(xué)哲學(xué)導(dǎo)論》（1919）。1920年訪問(wèn)中國(guó)和蘇聯(lián)，著有《布爾什維主義實(shí)踐和理論》。1920年到北大擔(dān)任客座教授，一年后離開(kāi)，隔年寫成《中國(guó)問(wèn)題》這本書。他看見(jiàn)：“中國(guó)文化正在發(fā)生急遽改變”，提出提議：“假如中國(guó)人能自由地吸收我們文明中他們所需要東西，而排斥那些他們以為不好東西，那么他們將能夠在其本身傳統(tǒng)中取得一個(gè)有機(jī)發(fā)展，并產(chǎn)生將我們優(yōu)點(diǎn)同他們自己優(yōu)點(diǎn)相結(jié)合起來(lái)輝煌成就。”第28頁(yè)1927年，羅素和夫人布拉克在英國(guó)彼得斯費(fèi)爾德市附近創(chuàng)辦一所私立學(xué)校，試驗(yàn)他教育理論，是當(dāng)初英國(guó)進(jìn)步主義學(xué)校之一。1935年離婚后，布拉克獨(dú)自辦到1939年。他一直主張“自由教育”和“愛(ài)教育”。認(rèn)為教育基本目標(biāo)是品格發(fā)展，而“活力、勇氣、敏感和智慧”是形成“理想品格”基礎(chǔ)；并深信經(jīng)過(guò)對(duì)兒童身體、感情和智力上“恰當(dāng)處理”，能夠使這些品質(zhì)得到普遍培養(yǎng)。第29頁(yè)1931年他繼承為第三世羅素勛爵。1949年獲榮譽(yù)勛章。1950年因?yàn)樗岸喈a(chǎn)而主要哲學(xué)著作，并以此成為人道主義與自由思想代言人”而取得了該年度諾貝爾文學(xué)獎(jiǎng)。

第30頁(yè)

50年代因主動(dòng)參加世界和平運(yùn)動(dòng)，反對(duì)核戰(zhàn)爭(zhēng)而取得世界和平獎(jiǎng)。1955年2月，愛(ài)因斯坦收到了英國(guó)著名哲學(xué)家羅素信，告訴他因?yàn)橹圃旌宋淦鞲?jìng)賽，人類前途實(shí)在令人擔(dān)心，希望以愛(ài)因斯坦為首團(tuán)結(jié)幾個(gè)著名科學(xué)家發(fā)表宣言防止毀滅人類戰(zhàn)爭(zhēng)發(fā)生。愛(ài)因斯坦在收到信后馬上回信表示：“你熟悉這些組織工作。你是將軍我是小兵。你只要發(fā)出命令，我就隨即跟從。”于是出現(xiàn)了著名《羅素―愛(ài)因斯坦宣言》除了愛(ài)因斯坦在臨終前簽字外，約里奧·居里、湯川秀樹(shù)和李諾·鮑林等多位科學(xué)家都在宣言上簽字。1961年，89歲高齡羅素參加一個(gè)核裁軍游行后被拘禁了7天。他反對(duì)越南戰(zhàn)爭(zhēng)，和薩特一起于1967年5月成立了一個(gè)民間法庭（后被稱為“羅素法庭”），揭露美國(guó)戰(zhàn)爭(zhēng)罪行。第31頁(yè)1959年，羅素發(fā)表了《西方智慧》后，開(kāi)始了《羅素自傳》創(chuàng)作，并在1967年95歲高齡之際完成了一生最優(yōu)異著作之一《羅素自傳》。

1970年2月2日逝世，一生曾四次結(jié)婚，三次離婚。第32頁(yè)《羅素自傳》序言我為何而活著

對(duì)愛(ài)情渴望，對(duì)知識(shí)追求，對(duì)人類苦難不可遏制同情心，這三種純潔但無(wú)比強(qiáng)烈激情支配著我一生。這三種激情就像颶風(fēng)一樣，在深深苦海上，肆意地把我吹來(lái)吹大，吹到瀕臨絕望邊緣。

我尋求愛(ài)情，首先因?yàn)閻?ài)情給我?guī)?lái)狂喜，它如此強(qiáng)烈以致我經(jīng)常愿意為了幾小時(shí)歡愉而犧牲生命中其它一切。我尋求愛(ài)情，其次是因?yàn)閻?ài)情解除孤寂——那是一顆震顫心，在世界邊緣，俯瞰那冰涼死寂、深不可測(cè)深淵。我尋求愛(ài)情，最終是因?yàn)樵趷?ài)情結(jié)合中，我看到圣徒和詩(shī)人們所想象天堂景象神秘縮影。這就是我所尋求，即使它對(duì)人生似乎過(guò)于美好，然而最終我還是得到了它。第33頁(yè)我以一樣熱情尋求知識(shí)，我希望了解人心靈。我希望知道星星為何閃閃發(fā)光，我試圖了解畢達(dá)哥拉斯思想威力，即數(shù)字支配著萬(wàn)物流轉(zhuǎn)。這方面我取得一些成就，然而并不多。

愛(ài)情和知識(shí)，盡其可能地把我引上天堂，不過(guò)同情心總把我?guī)Щ貕m世。痛苦呼號(hào)回聲在我心中回蕩，饑餓兒童，被壓迫者折磨受害者，被兒女視為可厭負(fù)擔(dān)無(wú)助老人以及充滿孤寂、貧窮和痛苦整個(gè)世界，都是對(duì)人類應(yīng)有生活嘲諷。我渴望減輕這些不幸，不過(guò)我無(wú)能為力，而且我自己也深受其害。

這就是我一生，我以為它值得活。假如有機(jī)會(huì)話，我還愿意再活—次。第34頁(yè)TheProloguetoBertrandRussell'sAutobiography

WhatIHaveLivedFor

Threepassions,simplebutoverwhelminglystrong,havegovernedmylife:thelongingforlove,thesearchforknowledge,andunbearablepityforthesufferingofmankind.Thesepassions,likegreatwinds,haveblownmehitherandthither,inawaywardcourse,overagreatoceanofanguish,reachingtotheveryvergeofdespair.

Ihavesoughtlove,first,becauseitbringsecstasy-ecstasysogreatthatIwouldoftenhavesacrificedalltherestoflifeforafewhoursofthisjoy.Ihavesoughtit,next,becauseitrelievesloneliness--thatterriblelonelinessinwhichoneshiveringconsciousnesslooksovertherimoftheworldintothecoldunfathomablelifelessabyss.Ihavesoughtitfinally,becauseintheunionofloveIhaveseen,inamysticminiature,theprefiguringvisionoftheheaventhatsaintsandpoetshaveimagined.ThisiswhatIsought,andthoughitmightseemtoogoodforhumanlife,thisiswhat--atlast--Ihavefound.第35頁(yè)WithequalpassionIhavesoughtknowledge.Ihavewishedtounderstandtheheartsofmen.Ihavewishedtoknowwhythestarsshine.AndIhavetriedtoapprehendthePythagoreanpowerbywhichnumberholdsswayabovetheflux.Alittleofthis,butnotmuch,Ihaveachieved.

Loveandknowledge,sofarastheywerepossible,ledupwardtowardtheheavens.Butalwayspitybroughtmebacktoearth.Echoesofcriesofpainreverberateinmyheart.Childreninfamine,victimstorturedbyoppressors,helplessoldpeopleaburdentotheirsons,andthewholeworldofloneliness,poverty,andpainmakeamockeryofwhathumanlifeshouldbe.Ilongtoalleviatethisevil,butIcannot,andItoosuffer.

Thishasbeenmylife.Ihavefounditworthliving,andwouldgladlyliveitagainifthechancewereofferedme.第36頁(yè)羅素諺語(yǔ)許多人寧愿死，也不愿思索，實(shí)際上他們也確實(shí)至死都沒(méi)有思索。我人生正是：使事業(yè)成為喜悅，使喜悅成為事業(yè)。一部分兒童有思索習(xí)慣，而教育目標(biāo)在于鏟除他們這種習(xí)慣。乞丐并不會(huì)妒忌百萬(wàn)富翁，不過(guò)他必定會(huì)妒忌收入更高乞丐。即使真相并不令人愉快，也一定要做到老實(shí)，因?yàn)檠谏w真相往往要費(fèi)更大力氣。不要為自己持獨(dú)特看法而感到害怕，因?yàn)槲覀儸F(xiàn)在所接收常識(shí)都曾是獨(dú)特看法。不用盲目地崇敬任何權(quán)威，因?yàn)槟憧偰苷业较喾礄?quán)威。凡事不要抱絕對(duì)必定態(tài)度。第37頁(yè)因?yàn)镃antor所創(chuàng)建樸素集合論產(chǎn)生了悖論，促進(jìn)了集合論公理化工作。含有代表性工作有兩個(gè)：由德國(guó)數(shù)學(xué)家策梅洛(E.Zermelo)于1908年首先建立，以后由以色列數(shù)學(xué)家弗蘭克爾(A.A.Fraenkel)，挪威數(shù)學(xué)家斯科倫(T.Skolem)與馮?諾依曼(vonNeumann)等人于20世紀(jì)20年代加以改進(jìn)ZF公理集合論系統(tǒng)，加入選擇公理系統(tǒng)成為ZFC。vonNeumann-Bernays-G?del公理系統(tǒng)，簡(jiǎn)稱NBG系統(tǒng)。教材主要介紹Cantor樸素集合論工作。第38頁(yè)集合論在計(jì)算機(jī)科學(xué)、人工智能領(lǐng)域、邏輯學(xué)及語(yǔ)言學(xué)等方面都有著主要應(yīng)用．對(duì)于從事計(jì)算機(jī)科學(xué)工作者來(lái)說(shuō)，集合論是不可缺乏理論知識(shí)，熟悉和掌握它是十分必要．第39頁(yè)§1.1集合基本概念一、基本概念什么是集合(Set)？“所要討論一類對(duì)象整體”；“含有同一性質(zhì)單元集體”“所謂集合，是指我們無(wú)意中或思想中將一些確定，彼此完全不一樣客體總和而考慮為一個(gè)整體。這些客體叫做該集合元素”通常，用大寫英文字母A,B,C,……表示集合；第40頁(yè)1、二十六個(gè)英文字母能夠看成是一個(gè)集合；2、全部自然數(shù)看成是一個(gè)集合；約定自然數(shù)包含03、吉林大學(xué)軟件學(xué)院級(jí)本科學(xué)生能夠看成是一個(gè)集合；4、這間教室中全部座位能夠看成是一個(gè)集合。比如:第41頁(yè)集合元素(member或element)組成一個(gè)集合那些對(duì)象或單元稱為這個(gè)集合元素。通常，用小寫英文字母a,b,c,…表示集合中元素第42頁(yè)設(shè)A是一個(gè)集合，a是集合A中元素，記以a

A，讀作a屬于A；若a不是集合A中元素，則記以a

A，讀作a不屬于A。比如：A是正偶數(shù)集合，則2

A，8

A，36

A；而3

A，9

A，17

A屬于(belongto)第43頁(yè)約定，存在一個(gè)沒(méi)有任何元素集合，稱為空集(emptyset)

，記為

，有時(shí)也用{}來(lái)表示。約定，所討論對(duì)象全體稱為全集(universalset)，記作E或U，我們所討論集合都是全集子集。全集是相正確?？占⑷?4頁(yè)包含有限個(gè)元素集合，稱為有限集或有窮集(finiteset)；包含無(wú)限個(gè)元素集合，稱為無(wú)限集或無(wú)窮集(infiniteset

)。例：空集是有限集，全部英文字母組成集合是有限集，整數(shù)集合是無(wú)限集。有限集、無(wú)限集

第45頁(yè)設(shè)A是有窮集合，A中元素個(gè)數(shù)稱為集合A元素?cái)?shù)，記為

A

。比如，設(shè)A是全部小寫英文字母組成集合，則

A=26。

尤其，||=0，|{}|=1集合元素?cái)?shù)（基數(shù)）第46頁(yè)列舉法（外延法）將集合中元素一一列舉，或列出足夠多元素以反應(yīng)集合中元素特征，比如：V={a,e,i,o,u}或B={1,4,9,16,25,36……}。描述法（內(nèi)涵法）經(jīng)過(guò)描述集合中元素共同特征來(lái)表示集合，比如：V={x|x是英語(yǔ)元音字母}，B={x|x=a2,a是非零整數(shù)}慣用集合表示法第47頁(yè)文氏圖(VennDiagram)

英國(guó)數(shù)學(xué)家JohnVenn提出用一個(gè)大矩形表示全集，在矩形內(nèi)畫一些圓或其它簡(jiǎn)單封閉曲線，用其內(nèi)部來(lái)表示集合，能夠用一些點(diǎn)來(lái)表示集合中特定元素。比如：集合V={a,e,i,o,u}，用文氏圖表示以下:注意：文氏圖只是示意圖，即使直觀、有利于記憶，但不用于證實(shí)。全集EVaeiou第48頁(yè)確定性；互異性；無(wú)序性；多樣性；集合特征第49頁(yè)任何一個(gè)對(duì)象，或者是這個(gè)集合元素，或者不是，二者必居其一；比如：A={x|x是自然數(shù)，且x<100} B={x|x是年輕人} C={x|x是禿子}確定性第50頁(yè)集合中任何兩個(gè)元素都是不一樣，即集合中不允許出現(xiàn)重復(fù)元素。比如：集合A={a,b,c,c,b,d}，實(shí)際上，應(yīng)該是A={a,b,c,d}互異性第51頁(yè)集合與其中元素次序無(wú)關(guān)，集合中元素是沒(méi)有次序，或者說(shuō)，我們不考慮集合中元素次序。比如：集合{a,b,c,d,e}、{d,c,e,a,b}、{e,c,d,b,a}，都是表示同一個(gè)集合。無(wú)序性第52頁(yè)集合中元素能夠是任意對(duì)象，相互獨(dú)立，不要求一定要具備顯著共同特征。比如：

A={a,{a},{{a},b},{{a}},1}

B={1,a,*,-3,{a,b},{x|x是汽車},地球,板兒磚}多樣性第53頁(yè)康托爾樸素集合論剖析康托爾集合論中許多證實(shí)便知，幾乎他所證實(shí)一切定理均能從以下三個(gè)公理得出:外延公理任意兩個(gè)集合相等，當(dāng)且僅當(dāng)它們中各個(gè)元素都是相同。抽象公理任給一個(gè)性質(zhì)，都有一個(gè)滿足該性質(zhì)對(duì)象所組成集合。選擇公理每個(gè)集合都有一個(gè)選擇函數(shù)。Note:毛病出在抽象公理上.1903年,Russel發(fā)覺(jué)“由不為本身組員這一性質(zhì)全部客體集合”會(huì)導(dǎo)出矛盾來(lái),這就是著名羅素悖論.第54頁(yè)設(shè)集合S={A|A是集合，且A

A}若S

S，則S是集合S元素，則依據(jù)S定義，有S

S，與假設(shè)矛盾；若S

S，則S是不以本身為元素集合，則依據(jù)S定義，有S

S，與假設(shè)矛盾。羅素悖論(Russell’sparadox)

第55頁(yè)當(dāng)兩個(gè)集合A和B元素完全一樣，即A，B實(shí)際上是同一個(gè)集合時(shí)，則稱集合A，B相等，記以A=B。

例：設(shè)A={x|x是偶數(shù)，且0<x<10}，B={2,4,6,8}，則A=B。{1，3，5}≠{{1，3}，5}【定義1】集合相等第56頁(yè)設(shè)A，B是兩個(gè)集合，若A元素都是B元素，則稱A是B子集，也稱B包含A，或A包含于B，記以A

B，或B

A

。若A

B，且A

B，則稱A是B真子集(propersubset)，也稱B真包含A，或A真包含于B，記以A

B，或B

A。

【定義2】子集(subset)

第57頁(yè)設(shè)A={2,4,6,8}，B={x|x是正偶數(shù)}，C={x|x是整數(shù)},則有A

B，B

C，A

C,而且A

B，BC，A

C

。{x}

A當(dāng)且僅當(dāng)xA。例：

第58頁(yè)對(duì)任意集合A,有A

A。若A

B，BC，則A

C

。對(duì)于任意兩個(gè)集合A、B，A=B當(dāng)且僅當(dāng)A

B且B

A?？占侨我饧献蛹?，是任意非空集合真子集，且空集是唯一。證實(shí)：取任意集合A，因?yàn)閤∈是恒假，故x(x∈

x∈A)是恒真，即A。（

，

，∈

{

}）主要結(jié)論第59頁(yè)是否存在集合A和B,使得A

B且AB？若存在，請(qǐng)舉一例。設(shè)A={a}，B={a,{a},b,c}，則有:

A

B且AB再比如：

{

}且

{

}討論：第60頁(yè)設(shè)A是集合，A全部子集為元素做成集合稱為A冪集，記以

(A)或2A。

(A)={S|SA}例：

A={a,b,c}，則

(A)={,{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}【定義3】?jī)缂?powerset)第61頁(yè)注意冪集合依然是集合。比如，用枚舉法寫出集合{a,b}冪集合：

正確寫法：

(A)={,{a},,{a,b}}錯(cuò)誤寫法：(A)=,{a},,{a,b}

？寫出

(

)，((

))，(((

)))第62頁(yè)若A為有窮集，|A|=n，則

|2A|=Cn0+Cn1+

…+Cnn=2n。證實(shí)：首先，集合A子集元素個(gè)數(shù)在0到n之間，基于這個(gè)事實(shí)，我們能夠從A中取0個(gè)元素組成A子集，有Cn0

個(gè)，從A中取1個(gè)元素組成A子集，有Cn1

個(gè)，以這類推，從A中取n個(gè)元素組成A子集，有Cnn

個(gè)。而且取元素個(gè)數(shù)不一樣，必定得到不一樣子集，依據(jù)加法原理，集合A一共有Cn0+Cn1+

…+Cnn個(gè)子集。冪集性質(zhì)第63頁(yè)冪集性質(zhì) 其次，要獲取集合A一個(gè)子集，那么，A中每個(gè)元素都有兩種取法，要么在這個(gè)子集中，要么不在。而且每個(gè)元素取法之間是相互獨(dú)立，互不影響，這么，我們依據(jù)乘法原理，能夠很輕易得出集合A一共有：2×2×…×2=2n個(gè)子集。第64頁(yè)冪集性質(zhì)

這么，我們就證實(shí)了 若A為有窮集，|A|=n，則

|2A|=Cn0+Cn1+

…+Cnn=2n。 注意：我們證實(shí)過(guò)程采取是“組合分析”方法，在《組合數(shù)學(xué)》中會(huì)有詳細(xì)講解。第65頁(yè)冪集性質(zhì)

2.x

(A)當(dāng)且僅當(dāng)x

A。證實(shí)：必要性，從x

(A)推出x

A。假如x

(A)，那么x是屬于A冪集合，從而x是A一個(gè)子集，即x

A。

充分性，從x

A推出x

(A)。假如x

A，那么x是A子集，而

(A)是以A全部子集為元素，這么，就有x

(A)。第66頁(yè)冪集性質(zhì)3.設(shè)A、B是兩個(gè)集合,A

B當(dāng)且僅當(dāng)

(A)

(B)。

證實(shí)：必要性，任取C

(A)，則C

A，又由A

B知，C

B，即，C

(B)，故

(A)

(B)。

充分性，任取x

A，則{x}

A，即{x}

(A)，而

(A)

(B)，故{x}

(B)，即{x}

B，故xB。所以A

B。（假如

(A)

(B)，那么A全部子集都是B子集，輕易知道A

A，則A

B。）第67頁(yè)設(shè)C是一個(gè)集合。若C元素都是集合，則稱C為集合族。若集合族C可表示為C={Sd

d

D}，則稱D為集合族C標(biāo)志（索引）集。

【定義4】集合族、標(biāo)志集第68頁(yè)顯然，2A是一個(gè)集合族。設(shè)A0,A1,A2,…是集合序列，且兩兩之間互不相同，則集合{A0,A1,A2,…}是一個(gè)集合族，可表示為{Ai|iN}，其中,N是自然數(shù)集合，是該集合標(biāo)志集合。(1)若{A1,A2,A3,…}為一個(gè)集合族，那么它索引集為N+。(2)2A是一個(gè)集合族，若將2A寫為{A0,…,A2n-1}，那么它索引集為{0,…,2n-1}。例．第69頁(yè)設(shè)A，B是兩個(gè)集合。全部屬于A或者屬于B元素做成集合，稱為A和B并集，記以A∪B。即A∪B={x|xA或xB}比如，令A(yù)={a，b，c，d}，B={c，d，e，f}，于是A∪B={a，b，c，d，e，f}。

二、集合運(yùn)算及性質(zhì)

【定義5】集合并集(Union)第70頁(yè)并集文氏圖ABA∪B第71頁(yè)設(shè)A，B是兩個(gè)集合。由屬于A且屬于B元素組成集合，稱為A和B交集，記以A∩B。即A∩B={x|xA且xB}比如，令A(yù)={a，b，c，d}，B={c，d，e，f}，于是A∩B={c，d}?！径x6】集合交集(Intersection)第72頁(yè)交集文氏圖ABA∩B第73頁(yè)設(shè)A1，A2，…，An是n個(gè)集合，則，

A1∪A2∪…∪An，簡(jiǎn)記為

A1∩A2∩…∩An，簡(jiǎn)記為并集和交集推廣(∪∩滿足結(jié)合律)第74頁(yè)設(shè)A，B是兩個(gè)集合。由屬于集合A而不屬于集合B全部元素組成集合，稱為A與B差集，記以A-B，或A\B。

即A-B={x|xA且xB}例.令A(yù)={a，b，c，d}，B={c，d，e，f}，于是A-

B={a，b}?！径x7】集合差集(Difference)第75頁(yè)差集文氏圖ABA－BE第76頁(yè)設(shè)A是一個(gè)集合，全集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)第77頁(yè)補(bǔ)集文氏圖AA補(bǔ)集E第78頁(yè)設(shè)A，B是兩個(gè)集合。則A與B環(huán)和(對(duì)稱差),記以A

B,定義為A

B=(A-B)∪(B-A)。A與B對(duì)稱差還有一個(gè)等價(jià)定義，即A

B=(A∪B)-(A∩B)。

例：令A(yù)={a，b，c，d}，B={c，d，e，f}，于是A

B={a，b，e，f}?！径x9】集合環(huán)和（對(duì)稱差）第79頁(yè)環(huán)和（對(duì)稱差）文氏圖ABA

BE第80頁(yè)設(shè)A，B是兩個(gè)集合，則A與B環(huán)積定義為

A

B=A

BA

B＝（A∩B）∪（A∪B）【定義10】集合環(huán)積第81頁(yè)環(huán)積文氏圖ABA

B=（A∩B）∪（A∪B）E第82頁(yè)將(a1,a2,…,an)稱為有序n元組，其中，a1是其第一個(gè)元素，a2是其第二個(gè)元素，…，an是其第n個(gè)元素。兩個(gè)有序n元組(a1,a2,…,an)和(b1,b2,…,bn)相等當(dāng)且僅當(dāng)ai=bi,i=1,2,…,n【定義11】有序n元組(orderedn-tuple)第83頁(yè)對(duì)于有序n元組，當(dāng)n=2時(shí)，將其稱作有序二元組，也稱作有序?qū)?，或序偶。有序正確特點(diǎn)：若a

b,則（a，b）

（b，a）兩個(gè)有序?qū)?a,b)和(c,d)相等當(dāng)且僅當(dāng)a=c，b=d【定義12】有序?qū)?orderedpairs)第84頁(yè)設(shè)A，B是兩個(gè)集合，全部有序?qū)?x,y)做成集合(其中x

A，y

B)，稱為A，B直乘積(笛卡兒積)，記以A

B。A

B={(x，y)

x

A且y

B}。【定義13】笛卡兒積(Cartesianproduct)第85頁(yè)笛卡兒(René

Descartes，1596～1650)

在數(shù)學(xué)史上，笛卡兒因與費(fèi)馬共同創(chuàng)建解析幾何而聞名于世。與此同時(shí)，笛卡兒還是一位哲學(xué)家、物理學(xué)家、生物學(xué)家，尤其在哲學(xué)上出色貢獻(xiàn)使他成為當(dāng)之無(wú)愧一代哲學(xué)大師。第86頁(yè)笛卡兒是法國(guó)人，出生于一個(gè)貴族家庭，因?yàn)轶w弱多病，養(yǎng)成了在床上讀書習(xí)慣，這使得他有更多時(shí)間獨(dú)自靜靜地思索各種關(guān)于自然、科學(xué)與人問(wèn)題。1628年，笛卡兒移居荷蘭，潛心從事哲學(xué)、數(shù)學(xué)、天文學(xué)、物理學(xué)、化學(xué)和生理學(xué)等領(lǐng)域研究。他主要著作都是在荷蘭完成，其中1637年出版《方法論》一書成為哲學(xué)經(jīng)典。這本書中3個(gè)著名附錄《幾何》、《折光》和《氣象》更奠定了笛卡兒在數(shù)學(xué)、物理和天文學(xué)中地位。第87頁(yè)在《幾何》中，笛卡兒分析了幾何學(xué)與代數(shù)學(xué)優(yōu)缺點(diǎn)，指出：希臘人幾何過(guò)多依賴于圖形，總是要尋求一些奇妙想法。代數(shù)卻完全受法則和公式控制，以致于妨礙了自由思想和創(chuàng)造。他同時(shí)看到了幾何直觀與推理優(yōu)勢(shì)和代數(shù)機(jī)械化運(yùn)算力量。于是笛卡兒著手處理這個(gè)問(wèn)題，并由此創(chuàng)建了解析幾何。1650年2月，笛卡兒在瑞典病逝。

第88頁(yè)設(shè)A1,A2,

,An是n個(gè)集合，由全部有序n元組(a1,a2,…,an)做成集合(其中ai

Ai，i=1,2,…,n)，稱為A1,A2,

,An直乘積(笛卡兒積)，記以A1

A2

An。A1

A2

An={(a1,a2,…,an)

ai

Ai，i=1,2,…,n}?！径x14】笛卡兒積推廣第89頁(yè)設(shè)A={1,2}，B={a,b,c},則A

B={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)}；

B

A={(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)}；比如：第90頁(yè)|A

B|=

A

B

；對(duì)任意集合A，有A=，

A=；直乘積運(yùn)算不滿足交換律，即ABBA；

直乘積運(yùn)算不滿足結(jié)合律，即(AB)CA(BC)直乘積性質(zhì)第91頁(yè)5.直乘積運(yùn)算對(duì)并和交運(yùn)算滿足分配律，即:

A(B∪C)=(AB)∪(AC)，

(B∪C)A=(BA)∪(CA)，

A(B∩C)=(AB)∩(AC)，(B∩C)A=(BA)∩(CA)；

6.設(shè)A，B，C，D是集合，若AC且BD，則ABCD。

第92頁(yè)等冪律：A∩A=A，A∪A=A。交換律：A∩B=B∩A，A∪B=B∪A。結(jié)合律：(A∩B)∩C=A∩(B∩C)， (A∪B)∪C=A∪(B∪C)。分配律：A∩(B∪C)=(A∩B)∪(A∩C)，A∪(B∩C)=(A∪B)∩(A∪C)。5.

吸收律：A∩(A∪B)=A，A∪(A∩B)=A。對(duì)于任意集合A,B,C有以下算律：第93頁(yè)互補(bǔ)律：DeMorgan律：

同一律： E∩A=A，

∪A=A。零一律：

∩A=

，E∪A=E。雙重否定律：第94頁(yè)證實(shí)：A∩(B∪C)=(A∩B)∪(A∩C)證實(shí)：先證A∩(B∪C)

（A∩B）∪（A∩C）。任取a∈A∩(B∪C)，則a∈A而且a∈B∪C。由a∈B∪C知，a∈B或a∈C。若a∈B，則a∈A∩B；若a∈C，則a∈A∩C。所以，a∈A∩B或a∈A∩C,即a∈(A∩B)∪(A∩C)。再證(A∩B)∩(A∩C)

A∩(B∪C)

。任取a∈(A∩B)∪(A∩C),則a∈A∩B或a∈A∩C。若a∈A∩B，則a∈A且a∈B；若a∈A∩C，則a∈A且a∈C。總之，a∈A，且a∈B或a∈C，即a∈A且a∈

B∪C，亦即a∈A∩(B∪C)。

綜上：(A∩B)∩(A∩C)=A∩(B∪C)。第95頁(yè)證實(shí)：任取，即a

A∪B，亦即a

A且a

B，于是且，故

，所以任取，即且，亦即a

A且a

B，于是a

A∪B，故 ，所以綜上，得證。證實(shí)：第96頁(yè)結(jié)論1

設(shè)A1，A2是有限集，且不相交，則

|A1∪

A2|=|A1|

+

|A2|。結(jié)論2

設(shè)A1，A2是任意有限集，則

|A1∪

A2|=|A1|

+

|A2|-|A1∩

A2|。證實(shí)：A1∪A2可表為不相交A1

和A2–A1并，于是，|A1∪

A2|=|A1|

+

|A2–

A1|。A2可表為不相交A2–

A1和A1∩

A2并，

于是|A2|=

|A2–

A1|+|A1∩

A2|。由此得：|A1∪

A2|=|A1|

+

|A2|-|A1∩

A2|。容斥原理(principleofinclusion-exclusion)第97頁(yè)結(jié)論3

設(shè)A1，A2，A3是任意有限集，則|A1∪A2∪A3|=|A1|

+

|A2|+

|A3|-|A1∩A2|-|A1