离散数学及其应用 原书第7版PDF电子书下载

第1章 基础：逻辑和证明 1

1.1 命题逻辑 1

1.1.1 引言 1

1.1.2 命题 1

1.1.3 条件语句 4

1.1.4 复合命题的真值表 8

1.1.5 逻辑运算符的优先级 8

1.1.6 逻辑运算和位运算 8

练习 10

1.2 命题逻辑的应用 15

1.2.1 引言 15

1.2.2 语句翻译 15

1.2.3 系统规范说明 16

1.2.4 布尔搜索 16

1.2.5 逻辑谜题 17

1.2.6 逻辑电路 18

练习 19

1.3 命题等价式 22

1.3.1 引言 22

1.3.2 逻辑等价式 23

1.3.3 德·摩根律的运用 25

1.3.4 构造新的逻辑等价式 25

1.3.5 命题的可满足性 26

1.3.6 可满足性的应用 27

1.3.7 可满足性问题求解 29

练习 30

1.4 谓词和量词 32

1.4.1 引言 32

1.4.2 谓词 33

1.4.3 量词 35

1.4.4 约束论域的量词 37

1.4.5 量词的优先级 38

1.4.6 变量绑定 38

1.4.7 涉及量词的逻辑等价式 38

1.4.8 量化表达式的否定 39

1.4.9 语句到逻辑表达式的翻译 40

1.4.10 系统规范说明中量词的使用 42

1.4.11 选自路易斯·卡罗尔的例子 42

1.4.12 逻辑程序设计 43

练习 44

1.5 嵌套量词 49

1.5.1 引言 49

1.5.2 理解涉及嵌套量词的语句 49

1.5.3 量词的顺序 50

1.5.4 数学语句到嵌套量词语句的翻译 51

1.5.5 嵌套量词到自然语言的翻译 52

1.5.6 汉语语句到逻辑表达式的翻译 52

1.5.7 嵌套量词的否定 53

练习 54

1.6 推理规则 59

1.6.1 引言 59

1.6.2 命题逻辑的有效论证 60

1.6.3 命题逻辑的推理规则 61

1.6.4 使用推理规则建立论证 62

1.6.5 消解律 63

1.6.6 谬误 64

1.6.7 量化命题的推理规则 64

1.6.8 命题和量化命题推理规则的组合使用 66

练习 66

1.7 证明导论 69

1.7.1 引言 69

1.7.2 一些专用术语 70

1.7.3 理解定理是如何陈述的 70

1.7.4 证明定理的方法 70

1.7.5 直接证明法 71

1.7.6 反证法 71

1.7.7 归谬证明法 73

1.7.8 证明中的错误 75

1.7.9 良好的开端 76

练习 77

1.8 证明的方法和策略 78

1.8.1 引言 78

1.8.2 穷举证明法和分情形证明法 78

1.8.3 存在性证明 81

1.8.4 唯一性证明 84

1.8.5 证明策略 84

1.8.6 寻找反例 86

1.8.7 证明策略实践 86

1.8.8 拼接 87

1.8.9 开放问题的作用 89

1.8.10 其他证明方法 90

练习 90

关键术语和结论 92

复习题 94

补充练习 95

计算机课题 97

计算和探索 97

写作课题 98

第2章 基本结构：集合、函数、序列、求和与矩阵 99

2.1 集合 99

2.1.1 引言 99

2.1.2 文氏图 101

2.1.3 子集 102

2.1.4 集合的大小 103

2.1.5 幂集 103

2.1.6 笛卡儿积 104

2.1.7 使用带量词的集合符号 105

2.1.8 真值集和量词 106

练习 106

2.2 集合运算 108

2.2.1 引言 108

2.2.2 集合恒等式 110

2.2.3 扩展的并集和交集 112

2.2.4 集合的计算机表示 114

练习 115

2.3 函数 118

2.3.1 引言 118

2.3.2 一对一函数和映上函数 120

2.3.3 反函数和函数组合 122

2.3.4 函数的图 124

2.3.5 一些重要的函数 125

2.3.6 部分函数 127

练习 128

2.4 序列与求和 132

2.4.1 引言 132

2.4.2 序列 133

2.4.3 递推关系 134

2.4.4 特殊的整数序列 136

2.4.5 求和 137

练习 141

2.5 集合的基数 144

2.5.1 引言 144

2.5.2 可数集 145

2.5.3 不可数集合 147

练习 149

2.6 矩阵 151

2.6.1 引言 151

2.6.2 矩阵算术 152

2.6.3 矩阵的转置和幂 153

2.6.4 0-1矩阵 153

练习 155

关键术语和结论 158

复习题 160

补充练习 160

计算机课题 162

计算和探索 163

写作课题 163

第3章 算法 164

3.1 算法 164

3.1.1 引言 164

3.1.2 搜索算法 166

3.1.3 排序 167

3.1.4 贪婪算法 170

3.1.5 停机问题 172

练习 173

3.2 函数的增长 176

3.2.1 引言 176

3.2.2 大O记号 176

3.2.3 一些重要函数的大O估算 179

3.2.4 函数组合的增长 182

3.2.5 大Ω与大Θ记号 183

练习 184

3.3 算法的复杂度 187

3.3.1 引言 187

3.3.2 时间复杂度 188

3.3.3 矩阵乘法的复杂度 190

3.3.4 算法范型 191

3.3.5 理解算法的复杂度 192

练习 195

关键术语和结论 198

复习题 199

补充练习 200

计算机课题 203

计算和探索 203

写作课题 203

第4章 数论和密码学 204

4.1 整除性和模算术 204

4.1.1 引言 204

4.1.2 除法 204

4.1.3 除法算法 205

4.1.4 模算术 206

4.1.5 模m算术 208

练习 208

4.2 整数表示和算法 210

4.2.1 引言 210

4.2.2 整数表示 210

4.2.3 整数运算算法 213

4.2.4 模指数运算 216

练习 217

4.3 素数和最大公约数 219

4.3.1 引言 219

4.3.2 素数 220

4.3.3 试除法 220

4.3.4 埃拉托斯特尼筛法 221

4.3.5 关于素数的猜想和开放问题 224

4.3.6 最大公约数和最小公倍数 225

4.3.7 欧几里得算法 227

4.3.8 gcd的线性组合表示 228

练习 230

4.4 求解同余方程 233

4.4.1 引言 233

4.4.2 线性同余方程 233

4.4.3 中国剩余定理 235

4.4.4 大整数的计算机算术 236

4.4.5 费马小定理 237

4.4.6 伪素数 238

4.4.7 原根和离散对数 239

练习 240

4.5 同余应用 243

4.5.1 散列函数 243

4.5.2 伪随机数 244

4.5.3 校验码 244

练习 246

4.6 密码学 248

4.6.1 引言 248

4.6.2 古典密码学 248

4.6.3 公钥密码学 251

4.6.4 RSA密码系统 251

4.6.5 RSA加密 252

4.6.6 RSA解密 253

4.6.7 用RSA作为公钥系统 254

4.6.8 密码协议 254

练习 255

关键术语和结论 257

复习题 259

补充练习 260

计算机课题 262

计算和探索 262

写作课题 263

第5章 归纳与递归 264

5.1 数学归纳法 264

5.1.1 引言 264

5.1.2 数学归纳法 265

5.1.3 为什么数学归纳法是有效的 266

5.1.4 数学归纳法的优点与缺点 266

5.1.5 利用数学归纳法证明的例子 266

5.1.6 使用数学归纳法时犯的错误 275

5.1.7 运用数学归纳法证明的原则 276

练习 276

5.2 强归纳法与良序性 281

5.2.1 引言 281

5.2.2 强归纳法 282

5.2.3 利用强归纳法证明的例子 283

5.2.4 计算几何学中使用强归纳法 285

5.2.5 利用良序性证明 287

练习 288

5.3 递归定义与结构归纳法 291

5.3.1 引言 291

5.3.2 递归地定义函数 291

5.3.3 递归地定义集合与结构 294

5.3.4 结构归纳法 298

5.3.5 广义归纳法 300

练习 300

5.4 递归算法 305

5.4.1 引言 305

5.4.2 证明递归算法的正确性 307

5.4.3 递归与迭代 308

5.4.4 归并排序 309

练习 312

5.5 程序正确性 314

5.5.1 引言 314

5.5.2 程序验证 314

5.5.3 推理规则 315

5.5.4 条件语句 315

5.5.5 循环不变量 316

练习 318

关键术语和结论 319

复习题 320

补充练习 321

计算机课题 325

计算和探索 325

写作课题 326

第6章 计数 327

6.1 计数的基础 327

6.1.1 引言 327

6.1.2 基本的计数原则 327

6.1.3 比较复杂的计数问题 331

6.1.4 减法法则（两个集合的容斥原理） 332

6.1.5 除法法则 333

6.1.6 树图 333

练习 334

6.2 鸽巢原理 338

6.2.1 引言 338

6.2.2 广义鸽巢原理 339

6.2.3 鸽巢原理的几个简单应用 341

练习 342

6.3 排列与组合 344

6.3.1 引言 344

6.3.2 排列 345

6.3.3 组合 346

练习 348

6.4 二项式系数和恒等式 351

6.4.1 二项式定理 351

6.4.2 帕斯卡恒等式和三角形 353

6.4.3 其他的二项式系数恒等式 354

练习 355

6.5 排列与组合的推广 358

6.5.1 引言 358

6.5.2 有重复的排列 358

6.5.3 有重复的组合 358

6.5.4 具有不可区别物体的集合的排列 361

6.5.5 把物体放入盒子 362

练习 364

6.6 生成排列和组合 367

6.6.1 引言 367

6.6.2 生成排列 368

6.6.3 生成组合 369

练习 370

关键术语和结论 371

复习题 372

补充练习 373

计算机课题 376

计算和探索 376

写作课题 377

第7章 离散概率 378

7.1 离散概率引论 378

7.1.1 引言 378

7.1.2 有限概率 378

7.1.3 事件组合的概率 381

7.1.4 概率的推理 381

练习 382

7.2 概率论 384

7.2.1 引言 384

7.2.2 概率指派 384

7.2.3 事件的组合 385

7.2.4 条件概率 386

7.2.5 独立性 387

7.2.6 伯努利试验与二项分布 388

7.2.7 随机变量 389

7.2.8 生日问题 390

7.2.9 蒙特卡罗算法 391

7.2.10 概率方法 392

练习 393

7.3 贝叶斯定理 396

7.3.1 引言 396

7.3.2 贝叶斯定理 396

7.3.3 贝叶斯垃圾邮件过滤器 399

练习 401

7.4 期望值和方差 403

7.4.1 引言 403

7.4.2 期望值 404

7.4.3 期望的线性性质 405

7.4.4 平均情形下的计算复杂度 407

7.4.5 几何分布 408

7.4.6 独立随机变量 409

7.4.7 方差 410

7.4.8 切比雪夫不等式 413

练习 414

关键术语和结论 416

复习题 417

补充练习 418

计算机课题 422

计算和探索 422

写作课题 422

第8章 高级计数技术 424

8.1 递推关系的应用 424

8.1.1 引言 424

8.1.2 用递推关系构造模型 425

8.1.3 算法与递推关系 429

练习 431

8.2 求解线性递推关系 435

8.2.1 引言 435

8.2.2 求解常系数线性齐次递推关系 436

8.2.3 常系数线性非齐次的递推关系 439

练习 441

8.3 分治算法和递推关系 444

8.3.1 引言 444

8.3.2 分治递推关系 445

练习 450

8.4 生成函数 452

8.4.1 引言 452

8.4.2 关于幂级数的有用事实 452

8.4.3 计数问题与生成函数 455

8.4.4 使用生成函数求解递推关系 458

8.4.5 使用生成函数证明恒等式 459

练习 459

8.5 容斥 464

8.5.1 引言 464

8.5.2 容斥原理 464

练习 467

8.6 容斥原理的应用 468

8.6.1 引言 468

8.6.2 容斥原理的另一种形式 469

8.6.3 埃拉托色尼筛 469

8.6.4 映上函数的个数 470

8.6.5 错位排列 471

练习 472

关键术语和结论 473

复习题 474

补充练习 475

计算机课题 478

计算和探索 478

写作课题 479

第9章 关系 480

9.1 关系及其性质 480

9.1.1 引言 480

9.1.2 函数作为关系 481

9.1.3 集合的关系 481

9.1.4 关系的性质 482

9.1.5 关系的组合 484

练习 485

9.2 n元关系及其应用 489

9.2.1 引言 489

9.2.2 n元关系 489

9.2.3 数据库和关系 490

9.2.4 n元关系的运算 491

9.2.5 SQL 493

练习 493

9.3 关系的表示 495

9.3.1 引言 495

9.3.2 用矩阵表示关系 495

9.3.3 用图表示关系 497

练习 498

9.4 关系的闭包 500

9.4.1 引言 500

9.4.2 闭包 501

9.4.3 有向图中的路径 501

9.4.4 传递闭包 502

9.4.5 沃舍尔算法 505

练习 507

9.5 等价关系 509

9.5.1 引言 509

9.5.2 等价关系 509

9.5.3 等价类 510

9.5.4 等价类与划分 512

练习 514

9.6 偏序 518

9.6.1 引言 518

9.6.2 字典顺序 520

9.6.3 哈塞图 521

9.6.4 极大元与极小元 522

9.6.5 格 524

9.6.6 拓扑排序 525

练习 527

关键术语和结论 532

复习题 533

补充练习 534

计算机课题 538

计算和探索 538

写作课题 538

第10章 图 540

10.1 图和图模型 540

10.1.1 图模型 543

练习 546

10.2 图的术语和几种特殊的图 549

10.2.1 引言 549

10.2.2 基本术语 549

10.2.3 一些特殊的简单图 551

10.2.4 二分图 552

10.2.5 二分图和匹配 553

10.2.6 特殊类型图的一些应用 556

10.2.7 从旧图构造新图 557

练习 559

10.3 图的表示和图的同构 563

10.3.1 引言 563

10.3.2 图的表示 563

10.3.3 邻接矩阵 563

10.3.4 关联矩阵 565

10.3.5 图的同构 566

10.3.6 判定两个简单图是否同构 566

练习 568

10.4 连通性 573

10.4.1 引言 573

10.4.2 通路 573

10.4.3 无向图的连通性 575

10.4.4 图是如何连通的 576

10.4.5 有向图的连通性 578

10.4.6 通路与同构 579

10.4.7 计算顶点之间的通路数 580

练习 580

10.5 欧拉通路与哈密顿通路 585

10.5.1 引言 585

10.5.2 欧拉通路与欧拉回路 585

10.5.3 哈密顿通路与哈密顿回路 589

10.5.4 哈密顿回路的应用 592

练习 593

10.6 最短通路问题 597

10.6.1 引言 597

10.6.2 最短通路算法 599

10.6.3 旅行商问题 603

练习 604

10.7 平面图 607

10.7.1 引言 607

10.7.2 欧拉公式 609

10.7.3 库拉图斯基定理 611

练习 612

10.8 图着色 614

10.8.1 引言 614

10.8.2 图着色的应用 618

练习 619

关键术语和结论 622

复习题 625

补充练习 626

计算机课题 630

计算和探索 631

写作课题 631

第11章 树 633

11.1 树的概述 633

11.1.1 有根树 634

11.1.2 树作为模型 637

11.1.3 树的性质 638

练习 641

11.2 树的应用 643

11.2.1 引言 643

11.2.2 二叉搜索树 643

11.2.3 决策树 646

11.2.4 前缀码 647

11.2.5 博弈树 649

练习 653

11.3 树的遍历 656

11.3.1 引言 656

11.3.2 通用地址系统 656

11.3.3 遍历算法 657

11.3.4 中缀、前缀和后缀记法 662

练习 665

11.4 生成树 667

11.4.1 引言 667

11.4.2 深度优先搜索 669

11.4.3 宽度优先搜索 671

11.4.4 回溯的应用 672

11.4.5 有向图中的深度优先搜索 674

练习 675

11.5 最小生成树 678

11.5.1 引言 678

11.5.2 最小生成树算法 678

练习 681

关键术语和结论 683

复习题 685

补充练习 686

计算机课题 688

计算和探索 689

写作课题 689

第12章 布尔代数 690

12.1 布尔函数 690

12.1.1 引言 690

12.1.2 布尔表达式和布尔函数 691

12.1.3 布尔代数恒等式 692

12.1.4 对偶性 694

12.1.5 布尔代数的抽象定义 694

练习 695

12.2 布尔函数的表示 696

12.2.1 积之和展开式 696

12.2.2 函数完备性 698

练习 698

12.3 逻辑门电路 699

12.3.1 引言 699

12.3.2 门的组合 699

12.3.3 电路的例子 700

12.3.4 加法器 702

练习 703

12.4 电路的极小化 704

12.4.1 引言 704

12.4.2 卡诺图 705

12.4.3 无需在意的条件 710

12.4.4 奎因-莫可拉斯基方法 712

练习 715

关键术语和结论 716

复习题 718

补充练习 718

计算机课题 720

计算和探索 720

写作课题 720

第13章 计算模型 722

13.1 语言和文法 722

13.1.1 引言 722

13.1.2 短语结构文法 723

13.1.3 短语结构文法的类型 725

13.1.4 派生树 726

13.1.5 巴克斯-诺尔范式 727

练习 728

13.2 带输出的有限状态机 732

13.2.1 引言 732

13.2.2 带输出的有限状态机 733

练习 736

13.3 不带输出的有限状态机 738

13.3.1 引言 738

13.3.2 串的集合 738

13.3.3 有限状态自动机 738

13.3.4 有限状态机的语言识别 739

13.3.5 非确定性的有限状态自动机 743

练习 746

13.4 语言的识别 750

13.4.1 引言 750

13.4.2 克莱因定理 751

13.4.3 正则集合和正则文法 754

13.4.4 一个不能由有限状态自动机识别的集合 756

13.4.5 一些更强大的机器 756

练习 757

13.5 图灵机 759

13.5.1 引言 759

13.5.2 图灵机的定义 760

13.5.3 用图灵机识别集合 762

13.5.4 用图灵机计算函数 763

13.5.5 不同类型的图灵机 763

13.5.6 丘奇-图灵论题 764

13.5.7 计算复杂度、可计算性和可判定性 764

练习 767

关键术语和结论 769

复习题 770

补充练习 771

计算机课题 773

计算和探索 773

写作课题 773

附录A 实数和正整数的公理 775

附录B 指数与对数函数 779

附录C 伪代码 781

推荐读物 785

参考文献 789