专家指导委员会 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