前言
離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)專業(yè)的核心課程、信息類專業(yè)的必修課程、多數(shù)工科類專業(yè)的重要選修課程.離散數(shù)學(xué)在各學(xué)科領(lǐng)域，特別在計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，同時(shí)離散數(shù)學(xué)是學(xué)習(xí)程序設(shè)計(jì)語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯技術(shù)、人工智能、數(shù)據(jù)庫(kù)、算法設(shè)計(jì)與分析、理論計(jì)算機(jī)科學(xué)基礎(chǔ)、電路分析與邏輯設(shè)計(jì)等課程必不可少的先修課程.近年來，隨著科學(xué)技術(shù)的飛速發(fā)展，計(jì)算機(jī)科學(xué)與技術(shù)、智能科學(xué)與技術(shù)、數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)等相關(guān)學(xué)科專業(yè)正在以驚人的速度不斷迭代發(fā)展，對(duì)人類社會(huì)的各個(gè)領(lǐng)域產(chǎn)生著日益廣泛和深入的影響.離散數(shù)學(xué)課程所體現(xiàn)的思想和方法，廣泛地體現(xiàn)在計(jì)算機(jī)科學(xué)、人工智能、大數(shù)據(jù)技術(shù)及相關(guān)專業(yè)的諸領(lǐng)域，從科學(xué)計(jì)算到信息處理，從理論計(jì)算機(jī)科學(xué)到計(jì)算機(jī)應(yīng)用技術(shù)，從計(jì)算機(jī)軟件到計(jì)算機(jī)硬件，從人工智能到認(rèn)知系統(tǒng)，從認(rèn)知系統(tǒng)到生成式人工智能系統(tǒng)等，無(wú)不與離散數(shù)學(xué)密切相關(guān).通過離散數(shù)學(xué)課程的學(xué)習(xí)，學(xué)生不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅(jiān)實(shí)的基礎(chǔ).
離散數(shù)學(xué)是邏輯學(xué)、集合論(包括函數(shù))、數(shù)論基礎(chǔ)、算法設(shè)計(jì)、組合分析、
關(guān)系理論、圖論、抽象代數(shù)(包括代數(shù)系統(tǒng)，群、環(huán)、域等)、布爾代數(shù)、計(jì)算模型(語(yǔ)言與自動(dòng)機(jī))等匯集起來的一門綜合學(xué)科.多數(shù)工科專業(yè)的離散數(shù)學(xué)課程主要內(nèi)容包括四個(gè)部分：數(shù)理邏輯、集合與關(guān)系、代數(shù)系統(tǒng)、圖論基礎(chǔ)等.①數(shù)理邏輯是邏輯學(xué)的一個(gè)核心內(nèi)容，它是研究思維形式及思維規(guī)律的基礎(chǔ)，也就是研究推理過程規(guī)律的科學(xué).數(shù)理邏輯是用數(shù)學(xué)方法來研究推理的規(guī)律，這里所指的數(shù)學(xué)方法，就是引進(jìn)一套符號(hào)體系的方法，在其中表達(dá)和研究推理的規(guī)律.②集合論的起源可以追溯到19世紀(jì)末期，德國(guó)數(shù)學(xué)家康托爾在《數(shù)學(xué)雜志》上發(fā)表了關(guān)于無(wú)窮集合論的第一篇革命性文章，奠定了集合論的基礎(chǔ).集合不僅可以用來表示數(shù)及其運(yùn)算，更可以用于非數(shù)值信息的表示和處理，有些問題很難用傳統(tǒng)的數(shù)值計(jì)算來處理，但可以用集合運(yùn)算來處理，在程序語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、編譯原理、數(shù)據(jù)庫(kù)與知識(shí)庫(kù)、形式語(yǔ)言和人工智能等領(lǐng)域中都得到了廣泛的應(yīng)用，并且還得到了發(fā)展，如Zadeh提出的模糊集理論和Pawlak提出的粗糙集理論.③代數(shù)系統(tǒng)是抽象代數(shù)的一個(gè)重要內(nèi)容，除了數(shù)理邏輯外，對(duì)計(jì)算科學(xué)最有用的數(shù)學(xué)分支學(xué)就是代數(shù)，特別是抽象代數(shù)，在許多實(shí)際問題的研究中都需要用某種數(shù)學(xué)結(jié)構(gòu)來構(gòu)造數(shù)學(xué)模型.代數(shù)系統(tǒng)就是一種很重要的數(shù)學(xué)結(jié)構(gòu)，主要包括半群、群、環(huán)、域、格與布爾代數(shù)等，半群理論在自動(dòng)機(jī)理論和形式語(yǔ)言中發(fā)揮了重要作用，有限域理論是編碼理論的數(shù)學(xué)基礎(chǔ)，在信息通信中起著重要作用，格和布爾代數(shù)是電子線路設(shè)計(jì)、計(jì)算機(jī)硬件設(shè)計(jì)和通信系統(tǒng)設(shè)計(jì)的重要作具.④圖論是離散數(shù)學(xué)的重要組成部分，是近代應(yīng)用數(shù)學(xué)的重要分支.1736年是圖論歷史元年，因?yàn)樵谶@一年瑞士數(shù)學(xué)家歐拉發(fā)表了圖論的首篇論文——《哥尼斯堡七橋問題無(wú)解》，標(biāo)志著圖論的誕生.作為描述事物之間關(guān)系的手段或稱工具，圖論在許多領(lǐng)域，諸如計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、運(yùn)籌學(xué)、信息論、控制論、人工智能、計(jì)算機(jī)網(wǎng)絡(luò)、社會(huì)科學(xué)以及經(jīng)濟(jì)管理、軍事、國(guó)防、工農(nóng)業(yè)生產(chǎn)等方面都得到廣泛的應(yīng)用，也正是因?yàn)樵诒姸喾矫娴膽?yīng)用，圖論自身才得到了非常迅速的發(fā)展.
本書結(jié)合信息類工科學(xué)生培養(yǎng)方案對(duì)應(yīng)的課程體系與知識(shí)體系，尤其是計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、智能科學(xué)與技術(shù)、數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)和人工智能等相關(guān)專業(yè)，針對(duì)這類專業(yè)后繼課程知識(shí)銜接的需要，融合離散數(shù)學(xué)的重要內(nèi)容，在編者團(tuán)隊(duì)二十多年離散數(shù)學(xué)教學(xué)實(shí)踐的基礎(chǔ)上，在學(xué)校離散數(shù)學(xué)重點(diǎn)課程建設(shè)和精品課程建設(shè)的基礎(chǔ)上，在我們出版的《離散數(shù)學(xué)》（機(jī)械工業(yè)出版社，2010年）教材和《離散數(shù)學(xué)及其應(yīng)用》（清華大學(xué)出版社，2016年）基礎(chǔ)之上，借鑒了國(guó)內(nèi)外眾多離散數(shù)學(xué)教材的優(yōu)點(diǎn)（尤其是工科類教材），
針對(duì)信息類工科學(xué)生學(xué)科專業(yè)特點(diǎn)，反復(fù)調(diào)研，充分論證，結(jié)合教學(xué)團(tuán)隊(duì)在教學(xué)和科研方面多年的成果編寫而成.本書在力求介紹離散數(shù)學(xué)基礎(chǔ)知識(shí)的前提下，簡(jiǎn)明扼要、通俗易懂地介紹相關(guān)內(nèi)容，注重理論聯(lián)系實(shí)際，融入啟發(fā)式教學(xué)理念和課程思政元素，使得教師教學(xué)和學(xué)生自學(xué)渾然一體，著重培養(yǎng)學(xué)生的自學(xué)能力和創(chuàng)新能力.本書的特點(diǎn)如下：內(nèi)容深入淺出，知識(shí)點(diǎn)脈絡(luò)清晰，通俗易懂；基礎(chǔ)理論與實(shí)際問題相結(jié)合，變抽象思維為形象思維，提高學(xué)生知識(shí)應(yīng)用的綜合能力和創(chuàng)新實(shí)踐能力；重點(diǎn)突出知識(shí)的內(nèi)在邏輯結(jié)構(gòu)，注重培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)思維能力；編寫內(nèi)容普適性強(qiáng)，便于工科學(xué)生考研復(fù)習(xí).
離 散 數(shù) 學(xué)
前言
全書共分為四個(gè)部分.其中，第1部分為數(shù)理邏輯，由蔣觀敏和張清華等人編寫，第2部分為集合論，由張清華和尹邦勇等人編寫，第3部分為代數(shù)結(jié)構(gòu)，由劉勇杉和劉勇等人編寫，第4部分為圖論，由楊映雪、蒲興成和張清華等人編寫.
本書的出版得到了重慶郵電大學(xué)規(guī)劃教材建設(shè)項(xiàng)目（JCZ 2024-13）、重慶市高等教育教學(xué)改革研究重點(diǎn)項(xiàng)目和重慶郵電大學(xué)學(xué)科專業(yè)建設(shè)項(xiàng)目等的資助
，還得到了陳六新和方長(zhǎng)杰等老師和部分研究生（趙凡、郭芮利等）的幫助.特別感謝楊春德、朱偉、鮮思東教授
為本書提出的寶貴修改意見和建議.感謝為本書出版做出貢獻(xiàn)的同志們！最后，還要特別感謝機(jī)械工業(yè)出版社湯嘉編輯的大力支持，使得本書得以順利出版.
本書的講義在重慶郵電大學(xué)等多所高校多次講授，反復(fù)修改，但由于編者水平所限，加之時(shí)間倉(cāng)促，書中難免有不妥或錯(cuò)誤之處，懇請(qǐng)廣大讀者批評(píng)指正.
編者