離散數學

《離散數學》為高等教育“十五”國家級規劃教材，是作者結合多年的教學實踐，並參考了國內外多種同類教材編寫而成的。為了更好的適應計算機學科發展的需要，增加了不少新知識、新內容以及演示性例子和應用實例。力求使之適應計算機學科發展的需要，希望能兼有國外教材與國內教材的優點。全書內容共分9章，主要包括：集合論基礎、命題邏輯和謂詞邏輯、圖論與網絡、數論基礎、近世代數、格論與布爾代數基礎知識以及計算機模型中語言、有限狀態機和圖靈機的內容。《離散數學》還將配有相應的學習指導書及習題解答，以方便教學。 ^[1] 

1.1 集合的基本概念

習題1.1

1.2 關係

1.2.1 關係的基本概念及其性質

1.2.2 等價關係

1.2.3 部分序關係

習題1.2

1.3 映射

1.3.1 集合的基數

1.3.2 可數集合

1.3.3 不可數集甘

習題1.3

1.4 集合在計算機科學中的應用

1.4.1 關係在關係數據庫中的應用

1.4.2 關係代數與數據子語言

1.4.3 等價關係在計算機中的應用

1.4.4 序關係在項目管理中的應用

2.1 命題以及邏輯聯結詞

2.1.1 命題

2.1.2 邏輯聯結詞

習題2.1

2.2 命題公式

2.2.1 公式

2.2.2 解釋

習題2.2

2.3 命題公式的等價關係和藴涵關係

2.3.1 公式的等價

2.3.2 公式的藴涵

2.3.3 演繹

2.3.4 公式藴涵的證明方法

習題2.3

2.4 範式

2.4.1 析取範式和合取範式

2.4.2 主析取範式和主合取範式

2.4.3 恆真恆假性的判定

習題2.4

2.5 命題邏輯在二值邏輯器件和語句邏輯中的應用

3.1 謂詞邏輯的基本概念

3.1.1 謂詞和量詞

3.1.2 改名規則

習題3.1

3.2 謂詞公式

3.2.1 公式

3.2.2 解釋

習題3.2

3.3 謂詞公式的等價關係和藴涵關係

3.3.1 公式的等價和藴涵

3.3.2 謂詞演算的推理理論

習題3.3

3.4 範式

3.4.1 前束範式

3.4.2 Skolem範式

習題3.4

3.5 例

習題3.5

3.6 謂詞邏輯的應用

3.6.1 謂詞邏輯與數據子語言

3.6.2 謂詞邏輯與邏輯程序設計語言

4.1 圖

4.1.1 圖的基本概念

4.1.2 權圖Dijkstra算法

習題4.1

4.2 樹

4.2.1 樹及其等價命題

4.2.2 最優樹Kruskal算法

4.2.3 求最優樹的其他算法

習題4.2

4.3 有向圖Euler路

4.3.1 有向圖與有向樹

4.3.2 Euler路Euler圖

4.3.3 無向圖無向圖中的Euler路

習題4.3

4.4 Hamilton圖

4.4.1 Hamilton路Hamilton圖的必要條件

4.4.2 Hamilton圖的若干充分條件

習題4.4

4.5 平面圖

4.5.1 平面圖判定Kuratowski判字準則

4.5.2 平面圖的Euler公式

4.5.3 平面圖的對偶圖Plato體

4.5.4 平面圖的着色

習題4.5

4.6 匹配二部圖

習題4.6

4.7 Konig無限性引理

習題4.7

4.8 網絡優化算法

4.8.1 圖與網絡的數據結構

4.8.2 單源最短路徑問題具體算法及實現和比較

4.8.3 最大流問題具體算法及實現和比較

習題4.8

5.1 整除性輾轉相除

5.1.1 整除及其性質

5.1.2 輾轉相除

5.1.3 利用數的數碼特徵判別某些整除性

習題5.1

5.2 互質質因數分解

5.2.1 整數互質

5.2.2 質數與合數算術基本定理

習題5.2

5.3 合同一次同餘式

5.3.1 合同及其性質

5.3.2 剩餘類一次同餘式

習題5.3

5.4 秦九韶定理Euler函數

5.4.1 一次同餘式組秦九韶定理

5.4.2 一元高次同餘式的化簡

5.4.3 剩餘系遍歷Euler函數

習題5.4

5.5 一元高次同餘式二次剩餘

5.5.1 一元高次同餘式的解

5.5.2 二次同餘式二次剩餘

5.5.3 二次剩餘的判定Legendre符號

習題5.5

5.6 數論在計算機通信安全中的應用

5.6.1 密碼系統

5.6.2 凱撒密碼

5.6.3 Vigenere密碼

5.6.4 Hill加密算法

5.6.5 RSA公鑰系統

習題5.6

6.1 代數系統

習題6.1

6.2 羣的定義

6.2.1 半羣

6.2.2 羣

6.2.3 羣的性質

習題6.2

6.3 置換羣

6.3.1 置換的定義

6.3.2 置換的輪換表法

6.3.3 置換的順向圈表示

6.3.4 置換的奇偶性

習題6.3

6.4 子羣及其陪集

6.4.1 子羣的定義

6.4.2 子羣的判別條件

6.4.3 循環羣

6.4.4 陪集

習題6.4

6.5 同構及同態

6.5.1 同態映射

6.5.2 同構映射

6.5.3 同態核

習題6.5

6.6 環

6.6.1 環的定義

6.6.2 環的性質

習題6.6

6.7 環同態

6.7.1 理想

6.7.2 環中合同關係

6.7.3 環同態與同構

6.7.4 單純環與極大理想

習題6.7

6.8 羣與環在計算機科學中的應用

6.8.1 計數問題

6.8.2 糾錯碼

67.1 域的特徵素域

7.1.1 域的特徵

7.1.2 素域

習題7.1

7.2 多項式的整除性

習題7.2

7.3 多項式的根

習題7.3

7.4 有理域上的多項式

習題7.4

7.5 分圓多項式

7.5.1 複數域上的分圓多項式

7.5.2 任意域上的分圓多項式

習題7.5

7.6 有限域

習題7.6

7.7 多項式編碼方法及其實現

習題7.7

8.1 引言

8.2 格的定義

習題8.2

8.3 格的性質

8.3.1 對偶原理

8.3.2 格的其他性質

8.3.3 格的同態與同構

習題8.3

8.4 幾種特殊的格

8.4.1 有界格

8.4.2 有餘格

8.4.3 分配格

8.4.4 模格

習題8.4

8.5 布爾代數

8.5.1 布爾代數的定義及其性質

8.5.2 有限布爾代數的表示理論

8.5.3 布爾代數的同態與同構

習題8.5

8.6 布爾表達式的化簡問題

習題8.6

8.7 格與布爾代數在計算機科學中的應用

8.7.1 開關電路函數

8.7.2 邏輯門

8.7.3 全加器的邏輯設計

9.1 語言和語法

9.1.1 語法結構

9.1.2 語法結構的類型

9.1.3 演繹樹

9.1.4 Backus-Naurform

習題9.1

9.2 帶有輸出的有限狀態機

習題9.2

9.3 沒有輸出的有限狀態機

習題9.3

9.4 語言識別

9.4.1 正則集合

9.4.2 KLEENE定理

9.4.3 其他幾種類型的有限狀態機

習題9.4

9.5 Turing機

習題9.5

參考文獻