離散數學

本書包括離散數學課程的標準內容：數理邏輯中的命題邏輯、一階謂詞邏輯、集合論、代數系統、圖論等.特別是豐富了集合論的內容，將數學歸納法、計數以及組合論中的一些廣泛應用的方法納入集合論中.另外，書末附錄中還講述了離散數學在關係數據庫中的應用.

本書力求做到簡潔明瞭、易懂易學，注重理論與實際的結合，注意與後續課程的銜接.適合作為普通高等院校數學、計算機科學與技術等專業的本科生教材，也可供高職高專院校的師生參考使用. ^[1] 

第1章 集合論11.1 集合的概念與運算1

1.1.1 集合的概念1

1.1.2 集合之間的關係2

1.1.3 集合的運算2

1.1.4 集合的運算性質3

1.1.5 序偶與笛卡兒積5

1.2 二元關係6

1.2.1 二元關係及其表示6

1.2.2 二元關係的運算7

1.3 關係的性質10

1.4 關係的閉包運算12

1.5 序關係15

1.6 等價關係18

1.7 映射20

?*1.8 數學歸納法22

?*1.9 計數24

1.9.1 帕斯卡三角形和二項式定理25

1.9.2 鴿巢原理26

1.9.3 乘法法則和加法法則28

1.9.4 排列和組合29

?*1.10 排列組合生成算法31

?*1.11 離散概率簡介34

習題137

第2章 命題邏輯41

2.1 命題與聯結詞41離散數學目錄2.1.1 命題與真值41

2.1.2 命題聯結詞42

2.2 命題公式、指派及真值表46

2.2.1 命題公式46

2.2.2 命題的符號化 47

2.2.3 公式的指派(賦值)及真值表48

2.3 命題公式的等值式，藴含關係式50

2.3.1 命題公式的等值式50

2.3.2 代入規則與替換規則51

2.3.3 對偶式53

2.3.4 藴含關係式54

2.4 主析取範式和主合取範式56

2.4.1 合取範式與析取範式57

2.4.2 主範式58

?*2.5 聯結詞完備集61

2.6 可滿足性問題與消解法63

2.7 推理的形式結構68

2.8 自然推理系統?N?中的形式證明70

習題276

第3章 謂詞邏輯79

3.1 基本概念79

3.1.1 個體詞、謂詞79

3.1.2 量詞80

3.2 一階邏輯公式及解釋83

3.3 一階邏輯等值式87

3.4 前束範式與斯科林範式90

3.4.1 前束範式90

3.4.2 斯科林範式92

3.5 謂詞演算的推理理論93

??3.6 數理邏輯在計算機科學中的應用99

3.6.1 “鑰匙在點火開關中”報警蜂鳴器100

3.6.2 構造自鎖控制安全帶的電路103

3.6.3 構造一個拿子游戲裝置105

3.6.4 構造電路： 專用裝置和程序化計算機108

習題3109

??第4章 公理系統下的形式證明112

4.1 命題邏輯的公理推理系統112

4.1.1 公理推理系統?P?112

4.1.2 公理推理系統?P?的可靠性、和諧性和完備性117

4.2 謂詞邏輯的公理系統120

4.3 定理的機器證明122

第5章 圖論124

5.1 圖的基本概念124

5.1.1 圖及其圖形表示125

5.1.2 頂點的度126

5.1.3 完全圖和補圖128

5.1.4 子圖129

5.1.5 圖的同構129

5.2 通路、迴路與連通性131

5.2.1 通路和迴路131

5.2.2 無向圖的連通性133

5.2.3 有向圖的連通性136

5.2.4 門格定理137

5.3 歐拉圖與中國郵遞員問題138

5.3.1 哥尼斯堡七橋問題138

5.3.2 歐拉圖139

5.3.3 中國郵遞員問題142

5.4 哈密爾頓圖與旅行售貨商問題144

5.4.1 哈密爾頓圖144

5.4.2 旅行售貨商問題147

5.5 樹149

5.5.1 樹的定義及其基本性質149

5.5.2 生成樹151

5.5.3 最小生成樹問題153

5.5.4 根樹及其應用154

5.6 圖的矩陣表示158

5.6.1 關聯矩陣158

5.6.2 鄰接矩陣159

5.6.3 可達矩陣164

5.6.4 圖的運算165

5.7 平面圖與圖的着色166

5.7.1 平面圖166

5.7.2 對偶圖與圖着色169

習題5171

第6章 代數系統175

6.1 二元運算與代數系統175

6.1.1 二元運算175

6.1.2 代數系統179

6.2 羣和半羣180

6.2.1 羣和半羣的定義 180

6.2.2 關於逆元的性質182

6.2.3 羣的幾個等價性質182

6.3 子羣和元素的階183

6.3.1 子羣183

6.3.2 元素的階184

6.4 循環羣和生成羣、羣的同構185

6.4.1 循環羣和生成羣185

6.4.2 羣的同構186

6.4.3 循環羣的性質186

6.5 變換羣和置換羣、凱萊定理187

6.5.1 置換羣188

6.5.2 凱萊定理190

6.6 子羣的陪集和拉格朗日定理192

6.6.1 子羣的陪集192

6.6.2 子羣的指數和拉格朗日定理193

6.7 正規子羣和商羣195

6.7.1 正規子羣的概念195

6.7.2 正規子羣的性質195

6.7.3 商羣196

6.8 共軛元和共軛子羣198

6.8.1 中心和中心化子198

6.8.2 共軛元和共軛類198

6.8.3 共軛子羣與正規化子199

6.9 羣的同態200

6.9.1 羣的同態定義200

6.9.2 同態基本定理202

6.10 環與域203

?*6.11 代數系統在計算機科學中的應用206

6.11.1 通信模型的基本概念206

6.11.2 糾錯編碼的基本概念207

6.11.3 線性分組碼和漢明碼209

習題6212

第7章 格與布爾代數215

7.1 格215

7.2 格同態220

7.3 分配格和有補格223

7.4 布爾代數227

??7.5 布爾函數及其表達式234

習題7238

?*附錄A 離散數學在關係數據庫中的應用240

A.1 關係數據庫簡介240

A.2 關係代數與數據子語言242

參考文獻251 ^[1]