目錄

第1章命題邏輯1

1.1命題符號化及聯結詞1

1.2命題公式及分類5

1.3等值演算8

1.4范式12

1.5聯結詞全功能集17

1.6組合電路19

1.7推理理論21

1.8題例分析26

習題31

第2章一階邏輯37

2.1一階邏輯基本概念37

2.2一階邏輯合式公式及解釋42

2.3一階邏輯等值式與前束范式46

2.4題例分析49

習題52

第3章集合的基本概念和運算56

3.1集合的基本概念56

3.2集合的基本運算58

3.3集合中元素的計數63

3.4題例分析67

習題71

第4章二元關系和函數77

4.1集合的笛卡兒積與二元關系77

4.2關系的運算81

4.3關系的性質86

4.4關系的閉包88

4.5等價關系和偏序關系90

4.6函數的定義和性質95

4.7函數的復合和反函數99

4.8題例分析107

習題113

第5章圖的基本概念119

5.1無向圖及有向圖119

5.2通路、回路和圖的連通性124

離散數學(第六版)目錄5.3圖的矩陣表示126

5.4*短路徑、關鍵路徑和著色129

5.5題例分析135

習題138

第6章特殊的圖141

6.1二部圖141

6.2歐拉圖143

6.3哈密頓圖145

6.4平面圖147

6.5題例分析152

習題155

第7章樹158

7.1無向樹及生成樹158

7.2根樹及其應用162

7.3題例分析168

習題172

第8章組合分析初步175

8.1加法法則和乘法法則175

8.2基本排列組合的計數方法176

8.3遞推方程的求解與應用182

8.4題例分析188

習題193

第9章代數系統簡介197

9.1二元運算及其性質197

9.2代數系統203

9.3幾個典型的代數系統207

9.4題例分析219

習題224

第10章形式語言和自動機初步231

10.1形式語言和形式文法231

10.1.1字符串和形式語言231

10.1.2形式文法232

10.1.3形式文法的分類235

10.1.4正則文法和上下文無關文法的應用236

10.1.5語法分析樹238

10.2有窮自動機239

10.2.1基本概念240

10.2.2非確定型有窮自動機240

10.2.3帶ε轉移的非確定型有窮自動機243

10.3正則表達式246

10.4圖靈機248

10.5題例分析252

習題254