離散數(shù)學(xué) 第2版

前言

　　“離散”與“連續(xù)”是數(shù)量關(guān)系中一對(duì)極為深刻的矛盾，它們之間的對(duì)立與統(tǒng)一是數(shù)學(xué)發(fā)展的重要原動(dòng)力之一。“離散”是“連續(xù)”的否定，即“不連續(xù)”；而“連續(xù)”則是指事物、數(shù)量的一種屬性，這種屬性使它們?nèi)菀妆环指罨蚪Y(jié)合，并且不會(huì)因分割或結(jié)合而喪失它們?cè)械谋拘?。例如，?shí)數(shù)是連續(xù)的，整數(shù)則是離散的；二次函數(shù)是連續(xù)的，二次函數(shù)值的計(jì)算則是離散的。　　“離散數(shù)學(xué)”作為一門學(xué)科，其研究對(duì)象是離散數(shù)量關(guān)系以及離散系統(tǒng)結(jié)構(gòu)的數(shù)學(xué)模型及建模方法；而其作為一門課程，則是眾多離散數(shù)學(xué)分支的一個(gè)拼盤，包括集合論基礎(chǔ)、邏輯代數(shù)、圖論基礎(chǔ)、關(guān)系與函數(shù)、抽象代數(shù)學(xué)基礎(chǔ)和組合論基礎(chǔ)知識(shí)，以及形式系統(tǒng)、形式推理、可計(jì)算性的基礎(chǔ)理論。其內(nèi)容大致可以劃分為以下三個(gè)組成部分?！　∫弧㈦x散結(jié)構(gòu)的研究中所需的基本數(shù)學(xué)知識(shí)　　集合論基礎(chǔ)和兩個(gè)常用數(shù)學(xué)基本原理（第1、2章）?！　《⒀芯坑?jì)算機(jī)本身離散結(jié)構(gòu)的數(shù)學(xué)模型及數(shù)學(xué)方法　　1.作為計(jì)算機(jī)運(yùn)算基礎(chǔ)的邏輯代數(shù)（第4、5章）。　　2.作為計(jì)算機(jī)表示基礎(chǔ)的形式化、形式系統(tǒng)技術(shù)（第6章）?！　?.作為計(jì)算機(jī)科學(xué)中“力學(xué)”的、討論計(jì)算能力的可計(jì)算性理論（第11章）?！　∪?、研究計(jì)算機(jī)應(yīng)用對(duì)象的離散結(jié)構(gòu)的數(shù)學(xué)模型及建模方法　　1.離散結(jié)構(gòu)的計(jì)數(shù)模型及遞歸關(guān)系模型（第3章）。　　2.離散結(jié)構(gòu)的圖模型（第7、8章）?！　?.離散結(jié)構(gòu)的一般關(guān)系模型及函數(shù)模型（第9、10章）?！　?.離散結(jié)構(gòu)的抽象代數(shù)模型（第12—14章）?！　〔浑y看出，本書(shū)完全覆蓋了經(jīng)典的“離散結(jié)構(gòu)”或“離散數(shù)學(xué)”課程的主要內(nèi)容，既適合于對(duì)離散數(shù)學(xué)課程的教學(xué)內(nèi)容有全面要求的院校，又可通過(guò)適當(dāng)選材，有針對(duì)性地分別用于注重計(jì)算機(jī)科學(xué)理論的或強(qiáng)調(diào)計(jì)算機(jī)應(yīng)用技術(shù)的學(xué)科專業(yè)。因而，本書(shū)可作為高等院校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)及計(jì)算機(jī)軟件學(xué)院本科生、?？粕碾x散數(shù)學(xué)課程的教材，以及畢業(yè)生考研復(fù)習(xí)用書(shū)，也可作為計(jì)算機(jī)教育工作者、研究開(kāi)發(fā)技術(shù)人員的參考讀物?！　”緯?shū)包含了大約100個(gè)學(xué)時(shí)的內(nèi)容；如果全部或部分刪除標(biāo)記*的內(nèi)容，則完成教學(xué)計(jì)劃的學(xué)時(shí)數(shù)可控制在80學(xué)時(shí)左右；如果根據(jù)學(xué)校的具體情況，按照以下兩種思路來(lái)篩選素材（參見(jiàn)下頁(yè)圖表），則可以將課時(shí)控制在70～80學(xué)時(shí)。

內(nèi)容概要

　　《離散數(shù)學(xué)（第2版）》是機(jī)械工業(yè)出版社2004年出版的《計(jì)算機(jī)科學(xué)中的離散結(jié)構(gòu)》的新版教材?！峨x散數(shù)學(xué)（第2版）》涵蓋了經(jīng)典“離散結(jié)構(gòu)”或“離散數(shù)學(xué)”課程的主要內(nèi)容，包括集合論基礎(chǔ)、邏輯代數(shù)、圖論基礎(chǔ)、關(guān)系與函數(shù)、抽象代數(shù)學(xué)基礎(chǔ)，并適度擴(kuò)充了計(jì)算機(jī)科學(xué)中常用的組合論基礎(chǔ)知識(shí)，以及形式系統(tǒng)、形式推理、可計(jì)算性的基礎(chǔ)理論?！　　峨x散數(shù)學(xué)（第2版）》內(nèi)容既適合于對(duì)“離散數(shù)學(xué)”課程的教學(xué)內(nèi)容有全面要求的院校，又可通過(guò)適當(dāng)選材，有針對(duì)性地分別用于注重計(jì)算機(jī)科學(xué)理論或強(qiáng)調(diào)計(jì)算機(jī)應(yīng)用技術(shù)的學(xué)科專業(yè)，具有內(nèi)容系統(tǒng)全面、闡述淺顯易懂、編排合理新穎、習(xí)題編配豐富、使用靈活方便的特點(diǎn)?！　　峨x散數(shù)學(xué)（第2版）》可作為高等院校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)及計(jì)算機(jī)軟件學(xué)院本科生、?？粕摹半x散數(shù)學(xué)”課程的教材，以及畢業(yè)生考研復(fù)習(xí)用書(shū)，也可作為計(jì)算機(jī)教育工作者、研究開(kāi)發(fā)技術(shù)人員的參考讀物。

書(shū)籍目錄

出版說(shuō)明前言第1章 集合代數(shù)1.1 集合的概念與表示1.1.1 集合及其元素1.1.2 集合的表示1.1.3 外延性公理與子集合練習(xí)1.11.2 集合運(yùn)算1.2.1 并、交、差、補(bǔ)運(yùn)算1.2.2 冪集運(yùn)算和廣義并、交運(yùn)算1.2.3 集合的笛卡兒積練習(xí)1.21.3 集合的歸納定義的意義1.3.1 集合的歸納定義1.3.2 集合定義的自然數(shù)練習(xí)1.3第2章 兩個(gè)常用數(shù)學(xué)基本原理2.1 歸納原理2.1.1 結(jié)構(gòu)歸納原理2.1.2 數(shù)學(xué)歸納原理練習(xí)2.12.2 鴿籠原理2.2.1 鴿籠原理的基本形式2.2.2 鴿籠原理的加強(qiáng)形式練習(xí)2.2第3章 組合論基礎(chǔ)計(jì)數(shù)3.1 計(jì)數(shù)基本原理3.1.1 加法原理和乘法原理3.1.2 包含排斥原理練習(xí)3.13.2 排列與組合3.2.1 排列的計(jì)數(shù)3.2.2 組合的計(jì)數(shù)練習(xí)3.23.3 重集的排列與組合3.3.1 重集的排列3.3.2 重集的組合3.3.3 禁位排列的計(jì)數(shù)練習(xí)3.33.4 遞歸關(guān)系3.4.1 一個(gè)重要的遞歸關(guān)系3.4.2 遞歸關(guān)系的求解練習(xí)3.4第4章 邏輯代數(shù)（上）：命題演算4.1 命題與邏輯聯(lián)結(jié)詞4.1.1 命題4.1.2 邏輯聯(lián)結(jié)詞4.1.3 命題公式4.1.4 語(yǔ)句的形式化練習(xí)4.14.2 邏輯等價(jià)式和邏輯蘊(yùn)涵式4.2.1 重言式4.2.2 邏輯等價(jià)式和邏輯蘊(yùn)涵式4.2.3 對(duì)偶原理練習(xí)4.24.3 范式4.3.1 析取范式和合取范式4.3.2 主析取范式與主合取范式4.3.3 聯(lián)結(jié)詞的擴(kuò)充與歸約練習(xí)4.3 第5章 邏輯代數(shù)（下）：謂詞演算5.1 謂詞演算基本概念5.1.1 個(gè)體與個(gè)體域5.1.2 謂詞與謂詞填式5.1.3 量詞及其轄域5.1.4 謂詞公式及語(yǔ)句的形式化練習(xí)5.15.2 謂詞演算永真式5.2.1 謂詞公式的真值規(guī)定5.2.2 謂詞演算永真式5.2.3 關(guān)于永真式的幾個(gè)基本原理練習(xí)5.25.3 謂詞公式的前束范式練習(xí)5.3第6章 形式系統(tǒng)與推理技術(shù)6.1 謂詞演算形式系統(tǒng)FC6.1.1 FC的基本構(gòu)成6.1.2 系統(tǒng)內(nèi)的推理：證明與演繹6.1.3 FC的重要性質(zhì)練習(xí)6.16.2 自然推理形式系統(tǒng)ND6.2.1 ND的基本構(gòu)成6.2.2 ND的系統(tǒng)內(nèi)推理及性質(zhì)練習(xí)6.2第7章 圖7.1 圖的基礎(chǔ)知識(shí)7.1.1 圖的基本概念7.1.2 結(jié)點(diǎn)的度7.1.3 子圖、補(bǔ)圖及圖同構(gòu)練習(xí)7.17.2 路徑、回路及連通性7.2.1 路徑與回路7.2.2 連通性7.2.3 連通度練習(xí)7.27.3 歐拉圖與哈密頓圖7.3.1 歐拉圖及歐拉路徑7.3.2 哈密頓圖及哈密頓通路練習(xí)7.37.4 圖的矩陣表示7.4.1 鄰接矩陣7.4.2 路徑矩陣與可達(dá)性矩陣練習(xí)7.4第8章 二分圖、平面圖和樹(shù)8.1 二分圖8.1.1 二分圖的基本概念8.1.2 匹配練習(xí)8.18.2 平面圖8.2.1 平面圖的基本概念8.2.2 歐拉公式和庫(kù)拉托夫斯基定理8.2.3 著色問(wèn)題練習(xí)8.28.3 樹(shù)8.3.1 樹(shù)的基本概念8.3.2 生成樹(shù)8.3.3 根樹(shù)練習(xí)8.3第9章 關(guān)系9.1 關(guān)系9.1.1 關(guān)系的基本概念9.1.2 關(guān)系的基本運(yùn)算9.1.3 關(guān)系的基本特性9.1.4 關(guān)系特性閉包練習(xí)9.19.2 等價(jià)關(guān)系9.2.1 等價(jià)關(guān)系與等價(jià)類9.2.2 等價(jià)關(guān)系與劃分練習(xí)9.29.3 序關(guān)系9.3.1 序關(guān)系和有序集9.3.2 良基性與良序集，完備序集9.3.3 全序集與良序集的構(gòu)造練習(xí)9.3第10章 函數(shù)10.1 函數(shù)及函數(shù)的合成10.1.1 函數(shù)的基本概念10.1.2 函數(shù)概念的拓廣10.1.3 函數(shù)的合成10.1.4 函數(shù)的遞歸定義練習(xí)10.110.2 特殊函數(shù)類10.2.1 單射的、滿射的和雙射的函數(shù)10.2.2 規(guī)范映射、單調(diào)映射和連續(xù)映射練習(xí)10.210.3 函數(shù)的逆練習(xí)10.3 10.4 有限集和無(wú)限集10.4.1 有限集、可數(shù)集與不可數(shù)集10.4.2 無(wú)限集的特性10.4.3 有限集和無(wú)限集的基數(shù)10.4.4 基數(shù)比較練習(xí)10.4第11章 遞歸函數(shù)集與可計(jì)算性11.1 初等函數(shù)集11.1.1 初等函數(shù)11.1.2 初等謂詞練習(xí)11.111.2 原始遞歸函數(shù)集11.2.1 初等函數(shù)集的不足11.2.2 原始遞歸式11.2.3 原始遞歸函數(shù)練習(xí)11.211.3 遞歸函數(shù)集11.3.1 阿克曼函數(shù)及其性質(zhì)11.3.2 μ-遞歸式11.3.3 遞歸函數(shù)集(μ-遞歸函數(shù)集)練習(xí)11.3 11.4 圖靈機(jī)與可計(jì)算函數(shù)集11.4.1 圖靈機(jī)11.4.2 圖靈可計(jì)算函數(shù)練習(xí)11.4第12章 代數(shù)結(jié)構(gòu)概論12.1 代數(shù)結(jié)構(gòu)12.1.1 代數(shù)結(jié)構(gòu)的意義12.1.2 代數(shù)結(jié)構(gòu)的特殊元素12.1.3 子代數(shù)結(jié)構(gòu)練習(xí)12.112.2 同態(tài)、同構(gòu)及同余12.2.1 同態(tài)與同構(gòu)12.2.2 同余關(guān)系練習(xí)12.212.3 商代數(shù)練習(xí)12.3第13章 群、環(huán)、域13.1 半群13.1.1 半群及獨(dú)異點(diǎn)13.1.2 自由獨(dú)異點(diǎn)13.1.3 高斯半群練習(xí)13.113.2 群13.2.1 群及其基本性質(zhì)13.2.2 子群、陪集和拉格朗日定理13.2.3 正規(guī)子群、商群和同態(tài)基本定理練習(xí)13.213.3 循環(huán)群和置換群13.3.1 循環(huán)群13.3.2 置換群練習(xí)13.313.4 環(huán)13.4.1 環(huán)和整環(huán)13.4.2 子環(huán)和理想練習(xí)13.413.5 域和有限域練習(xí)13.5第14章 格與布爾代數(shù)14.1 格14.1.1 格——有序集14.1.2 格代數(shù)14.1.3 分配格和模格練習(xí)14.114.2 布爾代數(shù)14.2.1 有界格和有補(bǔ)格14.2.2 布爾代數(shù)14.2.3 布爾代數(shù)表示定理14.2.4 布爾表達(dá)式與布爾函數(shù)練習(xí)14.2參考文獻(xiàn)

圖書(shū)封面

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

---

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

---