前 言

離散數(shù)學(xué)是計算機學(xué)科的核心課程，是一門理論抽象、內(nèi)容廣泛、結(jié)構(gòu)嚴(yán)謹(jǐn)?shù)挠嬎銠C相關(guān)專業(yè)的基礎(chǔ)課程。它不僅與后續(xù)課程，如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、操作系統(tǒng)、人工智能等有緊密聯(lián)系，而且對于訓(xùn)練和培養(yǎng)學(xué)生的抽象和邏輯思維能力，提高學(xué)生的科研素質(zhì)方面都有著十分重要的作用。

為了適應(yīng)省級示范性軟件學(xué)院及計算機相關(guān)專業(yè)《離散數(shù)學(xué)》教學(xué)改革的需要，提高學(xué)生應(yīng)用理論知識解決實際問題能力的需要，根據(jù)教育部高等學(xué)校計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會頒布的計算機相關(guān)專業(yè)教學(xué)基本要求，針對地方院校的教學(xué)對象、教學(xué)特點和方法進(jìn)行研究，我們提出了“《離散數(shù)學(xué)》軟件工程化教學(xué)改革”研究課題和編寫應(yīng)用型《離散數(shù)學(xué)》教材任務(wù)，并得到教育主管部門的立項支持。為了編寫好本教材，參考了美國俄克拉荷馬（Oklahoma）大學(xué)的Beseme項目出版的《軟件工程數(shù)學(xué)》等教材。編寫教材內(nèi)容注重理論知識的講解和邏輯推理的訓(xùn)練，也注重應(yīng)用離散數(shù)學(xué)知識分析專業(yè)課程的實際問題，討論離散數(shù)學(xué)對后續(xù)專業(yè)課的影響，引入軟件工程化應(yīng)用范例和實踐性內(nèi)容，加強實踐能力的培養(yǎng)。

本書包含數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論四部分內(nèi)容。每部分內(nèi)容結(jié)合建構(gòu)主義教學(xué)理論，設(shè)計不同離散數(shù)學(xué)應(yīng)用案例，提供學(xué)習(xí)《離散數(shù)學(xué)》的應(yīng)用場景。每一章選擇了有意義的范例和實驗項目，有利于學(xué)生通過編程實踐增進(jìn)對離散數(shù)學(xué)知識的理解和應(yīng)用，提高學(xué)生的學(xué)習(xí)興趣。全書體系嚴(yán)謹(jǐn)、敘述深入淺出。每部分內(nèi)容都分為基礎(chǔ)知識章節(jié)和高級應(yīng)用章節(jié)（帶*部分），便于教師根據(jù)學(xué)時要求選講章節(jié)內(nèi)容，適合不同學(xué)時的授課（刪除帶**章節(jié)，可采用90學(xué)時教學(xué)，再刪除帶*章節(jié)，可采用60學(xué)時教學(xué)），也方便軟件開發(fā)人員參考應(yīng)用。

本書的數(shù)理邏輯部分第1～3章由邱曉紅編寫，集合論部分第4～7章由李光泉編寫，代數(shù)結(jié)構(gòu)部分第8～9章由張帆編寫，第10章由艾施榮編寫，圖論部分第11～13章由熊煥亮編寫。全書由邱曉紅教授進(jìn)行組織整理和統(tǒng)一風(fēng)格。本書配套提供的實驗程序源代碼和演示范例，很多出自教學(xué)過程中指導(dǎo)學(xué)生參加各類軟件大賽的作品，有些內(nèi)容是“《離散數(shù)學(xué)》軟件工程化教學(xué)改革”（JXJG-08-4-28）、“教學(xué)與科研有機結(jié)合提高教學(xué)質(zhì)量和學(xué)生綜合素質(zhì)的研究”（2008B2ZB04）、“實施本科生全程導(dǎo)師制教育培養(yǎng)模式的研究——以江西省高校軟件學(xué)院為例”（08YB078）、“軟件工程融合傳統(tǒng)專業(yè)復(fù)合型創(chuàng)新人才培養(yǎng)模式研究”（JXJG-12-6-15）等教改課題的研究成果，在此特別感謝有關(guān)單位領(lǐng)導(dǎo)和作者的支持。在編寫過程中還參閱了大量的《離散數(shù)學(xué)》書籍和有關(guān)教學(xué)研究論文資料，在此向有關(guān)作者表示衷心的感謝。

本書再版時，對有些章節(jié)順序作了適當(dāng)調(diào)整和刪減，修訂了初版中的錯誤，使得全書內(nèi)容邏輯層次更加清晰完整。再版過程中，南昌大學(xué)幸冬梅博士、江西理工大學(xué)劉展、曾麗華老師，審閱了全稿，提出了寶貴的意見和建議，在此深表謝意。

由于時間倉促及編輯者水平有限，懇請廣大讀者及同行專家批評指正。

編 者

2014年10月

前言
第一部分 數(shù)理邏輯
第1章 命題邏輯 3
1.1 命題及其表示 3
1.1.1 命題的基本概念 3
1.1.2 命題分類 4
1.1.3 命題標(biāo)識符 4
1.2 邏輯聯(lián)結(jié)詞 5
1.2.1 否定聯(lián)結(jié)詞 5
1.2.2 合取聯(lián)結(jié)詞 5
1.2.3 析取聯(lián)結(jié)詞 6
1.2.4 條件聯(lián)結(jié)詞 7
1.2.5 雙條件聯(lián)結(jié)詞 7
1.2.6 字位運算與布爾檢索 8
1.3 命題公式與解釋 9
1.3.1 命題公式 9
1.3.2 命題的符號化 10
1.4 真值表與等價公式 12
1.4.1 真值表 12
1.4.2 等價公式 13
1.5 命題公式的分類與蘊含式 17
1.5.1 命題公式的分類 17
1.5.2 重言式與矛盾式的性質(zhì) 18
1.5.3 蘊含式 18
1.6 其他邏輯聯(lián)結(jié)詞和最小功能完備聯(lián)結(jié)詞組 21
1.6.1 其他邏輯聯(lián)結(jié)詞 21
1.6.2 最小功能完備聯(lián)結(jié)詞組 22
1.6.3* 聯(lián)結(jié)詞的邏輯電路表示 23
1.7 對偶與范式 24
1.7.1 對偶式與對偶原理 24
1.7.2 命題公式的范式 26
1.7.3 命題公式的主析取范式和主合取范式 28
1.8 推理理論 37
1.8.1 直接證法 38
1.8.2 間接證法 40
習(xí)題一 42
實驗一 真值表的程序計算 47
第2章 謂詞邏輯 49
2.1 謂詞的基本概念 49
2.1.1 個體和謂詞 49
2.1.2 量詞 51
2.2 謂詞公式與符號化解釋 52
2.2.1 謂詞公式 52
2.2.2 謂詞公式的符號化 53
2.3 變元的約束 54
2.3.1 約束變元和自由變元 54
2.3.2 換名規(guī)則 55
2.3.3 代替規(guī)則 56
2.4 謂詞演算的等價式與蘊含式 56
2.4.1 謂詞公式的賦值 56
2.4.2 謂詞公式的分類 57
2.4.3 謂詞演算的等價式 58
2.4.4 謂詞演算的蘊含式 62
2.5* 謂詞公式范式 64
2.5.1 前束范式 64
2.5.2 斯柯林范式 65
2.6* 謂詞演算的推理理論 66
2.6.1 US規(guī)則（Universal Specification，全稱指定規(guī)則） 66
2.6.2 UG規(guī)則（Universal Generalization，全稱推廣規(guī)則） 66
2.6.3 ES規(guī)則（Existential Specification，存在指定規(guī)則） 66
2.6.4 EG規(guī)則（Existential Generalization，存在推廣規(guī)則） 67
習(xí)題二 71
實驗二 命題邏輯簡單推理系統(tǒng) 73
第3章 基于歸結(jié)原理的推理證明** 75
3.1 謂詞公式與子句集 75
3.1.1 斯柯林（Skolem）標(biāo)準(zhǔn)范式 75
3.1.2 子句與子句集 76
3.1.3 不可滿足意義下的一致性 76
3.1.4 P＝P1∧P2∧…∧Pn的子句集 76
3.2 海伯倫（Herbrand）理論 77
3.2.1 H域 77
3.2.2 原子集 77
3.2.3 H域上的解釋 77
3.3 歸結(jié)原理（Resolution Method） 78
3.3.1 置換與合一 78
3.3.2 命題邏輯中的歸結(jié)原理 79
3.3.3 一階謂詞邏輯中的歸結(jié)原理 80
3.3.4 歸結(jié)原理的完備性 81
3.3.5 利用歸結(jié)原理進(jìn)行定理證明 81
3.3.6 應(yīng)用歸結(jié)原理進(jìn)行問題求解 81
3.4 歸結(jié)過程的控制策略 83
3.4.1 引入控制策略 83
3.4.2 歸結(jié)控制策略及其應(yīng)用舉例 83
習(xí)題三 84
實驗三 歸結(jié)原理的程序?qū)崿F(xiàn) 85
第二部分 集合論
第4章 集合及其運算 89
4.1 集合的概念及其表示 89
4.1.1 集合的概念 89
4.1.2 集合與集合間的關(guān)系 90
4.1.3 冪集（Power Set） 91
4.2 集合的基本運算 91
4.2.1 集合的并（Union）運算 91
4.2.2 集合的交（Intersection）運算 92
4.2.3 集合的交運算與并運算之間的關(guān)系 93
4.2.4 集合的補（Substraction）運算 93
4.2.5 集合的對稱差（Symmetric Difference）運算 94
4.2.6 集合的計算機表示 96
4.3 集合中元素的計數(shù) 97
4.3.1 兩個基本原理 97
4.3.2 排列、組合 97
4.3.3 容斥原理 98
4.4 集合的應(yīng)用 100
4.4.1 數(shù)據(jù)表的并（∪）運算 101
4.4.2 數(shù)據(jù)表的差（-）運算 101
4.4.3 數(shù)據(jù)表的交（∩）運算 101
習(xí)題四 102
實驗四 集合的基本運算 104
第5章 二元關(guān)系 106
5.1 集合的笛卡兒積 106
5.1.1 序偶（Ordered Pair） 106
5.1.2 笛卡兒積（Cartesian Product） 107
5.2 二元關(guān)系 109
5.2.1 二元關(guān)系的基本概念 109
5.2.2 二元關(guān)系的表示 109
5.2.3 關(guān)系的運算 110
5.2.4 關(guān)系的性質(zhì) 114
5.2.5 關(guān)系的閉包（Closure）運算 116
5.3 等價關(guān)系 122
5.3.1 集合的劃分（Partion of Set） 122
5.3.2 等價關(guān)系（Equivalent Relation）與等價類 124
5.4 相容關(guān)系* 127
5.4.1 集合的覆蓋（Covering） 127
5.4.2 相容關(guān)系（Consistent Relation）與相容類 127
5.5 偏序關(guān)系 130
5.5.1 偏序關(guān)系（Partial Relation）與偏序集的概念 130
5.5.2 偏序集的哈斯（Hasse）圖 131
5.5.3 偏序集中的特殊元 132
5.5.4 全序關(guān)系（Complete Partial Relation）及其應(yīng)用 134
5.6 關(guān)系的應(yīng)用 135
5.6.1 等價關(guān)系在計算機中的應(yīng)用 135
5.6.2 序關(guān)系在項目管理中的應(yīng)用 136
習(xí)題五 137
實驗五 求關(guān)系的閉包 140
第6章 函數(shù) 142
6.1 函數(shù)的概念 142
6.1.1 函數(shù)（Function）的概念 142
6.1.2 幾類特殊函數(shù) 143
6.2 逆函數(shù)與復(fù)合函數(shù) 145
6.2.1 逆函數(shù) 145
6.2.2 復(fù)合函數(shù) 146
習(xí)題六 148
實驗六 函數(shù)的圖形可視化 150
第7章 集合的基數(shù)** 151
7.1 集合的等勢與優(yōu)勢 151
7.2 基數(shù)、可數(shù)集與不可數(shù)集 151
7.2.1 基數(shù) 152
7.2.2 可數(shù)集與不可數(shù)集 153
7.2.3 基數(shù)的比較 157
習(xí)題七 159
實驗七 自然數(shù)性質(zhì)的可視化表示 160
第三部分 代數(shù)結(jié)構(gòu)
第8章 代數(shù)系統(tǒng) 163
8.1 代數(shù)系統(tǒng)的概念 163
8.2 代數(shù)系統(tǒng)的運算及其性質(zhì) 165
8.3 半群、群與子群 170
8.4 同態(tài)與同構(gòu)* 175
8.5 交換群與循環(huán)群、置換群 182
8.5.1 交換群 182
8.5.2 循環(huán)群 183
8.5.3 置換群 184
8.6 子群與群的陪集分解* 186
8.7 環(huán)與域* 189
習(xí)題八 194
實驗八 代數(shù)系統(tǒng)的基本運算 198
第9章 形式語言和自動機 200
9.1 語言 200
9.2 形式語言和文法 203
9.3 有限狀態(tài)機 205
9.4 有限狀態(tài)自動機 206
9.5 語言與自動機的關(guān)系* 211
習(xí)題九 215
實驗九 設(shè)計輸出狀態(tài)自動機實驗 219
第10章 格與布爾代數(shù)* 220
10.1 格的概念 220
10.2 分配格 228
10.3 有補格 232
10.4 布爾代數(shù)與布爾表達(dá)式** 234
10.5 數(shù)字電路邏輯運算 243
習(xí)題十 246
實驗十 代數(shù)系統(tǒng)綜合課程設(shè)計 247
第四部分 圖論
第11章 圖的基本概念 251
11.1 圖的概念 251
11.1.1 無向圖和有向圖 251
11.1.2 簡單圖、多重圖和同構(gòu)圖 252
11.1.3 完全圖和正則圖 255
11.1.4 幾種特殊的圖 255
11.1.5 子圖 257
11.1.6 圖的操作 258
11.2 圖的連通性 259
11.2.1 通路與回路 259
11.2.2 連通圖 260
11.2.3 二部圖 263
11.3 圖的矩陣表示 264
11.3.1 關(guān)聯(lián)矩陣 265
11.3.2 鄰接矩陣 266
11.3.3 可達(dá)矩陣 268
11.4 圖的運算 268
11.5 歐拉圖 269
11.5.1 歐拉通路和回路 269
11.5.2 半歐拉圖和歐拉圖 270
11.6 哈密頓圖 273
11.6.1 哈密頓圖 274
11.6.2 哈密頓圖的判斷條件 275
11.7 帶權(quán)圖 278
11.8 平面圖 278
11.8.1 平面圖的基本概念及性質(zhì) 278
11.8.2 庫拉托夫斯基定理 280
11.8.3 平面圖著色及應(yīng)用 281
11.8.4 邊著色 282
11.9 應(yīng)用舉例* 284
11.9.1 中國郵路問題 284
11.9.2 冰箱分隔問題 286
11.9.3 排課表問題 287
習(xí)題十一 288
實驗十一 應(yīng)用鄰接矩陣方法求解鎖具裝箱問題 292
第12章 樹 294
12.1 樹的概念及性質(zhì) 294
12.1.1 樹的定義 294
12.1.2 樹的一些性質(zhì) 294
12.2 最小生成樹 295
12.2.1 生成樹 295
12.2.2 最小代價生成樹 297
12.3 根樹 298
12.3.1 根樹的定義 298
12.3.2 根樹的分類 299
12.4 樹的應(yīng)用* 300
12.4.1 決策樹 300
12.4.2 博弈樹 301
習(xí)題十二 302
實驗十二 應(yīng)用生成樹算法求解旅行商問題 304
第13章 支配集、覆蓋集、獨立集與匹配理論* 306
13.1 支配集、覆蓋集、獨立集概念 306
13.1.1 支配集 306
13.1.2 覆蓋集 306
13.1.3 獨立集 307
13.2 邊覆蓋集與匹配 308
13.3 二部圖中的匹配 311
13.4 圖論的綜合應(yīng)用舉例** 312
13.4.1 會議議程安排問題 312
13.4.2 大中型工程項目的優(yōu)化 315
習(xí)題十三 320
實驗十三 程序求解支配集、獨立集問題 322
《離散數(shù)學(xué)》常用符號表 323
參考文獻(xiàn) 327

1. 大學(xué)生創(chuàng)新創(chuàng)業(yè)基礎(chǔ) [主編 姜國權(quán) 姜福佳]
2. 信息技術(shù)（微課版） [王云　徐江鴻　李清霞　羅學(xué)鋒　]
3. 管理基礎(chǔ)與實務(wù) [主編 王鳳基 顏漢軍]
4. 高等數(shù)學(xué)導(dǎo)學(xué)篇（下冊） [主編 李文婧 胡雷 尹金生]
5. 高等數(shù)學(xué)導(dǎo)學(xué)篇（上冊） [主編 李文婧 胡雷 尹金生]
6. 高等數(shù)學(xué)（下冊） [主編 李愛芹 胡雷 尹金生]
7. 高等數(shù)學(xué)（上冊） [主編 李愛芹 胡雷 尹金生]
8. 人工智能應(yīng)用基礎(chǔ) [主編 楊纓 李佳]
9. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
10. 電路與電子技術(shù)Ⅱ——電路分析基礎(chǔ) [主編 陳曉 金哲]
11. 人工智能概論（第二版） [主編　任云暉　丁紅　徐迎春 ]
12. 信息時代美育之道 [主編　劉宏宇　黎婭]
13. 數(shù)字媒體交互設(shè)計項目式教程（微課版） [主編　蘇陸]
14. Amazing！兒童英語自然拼讀分級教材（全8冊） [王玲　編著]
15. Spark大數(shù)據(jù)處理技術(shù) [主編　劉仁山　周洪翠　莊新妍]
16. 人工智能算法與實踐 [主編　梁琨　張翼英]
17. 計算機網(wǎng)絡(luò)技術(shù)項目化教程（微課版） [主編 王艷萍 安華萍]
18. 數(shù)據(jù)清洗 [黃源　劉智楊　孫大松]
19. 電路設(shè)計與PCB制作實操教程 [主編 周永宏]
20. 電路與電子技術(shù)Ⅰ—數(shù)字電子技術(shù) [主編 鄭玉珍 王淑琴]
21. Java編程基礎(chǔ)案例式教程 [主編 陳艷華 唐春蘭]
22. Python語言同步案例習(xí)題精解 [主編 肖朝暉]
23. Excel在會計工作中的應(yīng)用（第三版） [主 編 趙艷莉 耿聰慧]
24. 應(yīng)用數(shù)學(xué) [主編 劉東海 劉麗瑤]
25. Web用戶界面設(shè)計與制作 [主編 趙娟]
26. 計算機網(wǎng)絡(luò)基礎(chǔ)創(chuàng)新教程（模塊化+課程思政版） [主編 唐繼勇 李旭]
27. 計算機應(yīng)用技術(shù)基礎(chǔ)案例教程 [主編 周麗娟 王璐]
28. Unity應(yīng)用開發(fā)與實戰(zhàn)（微課版） [主 編 程永恒]
29. PHP程序設(shè)計項目化教程 [主 編 杜海穎]
30. 文學(xué)基礎(chǔ)與影視欣賞 [楊華軻 朱偉利 畢雪燕 羅玲誼]