離散數學

離散數學是計算機科學基礎理論的核心課程，也是現代數學的一個重要分支。本教材包含了集合論、圖論、數理邏輯、組合數學、代數系統等內容。在介紹離散數學主要內容的同時，對相關知識的專業應用也做了實用性介紹。本書適合作為計算機和相關專業本科生“離散數學”的教學用書，也可以作為對離散數學感興趣的學生的參考書。

第一篇 集合論

第1章 集合 2

1.1 集合的概念與表示 2

1.1.1 集合及其表示 3

1.1.2 子集與冪集 5

1.2 集合的運算 8

1.2.1 集合的交、並、補、差 8

1.2.2 集合運算的性質 10

*1.3 容斥原理 12

本章小結 15

習題一 15

第2章 關係 18

2.1 關係的概念與表示 19

2.1.1 笛卡兒積 19

2.1.2 關係的概念 21

2.1.3 關係的表示 23

2.2 關係的基本性質 24

2.2.1 自反 24

2.2.2 對稱 26

2.2.3 傳遞 27

2.3 關係的運算 30

2.3.1 關係的交、並、補、差 30

2.3.2 關係的複合 30

2.3.3 關係的逆 32

2.3.4 關係的閉包 33

2.4 等價關係與序關係 36

2.4.1 等價關係與劃分 36

2.4.2 序關係 39

本章小結 43

習題二 44

第3章 函數 47

3.1 函數的概念與分類 48

3.1.1 函數的概念 48

3.1.2 函數的分類 50

3.2 函數的運算 54

3.2.1 函數的複合 54

3.2.2 函數的逆 56

*3.3 計算機科學中常用的兩類函數 57

3.3.1 取整函數 57

3.3.2 哈希函數 58

*3.4 基數 59

3.4.1 基數的概念 59

3.4.2 可數集與不可數集 61

本章小結 63

習題三 64

第二篇 圖論

第4章 圖 68

4.1 圖的概念與表示 69

4.1.1 圖的基本概念 69

4.1.2 圖的矩陣表示 76

4.2 路徑與連通性 78

4.2.1 路徑與迴路 78

4.2.2 圖的連通性 80

4.3 歐拉圖與漢密爾頓圖 83

4.3.1 歐拉圖 84

4.3.2 漢密爾頓圖 86

*4.4 圖的應用 89

4.4.1 最短路徑問題 89

4.4.2 支配集與通信系統建站問題 90

本章小結 91

習題四 91

第5章 樹 95

5.1 樹與圖的生成樹 95

5.1.1 樹的概念與性質 96

5.1.2 圖的生成樹 98

5.2 根樹 101

5.2.1 根樹的基本概念 101

5.2.2 二叉樹 102

5.2.3 二叉樹的遍歷 104

*5.3 樹的應用 105

5.3.1 決策樹 105

5.3.2 二叉搜索樹 106

5.3.3 最優二叉樹與哈夫曼編碼 107

本章小結 109

習題五 109

第三篇 數理邏輯

第6章 命題邏輯 114

6.1 命題與命題公式 115

6.1.1 命題的概念與表示 115

6.1.2 命題聯結詞 116

6.1.3 命題公式 119

6.2 命題公式的真值賦值與分類 120

6.2.1 真值表 120

6.2.2 重言式、矛盾式與可滿足式 122

6.2.3 邏輯等價與邏輯蘊涵 123

6.3 範式 128

6.3.1 合取範式與析取範式 128

6.3.2 主析取範式與主合取範式 129

*6.3.3 聯結詞的完備集 132

6.4 命題邏輯的推理理論 133

6.4.1 推理的形式結構 134

6.4.2 推理規則 135

本章小結 137

習題六 138

第7章 謂詞邏輯 140

7.1 謂詞與謂詞公式 141

7.1.1 個體、謂詞與量詞 141

7.1.2 項與謂詞公式 143

7.1.3 變元的約束 145

7.2 謂詞邏輯的語義 147

7.2.1 真值與解釋 147

7.2.2 永真式、矛盾式與可滿足式 148

7.2.3 邏輯等價與邏輯蘊涵 149

*7.3 前束範式 152

7.4 謂詞邏輯的推理理論 152

本章小結 156

習題七 156

第四篇 組合數學

第8章 組合數學 160

8.1 基本計數原理 161

8.1.1 加法原理 161

8.1.2 乘法原理 161

8.2 排列與組合 163

8.2.1 排列 163

8.2.2 組合 164

*8.2.3 廣義的排列與組合 166

8.3 二項式係數與組合恆等式 168

8.3.1 二項式係數 168

8.3.2 組合恆等式 169

*8.4 鴿籠原理 171

8.4.1 鴿籠原理的簡單形式 171

8.4.2 鴿籠原理的一般形式 173

*8.5 遞歸關係及其解法 174

8.5.1 遞歸關係的定義 174

8.5.2 逆向代換法 177

8.5.3 常係數齊次線性遞歸關係 177

8.5.4 常係數非齊次線性遞歸關係 179

本章小結 180

習題八 180

第五篇 代數系統

第9章 代數系統 184

9.1 代數系統的概念及運算性質 185

9.1.1 代數系統的概念 185

9.1.2 二元運算的性質 187

9.2 代數系統的同態與同構 190

9.2.1 同態與同構 190

9.2.2 同態的性質 191

9.3 群 193

9.3.1 半群與獨異點 193

9.3.2 群及其基本性質 194

9.3.3 子群與陪集 195

9.3.4 循環群與置換群 200

9.4 環與域 203

9.4.1 環與域的概念 203

*9.4.2 環與域的性質 204

9.5 格與布爾代數 205

9.5.1 格的概念與性質 205

9.5.2 分配格、有補格 206

9.5.3 布爾代數 208

本章小結 210

習題九 210

附錄A 213

參考文獻 221