離散數(shù)學教程

前言

教過多年的離散數(shù)學課程，也寫過離散數(shù)學教材，但總覺得這門課程現(xiàn)有的一些教材內(nèi)容過于“離散”，體系結(jié)構(gòu)間的相互銜接不盡合理，知識模塊的內(nèi)在聯(lián)系不夠緊密。教學之余，筆者感到似乎需要一本系統(tǒng)性更強的離散數(shù)學教程，以更好地滿足教學的需求。因此，筆者在傳統(tǒng)內(nèi)容的基礎(chǔ)上對內(nèi)容進行擴展梳理，試圖做成這樣一部“離散數(shù)學教程”：它首先把離散結(jié)構(gòu)涉及的原始概念，諸如集合、命題、謂詞、運算等，提煉出來作為全部學習內(nèi)容的準備知識，為其后的各大組成模塊作統(tǒng)一的鋪墊；然后介紹離散結(jié)構(gòu)形式化表示的理論，即邏輯代數(shù)和集合代數(shù)；再基于所有這些公共基礎(chǔ)，由淺入深、由簡單到復(fù)雜、由具體到抽象地依次推出各類離散結(jié)構(gòu)及其數(shù)學模型。現(xiàn)在呈現(xiàn)在讀者面前的，正是筆者努力想要達成的“離散數(shù)學教程”的雛形。它在選材和編排上的內(nèi)在邏輯大致體現(xiàn)在以下圖示中。如果說本教程在教學內(nèi)容系統(tǒng)性的改造上所做的工作還只是一種嘗試，那么在教學內(nèi)容廣泛性的開拓上可以說是用心良苦了。本教程不僅覆蓋了集合論、數(shù)理邏輯、數(shù)論、組合論、圖論、可計算性、抽象代數(shù)等基礎(chǔ)理論部分，還包含了這些基本理論在粗糙集、模糊集、自動推理、智能搜索、加密技術(shù)等領(lǐng)域的應(yīng)用，并涉及公理化集合論、數(shù)理邏輯形式系統(tǒng)、形式語言與自動機等相關(guān)理論。為了教師和學生能更好地使用本教程，更加便捷地在這個浩瀚的知識海洋里選取適合的模塊、章節(jié)，以便設(shè)計出具有自己所在院校及專業(yè)特色的離散數(shù)學課程，我們把教程的全部內(nèi)容分為了如下三個層次。（1）基本內(nèi)容，它們是教程的主體。運用本教程的教師，可以依據(jù)教育部計算機科學與技術(shù)教學指導委員會編制的《高等學校計算機科學與技術(shù)專業(yè)規(guī)范》和《高等學校計算機科學與技術(shù)專業(yè)核心課程教學實施方案》，以及所在學校的特色、定位，在基本內(nèi)容中選取大部或全部內(nèi)容進行教學。（2）推薦內(nèi)容，其標題被標記了*號。教程的這部分內(nèi)容理論上較為深入，理解上有些難度，推薦給使用本教程的教師，可視情況選作教學內(nèi)容或課外講座。

內(nèi)容概要

　　《離散數(shù)學教程》打破了傳統(tǒng)離散數(shù)學教材幾大模塊分割的編寫方式，突出知識的內(nèi)在聯(lián)系，強調(diào)理論的循序漸進、相互依存，從而更具有可讀性和系統(tǒng)性?！　　峨x散數(shù)學教程》覆蓋了集合論、數(shù)理邏輯、組合論、數(shù)論、圖論、抽象代數(shù)、可計算性等基礎(chǔ)理論部分，還包含了這些理論在粗糙集、模糊集、自動推理、智能搜索、加密技術(shù)等領(lǐng)域的應(yīng)用，并涉及公理化集合論、數(shù)理邏輯形式系統(tǒng)、形式語言與自動機等相關(guān)理論?！　　峨x散數(shù)學教程》以離散結(jié)構(gòu)為建模對象，緊密聯(lián)系計算機科學技術(shù)，特別強調(diào)應(yīng)用能力、證明技術(shù)、計算思維的培養(yǎng)。此外，《離散數(shù)學教程》內(nèi)容寬泛，深度適當，每章后還安排了與本章內(nèi)容有關(guān)的閱讀材料，便于學生及時復(fù)習并鞏固所學知識?！　　峨x散數(shù)學教程》配有教學課件與詳細的習題解答，便于教師教學。

作者簡介

王元元，中國人民解放軍理工大學教授、博士研究生指導教師，長期從事計算機基礎(chǔ)理論的研究和教學工作。先后被評為總參優(yōu)秀教員，全軍優(yōu)秀教員；榮獲國家教學名師獎、國家級教學成果二等獎；榮立二等功一次，三等功三次。其任教的主要課程有離散數(shù)學、組合數(shù)學以及數(shù)理邏輯等，其中離散數(shù)學課程被推薦為軍隊級優(yōu)質(zhì)課程和國家精品課程。所主編的教材《計算機科學中的邏輯學》、《離散數(shù)學》曾分別獲得國家級優(yōu)秀教材獎和電子工業(yè)部優(yōu)秀教材獎。

書籍目錄

第0章 準備知識0.1 集合、命題、謂詞和運算0.1.1 集合0.1.2 命題與謂詞0.1.3 集合的表示0.1.4 外延性原理與子集合0.1.5 運算練習0.1 0.2 鴿籠原理0.2.1 鴿籠原理基本形式0.2.2 鴿籠原理加強形式練習0.2 第1章 邏輯代數(shù)(上)：命題演算1.1 邏輯聯(lián)結(jié)詞與命題公式1.1.1 邏輯聯(lián)結(jié)詞1.1.2 命題公式1.1.3 語句形式化練習1.1 1.2 邏輯等價式和邏輯蘊涵式1.2.1 重言式1.2.2 邏輯等價式和邏輯蘊涵式1.2.3 對偶原理1.2.4 應(yīng)用邏輯練習1.2 1.3 范式1.3.1 析取范式和合取范式1.3.2 主析取范式與主合取范式1.3.3 聯(lián)結(jié)詞的擴充與歸約練習1.3 1.4 命題演算消解原理練習1.4 1.5 閱讀材料：布爾代數(shù)第2章 邏輯代數(shù)(下)：謂詞演算2.1 謂詞演算基本概念2.1.1 個體2.1.2 謂詞2.1.3 量詞2.1.4 謂詞公式及語句形式化練習2.1 2.2 謂詞演算永真式2.2.1 謂詞公式的語義2.2.2 謂詞演算永真式2.2.3 謂詞公式等價變換的幾個基本原理練習2.2 2.3 謂詞演算消解原理2.3.1 前柬化和消去量詞2.3.2 謂詞演算消解原理練習2.3 2.4 閱讀材料：形式推理與形式系統(tǒng)[2]2.4.1 一個形式系統(tǒng)的例子2.4.2 自然推理形式系統(tǒng)ND第3章 集合代數(shù)3.1 集合運算3.1.1 集合的并、交、差、補運算3.1.2 集合的環(huán)和與環(huán)積運算3.1.3 冪集與廣義并、交運算練習3.1 3.2 集合的笛卡兒積練習3.2 3.3 集合定義的自然數(shù)和歸納法證明3.3.1 集合定義的自然數(shù)3.3.2 歸納法證明練習3.3 3.4 閱讀材料：公理化集合論簡介[4]第4章 初等數(shù)論4.1 整除和素數(shù)4.1.1 整除4.1.2 最大公因子4.1.3 算術(shù)基本定理4.1.4 素數(shù)的性質(zhì)4.1.5 實數(shù)的取整[z]與取另{z)練習4.1 4.2 同余4.2.1 同余的基本性質(zhì)4.2.2 剩余系4.2.3 一次同余方程4.2.4 同余式組4.2.5 Euler定理和Fetmat小定理練習4.2 4.3 閱讀材料：數(shù)論在加密技術(shù)中的應(yīng)用4.3.1 仿射加密方法4.3.2 RSA加密方法4.3.3 數(shù)字簽名第5章 計數(shù)5.1 計數(shù)基本原理5.1.1 加法原理和乘法原理5.1.2 包含排斥原理練習5.1 5.2 排列與組合5.2.1 排列的計數(shù)5.2.2 組合的計數(shù)練習5.2 5.3 重集的排列與組合5.3.1 重集的排列5.3.2 重集的組合5.3.3 錯置的計數(shù)練習5.3 5.4 遞歸式及其應(yīng)用5.4.1 遞歸式建模5.4.2 遞歸式求解練習5.4 5.5 閱讀材料：母函數(shù)第6章 關(guān)系6.1 關(guān)系6.1.1 關(guān)系及二元關(guān)系6.1.2 關(guān)系基本運算6.1.3 關(guān)系數(shù)據(jù)庫中的關(guān)系運算6.1.4 關(guān)系的基本特性6.1.5 關(guān)系的特性閉包練習6.1 6.2 等價關(guān)系6.2.1 等價關(guān)系及其等價類6.2.2 等價關(guān)系與劃分6.2.3 等價關(guān)系的應(yīng)用練習6.2 6.3 序關(guān)系6.3.1 序關(guān)系和有序集6.3.2 全序集與良序集6.3.3 有序集的應(yīng)用練習6.3 6.4 閱讀材料：格第7章 函數(shù)7.1 函數(shù)及函數(shù)的合成7.1.1 函數(shù)基本概念7.1.2 函數(shù)的合成7.1.3 函數(shù)的遞歸定義練習7.1 7.2 特殊函數(shù)類7.2.1 單射、滿射和雙射7.2.2 函數(shù)的逆7.2.3 謂詞、集合、函數(shù)的統(tǒng)描述與模糊子集練習7.2 7.3 有限集和無限集7.3.1 有限集、可數(shù)集與不可數(shù)集7.3.2 無限集的特性練習7.3 7.4 閱讀材料：集合基數(shù)與基數(shù)比較第8章 可計算函數(shù)8.1 函數(shù)概念的拓廣練習8.1 8.2 初等函數(shù)8.2.1 初等函數(shù)集8.2.2 初等謂詞練習8.2 8.3 原始遞歸函數(shù)8.3.1 初等函數(shù)集的不足8.3.2 原始遞歸式8.3.3 原始遞歸函數(shù)集練習8.3 8.4 遞歸函數(shù)8.4.1 阿克曼函數(shù)及其性質(zhì)8.4.2 pc一遞歸式8.4.3 遞歸函數(shù)集(口一遞歸函數(shù)集)練習8.4 8.5 閱讀材料：圖靈機8.5.1 圖靈機的組成8.5.2 圖靈可計算函數(shù)第9章 圖與樹9.1 圖9.1.1 圖的基本概念9.1.2 結(jié)點的度9.1.3 子圖、補圖及圖同構(gòu)9.1.4 圖的應(yīng)用練習9.1 9.2 路徑、回路及連通性9.2.1 路徑、通路與回路9.2.2 連通性9.2.3 連通度練習9.2 9.3 圖的矩陣表示9.3.1 鄰接矩陣9.3.2 路徑矩陣與可達性矩陣練習9.3 9.4 樹9.4.1 樹的基本概念9.4.2 生成樹練習9.4 9.5 閱讀材料：圖搜索算法9.5.1 圖搜索算法(A算法)9.5.2 啟發(fā)式圖搜索算法(A算法)第10章 特殊圖10.1 歐拉圖與哈密頓圖10.1.1 歐拉圖及歐拉路徑10.1.2 哈密頓圖及哈密頓通路10.1.3 歐拉圖與哈密頓圖的應(yīng)用練習10.1 10.2 二分圖10.2.1 二分圖基本概念l0.2.2 二分圖的匹配及其應(yīng)用練習10.2 10.3 平面圖l0.3.1 F面圖基本概念10.3.2 歐拉公式和庫拉托夫斯基定理10.3.3 F面圖的應(yīng)用：著色問題練習10.3 10.4 根樹10.4.1 根樹的概念10.4.2 二元樹的性質(zhì)及應(yīng)用練習10.4 10.5 閱讀材料：博弈樹與智能博弈第11章 代數(shù)結(jié)構(gòu)通論11.1 代數(shù)結(jié)構(gòu)11.1.1 代數(shù)結(jié)構(gòu)的組成11.1.2 代數(shù)結(jié)構(gòu)的特殊元素11.1.3 子代數(shù)練習11.1 11.2 同態(tài)和同構(gòu)練習11.2 11.3 同余關(guān)系11.3.1 同余關(guān)系的意義11.3.2 同態(tài)與同余關(guān)系11.3.3 同余關(guān)系的應(yīng)用練習11.3 11.4 閱讀材料：正則語言及其代數(shù)性質(zhì)第12章 群、環(huán)、域12.1 半群12.1.I蘆群及獨異點12.1.2 自由獨異點練習12.1 12.2 群12.2.1 群及其基本性質(zhì)12.2.2 群的元素的階12.2.3 子群、陪集和拉格朗日定理12.2.4 iE規(guī)子群和商群練習12.2 12.3 循環(huán)群和置換群12.3.1 循環(huán)群12.3.2 置換群12.3.3 置換群的應(yīng)用練習12.3 12.4 環(huán)和域12.4.1 環(huán)12.4.2 域練習12.4 12.5 閱讀材料：有窮自動機12.5.1 有窮自動機12.5.2 狀態(tài)遷移幺半群12.5.3 語言同余關(guān)系參考文獻

章節(jié)摘錄

插圖：什么是離散數(shù)學？離散數(shù)學是研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學模型的數(shù)學分支的一個集成?！半x散”是“連續(xù)”的否定，即“不連續(xù)”；“連續(xù)”則是事物、數(shù)量的一種屬性，這種屬性使得它們?nèi)菀妆环指罨蚪Y(jié)合，并且不會因此而喪失它們原有的屬性。舉例來說，整數(shù)是離散的，實數(shù)則是連續(xù)的；馬鈴薯是離散的，馬鈴薯羹則是連續(xù)的。與初等數(shù)學和高等數(shù)學不同，離散數(shù)學處理的對象不再局限于連續(xù)的實數(shù)，而對離散的整數(shù)情有獨鐘，甚至不再局限于“數(shù)”，而是要面對任意對象所組成的離散結(jié)構(gòu)；離散數(shù)學關(guān)注的問題也不再局限于數(shù)的運算，而是任意對象的總體屬性以及它們之間的關(guān)系和運算。本章是閱讀全書的準備內(nèi)容，因此，首先要介紹各個章節(jié)公共的基礎(chǔ)——離散結(jié)構(gòu)的原始概念，包括集合、命題、謂詞、運算等；然后介紹在邏輯推理中常常涉及的最為簡單的一個數(shù)學原理——鴿籠原理。0.1 集合、命題、謂詞和運算0.1.1 集合集合（sets）是一個十分常用的基本概念。在中學的數(shù)學課程中，讀者對集合及其元素的意義已經(jīng)有所了解。集合是由確定的、互相區(qū)別的、并作整體識別的一些對象組成的總體。通常用{..·）表示一個集合，其中…是集合中的對象，對象間用逗號分開。確切地說這不是集合的定義，因為“總體”只是“集合”一詞的同義反復(fù)。實際上，集合是一個未作定義的原始概念（就像幾何學中的點、線、面等概念一樣）。不過，上述關(guān)于集合概念的描述，有益于對它的內(nèi)涵和外延作直觀的理解和認識。例0.1 （1）“北京大學全體學生”為一集合，組成這一集合的對象是北京大學的學生。（2）“全體正整數(shù)”為一集合，其組成對象是正整數(shù)。（3）“本書中所有漢字”的集合，其組成對象是本書中的不同漢字。（4）“獲1921年諾貝爾物理學獎的科學家”構(gòu)成一個集合，盡管它只有一個對象——愛因斯坦。

編輯推薦

《離散數(shù)學教程》：教育部高等理工教育教學改革與實踐項目研究成果

圖書封面

評論、評分、閱讀與下載

---

    離散數(shù)學教程 PDF格式下載

---