本書是“十二五”普通高等教育本科***規(guī)劃教材。
本書是編者根據(jù)多年講授離散數(shù)學課程的教學實踐,并參考國內(nèi)外同類教材編寫而成的。為適應計算機科學發(fā)展的需要,本書增加了新的內(nèi)容,其目的在于通過講授離散數(shù)學中的基本概念、基本定理和運算及其在計算機科學與技術(shù)學科中的應用,培養(yǎng)學生的數(shù)學抽象能力、用數(shù)學語言描述問題的能力、邏輯思維能力以及數(shù)學論證能力。 本書力求概念闡述嚴謹,證明推演詳盡,較難理解的概念用實例說明。 全書分四篇共24章,內(nèi)容包括:集合論與數(shù)理邏輯、圖論與組合數(shù)學、代數(shù)結(jié)構(gòu)與初等數(shù)論、形式語言與自動機理論基礎(chǔ)。本書有配套教材《離散數(shù)學題解與分析(第二版)》(劉任任主編,中國鐵道出版社出版,2015年)。
本書適合作為高等院校計算機及相關(guān)專業(yè)的教材,也可供從事離散結(jié)構(gòu)領(lǐng)域研究工作的人員參考。
劉任任,男,漢族,中共黨員,博士,教授,博士生導師。 現(xiàn)任湘潭大學信息工程學院院長、中國計算機學會理事、中國人民解放軍總參謀部三部八局兼職研究員、中國計算機學會多值邏輯與模糊邏輯專業(yè)委員會委員、理論計算機科學專業(yè)委員會委員、教育部高等學校計算機科學與技術(shù)專業(yè)教學指導分委員會專家工作組成員,全國高等學校計算機教育研究會常務(wù)理事,湖南省高教學會計算機教育專業(yè)委員會副理事長, 湖南省軟件行業(yè)協(xié)會常務(wù)理事、專家委員會成員,《計算技術(shù)與自動化》雜志編委。
第一篇集合論與數(shù)理邏輯
第1章集合
§1.1集合的概念及其表示
§1.2集合的基本運算
§1.3笛卡兒積6習題
第2章關(guān)系
§2.1關(guān)系及其表示
§2.2關(guān)系的運算
§2.3等價關(guān)系
§2.4序關(guān)系15習題
第3章映射
§3.1基本概念
§3.2映射的運算20習題
第4章可數(shù)集與不可數(shù)集
§4.1等勢
§4.2集合的基數(shù)
§4.3可數(shù)集與不可數(shù)集的概念24習題
第5章命題邏輯
§5.1命題與邏輯聯(lián)結(jié)詞
§5.2命題公式與等值演算
§5.3對偶與范式
§5.4推理理論
§5.5命題演算的公理系統(tǒng)42習題
第6章一階邏輯
§6.1謂詞與量詞
§6.2合式公式及解釋
§6.3等值式與范式
§6.4一階邏輯的推理理論56習題
第二篇圖論與組合數(shù)學
第7章圖與子圖
§7.1圖的概念
§7.2圖的同構(gòu)
§7.3頂點的度
§7.4子圖及圖的運算
§7.5通路與連通圖
§7.6圖的矩陣表示
§7.7應用(*短通路問題)73習題
第8章樹
§8.1樹的定義
§8.2生成樹
§8.3應用 (**樹問題)84習題
第9章圖的連通性
§9.1點連通度和邊連通度
§9.2塊
§9.3應用 (構(gòu)造可靠的通信網(wǎng)絡(luò))91習題
第10章E圖與H圖
§10.1七橋問題與E圖
§10.2周游世界問題與H圖
§10.3應用 (旅行推銷員問題)99習題
第11章匹配與點獨立集
§11.1匹配
§11.2獨立集和覆蓋
§11.3Ramsey數(shù)
§11.4應用 (人員分配問題)112習題
第12章圖的著色
§12.1頂點著色
§12.2邊著色
§12.3色多項式
§12.4應用123習題
第13章平面圖
§13.1平面圖的概念
§13.2歐拉公式
§13.3可平面性判定
§13.4平面圖的面著色
§13.5應用(印制電路板的設(shè)計)131習題
第14章有向圖
§14.1有向圖的概念
§14.2有向通路與有向回路
§14.3有向樹
§14.4應用139習題
第15章網(wǎng)絡(luò)**流
§15.1網(wǎng)絡(luò)的流與割
§15.2**流*小割定理
§15.3應用(中國郵遞員問題)147習題
第16章排列和組合的一般計數(shù)方法
§16.1兩個基本的計數(shù)法則
§16.2基本排列組合的計數(shù)方法
§16.3可重復排列組合的計數(shù)方法151習題
第17章容斥原理
§17.1容斥原理概述
§17.2有禁止位的排列155習題
第18章遞推關(guān)系與生成函數(shù)
§18.1遞推關(guān)系及其解法
§18.2生成函數(shù)161習題
第三篇代數(shù)結(jié)構(gòu)與初等數(shù)論
第19章整數(shù)
§19.1整除性
§19.2素因數(shù)分解
§19.3同余
§19.4孫子定理?Euler函數(shù)
§19.5數(shù)論在計算機密碼學中的應用179習題
第20章群
§20.1群的概念
§20.2子群
*§20.3置換群
§20.4陪集與Lagrange定理
§20.5同態(tài)與同構(gòu)
§20.6群在計算機科學與技術(shù)中的應用201習題
第21章環(huán)與域
§21.1環(huán)與子環(huán)
§21.2環(huán)同態(tài)
§21.3域的特征?質(zhì)域
*§21.4有限域
§21.5有限域的結(jié)構(gòu)
§21.6糾錯碼
§21.7多項式編碼方法及其實現(xiàn)230習題
第22章格與布爾代數(shù)
§22.1格的定義
§22.2格的性質(zhì)
§22.3幾種特殊的格
§22.4布爾代數(shù)
§22.5有限布爾代數(shù)的結(jié)構(gòu)
§22.6格與布爾代數(shù)在計算機科學與技術(shù)中的應用253習題
第四篇形式語言與自動機理論基礎(chǔ)
第23章形式語言
§23.1符號、符號串及其運算
§23.2文法與語言的形式定義
§23.3正規(guī)表達式
§23.4正規(guī)文法與正規(guī)式276習題
第24章有限自動機理論
§24.1有限自動機的定義與構(gòu)造
§24.2確定的有限自動機(DFA)
§24.3不確定的有限自動機(NFA)
§24.4NFA的確定化
§24.5DFA的*小化
§24.6正規(guī)集與有限自動機的等價性290習題
參考文獻