离散数学PDF电子书下载

第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.1 6

1.2 映射的有关概念 7

1.2.1 映射的定义 7

1.2.2 映射的性质 9

1.2.3 逆映射 10

1.2.4 复合映射 11

习题1.2 13

1.3 运算的定义及性质 14

1.3.1 运算的定义 14

1.3.2 运算的性质 17

习题1.3 21

1.4 集合的运算 22

1.4.1 并运算 22

1.4.2 交运算 23

1.4.3 补运算 24

1.4.4 差运算 26

1.4.5 对称差运算 27

习题1.4 28

1.5 集合的划分与覆盖 29

1.5.1 集合的划分 29

1.5.2 集合的覆盖 32

习题1.5 32

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.6 36

第2章 关系 37

2.1 关系的概念 37

2.1.1 n元关系的定义 37

2.1.2 2元关系 38

2.1.3 关系的定义域和值域 41

2.1.4 关系的表示 42

2.1.5 函数的关系定义 43

习题2.1 44

2.2 关系的运算 46

2.2.1 关系的集合运算 46

2.2.2 关系的逆运算 46

2.2.3 关系的复合运算 47

2.2.4 关系的其他运算 51

习题2.2 51

2.3 关系的性质 52

2.3.1 自反性 52

2.3.2 反自反性 53

2.3.3 对称性 54

2.3.4 反对称性 55

2.3.5 传递性 56

习题2.3 58

2.4 关系的闭包 59

2.4.1 自反闭包r（R） 59

2.4.2 对称闭包s（R） 60

2.4.3 传递闭包t（R） 61

习题2.4 64

2.5 等价关系 65

2.5.1 等价关系的定义 65

2.5.2 等价类 66

习题2.5 68

2.6 相容关系 69

2.6.1 相容关系的定义 69

2.6.2 相容类 70

习题2.6 71

2.7 偏序关系 71

2.7.1 偏序关系的定义 71

2.7.2 偏序集的哈斯图 73

2.7.3 偏序集中的特殊元素 74

习题2.7 76

第3章 命题逻辑 78

3.1 命题的有关概念 78

习题3.1 80

3.2 逻辑联结词 80

3.2.1 否定联结词￢p 81

3.2.2 合取联结词p∧q 81

3.2.3 析取联结词p∨q 81

3.2.4 异或联结词p⊕q 82

3.2.5 条件联结词p→q 82

3.2.6 双条件联结词p？q 83

3.2.7 与非联结词p↑q 83

3.2.8 或非联结词p↓q 84

3.2.9 条件否定联结词pn→q 84

习题3.2 84

3.3 命题公式及其真值表 85

3.3.1 命题公式的定义 85

3.3.2 命题的符号化 86

3.3.3 命题公式的真值表 86

3.3.4 命题公式的类型 87

习题3.3 88

3.4 逻辑等值的命题公式 89

3.4.1 逻辑等值的定义 90

3.4.2 基本等值式 91

3.4.3 等值演算法 92

3.4.4 对偶原理 93

习题3.4 93

3.5 命题公式的范式 95

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

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

习题3.5 103

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

3.6.1 联结词的个数 104

3.6.2 功能完备联结词集 105

习题3.6 107

3.7 命题逻辑中的推理 108

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

3.7.2 基本推理规则 109

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

习题3.7 114

第4章 谓词逻辑 116

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

4.1.1 个体 116

4.1.2 谓词 117

4.1.3 量词 117

4.1.4 函词 119

习题4.1 119

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

4.2.1 谓词公式 120

4.2.2 命题的符号化 120

习题4.2 122

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

4.3.1 谓词公式的解释 124

4.3.2 谓词公式的类型 125

习题4.3 125

4.4 逻辑等值的谓词公式 127

4.4.1 谓词公式等值的定义 127

4.4.2 基本等值式 127

习题4.4 129

4.5 谓词公式的前束范式 129

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

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

习题4.5 130

4.6 谓词逻辑中的推理 131

4.6.1 逻辑蕴涵式 131

4.6.2 基本推理规则 131

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

习题4.6 134

第5章 代数结构 136

5.1 代数结构简介 136

5.1.1 代数结构的定义 136

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

5.1.3 子代数 138

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

习题5.1 140

5.2 群的定义及性质 141

5.2.1 群的有关概念 141

5.2.2 子群 143

5.2.3 群的同态 144

习题5.2 144

5.3 环和域 145

5.3.1 环的定义 145

5.3.2 几种特殊的环 146

5.3.3 域的定义 147

5.3.4 有限域 148

习题5.3 149

5.4 格与布尔代数 150

5.4.1 格的定义和性质 150

5.4.2 分配格 153

5.4.3 有补格 154

5.4.4 布尔代数 155

习题5.4 157

第6章 图论 159

6.1 图的基本概念 159

6.1.1 图的定义 159

6.1.2 邻接 161

6.1.3 关联 161

6.1.4 简单图 161

习题6.1 162

6.2 节点的度数 163

习题6.2 165

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

6.3.1 子图 165

6.3.2 图的运算 166

6.3.3 图同构 167

习题6.3 168

6.4 路与回路 168

6.4.1 路 169

6.4.2 回路 169

习题6.4 170

6.5 图的连通性 171

6.5.1 无向图的连通性 171

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

6.5.3 有向图的连通性 173

习题6.5 175

6.6 图的矩阵表示 176

6.6.1 图的邻接矩阵 176

6.6.2 图的可达矩阵 177

6.6.3 图的关联矩阵 178

习题6.6 179

6.7 赋权图及最短路径 180

6.7.1 赋权图 180

6.7.2 最短路径 180

习题6.7 182

第7章 几类特殊的图 183

7.1 欧拉图 183

7.1.1 欧拉图的有关概念 183

7.1.2 欧拉定理 183

7.1.3 中国邮递员问题 184

习题7.1 185

7.2 哈密尔顿图 186

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

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

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

7.2.4 旅行商问题 189

习题7.2 189

7.3 无向树 190

7.3.1 无向树的定义 190

7.3.2 无向树的性质 191

7.3.3 生成树 192

7.3.4 最小生成树 193

习题7.3 194

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.4 201

7.5 平面图 202

7.5.1 平面图的有关概念 203

7.5.2 欧拉公式 204

7.5.3 库拉托夫斯基定理 205

7.5.4 平面图的对偶图 205

习题7.5 206

7.6 平面图的面着色 207

7.6.1 平面图的面着色定义 208

7.6.2 图的节点着色 208

7.6.3 任意图的边着色 209

习题7.6 210

7.7 二部图及其匹配 210

7.7.1 二部图 211

7.7.2 匹配 211

习题7.7 212

第8章 组合计数 214

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

8.1.1 排列 214

8.1.2 组合 215

8.1.3 二项式定理 216

习题8.1 217

8.2 生成函数 217

8.2.1 组合计数生成函数 217

8.2.2 排列计数生成函数 219

习题8.2 221

8.3 递归关系 221

8.3.1 递归关系的概念 221

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

习题8.3 227

附录A 符号索引 228

附录B 中英文名词索引 231

附录C 习题答案及提示 236

参考文献 259