本書認(rèn)真分析、總結(jié)、吸收了部分高校離散數(shù)學(xué)課程教學(xué)改革經(jīng)驗(yàn)，以教育部高等教育教學(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í)點(diǎn)豐富，采用模塊化設(shè)計(jì)；為提高學(xué)生對離散數(shù)學(xué)源流的認(rèn)識(shí)，每章后附興趣閱讀；每章均給出了本章重點(diǎn)知識(shí)的小結(jié)，有利于學(xué)生進(jìn)行系統(tǒng)的復(fù)習(xí)。

前 言

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

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

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

1．科學(xué)性

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

2．先進(jìn)性

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

3．實(shí)用性

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

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

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

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

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

編 者

2012年3月

前言

第一章 矩陣代數(shù) 1
本章學(xué)習(xí)目標(biāo) 1
第一節(jié) 行列式 1
一、行列式的定義 2
二、行列式的性質(zhì) 3
三、行列式的計(jì)算 5
四、克拉默法則 8
習(xí)題 9
第二節(jié) 矩陣的概念及矩陣的運(yùn)算 11
一、矩陣的概念 11
二、矩陣的運(yùn)算 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é) 集合的基本概念與運(yùn)算 38
一、集合的表示 38
二、集合之間的關(guān)系 39
三、集合的基本運(yùn)算 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)系的運(yùn)算 53
一、基本概念 53
二、運(yùn)算的性質(zhì) 55
三、關(guān)系冪 55
四、冪運(yùn)算的性質(zhì) 57
習(xí)題 57
第七節(jié) 關(guān)系的性質(zhì) 58
一、關(guān)系的五種基本性質(zhì) 58
二、關(guān)系性質(zhì)的等價(jià) 59
習(xí)題 61
第八節(jié) 關(guān)系的閉包 61
一、基本概念 61
二、閉包的性質(zhì) 64
習(xí)題 64
第九節(jié) 等價(jià)關(guān)系與相容關(guān)系 65
一、集合的劃分和覆蓋 65
二、等價(jià)關(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é) 等價(jià)式與蘊(yùn)含式 94
一、等價(jià)式的概念 94
二、用真值表判斷公式的等價(jià) 94
三、等價(jià)演算 95
四、蘊(yùn)含式 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
一、個(gè)體詞 121
二、謂詞 121
三、量詞 122
四、謂詞邏輯命題符號(hào)化 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)的運(yùn)算及其性質(zhì) 152
一、運(yùn)算的性質(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é) 有界格與有補(bǔ)格 188
一、有界格 188
二、有補(bǔ)格 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
三、頂點(diǎn)的度數(shù)與握手定理 204
四、圖的同構(gòu)、完全圖與補(bǔ)圖 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ì)算機(jī) 246
參考文獻(xiàn) 247

1. Java Web項(xiàng)目化設(shè)計(jì)實(shí)踐教程 [邱云 曾陳萍]
2. Python數(shù)據(jù)分析 [主編　馮志輝　趙磊　李放]
3. 大學(xué)信息技術(shù) [曾翰穎 編著]
4. 多維視域下的高校籃球教學(xué)創(chuàng)新研究 [張利超 李寧 著]
5. 創(chuàng)新創(chuàng)業(yè)訓(xùn)練實(shí)踐教程 [主編 王日華 陳武 黃喆誠]
6. 實(shí)用運(yùn)籌學(xué) [主編　邢育紅　于晉臣]
7. 電子技術(shù)（第二版） [主編 覃愛娜 李飛]
8. 勞動(dòng)爭議處理實(shí)務(wù) [主編 王秀卿 羅靜]
9. 語音識(shí)別理論與實(shí)踐 [主編　莫宏偉]
10. 武術(shù)基礎(chǔ)教程 [主編 李代勇 謝志民]
11. 畫法幾何與機(jī)械制圖習(xí)題集（多學(xué)時(shí)） [主編 趙軍]
12. 機(jī)械設(shè)計(jì)基礎(chǔ)（第二版） [主編 田亞平 李愛姣]
13. 畫法幾何與機(jī)械制圖 [主編 趙軍]
14. C語言程序設(shè)計(jì)習(xí)題與實(shí)驗(yàn)指導(dǎo)（第二版） [主編 甄增榮 張賓]
15. C語言程序設(shè)計(jì)（第二版） [主編 甄增榮 田云霞]
16. Unity3D虛擬現(xiàn)實(shí)應(yīng)用開發(fā)實(shí)踐 [主 編 劉龍]
17. 面向?qū)ο蟪绦蛟O(shè)計(jì) [主編 張勇 張平華 趙小龍]
18. 網(wǎng)絡(luò)營銷 [主編 夏薇薇 劉婷 尚潔]
19. 數(shù)據(jù)庫技術(shù)與應(yīng)用實(shí)踐教程（SQL Server 2019） [主 編 嚴(yán)暉 周肆清]
20. 功能材料制備與表征實(shí)驗(yàn)指導(dǎo)書 [龔偉平 趙軍峰 梅海娟 等編著]
21. 信號(hào)與系統(tǒng)（第二版） [主編 張宇]
22. Python 語言程序設(shè)計(jì)實(shí)踐指導(dǎo) [主編　張雙獅]
23. 體育舞蹈教程 [主編 劉偉 陳志明 曾明]
24. 線性代數(shù)導(dǎo)學(xué)篇 [主編 史昱]
25. 信息技術(shù)基礎(chǔ)實(shí)訓(xùn)與習(xí)題指導(dǎo)（Windows7+Office2016） [主編 周金容 唐天國]
26. 高等數(shù)學(xué)導(dǎo)學(xué)篇（下冊） [主編 李文婧 胡雷 尹金生]
27. 高等數(shù)學(xué)導(dǎo)學(xué)篇（上冊） [主編 李文婧 胡雷 尹金生]
28. 高等數(shù)學(xué)（下冊） [主編 李愛芹 胡雷 尹金生]
29. 高等數(shù)學(xué)（上冊） [主編 李愛芹 胡雷 尹金生]
30. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]