離散數(shù)學(xué)基礎(chǔ)

本書認(rèn)真分析、總結(jié)、吸收了部分高校離散數(shù)學(xué)課程教學(xué)改革經(jīng)驗，以教育部高等教育教學(xué)課程的基本要求與課程改革精神及人才培養(yǎng)目標(biāo)為依據(jù)，在取材上注重基礎(chǔ)完整，講述上力求深入淺出，從而達(dá)到既為學(xué)生專業(yè)功能服務(wù)，又加強(qiáng)基本思維素質(zhì)訓(xùn)練的目的。

本書包括矩陣代數(shù)、數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論五部分，均為離散數(shù)學(xué)中的核心內(nèi)容。各章知識點豐富，采用模塊化設(shè)計；為提高學(xué)生對離散數(shù)學(xué)源流的認(rèn)識，每章后附興趣閱讀；每章均給出了本章重點知識的小結(jié)，有利于學(xué)生進(jìn)行系統(tǒng)的復(fù)習(xí)。

前 言

隨著現(xiàn)代社會對人才的要求越來越高，對于學(xué)生來講，只具備專業(yè)知識已經(jīng)不能適應(yīng)社會的需求。還必須具備較強(qiáng)的適應(yīng)能力、應(yīng)變能力、學(xué)習(xí)能力、創(chuàng)新能力等才能在日趨激烈的競爭中立于不敗之地，才能為社會作出更大的貢獻(xiàn)。而這些能力的基礎(chǔ)不但要有豐富的專業(yè)知識基礎(chǔ)，還要有良好的思維品質(zhì)。離散數(shù)學(xué)的學(xué)習(xí)，就最能體現(xiàn)這兩方面。

離散數(shù)學(xué)是應(yīng)用數(shù)學(xué)的一個重要分支，逐步成為本世紀(jì)的主流數(shù)學(xué)，也是計算機(jī)專業(yè)的核心課程之一。該課程是以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)，其研究對象一般是有限個或可數(shù)個元素，因此它充分描述了計算機(jī)科學(xué)離散性的特點。隨著計算機(jī)科學(xué)的發(fā)展，離散數(shù)學(xué)形成于20世紀(jì)70年代初期，是一門新興的工具性學(xué)科。該課程與計算機(jī)科學(xué)中的數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯理論、數(shù)據(jù)庫系統(tǒng)、人工智能、計算機(jī)網(wǎng)絡(luò)、算法分析、邏輯設(shè)計、系統(tǒng)結(jié)構(gòu)、容錯診斷、機(jī)器定理證明等理論課程聯(lián)系緊密。

通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散問題的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，通過思維品質(zhì)的培養(yǎng)和訓(xùn)練，提高觀察事物現(xiàn)象、分析問題本質(zhì)、解決問題的能力，養(yǎng)成良好的意志力、邏輯性、新穎性等思維習(xí)慣。為學(xué)生以后的學(xué)習(xí)、工作、生活打下堅實的基礎(chǔ)。

因此，本教材在具體編寫過程中，力求既介紹離散數(shù)學(xué)基礎(chǔ)知識的核心內(nèi)容，簡明扼要、通俗易懂，又注重理論聯(lián)系實際，融入啟發(fā)式思維訓(xùn)練，著重培養(yǎng)學(xué)生良好的思維品質(zhì)，加強(qiáng)學(xué)生系統(tǒng)性、創(chuàng)新性、發(fā)散性、堅韌性的思維訓(xùn)練。本教材在結(jié)合編者多年離散數(shù)學(xué)教學(xué)經(jīng)驗的基礎(chǔ)上，根據(jù)計算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生的特點，參考了國內(nèi)眾多教材的優(yōu)勢并借鑒國外教材的特點編寫而成的。本書的主要特點如下：

1．科學(xué)性

教材的整個體系保持了離散數(shù)學(xué)具有代表性的核心內(nèi)容，堅持少而精、釋義清楚、學(xué)以致用的原則，內(nèi)容安排上由淺入深，符合認(rèn)知規(guī)律，理論嚴(yán)謹(jǐn)、敘述明確簡練、邏輯性強(qiáng)，知識點脈絡(luò)清晰。

2．先進(jìn)性

大部分例題都融入啟發(fā)式思維訓(xùn)練，重點突出解題思路，注重培養(yǎng)學(xué)生的數(shù)學(xué)思維能力和分析、解決問題的能力。每一章都增加了應(yīng)用和相關(guān)離散數(shù)學(xué)源流的介紹，不但有助于提高學(xué)生的學(xué)習(xí)興趣，而且將基礎(chǔ)理論與相關(guān)實際問題相結(jié)合，變抽象思維為形象思維，提高學(xué)生思考能力，培養(yǎng)學(xué)生系統(tǒng)性、創(chuàng)新性、發(fā)散性、堅韌性的思維品質(zhì)。

3．實用性

每章都列出了學(xué)習(xí)目標(biāo)和小結(jié)，并配以大量習(xí)題和思考題，以便學(xué)生及時掌握知識點和知識結(jié)構(gòu)。

全書共5章。第一章由楊勇編寫，第二章由呂興漢編寫，第三章由吳杰編寫，第四章由任超、楊德山編寫，第五章由陳華峰編寫。每章節(jié)的應(yīng)用題例部分由鄭倫川和王瑤編寫。第一章是矩陣代數(shù)基礎(chǔ)知識，第二章介紹集合論；第三章是數(shù)理邏輯初步，第四章介紹代數(shù)系統(tǒng)，第五章主要介紹圖論的初步知識。全書由陳華峰與楊勇統(tǒng)稿。

本書不僅可以作為普通高等院校計算機(jī)科學(xué)與技術(shù)、軟件工程等相關(guān)專業(yè)本科的離散數(shù)學(xué)教材，也可以作為考研、計算機(jī)相關(guān)開發(fā)人員的參考書。

最后，特別感謝唐藝川教授為審閱本書所作出的辛勤勞動。感謝中國水利水電出版社的大力支持，使得本書得以順利出版。

由于作者水平有限，加之時間倉促，書中難免有不妥或錯誤之處，懇請廣大讀者批評指正。

編 者

2012年3月

前言

第一章 矩陣代數(shù) 1
本章學(xué)習(xí)目標(biāo) 1
第一節(jié) 行列式 1
一、行列式的定義 2
二、行列式的性質(zhì) 3
三、行列式的計算 5
四、克拉默法則 8
習(xí)題 9
第二節(jié) 矩陣的概念及矩陣的運算 11
一、矩陣的概念 11
二、矩陣的運算 13
三、矩陣的初等變換 15
四、矩陣的秩 16
五、逆矩陣 17
習(xí)題 19
第三節(jié) 線性方程組 20
一、線性方程組的基本概念和定理 20
二、線性方程組解的結(jié)構(gòu) 22
三、非齊次線性方程組的解的結(jié)構(gòu) 23
習(xí)題 24
第四節(jié) 矩陣在圖形變換中的應(yīng)用 26
一、常見的幾種二維幾何變換矩陣 26
二、三維圖形的基本變換矩陣 29
本章小結(jié) 30
復(fù)習(xí)題一 32
興趣閱讀——數(shù)學(xué)家韋達(dá)簡介 37
第二章 集合論 38
本章學(xué)習(xí)目標(biāo) 38
第一節(jié) 集合的基本概念與運算 38
一、集合的表示 38
二、集合之間的關(guān)系 39
三、集合的基本運算 40
習(xí)題 42
第二節(jié) 集合恒等式 43
一、基本集合恒等式 43
二、證明技巧 44
習(xí)題 45
第三節(jié) 包含排斥原理 46
習(xí)題 48
第四節(jié) 序偶與笛卡兒積 48
習(xí)題 50
第五節(jié) 關(guān)系及其表示 50
一、基本概念 50
二、關(guān)系表示法 51
習(xí)題 53
第六節(jié) 關(guān)系的運算 53
一、基本概念 53
二、運算的性質(zhì) 55
三、關(guān)系冪 55
四、冪運算的性質(zhì) 57
習(xí)題 57
第七節(jié) 關(guān)系的性質(zhì) 58
一、關(guān)系的五種基本性質(zhì) 58
二、關(guān)系性質(zhì)的等價 59
習(xí)題 61
第八節(jié) 關(guān)系的閉包 61
一、基本概念 61
二、閉包的性質(zhì) 64
習(xí)題 64
第九節(jié) 等價關(guān)系與相容關(guān)系 65
一、集合的劃分和覆蓋 65
二、等價關(guān)系 66
三、相容關(guān)系 69
習(xí)題 71
第十節(jié) 偏序關(guān)系 71
一、偏序關(guān)系的定義 71
二、偏序關(guān)系的哈斯圖 72
三、偏序集中特殊位置的元素 73
習(xí)題 75
第十一節(jié) 函數(shù)的概念 76
一、函數(shù)和像 76
二、函數(shù)的性質(zhì) 78
三、函數(shù)的復(fù)合 78
習(xí)題 79
本章小結(jié) 80
復(fù)習(xí)題二 81
興趣閱讀——數(shù)學(xué)家康托爾與集合論 84
第三章 數(shù)理邏輯 85
本章學(xué)習(xí)目標(biāo) 85
第一節(jié) 命題與聯(lián)結(jié)詞 85
一、命題的概念 85
二、復(fù)合命題與聯(lián)結(jié)詞 86
習(xí)題 89
第二節(jié) 命題公式與賦值 90
一、合式公式的定義 90
二、公式的賦值 91
三、真值表 91
習(xí)題 93
第三節(jié) 等價式與蘊含式 94
一、等價式的概念 94
二、用真值表判斷公式的等價 94
三、等價演算 95
四、蘊含式 97
習(xí)題 99
第四節(jié) 范式 101
一、簡單合取式和簡單析取式 101
二、范式 101
三、范式的唯一性——主范式 103
四、主析取范式的作用 107
五、主析取范式與主合取范式的聯(lián)系 108
習(xí)題 108
第五節(jié) 聯(lián)結(jié)詞的完備集 109
一、n元真值函數(shù) 109
二、真值函數(shù)與命題公式的關(guān)系 110
三、聯(lián)結(jié)詞完備集 110
四、單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集 111
習(xí)題 112
第六節(jié) 推理理論 113
一、有效推理 113
二、直接證法 113
三、間接證法 116
習(xí)題 119
第七節(jié) 謂詞邏輯的基本概念 120
一、個體詞 121
二、謂詞 121
三、量詞 122
四、謂詞邏輯命題符號化 122
習(xí)題 124
第八節(jié) 謂詞公式與翻譯 125
一、謂詞語言 125
二、自由與約束 126
三、閉式 126
四、謂詞公式的解釋 127
五、謂詞公式的分類 128
習(xí)題 129
第九節(jié) 謂詞邏輯等值式 130
一、常用等值式 130
二、基本規(guī)則 131
三、等值演算 132
習(xí)題 134
第十節(jié) 謂詞邏輯的前束范式 135
習(xí)題 136
第十一節(jié) 謂詞邏輯推理理論 136
一、推理定律 136
二、推理規(guī)則 137
習(xí)題 140
本章小結(jié) 140
復(fù)習(xí)題三 141
興趣閱讀——數(shù)理邏輯簡介 145
第四章 代數(shù)系統(tǒng) 149
本章學(xué)習(xí)目標(biāo) 149
第一節(jié) 代數(shù)系統(tǒng)的概念 149
習(xí)題 151
第二節(jié) 代數(shù)系統(tǒng)的運算及其性質(zhì) 152
一、運算的性質(zhì) 152
二、特殊元 155
習(xí)題 159
第三節(jié) 半群與含幺半群 161
一、半群 161
二、含幺半群 162
習(xí)題 164
第四節(jié) 群與子群 166
一、群 166
二、群的基本性質(zhì) 167
三、子群 169
習(xí)題 170
第五節(jié) 交換群、循環(huán)群與置換群 171
習(xí)題 173
第六節(jié) 環(huán)與域 174
一、環(huán) 174
二、域 176
習(xí)題 177
第七節(jié) 格的概念及性質(zhì) 178
一、格的定義 178
二、子格 180
三、格的性質(zhì) 181
四、作為代數(shù)系統(tǒng)的格 183
習(xí)題 183
第八節(jié) 分配格與模格 185
一、分配格 185
二、模格 187
習(xí)題 187
第九節(jié) 有界格與有補格 188
一、有界格 188
二、有補格 189
習(xí)題 190
第十節(jié) 布爾代數(shù) 191
一、布爾代數(shù)的概念 191
二、布爾代數(shù)的性質(zhì) 193
習(xí)題 195
本章小結(jié) 196
復(fù)習(xí)題四 197
興趣閱讀——群論的創(chuàng)始人伽羅華 200
第五章 圖論初步 202
本章學(xué)習(xí)目標(biāo) 202
第一節(jié) 圖的基本概念 202
一、圖的定義 202
二、圖的相關(guān)概念和規(guī)定 203
三、頂點的度數(shù)與握手定理 204
四、圖的同構(gòu)、完全圖與補圖 206
習(xí)題 208
第二節(jié) 路與回路 209
一、通路與回路 209
二、通路與回路的性質(zhì) 210
三、圖的連通性 211
習(xí)題 213
第三節(jié) 圖的矩陣表示 213
習(xí)題 217
第四節(jié) 歐拉圖與哈密爾頓圖 218
一、歐拉圖 218
二、哈密爾頓圖 219
習(xí)題 221
第五節(jié) 平面圖 222
一、平面圖的定義 222
二、歐拉公式 224
三、平面圖的著色 227
習(xí)題 229
第六節(jié) 樹 230
一、樹的定義 230
二、生成樹與最小生成樹 232
三、有向樹 234
四、二叉樹 236
習(xí)題 241
本章小結(jié) 242
復(fù)習(xí)題五 242
興趣閱讀——阿蘭•麥席森•圖靈與計算機(jī) 246
參考文獻(xiàn) 247

1. 高等數(shù)學(xué)導(dǎo)學(xué)篇（下冊） [主編 李文婧 胡雷 尹金生]
2. 高等數(shù)學(xué)導(dǎo)學(xué)篇（上冊） [主編 李文婧 胡雷 尹金生]
3. 高等數(shù)學(xué)（下冊） [主編 李愛芹 胡雷 尹金生]
4. 高等數(shù)學(xué)（上冊） [主編 李愛芹 胡雷 尹金生]
5. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
6. 電路與電子技術(shù)Ⅱ——電路分析基礎(chǔ) [主編 陳曉 金哲]
7. Spark大數(shù)據(jù)處理技術(shù) [主編　劉仁山　周洪翠　莊新妍]
8. 人工智能算法與實踐 [主編　梁琨　張翼英]
9. 數(shù)據(jù)清洗 [黃源　劉智楊　孫大松]
10. 電路設(shè)計與PCB制作實操教程 [主編 周永宏]
11. 電路與電子技術(shù)Ⅰ—數(shù)字電子技術(shù) [主編 鄭玉珍 王淑琴]
12. Java編程基礎(chǔ)案例式教程 [主編 陳艷華 唐春蘭]
13. Python語言同步案例習(xí)題精解 [主編 肖朝暉]
14. Web用戶界面設(shè)計與制作 [主編 趙娟]
15. Unity應(yīng)用開發(fā)與實戰(zhàn)（微課版） [主 編 程永恒]
16. 文學(xué)基礎(chǔ)與影視欣賞 [楊華軻 朱偉利 畢雪燕 羅玲誼]
17. 大學(xué)計算機(jī)基礎(chǔ)與計算思維 [主編 閔笛 汪瑩]
18. 大學(xué)計算機(jī)信息素養(yǎng)（第二版） [主編 盧山]
19. 大學(xué)計算機(jī)基礎(chǔ)實驗指導(dǎo)及習(xí)題解析 [主編 閔笛 李明]
20. 大學(xué)計算機(jī)信息素養(yǎng)實驗指導(dǎo)（第二版） [主編 盧山]
21. 計算機(jī)應(yīng)用基礎(chǔ)教程（Windows 10+Office 2019） [主編 聶長浪 賀秋芳 李久仲]
22. 計算機(jī)應(yīng)用基礎(chǔ)（Windows 7+Office 2016） [主編 王洪平 楊華]
23. 計算機(jī)信息素養(yǎng)基礎(chǔ) [主編 陳艷 秦凱 黃海玉]
24. 計算機(jī)基礎(chǔ)與應(yīng)用 [主編 秦凱 梁寧玉 王毅]
25. 大學(xué)計算機(jī)基礎(chǔ)上機(jī)實踐教程（第六版） [主編 何振林 羅奕]
26. C語言程序設(shè)計（微課版） [主編　夏啟壽]
27. 大學(xué)計算機(jī)基礎(chǔ)教程實驗指導(dǎo)與測試題集 [主編 饒拱維 吳華光 巫滿秀]
28. 計算機(jī)組成原理 [主編 史士英 唐為方]
29. 大學(xué)計算機(jī)基礎(chǔ)教程（Windows 10+Office 2016） [主編 饒拱維 郭其標(biāo) 房宜汕]
30. 新編高等學(xué)校英語應(yīng)用能力考試（A級）教程（第二版） [主編 洪金梅 邵毅 向雙豐]