本書認真分析、總結、吸收了部分高校離散數學課程教學改革經驗，以教育部高等教育教學課程的基本要求與課程改革精神及人才培養目標為依據，在取材上注重基礎完整，講述上力求深入淺出，從而達到既為學生專業功能服務，又加強基本思維素質訓練的目的。

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

前 言

隨著現代社會對人才的要求越來越高，對于學生來講，只具備專業知識已經不能適應社會的需求。還必須具備較強的適應能力、應變能力、學習能力、創新能力等才能在日趨激烈的競爭中立于不敗之地，才能為社會作出更大的貢獻。而這些能力的基礎不但要有豐富的專業知識基礎，還要有良好的思維品質。離散數學的學習，就最能體現這兩方面。

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

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

因此，本教材在具體編寫過程中，力求既介紹離散數學基礎知識的核心內容，簡明扼要、通俗易懂，又注重理論聯系實際，融入啟發式思維訓練，著重培養學生良好的思維品質，加強學生系統性、創新性、發散性、堅韌性的思維訓練。本教材在結合編者多年離散數學教學經驗的基礎上，根據計算機科學與技術專業學生的特點，參考了國內眾多教材的優勢并借鑒國外教材的特點編寫而成的。本書的主要特點如下：

1．科學性

教材的整個體系保持了離散數學具有代表性的核心內容，堅持少而精、釋義清楚、學以致用的原則，內容安排上由淺入深，符合認知規律，理論嚴謹、敘述明確簡練、邏輯性強，知識點脈絡清晰。

2．先進性

大部分例題都融入啟發式思維訓練，重點突出解題思路，注重培養學生的數學思維能力和分析、解決問題的能力。每一章都增加了應用和相關離散數學源流的介紹，不但有助于提高學生的學習興趣，而且將基礎理論與相關實際問題相結合，變抽象思維為形象思維，提高學生思考能力，培養學生系統性、創新性、發散性、堅韌性的思維品質。

3．實用性

每章都列出了學習目標和小結，并配以大量習題和思考題，以便學生及時掌握知識點和知識結構。

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

本書不僅可以作為普通高等院校計算機科學與技術、軟件工程等相關專業本科的離散數學教材，也可以作為考研、計算機相關開發人員的參考書。

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

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

編 者

2012年3月

前言

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

1. 實用運籌學 [主編　邢育紅　于晉臣]
2. 電子技術（第二版） [主編 覃愛娜 李飛]
3. 勞動爭議處理實務 [主編 王秀卿 羅靜]
4. 語音識別理論與實踐 [主編　莫宏偉]
5. 武術基礎教程 [主編 李代勇 謝志民]
6. 畫法幾何與機械制圖習題集（多學時） [主編 趙軍]
7. 機械設計基礎（第二版） [主編 田亞平 李愛姣]
8. 畫法幾何與機械制圖 [主編 趙軍]
9. C語言程序設計習題與實驗指導（第二版） [主編 甄增榮 張賓]
10. C語言程序設計（第二版） [主編 甄增榮 田云霞]
11. Unity3D虛擬現實應用開發實踐 [主 編 劉龍]
12. 面向對象程序設計 [主編 張勇 張平華 趙小龍]
13. 網絡營銷 [主編 夏薇薇 劉婷 尚潔]
14. 數據庫技術與應用實踐教程（SQL Server 2019） [主 編 嚴暉 周肆清]
15. 功能材料制備與表征實驗指導書 [龔偉平 趙軍峰 梅海娟 等編著]
16. 信號與系統（第二版） [主編 張宇]
17. Python 語言程序設計實踐指導 [主編　張雙獅]
18. 體育舞蹈教程 [主編 劉偉 陳志明 曾明]
19. 線性代數導學篇 [主編 史昱]
20. 信息技術基礎實訓與習題指導（Windows7+Office2016） [主編 周金容 唐天國]
21. 高等數學導學篇（下冊） [主編 李文婧 胡雷 尹金生]
22. 高等數學導學篇（上冊） [主編 李文婧 胡雷 尹金生]
23. 高等數學（下冊） [主編 李愛芹 胡雷 尹金生]
24. 高等數學（上冊） [主編 李愛芹 胡雷 尹金生]
25. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
26. 電路與電子技術Ⅱ——電路分析基礎 [主編 陳曉 金哲]
27. Spark大數據處理技術 [主編　劉仁山　周洪翠　莊新妍]
28. 人工智能算法與實踐 [主編　梁琨　張翼英]
29. 數據清洗 [黃源　劉智楊　孫大松]
30. 電路設計與PCB制作實操教程 [主編 周永宏]