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

专家指导委员会 1

译者序 1

前言 1

第1章 基础：逻辑、集合和函数 1

1.1 逻辑 1

1.1.1 引言 1

1.1.2 命题 1

出版者的话 1

1.1.3 翻译语言的句子 6

1.1.4 布尔检索 7

1.1.5 逻辑运算和位运算 7

练习 9

1.2.2 逻辑等价 15

1.2 命题等价 15

1.2.1 引言 15

练习 19

1.3 谓词和量词 22

1.3.1 引言 22

1.3.2 量词 23

1.3.3 翻译语句为逻辑表达式 26

1.3.4 选自Lewis Carroll的例子(选读) 27

1.3.5 绑定变量 28

1.3.6 否定 31

练习 31

1.4 集合 39

1.4.1 引言 39

1.4.3 笛卡儿积 43

1.4.2 幂集合 43

练习 45

1.5 集合运算 47

1.5.1 引言 47

1.5.2 集合相等 49

1.5.3 扩展的并集和交集 51

1.5.4 集合的计算机表示 52

练习 53

1.6 函数 57

1.6.1 引言 57

1.6.2 一对一函数和映上函数 59

1.6.3 反函数和函数组合 61

1.6.4 函数的图像 63

1.6.5 几个重要的函数 64

练习 65

1.7 序列和求和 70

1.7.1 引言 70

1.7.2 序列 70

1.7.3 特殊的整数序列 71

1.7.4 求和 72

1.7.5 基数(选读) 75

练习 76

1.8 函数增长 80

1.8.1 引言 80

1.8.2 大O符号 80

1.8.3 函数组合的增长 84

1.8.4 大Ω和θ符号 86

练习 88

关键术语和结果 92

复习题 94

补充练习 95

计算机题目 98

计算和研究 98

写作题目 98

第2章 基础：算法、整数和矩阵 100

2.1 算法 100

2.1.1 引言 100

2.1.2 搜索算法 102

练习 104

2.2 算法的复杂性 106

2.2.1 引言 106

练习 109

2.3.2 除法 112

2.3.1 引言 112

2.3 整数和除法 112

2.3.3 素数 113

2.3.4 除法算法 115

2.3.5 最大公约数和最小公倍数 115

2.3.6 模运算 117

2.3.7 同余应用 118

2.3.8 密码学 120

练习 121

2.4 整数和算法 124

2.4.1 引言 124

2.4.2 欧几里德算法 125

2.4.3 整数表示 127

2.4.4 整数运算算法 128

练习 131

2.5 数论应用 134

2.5.1 引言 134

2.5.2 若干有用的结果 134

2.5.3 线性同余 136

2.5.4 中国余数定理 137

2.5.5 大整数的计算机算术运算 138

2.5.6 伪素数 140

2.5.7 公钥密码学 141

2.5.8 RSA加密 141

2.5.9 RSA解密 142

2.5.10 用RSA作公钥系统 143

练习 143

2.6.1 引言 146

2.6 矩阵 146

2.6.2 矩阵运算 147

2.6.3 矩阵乘法运算 148

2.6.4 矩阵的转置和幂 149

2.6.5 0-1矩阵 150

练习 153

关键术语和结果 156

复习题 158

补充练习 159

计算机题目 161

计算和研究 161

写作题目 162

第3章 数学推理 163

3.1 证明方法 163

3.1.1 引言 163

3.1.2 推理规则 164

3.1.3 谬误 167

3.1.4 带量词命题的推理规则 168

3.1.5 证明定理的方法 169

3.1.6 定理与量词 172

3.1.7 停机问题 174

3.1.8 关于证明的一些评注 175

练习 175

3.2 数学归纳法 181

3.2.1 引言 181

3.2.2 良序性 181

3.2.3 数学归纳法 181

3.2.4 数学归纳法证明的例子 183

3.2.5 数学归纳法的第二原理 189

练习 191

3.3 递归定义 195

3.3.1 引言 195

3.3.2 递归地定义函数 196

3.3.3 递归地定义集合 199

练习 201

3.4 递归算法 208

3.4.1 引言 208

3.4.2 递归与迭代 209

练习 211

3.5 程序正确性 211

3.5.1 引言 212

3.5.2 程序验证 213

3.5.4 条件语句 214

3.5.3 推理规则 214

3.5.5 循环不变量 215

练习 217

关键术语和结果 219

复习题 219

补充练习 221

计算机题目 224

计算和研究 225

写作题目 225

第4章 计数 227

4.1 计数的基础 227

4.1.1 引言 227

4.1.2 基本的计数原则 227

4.1.3 容斥原理 232

4.1.4 树图 233

练习 234

4.2 鸽巢原理 238

4.2.1 引言 238

4.2.2 推广的鸽巢原理 239

4.2.3 巧妙使用鸽巢原理 240

练习 242

4.3 排列与组合 244

4.3.1 引言 244

4.3.2 排列 244

4.3.3 组合 245

4.3.4 二项式系数 246

4.3.5 二项式定理 248

练习 250

4.4.1 引言 254

4.4 离散概率 254

4.4.2 有限概率 255

4.4.3 事件组合的概率 256

4.4.4 概述的推理 257

练习 258

4.5 概率论 260

4.5.1 引言 260

4.5.2 概率赋值 260

4.5.3 事件的组合 262

4.5.4 条件概率 262

4.5.5 独立性 263

4.5.6 伯努利实验与二项式分布 264

4.5.7 随机变量 266

4.5.8 期望值 267

4.5.9 独立随机变量 269

4.5.10 方差 270

4.5.11 切比雪夫不等式 272

4.5.12 平均状态下的计算复杂性 273

练习 274

4.6 一般性的排列和组合 277

4.6.1 引言 277

4.6.2 有重复的排列 277

4.6.3 有重复的组合 278

4.6.4 具有不可区别物体的集合的排列 281

4.6.5 把物体放入盒子 282

练习 282

4.7.1 引言 283

4.7.2 生成排列 286

4.7 生成排列和组合 286

4.7.3 生成组合 288

练习 289

关键术语和结果 290

复习题 292

补充练习 294

计算机题目 298

计算和研究 298

写作题目 299

第五章 高级计数技术 300

5.1 递推关系 300

5.1.1 引言 300

5.1.2 递推关系 300

5.1.3 用递推关系构造模型 301

练习 306

5.2 求解递推关系 312

5.2.1 引言 312

5.2.2 求解常系数线性齐次递推关系 313

5.2.3 常系数线性非齐次的递推关系 317

练习 318

练习 321

5.3 分而治之关系 325

5.3.1 引言 325

5.3.2 分而治之关系 326

练习 329

5.4 生成函数 330

5.4.1 引言 330

5.4.2 关于幂级数的有用的事实 331

5.4.3 计数问题与生成函数 335

5.4.4 使用生成函数求解递推关系 338

5.4.5 使用生成函数证明恒等式 340

练习 340

5.5.1 引言 347

5.5.2 容斥原理 347

5.5 容斥 347

练习 352

5.6 容斥原理的应用 353

5.6.1 引言 353

5.6.2 容斥原理的另一种形式 354

5.6.3 伊拉脱森筛 355

5.6.4 映上函数的个数 356

5.6.5 错位排列 357

练习 359

关键术语和结果 360

复习题 361

补充练习 362

计算机题目 365

计算和研究 366

写作题目 366

第6章 关系 368

6.1 关系及其性质 368

6.1.1 引言 368

6.1.2 函数作为关系 369

6.1.3 集合上的关系 369

6.1.4 关系的性质 370

6.1.5 关系的组合 372

练习 374

6.2.3 数据库和关系 377

6.2.2 n元关系 377

6.2.1 引言 377

6.2 n元关系及其应用 377

6.3 关系的表示 382

6.3.1 引言 382

6.3.2 用矩阵表示关系 382

6.3.3 用图表示关系 384

练习 386

6.4 关系的闭包 387

6.4.1 引言 387

6.4.2 闭包 388

6.4.3 有向图的路径 389

6.4.4 传递闭包 390

6.4.5 沃舍尔算法 393

练习 396

6.5 等价关系 398

6.5.1 引言 398

6.5.2 等价关系 398

6.5.3 等价类 399

6.5.4 等价类与划分 400

练习 402

6.6 偏序 405

6.6.1 引言 405

6.6.2 字典顺序 406

6.6.3 哈斯图 408

6.6.4 极大元素与极小元素 409

6.6.5 格 411

6.6.6 拓扑排序 412

练习 414

关键术语和结果 419

复习题 420

补充练习 422

计算机题目 426

计算和研究 426

写作题目 427

第7章 图 428

7.1 图的介绍 428

7.1.1 图的种类 428

7.1.2 图模型 431

练习 432

7.2.1 引言 434

7.2.2 基本术语 434

7.2 图的术语 434

7.2.3 一些特殊的简单图 436

7.2.4 偶图 437

7.2.5 特殊类型的图的一些应用 438

7.2.6 从旧图到新图 440

练习 441

7.3 图的表示和图的同构 443

7.3.1 引言 443

7.3.2 图的表示 443

7.3.3 相邻矩阵 444

7.3.4 关联矩阵 445

7.3.5 图的同构 446

练习 449

7.4.2 通路 454

7.4.1 引言 454

7.4 连通性 454

7.4.3 无向图连通性 455

7.4.4 有向图中的连通性 456

7.4.5 通路与同构 456

7.4.6 统计顶点之间的通路 457

练习 458

7.5 欧拉通路与哈密顿通路 461

7.5.1 引言 461

7.5.2 欧拉回路和欧拉通路的充要条件 462

7.5.3 哈密顿通路和回路 465

练习 468

7.6 最短通路问题 473

7.6.1 引言 473

7.6.2 一个最短通路算法 475

7.6.3 旅行推销员问题 479

练习 480

7.7 平面性图 484

7.7.1 引言 484

7.7.2 欧拉公式 485

7.7.3 库拉图斯基定理 488

练习 489

7.8 图着色 491

7.8.1 引言 491

7.8.2 图着色的应用 495

练习 496

关键术语和结果 499

复习题 501

补充练习 502

计算和研究 507

计算机题目 507

写作题目 508

第8章 树 510

8.1 介绍树 510

8.1.1 树作为模型 514

8.1.2 树的性质 516

练习 518

8.2 树的应用 521

8.2.1 引言 521

8.2.2 二叉搜索树 521

8.2.3 决策树 524

8.2.4 前辍码 524

练习 525

8.3.1 引言 526

8.3 树的遍历 526

8.3.2 通用地址系统 527

8.3.3 遍历算法 527

8.3.4 中缀、前缀和后缀记法 533

练习 536

8.4 树与排序 538

8.4.1 引言 538

8.4.2 排序的复杂性 539

8.4.3 冒泡排序 539

8.4.4 归并排序 541

练习 544

8.5 生成树 545

8.5.1 引言 545

8.5.2 一些构造生成树的算法 547

8.5.3 回溯 549

练习 551

8.6 最小生成树 554

8.6.1 引言 554

8.6.2 最小生成树算法 554

练习 558

关键术语和结果 560

复习题 561

补充练习 562

计算机题目 566

计算和研究 566

写作题目 567

9.1.1 引言 568

9.1 布尔函数 568

第9章 布尔代数 568

9.1.2 布尔表达式和布尔函数 569

9.1.3 布尔代数中的恒等式 570

9.1.4 对偶性 571

9.1.5 布尔代数和抽象定义 572

练习 573

9.2 布尔函数的表示 574

9.2.1 积之和展开式 574

9.2.2 函数完备性 575

练习 576

9.3 逻辑门电路 577

9.3.1 引言 577

9.3.2 门的组合 578

9.3.3 电路的例子 579

9.3.4 加法器 581

9.4 电路的极小化 583

9.4.1 引言 583

练习 583

9.4.2 卡诺图 584

9.4.3 无需在意条件 588

9.4.4 奎因-莫可拉斯基方法 588

练习 592

关键术语和结果 594

复习题 595

补充练习 596

计算机题目 598

计算和研究 598

写作题目 598

10.1.1 引言 600

第10章 计算模型 600

10.1 语言和文法 600

10.1.2 短语结构文法 601

10.1.3 短语结构文法的类型 604

10.1.4 派生树 605

10.1.5 巴科斯-诺尔范式 605

练习 607

10.2 带输出的有限状态机 609

10.2.1 引言 609

10.2.2 带输出的有限状态机 610

10.3 不带输出的有限状态机 612

练习 614

10.3.1 引言 616

10.3.2 串的集合 616

10.3.3 有限状态自动机 617

练习 621

10.4 语言的识别 623

10.4.1 引言 623

10.4.2 正则集合 623

10.4.3 克莱因定理 624

10.4.4 正则集合和正则文法 627

10.4.5 一个不能由有限状态自动机识别的语言 629

10.4.6 一些更强大的机器 630

练习 631

10.5 图灵机 632

10.5.1 引言 632

10.5.2 图灵机的定义 633

10.5.3 用图灵机识别集合 634

10.5.4 用图灵机计算函数 636

10.5.5 不同类型的图灵机 637

10.5.6 丘奇-图灵论题 637

练习 637

关键术语和结果 639

复习题 640

补充练习 641

计算机题目 644

计算和研究 644

写作题目 644

附录A 指数函数和对数函数 646

附录B 伪代码 649

奇数练习题答案 654

推荐读物 790

参考文献 794