離散數(shù)學(xué)基礎(chǔ)及實(shí)驗(yàn)教程（第3版）

目錄



第1章準(zhǔn)備知識(shí)

1.1集合

1.1.1集合的基本概念

1.1.2集合的基本運(yùn)算和性質(zhì)

1.1.3集合的笛卡兒積

1.1.4集合的計(jì)算機(jī)表示

1.2整數(shù)

1.2.1整除

1.2.2最大公約數(shù)和最小公倍數(shù)

1.2.3模運(yùn)算

1.3序列和遞推關(guān)系

1.3.1序列

1.3.2序列求和

1.3.3遞推關(guān)系

1.4矩陣

1.4.1矩陣的概念

1.4.2矩陣的運(yùn)算

1.4.3布爾矩陣

習(xí)題1

第2章數(shù)理邏輯

2.1命題及聯(lián)結(jié)詞

2.1.1命題的概念

2.1.2命題聯(lián)結(jié)詞

2.2命題公式和分類

2.2.1命題變?cè)兔}公式

2.2.2命題公式的賦值和真值表

2.2.3命題公式的類型

2.3等值演算與范式

2.3.1等價(jià)和基本等價(jià)式

2.3.2等值演算

2.3.3范式

2.4命題邏輯的推理理論

2.4.1推理的形式結(jié)構(gòu)

2.4.2演繹法證明推理

2.5謂詞邏輯基礎(chǔ)

2.5.1謂詞邏輯的基本概念

2.5.2謂詞公式及其解釋

2.6謂詞邏輯等值式與范式

2.6.1謂詞邏輯等值式

2.6.2前束范式

2.7謂詞邏輯的推理理論

2.7.1有關(guān)量詞的基本蘊(yùn)涵式

2.7.2有關(guān)量詞的推理規(guī)則

習(xí)題2

第3章計(jì)數(shù)

3.1基本計(jì)數(shù)、排列與組合

3.1.1基本的計(jì)數(shù)原則

3.1.2排列與組合

3.2排列組合的進(jìn)一步討論

3.2.1圓周排列

3.2.2有重復(fù)的排列

3.2.3有重復(fù)的組合

3.3生成排列和組合

3.3.1生成排列

3.3.2生成組合

3.4生成函數(shù)及其應(yīng)用

3.4.1生成函數(shù)的定義

3.4.2生成函數(shù)求解計(jì)數(shù)問題

3.4.3使用生成函數(shù)求解遞推關(guān)系

3.5鴿巢原理

3.5.1一般的鴿巢原理

3.5.2推廣的鴿巢原理

3.6容斥原理

3.6.1容斥原理簡介

3.6.2容斥原理的應(yīng)用

習(xí)題3

第4章關(guān)系

4.1關(guān)系定義及其表示

4.1.1關(guān)系的基本概念

4.1.2二元關(guān)系的表示

4.2關(guān)系的運(yùn)算

4.2.1關(guān)系的合成

4.2.2逆運(yùn)算

4.3關(guān)系的性質(zhì)

4.3.1自反性與反自反性

4.3.2對(duì)稱性與反對(duì)稱性

4.3.3傳遞關(guān)系

4.4n元關(guān)系及其應(yīng)用

4.5關(guān)系的閉包

4.5.1閉包的概念和求法

4.5.2Warshall算法

4.6等價(jià)關(guān)系

4.6.1等價(jià)關(guān)系與等價(jià)類

4.6.2等價(jià)關(guān)系與劃分

4.7偏序關(guān)系

4.7.1偏序關(guān)系和哈斯圖

4.7.2極值和最值

4.7.3拓?fù)渑判?

4.8函數(shù)

4.8.1函數(shù)的定義

4.8.2函數(shù)的類型

4.8.3函數(shù)的運(yùn)算

習(xí)題4

第5章布爾代數(shù)

5.1布爾函數(shù)

5.1.1布爾函數(shù)和布爾表達(dá)式

5.1.2布爾代數(shù)中的恒等式

5.2布爾函數(shù)的表示

5.2.1布爾函數(shù)的主析取范式

5.2.2函數(shù)完備性

5.3布爾代數(shù)的應(yīng)用

5.3.1門電路

5.3.2卡諾圖

習(xí)題5

第6章圖

6.1圖的基本概念

6.1.1無向圖和有向圖

6.1.2握手定理

6.1.3圖的同構(gòu)

6.2圖的連通性

6.2.1通路和回路

6.2.2無向圖的連通性

6.2.3有向圖的連通性

6.3圖的矩陣表示

6.3.1關(guān)聯(lián)矩陣

6.3.2鄰接矩陣

6.3.3有向圖的可達(dá)矩陣

6.4一些特殊的圖

6.4.1二部圖

6.4.2歐拉圖

6.4.3哈密爾頓圖

6.5帶權(quán)圖的最短路徑

6.5.1Dijkstra算法

6.5.2Floyd算法

6.5.3旅行商問題

6.6平面圖

6.6.1平面圖的定義

6.6.2歐拉公式

6.6.3庫拉圖斯基定理

習(xí)題6

第7章樹

7.1無向樹

7.1.1無向樹的定義

7.1.2無向樹的應(yīng)用例子

7.2生成樹

7.2.1生成樹的定義

7.2.2求最小生成樹的算法

7.3根樹及應(yīng)用

7.3.1根樹的定義及應(yīng)用

7.3.2最優(yōu)二叉樹和Huffman編碼

7.3.3二叉樹的遍歷

習(xí)題7

第8章離散數(shù)學(xué)實(shí)驗(yàn)

8.1實(shí)驗(yàn)一準(zhǔn)備知識(shí)

8.1.1集合定義

8.1.2子集

8.1.3A-B

8.1.4集合相等

8.1.5笛卡兒積

8.1.6最大公約數(shù)與最小公倍數(shù)

8.1.7余數(shù)

8.1.8Fibonacci數(shù)列

8.1.9漢諾塔

8.1.10漢諾塔Ⅲ

8.1.11序列和

8.1.12有效編碼

8.1.13矩陣的和

8.1.14矩陣的布爾積

8.2實(shí)驗(yàn)二數(shù)理邏輯

8.2.1命題聯(lián)結(jié)詞

8.2.2成真解釋

8.2.3公式類型

8.2.4主析取范式

8.2.5主合取范式

8.2.6派誰去進(jìn)修的問題

8.2.7推理1

8.2.8推理2

8.2.9公式的真值1

8.2.10公式的真值2

8.3實(shí)驗(yàn)三計(jì)數(shù)

8.3.1密碼

8.3.2圓周排列1

8.3.3圓周排列2

8.3.4有重復(fù)的組合

8.3.5生成排列

8.3.6生成組合

8.3.7上班問題

8.3.8解方程1

8.3.9解方程2

8.3.10工作組

8.4實(shí)驗(yàn)四關(guān)系

8.4.1關(guān)系矩陣

8.4.2關(guān)系的合成1

8.4.3關(guān)系的合成2

8.4.4關(guān)系的運(yùn)算

8.4.5自反性

8.4.6對(duì)稱性

8.4.7對(duì)稱閉包

8.4.8傳遞閉包

8.4.9同余

8.4.10等價(jià)類

8.4.11等價(jià)關(guān)系

8.4.12哈斯圖

8.4.13極值

8.4.14最值

8.4.15拓?fù)渑判?

8.5實(shí)驗(yàn)五圖

8.5.1簡單圖1

8.5.2簡單圖2

8.5.3度數(shù)列1

8.5.4度數(shù)列2

8.5.5連通圖

8.5.6單向連通

8.5.7強(qiáng)連通

8.5.8二分圖

8.5.9歐拉圖

8.5.10半歐拉圖

8.5.11歐拉回路

8.5.12歐拉路

8.5.13單源正權(quán)最短路徑

8.5.14最短路徑

8.5.15平面圖1

8.5.16平面圖2

8.6實(shí)驗(yàn)六樹

8.6.1無向樹

8.6.2最小生成樹

8.6.3根樹

8.6.4Huffman編碼

參考文獻(xiàn)