離散結構

第1章 命題邏輯1
1.1 命題和邏輯運算1
1.1.1 命題1
1.1.2 邏輯聯(lián)結詞和復合命題2
1.2 合式公式6
1.2.1 語法6
1.2.2 語義（semantics）7
1.3 邏輯等價8
1.4 范式12
1.4.1 析取范式12
1.4.2 合取范式13
1.4.3 用等價替換方法構造主范式14
1.5 聯(lián)結詞的完備集及應用15
1.5.1 聯(lián)結詞的完備集15
1.5.2 一些計算機應用16
1.6 蘊涵和演繹19
1.7 本章小結22
習題23
第2章 一階邏輯26
2.1 謂詞和量詞26
2.1.1 謂詞26
2.1.2 量詞27
2.2 合式公式29
2.2.1 語法29
2.2.2 語義31
2.3 邏輯等價和蘊涵33
2.4 范式37
2.5 數學歸納法39
2.5.1 歸納推理和演繹推理39
2.5.2 數學歸納法41
2.5.3 數學歸納法的應用43
2.6 本章小結44
習題45第3章 集合48
3.1 集合及子集48
3.1.1 集合及其表示48
3.1.2 子集49
3.1.3 冪集50
3.1.4 多重集合51
3.2 集合上的運算51
3.2.1 集合的并51
3.2.2 集合的交52
3.2.3 集合的差53
3.2.4 集合的對稱差53
3.3 集合的笛卡兒乘積54
3.3.1 有序對54
3.3.2 集合的笛卡兒乘積55
3.4 本章小結56
習題56
第4章 關系60
4.1 關系的基本概念60
4.1.1 二元關系的定義60
4.1.2 關系矩陣62
4.1.3 關系圖63
4.1.4 n元關系及其應用64
4.2 復合關系和逆關系64
4.2.1 復合關系65
4.2.2 逆關系67
4.3 關系的性質69
4.4 等價關系和集合的劃分72
4.4.1 等價關系73
4.4.2 集合的劃分75
4.5 關系的閉包76
4.6 本章小結79
習題80
第5章 函數84
5.1 函數的基本概念84
5.2 特殊函數86
5.3 函數的運算88
5.4 一些常見的函數91
5.5 本章小結92
習題93
第6章 計數初步95
6.1 計數的兩個基本原理95
6.1.1 加法原理(addition principle of counting)95
6.1.2 乘法原理(multiplication principle of counting)96
6.2 排列與組合97
6.2.1 排列97
6.2.2 組合99
6.3 鴿籠原理101
6.4 容斥原理及其應用103
6.4.1 容斥原理103
6.4.2 容斥原理的應用104
6.5 遞歸關系106
6.5.1 遞歸關系模型106
6.5.2 遞歸關系的基本解法109
6.6 本章小結114
習題115
第7章 圖論118
7.1 圖的基本概念118
7.1.1 圖的定義、表示和一些術語118
7.1.2 圖的同構120
7.1.3 關聯(lián)矩陣和鄰接矩陣122
7.1.4 子圖122
7.1.5 頂點的度123
7.1.6 路和連通124
7.1.7 回路126
7.1.8 最短路問題127
7.2 歐拉圖130
7.2.1 基本概念130
7.2.2 中國郵遞員問題133
7.3 哈密爾頓圖134
7.3.1 基本概念134
7.3.2 巡回售貨員問題(TSP)137
7.4 可平面性137
7.4.1 平面圖和可平面圖137
7.4.2 平面圖的歐拉公式及其應用139
7.4.3 可平面圖的判定140
7.4.4 平面圖的對偶圖141
7.5 本章小結142
習題143
第8章 樹147
8.1 無向樹147
8.1.1 無向樹的定義和基本性質147
8.1.2 生成樹和最小生成樹149
8.2 有向樹及根樹151
8.2.1 有向樹及根樹的定義151
8.2.2 有序樹153
8.2.3 樹搜索155
8.2.4 前綴碼和最優(yōu)樹158
8.3 本章小結161
習題162
部分習題的提示與解答165
參考文獻176