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

前言

　  回顧過去的一個世紀(jì)，數(shù)學(xué)科學(xué)的巨大發(fā)展，比以往任何時代都更牢固地確立了它作為整個科學(xué)技術(shù)領(lǐng)域的基礎(chǔ)的地位。數(shù)學(xué)正突破傳統(tǒng)的應(yīng)用范圍向幾乎所有的人類知識領(lǐng)域滲透，并越來越直接地為人類物質(zhì)生產(chǎn)與日常生活作出貢獻(xiàn)。同時，數(shù)學(xué)作為一種文化，已成為人類進(jìn)步的標(biāo)志。因此，對于當(dāng)今社會每一個有文化的人士而言，不論他從事何種職業(yè)，都需要學(xué)習(xí)數(shù)學(xué)，了解數(shù)學(xué)和運用數(shù)學(xué)?，F(xiàn)代社會對數(shù)學(xué)的這種需要，在新的世紀(jì)中無疑將更加與日俱增。20世紀(jì)數(shù)學(xué)思想的深刻變革，已將數(shù)學(xué)這門科學(xué)的核心部分引向高度抽象化的道路。面對各種深奧的數(shù)學(xué)理論和復(fù)雜的數(shù)學(xué)方法，門外漢往往只能望而卻步?！? 一個本質(zhì)上簡單的學(xué)科卻難以學(xué)習(xí)。有些困難是表面的，其一是詞匯。數(shù)學(xué)家用一些對普通人來說很生僻的詞來表達(dá)從實際事物中抽象出來的概念。如“四邊形”和“平行四邊形”有一些在其他領(lǐng)域遇不到的特定的精確含意，要研究數(shù)學(xué)就得學(xué)著用。另一個看得見的但同樣是表面的困難是使用符號。我們要解決問題，可以以某些給定的信息為基礎(chǔ)決定一個未知數(shù)。設(shè)此未知數(shù)是某一個長度以尺計的數(shù)字。用x去代表這個長度，而之后就只用符號x而不去說那么長的一句話，肯定是有利的，然而使用符號不會產(chǎn)生任何概念上的困難?！? 人們能想到的第三個困難是抽象性。但是由于基本的抽象概念是直接來自日常經(jīng)驗的，人們很容易記住它們的含義。事實上，數(shù)學(xué)家不斷地訴諸物理對象和物理圖像，以便記住這些抽象概念的含義。古希臘數(shù)學(xué)家用小石子代表各類對象，用小石子學(xué)會了自然數(shù)的基本事實。順便說一下，“計算”一詞，廣義地表示任一個算術(shù)或代數(shù)過程，它的英文Calculus的拉丁語源就是“小石子”。甚至更高級的數(shù)學(xué)抽象，如微積分學(xué)中的導(dǎo)數(shù)和積分，說到底離這些初等概念僅一步之隔，甚至微積分的概念也有圖像的物理的意義。要學(xué)會這些抽象概念，并不比學(xué)習(xí)初等概念要求更高的智力。離散數(shù)學(xué)（第2版）第1版序  數(shù)學(xué)的完全的形式是一系列概念、一系列程序，例如求解某種類型方程的方法，以及一系列事實，例如定理。當(dāng)然，程序和定理都要通過證明來確認(rèn)。要想教會人這些數(shù)學(xué)元素，最容易的方法似乎莫過于用這些概念、過程、定理與證明的最終的、確定的形式去教學(xué)生。但是數(shù)學(xué)是一門老學(xué)科，它的某些重大的成就可以追溯到公元前3000年，過去五千多年里數(shù)學(xué)家不僅極大地擴大了這個學(xué)科的領(lǐng)域，當(dāng)他們不斷認(rèn)識了新的客體和現(xiàn)象，當(dāng)他們不斷改進(jìn)自己的理解，他們也重塑了這些概念、程序與證明來把這些成就組合起來。而這些訂正了的版本中有許多就不再清晰易懂了。　  此外，數(shù)學(xué)的分量在增加，因此最好把它組織起來，使關(guān)于同一主題的許多定理有合乎邏輯的次序。每一門學(xué)科的基礎(chǔ)是公理，其后就是一串定理，每一個定理都用公理和前面已證的定理來證明。把結(jié)果按這樣的合乎邏輯的次序來安排，這就需要數(shù)學(xué)家找出新的、不甚自然的、不甚明白的證明。結(jié)果是許多證明都被除去了它們的直觀、透明和易于理解的面貌，而被十分人為的證明代替了?！? 表述上的有效性似乎導(dǎo)致數(shù)學(xué)的另一個特點被忽視了，而這個特點對于理解數(shù)學(xué)卻是至關(guān)重要的。數(shù)學(xué)本身是一副骨骼。數(shù)學(xué)的血肉和生命在于用數(shù)學(xué)做什么。有意義的數(shù)學(xué)要為一種目的服務(wù)，這種目的用笛卡兒的話來說，就是使人成為大自然的主人和占有者。數(shù)學(xué)的意義在于數(shù)學(xué)本身之外，正如好的文學(xué)作品的意義在于紙面上堆積的文字之外。要懂得數(shù)學(xué)就要知道為什么需要這個結(jié)果，它和其他結(jié)果的關(guān)系如何，用它可以做些什么事。　  學(xué)校由于它的目的和繁多的義務(wù)，有時能夠，有時又不能夠給數(shù)學(xué)一種更有啟發(fā)性的講法。有志于此的學(xué)生必須要走得遠(yuǎn)一些，尋求一種完全的知識。要對數(shù)學(xué)有較徹底的理解與領(lǐng)會，就必須去掉那些纖巧的細(xì)節(jié)，深入到其深層的思想之中；就必須知道它的目的和用處，知道創(chuàng)造它的人們的動機，以及這些概念和結(jié)構(gòu)的創(chuàng)生背景?！? 創(chuàng)造性的活動，對學(xué)生來說則是再創(chuàng)造的活動，是數(shù)學(xué)的心臟。正是在這種活動中，數(shù)學(xué)家創(chuàng)造了最高成就，克服了最大的困難并使數(shù)學(xué)這門學(xué)科取得了最有意義的進(jìn)展。創(chuàng)造過程不僅在解決已有問題時必不可少。沒有新觀點、新研究方法和新目標(biāo)的創(chuàng)造，數(shù)學(xué)就會反反復(fù)復(fù)重新組織老的證明，使它們更加嚴(yán)格，并在這樣的過程中日趨枯竭，喪失生命力。對已經(jīng)得到的知識，重新排列其步驟，安排其定理的次序來構(gòu)成一個演繹的組織，這時常需要創(chuàng)意，但從總體上說，這更像是把書本重新排一個次序。而這種創(chuàng)造的活動可以比作寫書。數(shù)學(xué)給人的滿足--獲得獵物時的興奮，發(fā)現(xiàn)的激動，成就的感覺，以及成功時的歡樂--更多更強烈的是在創(chuàng)造性的工作之中，而不是在最后按演繹的模式來重寫論證之中?！? 數(shù)學(xué)中有許多美的篇章。無疑，數(shù)學(xué)家從事數(shù)學(xué)活動也能獲得其他創(chuàng)造活動提供的滿足感，但是偉大的數(shù)學(xué)家情愿把數(shù)學(xué)的美作為一種額外報償，激勵他們奮斗的最深層的動力則是以數(shù)學(xué)為媒介在人類的探索活動中理解宇宙，也理解人類自身在其中的角色，并且探求如何利用自然現(xiàn)象和自然的力量為人類服務(wù)。那些作出巨大貢獻(xiàn)的數(shù)學(xué)家們，像阿基米德、牛頓、拉格朗日、拉普拉斯、高斯、哈密頓、龐加萊，或者是一流的物理學(xué)家，或者在科學(xué)史中占據(jù)顯要地位。這絕不是偶然的。幾乎所有數(shù)學(xué)的目的和意義并不在于對于一堆符號作一系列的邏輯闡述，而在于這些符號必定告訴我們一些關(guān)于外部世界的知識。　  離散數(shù)學(xué)是計算機科學(xué)的基礎(chǔ)　  離散數(shù)學(xué)是計算機專業(yè)最重要的必修課程之一，它是許多計算機專業(yè)課程的基礎(chǔ)?！? 離散數(shù)學(xué)是研究離散對象的數(shù)量和空間關(guān)系的數(shù)學(xué)，它包括多個數(shù)學(xué)分支，如本書所涉及到的集合論、圖論、組合數(shù)學(xué)、古典概率、自動機理論等，是計算機科學(xué)的理論基礎(chǔ)，也是計算機應(yīng)用的有力工具。另一方面，計算機科學(xué)的發(fā)展又促進(jìn)了離散數(shù)學(xué)的發(fā)展。18世紀(jì)以前的數(shù)學(xué)基本上都屬于離散數(shù)學(xué)的范疇，以后，天文學(xué)、物理學(xué)等的發(fā)展極大地推動了連續(xù)數(shù)學(xué)（如微積分）的發(fā)展，直到20世紀(jì)中期，尤其是20世紀(jì)80年代以后，隨著計算機日益滲透到現(xiàn)代社會的各個方面，離散數(shù)學(xué)又重新受到高度重視。當(dāng)然，離散數(shù)學(xué)涉及的內(nèi)容極其廣泛，其應(yīng)用全然不是僅局限于計算機科學(xué)及其應(yīng)用，而是涉及到我們生活的方方面面。　  由于數(shù)字計算機軟硬件結(jié)構(gòu)決定了它僅適于處理離散型信息的存儲與計算，因此離散數(shù)學(xué)便成為計算機科學(xué)與技術(shù)的基本數(shù)學(xué)工具。某些理論上的“先見之明”，將會給以后學(xué)科的發(fā)展帶來巨大的影響。例如，對可計算的研究所建立的圖靈機是計算機的理論模型，隨后這種理念導(dǎo)致了計算機的誕生。布爾的邏輯代數(shù)已成功地用于計算機的硬件分析與設(shè)計。謂詞邏輯演算為人工智能學(xué)科提供了一種重要的知識表示方法和推理方法。這些都體現(xiàn)了離散數(shù)學(xué)的重要作用。對于離散數(shù)學(xué)的原理和方法，經(jīng)常要求其在計算機上的可實現(xiàn)性；而一般的數(shù)學(xué)理論和方法有時僅給出存在性的結(jié)論，并不給出構(gòu)造性的問題解答，因此難以滿足實用性的要求。現(xiàn)代數(shù)字計算機的理論模型依然是20世紀(jì)30年代提出的圖靈機，這是一種“離散”的機器，可用來處理“離散”的對象。當(dāng)然，正如大多數(shù)計算機的早期應(yīng)用，通過近似計算等手段，計算機也可以處理“連續(xù)”的對象，但現(xiàn)代的數(shù)字計算機仍然是一種“離散”的機器。事實上，目前計算機已經(jīng)越來越多地用于處理各種“離散”的對象?！? 隨著計算機技術(shù)的發(fā)展，離散數(shù)學(xué)作為計算機科學(xué)的一種數(shù)學(xué)工具，其作用顯得越來越重要。對于一種程序設(shè)計語言來說，我們需要了解一些相關(guān)的問題： 為什么會提出這種語言？它能解決什么問題？優(yōu)勢是什么？存在什么問題？它的語法、語義怎么樣？利用該語言編寫的程序必然是正確的嗎？更深入的分析就是，計算機到底能做些什么？不能做些什么？什么是可計算的，什么是不可計算的，以及計算的復(fù)雜性又怎樣？只有懂得一些深刻的基礎(chǔ)性數(shù)學(xué)知識，才能對這些問題給出較為準(zhǔn)確的回答。　  離散數(shù)學(xué)為什么作為計算機專業(yè)學(xué)生的基礎(chǔ)課？美國數(shù)學(xué)會主席Lynn A。 Steen回答了該問題：But today's growth industries are dominated by information， which is abstract and immaterial。 Where the material world is modeled by calculus， the language of continuous change， the immaterial world of information requires discontinuous discrete mathematics。 Both genetic codes and computer codes are intrinsically discrete。 Discrete mathematics basically deals with fancy ways of arranging and counting。 It can be used to enumerate genetic patterns and to count the branches in computer algorithms； it can be used to analyze the treelike branching of arteries and nerves，as well as the cascading options in a succession of either-or decisions。 It can tell us how many things are there as well as help us find what we want among a bewildering morass of possibilities。　  離散數(shù)學(xué)的主要內(nèi)容　  由于數(shù)字電子計算機是一個離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系。因此無論計算機科學(xué)本身，還是與計算機科學(xué)及其應(yīng)用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨著如何對離散結(jié)構(gòu)建立數(shù)學(xué)模型又如何將已經(jīng)用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可以用計算機加工處理的問題。離散數(shù)學(xué)是數(shù)學(xué)里專門用來研究離散對象的一個數(shù)學(xué)分支，是計算機專業(yè)的一門重要的基礎(chǔ)課。它所研究的對象是離散的數(shù)量關(guān)系和離散的數(shù)學(xué)結(jié)構(gòu)模型?！? 20 世紀(jì) 70 年代，國外開始將離散數(shù)學(xué)作為一門大學(xué)課程。當(dāng)時，有一些計算機科學(xué)家根據(jù)自己對計算機科學(xué)的理解，與一些數(shù)學(xué)家一起圈定了一些他們認(rèn)為對計算機科學(xué)是必需的數(shù)學(xué)專題，結(jié)合計算機科學(xué)中的一些實例編著了一些主要命名為“離散數(shù)學(xué)結(jié)構(gòu)和方法”或“離散數(shù)學(xué)基礎(chǔ)”之類的書籍，并開設(shè)相應(yīng)的課程供大學(xué)里學(xué)習(xí)計算機專業(yè)和其他一些相關(guān)工程專業(yè)的學(xué)生選修。由于反響很好，漸漸在計算機專業(yè)中，“離散數(shù)學(xué)”即作為必修課來開設(shè)。我國是在大約 20 世紀(jì) 80 年代初期，從翻譯國外離散數(shù)學(xué)專著開始，逐漸編寫了一些適合我國教學(xué)情況的離散數(shù)學(xué)的教材，并在計算機系中開設(shè)了相應(yīng)的課程?！? 如上所述，由于各專家對于計算機的主攻方向和他們對計算機教學(xué)的理解不盡相同，因此，在“離散數(shù)學(xué)”名下的內(nèi)容也不完全一樣。本書根據(jù)ACM和IEEE/CS最新推出的Computing Curricula 2004以及教育部高等教育司組織評審?fù)ㄟ^的《中國計算機科學(xué)與技術(shù)學(xué)科教程2002》中制定的關(guān)于“離散數(shù)學(xué)”的知識結(jié)構(gòu)和體系撰寫。全書共10章，主要包含數(shù)理邏輯、集合與關(guān)系、函數(shù)、圖和樹、組合計數(shù)、數(shù)論與遞歸關(guān)系、代數(shù)系統(tǒng)、自動機、文法和語言等內(nèi)容，基本上涵蓋了計算機專業(yè)所必需的數(shù)學(xué)內(nèi)容。離散數(shù)學(xué)這門課程，主要介紹各分支的基本概念、基本理論和基本方法，這些知識將應(yīng)用于數(shù)字電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫原理、算法分析與設(shè)計、人工智能、軟件工程、計算機網(wǎng)絡(luò)等專業(yè)課程之中?！? 學(xué)習(xí)離散數(shù)學(xué)的方法　  離散數(shù)學(xué)是計算機科學(xué)系所有專業(yè)的基礎(chǔ)數(shù)學(xué)課程，一方面具有實用性（應(yīng)用數(shù)學(xué)的特征），另一方面又具有作為數(shù)學(xué)基礎(chǔ)課的理論的嚴(yán)謹(jǐn)性。所以，學(xué)習(xí)任何一個專題時，首先要精確嚴(yán)格地掌握好概念和術(shù)語，正確理解它們的內(nèi)涵和外延。因為公理、定理或定律的基石都是概念，只有正確地理解概念，才能把握定理的實質(zhì)，熟練地將公理、定理應(yīng)用于解決問題。完全地、精確地掌握一個概念的方法是首先深刻理解概念的內(nèi)涵，然后舉一些屬于和不屬于該概念外延的正反兩方面的實例。如果對一些似是而非的例子也能辨別的話，應(yīng)該說就已經(jīng)真正地理解這個概念了。對一些重要的概念，能記住一兩個實例也是很有好處的。　  讀者應(yīng)養(yǎng)成一種自覺的學(xué)習(xí)習(xí)慣，首先要掌握好基本概念和術(shù)語，然后在此基礎(chǔ)上，理解每個基本定理的本質(zhì)，最后通過學(xué)習(xí)和借鑒書中提供的例題，獨立地完成每一次作業(yè)，并且在每次作業(yè)完成之后，自覺地歸納出其中用到的基本解題方法。注意，千萬不要在完全理解相關(guān)概念和基本定理之前就匆忙去做相應(yīng)的習(xí)題?！? 學(xué)習(xí)數(shù)學(xué)的唯一途徑是實踐。就好像僅看別人怎么做，你是不可能學(xué)會彈吉他或投籃的，你也不可能僅靠閱讀本書或聽課就學(xué)好離散數(shù)學(xué)。你必須積極主動地思考。在閱讀數(shù)學(xué)書時，你應(yīng)該在手頭隨時備好筆和紙，以便進(jìn)行詳細(xì)的推導(dǎo)和計算。在聽數(shù)學(xué)課前，你最好先閱讀有關(guān)的內(nèi)容，這樣，你就可以專注于你對內(nèi)容的理解是否與教授的理解相一致，還可以就一些難點提問。本書中有很多習(xí)題，有些是純粹的計算題，有些測試對概念的理解，有些要求給出論證，建議讀者多做?！? 學(xué)習(xí)和理解術(shù)語也很重要。在數(shù)學(xué)中，傳統(tǒng)的做法是對一些簡單、常見的詞匯賦予特殊的含義，如集合、函數(shù)、關(guān)系、圖、樹、網(wǎng)絡(luò)。這些詞都有嚴(yán)格的定義，必須認(rèn)真學(xué)習(xí)，否則你就不能理解你在書中讀到的內(nèi)容和教授所講述的課程。術(shù)語能幫助你有效地與別人共享信息，而且在現(xiàn)實生活中，僅僅簡單地計算出某些東西往往不夠，還必須能夠向別人解釋，使別人確信你的解是正確的?！? 我們期待你成功地學(xué)好離散數(shù)學(xué)，并從中學(xué)到許多技術(shù)和觀點，你將會發(fā)現(xiàn)它們在許多地方都是有用的?！? 對數(shù)學(xué)和邏輯的感悟得益于我的老師們，他們是陳火旺先生、莫紹揆先生、王世強先生、康宏逵先生、齊治昌先生、胡靜婉老師、丁德成老師，也獲益于我的同學(xué)們，包括沈恩紹、宋方敏、王公寶、王懷民、王戟、王獻(xiàn)昌，如果本書有什么新意的地方，應(yīng)首先歸功于他們。　  本書第1～4章、第6章、第8～9章及附錄由賁可榮、高志華撰寫，第5， 7， 10章由袁景凌撰寫，全書由賁可榮統(tǒng)稿。在本書撰寫過程中，鐘珞教授、郭福亮教授給予了多方面的支持。武漢大學(xué)計算機學(xué)院院長何炎祥教授對全書進(jìn)行了審校，特此致謝。　  賁可榮2007年1月

內(nèi)容概要

　　離散數(shù)學(xué)是數(shù)學(xué)中專門用來研究離散對象及其關(guān)系的一個分支，是計算機科學(xué)與技術(shù)專業(yè)的一門重要基礎(chǔ)課。它所研究的對象是離散的數(shù)量關(guān)系和離散的數(shù)學(xué)結(jié)構(gòu)模型。全書共10章，主要包含數(shù)理邏輯、集合與關(guān)系、函數(shù)、組合計數(shù)、圖和樹、代數(shù)系統(tǒng)、自動機和初等數(shù)論等內(nèi)容。本書中的“歷史注記”可以幫助讀者理解數(shù)學(xué)，洞察內(nèi)在本質(zhì)。
　　《離散數(shù)學(xué)(第2版)》體系嚴(yán)謹(jǐn)，選材精煉，講解翔實，例題豐富，注重理論與計算機科學(xué)技術(shù)的實際問題相結(jié)合，書中選配了大量難度適當(dāng)?shù)牧?xí)題，并給出奇數(shù)題的答案，適合教學(xué)。本書適合作為計算機和相關(guān)專業(yè)本科生“離散數(shù)學(xué)”的教學(xué)用書，亦可作為對離散數(shù)學(xué)感興趣的人員的參考書。

書籍目錄

第1章 命題邏輯1
　1.1 現(xiàn)代邏輯學(xué)的基本研究方法1
　1.2 命題及其表示法3
　　1.2.1 命題的概念3
　　1.2.2 聯(lián)結(jié)詞4
　1.3 命題公式與語句形式化7
　　1.3.1 命題公式的定義7
　　1.3.2 公式的層次8
　　1.3.3 語句形式化8
　　1.3.4 復(fù)合命題真假值9
　　1.3.5 真值表10
　1.4 重言式11
　　1.4.1 重言式概述11
　　1.4.2 邏輯等價式13
　　1.4.3 等值演算15
　1.5 對偶與范式16
　　1.5.1 對偶16
　　1.5.2 簡單合取式和簡單析取式16
　　1.5.3 范式17
　　1.5.4 范式的唯一性--主范式19
　1.6 其他聯(lián)結(jié)詞24
　　1.6.1 n元真值函數(shù)24
　　1.6.2 真值函數(shù)與命題公式的關(guān)系25
　　1.6.3 聯(lián)結(jié)詞完備集25
　　1.6.4 單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集26
　1.7 命題演算的推理理論27
　　1.7.1 有效推理27
　　1.7.2 有效推理的等價定理29離散數(shù)學(xué)（第2版）
　　1.7.3 重言蘊涵式31
　　1.7.4 形式推理系統(tǒng)32
　　1.7.5 自然推理系統(tǒng)p235
　1.8 命題演算中的歸結(jié)推理42
　　1.8.1 歸結(jié)推理規(guī)則42
　　1.8.2 歸結(jié)反演43
　　1.8.3 命題邏輯歸結(jié)反演的合理性和完備性44
　　習(xí)題44
第2章 謂詞邏輯53
　2.1 謂詞邏輯的基本概念53
　　2.1.1 個體詞54
　　2.1.2 謂詞54
　　2.1.3 量詞55
　2.2 謂詞邏輯公式與翻譯56
　　2.2.1 一階語言56
　　2.2.2 自由與約束57
　　2.2.3 閉公式58
　　2.2.4 謂詞邏輯公式的解釋59
　　2.2.5 謂詞邏輯命題符號化60
　　2.2.6 一階公式的分類63
　2.3 謂詞邏輯等值演算64
　　2.3.1 基本等價式與置換規(guī)則64
　　2.3.2 謂詞邏輯前束范式68
　2.4 謂詞演算的推理理論69
　　2.4.1 推理定律69
　　2.4.2 量詞消去與引入規(guī)則70
　　2.4.3 一階謂詞演算公理系統(tǒng)f171
　　2.4.4 自然推理系統(tǒng)f272
　2.5 謂詞演算中的歸結(jié)推理74
　　2.5.1 子句型74
　　2.5.2 置換和合一76
　　2.5.3 合一算法78
　　2.5.4 歸結(jié)式79
　　2.5.5 歸結(jié)反演及其完備性80
　2.6 邏輯在計算機科學(xué)中的作用81
　　2.6.1 邏輯與計算81
　　2.6.2 邏輯與計算機的起源82
　　2.6.3 邏輯與程序設(shè)計83
　　習(xí)題84
第3章 集合與關(guān)系90
　3.1 集合的概念和表示法90
　　3.1.1 集合的表示90
　　3.1.2 基本概念92
　3.2 集合的運算93
　　3.2.1 集合的基本運算93
　　3.2.2 有窮計數(shù)集93
　　3.2.3 廣義交和廣義并95
　3.3 有序?qū)εc笛卡兒積97
　3.4 關(guān)系及其表示99
　　3.4.1 基本概念99
　　3.4.2 關(guān)系表示法100
　3.5 關(guān)系的運算102
　　3.5.1 基本概念102
　　3.5.2 復(fù)合關(guān)系103
　　3.5.3 逆關(guān)系104
　　3.5.4 關(guān)系冪106
　　3.5.5 冪運算的性質(zhì)107
　3.6 關(guān)系的性質(zhì)109
　　3.6.1 關(guān)系的5種基本性質(zhì)109
　　3.6.2 關(guān)系性質(zhì)的等價描述 110
　3.7 關(guān)系的閉包113
　　3.7.1 基本概念114
　　3.7.2 閉包的性質(zhì)118
　3.8 集合的劃分與覆蓋119
　3.9 等價關(guān)系和等價類120
　　3.9.1 等價關(guān)系120
　　3.9.2 等價類的性質(zhì)122
　　3.9.3 商集與劃分123
　3.10 相容關(guān)系和相容類124
　3.11 偏序關(guān)系125
　3.12 偏序集與哈斯圖126
　3.13 包含排斥原理129
　　習(xí)題130
第4章 函數(shù)137
　　4.1 函數(shù)的定義137
　　4.1.1 函數(shù)和像137
　　4.1.2 函數(shù)的性質(zhì)139
　　4.1.3 常用函數(shù)140
　　4.2 復(fù)合函數(shù)和反函數(shù)141
　　4.2.1 復(fù)合函數(shù) 141
　　4.2.2 反函數(shù)143
　　4.3 特征函數(shù)與模糊子集145
　　4.4 基數(shù)的概念147
　　4.4.1 后繼與歸納集147
　　4.4.2 自然數(shù)，有窮集，無窮集148
　　4.4.3 基數(shù)152
　　4.5 可數(shù)集與不可數(shù)集153
　　4.6 數(shù)學(xué)歸納法155
　　習(xí)題158
第5章 組合計數(shù)與離散概率162
　5.1 基本原理162
　　5.1.1 加法原理162
　　5.1.2 乘法原理163
　5.2 排列與組合164
　　5.2.1 排列164
　　5.2.2 組合164
　5.3 排列組合生成算法165
　　5.3.1 排列生成算法165
　　5.3.2 組合生成算法 166
　5.4 廣義的排列和組合169
　5.5 二項式系數(shù)和組合恒等式171
　　5.5.1 二項式定理171
　　5.5.2 組合恒等式172
　5.6 鴿籠原理174
　　5.6.1 鴿籠原理的簡單形式174
　　5.6.2 鴿籠原理的一般形式174
　5.7 遞推關(guān)系及應(yīng)用176
　　5.7.1 遞推定義函數(shù)176
　　5.7.2 遞推定義集合178
　　5.7.3 遞推關(guān)系模型179
　　5.7.4 求解遞推關(guān)系181
　　5.7.5 遞推在算法分析中的應(yīng)用183
　　5.7.6 生成函數(shù)187
　5.8 離散概率190
　　5.8.1 隨機事件與概率190
　　5.8.2 有限概率191
　　5.8.3 條件概率與獨立性 193
　　5.8.4 bayes定理194
　　習(xí)題195
第6章 圖論198
　6.1 圖的基本概念198
　　6.1.1 圖的定義和表示198
　　6.1.2 圖的同構(gòu) 202
　　6.1.3 完全圖與正則圖 204
　　6.1.4 子圖與補圖204
　　6.1.5 通路與回路206
　6.2 圖的連通性208
　　6.2.1 無向圖的連通性208
　　6.2.2 有向圖的連通性209
　6.3 圖的矩陣表示210
　　6.3.1 關(guān)聯(lián)矩陣210
　　6.3.2 有向圖的鄰接矩陣211
　　6.3.3 有向圖的可達(dá)矩陣 212
　6.4 歐拉圖213
　6.5 哈密頓圖215
　6.6 二部圖218
　　6.6.1 二部圖及判別定理218
　　6.6.2 完備匹配219
　6.7 平面圖221
　　6.7.1 平面圖及其判定定理221
　　6.7.2 平面圖的對偶圖226
　6.8 帶權(quán)圖228
　　習(xí)題229
第7章 樹及其應(yīng)用237
　7.1 概述237
　　7.1.1 樹的定義及相關(guān)術(shù)語237
　　7.1.2 樹的性質(zhì)239
　7.2 生成樹240
　7.3 最小生成樹243
　7.4 樹的遍歷246
　7.5 二叉樹248
　　7.5.1 二叉樹的性質(zhì)248
　　7.5.2 二叉搜索樹249
　　7.5.3 哈夫曼樹250
　7.6 決策樹252
　　7.6.1 決策樹的定義252
　　7.6.2 最短時間排序253
　7.7 樹的同構(gòu)254
　7.8 博弈樹258
　　7.8.1 博弈樹的概念258
　　7.8.2 極大極小分析法258
　　習(xí)題260
第8章 代數(shù)系統(tǒng)264
　8.1 二元運算及其性質(zhì)264
　　8.1.1 定義和表示 264
　　8.1.2 二元運算的性質(zhì) 266
　8.2 代數(shù)系統(tǒng)268
　　8.2.1 定義和實例268
　　8.2.2 子代數(shù)系統(tǒng)270
　　8.2.3 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)270
　8.3 半群與獨異點271
　　8.3.1 定義與性質(zhì)271
　　8.3.2 子系統(tǒng)與直積273
　8.4 群273
　　8.4.1 群的定義 273
　　8.4.2 群的性質(zhì) 275
　　8.4.3 子群的定義 278
　　8.4.4 特殊的群279
　　8.4.5 陪集與拉格朗日定理282
　　8.4.6 正規(guī)子群與商群283
　　8.4.7 群的同態(tài)與同構(gòu)實例286
　8.5 環(huán)與域288
　　8.5.1 環(huán)288
　　8.5.2 域289
　8.6 格與布爾代數(shù)290
　　8.6.1 格290
　　8.6.2 布爾代數(shù)295
　8.7 組合電路297
　　習(xí)題299
第9章 自動機、文法和語言306
　9.1 串和語言306
　9.2 形式文法307
　9.3 有限狀態(tài)機310
　9.4 有限狀態(tài)自動機312
　9.5 不確定有限狀態(tài)自動機315
　9.6 語言和自動機之間的關(guān)系318
　　習(xí)題319
第10章 初等數(shù)論322
　10.1 素數(shù)322
　10.2 最大公約數(shù)與最小公倍數(shù)323
　10.3 同余326
　10.4 一次同余方程和中國剩余定理328
　　10.4.1 一次同余方程328
　　10.4.2 中國剩余定理329
　10.5 歐拉定理和費馬小定理330
　10.6 數(shù)論在密碼學(xué)中的應(yīng)用331
　　10.6.1 公鑰密碼學(xué)331
　　10.6.2 rsa密碼332
　　習(xí)題333
附錄 歷史注記335
習(xí)題答案348
參考文獻(xiàn)370

章節(jié)摘錄

版權(quán)頁：插圖：

圖書封面

評論、評分、閱讀與下載

---

    離散數(shù)學(xué) PDF格式下載

---