本書針對本科離散數學課程的要點和關鍵問題，深入淺出地介紹了數理邏輯、集合論、圖論、代數結構和布爾代數、網絡模型、組合數學理論和算法等與計算機科學密切相關的問題，既著重于各部分內容之間的緊密聯系，又深入探討各部分內容的概念、理論、算法和實際應用，本書敘述嚴謹，推演詳盡。各章配有習題，可為讀者迅速掌握有關知識提供有效的幫助。
離散數學是計算機及相關專業(yè)的重要數學基礎之一，它是以離散型變量、離散數量關系和離散結構模型為研究對象，以研究離散型變量的結構和相互間的關系為主要目標的一門學科，內容包括數理邏輯、抽象代數、古典概率、組合學、圖論、集合論、數論、自動機和形式語言、可計算性和可判定性、離散幾何等.
18世紀以前，數學基本上是研究離散對象的數量和空間關系的科學.天文學、物理學的發(fā)展，如牛頓三大力學定律等的研究，極大地推動了連續(xù)數學的發(fā)展.在這個時期，除了抽象代數外，屬于離散數學范圍的組合學（包括圖論）、數理邏輯等一直處于相對停滯的狀態(tài).但自20世紀30年代起，隨著圖靈提出計算機的理論模型圖靈機，以及電子計算機的迅猛發(fā)展，離散數學重新煥發(fā)青春.
由于電子計算機是一個離散結構，它只能處理離散的或離散化了的數量關系，因此，無論計算機科學本身，還是與計算機科學及其應用密切相關的現代科學研究領域，都面臨著如何對離散結構建立相應的數學模型，以及如何將已用連續(xù)數量關系建立起來的數學模型離散化，從而可由計算機進行處理等問題.于是離散數學的地位不斷攀升，成為近代數學的一個重要分支.
本書系統地介紹了離散數學各個分支的基本概念、基本理論和基本方法.這些概念、理論以及方法大量地應用在數字電路、編譯原理、數據結構、操作系統、數據庫系統、算法的分析與設計、人工智能、計算機網絡等專業(yè)課程中，為學生提高專業(yè)理論水平打下堅實的基礎.同時，本書著重培養(yǎng)學生的抽象概括能力、邏輯思維能力、歸納構造能力，有益于培養(yǎng)學生嚴謹、規(guī)范的科學態(tài)度.
本書在構思、編寫過程中參考了一些書籍和文獻（已在本書的參考文獻中列出），在此對這些文獻的作者表示感謝.
本書共10章，內容包括：命題邏輯、謂詞邏輯、集合及其運算、二元關系、函數、代數結構、格和布爾代數、圖論、樹、計數方法和分類原理.每章均有豐富的例題，幫助讀者理解知識點；每章后配有相關習題，可供讀者鞏固知識點.
本書第1、2、4、7、9、10章由邵秀麗完成，習題由邵秀麗和任明明完成，第3、5、6、8章由張瑞勛完成，任明明負責全書的終統稿，全書經過三人共同討論和修改完稿.
本書依據作者在南開大學一直使用的課程講義整理而成，但由于作者經驗所限，書中難免會有疏漏和錯誤之處，希望讀者給予批評和指正.
作者
2020年于南開大學
前言
第1章 命題邏輯1
1.1 引言1
1.2 命題與命題聯結詞1
1.2.1 命題的概念1
1.2.2 命題標識符和命題分類3
1.2.3 命題聯結詞3
1.3 翻譯、命題公式和真值表7
1.3.1 翻譯7
1.3.2 命題公式9
1.3.3 真值情況和真值表10
1.4 永真式、永假式和等價關系12
1.5 等價式和蘊涵式14
1.5.1 等價公式14
1.5.2 等價定律公式14
1.5.3 子公式15
1.5.4 證明兩個公式等價的方法16
1.5.5 蘊涵式19
1.5.6 永真蘊涵關系的判斷20
1.6 其他聯結詞22
1.6.1 其他聯結詞的定義22
1.6.2 與非聯結詞的性質23
1.6.3 或非聯結詞的性質23
1.6.4 異或聯結詞的性質24
1.6.5 小聯結詞組25
1.7 對偶與范式26
1.7.1 對偶27
1.7.2 范式29
1.7.3 主析取范式31
1.7.4 主合取范式35
1.7.5 主范式的應用37
1.8 命題演算的推理理論39
1.8.1 推理的基本概念39
1.8.2 判斷有效結論的方法和規(guī)則41
本章習題48
第2章 謂詞邏輯53
2.1 謂詞的基本概念53
2.2 個體、謂詞及表達式54
2.3 命題函數57
2.4 量詞59
2.5 謂詞公式與翻譯62
2.5.1 謂詞公式62
2.5.2 謂詞邏輯的翻譯63
2.6 變元的約束65
2.7 謂詞公式的永真式、永假式、等價式和蘊涵式68
2.7.1 判定方法和基本公式69
2.7.2 謂詞等價式和蘊涵式70
2.7.3 謂詞公式的范式72
2.7.4 多個量詞的使用74
2.8 謂詞演算的推理理論76
2.8.1 4個與量詞有關的推理規(guī)則76
2.8.2 謂詞邏輯中推理的論證78
2.8.3 演算中常見的錯誤83
本章習題84
第3章 集合及其運算86
3.1 集合的概念與表示86
3.1.1 集合的概念86
3.1.2 集合的表示87
3.1.3 集合的相等或包含關系88
3.1.4 集合的基數90
3.2 集合的運算90
3.3 基本的集合運算律93
3.4 包含排斥原理99
本章習題103
第4章 二元關系105
4.1 序偶和笛卡兒乘積105
4.2 關系及其表示108
4.3 復合關系和逆關系112
4.4 關系的性質118
4.5 關系的閉包124
4.6 等價關系132
4.7 序關系135
本章習題139
第5章 函數141
5.1 函數的概念141
5.2 函數的類型143
5.3 復合函數147
5.4 逆函數149
本章習題153
第6章 代數結構155
6.1 代數系統的一般概念155
6.2 代數系統的運算性質157
6.3 代數系統的同態(tài)和同構164
6.4 半群和獨異點168
6.5 子半群和子獨異點172
6.6 群和子群173
6.7 交換群和循環(huán)群181
6.8 子群的陪集及拉格朗日定理184
6.9 置換群188
6.10 環(huán)和域190
本章習題196
第7章 格和布爾代數199
7.1 格的基本概念199
7.2 格的基本性質202
7.3 幾種特殊的格207
7.4 有界格和有補格212
7.5 布爾代數214
本章習題216
第8章 圖論219
8.1 圖的基本定義及相關術語219
8.1.1 圖的概念219
8.1.2 圖的邊點之間的關系221
8.1.3 圖的分類222
8.2 結點的度數及其計算224
8.3 子圖、補圖和圖的同構227
8.3.1 子圖的概念227
8.3.2 補圖的概念229
8.3.3 圖的同構概念230
8.4 通路、回路和連通性232
8.4.1 通路和回路的概念232
8.4.2 簡單有向圖的連通性235
8.4.3 無向圖的連通性238
8.5 圖的矩陣表示241
8.5.1 無向圖與有向圖的關聯矩陣241
8.5.2 圖的鄰接矩陣242
8.5.3 有向圖的可達矩陣244
8.6 歐拉圖與哈密頓圖245
8.6.1 歐拉圖245
8.6.2 哈密頓圖251
8.7 路徑和關鍵路徑257
8.7.1 路徑的概念257
8.7.2 路徑在實際中的應用259
8.7.3 歐拉圖的應用中國郵路問題259
8.7.4 哈密頓回路和貨郎擔問題260
8.8 平面圖262
8.8.1 平面圖的概念262
8.8.2 平面圖的面263
8.8.3 平面圖的判定264
8.9 對偶與著色269
8.9.1 對偶的基本概念269
8.9.2 平面圖的對偶圖的做法269
8.9.3 對偶圖的性質270
8.9.4 圖的著色271
8.9.5 地圖的著色與平面圖的點著色272
本章習題273
第9章 樹277
9.1 無向樹及其性質277
9.1.1 樹的基本概念277
9.1.2 無向樹的性質277
9.2 生成樹和小生成樹280
9.3 有向樹、根樹和二叉樹285
9.3
書單推薦
