離散數(shù)學及算法

前言
第一篇　計算機科學中的離散結構
第1章命題邏輯
1.1 引言
1.2　命題及命題邏輯聯(lián)結詞
　1.2.1　命題
　1.2.2　邏輯聯(lián)結詞
1.3　命題變元和合式的公式
1.4　重言式(或永真式)和永真蘊涵式
　1.4.1　有關重言式的討論
　1.4.2　重言式與恒等式
　1.4.3　永真蘊涵式的定義和常用永真蘊涵式
　1.4.4　代入規(guī)則和替換規(guī)則
1.5　對偶原理
1.6　范式和判定問題
　1.6.1　析取范式和合取范式
　1.6.2　主析取范式和主合取范式
1.7　命題演算的推理理論
小結
第2章　謂詞邏輯
2.1 謂詞演算
　2.1.1　謂詞和量詞
　2.1.2　謂詞和個體
　2.1.3　量詞
　2.1.4　合式公式
　2.1.5 自由變元和約束變元
　2.1.6　謂詞公式的解釋
　2.1.7　含有量詞的等價式和永真蘊涵式
2.2 謂詞邏輯中的推理理論
　2.2.1　謂詞公式的翻譯
　2.2.2　推理規(guī)則
2.3　謂詞公式的范式
　2.3.1　前束范式
　2.3.2　斯柯林范式
小結
第3章　集合論
3.1　集合的概念及其表示
3.2　集合的運算
3.3　集合定律
3.4　包含排斥原理
3.5　多重序元與笛卡兒乘積
　3.5.1　序偶和多重序元
　3.5.2　笛卡兒乘積
小結
第4章 二元關系
4.1 關系的基本概念
4.2　關系的性質(zhì)
4.3　關系的表示
4.4　關系的運算
　4.4.1　關系的合成
　4.4.2　合成關系的矩陣表達和圖解
　4.4.3　關系的求逆運算
　4.4.4　關系的閉包運算
4.5　特殊關系
　4.5.1　集合的劃分和覆蓋
　4.5.2　等價關系
　4.5.3　相容關系
　4.5.4　次序關系
　4.5.5　偏序集合與哈斯圖
小結
第5章 函數(shù)
5.1 函數(shù)的基本概念和性質(zhì)
5.2　函數(shù)的合成與合成函數(shù)的性質(zhì)
5.3　特殊函數(shù)
5.4　反函數(shù)
5.5　特征函數(shù)
5.6　基數(shù)
5.7 二元運算
小結
第6章　代數(shù)系統(tǒng)
6.1　代數(shù)系統(tǒng)的一般概念
6.2　同態(tài)與同構
6.3　同余關系
6.4　商代數(shù)和積代數(shù)
6.5　典型代數(shù)系統(tǒng)
小結
第7章　圖論
7.1　圖的基本概念
7.2　子圖和圖的運算
7.3　路徑、回路和連通性
7.4　圖的矩陣表示
　7.4.1　鄰接矩陣
　7.4.2　可達性矩陣
7.5　歐拉圖
7.6　特殊圖
　7.6.1　二部圖
　7.6.2　平面圖
7.7　樹
7.8 網(wǎng)絡
　7.8.1　網(wǎng)絡流與最大流
　7.8.2　割集
　7.8.3　標號法
　7.8.4　開關網(wǎng)絡
小結
第二篇　離散數(shù)學中的算法
第8章 數(shù)理邏輯中的算法
8.1　邏輯聯(lián)結詞的定義方法
8.2　合式公式的表示方法
8.3 構造任意合式公式的真值表
第9章 集合論中的算法
9.1　求并集
9.2　求交集
9.3　求差集
9.4　求笛卡兒乘積
第10章 關系中的算法
10.1 判斷關系R是否為自反關系及對稱關系
10.2 判斷關系R是否為可傳遞關系
10.3 判斷關系R是否為等價關系
10.4 求等價類
10.5 求極大相容類
10.6 關系的合成運算
10.7 關系的閉包運算(1)
10.8 關系的閉包運算(2)
10.9 m個字符串按字典順序分類算法
第11章 函數(shù)中的算法
第12章 代數(shù)系統(tǒng)中的算法
12.1 判斷是否為代數(shù)系統(tǒng)的算法
12.2 判斷是否為同余關系
12.3 判斷是否為群的算法
第13章 圖論中的算法
13.1 道路矩陣的Warshall算法
13.2 二叉樹的遍歷
13.3 構造最優(yōu)二叉樹算法
13.4 最小生成樹的：Kruskal算法
13.5 求最短距離的Dijkstra算法
13.6 判別連通性的算法
附錄　考研例題解析
參考文獻