本書分為數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)和圖論4個(gè)部分。全書內(nèi)容嚴(yán)謹(jǐn),條理清晰,對概念的闡述精確,對實(shí)例的使用合理,適合作為高等學(xué)校軟件工程專業(yè)和計(jì)算機(jī)專業(yè)離散數(shù)學(xué)課程的本科生教材,也可作為軟件工程與計(jì)算機(jī)等相關(guān)專業(yè)的自學(xué)參考書。
隨著國內(nèi)軟件行業(yè)的迅猛發(fā)展,社會(huì)對軟件人才的需求量越來越大。為此,教育部于2001年12月發(fā)布《關(guān)于批準(zhǔn)有關(guān)高等學(xué)校試辦示范性軟件學(xué)院的通知》,以35所重點(diǎn)高校為依托,開辦示范性軟件學(xué)院,采取開放式的培養(yǎng)模式,摸索培養(yǎng)高素質(zhì)的軟件工程人才的方式。
軟件工程專業(yè)所使用的教材大多來自于計(jì)算機(jī)科學(xué)與技術(shù)!半x散數(shù)學(xué)”是計(jì)算機(jī)科學(xué)與技術(shù)和軟件工程專業(yè)的培養(yǎng)體系中的核心基礎(chǔ)課程。大多數(shù)離散數(shù)學(xué)的教材都是針對計(jì)算機(jī)科學(xué)與技術(shù)專業(yè),多著重于數(shù)學(xué)理論的建立與推導(dǎo),涉及的實(shí)際工程應(yīng)用較少。這使得學(xué)生在學(xué)習(xí)的過程中,很難對重要的知識點(diǎn)消化吸收,降低了學(xué)習(xí)效率。國外的一些經(jīng)典教材邏輯性強(qiáng)但實(shí)例較少,并不太適合自學(xué),而有些教材雖然實(shí)例較多,但邏輯性中國學(xué)生難以接受;谶@種現(xiàn)狀,在我們軟件工程專業(yè)教授離散數(shù)學(xué)多年經(jīng)驗(yàn)的基礎(chǔ)上,經(jīng)過廣泛的調(diào)研以及與相關(guān)任課老師的交流與討論,認(rèn)為有必要編寫一本實(shí)例較多,邏輯合理,淺顯易懂,便于軟件工程專業(yè)學(xué)生學(xué)習(xí)的離散數(shù)學(xué)教材。
離散數(shù)學(xué)在軟件工程專業(yè)的授課內(nèi)容一般分為4大部分:數(shù)理邏輯、集合論、代數(shù)系統(tǒng)、圖論,這4個(gè)部分緊密連接。數(shù)理邏輯描述了一個(gè)符號化體系,這個(gè)體系可以描述集合論中的所有概念。集合論中又有三個(gè)小模塊:集合、關(guān)系、函數(shù)。關(guān)系是集合中迪卡兒乘積的子集,函數(shù)是關(guān)系的子集,代數(shù)系統(tǒng)是定義函數(shù)的運(yùn)算,圖論是一類特殊的代數(shù)系統(tǒng)。本教材針對軟件工程專業(yè),強(qiáng)調(diào)系統(tǒng)邏輯性,前后內(nèi)容的銜接,在內(nèi)容安排上會(huì)點(diǎn)出這種聯(lián)系并將章節(jié)高度地模塊化,另外,整本書使用統(tǒng)一的符號化體系描述和解題。因此本教材具有以下一些特點(diǎn):
首先,本教材著重體現(xiàn)理論與應(yīng)用的結(jié)合。離散數(shù)學(xué)是軟件工程專業(yè)的核心課程之一,與高等數(shù)學(xué)、線性代數(shù)等其他公共數(shù)學(xué)課程不同,但是,對于學(xué)生而言,往往誤把它作為同高等數(shù)學(xué)一樣的公共數(shù)學(xué)課,僅僅認(rèn)識到離散數(shù)學(xué)的理論公式部分,看不到其在實(shí)際中的應(yīng)用價(jià)值以及同軟件工程專業(yè)之間的關(guān)系和在軟件工程專業(yè)中處的位置。本書的一個(gè)著眼點(diǎn)就是在章節(jié)結(jié)構(gòu)清晰的基礎(chǔ)上,每一個(gè)部分都與具體的應(yīng)用相結(jié)合,比如說布爾邏輯與信息檢索、圖的遍歷與網(wǎng)絡(luò)爬蟲、圖的最短路徑與地圖導(dǎo)航等。每一個(gè)定義、定理都由軟件工程的實(shí)例加以解釋和說明,增強(qiáng)可讀性,這對軟件工程專業(yè)的學(xué)生來說,看到這些應(yīng)用與實(shí)例能夠激發(fā)學(xué)生的學(xué)習(xí)熱情,并培養(yǎng)建立離散模型解題的認(rèn)識和能力,不斷增強(qiáng)對軟件工程的認(rèn)識和理解。為此,在本教材中,我們?yōu)檫@些定義和定理準(zhǔn)備了大量的范例,將抽象的內(nèi)容具體化,來降低理解的難度。
其次,實(shí)例同軟件工程的相關(guān)性強(qiáng)。對知識點(diǎn)的解釋方式同被教授對象的知識體系的吻合度越高,其被理解和吸收的效率就越高。為了使教材中的知識點(diǎn)可以更好地被軟件工程專業(yè)的學(xué)生所掌握,我們在教材中應(yīng)用了許多同計(jì)算機(jī)科學(xué)相關(guān)的實(shí)例。
最后,離散數(shù)學(xué)是很多軟件工程專業(yè)課程的先修課,比如說操作系統(tǒng)、數(shù)據(jù)結(jié)構(gòu)、編譯原理等。本書將相關(guān)理論與后續(xù)專業(yè)課聯(lián)系,真正實(shí)現(xiàn)先修課的價(jià)值和無縫銜接,幫助學(xué)生構(gòu)建自己的知識架構(gòu)。將軟件工程的基本原理貫穿到離散數(shù)學(xué)的知識點(diǎn),貫穿到后續(xù)課程的體系中。
在本書的編寫過程中,得到了許多教師的幫助,特別是曹曉東教授對書稿進(jìn)行了認(rèn)真的審閱,并提出了寶貴的修改意見,對此我們表示衷心的感謝。本教材的第3~5章由周勇老師完成,其他部分由陳志奎老師完成,高靜老師參與了例習(xí)題的補(bǔ)充和部分內(nèi)容的修改與完善。作者還要感謝清華大學(xué)出版社的編輯,是在他們的支持下,才能使本書很快出版發(fā)行。另外,本書在編寫過程中參考和引用了有關(guān)方面的書籍,以及一些網(wǎng)絡(luò)材料,作者在此對參考文獻(xiàn)中所有的作者表示衷心的感謝。
由于作者的學(xué)識水平有限,書中如出現(xiàn)不準(zhǔn)確、不適宜或者疏漏的內(nèi)容,希望讀者給予批評指正,在此表示感謝。
編者2016年春于大連理工大學(xué)
第1章命題邏輯
1.1命題和聯(lián)結(jié)詞
1.1.1命題的概念
1.1.2聯(lián)結(jié)詞
1.2合式公式與真值表
1.2.1合式公式
1.2.2真值表
1.3永真式和等價(jià)式
1.3.1永真式
1.3.2等價(jià)式
1.3.3代入規(guī)則和替換規(guī)則
1.4對偶式與蘊(yùn)涵式
1.4.1對偶式
1.4.2蘊(yùn)涵式
1.5范式和判定問題
1.5.1析取范式和合取范式
1.5.2主析取范式和主合取范式
1.6命題演算的推理理論
1.7基于布爾邏輯的信息檢索
1.7.1布爾邏輯運(yùn)算符
1.7.2應(yīng)用技巧
習(xí)題
第2章謂詞邏輯
2.1基本概念和表示
2.1.1個(gè)體、謂詞和謂詞形式
2.1.2量詞
2.1.3合式謂詞公式
2.1.4自由變元和約束變元
2.2謂詞邏輯的翻譯與解釋
2.2.1謂詞邏輯的翻譯
2.2.2謂詞公式的解釋
2.3謂詞邏輯的等價(jià)式與蘊(yùn)涵式
2.4謂詞邏輯中的推論理論
2.4.1推理規(guī)則
2.4.2推理實(shí)例
2.5謂詞邏輯中公式范式
2.5.1前束范式
2.5.2斯柯林范式
2.6謂詞邏輯的應(yīng)用
習(xí)題
第3章集合論
3.1集合的概念及其表示
3.2集合的運(yùn)算及恒等式
3.3有窮集的計(jì)數(shù)和包含排斥原理
習(xí)題
第4章二元關(guān)系
4.1多重序元與笛卡兒乘積
4.2關(guān)系的基本概念
4.3關(guān)系的運(yùn)算
4.4關(guān)系的性質(zhì)
4.5關(guān)系的表示
4.6關(guān)系的閉包運(yùn)算
4.7特殊關(guān)系
4.7.1集合的劃分和覆蓋
4.7.2等價(jià)關(guān)系
4.7.3相容關(guān)系
4.7.4次序關(guān)系
4.7.5偏序集合與哈斯圖
4.8*關(guān)系型數(shù)據(jù)庫與非關(guān)系型數(shù)據(jù)庫
4.8.1關(guān)系型數(shù)據(jù)庫
4.8.2非關(guān)系型數(shù)據(jù)庫
習(xí)題
第5章函數(shù)
5.1函數(shù)的基本概念和性質(zhì)
5.2函數(shù)的合成和合成函數(shù)的性質(zhì)
5.3特殊函數(shù)
5.4反函數(shù)
5.5特征函數(shù)
5.6基數(shù)
5.7*不可解問題
5.7.1不可解問題的存在性
5.7.2停機(jī)問題
習(xí)題
第6章代數(shù)系統(tǒng)
6.1代數(shù)系統(tǒng)的一般概念
6.1.1二元運(yùn)算
6.1.2代數(shù)系統(tǒng)
6.2代數(shù)系統(tǒng)的基本性質(zhì)
6.3同態(tài)與同構(gòu)
6.3.1同態(tài)
6.3.2同構(gòu)
6.3.3同態(tài)與同構(gòu)的性質(zhì)
6.4同余關(guān)系
6.5商代數(shù)
6.6積代數(shù)
6.7云環(huán)境中的數(shù)據(jù)安全之同態(tài)計(jì)算
6.7.1云計(jì)算中的同態(tài)計(jì)算
6.7.2數(shù)據(jù)安全的同態(tài)計(jì)算過程
6.7.3同態(tài)計(jì)算在數(shù)據(jù)安全中的主要應(yīng)用
習(xí)題
第7章群與環(huán)
7.1半群
7.2群
7.2.1群的概念
7.2.2群的性質(zhì)
7.3子群與群的陪集分解
7.3.1子群
7.3.2子群的判定
7.3.3子群的性質(zhì)
7.3.4子群的陪集分解
7.3.5拉格朗日定理
7.4循環(huán)群與置換群
7.4.1循環(huán)群
7.4.2置換群
7.5群的同態(tài)與同構(gòu)
7.6環(huán)與域
7.6.1環(huán)的概念與性質(zhì)
7.6.2域的概念
7.7群理論的應(yīng)用
7.7.1群與網(wǎng)絡(luò)安全
7.7.2群與糾錯(cuò)編碼
習(xí)題
第8章格與布爾代數(shù)
8.1格的定義與性質(zhì)
8.2分配格、有補(bǔ)格與布爾代數(shù)
8.3應(yīng)用
習(xí)題
第9章圖的基本概念及其矩陣表示
9.1圖的基本概念
9.1.1圖的定義及相關(guān)概念
9.1.2結(jié)點(diǎn)的度
9.2子圖和圖的運(yùn)算
9.2.1子圖和補(bǔ)圖
9.2.2圖的運(yùn)算
9.3路徑、回路和連通性
9.3.1路徑和回路
9.3.2圖的連通性
9.4圖的矩陣表示
9.4.1鄰接矩陣
9.4.2可達(dá)性矩陣
9.4.3關(guān)聯(lián)矩陣
9.5圖論在社會(huì)網(wǎng)絡(luò)分析中的應(yīng)用
習(xí)題
第10章幾種特殊圖
10.1歐拉圖
10.2哈密爾頓圖
10.3二部圖及匹配
10.3.1二部圖的概念及性質(zhì)
10.3.2二部圖匹配
10.4平面圖
10.4.1平面圖的概念及性質(zhì)
10.4.2多邊形圖、對偶圖及平面圖著色
10.5網(wǎng)絡(luò)
10.5.1網(wǎng)絡(luò)的基本概念
10.5.2網(wǎng)絡(luò)流
10.5.3網(wǎng)絡(luò)最大流求解
10.5.4開關(guān)網(wǎng)絡(luò)
10.6圖的實(shí)例分析
10.6.1中國郵遞員問題
10.6.2旅行售貨員問題
10.6.3排課問題
10.6.4時(shí)延容忍網(wǎng)絡(luò)問題
10.6.5最短路徑問題
習(xí)題
第11章樹
11.1樹與生成樹
11.1.1樹及其性質(zhì)
11.1.2生成樹與最小生成樹
11.2有向樹及其應(yīng)用
11.2.1有向樹
11.2.2m叉樹
11.2.3有序樹
11.2.4二叉樹的遍歷
11.2.5搜索樹
習(xí)題
參考文獻(xiàn)