離散數學教程（第4版）

目 錄
第1章 集合 1
1.1 集合的基本概念 1
1.1.1 集合的表示方法 1
1.1.2 子集 2
1.1.3 全集和補集 3
1.1.4 冪集 3
1.2 集合的基本運算 4
1.2.1 並和交 4
1.2.2 差和對稱差 7
習題1 9
第2章 二元關系與函數 12
2.1 二元關系的基本概念 12
2.1.1 引言 12
2.1.2 笛卡兒乘積和二元關系的定義 12
2.1.3 二元關系的三種表示方法 13
2.1.4 二元關系的基本類型 16
2.2 等價關系和偏序關系 19
2.2.1 等價關系與劃分 19
2.2.2 偏序關系 25
2.3 關系的特殊運算 28
2.3.1 復合關系 28
2.3.2 逆關系 32
2.3.3 閉包運算 33
2.4 函數 36
2.4.1 函數的基本概念 36
2.4.2 特殊函數 38
2.4.3 復合函數和逆函數 40
習題2 43
第3章 組合數學初步 47
3.1 計數的基本原則與鴿巢原理 47
3.1.1 乘積法則與求和法則 47
3.1.2 減法法則（容斥原理） 48
3.1.3 除法法則 49
3.1.4 樹形圖 50
3.1.5 鴿巢原理 50
3.1.6 鴿巢原理的應用 52
3.2 排列與組合及其推廣 53
3.2.1 基本計數原理 53
3.2.2 排列：順序重要、不放回 54
3.2.3 組合：順序不重要、不放回 54
3.2.4 允許重復的排列（有放回） 55
3.2.5 多重集的排列（元素不可區分） 55
3.2.6 允許重復的組合（多重集的組合） 56
3.2.7 分配模型與等價轉換 57
3.3 二項式與經典恒等式 57
3.3.1 二項式定理 58
3.3.2 組合恒等式的推導 59
3.3.3 帕斯卡恒等式 60
3.3.4 範德蒙德卷積 61
3.3.5 上指標求和與其他恒等式 62
3.3.6 應用舉例 62
3.4 生成排列與組合 63
3.4.1 生成排列 63
3.4.2 生成組合 65
3.5 遞推模型與分治思想 67
3.5.1 遞推關系及應用 67
3.5.2 動態規劃與遞推關系 68
3.5.3 分治算法與遞推關系 69
3.5.4 分治遞推關系估計算法復雜度 71
3.6 線性遞推關系的求解 73
3.6.1 線性齊次遞推關系求解 73
3.6.2 常系數線性齊次遞推關系求解 73
3.6.3 常系數線性非齊次遞推關系求解 75
3.7 生成函數 76
3.7.1 生成函數的定義和定理 76
3.7.2 生成函數的應用 77
習題3 78
第4章 圖論 81
4.1 圖的基本概念 81
4.1.1 幾個問題 81
4.1.2 圖的基本術語 82
4.1.3 圖的矩陣表示 85
4.1.4 子圖與圖的同構 87
4.1.5 完全圖與補圖 89
4.2 通路與賦權圖的最短通路 91
4.2.1 通路與回路 91
4.2.2 圖的連通性 92
4.2.3 賦權圖的最短通路 96
4.3 樹 102
4.3.1 無向樹 102
4.3.2 有向樹 106
4.3.3 前綴碼與最優樹 108
4.4 歐拉圖和哈密頓圖 114
4.4.1 歐拉圖 114
4.4.2 哈密頓圖 118
4.5 二部圖和平面圖 122
4.5.1 二部圖 123
4.5.2 平面圖 127
習題4 135
第5章 命題邏輯 140
5.1　命題邏輯的基本概念 140
5.1.1　命題 140
5.1.2 命題聯結詞 141
5.1.3 命題公式 143
5.1.4 命題公式的真值表 145
5.1.5 永真式、永假式和可滿足式 145
5.2　邏輯等價 147
5.2.1　邏輯等價 147
5.2.2 代換規則 148
5.2.3 對偶原理 150
5.2.4 聯結詞的完備集 150
5.2.5 奎因法 151
5.3 範式和主範式 152
5.3.1 析取範式和合取範式 152
5.3.2 主析取範式和主合取範式 153
5.4 邏輯蘊涵 160
5.4.1 邏輯蘊涵的定義 160
5.4.2 邏輯蘊涵的性質 161
5.5 推理理論 164
5.5.1 前提和有效結論 164
5.5.2 直接證明法 165
5.5.3 間接證明法 166
習題5 170
第6章 謂詞邏輯 174
6.1 謂詞邏輯的基本概念 174
6.1.1 個體詞、謂詞和命題函數 174
6.1.2 量詞 176
6.1.3 謂詞公式 181
6.1.4 約束變元和自由變元 182
6.1.5 解釋 184
6.2 邏輯等價與邏輯蘊含 186
6.2.1 永真式、永假式和可滿足式 186
6.2.2 邏輯等價式和邏輯蘊含式 186
6.2.3 前束範式 191
6.3 謂詞演算的推理理論 192
習題6 196
第7章 代數系統簡介 198
7.1 代數系統的基本概念 198
7.1.1 代數系統的定義 198
7.1.2 特殊運算與特殊元素 201
7.1.3 同構 206
7.2 半群和獨異點 207
7.2.1 半群和子半群 207
7.2.2 獨異點和子獨異點 211
7.3 群 212
7.3.1 群的定義和性質 212
7.3.2 子群 218
7.3.3 循環群 223
7.3.4 陪集和拉格朗日定理 225
7.3.5 群碼 229
7.4 環和域 232
7.4.1 環 232
7.4.2 域 235
7.5 格 237
7.5.1 格的定義 237
7.5.2 格和偏序集 239
7.5.3 特殊格 241
習題7 246
參考文獻 251