離散數學

第0章?基礎知識1
0.1?集合及子集1
0.1.1?集合及其表示1
0.1.2?子集2
0.1.3?冪集3
0.2?集合上的運算4
0.2.1?集合的并4
0.2.2?集合的交4
0.2.3?集合的差5
0.2.4?集合的對稱差6
0.3?多重集合9
0.4?序列10
0.4.1?序列和數組10
0.4.2?特征函數12
0.4.3?集合及子集的計算機表示13
0.4.4?串和正則表達式14
0.5?整數的分解16
0.5.1?整除及素數16
0.5.2?最大公因數17
0.5.3?最小公倍數20
0.5.4?某些算法的偽代碼21
0.6?矩陣22
0.6.1?矩陣的定義22
0.6.2?矩陣的運算23
0.6.3?布爾矩陣運算26
0.7?算法和算法語言28
0.7.1?算法簡介28
0.7.2?算法概念29
0.7.3?算法語言31
0.7.4?遞歸算法34
0.8?數學結構36
0.9?習題39
本章小結45
第1章?邏輯46
A命題邏輯46
1.1?命題和邏輯運算46
1.1.1?命題46
1.1.2?邏輯聯結詞和復合命題47
1.1.3?邏輯和位運算51
1.2?合式公式和語義51
1.2.1?語法52
1.2.2?語義52
1.3?邏輯等價53
1.4?真值函數和范式57
1.4.1?真值函數和合式公式57
1.4.2?析取范式59
1.4.3?合取范式60
1.4.4?用等價替換方法構造主范式61
1.5?聯結詞的完備集63
1.5.1?聯結詞的完備集63
1.5.2?一些計算機應用64
1.6?形式推理系統(tǒng)66
1.6.1?形式推演規(guī)則66
1.6.2?形式可推演性的一些性質69
1.6.3?形式推演實例73
B一階邏輯76
1.7?謂詞和量詞76
1.7.1?謂詞76
1.7.2?量詞77
1.7.3?Lewis?Carroll?例79
1.8?合式公式和語義80
1.8.1?合式公式80
1.8.2?語義82
1.8.3?自然語言的形式化83
1.9?邏輯等價和蘊涵85
1.10?范式90
1.11?一階邏輯的形式推理系統(tǒng)93
1.12?數學歸納法97
1.12.1?歸納推理和演繹推理97
1.12.2?數學歸納法99
1.12.3?數學歸納法在證明不等式中的應用102
1.12.4?數學歸納法在其它方面的應用103
1.13?習題106
本章小結111
第2章?計數114
2.1?計數的兩個基本原理114
2.1.1?加法原理114
2.1.2?乘法原理115
2.2?排列與組合115
2.2.1?排列115
2.2.2?組合119
2.2.3?二項式定理121
2.2.4?多項式定理124
2.3?鴿籠原理124
2.3.1?鴿籠原理的簡單形式125
2.3.2?鴿籠原理的一般形式126
2.3.3?Ramsey數128
2.4?容斥原理130
2.4.1?引130
2.4.2?容斥原理131
2.4.3?容斥原理的應用135
2.5?概率初步140
2.5.1?引140
2.5.2?樣本空間140
2.5.3?事件141
2.5.4?對事件賦予概率142
2.5.5?可望相等結果143
2.6?遞歸關系145
2.6.1?遞歸關系模型146
2.6.2?遞歸關系的基本解法151
2.7?習題159
本章小結164
第3章?關系和有向圖166
3.1?集合的積166
3.1.1?有序對166
3.1.2?集合的笛卡兒乘積166
3.2?關系和有向圖168
3.2.1?二元關系的定義168
3.2.2?關系矩陣171
3.2.3?關系圖172
3.2.4?n元關系及其應用173
3.3?復合關系和逆關系175
3.3.1?復合關系175
3.3.2?逆關系178
3.4?關系圖中的通路179
3.5?關系的性質183
3.6?等價關系和集合的劃分187
3.6.1?等價關系187
3.6.2?集合的劃分190
3.6.3?有限集合上等價關系的計數191
3.7?關系的閉包193
3.7.1?關系閉包的基本概念193
3.7.2?求傳遞閉包的Warshall?算法196
3.8?習題200
本章小結204
第4章?函數206
4.1?函數的基本概念206
4.1.1?函數206
4.1.2?偏函數208
4.2?特殊函數209
4.3?函數的運算213
4.4?基數216
4.4.1?基數216
4.4.2?可數集與不可數集218
4.4.3?基數的比較220
4.5?用于計算機科學的函數221
4.5.1?一般函數221
4.5.2?散列函數223
4.6?函數的增長224
4.6.1?大O224
4.6.2?大Θ225
4.6.3?確定函數Θ類的規(guī)則226
4.7?置換226
4.7.1?置換的基本概念227
4.7.2?置換的表示227
4.7.3?置換的積227
4.7.4?循環(huán)228
4.8?習題231
本章小結234
第5章?群、環(huán)和域236
5.1?預備知識236
5.1.1?一些基本運算236
5.1.2?特殊元素240
5.1.3?同態(tài)與同構244
5.2?半群和獨異點246
5.2.1?半群246
5.2.2