本書是國(guó)家精品課程——解放軍理工大學(xué)王元元老師主持的“離散數(shù)學(xué)”配套的主講教材,也是教育部高等理工教育教學(xué)改革與實(shí)踐項(xiàng)目——“高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)核心課程教學(xué)實(shí)施方案研究”成果之一。本書內(nèi)容按照教育部高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會(huì)發(fā)布的《高等學(xué)校計(jì)算機(jī)專業(yè)核心課程教學(xué)實(shí)施方案》并參考IEEE&ACM的CC 2008教程編寫而成,主要內(nèi)容包括離散數(shù)學(xué)四大分支的基礎(chǔ)理論:數(shù)理邏輯、圖論、集合論、抽象代數(shù)學(xué)。它既注重離散數(shù)學(xué)內(nèi)容本身的系統(tǒng)完善,同時(shí)又注重與計(jì)算機(jī)科學(xué)的密切聯(lián)系,具有結(jié)構(gòu)合理、內(nèi)容系統(tǒng)、闡釋新穎的特點(diǎn)。本書取材詳略得當(dāng),敘述清楚流暢,論證科學(xué)嚴(yán)謹(jǐn),釋例、練習(xí)精選獨(dú)到,力求科學(xué)性、應(yīng)用性、工具性和可讀性的完美統(tǒng)一。本書可作為高等院校計(jì)算機(jī)專業(yè)及相關(guān)專業(yè)本科生的離散數(shù)學(xué)教材和教學(xué)參考書,也可作為計(jì)算機(jī)軟硬件研究開發(fā)者和應(yīng)用人員的學(xué)習(xí)用書,以及大學(xué)畢業(yè)生考研復(fù)習(xí)用書。
《離散數(shù)學(xué)教程(第2版)》針對(duì)綜合性大學(xué)和工程類院校計(jì)算機(jī)類專業(yè)本科生進(jìn)行選材與編撰,內(nèi)容覆蓋ACM計(jì)算機(jī)科學(xué)課程體系規(guī)范2013( Computer Science Cur-ricula 2013)中離散結(jié)構(gòu)知識(shí)領(lǐng)域下除離散概率之外的全部知識(shí)點(diǎn)。
從離散結(jié)構(gòu)形式化表示理論到各類離散結(jié)構(gòu)及其數(shù)學(xué)模型的介紹,該書在內(nèi)容組織上力求做到突出知識(shí)內(nèi)在聯(lián)系與保持知識(shí)模塊完整性之間的平衡,從而使教材更具可讀性和系統(tǒng)性。該書章節(jié)內(nèi)容不僅覆蓋集合論、數(shù)理邏輯、組合論、圖論、可計(jì)算性、抽象代數(shù)等基礎(chǔ)理論部分,還給出了這些基本理論在粗糙集、模糊集、自動(dòng)推理、智能搜索、加密技術(shù)等領(lǐng)域的應(yīng)用,并涉及公理化集合論、數(shù)理邏輯形式系統(tǒng)、形式語(yǔ)言與自動(dòng)機(jī)等相關(guān)理論。該書以離散結(jié)構(gòu)為建模對(duì)象,緊密聯(lián)系計(jì)算機(jī)科學(xué)技術(shù),特別強(qiáng)調(diào)應(yīng)用能力、證明技術(shù)、計(jì)算思維的培養(yǎng)。
為便于學(xué)生及時(shí)復(fù)習(xí)并鞏固所學(xué)知識(shí),該書在每節(jié)后安排了大量習(xí)題;同時(shí),為便于學(xué)有余力的學(xué)生進(jìn)一步深造,每章后安排了一節(jié)閱讀材料,以此來(lái)對(duì)本章所介紹的理論進(jìn)行深入探討,或進(jìn)一步介紹技術(shù)的相關(guān)應(yīng)用。
該書不僅可用作高等學(xué)校計(jì)算機(jī)類專業(yè)本科生的離散數(shù)學(xué)課程教材,也可供相關(guān)工程技術(shù)人員閱讀參考。
《離散數(shù)學(xué)教程》第一版出版距今八年了。這八年來(lái),互聯(lián)網(wǎng)、人工智能等信息技術(shù)推動(dòng)下的教育革新可謂風(fēng)起潮涌、方興未艾。慕課、視頻公開課、資源共享課等在線數(shù)字資源極大提高了教育的受眾面,提升了學(xué)習(xí)者的個(gè)性化學(xué)習(xí)體驗(yàn)。受惠于這一波革新浪潮,傳統(tǒng)的紙質(zhì)教材也可一改以往刻板單調(diào)的形象,結(jié)合形式各異的在線資源向讀者呈現(xiàn)一個(gè)豐富、生動(dòng)、易得、滿足個(gè)性化需求的“新形態(tài)”。教程第2版正是在這一背景下應(yīng)運(yùn)而生。
如上所述,相對(duì)教程第1版,本版的最大特色是融合了在線教學(xué)資源。這些資源共分為四類:授課幻燈片,重難點(diǎn)講解,典型習(xí)題解答與常見錯(cuò)誤分析,以及知識(shí)點(diǎn)講解視頻。這些資源來(lái)自筆者多年的教學(xué)積累與心得,感謝高教出版社“新形態(tài)”教材計(jì)劃,使其有機(jī)會(huì)被整理出來(lái),與課堂之外的廣大讀者見面。目前上線的資源只是一部分,后期還會(huì)有一些陸續(xù)整理完成后上線。
相對(duì)前一版次,本版教程在內(nèi)容上也稍作了一些調(diào)整。本版在內(nèi)容編排上沿襲了前一版中先介紹離散結(jié)構(gòu)形式化表示理論(邏輯代數(shù)和集合代數(shù)),再依次介紹各類離散結(jié)構(gòu)及其數(shù)學(xué)模型的思路,但刪除了原“準(zhǔn)備知識(shí)”一章,將原在這一章集中介紹的集合、命題、謂詞、運(yùn)算等基本概念分類并入后續(xù)相關(guān)章節(jié)。作此改動(dòng),目的主要是希望在突出知識(shí)內(nèi)在聯(lián)系的同時(shí)更好地保持各個(gè)知識(shí)模塊的完整性,在兩者之間取得某種平衡,使教材更具可讀性。
此外,本教程還對(duì)關(guān)系和圖論兩個(gè)知識(shí)模塊作了擴(kuò)充,增加了相容關(guān)系、圖搜索、最短路徑、有向無(wú)環(huán)圖等內(nèi)容的介紹,如此更加突出了教程所強(qiáng)調(diào)的在應(yīng)用能力、證明技術(shù)和計(jì)算思維培養(yǎng)方面的特色。同時(shí),為控制篇幅本版去掉了原“數(shù)論”一章,還請(qǐng)老讀者見諒。
我們希望本版能夠?yàn)樽x者帶來(lái)更好的閱讀體驗(yàn),為教師和學(xué)生運(yùn)用本教材教授和學(xué)習(xí)離散數(shù)學(xué)課程提供更多更好的幫助。但限于編者專業(yè)水平,錯(cuò)誤和疏漏之處在所難免,還請(qǐng)讀者不吝指正。
王元元,原中國(guó)人民解放軍理工大學(xué)教授、博士研究生指導(dǎo)教師,長(zhǎng)期從事計(jì)算機(jī)基礎(chǔ)理論的研究和教學(xué)工作。先后被評(píng)為總參優(yōu)秀教員,全軍優(yōu)秀教員;榮獲國(guó)家教學(xué)名師獎(jiǎng)、國(guó)家教學(xué)成果二等獎(jiǎng);榮立二等功一次、三等功三次。其任教的主要課程有離散數(shù)學(xué)、組合數(shù)學(xué)以及數(shù)理邏輯等,其中離散數(shù)學(xué)課程被推薦為軍隊(duì)級(jí)優(yōu)質(zhì)課程和國(guó)家精品課程。所主編的教材《計(jì)算機(jī)科學(xué)中的邏輯學(xué)》《離散數(shù)學(xué)》曾分別獲得***優(yōu)秀教材獎(jiǎng)和電子工業(yè)部?jī)?yōu)秀教材獎(jiǎng)。
宋麗華,中國(guó)人民解放軍陸軍工程大學(xué)教授、碩士研究生指導(dǎo)教師,多年從事計(jì)算機(jī)基礎(chǔ)理論的研究和教學(xué)工作。曾獲軍隊(duì)教學(xué)成果一等獎(jiǎng)一項(xiàng),軍隊(duì)科技進(jìn)步二等獎(jiǎng)兩項(xiàng);榮立三等功一次。其任教的主要課程有離散數(shù)學(xué)、數(shù)理邏輯、計(jì)算科學(xué)基礎(chǔ)理論、函數(shù)式語(yǔ)言與編譯方法等。
第1章 邏輯代數(shù)(上):命題演算
1.1 邏輯聯(lián)結(jié)詞與命題公式
1.1.1 命題
1.1.2 邏輯聯(lián)結(jié)詞
1.1.3 命題公式
1.1.4 語(yǔ)句形式化
練習(xí)1.1
1.2 命題演算永真式
1.2.1 重言式
1.2.2 邏輯等價(jià)式與邏輯蘊(yùn)
涵式
1.2.3 對(duì)偶原理
1.2.4 邏輯應(yīng)用
練習(xí)1.2
1.3 范式
1.3.1 析取范式與合取范式
1.3.2 主析取范式與主合取
范式
1.3.3 聯(lián)結(jié)詞的擴(kuò)充與歸約
練習(xí)1.3
1.4 命題演算消解原理
練習(xí)1.4
1.5 閱讀材料:布爾代數(shù)
第2章 邏輯代數(shù)(下):謂詞演算
2.1 謂詞演算基本概念
2.1.1 個(gè)體
2.1.2 謂詞
2.1.3 量詞
2.1.4 謂詞公式及語(yǔ)句形式化
練習(xí)2.1
2.2 謂詞演算永真式
2.2.1 謂詞公式的語(yǔ)義
2.2.2 幾組謂詞演算永真式
2.2.3 謂詞公式等價(jià)變換的幾個(gè)
基本原理
練習(xí)2.2
*2.3 謂詞演算消解原理
2.3.1 前束化與消去量詞
2.3.2 謂詞演算消解原理簡(jiǎn)介
練習(xí)2.3
2.4 閱讀材料:形式推理與形式
系統(tǒng)
2.4.1 一個(gè)形式系統(tǒng)的例子
2.4.2 自然推理形式系統(tǒng)ND
第3章 集合代數(shù)
3.1 集合的概念與表示
3.1.1 集合基本概念
3.1.2 集合的表示
3.1.3 外延性原理與子集合
練習(xí)3.1
3.2 集合運(yùn)算
3.2.1 并、交、差、補(bǔ)運(yùn)算
3.2.2 環(huán)和與環(huán)積運(yùn)算
3.2.3 冪集與廣義并、交運(yùn)算
練習(xí)3.2
3.3 集合的笛卡兒積
練習(xí)3.3
3.4 集合的歸納定義
3.4.1 集合的歸納定義方法
3.4.2 集合定義的自然數(shù)
練習(xí)3.4
3.5 歸納法證明
3.5.1 結(jié)構(gòu)歸納法
3.5.2 數(shù)學(xué)歸納法
練習(xí)3.5
3.6 閱讀材料:公理化集合論
簡(jiǎn)介
第4章 計(jì)數(shù)
4.1 計(jì)數(shù)基本原理
4.1.1 加法原理與乘法原理
4.1.2 包含排斥原理
練習(xí)4.1
4.2 鴿籠原理
4.2.1 鴿籠原理基本形式
4.2.2 鴿籠原理加強(qiáng)形式
練習(xí)4.2
4.3 排列與組合
4.3.1 排列的計(jì)數(shù)
4.3.2 組合的計(jì)數(shù)
練習(xí)4.3
4.4 重集的排列與組合
4.4.1 重集的排列
4.4.2 重集的組合
4.4.3 錯(cuò)置的計(jì)數(shù)
練習(xí)4.4
4.5 遞歸式及其應(yīng)用
4.5.1 遞歸式建模
4.5.2 遞歸式求解
練習(xí)4.5
4.6 閱讀材料:母函數(shù)
……
第5章 關(guān)系
第6章 函數(shù)
第7章 可計(jì)算函數(shù)
第8章 圖與樹
第9章 特殊圖
第10章 代數(shù)結(jié)構(gòu)通論
第11章 群、環(huán)、域
參考文獻(xiàn)