本書分為四部分，共9章。第一部分為數(shù)理邏輯，主要包括命題邏輯、一階邏輯及數(shù)理邏輯中的推理證明等內(nèi)容。第二部分為集合論，主要包括集合、矩陣、關系和函數(shù)等內(nèi)容。第三部分為圖論，主要包括圖的基本概念和矩陣表示、特殊的圖和樹等內(nèi)容。第四部分為代數(shù)系統(tǒng)，主要包括代數(shù)系統(tǒng)基礎、格與布爾代數(shù)等內(nèi)容。
本書內(nèi)容豐富，層次分明，重點突出，并注重離散數(shù)學的實用性，可以為計算機專業(yè)學生提供重要的數(shù)學基礎。本書可作為計算機專業(yè)本科生、大專生等的理論教學教材。
為配合教學，本書配有電子課件、教學大綱、習題答案等教學資源，有需要的教師可登錄機械工業(yè)出版社教育服務網(wǎng)（www.cmpedu.com）免費注冊,審核通過后下載，或聯(lián)系編輯索�。ㄎ⑿牛�18515977506，電話：010-88379739）。本書還配有教學視頻，讀者可在正文中掃描二維碼觀看。
適讀人群 ：計算機專業(yè)本、�？粕�
本書是一本通俗易懂的離散數(shù)學課程教材。由淺入深地介紹了數(shù)理邏輯、集合論、圖論和代數(shù)系統(tǒng)四個部分，每一部分均配有大量難易程度不同的例題，且重、難點知識點均配有視頻講解。
本書內(nèi)容翔實，深入淺出，是一本適宜學生預習和復習，且可讀性強的教材。
本書注重先進性和實用性，同時概念清楚，系統(tǒng)性強，力求保持離散數(shù)學知識的完整性，有利于不同層次的讀者從不同起點逐步理解和掌握離散數(shù)學知識。
課時安排：本書數(shù)理邏輯部分適宜12～16個課時，集合論部分適宜16～22個課時，圖論部分適宜10～12個課時，代數(shù)系統(tǒng)部分適宜6～8個課時。
前 言
離散數(shù)學是計算機科學的基礎核心學科,也是計算機專業(yè)的核心基礎課程，主要研究離散結構和相互關系。離散數(shù)學是數(shù)據(jù)結構、編譯原理、數(shù)據(jù)庫原理、計算機組成原理和計算機操作系統(tǒng)等計算機專業(yè)課程的數(shù)學基礎�；A研究是科學之本和創(chuàng)新之源。黨的二十大報告中指出：“加強基礎學科、新興學科、交叉學科建設，加快建設中國特色、世界一流的大學和優(yōu)勢學科。”可見，基礎研究是國家核心競爭力的重要組成部分，是提升原始創(chuàng)新能力的根本途徑。學習離散數(shù)學不僅能幫助學生學會應用數(shù)學知識，更重要的是可以提高學生的數(shù)學邏輯思維能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎。
編寫本書的宗旨是在幫助學生全面掌握離散數(shù)學理論知識的基礎上，注重理論和實踐的結合，培養(yǎng)學生運用基礎知識分析和解決問題的能力。編者經(jīng)過對目前主流離散數(shù)學教材的分析研究并結合計算機專業(yè)的后續(xù)學習需求，由淺入深地介紹了數(shù)理邏輯、集合論、圖論和代數(shù)系統(tǒng)四個部分，每一部分均配有大量難易程度不同的例題，且重、難點知識點均配有視頻講解。本書內(nèi)容翔實，深入淺出，是一本適宜學生預習和復習，且可讀性強的教材。
本書注重先進性和實用性，同時概念清楚，系統(tǒng)性強，力求保持離散數(shù)學知識的完整性，有利于不同層次的讀者從不同起點逐步理解和掌握離散數(shù)學知識。本書數(shù)理邏輯部分適宜12～16個課時，集合論部分適宜16～22個課時，圖論部分適宜10～12個課時，代數(shù)系統(tǒng)部分適宜6～8個課時。
本書第1、2、3、4章由田秋紅執(zhí)筆，第5、6、7章由王成群執(zhí)筆，第8、9章由梁道雷執(zhí)筆，田秋紅負責確定全書的組織架構，金耀負責全書的統(tǒng)稿。本書的出版得到了“十四五”省級教改項目“研究導向的‘計算機科學的教學基礎’課程改革研究”（11120032412306）、“浙江理工大學521人才項目”、“浙江理工大學博士科研啟動項目（11122932611817）”
和校級教改項目“基于實踐課程的學生創(chuàng)新能力培養(yǎng)方法研究（xxjg202103）”的經(jīng)費資助。
本書的編寫和出版得到了機械工業(yè)出版社的大力支持，以及許多教師及業(yè)界同人的幫助，他們?yōu)楸緯捻樌霭嫣峁┝肆己玫臈l件，編者表示衷心感謝。
由于時間和編者水平有限，錯漏之處在所難免，歡迎廣大讀者批評指正。
編 者
田秋紅，女，博士，浙江理工大學計算機科學與技術學院（人工智能學院）教授，碩士生導師，計算機科學與技術系副主任，計算機系黨支部書記，曾獲計算機科學與技術學院與信息學院第一屆“我心目中的好老師”稱號。主持或參與國家自然科學基金和浙江省自然科學基金項目10余項；主持橫向與參與課題10余項；授權國家發(fā)明專利20余項，其中國家發(fā)明專利轉(zhuǎn)化5項、先后發(fā)表論文30余篇，其中SCI、EI收錄10余篇、編寫教材2部。指導的本科生以第一作者發(fā)表論文6篇，其中SCI文章一篇。指導本科生參加大學生挑戰(zhàn)杯與互聯(lián)網(wǎng)+競賽，并于2021年獲互聯(lián)網(wǎng)+競賽浙江省銅獎，大學生挑戰(zhàn)杯浙江省三等獎，2022年獲大學生挑戰(zhàn)杯浙江省金獎。指導本科生立項國家級大學生創(chuàng)新創(chuàng)業(yè)項目3項、浙江省新苗項目10項；指導本科生授權國家發(fā)明專利2項、受理國家發(fā)明專利10余項、授權軟件著作權20余項、實用新型專利1項。
第一部分 數(shù)理邏輯
第1章 命題邏輯2
1.1 命題及符號化2
1.1.1 命題2
1.1.2 聯(lián)結詞3
1.1.3 真值表5
1.1.4 復合命題符號化6
1.1.5 命題公式分類7
1.2 命題等值演算9
1.2.1 等值式9
1.2.2 等值演算9
1.3 范式12
1.3.1 析取范式和合取范式12
1.3.2 主析取范式和主合取范式14
1.4 邏輯電路20
1.5 習題22
第2章 一階邏輯26
2.1 一階邏輯基本概念26
2.1.1 個體詞、謂詞26
2.1.2 量詞27
2.1.3 嵌套量詞29
2.2 一階邏輯公式分類及解釋30
2.2.1 謂詞公式解釋30
2.2.2 謂詞公式分類32
2.3 一階邏輯等值式和前束范式33
2.3.1 一階邏輯等值式33
2.3.2 前束范式35
2.4 邏輯推理36
2.4.1 命題邏輯推理37
2.4.2 一階邏輯推理41
2.5 習題44
第二部分 集合論
第3章 集合和矩陣50
3.1 集合50
3.1.1 集合概念50
3.1.2 集合間關系51
3.1.3 集合運算53
3.1.4 集合證明55
3.1.5 集合的計算機表示方法58
3.2 矩陣59
3.2.1 矩陣概念59
3.2.2 矩陣基本運算60
3.2.3 布爾矩陣運算62
3.3 習題63
第4章 關系和函數(shù)66
4.1 關系66
4.1.1 關系概念66
4.1.2 關系表示方法70
4.1.3 關系運算72
4.1.4 關系性質(zhì)77
4.1.5 關系閉包82
4.1.6 等價關系84
4.1.7 偏序關系88
4.2 函數(shù)92
4.2.1 函數(shù)定義92
4.2.2 函數(shù)性質(zhì)94
4.2.3 函數(shù)運算95
4.3 習題97
第三部分 圖論
第5章 圖的基本概念和矩陣表示102
5.1 圖的基本概念102
5.2 頂點的度數(shù)與度序列104
5.3 握手定理105
5.4 完全圖106
5.5 圖的同構與子圖107
5.6 圖的操作109
5.7 通路回路111
5.8 連通性112
5.8.1 無向圖的連通性112
5.8.2 有向圖的連通性114
5.9 矩陣表示115
5.9.1 鄰接矩陣115
5.9.2 可達矩陣118
5.9.3 關聯(lián)矩陣119
5.9.4 連通性與矩陣關系120
5.10 路徑120
5.10.1 最短路徑120
5.10.2 Dijkstra算法121
5.10.3 Bellman-Ford算法123
5.10.4 SPFA算法125
5.10.5 Floyd算法127
5.10.6 拓撲排序和關鍵路徑130
5.11 習題134
第6章 特殊的圖136
6.1 歐拉圖136
6.1.1 基本概念136
6.1.2 判定137
6.2 哈密頓圖138
6.3 二部圖142
6.4 平面圖146
6.4.1 基本概念146
6.4.2 歐拉公式147
6.4.3 平面圖判定148
6.5 圖的著色問題151
6.5.1 對偶圖151
6.5.2 地圖著色與四色猜想152
6.5.3 平面圖著色與五色定理153
6.5.4 平面圖點著色154
6.6 習題156
第7章 樹159
7.1 概念介紹159
7.2 生成樹與最小生成樹160
7.2.1 Kruskal算法162
7.2.2 管梅谷算法163
7.2.3 逐步短接法164
7.3 根樹165
7.3.1 根樹概念165
7.3.2 二叉樹遍歷167
7.3.3 最優(yōu)二叉樹和哈夫曼編碼169
7.3.4 一般樹遍歷170
7.4 習題172
第四部分 代數(shù)系統(tǒng)
第8章 代數(shù)系統(tǒng)基礎174
8.1 代數(shù)系統(tǒng)概念174
8.2 半群與獨異點182
8.3 群的基本定義與性質(zhì)184
8.4 子群與陪集189
8.5 循環(huán)群和置換群195
8.6 環(huán)和域200
8.7 習題203
第9章 格與布爾代數(shù)206
9.1 格206
9.2 布爾代數(shù)213
9.3 習題215
參考文獻217
書單推薦
