本書分為四部分，共9章。第一部分為數(shù)理邏輯，主要包括命題邏輯、一階邏輯及數(shù)理邏輯中的推理證明等內(nèi)容。第二部分為集合論，主要包括集合、矩陣、關(guān)系和函數(shù)等內(nèi)容。第三部分為圖論，主要包括圖的基本概念和矩陣表示、特殊的圖和樹等內(nèi)容。第四部分為代數(shù)系統(tǒng)，主要包括代數(shù)系統(tǒng)基礎(chǔ)、格與布爾代數(shù)等內(nèi)容。
本書內(nèi)容豐富，層次分明，重點(diǎn)突出，并注重離散數(shù)學(xué)的實(shí)用性，可以為計(jì)算機(jī)專業(yè)學(xué)生提供重要的數(shù)學(xué)基礎(chǔ)。本書可作為計(jì)算機(jī)專業(yè)本科生、大專生等的理論教學(xué)教材。
為配合教學(xué)，本書配有電子課件、教學(xué)大綱、習(xí)題答案等教學(xué)資源，有需要的教師可登錄機(jī)械工業(yè)出版社教育服務(wù)網(wǎng)（www.cmpedu.com）免費(fèi)注冊(cè),審核通過后下載，或聯(lián)系編輯索�。ㄎ⑿牛�18515977506，電話：010-88379739）。本書還配有教學(xué)視頻，讀者可在正文中掃描二維碼觀看。

適讀人群 ：計(jì)算機(jī)專業(yè)本、�？粕�

本書是一本通俗易懂的離散數(shù)學(xué)課程教材。由淺入深地介紹了數(shù)理邏輯、集合論、圖論和代數(shù)系統(tǒng)四個(gè)部分，每一部分均配有大量難易程度不同的例題，且重、難點(diǎn)知識(shí)點(diǎn)均配有視頻講解。

本書內(nèi)容翔實(shí)，深入淺出，是一本適宜學(xué)生預(yù)習(xí)和復(fù)習(xí)，且可讀性強(qiáng)的教材。

本書注重先進(jìn)性和實(shí)用性，同時(shí)概念清楚，系統(tǒng)性強(qiáng)，力求保持離散數(shù)學(xué)知識(shí)的完整性，有利于不同層次的讀者從不同起點(diǎn)逐步理解和掌握離散數(shù)學(xué)知識(shí)。

課時(shí)安排：本書數(shù)理邏輯部分適宜12～16個(gè)課時(shí)，集合論部分適宜16～22個(gè)課時(shí)，圖論部分適宜10～12個(gè)課時(shí)，代數(shù)系統(tǒng)部分適宜6～8個(gè)課時(shí)。

前　言

離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)的基礎(chǔ)核心學(xué)科,也是計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程，主要研究離散結(jié)構(gòu)和相互關(guān)系。離散數(shù)學(xué)是數(shù)據(jù)結(jié)構(gòu)、編譯原理、數(shù)據(jù)庫(kù)原理、計(jì)算機(jī)組成原理和計(jì)算機(jī)操作系統(tǒng)等計(jì)算機(jī)專業(yè)課程的數(shù)學(xué)基礎(chǔ)�；�礎(chǔ)研究是科學(xué)之本和創(chuàng)新之源。黨的二十大報(bào)告中指出：“加強(qiáng)基礎(chǔ)學(xué)科、新興學(xué)科、交叉學(xué)科建設(shè)，加快建設(shè)中國(guó)特色、世界一流的大學(xué)和優(yōu)勢(shì)學(xué)科�！笨梢�，基礎(chǔ)研究是國(guó)家核心競(jìng)爭(zhēng)力的重要組成部分，是提升原始創(chuàng)新能力的根本途徑。學(xué)習(xí)離散數(shù)學(xué)不僅能幫助學(xué)生學(xué)會(huì)應(yīng)用數(shù)學(xué)知識(shí)，更重要的是可以提高學(xué)生的數(shù)學(xué)邏輯思維能力，為將來(lái)參與創(chuàng)新性的研究和開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ)。

編寫本書的宗旨是在幫助學(xué)生全面掌握離散數(shù)學(xué)理論知識(shí)的基礎(chǔ)上，注重理論和實(shí)踐的結(jié)合，培養(yǎng)學(xué)生運(yùn)用基礎(chǔ)知識(shí)分析和解決問題的能力。編者經(jīng)過對(duì)目前主流離散數(shù)學(xué)教材的分析研究并結(jié)合計(jì)算機(jī)專業(yè)的后續(xù)學(xué)習(xí)需求，由淺入深地介紹了數(shù)理邏輯、集合論、圖論和代數(shù)系統(tǒng)四個(gè)部分，每一部分均配有大量難易程度不同的例題，且重、難點(diǎn)知識(shí)點(diǎn)均配有視頻講解。本書內(nèi)容翔實(shí)，深入淺出，是一本適宜學(xué)生預(yù)習(xí)和復(fù)習(xí)，且可讀性強(qiáng)的教材。

本書注重先進(jìn)性和實(shí)用性，同時(shí)概念清楚，系統(tǒng)性強(qiáng)，力求保持離散數(shù)學(xué)知識(shí)的完整性，有利于不同層次的讀者從不同起點(diǎn)逐步理解和掌握離散數(shù)學(xué)知識(shí)。本書數(shù)理邏輯部分適宜12～16個(gè)課時(shí)，集合論部分適宜16～22個(gè)課時(shí)，圖論部分適宜10～12個(gè)課時(shí)，代數(shù)系統(tǒng)部分適宜6～8個(gè)課時(shí)。

本書第1、2、3、4章由田秋紅執(zhí)筆，第5、6、7章由王成群執(zhí)筆，第8、9章由梁道雷執(zhí)筆，田秋紅負(fù)責(zé)確定全書的組織架構(gòu)，金耀負(fù)責(zé)全書的統(tǒng)稿。本書的出版得到了“十四五”省級(jí)教改項(xiàng)目“研究導(dǎo)向的‘計(jì)算機(jī)科學(xué)的教學(xué)基礎(chǔ)’課程改革研究”（11120032412306）、“浙江理工大學(xué)521人才項(xiàng)目”、“浙江理工大學(xué)博士科研啟動(dòng)項(xiàng)目（11122932611817）”
和校級(jí)教改項(xiàng)目“基于實(shí)踐課程的學(xué)生創(chuàng)新能力培養(yǎng)方法研究（xxjg202103）”的經(jīng)費(fèi)資助。

本書的編寫和出版得到了機(jī)械工業(yè)出版社的大力支持，以及許多教師及業(yè)界同人的幫助，他們?yōu)楸緯�的順利出版提供了良好的條件，編者表示衷心感謝。

由于時(shí)間和編者水平有限，錯(cuò)漏之處在所難免，歡迎廣大讀者批評(píng)指正。



編　者

田秋紅，女，博士，浙江理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院（人工智能學(xué)院）教授，碩士生導(dǎo)師，計(jì)算機(jī)科學(xué)與技術(shù)系副主任，計(jì)算機(jī)系黨支部書記，曾獲計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院與信息學(xué)院第一屆“我心目中的好老師”稱號(hào)。主持或參與國(guó)家自然科學(xué)基金和浙江省自然科學(xué)基金項(xiàng)目10余項(xiàng)；主持橫向與參與課題10余項(xiàng)；授權(quán)國(guó)家發(fā)明專利20余項(xiàng)，其中國(guó)家發(fā)明專利轉(zhuǎn)化5項(xiàng)、先后發(fā)表論文30余篇，其中SCI、EI收錄10余篇、編寫教材2部。指導(dǎo)的本科生以第一作者發(fā)表論文6篇，其中SCI文章一篇。指導(dǎo)本科生參加大學(xué)生挑戰(zhàn)杯與互聯(lián)網(wǎng)+競(jìng)賽，并于2021年獲互聯(lián)網(wǎng)+競(jìng)賽浙江省銅獎(jiǎng)，大學(xué)生挑戰(zhàn)杯浙江省三等獎(jiǎng)，2022年獲大學(xué)生挑戰(zhàn)杯浙江省金獎(jiǎng)。指導(dǎo)本科生立項(xiàng)國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)項(xiàng)目3項(xiàng)、浙江省新苗項(xiàng)目10項(xiàng)；指導(dǎo)本科生授權(quán)國(guó)家發(fā)明專利2項(xiàng)、受理國(guó)家發(fā)明專利10余項(xiàng)、授權(quán)軟件著作權(quán)20余項(xiàng)、實(shí)用新型專利1項(xiàng)。

第一部分　數(shù)理邏輯
第1章　命題邏輯2
　1.1　命題及符號(hào)化2
　　1.1.1　命題2
　　1.1.2　聯(lián)結(jié)詞3
　　1.1.3　真值表5
　　1.1.4　復(fù)合命題符號(hào)化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　習(xí)題22
第2章　一階邏輯26
　2.1　一階邏輯基本概念26
　　2.1.1　個(gè)體詞、謂詞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　習(xí)題44
第二部分　集合論
第3章　集合和矩陣50
　3.1　集合50
　　3.1.1　集合概念50
　　3.1.2　集合間關(guān)系51
　　3.1.3　集合運(yùn)算53
　　3.1.4　集合證明55
　　3.1.5　集合的計(jì)算機(jī)表示方法58
　3.2　矩陣59
　　3.2.1　矩陣概念59
　　3.2.2　矩陣基本運(yùn)算60
　　3.2.3　布爾矩陣運(yùn)算62
　3.3　習(xí)題63
第4章　關(guān)系和函數(shù)66
　4.1　關(guān)系66
　　4.1.1　關(guān)系概念66
　　4.1.2　關(guān)系表示方法70
　　4.1.3　關(guān)系運(yùn)算72
　　4.1.4　關(guān)系性質(zhì)77
　　4.1.5　關(guān)系閉包82
　　4.1.6　等價(jià)關(guān)系84
　　4.1.7　偏序關(guān)系88
　4.2　函數(shù)92
　　4.2.1　函數(shù)定義92
　　4.2.2　函數(shù)性質(zhì)94
　　4.2.3　函數(shù)運(yùn)算95
　4.3　習(xí)題97
第三部分　圖論
第5章　圖的基本概念和矩陣表示102
　5.1　圖的基本概念102
　5.2　頂點(diǎn)的度數(shù)與度序列104
　5.3　握手定理105
　5.4　完全圖106
　5.5　圖的同構(gòu)與子圖107
　5.6　圖的操作109
　5.7　通路回路111
　5.8　連通性112
　　5.8.1　無(wú)向圖的連通性112
　　5.8.2　有向圖的連通性114
　5.9　矩陣表示115
　　5.9.1　鄰接矩陣115
　　5.9.2　可達(dá)矩陣118
　　5.9.3　關(guān)聯(lián)矩陣119
　　5.9.4　連通性與矩陣關(guān)系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　拓?fù)渑判蚝完P(guān)鍵路徑130
　5.11　習(xí)題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　對(duì)偶圖151
　　6.5.2　地圖著色與四色猜想152
　　6.5.3　平面圖著色與五色定理153
　　6.5.4　平面圖點(diǎn)著色154
　6.6　習(xí)題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　習(xí)題172
第四部分　代數(shù)系統(tǒng)
第8章　代數(shù)系統(tǒng)基礎(chǔ)174
　8.1　代數(shù)系統(tǒng)概念174
　8.2　半群與獨(dú)異點(diǎn)182
　8.3　群的基本定義與性質(zhì)184
　8.4　子群與陪集189
　8.5　循環(huán)群和置換群195
　8.6　環(huán)和域200
　8.7　習(xí)題203
第9章　格與布爾代數(shù)206
　9.1　格206
　9.2　布爾代數(shù)213
　9.3　習(xí)題215
參考文獻(xiàn)217