《離散數(shù)學》是復旦大學離散數(shù)學教材。全書介紹離散數(shù)學中的5個部分,即集合論、組合數(shù)學、圖論、代數(shù)結(jié)構(gòu)和數(shù)理邏輯的初步知識。在內(nèi)容組織上,不但介紹基本內(nèi)容、基本概念及其實際背景、各概念間的相互關系,而且強化了證明的思想和方法。
《離散數(shù)學》可作為高等院校計算機科學與技術(shù)、軟件工程等專業(yè)的離散數(shù)學課程教材,也可以作為該課程的教學參考書。
目錄
�、窦险摳攀� 第1章 集合的基本概念 1.1 集合的表示 1.2 集合的子集 1.3 笛卡兒積 1.4 集合的運算 1.5 羅素悖論 習題 第2章 關系 2.1 二元關系 2.2 關系的性質(zhì) 2.3 關系的運算 2.4 關系數(shù)據(jù)庫的一個實例 2.5 關系的閉包 2.6 等價關系與劃分 2.7 次序關系 習題 第3章 函數(shù) 3.1 函數(shù)的基本概念 3.2 逆函數(shù)與復合函數(shù) 3.3 集合的特征函數(shù) 習題 第4章 無限集 4.1 集合的遞歸定義與自然數(shù)集合 4.2 基數(shù) 4.3 可列集與不可列集 4.4 基數(shù)的比較 習題 Ⅱ 組合數(shù)學初步 第5章 鴿籠原理 5.1 鴿籠原理的簡單形式 5.2 鴿籠原理的加強形式 習題 第6章 排列與組合 6.1 基本計數(shù)原理 6.2 集合的排列 6.3 集合元素的組合 6.4 多重集的排列和組合 6.5 容斥原理 習題 第7章 生成函數(shù)與遞推關系 7.1 冪級數(shù)型生成函數(shù) 7.2 指數(shù)型生成函數(shù) 7.3 遞推關系 習題 Ⅲ 圖論 第8章 圖的基本概念 8.1 引言 8.2 路與回路 8.3 歐拉圖 8.4 哈密頓圖 8.5 最短路 8.6 圖論模型初步 習題 第9章 平面圖與圖的著色 9.1 平面圖與歐拉公式 9.2 頂點著色 9.3 平面圖的著色 9.4 邊的著色 習題 第10章 樹 10.1 樹及其性質(zhì) 10.2 生成樹與割集 10.3 最小生成樹 10.4 樹的計數(shù) 10.5 有根樹與二分樹 10.6 最優(yōu)樹 習題 第11章 連通度、網(wǎng)絡、匹配與Petri網(wǎng) 11.1 連通度與塊 11.2 網(wǎng)絡最大流 11.3 二分圖的匹配 11.4 獨立集、覆蓋 11.5 Petri網(wǎng) 習題 Ⅳ 代數(shù)結(jié)構(gòu) 第12章 代數(shù)結(jié)構(gòu)預備知識 12.1 代數(shù)系統(tǒng) 12.2 同態(tài)、同構(gòu)與商系統(tǒng) 12.3 代數(shù)系統(tǒng)[Z;+,·] 習題 第13章 群 13.1 半群、擬群與群 13.2 變換群、置換群與循環(huán)群 13.3 子群、正規(guī)子群與商群 13.4 群的同態(tài)與同態(tài)基本定理 習題 第14章 環(huán) 14.1 環(huán)的定義與性質(zhì) 14.2 子環(huán)與環(huán)同態(tài) 14.3 多項式環(huán) 14.4 理想與商環(huán) 14.5 整環(huán)與分式域 習題 第15章 域 15.1 擴域 15.2 代數(shù)元與根域 15.3 有限域 15.4 本原元與本原多項式 習題 第16章 格與布爾代數(shù) 16.1 偏序與格 16.2 有補格及分配格 16.3 布爾格與布爾代數(shù) 習題 Ⅴ 數(shù)理邏輯 第17章 數(shù)理邏輯預備知識 17.1 命題和聯(lián)結(jié)詞 17.2 泛代數(shù) 習題 第18章 命題邏輯 18.1 命題代數(shù) 18.2 命題演算的語義 18.3 命題演算的形式 18.4 一般邏輯系統(tǒng) 18.5 命題演算的性質(zhì) 習題 第19章 謂詞邏輯 19.1 謂詞代數(shù) 19.2 謂詞公式語義解釋 19.3 謂詞演算的形式證明 19.4 前束范式 19.5 謂詞演算的性質(zhì) 習題 參考文獻
�、窦险摳攀� 第1章 集合的基本概念 1.1 集合的表示 1.2 集合的子集 1.3 笛卡兒積 1.4 集合的運算 1.5 羅素悖論 習題 第2章 關系 2.1 二元關系 2.2 關系的性質(zhì) 2.3 關系的運算 2.4 關系數(shù)據(jù)庫的一個實例 2.5 關系的閉包 2.6 等價關系與劃分 2.7 次序關系 習題 第3章 函數(shù) 3.1 函數(shù)的基本概念 3.2 逆函數(shù)與復合函數(shù) 3.3 集合的特征函數(shù) 習題 第4章 無限集 4.1 集合的遞歸定義與自然數(shù)集合 4.2 基數(shù) 4.3 可列集與不可列集 4.4 基數(shù)的比較 習題 Ⅱ 組合數(shù)學初步 第5章 鴿籠原理 5.1 鴿籠原理的簡單形式 5.2 鴿籠原理的加強形式 習題 第6章 排列與組合 6.1 基本計數(shù)原理 6.2 集合的排列 6.3 集合元素的組合 6.4 多重集的排列和組合 6.5 容斥原理 習題 第7章 生成函數(shù)與遞推關系 7.1 冪級數(shù)型生成函數(shù) 7.2 指數(shù)型生成函數(shù) 7.3 遞推關系 習題 Ⅲ 圖論 第8章 圖的基本概念 8.1 引言 8.2 路與回路 8.3 歐拉圖 8.4 哈密頓圖 8.5 最短路 8.6 圖論模型初步 習題 第9章 平面圖與圖的著色 9.1 平面圖與歐拉公式 9.2 頂點著色 9.3 平面圖的著色 9.4 邊的著色 習題 第10章 樹 10.1 樹及其性質(zhì) 10.2 生成樹與割集 10.3 最小生成樹 10.4 樹的計數(shù) 10.5 有根樹與二分樹 10.6 最優(yōu)樹 習題 第11章 連通度、網(wǎng)絡、匹配與Petri網(wǎng) 11.1 連通度與塊 11.2 網(wǎng)絡最大流 11.3 二分圖的匹配 11.4 獨立集、覆蓋 11.5 Petri網(wǎng) 習題 Ⅳ 代數(shù)結(jié)構(gòu) 第12章 代數(shù)結(jié)構(gòu)預備知識 12.1 代數(shù)系統(tǒng) 12.2 同態(tài)、同構(gòu)與商系統(tǒng) 12.3 代數(shù)系統(tǒng)[Z;+,·] 習題 第13章 群 13.1 半群、擬群與群 13.2 變換群、置換群與循環(huán)群 13.3 子群、正規(guī)子群與商群 13.4 群的同態(tài)與同態(tài)基本定理 習題 第14章 環(huán) 14.1 環(huán)的定義與性質(zhì) 14.2 子環(huán)與環(huán)同態(tài) 14.3 多項式環(huán) 14.4 理想與商環(huán) 14.5 整環(huán)與分式域 習題 第15章 域 15.1 擴域 15.2 代數(shù)元與根域 15.3 有限域 15.4 本原元與本原多項式 習題 第16章 格與布爾代數(shù) 16.1 偏序與格 16.2 有補格及分配格 16.3 布爾格與布爾代數(shù) 習題 Ⅴ 數(shù)理邏輯 第17章 數(shù)理邏輯預備知識 17.1 命題和聯(lián)結(jié)詞 17.2 泛代數(shù) 習題 第18章 命題邏輯 18.1 命題代數(shù) 18.2 命題演算的語義 18.3 命題演算的形式 18.4 一般邏輯系統(tǒng) 18.5 命題演算的性質(zhì) 習題 第19章 謂詞邏輯 19.1 謂詞代數(shù) 19.2 謂詞公式語義解釋 19.3 謂詞演算的形式證明 19.4 前束范式 19.5 謂詞演算的性質(zhì) 習題 參考文獻
|
