離散數學（第2版）

目錄

第一篇數 理 邏 輯

第1章命題邏輯/31.1命題及其表示3

1.1.1命題3

1.1.2命題的表示4

1.2聯結詞4

1.2.1否定5

1.2.2合取5

1.2.3析取6

1.2.4條件6

1.2.5雙條件7

1.3命題公式與翻譯8

1.3.1命題公式8

1.3.2翻譯9

1.4真值表與等價式10

1.4.1真值表10

1.4.2等價式12

1.5重言式、蘊含式與對偶式14

1.5.1重言式14

1.5.2蘊含式15

1.5.3對偶式17

1.6聯結詞的完備集18

1.6.1不可兼析取18

1.6.2條件的否定19

1.6.3與非19

1.6.4或非19

1.6.5聯結詞的完備集20

1.7命題公式的範式21

1.7.1合取範式與析取範式21

1.7.2主析取範式23

1.7.3主合取範式26

1.7.4主析取範式與主合取範式之間的聯系28

1.8推理理論29

1.8.1有效結論與推理規則29

1.8.2判斷有效結論的常用方法31

1.9命題邏輯的應用35

1.10本章總結37

1.11本章習題38

第2章謂詞邏輯/44

2.1謂詞的概念與表示44

2.1.1謂詞的定義44

2.1.2n元謂詞45

2.2命題函數與量詞46

2.2.1命題函數46

2.2.2量詞47

2.3謂詞公式與翻譯48

2.3.1謂詞公式48

2.3.2謂詞公式的翻譯49

2.4變元的約束50

2.4.1約束變元與自由變元50

2.4.2約束變元的換名與自由變元的代入51

2.4.3有限論域客體變元的枚舉52

2.5謂詞演算的等價式與蘊含式52

2.5.1謂詞公式的賦值及分類52

2.5.2謂詞演算的等價式53

2.5.3謂詞演算的蘊含式55

2.5.4多個量詞之間的等價關系與蘊含關系56

2.6前束範式57

2.7謂詞演算的推理理論58

2.8本章總結61

2.9本章習題63

第二篇集合論

第3章集合/713.1集合的概念和表示法71

3.1.1集合的概念71

3.1.2集合的表示73

3.1.3特殊集合74

3.1.4集合之間的關系75

3.2集合的運算77

3.3序偶與笛卡兒積83

3.3.1序偶83

3.3.2笛卡兒積84

3.4包含排斥原理87

3.5集合的劃分與覆蓋89

3.6集合的應用90

3.7本章總結94

3.8本章習題97

第4章關系/102

4.1關系的概念與表示102

4.1.1關系的概念102

4.1.2關系的表示104

4.2關系的性質107

4.2.1關系的幾種性質107

4.2.2性質的判別111

4.3復合關系和逆關系113

4.3.1復合關系113

4.3.2逆關系117

4.4關系的閉包運算119

4.4.1關系的閉包定義120

4.4.2關系閉包運算的相關定理120

4.5等價關系與等價類126

4.5.1等價關系126

4.5.2等價類127

4.5.3商集128

4.6相容關系130

4.6.1相容關系及其表示130

4.6.2相容類131

4.6.3最大相容類132

4.6.4完全覆蓋133

4.7序關系134

4.7.1偏序關系及其表示134

4.7.2蓋住關系135

4.7.3全序關系136

4.7.4特殊元素137

4.7.5良序集合139

4.8關系的應用140

4.9本章總結144

4.10本章習題145

第5章函數/153

5.1函數的概念153

5.2幾種特殊的函數154

5.3函數的運算156

5.3.1復合函數156

5.3.2逆函數157

5.4函數的應用159

5.5本章總結163

5.6本章習題164

第三篇代 數  系 統

第6章代數結構/1696.1代數系統引論169

6.2基本運算及其性質170

6.3半群與獨異點176

6.4群與子群178

6.5阿貝爾群與循環群182

6.5.1阿貝爾群（交換群）182

6.5.2循環群182

6.6置換群185

6.7陪集與拉格朗日定理186

6.7.1陪集186

6.7.2拉格朗日定理188

6.8同構與同態190

6.8.1同構190

6.8.2同態193

6.9環與域196

6.9.1環196

6.9.2域199

6.10代數結構的應用200

6.10.1計數問題201

6.10.2群碼與糾錯碼204

6.11本章總結217

6.12本章習題219

第7章格與布爾代數/224

7.1格的定義224

7.2分配格229

7.3有補格231

7.4布爾代數233

7.4.1布爾代數的一般概念233

7.4.2子代數234

7.4.3布爾同態與布爾同構235

7.5布爾代數表達式238

7.6格與布爾代數的應用245

7.6.1布爾函數的表示法246

7.6.2邏輯電路設計方法249

7.6.3時序邏輯電路的設計253

7.7本章總結257

7.8本章習題259

第四篇圖論

第8章圖/2658.1圖的基本概念265

8.2路、回路與連通性271

8.2.1路與回路271

8.2.2無向圖的連通性272

8.2.3有向圖的連通性275

8.3圖的矩陣表示277

8.3.1鄰接矩陣277

8.3.2可達矩陣280

8.3.3關聯矩陣281

8.4圖的應用283

8.4.1無向圖的應用283

8.4.2有向圖的應用284

8.4.3混合圖的應用284

8.4.4一些特殊簡單圖及其應用284

8.5本章總結286

8.6本章習題288

第9章特殊圖/291

9.1歐拉圖291

9.2哈密爾頓圖296

9.3平面圖300

9.4對偶圖303

9.5樹與根樹306

9.5.1樹的概念306

9.5.2生成樹308

9.5.3根樹309

9.6樹與根樹的應用311

9.6.1最小生成樹311

9.6.2最優樹312

9.7本章總結313

9.8本章習題316

第10章上機實驗/319

10.1實驗一： 數理邏輯319

10.1.1真值表319

10.1.2合式公式等價性驗證320

10.1.3主析取範式和主合取範式321

10.1.4有效結論321

10.2實驗二： 集合論322

10.2.1集合基本計算322

10.2.2冪集323

10.2.3笛卡兒積323

10.2.4關系的性質324

10.2.5關系的復合運算325

10.2.6關系的閉包325

10.2.7偏序關系326

10.2.8函數特性判斷326

10.3實驗三： 代數系統327

10.3.1幺元和零元327

10.3.2群328

10.3.3半群、獨異點和群328

10.4實驗四： 圖論328

10.4.1圈329

10.4.2連通圖329

10.4.3可達矩陣330

10.4.4歐拉圖331

10.4.5地圖著色問題331

10.4.6哈夫曼編碼332

參考文獻/333