離散數(shù)學

第0章?基礎(chǔ)知識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?序列和數(shù)組10
0.4.2?特征函數(shù)12
0.4.3?集合及子集的計算機表示13
0.4.4?串和正則表達式14
0.5?整數(shù)的分解16
0.5.1?整除及素數(shù)16
0.5.2?最大公因數(shù)17
0.5.3?最小公倍數(shù)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?數(shù)學結(jié)構(gòu)36
0.9?習題39
本章小結(jié)45
第1章?邏輯46
A命題邏輯46
1.1?命題和邏輯運算46
1.1.1?命題46
1.1.2?邏輯聯(lián)結(jié)詞和復合命題47
1.1.3?邏輯和位運算51
1.2?合式公式和語義51
1.2.1?語法52
1.2.2?語義52
1.3?邏輯等價53
1.4?真值函數(shù)和范式57
1.4.1?真值函數(shù)和合式公式57
1.4.2?析取范式59
1.4.3?合取范式60
1.4.4?用等價替換方法構(gòu)造主范式61
1.5?聯(lián)結(jié)詞的完備集63
1.5.1?聯(lián)結(jié)詞的完備集63
1.5.2?一些計算機應用64
1.6?形式推理系統(tǒng)66
1.6.1?形式推演規(guī)則66
1.6.2?形式可推演性的一些性質(zhì)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?數(shù)學歸納法97
1.12.1?歸納推理和演繹推理97
1.12.2?數(shù)學歸納法99
1.12.3?數(shù)學歸納法在證明不等式中的應用102
1.12.4?數(shù)學歸納法在其它方面的應用103
1.13?習題106
本章小結(jié)111
第2章?計數(shù)114
2.1?計數(shù)的兩個基本原理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數(shù)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?可望相等結(jié)果143
2.6?遞歸關(guān)系145
2.6.1?遞歸關(guān)系模型146
2.6.2?遞歸關(guān)系的基本解法151
2.7?習題159
本章小結(jié)164
第3章?關(guān)系和有向圖166
3.1?集合的積166
3.1.1?有序?qū)?66
3.1.2?集合的笛卡兒乘積166
3.2?關(guān)系和有向圖168
3.2.1?二元關(guān)系的定義168
3.2.2?關(guān)系矩陣171
3.2.3?關(guān)系圖172
3.2.4?n元關(guān)系及其應用173
3.3?復合關(guān)系和逆關(guān)系175
3.3.1?復合關(guān)系175
3.3.2?逆關(guān)系178
3.4?關(guān)系圖中的通路179
3.5?關(guān)系的性質(zhì)183
3.6?等價關(guān)系和集合的劃分187
3.6.1?等價關(guān)系187
3.6.2?集合的劃分190
3.6.3?有限集合上等價關(guān)系的計數(shù)191
3.7?關(guān)系的閉包193
3.7.1?關(guān)系閉包的基本概念193
3.7.2?求傳遞閉包的Warshall?算法196
3.8?習題200
本章小結(jié)204
第4章?函數(shù)206
4.1?函數(shù)的基本概念206
4.1.1?函數(shù)206
4.1.2?偏函數(shù)208
4.2?特殊函數(shù)209
4.3?函數(shù)的運算213
4.4?基數(shù)216
4.4.1?基數(shù)216
4.4.2?可數(shù)集與不可數(shù)集218
4.4.3?基數(shù)的比較220
4.5?用于計算機科學的函數(shù)221
4.5.1?一般函數(shù)221
4.5.2?散列函數(shù)223
4.6?函數(shù)的增長224
4.6.1?大O224
4.6.2?大Θ225
4.6.3?確定函數(shù)Θ類的規(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
本章小結(jié)234
第5章?群、環(huán)和域236
5.1?預備知識236
5.1.1?一些基本運算236
5.1.2?特殊元素240
5.1.3?同態(tài)與同構(gòu)244
5.2?半群和獨異點246
5.2.1?半群246
5.2.2