離散數(shù)學(xué)

第0章?基礎(chǔ)知識1
0.1?集合及子集1
0.1.1?集合及其表示1
0.1.2?子集2
0.1.3?冪集3
0.2?集合上的運(yùn)算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?集合及子集的計(jì)算機(jī)表示13
0.4.4?串和正則表達(dá)式14
0.5?整數(shù)的分解16
0.5.1?整除及素?cái)?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?矩陣的運(yùn)算23
0.6.3?布爾矩陣運(yùn)算26
0.7?算法和算法語言28
0.7.1?算法簡介28
0.7.2?算法概念29
0.7.3?算法語言31
0.7.4?遞歸算法34
0.8?數(shù)學(xué)結(jié)構(gòu)36
0.9?習(xí)題39
本章小結(jié)45
第1章?邏輯46
A命題邏輯46
1.1?命題和邏輯運(yùn)算46
1.1.1?命題46
1.1.2?邏輯聯(lián)結(jié)詞和復(fù)合命題47
1.1.3?邏輯和位運(yùn)算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?一些計(jì)算機(jī)應(yīng)用64
1.6?形式推理系統(tǒng)66
1.6.1?形式推演規(guī)則66
1.6.2?形式可推演性的一些性質(zhì)69
1.6.3?形式推演實(shí)例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?邏輯等價和蘊(yùn)涵85
1.10?范式90
1.11?一階邏輯的形式推理系統(tǒng)93
1.12?數(shù)學(xué)歸納法97
1.12.1?歸納推理和演繹推理97
1.12.2?數(shù)學(xué)歸納法99
1.12.3?數(shù)學(xué)歸納法在證明不等式中的應(yīng)用102
1.12.4?數(shù)學(xué)歸納法在其它方面的應(yīng)用103
1.13?習(xí)題106
本章小結(jié)111
第2章?計(jì)數(shù)114
2.1?計(jì)數(shù)的兩個基本原理114
2.1.1?加法原理114
2.1.2?乘法原理115
2.2?排列與組合115
2.2.1?排列115
2.2.2?組合119
2.2.3?二項(xiàng)式定理121
2.2.4?多項(xiàng)式定理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?容斥原理的應(yīng)用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?習(xí)題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)系及其應(yīng)用173
3.3?復(fù)合關(guān)系和逆關(guān)系175
3.3.1?復(fù)合關(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)系的計(jì)數(shù)191
3.7?關(guān)系的閉包193
3.7.1?關(guān)系閉包的基本概念193
3.7.2?求傳遞閉包的Warshall?算法196
3.8?習(xí)題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ù)的運(yùn)算213
4.4?基數(shù)216
4.4.1?基數(shù)216
4.4.2?可數(shù)集與不可數(shù)集218
4.4.3?基數(shù)的比較220
4.5?用于計(jì)算機(jī)科學(xué)的函數(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?習(xí)題231
本章小結(jié)234
第5章?群、環(huán)和域236
5.1?預(yù)備知識236
5.1.1?一些基本運(yùn)算236
5.1.2?特殊元素240
5.1.3?同態(tài)與同構(gòu)244
5.2?半群和獨(dú)異點(diǎn)246
5.2.1?半群246
5.2.2