離散數學

目　錄

第 1章　命題邏輯　1

1.1　命題和聯結詞　1

1.1.1　命題的概念　1

1.1.2　聯結詞　2

1.2　合式公式與真值表　6

1.2.1　合式公式　6

1.2.2　真值表　6

1.3　永真式和等價式　7

1.3.1　永真式　7

1.3.2　等價式　8

1.3.3　代入規則和替換規則　9

1.4　對偶式與蘊涵式　11

1.4.1　對偶式　11

1.4.2　蘊涵式　12

1.5　範式和判定問題　13

1.5.1　析取範式和合取範式　13

1.5.2　主析取範式和主合取範式　15

1.6　命題演算的推理理論　18

習題　21

第 2章　謂詞邏輯　25

2.1　基本概念和表示　25

2.1.1　個體、謂詞和謂詞形式　25

2.1.2　量詞　26

2.1.3　合式謂詞公式　28

2.1.4　自由變元和約束變元　28

2.2　謂詞邏輯的翻譯與解釋　29

2.2.1　謂詞邏輯的翻譯　29

2.2.2　謂詞公式的解釋　30

2.3　謂詞邏輯的等價式與蘊涵式　31

2.4　謂詞邏輯中的推論理論　32

2.4.1　推理規則　33

2.4.2　推理實例　34

2.5　謂詞邏輯中公式範式　37

2.5.1　前束範式　37

2.5.2　斯柯林範式　38

習題　39

第3章　集合論　41

3.1　集合的概念及其表示　41

3.2　集合的運算及恆等式　43

3.3　有窮集的計數和包含排斥原理　49

習題　51

第4章　二元關系　55

4.1　多重序元與笛卡兒乘積　55

4.2　關系的基本概念　57

4.3　關系的運算　58

4.4　關系的性質　63

4.5　關系的表示　66

4.6　關系的閉包運算　70

4.7　特殊關系　73

4.7.1　集合的劃分和覆蓋　73

4.7.2　等價關系　75

4.7.3　相容關系　79

4.7.4　次序關系　82

4.7.5　偏序集合與哈斯圖　84

4.8*　關系型數據庫　87

習題　88

第5章　函數　94

5.1　函數的基本概念和性質　94

5.2　函數的合成和合成函數的性質　97

5.3　特殊函數　99

5.4　反函數　101

5.5　特徵函數　103

5.6　基數　105

5.7*　不可解問題　108

5.7.1　不可解問題的存在性　108

5.7.2　停機問題　108

習題　109

第6章　代數系統　112

6.1　代數系統的一般概念　113

6.1.1　二元運算　113

6.1.2　代數系統　114

6.2　代數系統的基本性質　115

6.3　同態與同構　122

6.3.1　同態　122

6.3.2　同構　124

6.3.3　同態與同構的性質　127

6.4　同餘關系　128

6.5　商代數　129

6.6　積代數　130

6.7　代數系統實例　131

習題　132

第7章　群與環　134

7.1　半群與群的定義　134

7.2　群的性質　136

7.3　子群與群的陪集分解　139

7.3.1　子群的概念　139

7.3.2　群的陪集與拉格朗日定理　139

7.4　循環群與置換群　140

7.4.1　循環群　140

7.4.2　置換群　141

7.5　環與域　142

7.5.1　環的概念與性質　142

7.5.2　域的概念　143

7.6　應用：群與網絡安全　144

第8章　格與布爾代數　146

8.1　格的定義與性質　147

8.2　分配格、有補格與布爾代數　148

8.3　應用　150

習題　151

第9章　圖的基本概念及其矩陣表示　152

9.1　圖的基本概念　152

9.1.1　圖的定義及相關概念　152

9.1.2　節點的度　154

9.2　子圖和圖的運算　157

9.2.1　子圖和補圖　157

9.2.2　圖的運算　158

9.3　路徑、迴路和連通性　160

9.3.1　路徑和迴路　160

9.3.2　圖的連通性　162

9.4　圖的矩陣表示　165

9.4.1　鄰接矩陣　165

9.4.2　可達性矩陣　169

9.4.3　關聯矩陣　172

習題　174

第 10章　幾種圖的介紹　179

10.1　歐拉圖　179

10.2　哈密爾頓圖　181

10.3　二部圖及匹配　184

10.3.1　二部圖的概念及性質　184

10.3.2　二部圖匹配　185

10.4　平面圖　187

10.4.1　平面圖的概念及性質　187

10.4.2　多邊形圖、對偶圖及平面圖著色　189

10.5　網絡　192

10.5.1　網絡的基本概念　192

10.5.2　網絡流　193

10.5.3　網絡**大流求解　194

10.5.4　開關網絡　201

10.6　圖的實例分析　208

10.6.1　中國郵遞員問題　208

10.6.2　旅行售貨員問題　210

10.6.3　排課問題　211

10.6.4　延時容忍網絡問題　213

10.6.5　**短路徑問題　214

習題　216

第 11章　樹　221

11.1　樹與生成樹　221

11.1.1　樹及其性質　221

11.1.2　生成樹與**小生成樹　223

11.2　有向樹及其應用　224

11.2.1　有向樹　224

11.2.2　m叉樹　225

11.2.3　有序樹　227

11.2.4　二叉樹的遍歷　228

11.2.5　搜索樹　230

習題　232

參考文獻　235