●章 數學語言與證明方法
1.1 常用的數學符號
1.1.1 集合符號
1.1.2 運算符號
1.1.3 邏輯符號
1.2 集合及其運算
1.2.1 集合及其表示法
1.2.2 集合之間的包含與相等
1.2.3 集合的冪集
1.2.4 集合的運算
1.2.5 基本集合恆等式及其應用
1.3 證明方法概述
1.3.1 直接證明法和歸謬法
1.3.2 分情況證明法和構造性證明法
1.3.3 數學歸納法
1.4 遞歸定義
習題
第2章 命題邏輯
2.1 命題邏輯基本概念
2.1.1 命題與聯結詞
2.1.2 命題公式及其分類
2.2 命題邏輯等值演算
2.2.1 等值式與等值演算
2.2.2 聯結詞完備集
2.3 範式
2.3.1 析取範式與合取範式
2.3.2 主析取範式與主合取範式
2.4 推理
2.4.1 推理的形式結構
2.4.2 推理的證明.
2.4.3 歸結證明法
2.4.4 對證明方法的補充說明
習題
第3章 一階邏輯
3.1 一階邏輯基本概念
3.1.1 命題邏輯的局限性
3.1.2 個體詞、謂詞與量詞
3.1.3 一階邏輯命題符號化
3.1.4 一階邏輯公式與分類
3.2 一階邏輯等值演算
3.2.1 一階邏輯等值式與置換規則
3.2.2 一階邏輯前束範式
習題
第4章 關繫
4.1 關繫的定義及其表示
4.1.1 有序對與笛卡兒積
4.1.關繫的定義
4.1.關繫的表示
4.2 關繫的運算
4.2.1 關繫的基本運算
4.2.2 關繫的冪運算
4.3 關繫的性質
4.3.1 關繫性質的定義和判別
4.3.2 關繫的閉包
4.4 等價關繫與偏序關繫
4.4.1 等價關繫
4.4.2 等價類和商集
4.4.3 集合的劃分
4.4.4 偏序關繫
4.4.5 偏序集與哈斯圖
習題
第5章 函數
5.1 函數的定義及其性質
5.1.1 函數的定義
5.1.2 函數的像與完全原像
5.1.3 函數的性質
5.2 函數的復合與反函數
5.2.1 函數的復合
5.2.2 反函數
習題
第6章 圖
6.1 圖的基本概念
6.1.1 無向圖與有向圖
6.1.2 頂點的度數與握手定理
6.1.3 簡單圖、完全圖、正則圖、圈圖、輪圖、方體圖
6.1.4 子圖、補圖
6.1.5 圖的同構
6.2 圖的連通性
6.2.1 通路與回路
6.2.2 無向圖的連通性與連通度
6.2.3 有向圖的連通性及其分類
6.3 圖的矩陣表示
6.3.1 無向圖的關聯矩陣
6.3.2 有向無環圖的關聯矩陣
6.3.3 有向圖的鄰接矩陣
6.3.4 有向圖的可達矩陣
6.4 幾種特殊的圖
6.4.1 二部圖
6.4.2 歐拉圖
6.4.3 哈密頓圖
6.4.4 平面圖
習題
第7章 樹及其應用
7.1 無向樹
7.1.1 無向樹的定義及其性質
7.1.2 生成樹
7.2 根樹及其應用
7.2.1 根樹及其分類
7.2.2 最優樹與哈夫曼算法
7.2.3 最佳前綴碼
7.2.4 根樹的周遊及其應用
習題
第8章 組合計數基礎
8.1 基本計數規則
8.1.1 加法法則
8.1.2 乘法法則
8.1.3 分類處理與分步處理
8.2 排列與組合
8.2.1 集合的排列與組合
8.2.2 多重集的排列與組合
8.3 二項式定理與組合恆等式
8.3.1 二項式定理
8.3.2 組合恆等式
8.3.3 非降路徑問題
8.4 多項式定理與多項式繫數
8.4.1 多項式定理
8.4.2 多項式繫數
習題
第9章 容斥原理
9.1 容斥原理及其應用
9.1.1 容斥原理的基本形式
9.1.2 容斥原理的應用
9.2 對稱篩公式及其應用
9.2.1 對稱篩公式
9.2.2 棋盤多項式與有限制條件的排列
習題
0章 遞推方程與生成函數
10.1 遞推方程及其應用
10.1.1 遞推方程的定義及實例
10.1.2 常繫數線性齊次遞推方程的求解
10.1.3 常繫數線性非齊次遞推方程的求解
10.1.4 遞推方程的其他解法
10.1.5 遞推方程與遞歸算法
10.2 生成函數及其應用
10.2.1 牛頓二項式定理與牛頓二項式繫數
10.2.2 生成函數的定義及其性質
10.2.3 生成函數的應用
10.3 指數生成函數及其應用
10.4 Catalan數與Stirling數
習題
1章 初等數論
11.1 素數
11.2 優選公約數與最小公倍數
11.3 同餘
11.4 一次同餘方程與中國剩餘定理
11.4.1 一次同餘方程
11.4.2 中國剩餘定理
11.4.3 大整數算術運算
11.5 歐拉定理和費馬小定理
習題
2章 離散概率
12.1 隨機事件與概率、事件的運算
12.1.1 隨機事件與概率
12.1.2 事件的運算
12.2 條件概率與獨立性
12.2.1 條件概率
12.2.2 獨立性
12.2.3 伯努利概型與二項概率公式
12.3 離散型隨機變量
12.3.1 離散型隨機變量及其分布律
12.3.2 常用分布
12.3.3 數學期望
12.3.4 方差
12.4 概率母函數
習題
3章 初等數論和離散概率的應用
13.1 密碼學
13.1.1 愷撒密碼
13.1.2 RSA公鑰密碼
13.2 產生偽隨機數的方法
13.2.1 產生均勻偽隨機數的方法
13.2.2 產生離散型偽隨機數的方法
13.3 算法的平均復雜度分析
13.3.1 排序算法
13.3.2 散列表的檢索和插入
13.4 隨機算法
13.4.1 隨機快速排序算法
13.4.2 多項式恆零測試
13.4.3 素數測試
13.4.4 蒙特卡羅法和拉斯維加斯法
習題
4章 代數繫統
14.運算及其性質
14.1.運運算的定義
14.1.運算的性質
14.2 代數繫統
14.2.1 代數繫統的定義與實例
14.2.2 代數繫統的分類
14.2.3 子代數繫統與積代數繫統
14.2.4 代數繫統的同態與同構
14.3 幾個典型的代數繫統
14.3.1 半群與獨異點
14.3.2 群
14.3.3 環與域
14.3.4 格與布爾代數
習題
參考文獻
內容簡介
本教材是參照ACM和IEEE近期新推出的Computing CurricuLa，根據教育部高等學校計算機科學與技術教學指導委員會近期新編制的“高等學校計算機科學與技術專業規範”中制定的關於離散數學的知識結構和體繫撰寫的。全書共14章，內容包含證明技巧、數理邏輯、集合與關繫、函數、組合計數、圖和樹、初等數論、離散概率、代數繫統等，本書體繫嚴謹，文字精練，內容翔實，例題豐富，注重與計算機科學技術的實際問題相結合，並選配了大量難度適當的習題，適合教學。另外，本書有配套的習題解答與學習指導等教學輔導用書，以及用於課堂教學的PPT演示文稿和在線數字資源等，以滿足教學需要。本書適合作為高等學校計算機及相關專業本科生“離散數學”課程的教材，也可以作為對離散數學感興趣的人員的入門參考書。
