離散數學[高等教育出版社2002年版]

《離散數學》是2002年8月高等教育出版社出版的圖書。 《離散數學》可作為高等院校計算機及相關專業的教材，也可供從事計算機研究工作的人員參考使用。

圖書信息

書名： 離散數學

作者： 孫吉貴 楊鳳傑 歐陽丹彤 李占山

ISBN： 7-04-011248-5

出版社： 高等教育出版社

出版時間：2002年8月

叢書：普通高等教育“十五”國家級規劃教材

開本：16

內容簡介

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

目錄

第一章 集合論基礎

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

參考文獻