离散数学

第1章 集合、映射与运算1

1.1 集合的有关概念1

1.1.1 集合1

1.1.2 子集3

1.1.3 幂集4

1.1.4 n元组5

1.1.5 笛卡儿积6

习题1.16

1.2 映射的有关概念7

1.2.1 映射的定义7

1.2.2 映射的性质9

1.2.3 逆映射10

1.2.4 复合映射11

习题1.213

1.3 运算的定义及性质14

1.3.1 运算的定义14

1.3.2 运算的性质17

习题1.321

1.4 集合的运算22

1.4.1 并运算22

.1.4.2 交运算23

1.4.3 补运算24

1.4.4 差运算26

1.4.5 对称差运算27

习题1.428

1.5 集合的划分与覆盖29

1.5.1 集合的划分29

1.5.2 集合的覆盖32

习题1.532

1.6 集合的对等32

1.6.1 集合对等的定义33

1.6.2 无限集合33

1.6.3 集合的基数34

1.6.4 可数集合34

1.6.5 不可数集合35

1.6.6 基数的比较35

习题1.636第2章 关系37

2.1 关系的概念37

2.1.1 玭元关系的定义37

2.1.2 2元关系38

2.1.3 关系的定义域和值域41

2.1.4 关系的表示42

2.1.5 函数的关系定义43

习题2.144

2.2 关系的运算46

2.2.1 关系的集合运算46

2.2.2 关系的逆运算46

2.2.3 关系的复合运算47

2.2.4 关系的其他运算51

习题2.251

2.3 关系的性质52

2.3.1 自反性52

2.3.2 反自反性53

2.3.3 对称性54

2.3.4 反对称性55

2.3.5 传递性56

习题2.358

2.4 关系的闭包59

2.4.1 自反闭包玶(r)59

2.4.2 对称闭包玸(r)60

2.4.3 传递闭包玹(r)61

习题2.464

2.5 等价关系65

2.5.1 等价关系的定义65

2.5.2 等价类66

习题2.568

2.6 相容关系69

2.6.1 相容关系的定义69

2.6.2 相容类70

习题2.671

2.7 偏序关系71

2.7.1 偏序关系的定义71

2.7.2 偏序集的哈斯图73

2.7.3 偏序集中的特殊元素74

习题2.776第3章 命题逻辑78

3.1 命题的有关概念78

习题3.180

3.2 逻辑联结词80

3.2.1 否定联结词p81

3.2.2 合取联结词pC∧q81

3.2.3 析取联结词p∨q81

3.2.4 异或联结词pC﹒82

3.2.5 条件联结词pB→q82

3.2.6 双条件联结词pB躴83

3.2.7 与非联结词p↑q83

3.2.8 或非联结词p↓q84

3.2.9 条件否定联结词pB→玭玵84

习题3.284

3.3 命题公式及其真值表85

3.3.1 命题公式的定义85

3.3.2 命题的符号化86

3.3.3 命题公式的真值表86

3.3.4 命题公式的类型87

习题3.388

3.4 逻辑等值的命题公式89

3.4.1 逻辑等值的定义90

3.4.2 基本等值式91

3.4.3 等值演算法92

3.4.4 对偶原理93

习题3.493

3.5 命题公式的范式95

3.5.1 命题公式的析取范式及合取范式95

3.5.2 命题公式的主析取范式及主合取范式98

习题3.5103

3.6 联结词集合的功能完备性104

3.6.1 联结词的个数104

3.6.2 功能完备联结词集105

习题3.6107

3.7 命题逻辑中的推理108

3.7.1 推理形式有效性的定义108

3.7.2 基本推理规则109

3.7.3 命题逻辑的自然推理系统110

习题3.7114第4章 谓词逻辑116

4.1 个体、谓词、量词和函词116

4.1.1 个体116

4.1.2 谓词117

4.1.3 量词117

4.1.4 函词119

习题4.1119

4.2 谓词公式及命题的符号化120

4.2.1 谓词公式120

4.2.2 命题的符号化120

习题4.2122

4.3 谓词公式的解释及类型124

4.3.1 谓词公式的解释124

4.3.2 谓词公式的类型125

习题4.3125

4.4 逻辑等值的谓词公式127

4.4.1 谓词公式等值的定义127

4.4.2 基本等值式127

习题4.4129

4.5 谓词公式的前束范式129

4.5.1 谓词公式的前束范式的定义129

4.5.2 谓词公式的前束范式的计算130

习题4.5130

4.6 谓词逻辑中的推理131

4.6.1 逻辑蕴涵式131

4.6.2 基本推理规则131

4.6.3 谓词逻辑的自然推理系统132

习题4.6134第5章 代数结构136

5.1 代数结构简介136

5.1.1 代数结构的定义136

5.1.2 两种最简单的代数结构：半群及独异点137

5.1.3 子代数138

5.1.4 代数结构的同态与同构138

习题5.1140

5.2 群的定义及性质141

5.2.1 群的有关概念141

5.2.2 子群143

5.2.3 群的同态144

习题5.2144

5.3 环和域145

5.3.1 环的定义145

5.3.2 几种特殊的环146

5.3.3 域的定义147

5.3.4 有限域148

习题5.3149

5.4 格与布尔代数150

5.4.1 格的定义和性质150

5.4.2 分配格153

5.4.3 有补格154

5.4.4 布尔代数155

习题5.4157第6章 图论159

6.1 图的基本概念159

6.1.1 图的定义159

6.1.2 邻接161

6.1.3 关联161

6.1.4 简单图161

习题6.1162

6.2 节点的度数163

习题6.2165

6.3 子图、图的运算和图同构165

6.3.1 子图165

6.3.2 图的运算166

6.3.3 图同构167

习题6.3168

6.4 路与回路168

6.4.1 路169

6.4.2 回路169

习题6.4170

6.5 图的连通性171

6.5.1 无向图的连通性171

6.5.2 无向连通图的点连通度与边连通度172

6.5.3 有向图的连通性173

习题6.5175

6.6 图的矩阵表示176

6.6.1 图的邻接矩阵176

6.6.2 图的可达矩阵177

6.6.3 图的关联矩阵178

习题6.6179

6.7 赋权图及最短路径180

6.7.1 赋权图180

6.7.2 最短路径180

习题6.7182第7章 几类特殊的图183

7.1 欧拉图183

7.1.1 欧拉图的有关概念183

7.1.2 欧拉定理183

7.1.3 中国邮递员问题184

习题7.1185

7.2 哈密尔顿图186

7.2.1 哈密尔顿图的有关概念186

7.2.2 哈密尔顿图的必要条件187

7.2.3 哈密尔顿图的充分条件187

7.2.4 旅行商问题189

习题7.2189

7.3 无向树190

7.3.1 无向树的定义190

7.3.2 无向树的性质191

7.3.3 生成树192

7.3.4 最小生成树193

习题7.3194

7.4 有向树195

7.4.1 有向树的定义195

7.4.2 根树195

7.4.3 m叉树196

7.4.4 有序树199

7.4.5 定位二叉树199

习题7.4201

7.5 平面图202

7.5.1 平面图的有关概念203

7.5.2 欧拉公式204

7.5.3 库拉托夫斯基定理205

7.5.4 平面图的对偶图205

习题7.5206

7.6 平面图的面着色207

7.6.1 平面图的面着色定义208

7.6.2 图的节点着色208

7.6.3 任意图的边着色209

习题7.6210

7.7 二部图及其匹配210

7.7.1 二部图211

7.7.2 匹配211

习题7.7212第8章 组合计数214

8.1 排列组合与二项式定理214

8.1.1 排列214

8.1.2 组合215

8.1.3 二项式定理216

习题8.1217

8.2 生成函数217

8.2.1 组合计数生成函数217

8.2.2 排列计数生成函数219

习题8.2221

8.3 递归关系221

8.3.1 递归关系的概念221

8.3.2 常用的递归关系求解方法223

习题8.3227

附录a 符号索引228

附录b 中英文名词索引231

附录c 习题答案及提示236

参考文献259