離散數學

第1章 集合與關系 ............................................................................................ 1
1.1 集合 .......................................................................................................................................1
1.1.1 集合的概念與運算 ...................................................................................................1
1.1.2 映射和基數 ...............................................................................................................4
1.1.3 良序性與數學歸納法 ...............................................................................................8
習題1.1 ..........................................................................................................................................9
1.2 二元關系.............................................................................................................................. 11
1.2.1 關系的定義 ............................................................................................................. 11
1.2.2 關系的表示與復合 ................................................................................................. 13
1.2.3 關系閉包 ................................................................................................................. 16
習題1.2 ........................................................................................................................................ 18
1.3 等價關系與劃分 .................................................................................................................. 19
1.3.1 等價關系與等價類 ................................................................................................. 19
1.3.2 劃分 ......................................................................................................................... 21
*1.3.3 粗糙集 ..................................................................................................................... 22
習題1.3 ........................................................................................................................................ 25
1.4 偏序集與布爾格 .................................................................................................................. 26
1.4.1 偏序集 ..................................................................................................................... 26
1.4.2 布爾格 ..................................................................................................................... 29
習題1.4 ........................................................................................................................................ 32
*1.5 模糊集 .................................................................................................................................. 33
1.5.1 模糊集定義 ............................................................................................................. 33
1.5.2 模糊集的表示法 ..................................................................................................... 36
1.5.3 模糊集的運算 ......................................................................................................... 38
習題1.5 ........................................................................................................................................ 40
第2章 計數 .................................................................................................. 42
2.1 排列與組合 .......................................................................................................................... 42
2.1.1 兩個原理和排列 ..................................................................................................... 42
2.1.2 組合和二項式定理 ................................................................................................. 44
*2.1.3 Sperner定理 ............................................................................................................ 47
習題2.1 ........................................................................................................................................ 48
2.2 鴿巢原理與容斥原理 .......................................................................................................... 49
2.2.1 鴿巢原理 ................................................................................................................. 49
2.2.2 容斥原理 ................................................................................................................. 52
習題2.2 ........................................................................................................................................ 55
2.3 組合型生成函數 .................................................................................................................. 56
2.3.1 多重集的組合計數方法 ......................................................................................... 56
2.3.2 組合型生成函數的性質 ......................................................................................... 58
2.3.3 線性常系數遞推關系的求解 ................................................................................. 60
習題2.3 ........................................................................................................................................ 69
2.4 排列型生成函數 .................................................................................................................. 70
2.4.1 排列型生成函數的引入 ......................................................................................... 70
2.4.2 多重集排列計數的例子 ......................................................................................... 72
習題2.4 ........................................................................................................................................ 74
2.5 Catalan數和Stirling數 ....................................................................................................... 75
2.5.1 Catalan數 ................................................................................................................ 75
2.5.2 Stirling數 ................................................................................................................ 78
習題2.5 ........................................................................................................................................ 80
第3章 數理邏輯 ............................................................................................. 81
3.1 命題 ..................................................................................................................................... 81
3.1.1 命題的定義 ............................................................................................................. 81
3.1.2 聯結詞 ..................................................................................................................... 82
3.1.3 條件命題 ................................................................................................................. 85
習題3.1 ........................................................................................................................................ 87
3.2 命題公式與邏輯等價 .......................................................................................................... 88
3.2.1 命題公式 ................................................................................................................. 88
3.2.2 重言式和矛盾式 ..................................................................................................... 90
3.2.3 邏輯等價 ................................................................................................................. 91
習題3.2 ........................................................................................................................................ 94
3.3 範式 ..................................................................................................................................... 96
3.3.1 析取範式與合取範式 ............................................................................................. 96
3.3.2 主範式 ..................................................................................................................... 97
習題3.3 ...................................................................................................................................... 102
3.4 推理理論............................................................................................................................ 103
3.4.1 有效論證 ............................................................................................................... 103
3.4.2 推理規則 ............................................................................................................... 105
3.4.3 間接證法 ............................................................................................................... 106
習題3.4 ...................................................................................................................................... 108
3.5 謂詞與量詞 ........................................................................................................................ 108
3.5.1 謂詞 ....................................................................................................................... 109
3.5.2 量化命題的邏輯等價式 ....................................................................................... 112
3.5.3 量化命題的推理規則 ........................................................................................... 113
習題3.5 ...................................................................................................................................... 116
第4章 圖論基礎 ........................................................................................... 117
4.1 圖與有向圖 ........................................................................................................................ 117
4.1.1 圖與度序列 ........................................................................................................... 117
4.1.2 路徑與連通 ........................................................................................................... 119
習題4.1 ...................................................................................................................................... 121
4.2 樹的性質............................................................................................................................ 122
4.2.1 樹的定義及刻畫 ................................................................................................... 122
4.2.2 Cayley公式 ........................................................................................................... 124
習題4.2 ...................................................................................................................................... 126
4.3 根樹及其應用 .................................................................................................................... 128
4.3.1 Huffman算法 ........................................................................................................ 128
4.3.2 二叉搜索樹和決策樹 ........................................................................................... 130
習題4.3 ...................................................................................................................................... 131
4.4 最小生成樹和最短路徑 .................................................................................................... 132
4.4.1 最小生成樹 ........................................................................................................... 132
4.4.2 最短路徑問題 ....................................................................................................... 135
習題4.4 ...................................................................................................................................... 137
4.5 歐拉圖和哈密頓圖 ............................................................................................................ 138
4.5.1 歐拉圖 ................................................................................................................... 138
4.5.2 哈密頓圖 ............................................................................................................... 140
習題4.5 ...................................................................................................................................... 142
第5章 再論圖論 ........................................................................................... 144
5.1 二部圖 ............................................................................................................................... 144
5.1.1 二部圖和匹配 ....................................................................................................... 144
5.1.2 頂點覆蓋 ............................................................................................................... 146
習題5.1 ...................................................................................................................................... 148
5.2 最大匹配及穩定匹配 ........................................................................................................ 149
5.2.1 最大匹配 ............................................................................................................... 149
5.2.2 穩定匹配 ............................................................................................................... 150
習題5.2 ...................................................................................................................................... 152
5.3 圖的連通性 ........................................................................................................................ 153
5.3.1 連通度 ................................................................................................................... 154
5.3.2 Menger定理 .......................................................................................................... 155
習題5.3 ...................................................................................................................................... 156
5.4 平面圖 ............................................................................................................................... 157
5.4.1 歐拉定理及應用 ................................................................................................... 157
5.4.2 可平面圖的刻畫 ................................................................................................... 160
習題5.4 ...................................................................................................................................... 160
5.5 圖的頂點著色 .................................................................................................................... 162
5.5.1 頂點著色的定義和性質 ....................................................................................... 162
5.5.2 四色問題 ............................................................................................................... 165
習題5.5 ...................................................................................................................................... 166
第６章 代數結構 ........................................................................................... 168
6.1 代數系統............................................................................................................................ 168
6.1.1 代數運算 ............................................................................................................... 168
6.1.2 格和群 ................................................................................................................... 170
6.1.3 群的例子 ............................................................................................................... 173
習題6.1 ...................................................................................................................................... 175
6.2 子群和商群 ........................................................................................................................ 175
6.2.1 子群 ....................................................................................................................... 176
6.2.2 商群 ....................................................................................................................... 179
習題6.2 ...................................................................................................................................... 180
6.3 循環群和對稱群 ................................................................................................................ 181
6.3.1 循環群 ................................................................................................................... 181
6.3.2 置換群 ................................................................................................................... 183
習題6.3 ...................................................................................................................................... 185
6.4 群同態及應用 .................................................................................................................... 185
6.4.1 群同態基本定理 ................................................................................................... 185
6.4.2 任意群和循環群的同構刻畫 ............................................................................... 187
習題6.4 ...................................................................................................................................... 188
6.5 環和域 ............................................................................................................................... 188
6.5.1 環與子環 ............................................................................................................... 189
6.5.2 環的零因子和特徵 ............................................................................................... 191
6.5.3 域的定義 ............................................................................................................... 193
習題6.5 ...................................................................................................................................... 195
參考文獻 ........................................................................................................ 197