內容簡介

本書針對本科離散數學課程的要點和關鍵問題，深入淺出地介紹了數理邏輯、集合論、圖論、代數結構和布爾代數、網絡模型、組合數學理論和算法等與計算機科學密切相關的問題，既著重於各部分內容之間的緊密聯繫，又深入探討各部分內容的概念、理論、算法和實際應用，本書敘述嚴謹，推演詳盡。各章配有習題，可為讀者迅速掌握有關知識提供有效的幫助。

目錄

  前言
*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 判斷有效結論的方法和規則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.的約束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個與量詞有關的推理規則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 代數繫統的同態和同構164
6.4 半群和獨異點168
6.5 子半群和子獨異點172
6.6 群和子群173
6.7 交換群和循環群181
6.8 子群的陪集及拉格朗日定理184
6.9 置換群188
6.10 環和域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.1 有向樹和根樹的概念285
9.3.2 m叉樹和二叉樹286
9.4 樹的遍歷289
9.5 *優樹與Huffman算法290
9.6 *佳前綴碼291
本章習題293
*10章 計數方法和分類原理295
10.1 基本原理295
10.1.1 乘法原理295
10.1.2 加法原理296
10.2 排列與組合297
10.3 可重復的排列與組合301
10.4 鴿巢原理303
本章習題306
附錄A 模擬試卷1308
附錄B 模擬試卷2311
參考文獻313