《離散數(shù)學及其應(yīng)用》全面系統(tǒng)地介紹了離散數(shù)學的基本理論與應(yīng)用技術(shù),內(nèi)容主要包括集合與關(guān)系理論、組合計算方法與應(yīng)用、整數(shù)與算法設(shè)計知識、數(shù)理邏輯演算與推理、圖模型的基本理論與算法、抽象代數(shù)的基礎(chǔ)知識等!峨x散數(shù)學及其應(yīng)用》注重知識的應(yīng)用性、表達的可讀性和體系的完備性,將分布在不同數(shù)學分支的離散數(shù)學知識點進行凝練和優(yōu)化,形成一套相對完備的離散數(shù)學知識體系,并且在每個章節(jié)穿插豐富的應(yīng)用實例,使得讀者在學習離散數(shù)學理論知識的同時,還能比較系統(tǒng)地掌握離散數(shù)學的應(yīng)用知識。《離散數(shù)學及其應(yīng)用》用通俗易懂的語言深入淺出地表達知識內(nèi)容,著重突出數(shù)學概念和定理的思想、本質(zhì),而不僅僅是形式化描述,使得廣大讀者能夠通過自己的努力就可以不太困難地掌握離散數(shù)學的內(nèi)容。另外,每章均配有一定數(shù)量的習題,供讀者練習。
《離散數(shù)學及其應(yīng)用》內(nèi)容豐富、思路清晰、實例講解詳細、圖例直觀形象,適合作為計算機及相關(guān)專業(yè)的本科生教材,也可供工程技術(shù)人員和自學讀者學習參考。
一般來說,科學技術(shù)的專業(yè)研究或研發(fā)需要解決如下四個層次的基本問題:首先,要有一個基本的思想或創(chuàng)意;其次,建立一套基本理論支撐這個思想或創(chuàng)意;再次,用相關(guān)的數(shù)學理論或模型來量化表示、分析這套理論;最后,根據(jù)數(shù)學理論或數(shù)學模型實現(xiàn)對若干理論問題的求解,實現(xiàn)想法或創(chuàng)意。比如說,希望人類能像鳥兒一樣在天上飛翔。這就是一個想法,從專業(yè)角度看,要實現(xiàn)這個想法就必須建立一套空氣動力學理論來論證該想法的合理性、可行性,使用數(shù)學方法實現(xiàn)對該理論的定量分析并探索問題的求解方案。具體地說,就是建立若干代數(shù)方程或微分方程實現(xiàn)對該理論的數(shù)學建模,并通過求解這些方程探索飛行器設(shè)計與制造問題的求解方案。因此,任何一門科學技術(shù)專業(yè)都有一套與之緊密相關(guān)的數(shù)學理論為其提供堅實的基礎(chǔ)和定量分析工具。
我們知道,18世紀機械工業(yè)革命的核心技術(shù)物理學、力學取得了巨大進步,而支撐物理學、力學巨大進步的基礎(chǔ)正是微積分的發(fā)明和發(fā)展。如今,我們已經(jīng)進入信息社會,信息社會的核心是計算機科學與技術(shù)。那么,作為能夠有效支撐物理學的微積分是否能有效支撐計算機科學與技術(shù)呢?很遺憾,答案是否定的。微積分雖然能夠解決計算機與信息科學的部分問題,但是不足以完全支撐整個計算機與信息科學。因為計算機系統(tǒng)本質(zhì)上是一種離散系統(tǒng),只能進行有限次計算或信息處理,而且要求所用求解方法必須是滿足規(guī)定處理效率的構(gòu)造性方法。然而,微積分以極限或無限為基礎(chǔ),在很多方面難以滿足計算機問題求解的需要。因此,對于計算機相關(guān)專業(yè)的學生來說,除了要學好微積分等現(xiàn)有工科數(shù)學之外,還必須牢固掌握與計算機專業(yè)技術(shù)緊密相關(guān)的計算機專業(yè)數(shù)學。
由于計算機是一種離散系統(tǒng),處理對象是離散量或離散化的連續(xù)量。因此,通常將計算機專業(yè)數(shù)學稱為離散數(shù)學。離散數(shù)學包含了人類在創(chuàng)造、運用和研究計算機過程中所使用的基本數(shù)學方法和數(shù)學思想,以及與這些數(shù)學問題相關(guān)的基礎(chǔ)知識。可以這樣說,正如微積分支撐了作為近代工業(yè)文明基礎(chǔ)的物理學,離散數(shù)學支撐了作為現(xiàn)代信息社會基礎(chǔ)的計算機科學與技術(shù)。事實上,學好離散數(shù)學不僅可以為計算機后續(xù)幾乎所有軟硬件專業(yè)課程奠定必需的入門知識基礎(chǔ),而且能夠培養(yǎng)出良好的邏輯思維、算法思維和抽象思維能力,為計算機科學技術(shù)的理論研究和應(yīng)用開發(fā)打下一個堅實的數(shù)學理論基礎(chǔ)。
離散數(shù)學是一門綜合數(shù)學學科,主要包括集合論、數(shù)理邏輯、圖論、數(shù)論、組合分析、代數(shù)結(jié)構(gòu)六個數(shù)學分支,分別從不同角度出發(fā)研究各種離散數(shù)學結(jié)構(gòu)、分析離散量之間數(shù)與形的關(guān)系,以充分滿足計算機相關(guān)學科對離散量進行表示和處理的數(shù)學需求。離散數(shù)學所含知識內(nèi)容廣泛,涉及多個不同的數(shù)學分支和思維方式,為廣大初學者學習和掌握離散數(shù)學知識帶來一定困難。為此,編者編寫了這本離散數(shù)學教程,以較好地滿足廣大讀者系統(tǒng)地學習和掌握離散數(shù)學知識的需要。關(guān)于本書的編寫,編者著重考慮如下三個要點:
第一,強調(diào)應(yīng)用性。一項知識有了具體的應(yīng)用,大家自然會感興趣,興趣是最好的老師和學習動力。因此,本書在每個章節(jié)穿插豐富的應(yīng)用實例,使得讀者在學習離散數(shù)學理論知識的同時,還能夠系統(tǒng)地掌握離散數(shù)學的應(yīng)用知識。
第二,強調(diào)可讀性。本書站在本科生低年級的思維角度進行編寫,在保證表達準確的前提下,盡可能用通俗易懂的語言深入淺出地介紹離散數(shù)學,著重突出數(shù)學概念和定理的思想、本質(zhì),而不僅僅是形式化描述,使得廣大讀者能夠通過自己的努力就可以不太困難地掌握離散數(shù)學的基本理論和應(yīng)用知識。
第三,強調(diào)完備性。本書旨在為整個計算機學科提供一套相對完備的基本數(shù)學理論,涵蓋集合論、數(shù)理邏輯、圖論、數(shù)論、組合分析、代數(shù)結(jié)構(gòu)全部六個數(shù)學分支的基本內(nèi)容,通過對相關(guān)知識點的凝練和結(jié)構(gòu)優(yōu)化,使得這六部分內(nèi)容形成一個完備統(tǒng)一的整體。
全書內(nèi)容一共分為十章和附錄: 第1章和第2章是全書最基礎(chǔ)的知識。第1章主要介紹集合、自然數(shù)與組合計數(shù)的初步知識;第2章將自然數(shù)集合這種最基本的離散結(jié)構(gòu)擴展到整數(shù)集合,考察整數(shù)的基本理論,并以整數(shù)算法為切入點討論算法的基本知識和設(shè)計策略。 第3章和第4章介紹數(shù)理邏輯的基本知識,為后續(xù)內(nèi)容提供邏輯表達和處理工具。第3章主要介紹命題邏輯演算與推理;第4章則是將數(shù)理邏輯由命題判斷的層次進一步推進到更為精細復雜的概念層次,考察基于概念演算的謂詞邏輯。
隨后的連續(xù)三章介紹關(guān)系的基本理論與應(yīng)用。第5章從集合的角度介紹關(guān)系的數(shù)學模型,包括關(guān)系的基本概念、運算和性質(zhì);第6章主要介紹等價、相容和偏序這三種特殊關(guān)系的數(shù)學模型與性質(zhì);第7章主要從關(guān)系的角度考察函數(shù)與映射的概念,可以看成是關(guān)系理論的一種應(yīng)用。其實,關(guān)系理論是整個離散數(shù)學知識體系的樞紐,一頭聯(lián)系集合論,另一頭聯(lián)系圖論,同時關(guān)系數(shù)學模型的表達和演算還可以看成是謂詞邏輯的一個直接應(yīng)用。
前言
第1章集合與計數(shù)基礎(chǔ)
1.1集合的基本知識
1.1.1數(shù)學危機與集合論
1.1.2集合的概念與表示
1.1.3集合的基本運算
1.1.4集合的二進制表示
1.2可數(shù)集與不可數(shù)集
1.2.1無限集的度量問題
1.2.2自然數(shù)集的定義
1.2.3無限集的基數(shù)比較
1.3有限集的基本計數(shù)技術(shù)
1.3.1加法原理與乘法原理
1.3.2容斥原理與鴿籠原理
1.3.3排列計數(shù)與組合計數(shù)
1.4有限集的高級計數(shù)技術(shù)
1.4.1遞推關(guān)系計數(shù)法
1.4.2遞推關(guān)系的求解
1.4.3生成函數(shù)計數(shù)法
1.5習題
第2章整數(shù)與算法設(shè)計基礎(chǔ)
2.1整數(shù)的基本知識
2.1.1整數(shù)與整數(shù)除法
2.1.2整數(shù)的因數(shù)分解
2.1.3素數(shù)的性質(zhì)與查找
2.2同余算術(shù)及其應(yīng)用
2.2.1同余關(guān)系及其運算
2.2.2同余方程與方程組
2.2.3整數(shù)加密算法
2.3算法設(shè)計的基本知識
2.3.1算法的基本概念
2.3.2算法效率的度量
2.3.3算法設(shè)計應(yīng)用舉例
2.4算法設(shè)計策略與應(yīng)用
2.4.1蠻力與貪心策略
2.4.2遞歸與分治策略
2.4.3回溯與動態(tài)規(guī)劃策略
2.5習題
第3章命題演算與推理
3.1命題的概念與運算
3.1.1邏輯與命題邏輯
3.1.2命題的基本概念
3.1.3命題的常用聯(lián)結(jié)詞
3.2命題公式與等值演算
3.2.1命題公式的基本知識
3.2.2等值關(guān)系與等值演算
3.2.3公式的內(nèi)否與對偶
3.3聯(lián)結(jié)詞的完備集
3.3.1聯(lián)結(jié)詞的枚舉
3.3.2聯(lián)結(jié)詞的完備性
3.3.3聯(lián)結(jié)詞的應(yīng)用
3.4命題公式的范式
3.4.1范式的基本概念
3.4.2主析取范式
3.4.3主合取范式
3.4.4主范式間的聯(lián)系
3.5命題邏輯的演繹推理
3.5.1永真蘊含關(guān)系與判定
3.5.2命題公式推演系統(tǒng)
3.5.3命題推證的基本策略
3.6命題邏輯的應(yīng)用
3.6.1刑偵推斷問題
3.6.2組合邏輯電路設(shè)計
3.6.3加法器電路設(shè)計
3.7習題
第4章謂詞演算與推理
4.1個體詞、謂詞與量詞
4.1.1邏輯與謂詞邏輯
4.1.2命題函數(shù)與謂詞
4.1.3量詞與特性謂詞
4.2謂詞公式與等值演算
4.2.1謂詞公式的概念
4.2.2變量的自由與約束
4.2.3謂詞公式的解釋與分類
4.2.4謂詞公式的等值與蘊含
4.3謂詞公式的范式
4.3.1等值型范式
4.3.2非等值型范式
4.4謂詞邏輯的推理
4.4.1謂詞公式的推演系統(tǒng)
4.4.2謂詞推證的基本方法
4.4.3謂詞推理實例選講
4.5謂詞邏輯的應(yīng)用
4.5.1摘香蕉問題
4.5.2水容器問題
4.6習題
第5章關(guān)系模型與理論
5.1關(guān)系的數(shù)學模型
5.1.1序偶與笛卡兒積
5.1.2關(guān)系的概念
5.1.3關(guān)系的表示
5.2關(guān)系的基本運算
5.2.1關(guān)系的集合運算
5.2.2關(guān)系的復合運算
5.2.3冪關(guān)系與逆關(guān)系
5.3關(guān)系的基本性質(zhì)
5.3.1關(guān)系的自反與反自反
5.3.2關(guān)系的對稱與反對稱
5.3.3關(guān)系的傳遞性
5.3.4關(guān)系性質(zhì)的判定
5.4關(guān)系的性質(zhì)閉包
5.4.1關(guān)系閉包的概念
5.4.2傳遞閉包的構(gòu)造
5.4.3關(guān)系閉包的性質(zhì)
5.5關(guān)系模型的應(yīng)用
5.5.1關(guān)系代數(shù)模型
5.5.2關(guān)系演算模型
5.6習題
第6章特殊關(guān)系模型
6.1等價關(guān)系與元素分類
6.1.1等價關(guān)系與等價類
6.1.2集合的劃分與商集
6.2相容關(guān)系與元素聚類
6.2.1相容關(guān)系與相容類
6.2.2集合的覆蓋
6.3偏序關(guān)系與元素比較
6.3.1偏序關(guān)系與哈斯圖
6.3.2偏序集的特殊元素
6.3.3全序與良序
6.4特殊關(guān)系的應(yīng)用
6.4.1粗集定義問題
6.4.2得分評判問題
6.5習題
第7章函數(shù)與特殊函數(shù)
7.1函數(shù)的基本概念
7.1.1函數(shù)的集合定義
7.1.2函數(shù)的基本類型
7.1.3常用特殊函數(shù)
7.2函數(shù)的基本運算
7.2.1函數(shù)的復合運算
7.2.2函數(shù)的逆運算
7.2.3函數(shù)的遞歸運算
7.3集合的特征函數(shù)
7.3.1特征函數(shù)的概念
7.3.2特征函數(shù)的運算
7.4有限集的置換函數(shù)
7.4.1置換函數(shù)的概念
7.4.2置換函數(shù)的運算
7.4.3置換的輪換分解
7.5函數(shù)關(guān)系的應(yīng)用
7.5.1哈希查找問題
7.5.2寬帶分配問題
7.6習題
第8章圖的基本理論與算法
8.1圖的概念與表示
8.1.1圖模型的由來
8.1.2圖的定義與分類
8.1.3圖的表示方法
8.2圖的運算與結(jié)構(gòu)
8.2.1圖的基本運算
8.2.2圖模型的度結(jié)構(gòu)
8.2.3圖同構(gòu)及其判定
8.3圖的通路與連通性
8.3.1通路的概念與計數(shù)
8.3.2可達性及其判定
8.3.3無向圖的連通性
8.3.4有向圖的連通性
8.4圖模型的基本算法
8.4.1深度優(yōu)先搜索
8.4.2廣度優(yōu)先搜索
8.4.3單源最短路徑
8.4.4多源最短路徑
8.5圖模型的應(yīng)用
8.5.1交通燈相位問題
8.5.2作業(yè)規(guī)劃問題
8.5.3機器學習問題
8.6習題
第9章樹的基本理論與算法
9.1無向樹的基本知識
9.1.1無向樹的概念與性質(zhì)
9.1.2無向圖的生成樹
9.1.3最小生成樹
9.2根樹的基本知識
9.2.1有向樹與根樹
9.2.2根樹的基本算法
9.2.3前綴碼與最優(yōu)樹
9.3特殊根樹與算法
9.3.1平衡樹模型
9.3.2紅黑樹模型
9.3.3B樹模型
9.4樹模型的應(yīng)用
9.4.1找假幣問題
9.4.2輪流摸牌問題
9.4.3關(guān)鍵道路問題
9.5習題
第10章特殊圖模型與算法
10.1歐拉圖與哈密頓圖
10.1.1歐拉圖及其性質(zhì)
10.1.2哈密頓圖及其性質(zhì)
10.1.3中國郵路問題
10.2二分圖與匹配問題
10.2.1二分圖的概念與性質(zhì)
10.2.2完備匹配與最大匹配
10.2.3最大匹配判定與構(gòu)造
10.3平面圖與著色問題
10.3.1平面圖的概念與性質(zhì)
10.3.2平面圖的對偶圖
10.3.3著色問題與算法
10.4網(wǎng)絡(luò)流圖及其優(yōu)化問題
10.4.1流網(wǎng)絡(luò)與切割
10