离散数学 第3版PDF电子书下载

第一部分 数理逻辑 1

第1章 命题逻辑演算系统 1

1.1 命题逻辑演算系统的概念 1

1.1.1 命题 1

1.1.2 联结词 4

1.2 命题公式与真值表 8

1.2.1 命题公式与命题函数 8

1.2.2 命题公式的真值表 10

1.2.3 永真式与永假式 12

1.2.4 其他联结词 13

1.2.5 最小联结词组 14

1.3 等价式与蕴含式 16

1.3.1 命题公式的等价 16

1.3.2 命题公式的蕴含 17

1.3.3 等价的判定 18

1.3.4 蕴含的判定 19

1.4 范式与对偶式 21

1.4.1 对偶公式 21

1.4.2 范式 23

1.4.3 主范式 24

1.5 命题演算的推理理论 29

1.5.1 有效推理的概念 29

1.5.2 推理过程 30

习题 35

第2章 一阶谓词逻辑演算系统 39

2.1 谓词命题 39

2.1.1 原子命题的谓词表示 39

2.1.2 量词 40

2.1.3 论域 41

2.1.4 含量词的谓词命题 42

2.2 谓词命题公式及约束变元 44

2.2.1 谓词命题公式 44

2.2.2 谓词公式的解释与赋值 45

2.2.3 谓词公式的等价与蕴含 47

2.2.4 约束变元与自由变元 48

2.2.5 代入实例 49

2.3 谓词逻辑演算的等价式和蕴含式 50

2.3.1 等价式与蕴含式 51

2.3.2 多元谓词及其量词 52

2.3.3 前束范式与Skolem范式 53

2.4 谓词逻辑演算的推理理论 54

2.4.1 谓词逻辑的有效推理 55

2.4.2 卸下、添加量词的规则 55

习题 60

第二部分 集合论 63

第3章 集合与关系 63

3.1 集合及集合运算 63

3.1.1 集合的概念 63

3.1.2 集合的表示法 64

3.1.3 集合公理 64

3.1.4 集合的运算 69

3.1.5 集合运算的性质 71

3.2 三个基本原理 74

3.2.1 排列组合的复习 74

3.2.2 鸽巢原理 76

3.2.3 包含排斥原理 76

3.2.4 生成函数 78

3.3 笛卡儿积与关系 81

3.3.1 序偶与笛卡儿积 81

3.3.2 关系的概念 84

3.3.3 关系的表示 85

3.3.4 关系的性质 86

3.4 关系的运算 89

3.4.1 关系的集合运算 89

3.4.2 关系的复合运算 90

3.4.3 关系的逆运算 93

3.4.4 关系的闭包运算 95

3.5 等价关系与相容关系 99

3.5.1 划分与覆盖 99

3.5.2 等价关系与等价类 101

3.5.3 相容关系与相容类 104

3.6 次序关系 106

3.6.1 偏序关系 106

3.6.2 HASSE图 107

3.6.3 上确界与下确界 109

3.6.4 良序关系 110

习题 111

第4章 函数 117

4.1 函数的概念 117

4.1.1 函数的定义 117

4.1.2 函数的特性 119

4.2 复合函数与逆函数 121

4.2.1 复合函数 121

4.2.2 逆函数 122

4.2.3 函数的运算性质 123

4.3 序数与自然数 124

4.3.1 等势与劣势 124

4.3.2 自然数 126

4.3.3 序数 129

4.4 基数 131

4.4.1 关于基数 131

4.4.2 可数集与不可数集 132

4.4.3 基数的比较 134

习题 136

第三部分 代数系统 138

第5章 代数结构 138

5.1 置换及其运算 138

5.1.1 置换与轮换 138

5.1.2 轮换的运算性质及方法 141

5.1.3 几个轮换运算的等式 145

5.2 数论初步 145

5.2.1 整数 145

5.2.2 辗转相除法 147

5.2.3 整数的互质性 149

5.2.4 整数的同余性 150

5.3 代数系统的概念 154

5.3.1 代数系统 154

5.3.2 子代数系统 158

5.4 代数结构与子结构 159

5.4.1 代数结构 159

5.4.2 子代数结构 165

5.5 同态、同构与同余 167

5.5.1 同态与同构 167

5.5.2 同余关系 171

5.6 几种典型的群 174

5.6.1 交换群 174

5.6.2 循环群 175

5.6.3 置换群 176

5.6.4 变换群与Cayley定理 178

5.7 陪集与拉格朗日定理 179

5.7.1 陪集 180

5.7.2 拉格朗日定理 181

5.7.3 正规子群 183

5.7.4 同态定理 185

5.8 商代数与积代数 186

5.8.1 商代数 186

5.8.2 积代数 187

5.9 环与域 188

5.9.1 环 189

5.9.2 整环和域 190

5.9.3 环同态与理想 192

习题 194

第6章 格与布尔代数 200

6.1 格的概念 200

6.1.1 格与子格 200

6.1.2 格的性质 203

6.1.3 格的同态 206

6.2 几种典型的格 208

6.2.1 分配格 209

6.2.2 模格 211

6.2.3 有界格 213

6.2.4 有补格 214

6.2.5 布尔格 215

6.3 Stone表示定理 219

6.4 布尔表达式 221

6.4.1 布尔表达式的定义 221

6.4.2 布尔函数 222

6.4.3 布尔表达式的析取范式与合取范式 223

习题 226

第四部分 图论 229

第7章 图论 229

7.1 图的基本概念 229

7.1.1 图的概念与定义 229

7.1.2 常用术语 230

7.1.3 顶的度数 232

7.1.4 子图与补图 233

7.1.5 图同构 234

7.1.6 图的运算 235

7.2 路与连通性 237

7.2.1 路与通路 237

7.2.2 无向连通 238

7.2.3 有向连通 241

7.3 图的矩阵 243

7.3.1 邻接矩阵 243

7.3.2 完全关联矩阵 245

7.3.3 可达矩阵 249

7.3.4 回路矩阵 250

7.3.5 割集矩阵 251

7.4 欧拉图与哈密尔顿图 252

7.4.1 欧拉图 253

7.4.2 哈密尔顿图 256

7.5 树及其应用 259

7.5.1 无向树 259

7.5.2 生成树 262

7.5.3 生成树的个数 264

7.5.4 有向树及根树 267

7.5.5 Huffman树 269

7.5.6 树的应用 270

7.6 通路问题 272

7.6.1 关键路径 272

7.6.2 最短通路 274

7.6.3 最优通路 276

7.7 平面图 279

7.7.1 平面图的概念 279

7.7.2 对偶图 281

7.8 图的着色 282

7.8.1 色数与五色定理 283

7.8.2 色多项式 284

7.9 二分图与匹配 288

7.9.1 独立集与二分图 288

7.9.2 匹配 289

7.10 网络流 293

7.10.1 网络流的概念 294

7.10.2 最大流与最小割 295

习题 298

中英文索引 306

参考文献 316