第1章 基礎(chǔ)知識1
1.1 集合的初步知識1
1.2 數(shù)學(xué)歸納法1
1.3 整數(shù)的基本性質(zhì)2
1.3.1 整除2
1.3.2 素數(shù)3
1.3.3 帶余除法4
1.3.4 最大公約數(shù)5
1.3.5 最小公倍數(shù)7
1.3.6 模運算8
1.3.7 同余的應(yīng)用10
1.4 序列的基本知識11
1.4.1 序列11
1.4.2 典型的整數(shù)序列12
1.4.3 序列求和13
1.5 計數(shù)15
1.5.1 加法原理和乘法原理15
1.5.2 排列與組合17
1.5.3 二項式定理21
1.5.4 鴿巢原理22
1.6 矩陣的初步知識23
1.6.1 矩陣的概念23
1.6.2 矩陣的加法和數(shù)乘25
1.6.3 矩陣的乘法26
1.6.4 轉(zhuǎn)置矩陣和逆矩陣27
1.7 本章小結(jié)28
1.8 習(xí)題28

第2章 命題邏輯31
2.1 命題與聯(lián)結(jié)詞31
2.1.1 命題31
2.1.2 邏輯聯(lián)結(jié)詞33
2.1.3 聯(lián)結(jié)詞的優(yōu)先級37
2.1.4 命題符號化37
2.1.5 邏輯運算在計算機中的直接運用39
2.2 命題公式與等價演算41
2.2.1 命題公式及其層次41
2.2.2 命題公式的賦值42
2.2.3 等價式與等價演算45
2.2.4 等價演算的實際應(yīng)用48
2.3 聯(lián)結(jié)詞的擴充與聯(lián)結(jié)詞完備集49
2.3.1 聯(lián)結(jié)詞的擴充49
2.3.2 與非、或非、異或的性質(zhì)51
2.3.3 聯(lián)結(jié)詞完備集52
2.4 范式53
2.4.1 析取范式與合取范式53
2.4.2 主析取范式與主合取范式57
2.4.3 主范式的作用62
2.4.4 用主范式解答實際問題63
2.5 命題邏輯推理66
2.5.1 推理的形式結(jié)構(gòu)66
2.5.2 推理的證明方法68
2.5.3 命題邏輯推理的實際應(yīng)用71
2.6 本章小結(jié)72
2.7 習(xí)題73

第3章 謂詞邏輯76
3.1 謂詞邏輯的基本概念76
3.1.1 個體和謂詞76
3.1.2 量詞78
3.1.3 特性謂詞80
3.1.4 謂詞邏輯符號化81
3.2 謂詞公式與翻譯82
3.2.1 謂詞公式82
3.2.2 謂詞邏輯的翻譯83
3.3 變元的約束86
3.3.1 約束變元和自由變元86
3.3.2 約束變元的換名規(guī)則87
3.3.3 自由變元的代替規(guī)則88
3.4 謂詞公式的解釋與分類89
3.4.1 謂詞公式的解釋89
3.4.2 謂詞公式的分類90
3.5 謂詞邏輯的等價式和前束范式91
3.5.1 謂詞邏輯等價式91
3.5.2 前束范式94
3.6 謂詞邏輯推理95
3.6.1 推理定律95
3.6.2 推理規(guī)則97
3.6.3 謂詞邏輯推理例題98
3.7 程序正確性證明100
3.8 本章小結(jié)102
3.9 習(xí)題102

第4章 集合106
4.1 集合的基本概念106
4.1.1 集合及其表示方法106
4.1.2 集合間的關(guān)系108
4.1.3 特殊集合109
4.1.4 有限冪集元素的編碼表示110
4.2 集合的基本運算111
4.3 集合恒等式113
4.4 集合的劃分與覆蓋115
4.5 有窮集合的計數(shù)117
4.6 本章小結(jié)118
4.7 習(xí)題119

第5章 關(guān)系121
5.1 關(guān)系的概念與表示121
5.1.1 笛卡兒積121
5.1.2 二元關(guān)系的概念123
5.1.3 關(guān)系矩陣和關(guān)系圖125
5.2 復(fù)合關(guān)系和逆關(guān)系127
5.2.1 復(fù)合關(guān)系127
5.2.2 逆關(guān)系130
5.3 關(guān)系的性質(zhì)131
5.4 關(guān)系的閉包135
5.5 等價關(guān)系和偏序關(guān)系136
5.5.1 等價關(guān)系136
5.5.2 偏序關(guān)系138
5.5.3 字典排序和拓撲排序141
5.6 函數(shù)143
5.6.1 函數(shù)的基本概念143
5.6.2 復(fù)合函數(shù)和逆函數(shù)145
5.6.3 幾個重要的函數(shù)147
5.7 二元關(guān)系的應(yīng)用148
5.7.1 等價關(guān)系的應(yīng)用149
5.7.2 函數(shù)的應(yīng)用149
5.8 多元關(guān)系及其應(yīng)用149
5.8.1 多元關(guān)系149
5.8.2 關(guān)系數(shù)據(jù)庫151
5.9 本章小結(jié)153
5.10 習(xí)題153

第6章 代數(shù)系統(tǒng)155
6.1 二元運算及其性質(zhì)155
6.1.1 二元運算與一元運算155
6.1.2 二元運算的性質(zhì)與特殊元素157
6.1.3 代數(shù)系統(tǒng)簡介162
6.1.4 典型例題分析163
6.2 半群與群164
6.2.1 半群、獨異點與群164
6.2.2 冪167
6.2.3 群的性質(zhì)168
6.2.4 典型例題分析170
6.3 子群、循環(huán)群與置換群170
6.3.1 元素的周期170
6.3.2 子群171
6.3.3 循環(huán)群173
6.3.4 置換群176
6.4 陪集和正規(guī)子群178
6.4.1 陪集178
6.4.2 正規(guī)子群180
6.4.3 典型例題分析181
6.5 群的同態(tài)與同構(gòu)182
6.5.1 基本概念182
6.5.2 基本性質(zhì)183
6.6 環(huán)和域184
6.6.1 環(huán)184
6.6.2 域187
6.7 格187
6.7.1 格的定義187
6.7.2 格的性質(zhì)189
6.7.3 幾種特殊的格191
6.8 布爾代數(shù)193
6.8.1 布爾代數(shù)及其性質(zhì)193
6.8.2 布爾函數(shù)與布爾表達式196
6.9 應(yīng)用實例196
6.9.1 門電路196
6.9.2 邏輯電路設(shè)計197
6.10 本章小結(jié)199
6.11 習(xí)題200

第7章 圖論204
7.1 圖的基本概念204
7.1.1 圖的定義204
7.1.2 特殊的圖207
7.1.3 子圖208
7.1.4 結(jié)點的度209
7.2 圖的連通性211
7.2.1 路徑和回路211
7.2.2 無向圖的連通性212
7.2.3 有向圖的連通性212
7.2.4 歐拉圖213
7.2.5 哈密頓圖217
7.2.6 帶權(quán)圖的最短路217
7.3 圖的矩陣表示219
7.3.1 無向圖的關(guān)聯(lián)矩陣219
7.3.2 有向圖的關(guān)聯(lián)矩陣220
7.3.3 有向圖的鄰接矩陣220
7.3.4 無向圖的鄰接矩陣221
7.4 樹222
7.4.1 無向樹與生成樹222
7.4.2 有向樹224
7.4.3 最優(yōu)二元樹226
7.4.4 前綴碼228
7.4.5 樹的遍歷230
7.5 本章小結(jié)231
7.6 習(xí)題232

第8章 算法與偽代碼234
8.1 算法概述234
8.2 判斷素數(shù)算法236
8.3 求最大數(shù)算法236
8.4 求最大公約數(shù)的歐幾里得算法237
8.5 求拓撲排序的算法237
8.6 求歐拉路的Fleury算法239
8.7 求最短路徑的Dijkstra算法240
8.8 求最小生成樹的Prim算法241
8.9 求最優(yōu)二元樹的Huffman算法243

附錄A 離散數(shù)學(xué)常用符號245
附錄B 中英文名詞術(shù)語對照表250
附錄C 英中文名詞術(shù)語對照表263
附錄D 習(xí)題答案與提示275
參考文獻286