離散數學

第一章 集合論基礎
1.1 集合的基本概念
習題1.1
1.2 關系
1.2.1 關系的基本概念及其性質
1.2.2 等價關系
1.2.3 部分序關系
習題1.2
1.3 映射
1.3.1 集合的基數
1.3.2 可數集合
1.3.3 不可數集甘
習題1.3
1.4 集合在計算機科學中的應用
1.4.1 關系在關系數據庫中的應用
1.4.2 關系代數與數據子語言
1.4.3 等價關系在計算機中的應用
1.4.4 序關系在項目管理中的應用
第二章 命題邏輯
2.1 命題以及邏輯聯結詞
2.1.1 命題
2.1.2 邏輯聯結詞
習題2.1
2.2 命題公式
2.2.1 公式
2.2.2 解釋
習題2.2
2.3 命題公式的等價關系和蘊涵關系
2.3.1 公式的等價
2.3.2 公式的蘊涵
2.3.3 演繹
2.3.4 公式蘊涵的證明方法
習題2.3
2.4 范式
2.4.1 析取范式和合取范式
2.4.2 主析取范式和主合取范式
2.4.3 恒真恒假性的判定
習題2.4
2.5 命題邏輯在二值邏輯器件和語句邏輯中的應用
第三章 謂詞邏輯
3.1 謂詞邏輯的基本概念
3.1.1 謂詞和量詞
3.1.2 改名規(guī)則
習題3.1
3.2 謂詞公式
3.2.1 公式
3.2.2 解釋
習題3.2
3.3 謂詞公式的等價關系和蘊涵關系
3.3.1 公式的等價和蘊涵
3.3.2 謂詞演算的推理理論
習題3.3
3.4 范式
3.4.1 前束范式
3.4.2 Skolem范式
習題3.4
3.5 例
習題3.5
3.6 謂詞邏輯的應用
3.6.1 謂詞邏輯與數據子語言
3.6.2 謂詞邏輯與邏輯程序設計語言
第四章 圖與網絡
4.1 圖
4.1.1 圖的基本概念
4.1.2 權圖Dijkstra算法
習題4.1
4.2 樹
4.2.1 樹及其等價命題
4.2.2 最優(yōu)樹Kruskal算法
4.2.3 求最優(yōu)樹的其他算法
習題4.2
4.3 有向圖Euler路
4.3.1 有向圖與有向樹
4.3.2 Euler路Euler圖
4.3.3 無向圖無向圖中的Euler路
習題4.3
4.4 Hamilton圖
4.4.1 Hamilton路Hamilton圖的必要條件
4.4.2 Hamilton圖的若干充分條件
習題4.4
4.5 平面圖
4.5.1 平面圖判定Kuratowski判字準則
4.5.2 平面圖的Euler公式
4.5.3 平面圖的對偶圖Plato體
4.5.4 平面圖的著色
習題4.5
4.6 匹配二部圖
習題4.6
4.7 Konig無限性引理
習題4.7
4.8 網絡優(yōu)化算法
4.8.1 圖與網絡的數據結構
4.8.2 單源最短路徑問題具體算法及實現和比較
4.8.3 最大流問題具體算法及實現和比較
習題4.8
第五章 數論基礎
5.1 整除性輾轉相除
5.1.1 整除及其性質
5.1.2 輾轉相除
5.1.3 利用數的數碼特征判別某些整除性
習題5.1
5.2 互質質因數分解
5.2.1 整數互質
5.2.2 質數與合數算術基本定理
習題5.2
5.3 合同一次同余式
5.3.1 合同及其性質
5.3.2 剩余類一次同余式
習題5.3
5.4 秦九韶定理Euler函數
5.4.1 一次同余式組秦九韶定理
5.4.2 一元高次同余式的化簡
5.4.3 剩余系遍歷Euler函數
習題5.4
5.5 一元高次同余式二次剩余
5.5.1 一元高次同余式的解
5.5.2 二次同余式二次剩余
5.5.3 二次剩余的判定Legendre符號
習題5.5
5.6 數論在計算機通信安全中的應用
5.6.1 密碼系統(tǒng)
5.6.2 凱撒密碼
5.6.3 Vigenere密碼
5.6.4 Hill加密算法
5.6.5 RSA公鑰系統(tǒng)
習題5.6
第六章 群與環(huán)
6.1 代數系統(tǒng)
習題6.1
6.2 群的定義
6.2.1 半群
6.2.2 群
6.2.3 群的性質
習題6.2
6.3 置換群
6.3.1 置換的定義
6.3.2 置換的輪換表法
6.3.3 置換的順向圈表示
6.3.4 置換的奇偶性
習題6.3
6.4 子群及其陪集
6.4.1 子群的定義
6.4.2 子群的判別條件
6.4.3 循環(huán)群
6.4.4 陪集
習題6.4
6.5 同構及同態(tài)
6.5.1 同態(tài)映射
6.5.2 同構映射
6.5.3 同態(tài)核
習題6.5
6.6 環(huán)
6.6.1 環(huán)的定義
6.6.2 環(huán)的性質
習題6.6
6.7 環(huán)同態(tài)
6.7.1 理想
6.7.2 環(huán)中合同關系
6.7.3 環(huán)同態(tài)與同構
6.7.4 單純環(huán)與極大理想
習題6.7
6.8 群與環(huán)在計算機科學中的應用
6.8.1 計數問題
6.8.2 糾錯碼
第七章 多項式有限域
67.1 域的特征素域
7.1.1 域的特征
7.1.2 素域
習題7.1
7.2 多項式的整除性
習題7.2
7.3 多項式的根
習題7.3
7.4 有理域上的多項式
習題7.4
7.5 分圓多項式
7.5.1 復數域上的分圓多項式
7.5.2 任意域上的分圓多項式
習題7.5
7.6 有限域
習題7.6
7.7 多項式編碼方法及其實現
習題7.7
第八章 格與布爾代數
8.1 引言
8.2 格的定義
習題8.2
8.3 格的性質
8.3.1 對偶原理
8.3.2 格的其他性質
8.3.3 格的同態(tài)與同構
習題8.3
8.4 幾種特殊的格
8.4.1 有界格
8.4.2 有余格
8.4.3 分配格
8.4.4 模格
習題8.4
8.5 布爾代數
8.5.1 布爾代數的定義及其性質
8.5.2 有限布爾代數的表示理論
8.5.3 布爾代數的同態(tài)與同構
習題8.5
8.6 布爾表達式的化簡問題
習題8.6
8.7 格與布爾代數在計算機科學中的應用
8.7.1 開關電路函數
8.7.2 邏輯門
8.7.3 全加器的邏輯設計
第九章 語言和有限狀態(tài)機
9.1 語言和語法
9.1.1 語法結構
9.1.2 語法結構的類型
9.1.3 演繹樹
9.1.4 Backus-Naurform
習題9.1
9.2 帶有輸出的有限狀態(tài)機
習題9.2
9.3 沒有輸出的有限狀態(tài)機
習題9.3
9.4 語言識別
9.4.1 正則集合
9.4.2 KLEENE定理
9.4.3 其他幾種類型的有限狀態(tài)機
習題9.4
9.5 Turing機
習題9.5
參考文獻