依照2018年1月頒發(fā)的《普通高等學(xué)校本科專業(yè)類教學(xué)質(zhì)量國家標準》,在近20年的離散數(shù)學(xué)講義基礎(chǔ)上,精心整理,編撰成本書。在編寫過程中,充分考慮了重點高校和普通省屬院校等各類學(xué)校的學(xué)生基礎(chǔ)、教學(xué)特點和教材改革經(jīng)驗,以增強本書的適用性。
本書分為數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論4篇,內(nèi)容包括命題邏輯、謂詞邏輯、集合、二元關(guān)系、函數(shù)、代數(shù)系統(tǒng)基礎(chǔ)、群/環(huán)和域、格與布爾代數(shù)、圖論基礎(chǔ)、特殊圖與應(yīng)用共10章。各章的每節(jié)都配有習(xí)題,重要術(shù)語均有相應(yīng)的英文表述。
本書可以作為計算機科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息安全、物聯(lián)網(wǎng)工程等相關(guān)專業(yè)的本科生教材,也可以作為從事計算機軟件、硬件開發(fā)和應(yīng)用的工程技術(shù)人員的參考書,還可供教師參考或自學(xué)者使用。
重要概念和術(shù)語的英語表述,為讀者進一步閱讀英文文獻提供便利,以滿足我國高等教育與國際接軌的需要。
2.在編寫過程中,從理論論述到例題講解,均借鑒經(jīng)典教材的優(yōu)點,精心組織內(nèi)容,以增加本書的知識性和趣味性。
3.本書對重要定理和推論詳細論述,同時也為讀者預(yù)留部分練習(xí),使其在可望可及的訓(xùn)練中逐步培養(yǎng)邏輯思維能力。
4.本書注重從代數(shù)的角度來整合有關(guān)內(nèi)容,使讀者可以宏觀地體會各章節(jié)間的相互關(guān)聯(lián),從而加深對有關(guān)知識的理解。離散數(shù)學(xué)課程的內(nèi)容較多,為了突出概念和定理等內(nèi)容,對本書中的所有定義、定理和推論等均加陰影,便于讀者查找有關(guān)知識。
離散數(shù)學(xué)是計算機科學(xué)中基礎(chǔ)理論的核心課程之一,為計算機學(xué)科的研究和應(yīng)用提供了有力的數(shù)學(xué)工具。隨著計算機科學(xué)的發(fā)展,離散數(shù)學(xué)將扮演越來越重要的角色。離散數(shù)學(xué)提供了計算機學(xué)科專業(yè)必要的基本概念、基本理論和基本方法,這些概念、理論及方法大量地應(yīng)用在數(shù)字電路、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫系統(tǒng)、算法分析與設(shè)計、人工智能、計算機網(wǎng)絡(luò)等專業(yè)課程中,它可以為后續(xù)課程的學(xué)習(xí)奠定良好的理論基礎(chǔ)。作為現(xiàn)代數(shù)學(xué)的一個分支,離散數(shù)學(xué)以研究離散變量的結(jié)構(gòu)和相互關(guān)系為主要目標,除給計算機科學(xué)提供必要的知識支撐外,它也是培養(yǎng)學(xué)生縝密思維和綜合分析能力、提高素質(zhì)的核心課程之一。
2018年1月,發(fā)布《普通高等學(xué)校本科專業(yè)類教學(xué)質(zhì)量國家標準》(下稱《國標》),這是我國首個高等教育教學(xué)質(zhì)量的國家標準。依照《國標》關(guān)于計算機類專業(yè)知識體系和核心課程體系的建議,本書在編寫過程中注意吸納《國標》中對離散數(shù)學(xué)相關(guān)知識的有關(guān)要求,內(nèi)容上涵蓋數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論4篇,共10章。
本書的特色有以下幾個。
(1) 考慮到我國高等教育與國際接軌的需要,本書給出了重要概念和術(shù)語的英文表述,為讀者進一步閱讀英文文獻提供便利。
(2) 在編寫過程中,注意吸收國內(nèi)外經(jīng)典教材的優(yōu)點,從理論論述到例題講解,精心選擇,以增加內(nèi)容的知識性和趣味性。
(3) 本書中的重要定理和結(jié)論均有詳細論述,同時也為讀者預(yù)留部分練習(xí),使其在可望可及的訓(xùn)練中逐步培養(yǎng)邏輯思維能力。
(4) 本書注重通過代數(shù)的角度來整合有關(guān)內(nèi)容,使讀者可以宏觀地體會各章節(jié)間的相互關(guān)聯(lián),從而加深有關(guān)知識的理解。
(5) 離散數(shù)學(xué)內(nèi)容較多,為了突出概念和定理等內(nèi)容,書中將所有定義、定理和推論等均加陰影,便于讀者查找有關(guān)知識。
本書是在大連海事大學(xué)離散數(shù)學(xué)講義的基礎(chǔ)上整理而成,本書之所以能夠得以與讀者見面,離不開大連海事大學(xué)眾多教師的辛勞,特別是趙廣利副教授、薛大伸教授、趙煥忠工程師,在此向他們表示誠摯的感謝和崇高的敬意!在本書的編寫過程中參考了大量的相關(guān)文獻,也從中汲取了不少經(jīng)驗,在此向這些文獻的作者、譯者表示感謝。同時,本書得到了清華大學(xué)出版社的大力支持及幫助,對此深表感謝。此外本書的出版也得到
遼寧省教育廳2023年高;究蒲许椖浚↗YTMS20230556)和遼寧省教育廳科學(xué)研究一般項目
(2019JYT06)等的資助。
在使用本書時,教師可以根據(jù)不同教學(xué)要求進行適當(dāng)選擇,建議用64~72學(xué)時完成全書的教學(xué)計劃。
盡管作者長期從事離散數(shù)學(xué)的教學(xué)工作,在編寫過程中也力求完美,但由于水平有限,書中難免有不足之處,懇請廣大讀者批評指正。
作者2024年1月
第1篇數(shù) 理 邏 輯
第1章命題邏輯
1.1命題與邏輯聯(lián)結(jié)詞
1.1.1命題邏輯的基本概念
1.1.2邏輯聯(lián)結(jié)詞
習(xí)題1.1
1.2命題公式與真值表
習(xí)題1.2
1.3永真式與永假式
習(xí)題1.3
1.4代入規(guī)則與替換規(guī)則
習(xí)題1.4
1.5等價與蘊涵
習(xí)題1.5
1.6對偶原理
習(xí)題1.6
1.7其他聯(lián)結(jié)詞
習(xí)題1.7
1.8范式與范式判定問題
習(xí)題1.8
1.9命題演算的推理理論
1.9.1真值表法
1.9.2直接證明法
1.9.3反證法
習(xí)題1.9
第2章謂詞邏輯
2.1謂詞與個體
習(xí)題2.1
2.2量詞與全總個體域
習(xí)題2.2
2.3謂詞公式
習(xí)題2.3
2.4自由變元與約束變元
習(xí)題2.4
2.5謂詞公式的等價式與蘊涵式
習(xí)題2.5
2.6謂詞邏輯的推理理論
習(xí)題2.6
第2篇集合論
第3章集合
3.1集合的基本概念
習(xí)題3.1
3.2集合的運算
習(xí)題3.2
3.3包含排斥原理
習(xí)題3.3
3.4自然數(shù)與數(shù)學(xué)歸納法
習(xí)題3.4
3.5笛卡兒乘積
習(xí)題3.5
第4章二元關(guān)系
4.1關(guān)系及其性質(zhì)
習(xí)題4.1
4.2關(guān)系圖與關(guān)系矩陣
習(xí)題4.2
4.3關(guān)系的運算
4.3.1關(guān)系的合成運算
4.3.2關(guān)系的求逆運算
4.3.3關(guān)系的閉包運算
習(xí)題4.3
4.4等價關(guān)系與劃分
習(xí)題4.4
4.5相容關(guān)系與覆蓋
習(xí)題4.5
4.6次序關(guān)系
4.6.1偏序關(guān)系與哈斯圖
4.6.2全序和詞典序
4.6.3擬序與良序
習(xí)題4.6
第5章函數(shù)
5.1函數(shù)的基本概念
習(xí)題5.1
5.2復(fù)合函數(shù)與逆函數(shù)
習(xí)題5.2
5.3特征函數(shù)與模糊子集
習(xí)題5.3
5.4集合的基數(shù)
習(xí)題5.4
第3篇代 數(shù) 系 統(tǒng)
第6章代數(shù)系統(tǒng)基礎(chǔ)
6.1代數(shù)運算
習(xí)題6.1
6.2代數(shù)系統(tǒng)的概念
習(xí)題6.2
6.3同態(tài)與同構(gòu)
習(xí)題6.3
6.4同余關(guān)系
習(xí)題6.4
6.5商代數(shù)與積代數(shù)
6.5.1商代數(shù)
6.5.2積代數(shù)
習(xí)題6.5
第7章群、環(huán)和域
7.1半群與含幺半群
習(xí)題7.1
7.2群的定義及基本性質(zhì)
習(xí)題7.2
7.3循環(huán)群與變換群
7.3.1循環(huán)群
7.3.2變換群
習(xí)題7.3
7.4子群
7.4.1子群
7.4.2子群的陪集
習(xí)題7.4
7.5環(huán)和域
7.5.1環(huán)
7.5.2域
習(xí)題7.5
第8章格與布爾代數(shù)
8.1格的基本概念
習(xí)題8.1
8.2格的性質(zhì)和格同態(tài)
習(xí)題8.2
8.3幾種特殊格
習(xí)題8.3
8.4布爾代數(shù)
習(xí)題8.4
第4篇圖論
第9章圖論基礎(chǔ)
9.1圖的基本概念
習(xí)題9.1
9.2子圖與圖的運算
習(xí)題9.2
9.3路徑、回路和連通性
習(xí)題9.3
9.4可分圖與不可分圖
習(xí)題9.4
9.5圖的矩陣表示法
9.5.1鄰接矩陣
9.5.2可達矩陣
9.5.3關(guān)聯(lián)矩陣
習(xí)題9.5
第10章特殊圖與應(yīng)用
10.1歐拉圖與哈密頓圖
習(xí)題10.1
10.2平面圖與歐拉公式
習(xí)題10.2
10.3二部圖與匹配
習(xí)題10.3
10.4對偶圖與著色
習(xí)題10.4
10.5樹
習(xí)題10.5
10.6根樹及其應(yīng)用
習(xí)題10.6
10.7運輸網(wǎng)絡(luò)
10.7.1網(wǎng)絡(luò)的流
10.7.2割及割量
10.7.3確定最大流的標記法
習(xí)題10.7
參考文獻