離散數(shù)學

前言

　　現(xiàn)代社會與計算機日益密切地融合，而數(shù)字計算機本質(zhì)上是一種“離散”的機器，并越來越多地用于處理離散的對象，從而使“離散數(shù)學”成為計算機科學不可或缺的理論基礎(chǔ)和工具，并推動離散數(shù)學本身進一步發(fā)展和豐富。作為計算機專業(yè)最重要的必修課程之一，近年來離散數(shù)學越來越受到重視，它不僅是學習后繼課程的基礎(chǔ)，更是培養(yǎng)學生的思維、提高分析問題和解決問題的能力的重要途徑。　　本書第一版成書于1985年，11年后，為了適應(yīng)計算機學科的迅速發(fā)展作了一次修訂。如今，距第二版成書又過去了13年。期間，不僅計算機學科本身又有了許多重大進展，而且目前的社會環(huán)境、高校和學生的情況都與以往大不一樣。正是基于這樣的背景，我們對第二版再次作了全面修訂，以適應(yīng)學科的發(fā)展和教學的需要?！　〉谌娴膬?nèi)容組織主要依據(jù)教育部計算機科學與技術(shù)專業(yè)教學指導分委員會制定的《高等學校計算機科學與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范》，并參考了美國計算機學會ACM的Computing Curricula 2005。與第二版相比較，第三版的涵蓋面有所擴大，增加了初等數(shù)論、組合數(shù)學等方面的內(nèi)容；與計算機科學的結(jié)合更緊密，增加了離散數(shù)學應(yīng)用的內(nèi)容；壓縮了某些較抽象、實際應(yīng)用中較少涉及的內(nèi)容，如集合的基數(shù)等?！　”緯皟砂娴娘@著特點是：簡潔、條理清晰。第三版在保持這兩個特點的基礎(chǔ)上，把離散數(shù)學與計算機科學有機地聯(lián)系起來，力圖將本教材編寫成“面向計算機科學的”離散數(shù)學。一方面加強學生對基本內(nèi)容的掌握，培養(yǎng)分析問題和解決問題的能力；另一方面，進一步激發(fā)學生的學習興趣。此外，第三版對學生的實際情況也作了充分考慮，對難點和重點的討論盡可能地做到直觀、循序漸進、詳盡，并適當?shù)刈髁艘恍W習指導?！　〉谌姘膬?nèi)容較多，一般需要兩個學期才能全部覆蓋。教師可根據(jù)具體的專業(yè)方向、教學目標、學生的情況等進行適當組合。本書在內(nèi)容的組織上已經(jīng)充分考慮到這樣的需要，盡可能地保持各章節(jié)內(nèi)容的自含，以便于取舍。

內(nèi)容概要

　　《離散數(shù)學（第3版）》前兩版的顯著特點是：簡潔、條理清晰。第三版在保持這兩個特點的基礎(chǔ)上，把離散數(shù)學與計算機科學有機地聯(lián)系起來，力圖將本教材編寫成“面向計算機科學的”離散數(shù)學。一方面加強學生對基本內(nèi)容的掌握，培養(yǎng)分析問題和解決問題的能力；另一方面，進一步激發(fā)學生的學習興趣。此外，第三版對學生的實際情況也作了充分考慮，對難點和重點的討論盡可能地做到直觀、循序漸進、詳盡，并適當?shù)刈髁艘恍W習指導。

書籍目錄

第一章 集合論1.1 集合的概念和術(shù)語1.1.1 集合的基本概念和表示1.1.2 集合之間的關(guān)系1.1.3 集合簇1.2 集合的運算1.2.1 集合的基本運算1.2.2 冪集1.2.3 n元組和笛卡兒乘積1.2.4廣義并和廣義交1.3 集合運算的性質(zhì)1.3.1 集合恒等式1.3.2 集合演算1.3.3 對偶原理1.4 有限集合的計數(shù)1.5 羅素悖論1.6 小結(jié)1.7 習題第二章 數(shù)論基礎(chǔ)2.1 最大公因數(shù)和最小公倍數(shù)2.1.1 整除、同余、最大公因數(shù)和最小公倍數(shù)2.1.2 歐幾里得算法2.1.3 最大公因數(shù)和最小公倍數(shù)的性質(zhì)2.2 素數(shù)2.2.1 整數(shù)的素分解2.2.2 素性探測2.3 一次同余方程2.3.1 一次同余方程2.3.2 一次同余方程組2.3 3 大整數(shù)的剩余表示法2.4 RSA公鑰密碼體制2.5 小結(jié)2.6 習題第三章 命題邏輯3.1 命題和命題公式3.1.1 命題與邏輯聯(lián)結(jié)詞3.1.2 命題公式3.2 等值演算3.2.1 等值的概念3.2.2 等值演算3.2.3 對偶原理3.3 范式3.3.1 主析取范式3.3.2 主合取范式3.3.3 聯(lián)結(jié)詞的功能完備集3.4 命題邏輯的推理理論3.5 小結(jié)3.6 習題第四章 一階邏輯4.1 謂詞4.1.1 謂詞和量詞4.1.2 謂詞公式4.2 等值演算和前束范式4.3 一階邏輯的推理理論4.4 小結(jié)4.5 習題第五章 關(guān)系5.1 關(guān)系的概念5.1.1 二元關(guān)系5.1.2 二元關(guān)系的表示5.1.3 n元關(guān)系5.2 關(guān)系運算5.2.1 關(guān)系的基本運算5.2.2 關(guān)系運算的性質(zhì)5.3 關(guān)系的特殊性質(zhì)及其閉包5.3.1 關(guān)系的特殊性質(zhì)5.3.2 關(guān)系的閉包5.4 等價關(guān)系和劃分5.4.1 等價關(guān)系和等價類5.4.2 劃分和等價關(guān)系5.5 偏序關(guān)系5.5.1 偏序關(guān)系和偏序集5.5.2 哈斯圖5.5.3 偏序集的性質(zhì)5.5.4 拓撲序列5.5.5 格5.6 小結(jié)5.7 習題第六章 函數(shù)和集合的基數(shù)6.1 函數(shù)的概念和性質(zhì)6.1.1 函數(shù)的基本概念6.1.2 函數(shù)的復合和逆6.2 集合的基數(shù)6.2.1 集合的等勢6.2.2 可數(shù)集6.2.3 無限集和集合的基數(shù)6.3 不可解問題6.3.1 不可解問題的存在性6.3.2 停機問題6.4 小結(jié)6.5 習題第七章 圖論基礎(chǔ)7.1 圖及其表示7.1.1 圖的概念7.1.2 圖的矩陣表示7.1.3 幾種特殊的圖7.1.4 子圖和圖運算7.2 握手定理7.3 圖的連通性7.3.1 通路和回路7.3.2 圖的連通性7.3.3 矩陣運算和連通性7.4 最短通路和Dijkstra算法7.4.1 廣度優(yōu)先搜索算法7.4.2 帶權(quán)圖和Dijkstra算法7.5 頂點著色7.6 圖同構(gòu)7.7 小結(jié)7.8 習題第八章 具有特殊性質(zhì)的圖8.1 歐拉圖8.1.1 歐拉圖的概念8.1.2 無向歐拉圖的性質(zhì)8.1.3 有向歐拉圖的性質(zhì)8.2 哈密頓圖8.2.1 哈密頓圖的概念8.2.2 無向哈密頓圖的性質(zhì)8.2.3 格雷碼8.2.4 競賽圖8.3 平面圖8.3.1 平面圖的概念8.3.2 平面圖的性質(zhì)8.4 無向樹8.4.1 無向樹的概念8.4.2 無向樹的基本性質(zhì)8.4.3 求最小生成樹的Kruskal算法8.5 有向樹8.5.1 有向樹和根樹及其簡單性質(zhì)8.5.2 求最優(yōu)樹的Huffman算法8.6 小結(jié)8.7 習題第九章 基本計數(shù)方法9.1 鴿籠原理9.2 加法原理與乘法原理9.3 排列與組合9.3.1 排列9.3.2 組合9.4 二項式系數(shù)9.5 可重復的排列和組合9.5.1 可重復的排列9.5.2 可重復的組合9.6 容斥原理9.7 生成排列和組合9.7.1 生成排列9.7.2 生成組合9.9 習題第十章 遞推關(guān)系和生成函數(shù)10.1 遞推關(guān)系10.2 常系數(shù)線性遞推關(guān)系10.2.1 求解常系數(shù)線性齊次遞推關(guān)系10.2.2 求解常系數(shù)線性非齊次遞推關(guān)系10.3 生成函數(shù)10.3.1 冪級數(shù)型生成函數(shù)10.3.2 指數(shù)型生成函數(shù)10.4 生成函數(shù)應(yīng)用舉例10.5 小結(jié)10.6 習題第十一章 代數(shù)結(jié)構(gòu)基礎(chǔ)11.1 代數(shù)系統(tǒng)11.2 二元運算的性質(zhì)11.3 半群和獨異點11.4 同態(tài)和同構(gòu)11.5 小結(jié)11.6 習題第十二章 群12.1 群12.2 子群12.2.1 子群12.2.2 元素的階12.3 循環(huán)群和群的直積12.3.1 循環(huán)群12.3.2 群的直積12.4 陪集和正規(guī)子群12.5 群同態(tài)12.6 變換群和置換群12.7 群碼12.7.1 糾錯碼的基本概念12.7.2 線性碼的生成矩陣與校驗矩陣12.7.3 群碼12.8 小結(jié)12.9 習題第十三章 環(huán)和域13.1 環(huán)13.1.1 環(huán)的定義13.1.2 特殊元素和性質(zhì)13.1.3 環(huán)的分類13.2 子環(huán)、理想和商環(huán)13.2.1 子環(huán)和理想13.2.2 商環(huán)13.3 環(huán)同態(tài)13.4 一元多項式環(huán)與多項式編碼13.4. 1域上的一元多項式13.4.2 一元多項式環(huán)的主理想13.4.3多項式編碼13.5 域13.5.1 域的基本概念和簡單性質(zhì)13.5.2 有限域13.5.3 擴域的性質(zhì)和幾何作圖問題13.6 小結(jié)13.7 習題第十四章 格和布爾代數(shù)14.1 格14.1.1 偏序格14.1.2 代數(shù)格14.2 有界格、有補格和分配格14.3 布爾代數(shù)14.3.1 布爾格和布爾代數(shù)14.3.2 有限布爾代數(shù)14.3.3 對偶原理14.4 小結(jié)14.5 習題參考文獻

章節(jié)摘錄

　　第一章　集合論　　集合是數(shù)學的基本概念，很多數(shù)學家都認為，所有的數(shù)學都可以用集合論的術(shù)語來表示。集合論的起源可以追溯到16世紀末，但它的創(chuàng)立是在19世紀末由德國數(shù)學家康托爾（G.Cantor）完成的。最初，為了建立微積分學的嚴格的理論基礎(chǔ)，人們對數(shù)集進行了研究，直到l876～1883年，康托爾對任意元素的集合進行了系統(tǒng)的研究，提出了基數(shù)、序數(shù)和良序集等理論，從而奠定了集合論的基礎(chǔ)。這樣的集合論基于直觀的集合概念，稱為樸素集合論。l900年前后，由于各種悖論的發(fā)現(xiàn)，特別是1901年羅素（B.Russell）悖論的發(fā)現(xiàn)，使集合論的發(fā)展一度受阻。l908年，策墨羅（E.Zermelo）提出了第一個集合論的公理系統(tǒng)，使數(shù)學哲學中產(chǎn)生的一些矛盾基本上得到統(tǒng)一。在此基礎(chǔ)上，集合論與邏輯學相互融合并迅速發(fā)展，逐步形成了各種公理集合論?，F(xiàn)在，集合論不僅作為一門純數(shù)學成為數(shù)理邏輯的一個主要分支，而且作為精確、嚴謹而又簡便的語言，已經(jīng)滲透到現(xiàn)代數(shù)學的各個領(lǐng)域，成為整個數(shù)學的基礎(chǔ)?！　∮嬎銠C科學對集合論感興趣，是因為它在計算機科學中被廣泛地應(yīng)用，是建立數(shù)學模型以及進行深入探討的有力工具。比如，在形式語言、編譯理論、信息檢索、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計、算法分析、數(shù)據(jù)庫、有限自動機、人工智能等等許多領(lǐng)域中，集合論都是不可缺少的理論工具，起著重要的作用?！　”緯鴥H限于討論樸素集合論。本章介紹集合的基礎(chǔ)知識，主要包括集合的概念、集合運算及其基本性質(zhì)、n元組和笛卡兒乘積等等，這些基本概念是離散數(shù)學的基礎(chǔ)，將貫穿整個課程。集合論的其他重要內(nèi)容，如關(guān)系、函數(shù)、基數(shù)等等，將在第五章和第六章中講述。　　……

圖書封面

評論、評分、閱讀與下載

---

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

---