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

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

1.1 命题逻辑 1

1.1.1 引言 1

1.1.2 命题 1

1.1.3 条件语句 4

1.1.4 复合命题的真值袁 7

1.1.5 逻辑运算符的优先级 7

1.1.6 翻译语句 8

1.1.7 系统规范说明 8

1.1.8 布尔检索 9

1.1.9 逻辑难题 9

1.1.10 逻辑运算和位运算 10

练习 11

1.2 命题等价 17

1.2.1 引言 17

1.2.2 逻辑等价 17

1.2.3 德摩根律的运用 19

1.2.4 构建新的逻辑等价式 20

练习 21

1.3 谓词和量词 24

1.3.1 引言 24

1.3.2 谓词 24

1.3.3 量词 26

1.3.4 其他量词 28

1.3.5 约束论域量词 28

1.3.6 量词的优先级 28

1.3.7 绑定变量 28

1.3.8 涉及量词的逻辑等价 29

1.3.9 否定量化表达式 29

1.3.10 翻译语句为逻辑表达式 31

1.3.11 在系统说明中运用量词 32

1.3.12 选自Lewis Carroll的例子 32

1.3.13 逻辑程序设计 33

练习 34

1.4 嵌套量词 38

1.4.1 引言 38

1.4.2 量词的顺序 39

1.4.3 将数学语句翻译成涉及嵌套量词的语句 41

1.4.4 将嵌套量词翻译为汉语 41

1.4.5 将汉语语句翻译成逻辑表达式 42

1.4.6 否定嵌套量词 42

练习 43

1.5 推理规则 48

1.5.1 引言 48

1.5.2 命题逻辑的有效论证 48

1.5.3 命题逻辑的推理规则 49

1.5.4 用推理规则建立论证 51

1.5.5 消解 51

1.5.6 谬误 52

1.5.7 带量词命题的推理规则 52

1.5.8 命题推理和量化语句推理规则的结合 53

练习 54

1.6 证明导论 57

1.6.1 引言 57

1.6.2 一些专用术语 57

1.6.3 定理陈述的理解 58

1.6.4 证明定理的方法 58

1.6.5 直接证明 58

1.6.6 反证法 59

1.6.7 归谬证明 60

1.6.8 证明中的错误 62

1.6.9 仅仅是开始 63

练习 64

1.7 证明的方法和策略 65

1.7.1 引言 65

1.7.2 穷举证明和分情形证明 65

1.7.3 存在性证明 68

1.7.4 唯一性证明 69

1.7.5 证明策略 69

1.7.6 寻找反例 71

1.7.7 行动证明策略 71

1.7.8 填充 71

1.7.9 未解决问题的作用 74

1.7.10 其他证明方法 74

练习 75

关键术语和结果 76

复习题 78

补充练习 79

计算机题目 80

计算和研究 80

写作题目 81

第2章 基本结构：集合、函数、数列与求和 82

2.1 集合 82

2.1.1 引言 82

2.1.2 幂集合 85

2.1.3 笛卡儿积 86

2.1.4 使用带量词的集合符号 87

2.1.5 量词的真值集合 87

练习 87

2.2 集合运算 89

2.2.1 引言 89

2.2.2 集合恒等式 90

2.2.3 扩展的并集和交集 93

2.2.4 计算机表示集合的方式 94

练习 95

2.3 函数 98

2.3.1 引言 98

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

2.3.3 反函数和函数组合 102

2.3.4 函数的图像 104

2.3.5 几个重要的函数 104

练习 107

2.4 序列与求和 111

2.4.1 引言 111

2.4.2 序列 111

2.4.3 特殊的整数序列 112

2.4.4 求和 113

2.4.5 基数 116

练习 118

关键术语与结果 120

复习题 122

补充练习 122

计算机课题 124

计算和研究 124

写作题目 124

第3章 基础：算法、整数和矩阵 125

3.1 算法 125

3.1.1 引言 125

3.1.2 搜索算法 127

3.1.3 排序 128

3.1.4 贪心算法 130

3.1.5 停机问题 131

练习 132

3.2 函数的增长 135

3.2.1 引言 135

3.2.2 大O记号 135

3.2.3 一些重要的大O结果 138

3.2.4 函数组合的增长 139

3.2.5 大Ω与大Θ记号 141

练习 142

3.3 算法的复杂度 145

3.3.1 引言 145

3.3.2 时间复杂度 145

3.3.3 理解算法的复杂度 147

练习 149

3.4 整数和除法 151

3.4.1 引言 151

3.4.2 除法 151

3.4.3 带余除法 152

3.4.4 同余算术 152

3.4.5 同余应用 154

3.4.6 密码学 155

练习 156

3.5 素数和最大公约数 157

3.5.1 引言 157

3.5.2 素数 157

3.5.3 关于素数的猜想和一些未解决问题 160

3.5.4 最大公约数和最小公倍数 161

练习 162

3.6 整数和算法 163

3.6.1 引言 163

3.6.2 整数表示 164

3.6.3 整数运算算法 166

3.6.4 同余幂 168

3.6.5 欧几里得算法 169

练习 171

3.7 数论应用 173

3.7.1 引言 173

3.7.2 若干有用的结果 173

3.7.3 线性同余 175

3.7.4 中国剩余定理 175

3.7.5 大整数计算机算术 176

3.7.6 伪素数 177

3.7.7 公钥密码学 179

3.7.8 RSA密码系统 179

3.7.9 RSA加密 180

3.7.10 RSA解密 180

3.7.11 用RSA作为公钥系统 180

练习 181

3.8 矩阵 184

3.8.1 引言 184

3.8.2 矩阵算术 184

3.8.3 矩阵乘法算法 185

3.8.4 矩阵转置和幂 186

3.8.5 0-1矩阵 187

练习 189

关键术语和结果 191

复习题 193

补充练习 194

计算机题目 196

计算和研究 196

写作题目 197

第4章 归纳与递归 198

4.1 数学归纳法 198

4.1.1 引言 198

4.1.2 数学归纳法 199

4.1.3 利用数学归纳法证明的例子 200

4.1.4 为什么说数学归纳法是有效的 208

4.1.5 使用数学归纳法时犯的错误 208

练习 209

4.2 强归纳法与良序性 214

4.2.1 引言 214

4.2.2 强归纳法 214

4.2.3 利用强归纳法证明的例子 215

4.2.4 计算几何学中使用强归纳法 217

4.2.5 利用良序性证明 219

练习 220

4.3 递归定义与结构归纳法 223

4.3.1 引言 223

4.3.2 递归地定义函数 223

4.3.3 递归地定义集合与结构 226

4.3.4 结构归纳法 229

4.3.5 广义归纳法 232

练习 232

4.4 递归算法 236

4.4.1 引言 236

4.4.2 证明递归算法的正确性 239

4.4.3 递归与迭代 240

4.4.4 归并排序 241

练习 244

4.5 程序正确性 245

4.5.1 引言 245

4.5.2 程序验证 246

4.5.3 推理规则 246

4.5.4 条件语句 247

4.5.5 循环不变量 248

练习 249

关键术语和结果 251

复习题 251

补充练习 252

计算机题目 256

计算和研究 256

写作题目 257

第5章 计数 258

5.1 计数的基础 258

5.1.1 引言 258

5.1.2 基本的计数原则 258

5.1.3 比较复杂的计数问题 261

5.1.4 容斥原理 262

5.1.5 树图 263

练习 264

5.2 鸽巢原理 267

5.2.1 引言 267

5.2.2 广义鸽巢原理 268

5.2.3 巧妙使用鸽巢原理 270

练习 271

5.3 排列与组合 273

5.3.1 引言 273

5.3.2 排列 273

5.3.3 组合 275

练习 277

5.4 二项式系数 279

5.4.1 二项式定理 279

5.4.2 帕斯卡恒等式和三角形 281

5.4.3 其他的二项式系数恒等式 282

练习 283

5.5 排列与组合的推广 286

5.5.1 引言 286

5.5.2 有重复的排列 286

5.5.3 有重复的组合 286

5.5.4 具有不可区别物体的集合的排列 289

5.5.5 把物体放入盒子 289

练习 292

5.6 生成排列和组合 295

5.6.1 引言 295

5.6.2 生成排列 295

5.6.3 生成组合 296

练习 297

关键术语和结果 298

复习题 299

补充练习 300

计算机题目 302

计算和研究 303

写作题目 303

第6章 离散概率 304

6.1 离散概率引论 304

6.1.1 引言 304

6.1.2 有限概率 304

6.1.3 事件组合的概率 306

6.1.4 概率的推理 307

练习 307

6.2 概率论 309

6.2.1 引言 309

6.2.2 概率指派 309

6.2.3 事件的组合 311

6.2.4 条件概率 311

6.2.5 独立性 312

6.2.6 伯努利试验与二项分布 313

6.2.7 随机变量 314

6.2.8 生日问题 314

6.2.9 蒙特卡罗算法 316

6.2.10 概率方法 317

练习 318

6.3 贝叶斯定理 321

6.3.1 引言 321

6.3.2 贝叶斯定理 321

6.3.3 贝叶斯spam过滤器 323

练习 325

6.4 期望值和方差 327

6.4.1 引言 327

6.4.2 期望值 327

6.4.3 期望的线性性质 329

6.4.4 平均情形下的计算复杂度 330

6.4.5 几何分布 332

6.4.6 独立随机变量 332

6.4.7 方差 333

6.4.8 切比雪夫不等式 335

练习 336

关键术语和结果 338

复习题 339

补充练习 340

计算机题目 342

计算和研究 343

写作题目 343

第7章 高级计数技术 344

7.1 递推关系 344

7.1.1 引言 344

7.1.2 递推关系 344

7.1.3 用递推关系构造模型 345

练习 349

7.2 求解线性递推关系 354

7.2.1 引言 354

7.2.2 求解常系数线性齐次递推关系 354

7.2.3 常系数线性非齐次的递推关系 357

练习 360

7.3 分治算法和递推关系 363

7.3.1 引言 363

7.3.2 分治递推关系 363

练习 368

7.4 生成函数 370

7.4.1 引言 370

7.4.2 关于幂级数的有用事实 371

7.4.3 计数问题与生成函数 374

7.4.4 使用生成函数求解递推关系 376

7.4.5 使用生成函数证明恒等式 377

练习 378

7.5 容斥 382

7.5.1 引言 382

7.5.2 容斥原理 382

练习 385

7.6 容斥原理的应用 387

7.6.1 引言 387

7.6.2 容斥原理的另一种形式 387

7.6.3 埃拉托色尼筛 388

7.6.4 映上函数的个数 389

7.6.5 错位排列 390

练习 391

关键术语和结果 393

复习题 393

补充练习 394

计算机题目 396

计算和研究 396

写作题目 397

第8章 关系 398

8.1 关系及其性质 398

8.1.1 引言 398

8.1.2 函数作为关系 399

8.1.3 集合的关系 399

8.1.4 关系的性质 400

8.1.5 关系的组合 402

练习 403

8.2 n元关系及其应用 406

8.2.1 引言 406

8.2.2 n元关系 406

8.2.3 数据库和关系 407

8.2.4 n元关系的运算 408

8.2.5 SQL 410

练习 410

8.3 关系的表示 412

8.3.1 引言 412

8.3.2 用矩阵表示关系 412

8.3.3 用图表示关系 414

练习 415

8.4 关系的闭包 417

8.4.1 引言 417

8.4.2 闭包 418

8.4.3 有向图的路径 418

8.4.4 传递闭包 419

8.4.5 沃舍尔算法 422

练习 424

8.5 等价关系 425

8.5.1 引言 425

8.5.2 等价关系 426

8.5.3 等价类 427

8.5.4 等价类与划分 428

练习 430

8.6 偏序 434

8.6.1 引言 434

8.6.2 字典顺序 436

8.6.3 哈塞图 437

8.6.4 极大元素与极小元素 438

8.6.5 格 440

8.6.6 拓扑排序 441

练习 443

关键术语和结果 447

复习题 448

补充练习 449

计算机题目 452

计算和研究 452

写作题目 453

第9章 图 454

9.1 图和图模型 454

练习 459

9.2 图的术语和几种特殊的图 461

9.2.1 引言 461

9.2.2 基本术语 461

9.2.3 一些特殊的简单图 463

9.2.4 偶图 464

9.2.5 特殊类型的图的一些应用 465

9.2.6 从旧图到新图 468

练习 468

9.3 图的表示和图的同构 471

9.3.1 引言 471

9.3.2 图的表示 471

9.3.3 邻接矩阵 472

9.3.4 关联矩阵 474

9.3.5 图的同构 474

练习 477

9.4 连通性 480

9.4.1 引言 480

9.4.2 通路 480

9.4.3 无向图的连通性 482

9.4.4 有向图的连通性 483

9.4.5 通路与同构 484

9.4.6 计算顶点之间的通路数 485

练习 485

9.5 欧拉通路与哈密顿通路 489

9.5.1 引言 489

9.5.2 欧拉通路与欧拉回路 489

9.5.3 哈密顿通路与哈密顿回路 493

练习 496

9.6 最短通路问题 500

9.6.1 引言 500

9.6.2 最短通路算法 502

9.6.3 旅行商问题 505

练习 507

9.7 可平面图 509

9.7.1 引言 509

9.7.2 欧拉公式 511

9.7.3 库拉图斯基定理 513

练习 514

9.8 图着色 516

9.8.1 引言 516

9.8.2 图着色的应用 519

练习 520

关键术语和结果 524

复习题 525

补充练习 526

计算机题目 530

计算和研究 530

写作题目 531

第10章 树 532

10.1 概述 532

10.1.1 树作为模型 536

10.1.2 树的性质 537

练习 539

10.2 树的应用 542

10.2.1 引言 542

10.2.2 二叉搜索树 542

10.2.3 决策树 544

10.2.4 前缀码 546

10.2.5 博弈树 548

练习 551

10.3 树的遍历 555

10.3.1 引言 555

10.3.2 通用地址系统 555

10.3.3 遍历算法 556

10.3.4 中缀、前缀和后缀记法 561

练习 563

10.4 生成树 566

10.4.1 引言 566

10.4.2 深度优先搜索 567

10.4.3 宽度优先搜索 569

10.4.4 回溯 571

10.4.5 有向图中的深度优先搜索 572

练习 573

10.5 最小生成树 576

10.5.1 引言 576

10.5.2 最小生成树算法 577

练习 580

关键术语和结果 581

复习题 582

补充练习 583

计算机题目 586

计算和研究 586

写作题目 586

第11章 布尔代数 588

11.1 布尔函数 588

11.1.1 引言 588

11.1.2 布尔表达式和布尔函数 589

11.1.3 布尔代数恒等式 590

11.1.4 对偶性 591

11.1.5 布尔代数的抽象定义 592

练习 593

11.2 布尔函数的表示 594

11.2.1 积之和展开式 594

11.2.2 函数完全性 595

练习 596

11.3 逻辑门电路 597

11.3.1 引言 597

11.3.2 门的组合 597

11.3.3 电路的例子 599

11.3.4 加法器 600

练习 601

11.4 电路的极小化 603

11.4.1 引言 603

11.4.2 卡诺图 604

11.4.3 无需在意的条件 609

11.4.4 奎因-莫可拉斯基方法 609

练习 613

关键术语和结果 615

复习题 616

补充练习 616

计算机题目 618

计算和研究 618

写作题目 619

第12章 计算模型 620

12.1 语言和文法 620

12.1.1 引言 620

12.1.2 短语结构文法 621

12.1.3 短语结构文法的类型 623

12.1.4 派生树 624

12.1.5 巴克斯-诺尔范式 625

练习 626

12.2 带输出的有限状态机 629

12.2.1 引言 629

12.2.2 带输出的有限状态机 630

练习 633

12.3 不带输出的有限状态机 635

12.3.1 引言 635

12.3.2 串的集合 635

12.3.3 有限状态自动机 635

12.3.4 有限状态机的语言识别 636

12.3.5 非确定型有限状态自动机 640

练习 642

12.4 语言的识别 646

12.4.1 引言 646

12.4.2 正则集合 646

12.4.3 克莱因定理 647

12.4.4 正则集合和正则文法 649

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

12.4.6 一些更强大的机器 652

练习 653

12.5 图灵机 655

12.5.1 引言 655

12.5.2 图灵机的定义 655

12.5.3 用图灵机识别集合 657

12.5.4 用图灵机计算函数 658

12.5.5 不同类型的图灵机 659

12.5.6 丘奇-图灵论题 659

12.5.7 计算复杂度、可计算性和可判定性 660

练习 662

关键术语和结果 664

复习题 665

补充练习 666

计算机题目 668

计算和研究 668

写作题目 668

附录A 实数和正整数公理 669

附录B 指数函数和对数函数 673

附录C 伪代码 675

推荐读物 679

参考文献 682