第1章 命題邏輯1

1.1 現代邏輯學的基本研究方法1

1.2 命題及其表示法3

1.2.1 命題的概念3

1.2.2 聯結詞4

1.3 命題公式與語句形式化7

1.3.1 命題公式的定義7

1.3.2 公式的層次8

1.3.3 語句形式化8

1.3.4 復合命題真假值9

1.3.5 真值表10

1.4 重言式11

1.4.1 重言式概述11

1.4.2 邏輯等價式13

1.4.3 等值演算15

1.5 對偶與範式16

1.5.1 對偶16

1.5.2 簡單合取式和簡單析取式16

1.5.3 範式17

1.5.4 範式的性--主範式19

1.6 其他聯結詞24

1.6.真值函數24

1.6.2 真值函數與命題公式的關繫25

1.6.3 聯結詞完備集25

1.6.素聯結詞構成的聯結詞完備集26

1.7 命題演算的推理理論27

1.7.1 有效推理27

1.7.2 有效推理的等價定理29離散數學（第2版）

1.7.3 重言蘊涵式31

1.7.4 形式推理繫統32

1.7.5 自然推理繫統p235

1.8 命題演算中的歸結推理42

1.8.1 歸結推理規則42

1.8.2 歸結反演43

1.8.3 命題邏輯歸結反演的合理性和完備性44

習題44

第2章 謂詞邏輯53

2.1 謂詞邏輯的基本概念53

2.1.1 個體詞54

2.1.2 謂詞54

2.1.3 量詞55

2.2 謂詞邏輯公式與翻譯56

2.2.1 一階語言56

2.2.2 自由與約束57

2.2.3 閉公式58

2.2.4 謂詞邏輯公式的解釋59

2.2.5 謂詞邏輯命題符號化60

2.2.6 一階公式的分類63

2.3 謂詞邏輯等值演算64

2.3.1 基本等價式與置換規則64

2.3.2 謂詞邏輯前束範式68

2.4 謂詞演算的推理理論69

2.4.1 推理定律69

2.4.2 量詞消去與引入規則70

2.4.3 一階謂詞演算公理繫統f171

2.4.4 自然推理繫統f272

2.5 謂詞演算中的歸結推理74

2.5.1 子句型74

2.5.2 置換和合一76

2.5.3 合一算法78

2.5.4 歸結式79

2.5.5 歸結反演及其完備性80

2.6 邏輯在計算機科學中的作用81

2.6.1 邏輯與計算81

2.6.2 邏輯與計算機的起源82

2.6.3 邏輯與程序設計83

習題84

第3章 集合與關繫90

3.1 集合的概念和表示法90

3.1.1 集合的表示90

3.1.2 基本概念92

3.2 集合的運算93

3.2.1 集合的基本運算93

3.2.2 有窮計數集93

3.2.3 廣義交和廣義並95

3.3 有序對與笛卡兒積97

3.4 關繫及其表示99

3.4.1 基本概念99

3.4.2 關繫表示法100

3.5 關繫的運算102

3.5.1 基本概念102

3.5.2 復合關繫103

3.5.3 逆關繫104

3.5.4 關繫冪106

3.5.5 冪運算的性質107

3.6 關繫的性質109

3.6.1 關繫的5種基本性質109

3.6.2 關繫性質的等價描述 110

3.7 關繫的閉包113

3.7.1 基本概念114

3.7.2 閉包的性質118

3.8 集合的劃分與覆蓋119

3.9 等價關繫和等價類120

3.9.1 等價關繫120

3.9.2 等價類的性質122

3.9.3 商集與劃分123

3.10 相容關繫和相容類124

3.11 偏序關繫125

3.12 偏序集與哈斯圖126

3.13 包含排斥原理129

習題130

第4章 函數137

4.1 函數的定義137

4.1.1 函數和像137

4.1.2 函數的性質139

4.1.3 常用函數140

4.2 復合函數和反函數141

4.2.1 復合函數 141

4.2.2 反函數143

4.3 特征函數與模糊子集145

4.4 基數的概念147

4.4.1 後繼與歸納集147

4.4.2 自然數，有窮集，無窮集148

4.4.3 基數152

4.5 可數集與不可數集153

4.6 數學歸納法155

習題158

第5章 組合計數與離散概率162

5.1 基本原理162

5.1.1 加法原理162

5.1.2 乘法原理163

5.2 排列與組合164

5.2.1 排列164

5.2.2 組合164

5.3 排列組合生成算法165

5.3.1 排列生成算法165

5.3.2 組合生成算法 166

5.4 廣義的排列和組合169

5.5 二項式繫數和組合恆等式171

5.5.1 二項式定理171

5.5.2 組合恆等式172

5.6 鴿籠原理174

5.6.1 鴿籠原理的簡單形式174

5.6.2 鴿籠原理的一般形式174

5.7 遞推關繫及應用176

5.7.1 遞推定義函數176

5.7.2 遞推定義集合178

5.7.3 遞推關繫模型179

5.7.4 求解遞推關繫181

5.7.5 遞推在算法分析中的應用183

5.7.6 生成函數187

5.8 離散概率190

5.8.1 隨機事件與概率190

5.8.2 有限概率191

5.8.3 條件概率與獨立性 193

5.8.4 bayes定理194

習題195

第6章 圖論198

6.1 圖的基本概念198

6.1.1 圖的定義和表示198

6.1.2 圖的同構 202

6.1.3 完全圖與正則圖 204

6.1.4 子圖與補圖204

6.1.5 通路與回路206

6.2 圖的連通性208

6.2.1 無向圖的連通性208

6.2.2 有向圖的連通性209

6.3 圖的矩陣表示210

6.3.1 關聯矩陣210

6.3.2 有向圖的鄰接矩陣211

6.3.3 有向圖的可達矩陣 212

6.4 歐拉圖213

6.5 哈密頓圖215

6.6 二部圖218

6.6.1 二部圖及判別定理218

6.6.2 完備匹配219

6.7 平面圖221

6.7.1 平面圖及其判定定理221

6.7.2 平面圖的對偶圖226

6.8 帶權圖228

習題229

第7章 樹及其應用237

7.1 概述237

7.1.1 樹的定義及相關術語237

7.1.2 樹的性質239

7.2 生成樹240

7.3 小生成樹243

7.4 樹的遍歷246

7.5 二叉樹248

7.5.1 二叉樹的性質248

7.5.2 二叉搜索樹249

7.5.3 哈夫曼樹250

7.6 決策樹252

7.6.1 決策樹的定義252

7.6.2 短時間排序253

7.7 樹的同構254

7.8 博弈樹258

7.8.1 博弈樹的概念258

7.8.2 極大極小分析法258

習題260

第8章 代數繫統264

8.運算及其性質264

8.1.1 定義和表示 264

8.1.運算的性質 266

8.2 代數繫統268

8.2.1 定義和實例268

8.2.2 子代數繫統270

8.2.3 代數繫統的同態與同構270

8.3 半群與獨異點271

8.3.1 定義與性質271

8.3.2 子繫統與直積273

8.4 群273

8.4.1 群的定義 273

8.4.2 群的性質 275

8.4.3 子群的定義 278

8.4.4 特殊的群279

8.4.5 陪集與拉格朗日定理282

8.4.6 正規子群與商群283

8.4.7 群的同態與同構實例286

8.5 環與域288

8.5.1 環288

8.5.2 域289

8.6 格與布爾代數290

8.6.1 格290

8.6.2 布爾代數295

8.7 組合電路297

習題299

第9章 自動機、文法和語言306

9.1 串和語言306

9.2 形式文法307

9.3 有限狀態機310

9.4 有限狀態自動機312

9.5 不確定有限狀態自動機315

9.6 語言和自動機之間的關繫318

習題319

第10章 初等數論322

10.1 素數322

10.2 公約數與小公倍數323

10.3 同餘326

10.4 一次同餘方程和中國剩餘定理328

10.4.1 一次同餘方程328

10.4.2 中國剩餘定理329

10.5 歐拉定理和費馬小定理330

10.6 數論在密碼學中的應用331

10.6.1 公鑰密碼學331

10.6.2 rsa密碼332

習題333

附錄 歷史注記335

習題答案348

參考文獻370