离散数学PDF电子书下载

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

1.1 集合的有关概念 1

1.1.1 集合 1

1.1.2 子集 3

1.1.3 幂集 3

1.1.4 n元组 4

1.1.5 笛卡儿积 4

习题1.1 4

1.2 映射的有关概念 5

1.2.1 映射的定义 5

1.2.2 映射的性质 7

1.2.3 逆映射 8

1.2.4 复合映射 9

习题1.2 10

1.3 运算的定义及性质 11

1.3.1 运算的定义 12

1.3.2 运算的性质 13

习题1.3 17

1.4 集合的运算 18

1.4.1 并运算 18

1.4.2 交运算 19

1.4.3 补运算 20

1.4.4 差运算 21

1.4.5 对称差运算 22

习题1.4 23

1.5 集合的划分与覆盖 24

1.5.1 集合的划分 25

1.5.2 集合的覆盖 27

习题1.5 27

1.6 集合的对等 28

1.6.1 集合对等的定义 28

1.6.2 无限集合 29

1.6.3 集合的基数 29

1.6.5 不可列集合 30

1.6.6 基数的比较 30

1.6.4 可列集合 30

习题1.6 31

第2章 关系 33

2.1 关系的概念 33

2.1.1 n元关系的定义 33

2.1.2 2元关系 34

2.1.3 关系的定义域和值域 36

2.1.4 关系的表示 36

2.1.5 函数的关系定义 38

习题2.1 39

2.2 关系的运算 39

2.2.1 关系的集合运算 40

2.2.2 关系的逆运算 40

2.2.3 关系的复合运算 41

2.2.4 关系的其他运算 45

习题2.2 45

2.3.1 自反性 46

2.3 关系的性质 46

2.3.2 反自反性 47

2.3.3 对称性 48

2.3.4 反对称性 49

2.3.5 传递性 50

习题2.3 52

2.4 关系的闭包 53

2.4.1 自反闭包r（R） 53

2.4.2 对称闭包s（R） 54

2.4.3 传递闭包t（R） 55

习题2.4 58

2.5 等价关系 59

2.5.1 等价关系的定义 60

2.5.2 等价类 60

习题2.5 62

2.6 相容关系 63

2.6.1 相容关系的定义 63

2.6.2 相容类 65

习题2.6 65

2.7.1 偏序关系的定义 66

2.7 偏序关系 66

2.7.2 偏序集的哈斯图 67

2.7.3 偏序集中的特殊元素 68

习题2.7 70

第3章 命题逻辑 73

3.1 命题的有关概念 73

习题3.1 75

3.2 逻辑联结词 75

3.2.1 ？p 75

3.2.2 p∧q 76

3.2.3 p∨q 76

3.2.4 p？q 76

3.2.5 p→q 77

3.2.6 p？q 78

3.2.7 p↑q 78

3.2.9 p？q 79

习题3.2 79

3.2.8 p↓q 79

3.3 命题公式及其真值表 80

3.3.1 命题公式的定义 80

3.3.2 命题的符号化 81

3.3.3 命题公式的真值表 81

3.3.4 命题公式的类型 82

习题3.3 84

3.4 逻辑等值的命题公式 84

3.4.1 逻辑等值的定义 85

3.4.2 基本等值式 86

3.4.3 等值演算法 87

3.4.4 对偶原理 88

习题3.4 89

3.5 命题公式的范式 90

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

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

习题3.5 99

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

3.6.1 联结词的个数 100

3.6.2 功能完备联结词集 101

3.7 命题逻辑中的推理 103

习题3.6 103

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

3.7.2 基本推理规则 105

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

习题3.7 110

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

4.1.1 个体 113

第4章 谓词逻辑 113

4.1.2 谓词 114

4.1.3 量词 114

4.1.4 函词 116

习题4.1 117

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

4.2.1 谓词公式 117

4.2.2 命题的符号化 118

习题4.2 120

4.3.1 谓词公式的解释 121

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

4.3.2 谓词公式的类型 123

习题4.3 123

4.4 逻辑等值的谓词公式 125

4.4.1 谓词公式等值的定义 125

4.4.2 基本等值式 125

习题4.4 127

4.5 谓词公式的前束范式 127

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

习题4.5 128

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

4.6 谓词逻辑中的推理 129

4.6.1 逻辑蕴涵式 129

4.6.2 基本推理规则 129

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

习题4.6 132

第5章 群、环和域 135

5.1 代数结构简介 135

5.1.1 代数结构的定义 135

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

5.1.3 子代数 137

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

习题5.1 140

5.2 群的定义及性质 140

5.2.1 群的定义 141

5.2.2 群的性质 143

习题5.2 143

5.3 置换群 144

5.3.1 有限集合上的置换及表示 144

5.3.2 置换的复合运算 145

5.3.3 置换群的定义 145

习题5.3 146

5.4 阿贝尔群与循环群 146

5.4.1 阿贝尔群 146

5.4.2 循环群 147

习题5.4 150

5.5.1 子群 151

5.5 子群、群的陪集分解及正规子群 151

5.5.2 群的陪集分解 152

5.5.3 正规子群 154

习题5.5 156

5.6 群的同态与同构 157

5.6.1 群的同态 157

5.6.2 群的同构 158

5.6.3 群的自同态与自同构 160

习题5.6 160

5.7.1 环的定义 161

5.7 环 161

5.7.2 环的基本性质 162

5.7.3 子环及理想 163

习题5.7 164

5.8 域 165

5.8.1 域的定义 165

5.8.2 有限域 166

习题5.8 167

6.1.1 格的第一种定义 169

第6章 格与布尔代数 169

6.1 用偏序集定义的格 169

6.1.2 格的性质 171

6.1.3 格的保序映射 172

习题6.1 173

6.2 用代数结构定义的格 173

6.2.1 格的第二种定义 173

6.2.2 格的两种定义的等价性 174

6.2.3 子格 175

6.2.4 格的同态与同构 176

习题6.2 176

6.3 分配格 177

6.3.1 分配格的定义 177

6.3.2 分配格的性质 178

习题6.3 178

6.4.1 有界格 179

6.4.2 补元 179

6.4 有补格 179

习题6.4 180

6.5 布尔代数 181

6.5.1 布尔代数的格定义 181

6.5.2 布尔代数的性质 182

6.5.3 布尔代数的公理化定义 183

6.5.4 子布尔代数 185

6.5.5 布尔代数的同态与同构 185

习题6.5 186

6.6 有限布尔代数的结构 187

习题6.6 189

6.7 布尔表达式 190

6.7.1 布尔表达式的定义 190

6.7.2 布尔表达式的化简 191

6.7.3 布尔表达式的主范式 191

6.7.4 布尔函数 192

习题6.7 193

7.1 图的基本概念 195

7.1.1 图的定义 195

第7章 图论 195

7.1.2 邻接 197

7.1.3 关联 197

7.1.4 简单图 197

习题7.1 198

7.2 节点的度数 199

习题7.2 201

7.3.1 子图 202

7.3 子图、图的运算和图同构 202

7.3.2 图的运算 203

7.3.3 图同构 203

习题7.3 204

7.4 路与回路 205

7.4.1 路 205

7.4.2 回路 206

习题7.4 206

7.5 图的连通性 207

7.5.1 无向图的连通性 207

7.5.2 无向连通图的点连通度与边连通度 209

7.5.3 有向图的连通性 210

习题7.5 212

7.6 图的矩阵表示 212

7.6.1 图的邻接矩阵 213

7.6.2 图的可达矩阵 214

7.6.3 图的关联矩阵 214

习题7.6 216

7.7.2 最短路径 217

7.7.1 赋权图 217

7.7 赋权图及最短路径 217

习题7.7 219

第8章 几类特殊的图 221

8.1 欧拉图 221

8.1.1 欧拉图的有关概念 221

8.1.2 欧拉定理 222

8.1.3 中国邮递员问题 223

习题8.1 223

8.2.1 哈密尔顿图的有关概念 224

8.2 哈密尔顿图 224

8.2.2 哈密尔顿图的必要条件 225

8.2.3 哈密尔顿图的充分条件 226

8.2.4 旅行商问题 227

习题8.2 228

8.3 无向树 229

8.3.1 无向树的定义 229

8.3.2 无向树的性质 229

8.3.3 生成树 231

8.3.4 最小生成树 232

习题8.3 233

8.4 有向树 234

8.4.1 有向树的定义 234

8.4.2 根树 234

8.4.3 m叉树 235

8.4.4 有序树 238

8.4.5 定位2叉树 239

习题8.4 241

8.5 平面图 242

8.5.1 平面图的有关概念 243

8.5.2 欧拉公式 244

8.5.3 库拉托夫斯基定理 245

8.5.4 平面图的对偶图 245

习题8.5 246

8.6 平面图的面着色 247

8.6.1 平面图的面着色定义 248

8.6.2 图的节点着色 248

8.6.3 任意图的边着色 249

习题8.6 250

8.7 二部图及其匹配 251

8.7.1 二部图 251

8.7.2 匹配 252

习题8.7 252

附录A 符号索引 255

附录B 中英文名词索引 259

附录C 习题答案及提示 263

参考文献 289