離散數(shù)學(xué)

前言

近年來，計(jì)算機(jī)科學(xué)與信息技術(shù)正在以驚人的速度迅猛發(fā)展，并且對(duì)人類社會(huì)的各個(gè)領(lǐng)域產(chǎn)生著日益廣泛和深遠(yuǎn)的影響。離散數(shù)學(xué)，作為計(jì)算機(jī)科學(xué)與技術(shù)的重要理論基礎(chǔ)之一，也因此更加顯示出它的重要性。離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)與技術(shù)中的地位如同微積分在物理學(xué)和工程技術(shù)中的地位一樣，離散數(shù)學(xué)為計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展奠定了重要的數(shù)學(xué)基礎(chǔ)。不僅離散數(shù)學(xué)的基本思想、概念和方法廣泛地滲透到計(jì)算機(jī)科學(xué)與技術(shù)的各個(gè)領(lǐng)域，而且其基本理論和研究成果更是全面而系統(tǒng)地影響和推動(dòng)著這些領(lǐng)域的發(fā)展。例如，布爾代數(shù)為開關(guān)電路的研究提供了重要的分析工具，并且導(dǎo)致了數(shù)字邏輯理論的建立；自動(dòng)機(jī)理論對(duì)形式語言及其編譯產(chǎn)生了重大的影響，并形成了完整而嚴(yán)密的理論體系；謂詞演算成為程序理論的一種重要研究工具；代數(shù)結(jié)構(gòu)為編碼理論的研究提供了新的途徑；圖靈機(jī)模型和遞歸函數(shù)理論構(gòu)成了可計(jì)算性理論研究的基礎(chǔ)。離散數(shù)學(xué)的這些重要成果和作用，使得它成為一個(gè)計(jì)算機(jī)科學(xué)工作者和工程師所必須具備的基本理論知識(shí)。對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來說，離散數(shù)學(xué)不僅是很多后續(xù)專業(yè)課程所必需的先修課，而且也為高等院校工科本科生提供了必要的抽象思維和嚴(yán)密推理的基本訓(xùn)練。

內(nèi)容概要

　　《離散數(shù)學(xué)（修訂版）》由五篇構(gòu)成。第一篇數(shù)理邏輯，內(nèi)容包括：命題邏輯，謂詞邏輯，公理系統(tǒng)，歸結(jié)法原理。第二篇集合論，內(nèi)容包括：集合的基本概念及其運(yùn)算，關(guān)系，函數(shù)，自然數(shù)和基數(shù)。第三篇圖論，內(nèi)容包括：基本概念，通路問題，圖的矩陣表示，樹，穿程問題，二分圖的匹配問題，平面圖及色數(shù)。第四篇代數(shù)系統(tǒng)，內(nèi)容包括：基本概念，半群和群，環(huán)和域，格和布爾代數(shù)，抽象數(shù)據(jù)類型的代數(shù)規(guī)范。第五篇有限自動(dòng)機(jī)理論，內(nèi)容包括：基本概念，有限自動(dòng)機(jī)的簡化，有限自動(dòng)機(jī)和正則表達(dá)式，有限自動(dòng)機(jī)的綜合與應(yīng)用?！　　峨x散數(shù)學(xué)（修訂版）》內(nèi)容系統(tǒng)、全面，概念清晰，敘述嚴(yán)謹(jǐn)精煉，推理詳盡嚴(yán)格，語言簡明易懂，各部分獨(dú)立成篇，并有大量例題和習(xí)題，便于讀者理解和掌握相關(guān)知識(shí)?！峨x散數(shù)學(xué)（修訂版）》可作為高等院校本科計(jì)算機(jī)專業(yè)離散數(shù)學(xué)課程的教材，也可供計(jì)算機(jī)科學(xué)與工程技術(shù)人員學(xué)習(xí)參考。

書籍目錄

第一篇 數(shù)理邏輯第一章 命題邏輯§1．1 命題和聯(lián)結(jié)詞§1．2 公式和真值賦值§1．3 等值演算§1．4 對(duì)偶定理§1．5 聯(lián)結(jié)詞的完全集§1．6 范式§1．7 邏輯推論習(xí)題第二章 謂詞邏輯§2．1 謂詞和量詞§2．2 項(xiàng)和公式§2．3 解釋和賦值§2．4 永真式§2．5 等值演算§2．6 邏輯推論習(xí)題二第三章 公理系統(tǒng)§3．1 命題邏輯的公理系統(tǒng)§3．2 謂詞邏輯的公理系統(tǒng)習(xí)題三第四章 歸結(jié)法原理§4．1 命題邏輯的歸結(jié)法§4．2 前束范式與斯科倫范式§4．3 謂詞邏輯的歸結(jié)法習(xí)題四參考文獻(xiàn)第二篇 集合論第五章 集合的基本概念及其運(yùn)算§5．1 集合與元素§5．2 集合間的相等和包含關(guān)系§5．3 冪集§5．4 集合的運(yùn)算§5．5 有窮集的計(jì)數(shù)原理§5．6 集合的歸納定義法§5．7 有序偶和笛卡兒乘積習(xí)題五第六章 關(guān)系§6．1 關(guān)系及其性質(zhì)§6．2 關(guān)系的運(yùn)算§6．3 次序關(guān)系  §6．4 等價(jià)關(guān)系、劃分及其他習(xí)題六第七章 函數(shù)§7．1 基本概念§7．2 函數(shù)的復(fù)合§7．3 特殊性質(zhì)的函數(shù)§7．4 集合的特征函數(shù)習(xí)題七第八章 自然數(shù)和基數(shù)§8．1 自然數(shù)及數(shù)學(xué)歸納法§8．2 基數(shù)習(xí)題八 參考文獻(xiàn)第三篇 圖論第九章 基本概念§9．1 有向圖及無向圖  §9．2 圖的基本結(jié)構(gòu)§9．3 子圖  §9．4 連通性  §9．5 頂點(diǎn)基和強(qiáng)分圖習(xí)題九第十章 通路問題§10．1 最短通路§10．2 關(guān)鍵通路習(xí)題十第十一章 圖的矩陣表示§11．1 鄰接矩陣§11．2 有向圖的可達(dá)性矩陣§11．3 關(guān)聯(lián)矩陣習(xí)題十第十二章 樹§12．1 樹的一般定義§12．2 根樹與有序樹§12．3 二元樹§12．4 生成樹§12．5 割集習(xí)題十二第十三章 穿程問題§13．1 歐拉圖§13．2 哈密頓圖習(xí)題十三第十四章 二分圖的匹配問題§14．1 基本概念§14．2 二分圖的最大匹配§14．3 從x到y(tǒng)的匹配習(xí)題十四第十五章 平面圖及色數(shù)§15．1 平面圖§15．2 色數(shù)習(xí)題十五參考文獻(xiàn) 第四篇 代數(shù)系統(tǒng)第十六章基本概念§16．1 代數(shù)系統(tǒng)§16．2 同態(tài)和同構(gòu)§16．3 子代數(shù)和商代數(shù)習(xí)題十六第十七章 半群和群§17．1 半群的概念§17．2 子半群和半群同態(tài)§17．3 商半群和半群直積§17．4 群的概念§17．5 子群和群的同態(tài)§17．6 變換群、置換群和循環(huán)群§17．7 不變子群和商群習(xí)題十七第十八章 環(huán)和域§18．1 環(huán)和域的概念§18．2 子環(huán)和環(huán)的同態(tài)§18．3 理想和商環(huán)習(xí)題十八第十九章 格和布爾代數(shù)§19．1 格的定義與基本性質(zhì)§19．2 子格和格的同態(tài)§19．3 布爾代數(shù)§19．4 布爾代數(shù)的表示習(xí)題十九第二十章 抽象數(shù)據(jù)類型的代數(shù)規(guī)范§20．1 標(biāo)記、項(xiàng)和代數(shù)規(guī)范§20．2 ∑-代數(shù)和范疇§20．3 代數(shù)規(guī)范的初始語義習(xí)題二十參考文獻(xiàn)第五篇 有限自動(dòng)機(jī)理論第二十一章 基本概念§21．1 字符表、字符串及其集合的運(yùn)算§21．2 有限自動(dòng)機(jī)的定義§21．3 有限自動(dòng)機(jī)的等價(jià)§21．4 Mealy機(jī)與Moore機(jī)習(xí)題二十第二十二章 有限自動(dòng)機(jī)的簡化§22．1 最小有限自動(dòng)機(jī)的定義及性質(zhì)§22．2 狀態(tài)集的S劃分和格LM§22．3 有限自動(dòng)機(jī)的最小化習(xí)題二十二第二十三章 有限自動(dòng)機(jī)和正則表達(dá)式§23．1 有限自動(dòng)機(jī)的識(shí)別功能§23．2 非確定有限自動(dòng)機(jī)§23．3 正則表達(dá)式§23．4 由正則表達(dá)式構(gòu)造FA的算法§23．5 有限自動(dòng)機(jī)和正則表達(dá)式的等價(jià)性§23．6 正則集合及其性質(zhì)習(xí)題二十三第二十四章 有限自動(dòng)機(jī)的綜合與應(yīng)用§24．1 有限自動(dòng)機(jī)的綜合§24．2 FA理論在算法設(shè)計(jì)中的應(yīng)用§24．3 FA理論與形式語言理論的關(guān)系習(xí)題二十四參考文獻(xiàn)名詞索引

章節(jié)摘錄

插圖：邏輯學(xué)是研究推理的科學(xué)，具有十分悠久的歷史，在兩千多年前的古希臘時(shí)代就已很發(fā)達(dá)。數(shù)理邏輯是數(shù)學(xué)化的邏輯學(xué)，是用數(shù)學(xué)方法研究推理的科學(xué)，其歷史只有三百多年。德國數(shù)學(xué)家、哲學(xué)家萊布尼茨（Leibniz）于17世紀(jì)中葉明確地提出了建立通用的符號(hào)語言和通用代數(shù)的思想[1]。他指出，如果我們能對(duì)人類的全部思想進(jìn)行綜合分析，并把它們化歸成最簡單的概念，那么，只要再進(jìn)一步設(shè)計(jì)出適當(dāng)?shù)姆?hào)來表示這些基本概念及其組合關(guān)系，就可以獲得一種既簡單又嚴(yán)密的符號(hào)語言。由于這種語言克服了自然語言的弊病及局限性（如不規(guī)則性、歧義性等），因此，它是一種理想的、世界性的公共語言，即所謂的“通用語言”。其次，通用語言的建立不僅有益于思想的交流，而且也有益于思維。由于在通用語言中實(shí)現(xiàn)了徹底的符號(hào)化，其中的推理過程就表現(xiàn)為符號(hào)序列的變形，從而只要對(duì)此做出明確的規(guī)定，就可以按照這些規(guī)定機(jī)械地實(shí)行推理，正如人們?cè)诖鷶?shù)運(yùn)算中按照明確的法則對(duì)代數(shù)式進(jìn)行演算一樣。我們最終所獲得的就不僅是一種“通用語言”，而且也是一種“通用代數(shù)”。在這種符號(hào)語言中，思維被“演算化”了。萊布尼茨只是進(jìn)行了一些初步的嘗試，并沒有能夠?qū)崿F(xiàn)他的關(guān)于通用符號(hào)語言和通用代數(shù)的設(shè)想，但是數(shù)理邏輯卻是沿著他的設(shè)想發(fā)展起來的。因此，人們公認(rèn)萊布尼茨為數(shù)理邏輯的創(chuàng)始人。布爾（Boole）構(gòu)造了一個(gè)抽象的代數(shù)系統(tǒng)，并且給予它多種解釋，如類的演算、命題演算、概率演算。當(dāng)然，布爾所提出的演算很不成熟，某些演算公式?jīng)]有邏輯解釋。但是，布爾的貢獻(xiàn)在于，他在邏輯史上首先提出了一個(gè)邏輯演算，實(shí)現(xiàn)了萊布尼茨的一部分設(shè)想。經(jīng)過許多數(shù)學(xué)家的改進(jìn)，今天的布爾代數(shù)已發(fā)展成為具有廣泛應(yīng)用的豐富的代數(shù)理論。

編輯推薦

《離散數(shù)學(xué)(修訂版)》為高等學(xué)校教材之一，由高等教育出版社出版。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    離散數(shù)學(xué) PDF格式下載

---