离散数学及其应用PDF电子书下载

第一篇 预备知识 1

引言 1

第1章 集合论 3

1.0 内容提要 3

1.1 本章学习要求 3

1.2 集合 4

1.2.1 集合的表示 5

1.2.2 集合与元素的关系 6

1.2.3 集合与集合的关系 7

1.2.4 几个特殊的集合 8

1.2.5 集合的运算 10

1.2.6 集合的难点 13

1.3 无限集 13

1.3.1 可数集合和不可数集合 13

1.3.2 无限集的难点 16

1.4 集合的应用 16

1.5 本章总结 18

1.6 习题 19

第2章 计数问题 23

2.0 内容提要 23

2.1 本章学习要求 23

2.2 基本原理 24

2.2.1 乘法原理 24

2.2.2 加法原理 25

2.2.3 基本原理的难点 26

2.3 排列与组合 27

2.3.1 排列问题 27

2.3.2 组合问题 29

2.3.3 排列与组合的难点 30

2.4 容斥原理与鸽笼原理 31

2.4.1 容斥原理 31

2.4.2 鸽笼原理 34

2.4.3 容斥原理与鸽笼原理的难点 34

2.5 离散概率简介 35

2.5.1 基本概念 35

2.5.2 离散概率函数 36

2.5.3 离散概率简介的难点 39

2.6 递归关系 39

2.6.1 递归关系 39

2.6.2 递归关系的难点 40

2.7 计数问题的应用 41

2.8 本章总结 43

2.9 习题 44

第二篇 数理逻辑 47

引言 47

第3章 命题逻辑 49

3.0 内容提要 49

3.1 本章学习要求 49

3.2 命题与命题联结词 50

3.2.1 命题 50

3.2.2 命题联结词 51

3.2.3 联结词理解难点 56

3.2.4 命题联结词的应用 57

3.3 命题公式、解释与真值表 58

3.3.1 命题公式 59

3.3.2 命题公式的解释与真值表 61

3.3.3 命题公式的分类 64

3.3.4 命题公式的基本等价关系 66

3.3.5 命题公式的难点 69

3.3.6 命题公式的应用 70

3.4 联结词的完备集 73

3.4.1 命题联结词的个数 73

3.4.2 联结词的完备集 74

3.4.3 联结词的完备集的应用 75

3.5 公式的标准型——范式 77

3.5.1 析取范式和合取范式 77

3.5.2 主析取范式和主合取范式 79

3.5.3 范式的难点 86

3.5.4 范式的应用 86

3.6 本章总结 88

3.7 习题 89

第4章 谓词逻辑 92

4.0 内容提要 93

4.1 本章学习要求 93

4.2 谓词逻辑中的基本概念与表示 93

4.2.1 谓词 94

4.2.2 量词 96

4.2.3 谓词的语言翻译 99

4.2.4 谓词翻译难点 100

4.2.5 谓词翻译的应用 100

4.3 谓词合式公式与解释 101

4.3.1 谓词的合式公式 102

4.3.2 自由变元和约束变元 103

4.3.3 谓词合式公式的解释 105

4.3.4 谓词合式公式的分类 106

4.3.5 谓词合式公式的基本等价关系 108

4.3.6 谓词合式公式难点 110

4.3.7 谓词合式公式的应用 110

4.4 公式的标准型——范式 111

4.4.1 前束范式 111

4.4.2 Skolem标准型 112

4.4.3 范式的难点 113

4.5 本章总结 113

4.6 习题 115

第5章 推理与证明技术 118

5.0 内容提要 118

5.1 本章学习要求 118

5.2 命题逻辑的推理理论 118

5.2.1 推理的基本概念和推理形式 119

5.2.2 判断有效结论的常用方法 120

5.2.3 命题逻辑推理的难点 126

5.2.4 命题逻辑推理的应用 127

5.3 谓词逻辑的推理理论 129

5.3.1 谓词演算的演绎与推理 129

5.3.2 谓词演算的综合推理方法 131

5.3.3 谓词逻辑推理的难点 135

5.3.4 谓词逻辑推理的应用 135

5.4 数学归纳法 140

5.4.1 数学归纳法原理 140

5.4.2 数学归纳法应用 142

5.5 按定义证明方法 143

5.5.1 按定义证明方法原理 143

5.5.2 按定义证明方法应用实例 144

5.6 本章总结 145

5.7 习题 146

第三篇 二元关系 149

引言 149

第6章 二元关系 151

6.0 内容提要 151

6.1 本章学习要求 151

6.2 二元关系 152

6.2.1 序偶和笛卡儿积 152

6.2.2 关系的定义 155

6.2.3 关系的表示法 157

6.2.4 二元关系的难点 161

6.2.5 关系的应用 161

6.3 关系的运算 163

6.3.1 关系的复合运算 164

6.3.2 关系的逆运算 167

6.3.3 关系的幂运算 170

6.3.4 关系运算的难点 172

6.3.5 关系运算的应用 172

6.4 关系的性质 173

6.4.1 关系性质的定义 173

6.4.2 关系性质的判定定理 181

6.4.3 关系性质的保守性 182

6.4.4 关系性质的难点 183

6.4.5 关系性质的应用 183

6.5 关系的闭包运算 184

6.5.1 关系的闭包 184

6.5.2 关系闭包的难点 188

6.5.3 关系闭包的应用 188

6.6 本章总结 189

6.7 习题 190

第7章 特殊关系 194

7.0 内容提要 194

7.1 本章学习要求 194

7.2 等价关系 195

7.2.1 等价关系 195

7.2.2 集合的划分 197

7.2.3 等价类与商集 198

7.2.4 等价关系与划分 200

7.2.5 等价关系的难点 203

7.2.6 等价关系的应用 203

7.3 次序关系 204

7.3.1 拟序关系 205

7.3.2 偏序关系 205

7.3.3 全序关系 212

7.3.4 良序关系 213

7.3.5 次序关系的难点 214

7.3.6 次序关系的应用 214

7.4 本章总结 216

7.5 习题 217

第8章 函数 220

8.0 内容提要 220

8.1 本章学习要求 220

8.2 函数 221

8.2.1 函数的定义 221

8.2.2 函数的类型 223

8.2.3 常用函数 226

8.2.4 函数的难点 227

8.2.5 函数的应用 227

8.3 函数的运算 229

8.3.1 函数的复合运算 229

8.3.2 函数的逆运算 231

8.3.3 函数运算的难点 232

8.3.4 函数运算的应用 232

8.4 置换函数 233

8.4.1 基本概念 234

8.4.2 置换函数的难点 234

8.4.3 置换函数的应用 235

8.5 本章总结 235

8.6 习题 236

第四篇 图论 239

引言 239

第9章 图 241

9.0 内容提要 241

9.1 本章学习要求 241

9.2 图的基本概念 242

9.2.1 图的定义 242

9.2.2 图的表示 243

9.2.3 图的操作 245

9.2.4 邻接点与邻接边 245

9.2.5 图的分类 246

9.2.6 子图与补图 248

9.2.7 结点的度数与握手定理 251

9.2.8 图的同构 253

9.2.9 图的难点 254

9.2.10 图的应用 254

9.3 通路、回路与连通性 255

9.3.1 通路与回路 255

9.3.2 无向图的连通性 263

9.3.3 有向图的连通性 264

9.3.4 通路、回路与连通性的难点 266

9.3.5 通路、回路与连通性的应用 267

9.4 本章总结 273

9.5 习题 273

第10章 树 277

10.0 内容提要 277

10.1 本章学习要求 277

10.2 树 278

10.2.1 树的定义与性质 278

10.2.2 生成树 280

10.2.3 最小生成树 283

10.2.4 无向树的难点 285

10.2.5 无向树的应用 285

10.3 根树 285

10.3.1 根树的定义与分类 285

10.3.2 根树的遍历 289

10.3.3 最优树与哈夫曼算法 291

10.3.4 根树的难点 293

10.3.5 根树的应用 294

10.4 本章总结 297

10.5 习题 298

第11章 特殊图 300

11.0 内容提要 300

11.1 本章学习要求 300

11.2 欧拉图 301

11.2.1 欧拉图的引入与定义 301

11.2.2 欧拉图的判定 302

11.2.3 欧拉图的难点 304

11.2.4 欧拉图的应用 305

11.3 哈密顿图 306

11.3.1 哈密顿图的引入与定义 306

11.3.2 哈密顿图的判定 308

11.3.3 哈密顿图的难点 311

11.3.4 哈密顿图的应用 312

11.4 偶图 316

11.4.1 偶图的定义 316

11.4.2 偶图的判定 317

11.4.3 匹配 318

11.4.4 偶图的难点 319

11.4.5 偶图的应用 319

11.5 平面图 321

11.5.1 平面图的定义 321

11.5.2 平面图的简单判定方法——观察法 321

11.5.3 欧拉公式 322

11.5.4 库拉托夫斯基定理 325

11.5.5 对偶图 326

11.5.6 图的着色 327

11.5.7 平面图的难点 330

11.5.8 平面图的应用 330

11.6 本章总结 332

11.7 习题 333

第五篇 代数系统 337

引言 337

第12章 代数系统 339

12.0 内容提要 339

12.1 本章学习要求 339

12.2 代数系统 340

12.2.1 代数运算 340

12.2.2 代数系统与子代数 343

12.2.3 代数系统中的难点 344

12.2.4 代数系统的应用 344

12.3 代数系统的基本运算和性质 345

12.3.1 二元运算律 345

12.3.2 代数系统的性质 350

12.3.3 代数系统性质的难点 358

12.3.4 代数系统性质的应用 358

12.4 同态与同构 359

12.4.1 同态与同构 359

12.4.2 同态的性质 362

12.4.3 同态与同构的难点 363

12.4.4 同态与同构的应用 364

12.5 本章总结 365

12.6 习题 366

第13章 群 369

13.0 内容提要 369

13.1 本章学习要求 369

13.2 半群与含幺半群 370

13.2.1 半群与含幺半群 370

13.2.2 元素的幂 372

13.2.3 循环半群 373

13.2.4 半群与含幺半群的难点 375

13.2.5 半群的应用 375

13.3 群及其性质 376

13.3.1 群的定义及基本性质 378

13.3.2 元素的周期 380

13.3.3 子群 383

13.3.4 群的同态 389

13.3.5 群及子群的难点 391

13.3.6 群的应用 391

13.4 特殊群 393

13.4.1 交换群（阿贝尔群） 393

13.4.2 循环群 394

13.4.3 置换群 397

13.4.4 特殊群的难点 398

13.4.5 特殊群的应用 398

13.5 陪集与拉格朗日定理 400

13.5.1 陪集 400

13.5.2 拉格朗日定理 403

13.5.3 陪集与拉格朗日定理的难点 404

13.5.4 拉格朗日定理的应用 404

13.6 正规子群与商群 405

13.6.1 正规子群（不变子群） 405

13.6.2 商群 407

13.6.3 正规子群与商群的难点 410

13.6.4 商群的应用 410

13.7 本章总结 411

13.8 习题 412

第14章 环与域 415

14.0 内容提要 415

14.1 本章学习要求 415

14.2 环与域 416

14.2.1 环与域的定义 416

14.2.2 环与域的性质 418

14.2.3 环与域的应用 419

14.3 本章总结 420

14.4 习题 421

第15章 格与布尔代数 422

15.0 内容提要 422

15.1 本章学习要求 423

15.2 格 423

15.2.1 偏序格 423

15.2.2 代数格 425

15.2.3 偏序格与代数格的等价性 426

15.2.4 格的性质 428

15.2.5 子格与格同态 429

15.2.6 分配格与模格 432

15.2.7 有界格与有补格 434

15.2.8 格的难点 437

15.2.9 格的应用 438

15.3 布尔代数 438

15.3.1 布尔代数 438

15.3.2 布尔表达式 441

15.3.3 布尔代数的难点 444

15.3.4 布尔代数的应用 445

15.4 本章总结 448

15.5 习题 449

参考文献 451