本書針對本科離散數(shù)學課程的要點和關(guān)鍵問題，深入淺出地介紹了數(shù)理邏輯、集合論、圖論、代數(shù)結(jié)構(gòu)和布爾代數(shù)、網(wǎng)絡模型、組合數(shù)學理論和算法等與計算機科學密切相關(guān)的問題，既著重于各部分內(nèi)容之間的緊密聯(lián)系，又深入探討各部分內(nèi)容的概念、理論、算法和實際應用，本書敘述嚴謹，推演詳盡。各章配有習題，可為讀者迅速掌握有關(guān)知識提供有效的幫助。
離散數(shù)學是計算機及相關(guān)專業(yè)的重要數(shù)學基礎之一，它是以離散型變量、離散數(shù)量關(guān)系和離散結(jié)構(gòu)模型為研究對象，以研究離散型變量的結(jié)構(gòu)和相互間的關(guān)系為主要目標的一門學科，內(nèi)容包括數(shù)理邏輯、抽象代數(shù)、古典概率、組合學、圖論、集合論、數(shù)論、自動機和形式語言、可計算性和可判定性、離散幾何等.
18世紀以前，數(shù)學基本上是研究離散對象的數(shù)量和空間關(guān)系的科學.天文學、物理學的發(fā)展，如牛頓三大力學定律等的研究，極大地推動了連續(xù)數(shù)學的發(fā)展.在這個時期，除了抽象代數(shù)外，屬于離散數(shù)學范圍的組合學（包括圖論）、數(shù)理邏輯等一直處于相對停滯的狀態(tài).但自20世紀30年代起，隨著圖靈提出計算機的理論模型圖靈機，以及電子計算機的迅猛發(fā)展，離散數(shù)學重新煥發(fā)青春.
由于電子計算機是一個離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系，因此，無論計算機科學本身，還是與計算機科學及其應用密切相關(guān)的現(xiàn)代科學研究領(lǐng)域，都面臨著如何對離散結(jié)構(gòu)建立相應的數(shù)學模型，以及如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學模型離散化，從而可由計算機進行處理等問題.于是離散數(shù)學的地位不斷攀升，成為近代數(shù)學的一個重要分支.
本書系統(tǒng)地介紹了離散數(shù)學各個分支的基本概念、基本理論和基本方法.這些概念、理論以及方法大量地應用在數(shù)字電路、編譯原理、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)、算法的分析與設計、人工智能、計算機網(wǎng)絡等專業(yè)課程中，為學生提高專業(yè)理論水平打下堅實的基礎.同時，本書著重培養(yǎng)學生的抽象概括能力、邏輯思維能力、歸納構(gòu)造能力，有益于培養(yǎng)學生嚴謹、規(guī)范的科學態(tài)度.
本書在構(gòu)思、編寫過程中參考了一些書籍和文獻（已在本書的參考文獻中列出），在此對這些文獻的作者表示感謝.
本書共10章，內(nèi)容包括：命題邏輯、謂詞邏輯、集合及其運算、二元關(guān)系、函數(shù)、代數(shù)結(jié)構(gòu)、格和布爾代數(shù)、圖論、樹、計數(shù)方法和分類原理.每章均有豐富的例題，幫助讀者理解知識點；每章后配有相關(guān)習題，可供讀者鞏固知識點.
本書第1、2、4、7、9、10章由邵秀麗完成，習題由邵秀麗和任明明完成，第3、5、6、8章由張瑞勛完成，任明明負責全書的終統(tǒng)稿，全書經(jīng)過三人共同討論和修改完稿.
本書依據(jù)作者在南開大學一直使用的課程講義整理而成，但由于作者經(jīng)驗所限，書中難免會有疏漏和錯誤之處，希望讀者給予批評和指正.
作者
2020年于南開大學
前言
第1章 命題邏輯1
1.1 引言1
1.2 命題與命題聯(lián)結(jié)詞1
1.2.1 命題的概念1
1.2.2 命題標識符和命題分類3
1.2.3 命題聯(lián)結(jié)詞3
1.3 翻譯、命題公式和真值表7
1.3.1 翻譯7
1.3.2 命題公式9
1.3.3 真值情況和真值表10
1.4 永真式、永假式和等價關(guān)系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 永真蘊涵關(guān)系的判斷20
1.6 其他聯(lián)結(jié)詞22
1.6.1 其他聯(lián)結(jié)詞的定義22
1.6.2 與非聯(lián)結(jié)詞的性質(zhì)23
1.6.3 或非聯(lián)結(jié)詞的性質(zhì)23
1.6.4 異或聯(lián)結(jié)詞的性質(zhì)24
1.6.5 小聯(lián)結(jié)詞組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 判斷有效結(jié)論的方法和規(guī)則41
本章習題48
第2章 謂詞邏輯53
2.1 謂詞的基本概念53
2.2 個體、謂詞及表達式54
2.3 命題函數(shù)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ān)的推理規(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 集合的相等或包含關(guān)系88
3.1.4 集合的基數(shù)90
3.2 集合的運算90
3.3 基本的集合運算律93
3.4 包含排斥原理99
本章習題103
第4章 二元關(guān)系105
4.1 序偶和笛卡兒乘積105
4.2 關(guān)系及其表示108
4.3 復合關(guān)系和逆關(guān)系112
4.4 關(guān)系的性質(zhì)118
4.5 關(guān)系的閉包124
4.6 等價關(guān)系132
4.7 序關(guān)系135
本章習題139
第5章 函數(shù)141
5.1 函數(shù)的概念141
5.2 函數(shù)的類型143
5.3 復合函數(shù)147
5.4 逆函數(shù)149
本章習題153
第6章 代數(shù)結(jié)構(gòu)155
6.1 代數(shù)系統(tǒng)的一般概念155
6.2 代數(shù)系統(tǒng)的運算性質(zhì)157
6.3 代數(shù)系統(tǒng)的同態(tài)和同構(gòu)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章 格和布爾代數(shù)199
7.1 格的基本概念199
7.2 格的基本性質(zhì)202
7.3 幾種特殊的格207
7.4 有界格和有補格212
7.5 布爾代數(shù)214
本章習題216
第8章 圖論219
8.1 圖的基本定義及相關(guān)術(shù)語219
8.1.1 圖的概念219
8.1.2 圖的邊點之間的關(guān)系221
8.1.3 圖的分類222
8.2 結(jié)點的度數(shù)及其計算224
8.3 子圖、補圖和圖的同構(gòu)227
8.3.1 子圖的概念227
8.3.2 補圖的概念229
8.3.3 圖的同構(gòu)概念230
8.4 通路、回路和連通性232
8.4.1 通路和回路的概念232
8.4.2 簡單有向圖的連通性235
8.4.3 無向圖的連通性238
8.5 圖的矩陣表示241
8.5.1 無向圖與有向圖的關(guān)聯(lián)矩陣241
8.5.2 圖的鄰接矩陣242
8.5.3 有向圖的可達矩陣244
8.6 歐拉圖與哈密頓圖245
8.6.1 歐拉圖245
8.6.2 哈密頓圖251
8.7 路徑和關(guān)鍵路徑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 對偶圖的性質(zhì)270
8.9.4 圖的著色271
8.9.5 地圖的著色與平面圖的點著色272
本章習題273
第9章 樹277
9.1 無向樹及其性質(zhì)277
9.1.1 樹的基本概念277
9.1.2 無向樹的性質(zhì)277
9.2 生成樹和小生成樹280
9.3 有向樹、根樹和二叉樹285
9.3
書單推薦
