《离散数学基础》

目 录1

前 言1

第一章命题逻辑1

引言1

§1-1命题2

1-1.1命题和联结词2

1-1.2条件命题和双条件命题7

1-1.3命题公式9

1-1.4永真式和永假式13

§1-2命题演算14

1-2.1命题定律14

1-2.2代入实例与取代过程19

1-2.3永真蕴涵22

1-2.4不同真值表的命题公式25

1-2.5全功能联结词集合27

§1-3命题范式和判定问题30

1-3.1析取范式与合取范式30

1-3.2主析取范式32

1-3.3主合取范式34

1-3.4范式的唯一性36

§1-4命题演算的推论理论39

1-4.1真值表技术39

1-4.2推论规则41

1-4.3间接证明法44

第二章谓词逻辑46

引言46

§2-1谓词演算46

2-1.1谓词和量词46

2-1.2谓词公式49

2-1.3 自由变元和约束变元50

2-1.4客体域51

§2-2谓词演算的永真式53

2-2.1基本定义53

2-2.2含有量词的等价式和蕴涵式54

2-2.3含有多个量词的等价式和蕴涵式59

§2-3谓词演算的推论理论61

2-3.1含有量词的特殊蕴涵式61

2-3.2推论规则64

2-3.3推论实例68

第三章集合72

引言72

§3-1集合论的基本概念72

3-1.1集合与元素72

3-1.2集合间的关系74

3-1.3幂集78

§3-2集合代数80

3-2.1集合的运算80

3-2.2图解表示法89

3-2.3集合成员表92

3-2.4基本定律94

3-2.5规定原理96

§3-3笛卡儿乘积98

3-3.1多重序元98

3-3.2笛卡儿乘积99

§3-4贝安诺公理与数学归纳法101

引言105

§4-1关系105

第四章二元关系105

4-1.1基本定义106

4-1.2二元关系的基本性质108

4-1.3关系矩阵和关系图111

§4-2等价关系和相容关系116

4-2.1集合的覆盖和划分116

4-2.2等价关系118

*4-2.3相容关系124

4-3.1合成关系127

§4-3关系的合成127

4-3.2合成关系的矩阵表达和图解132

4-3.3逆关系135

§4-4关系的闭包运算139

§4-5次序关系148

4-5.1次序关系148

4-5.2偏序集合与哈斯图153

第五章函数157

引言157

5-1函数的基本性质157

5-1.1基本定义157

5-1.2函数的合成160

§5-2特种函数162

§5-3反函数167

§5-4置换170

§5-5二元运算173

*§5-6集合的特征函数177

§5-7基数180

第六章代数系统185

引言185

§6-1代数结构185

§6-2代数系统的实例189

§6-3同态和同构192

§6-4同余关系197

§6-5商代数200

§6-6积代数203

§7-1半群和含幺半群205

7-1.1基本定义205

引言205

第七章半群与群205

7-1.2半群和含幺半群的实例208

*7-1.3半群和含幺半群的同态与同构211

*7-1.4子半群和子含幺半群213

*7-1.5半群的积代数214

*§7-2群215

7-2.1基本定义215

7-2.2群的基本性质216

7-2.3置换群和循环群219

7-2.4子群226

7-2.5群的同态与同构228

7-2.6陪集和拉格朗日定理231

7-2.7正规子群235

7-2.8群的积代数238

*§7-3环和域240

7-3.1环240

7-3.2子环和理想243

7-3.3域245

§8-1格——偏序集合247

8-1.1基本定义247

引言247

*第八章格与布尔代数247

8-1.2格的基本性质250

§8-2格——代数系统254

8-2.1基本定义254

8-2.2子格与格的积代数256

8-2.3格同态与格同构258

8-3.1有补格260

§8-3特殊格260

8-3.2分配格262

§8-4布尔代数265

8-4.1基本定义266

8-4.2子布尔代数与布尔同态269

8-4.3布尔代数的原子表示271

8-4.4布尔代数的积代数276

8-4.5自由布尔代数278

§9-1图论的基本概念281

9-1.1基本定义281

引言281

第九章图论281

9-1.2子图和图的同构285

9-1.3路径和循环288

9-1.4图的连通性291

§9-2图的矩阵表示294

9-2.1邻接矩阵294

9-2.2可达性矩阵299

§9-3欧拉图与哈密顿图303

9-3.1欧拉图303

9-3.2 哈密顿图306

§9-4特殊图307

9-4.1平面图307

9-4.2二分图312

9-4.3树315

§9-5猜谜与对策322

9-5.1猜谜322

9-5.2最优原理323

9-5.3对策326

9-5.4关键路径法329

参考文献333

英汉术语对照表334