離散數學基礎

本書面向“新工科”建設背景下普通高等學校的電腦類和軟件工程專業類的本科生，以培養學生離散建模基礎能力為目標，論述邏輯、證明、集合、函數、關系、算法、整數與同餘、組合計數、圖論以及代數系統相關基礎知識，覆蓋Computer Science Curricula 2013離散結構知識體的所有知識單元。與傳統離散數學教材相比，

喬海燕，男，1983年畢業於南開大學數學系，現為中山大學計算機學院副教授。
從事形式化證明和程序驗證研究，主講離散數學和數據結構等課程。
曾主編《數據結構與算法實驗實踐教程》，翻譯《Haskell函數式程序設計》《算法設計與應用》《Python 3.6編程實踐指南》等教材。

目錄
第1 章  基礎知識  1
1.1  邏輯語言 1
1.2  集合語言 5
1.3  圖論語言 9
1.4  代數語言 13
1.5  算法語言 14
1.6  本章小結 20
1.7  習題  21

第2 章  命題邏輯 24
2.1  命題邏輯的基本概念  24
2.1.1  命題與真值 24
2.1.2  原子命題與復合命題 25
2.2  命題邏輯公式的語法  25
2.2.1  命題邏輯公式的定義 26
2.2.2  命題邏輯公式的語法性質 28
2.2.3  命題邏輯公式的簡寫 31
2.3  命題邏輯公式的語義  32
2.3.1  命題邏輯公式的真值定義 32
2.3.2  命題邏輯公式的真值表 35
2.3.3  命題邏輯公式的分類 37
2.4  命題邏輯的等值演算  40
2.4.1  命題邏輯公式的邏輯等值 40
2.4.2  基本邏輯等值式 41
2.4.3  命題邏輯公式的範式 44
2.5  命題邏輯的推理理論  48
2.5.1  推理的有效性 49
2.5.2  命題邏輯的自然推理系統 50
2.5.3  構造驗證推理有效性的論證  54
2.6  命題邏輯的應用 60
2.6.1  自然語言命題的符號化 60
2.6.2  普通邏輯問題的符號化分析  67
2.6.3  算法性質的邏輯分析 73
2.7  本章小結  75
2.8  習題 75

第3 章  一階邏輯  81
3.1  一階邏輯的基本概念 81
3.2  一階邏輯公式的語法 83
3.2.1  一階邏輯公式的符號 83
3.2.2  一階邏輯公式的定義 84
3.2.3  自由變量和約束變量 86
3.3  一階邏輯公式的語義 89
3.3.1  一階邏輯公式的解釋 89
3.3.2  一階邏輯公式的真值 91
3.3.3  一階邏輯公式的分類 97
3.4  一階邏輯的等值演算 100
3.4.1  一階邏輯公式的邏輯等值 100
3.4.2  量詞公式的基本等值式 103
3.4.3  一階邏輯的前束範式 106
3.5  一階邏輯的推理理論 110
3.5.1  一階邏輯推理的有效性 110
3.5.2  量詞公式的推理規則 112
3.5.3  一階邏輯的自然推理舉例 116
3.6  一階邏輯的應用  121
3.6.1  自然語言命題的符號化 122
3.6.2  自然語言推理有效性的驗證 128
3.6.3  算法性質的邏輯分析 130
3.7  本章小結 133
3.8  習題 134

第4 章  證明方法 139
4.1  數學證明導引 139
4.2  基本證明方法與策略 141
4.2.1  直接證明與間接證明 142
4.2.2  分情況證明  146
4.2.3  存在性證明  149
4.2.4  基本證明策略  152
4.3  歸納定義與歸納證明 154
4.3.1  數學歸納法與良序原理 154
4.3.2  歸納定義與結構歸納法 161
4.3.3  遞歸算法與歸納證明 168
4.4  本章小結 172
4.5  習題 173

第5 章  集合 179
5.1  集合的基本概念  179
5.1.1  集合的基本術語  179
5.1.2  定義集合的基本方法 181
5.1.3  文氏圖與成員關系表 184
5.2  集合運算 186
5.2.1  集合交  187
5.2.2  集合並  190
5.2.3  集合差與補  192
5.2.4  集合的冪集  194
5.2.5  集合運算的算法  195
5.3  集合等式 197
5.3.1  基於定義證明集合等式 197
5.3.2  集合等式演算  200
5.3.3  子集關系與集合等式 202
5.4  本章小結 206
5.5  習題 206

第6 章  關系 210
6.1  關系的基本概念  210
6.1.1  集合的笛卡兒積  210
6.1.2  關系的定義  212
6.1.3  關系的表示  214
6.1.4  關系的運算  216
6.2  關系的性質 222
6.2.1  關系的自反性與反自反性 223
6.2.2  關系的對稱性與反對稱性 225
6.2.3  關系的傳遞性  228
6.2.4  關系性質與關系運算 230
6.3  關系的閉包 233
6.3.1  關系閉包的定義  233
6.3.2  關系閉包的計算  235
6.3.3  Warshall 算法 240
6.4  特殊關系舉例 242
6.4.1  等價關系 242
6.4.2  偏序關系 247
6.5  本章小結 252
6.6  習題 253

第7 章  函數 259
7.1  函數的基礎知識  259
7.1.1  函數的基本概念  259
7.1.2  函數的性質  263
7.1.3  函數運算與函數的性質 266
7.2  集合基數的基礎知識 270
7.2.1  集合等勢  270
7.2.2  有窮集與無窮集  272
7.2.3  可數集與不可數集  276
7.3  函數的增長與算法效率分析 280
7.3.1  函數的增長  281
7.3.2  算法效率分析基礎  287
7.3.3  算法復雜度基礎知識 293
7.4  本章小結 295
7.5  習題 296

第8 章  計數與組合 301
8.1  組合計數的基本原理 301
8.1.1  加法原理和乘法原理 301
8.1.2  容斥原理  307
8.1.3  鴿籠原理  312
8.2  排列與組合 316
8.2.1  排列與組合的基本定義 316
8.2.2  二項式定理與組合等式 323
8.2.3  允許重復的排列與組合 328
8.2.4  再論容斥原理及其應用 333
8.2.5  排列與組合的生成算法 338
8.3  遞推關系式 342
8.3.1  計數問題的遞推關系式建模 342
8.3.2  線性遞推關系式求解 347
8.3.3  分治算法與遞推關系式 352
8.4  本章小結 355
8.5  習題 356

第9 章  圖與樹 362
9.1  圖的基礎知識 362
9.1.1  圖的基本概念  362
9.1.2  圖的連通性  368
9.1.3  圖的表示與存儲  373
9.1.4  無向圖的遍歷  377
9.2  樹的基礎知識 382
9.2.1  無向樹的定義  382
9.2.2  根樹的定義  384
9.2.3  樹的遍歷  386
9.3  帶權圖及其應用  390
9.3.1  帶權圖的最短距離  390
9.3.2  帶權圖的最小生成樹 395
9.3.3  哈夫曼樹  398
9.4  一些特殊的圖 402
9.4.1  平面圖  403
9.4.2  歐拉圖  406
9.4.3  哈密頓圖  407
9.5  本章小結 409
9.6  習題 410

第10章  代數系統 419
10.1  運算及其性質 419
10.1.1  運算的定義 419
10.1.2  運算的性質 422
10.1.3  運算性質的判定 427
10.2  代數及同態 430
10.2.1  代數與子代數 430
10.2.2  同餘關系與商代數 432
10.2.3  代數同態與同構 436
10.3  群的基礎知識 441
10.3.1  群的定義  442
10.3.2  群元素的階  445
10.3.3  子群與陪集  446
10.3.4  正規子群與商群  452
10.3.5  群同態  453
10.4  格與布爾代數 455
10.4.1  格的偏序定義與代數定義 455
10.4.2  分配格與有界格 458
10.4.3  布爾代數  460
10.5  本章小結  462
10.6  習題 463

第11章  結束語  468

參考文獻 471