目錄

第1章命題邏輯1

1.1命題和邏輯連接詞2

1.1.1命題2

1.1.2邏輯連接詞與命題符號化4

習(xí)題1.17

1.2命題公式及其真值表8目錄



第1章命題邏輯1

1.1命題和邏輯連接詞2

1.1.1命題2

1.1.2邏輯連接詞與命題符號化4

習(xí)題1.17

1.2命題公式及其真值表8

1.2.1命題公式8

1.2.2真值表8

習(xí)題1.211

1.3命題公式的等價演算12

習(xí)題1.315

1.4命題公式的范式15

1.4.1析取范式與合取范式15

1.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式18

1.4.3利用真值表求解標(biāo)準(zhǔn)范式20

1.4.4標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式的關(guān)系22

習(xí)題1.423

1.5命題公式的推理演算25

1.5.1基本概念25

1.5.2演繹推理方法27

1.5.3附加前提法28

習(xí)題1.530

1.6邏輯門電路32

1.6.1門電路32

1.6.2邏輯電路設(shè)計33

習(xí)題1.635

第1章上機練習(xí)35



第2章謂詞邏輯37

2.1個體詞、謂詞與量詞37

2.1.1個體詞與謂詞37

2.1.2量詞38

習(xí)題2.140

2.2謂詞公式及其解釋42

2.2.1謂詞公式42

2.2.2謂詞公式的解釋43

習(xí)題2.246

2.3謂詞公式的等價演算47

習(xí)題2.349

2.4謂詞公式的推理演算50

2.4.1基本概念50

2.4.2演繹推理方法51

習(xí)題2.455

第2章上機練習(xí)56



第3章集合與關(guān)系58

3.1集合及其運算58

3.1.1基本概念58

3.1.2集合的運算60

3.1.3集合的計算機表示62

習(xí)題3.163

3.2二元關(guān)系及其運算65

3.2.1笛卡爾積65

3.2.2二元關(guān)系及其表示66

3.2.3二元關(guān)系的運算67

習(xí)題3.270

3.3二元關(guān)系的性質(zhì)與閉包71

3.3.1二元關(guān)系的性質(zhì)71

3.3.2二元關(guān)系的閉包73

習(xí)題3.375

3.4等價關(guān)系與劃分77

習(xí)題3.480

3.5偏序關(guān)系與拓?fù)渑判?0

3.5.1偏序關(guān)系80

3.5.2偏序集中的特殊元82

3.5.3拓?fù)渑判?4

習(xí)題3.585

3.6函數(shù)87

3.6.1基本概念87

3.6.2復(fù)合函數(shù)88

3.6.3逆函數(shù)90

習(xí)題3.691

3.7集合的等勢與基數(shù)92

習(xí)題3.793

3.8多元關(guān)系及其應(yīng)用93

3.8.1多元關(guān)系93

3.8.2關(guān)系數(shù)據(jù)庫94

3.8.3數(shù)據(jù)庫的檢索95

3.8.4插入、刪除與修改96

習(xí)題3.897

第3章上機練習(xí)98



第4章代數(shù)結(jié)構(gòu)99

4.1代數(shù)運算99

4.1.1基本概念99

4.1.2二元運算的性質(zhì)100

4.1.3二元運算中的特殊元101

習(xí)題4.1103

4.2代數(shù)系統(tǒng)104

習(xí)題4.2106

4.3群107

4.3.1基本概念107

4.3.2冪運算109

4.3.3群的性質(zhì)110

習(xí)題4.3113

4.4子群與陪集114

4.4.1子群114

4.4.2陪集116

4.4.3正規(guī)子群與商群118

4.4.4群同態(tài)與同構(gòu)119

習(xí)題4.4120

4.5循環(huán)群、置換群121

4.5.1循環(huán)群121

4.5.2置換群122

習(xí)題4.5125

4.6環(huán)與域125

4.6.1環(huán)126

4.6.2整環(huán)與域127

習(xí)題4.6128

4.7格與布爾代數(shù)129

4.7.1格129

4.7.2幾種特殊的格130

4.7.3布爾代數(shù)132

習(xí)題4.7133

第4章上機練習(xí)134



第5章圖135

5.1基本概念135

5.1.1圖的定義135

5.1.2頂點的度137

習(xí)題5.1139

5.2圖的連通性139

5.2.1通路139

5.2.2連通圖141

5.2.3圖的矩陣表示144

習(xí)題5.2147

5.3歐拉圖與哈密爾頓圖148

5.3.1歐拉圖148

5.3.2哈密爾頓圖150

5.3.3旅行商問題151

習(xí)題5.3152

5.4最短通路153

5.4.1廣義優(yōu)先搜索153

5.4.2Dijkstra算法156

5.4.3中國郵遞員問題158

習(xí)題5.4159

5.5樹160

5.5.1基本概念160

5.5.2生成樹163

5.5.3深度優(yōu)先搜索165

5.5.4最小生成樹168

習(xí)題5.5171

5.6平面圖及圖的著色173

5.6.1平面圖173

5.6.2圖的著色176

習(xí)題5.6179

第5章上機練習(xí)180



第6章有向圖181

6.1有向圖概述181

6.1.1基本概念181

6.1.2有向圖的連通性182

6.1.3有向圖的矩陣表示184

習(xí)題6.1186

6.2根樹187

6.2.1基本概念187

6.2.2二叉搜索樹188

6.2.3最優(yōu)二叉樹190

習(xí)題6.2193

6.3網(wǎng)絡(luò)流194

6.3.1基本概念194

6.3.2最大流算法196

6.3.3最大流最小割定理202

習(xí)題6.3203

6.4匹配205

習(xí)題6.4207

第6章上機練習(xí)208



參考文獻(xiàn)209