《离散数学》

第一章 命题逻辑1

引言1

1-1 命题2

1-1.1 命题和联结词2

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

1-1.3 命题公式14

1-1.4 永真式和永假式20

1-2 命题演算23

1-2.1 命题定律23

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

1-2.3 永真蕴涵34

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

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

1-3 命题范式和判定问题47

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

1-3.2 主析取范式51

1-3.3 主合取范式54

1-4 命题演算的推理理论59

1-4.1 真值表技术59

1-4.2 推理规则63

第二章 谓词逻辑68

引言68

2-1.1 谓词和量词69

2-1 谓词演算69

2-1.2 谓词公式73

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

2-1.4 客体域78

2-2 谓词演算的永真式81

2-2.1 基本定义82

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

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

2-3 谓词演算的推理理论95

2-3.1 推理规则95

3-1 集合的基本概念101

引言101

第三章 集合101

3-1.1 集合与元素102

3-1.2 集合间的关系106

3-1.3 幂集112

3-2 集合代数116

3-2.1 集合的运算116

3-2.2 图解表示法130

3-2.3 集合成员表136

3-2.4 基本定律138

3-3 笛卡儿乘积143

3-3.1 多重序元143

3-3.2 笛卡儿乘积145

第四章 二元关系150

引言150

4-1 关系150

4-1.1 基本定义151

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

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

4-2 等价关系172

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

4-2.2 等价关系176

4-3.1 合成关系187

4-3 关系的合成187

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

4-3.3 逆关系201

第五章 函数209

引言209

5-1 函数的基本性质210

5-1.1 基本定义210

5-1.2 函数的合成215

5-2 几种重要函数220

5-3 反函数229

5-4 置换236

5-5 二元运算240

引言249

第六章 代数系统249

6-1 代数结构250

6-2 代数系统的实例257

6-3 同态和同构263

6-4 同余关系272

6-5 商代数278

6-6 积代数284

第七章 图论287

引言287

7-1 图论的基本概念287

7-1.1 基本定义288

7-1.2 子图与图的同构295

7-1.3 路径和循环302

7-1.4 图的连通性309

7-2 图的矩阵表示314

7-2.1 邻接矩阵314

7-2.2 可达性矩阵323

7-3 欧拉图与哈密顿图330

7-3.1 欧拉图331

7-3.2 哈密顿图337

7-4 特殊图339

7-4.1 平面图339

7-4.2 二分图349

7-4.3 树356