目录
出版者的话

译者序

前言

在线资源

致学生

作者简介

符号表

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

 1.1 命题逻辑1

  1.1.1 引言1

  1.1.2 命题1

  1.1.3 条件语句4

  1.1.4 复合命题的真值表7

  1.1.5 逻辑运算符的优先级8

  1.1.6 逻辑运算和比特运算8

  练习9

 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

  练习20

 1.3 命题等价式23

  1.3.1 引言23

  1.3.2 逻辑等价式23

  1.3.3 德·摩根律的运用25

  1.3.4 构造新的逻辑等价式26

  1.3.5 可满足性28

  1.3.6 可满足性的应用28

  1.3.7 可满足性问题求解30

  练习31

 1.4 谓词和量词34

  1.4.1 引言34

  1.4.2 谓词34

  1.4.3 量词37

  1.4.4 有限域上的量词39

  1.4.5 受限域的量词39

  1.4.6 量词的优先级40

  1.4.7 变量绑定40

  1.4.8 涉及量词的逻辑等价式40

  1.4.9 量化表达式的否定41

  1.4.10 语句到逻辑表达式的翻译42

  1.4.11 系统规范说明中量词的使用43

  1.4.12 选自路易斯·卡罗尔的例子44

  1.4.13 逻辑程序设计45

  练习46

 1.5 嵌套量词51

  1.5.1 引言51

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

  1.5.3 量词的顺序52

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

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

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

  1.5.7 嵌套量词的否定55

  练习56

 1.6 推理规则62

  1.6.1 引言62

  1.6.2 命题逻辑的有效论证62

  1.6.3 命题逻辑的推理规则63

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

  1.6.5 消解律66

  1.6.6 谬误66

  1.6.7 量化命题的推理规则67

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

  练习69

 1.7 证明导论72

  1.7.1 引言72

  1.7.2 一些专用术语72

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

  1.7.4 证明定理的方法73

  1.7.5 直接证明法73

  1.7.6 反证法74

  1.7.7 归谬证明法76

  1.7.8 证明中的错误78

  1.7.9 良好的开端79

  练习80

 1.8 证明的方法和策略81

  1.8.1 引言81

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

  1.8.3 存在性证明84

  1.8.4 唯一性证明86

  1.8.5 证明策略87

  1.8.6 寻找反例89

  1.8.7 证明策略实践90

  1.8.8 拼接90

  1.8.9 开放问题的作用92

  1.8.10 其他证明方法93

  练习94

 关键术语和结论96

 复习题97

 补充练习98

 计算机课题100

 计算和探索101

 写作课题101

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

 2.1 集合102

  2.1.1 引言102

  2.1.2 文氏图104

  2.1.3 子集105

  2.1.4 集合的大小106

  2.1.5 幂集107

  2.1.6 笛卡儿积107

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

  2.1.8 真值集和量词109

  练习109

 2.2 集合运算112

  2.2.1 引言112

  2.2.2 集合恒等式114

  2.2.3 扩展的并集和交集116

  2.2.4 集合的计算机表示117

  2.2.5 多重集118

  练习119

 2.3 函数123

  2.3.1 引言123

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

  2.3.3 反函数和函数合成128

  2.3.4 函数的图130

  2.3.5 一些重要的函数130

  2.3.6 部分函数133

  练习133

 2.4 序列与求和138

  2.4.1 引言138

  2.4.2 序列138

  2.4.3 递推关系139

  2.4.4 特殊的整数序列141

  2.4.5 求和144

  练习147

 2.5 集合的基数150

  2.5.1 引言150

  2.5.2 可数集合151

  2.5.3 不可数集合153

  练习155

 2.6 矩阵157

  2.6.1 引言157

  2.6.2 矩阵算术158

  2.6.3 矩阵的转置和幂159

  2.6.4 0-1矩阵160

  练习161

 关键术语和结论164

 复习题166

 补充练习166

 计算机课题168

 计算和探索169

 写作课题169

第3章 算法170

 3.1 算法170

  3.1.1 引言170

  3.1.2 搜索算法172

  3.1.3 排序174

  3.1.4 字符串匹配176

  3.1.5 贪婪算法177

  3.1.6 停机问题179

  练习180

 3.2 函数的增长183

  3.2.1 引言183

  3.2.2 大O记号184

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

  3.2.4 函数组合的增长190

  3.2.5 大Ω与大Θ记号191

  练习192

 3.3 算法的复杂度196

  3.3.1 引言196

  3.3.2 时间复杂度196

  3.3.3 矩阵乘法的复杂度198

  3.3.4 算法范型199

  3.3.5 理解算法的复杂度201

  练习203

 关键术语和结论207

 复习题208

 补充练习209

 计算机课题211

 计算和探索211

 写作课题212

第4章 数论和密码学213

 4.1 整除性和模算术213

  4.1.1 引言213

  4.1.2 除法213

  4.1.3 除法算法214

  4.1.4 模算术215

  4.1.5 模m算术217

  练习218

 4.2 整数表示和算法220

  4.2.1 引言220

  4.2.2 整数表示220

  4.2.3 整数运算算法223

  4.2.4 模指数运算225

  练习226

 4.3 素数和最大公约数229

  4.3.1 引言229

  4.3.2 素数229

  4.3.3 试除法230

  4.3.4 埃拉托斯特尼筛法231

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

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

  4.3.7 欧几里得算法238

  4.3.8 gcd的线性组合表示239

  练习242

 4.4 求解同余方程245

  4.4.1 引言245

  4.4.2 线性同余方程245

  4.4.3 中国剩余定理247

  4.4.4 大整数的计算机算术248

  4.4.5 费马小定理249

  4.4.6 伪素数250

  4.4.7 原根和离散对数251

  练习252

 4.5 同余的应用255

  4.5.1 散列函数255

  4.5.2 伪随机数256

  4.5.3 校验码257

  练习259

 4.6 密码学260

  4.6.1 引言260

  4.6.2 古典密码学261

  4.6.3 公钥密码学263

  4.6.4 RSA密码系统265

  4.6.5 RSA加密265

  4.6.6 RSA解密266

  4.6.7 用RSA作为公钥系统266

  4.6.8 密码协议267

  4.6.9 同态加密268

  练习269

 关键术语和结论271

 复习题273

 补充练习273

 计算机课题275

 计算和探索276

 写作课题276

第5章 归纳与递归278

 5.1 数学归纳法278

  5.1.1 引言278

  5.1.2 数学归纳法279

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

  5.1.4 选择正确的基础步骤280

  5.1.5 运用数学归纳法进行证明的原则281

  5.1.6 数学归纳法的优点与缺点281

  5.1.7 利用数学归纳法证明的例子281

  5.1.8 使用数学归纳法时犯的错误290

  练习291

 5.2 强归纳法与良序性296

  5.2.1 引言296

  5.2.2 强归纳法296

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

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

  5.2.5 利用良序性证明302

  练习302

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

  5.3.1 引言306

  5.3.2 递归地定义函数307

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

  5.3.4 结构归纳法312

  5.3.5 广义归纳法315

  练习315

 5.4 递归算法320

  5.4.1 引言320

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

  5.4.3 递归与迭代323

  5.4.4 归并排序324

  练习327

 5.5 程序正确性329

  5.5.1 引言329

  5.5.2 程序验证329

  5.5.3 推理规则330

  5.5.4 条件语句330

  5.5.5 循环不变量332

  练习333

 关键术语和结论334

 复习题335

 补充练习336

 计算机课题340

 计算和探索341

 写作课题341

第6章 计数342

 6.1 计数的基础342

  6.1.1 引言342

  6.1.2 基本的计数原则342

  6.1.3 比较复杂的计数问题346

  6.1.4 减法法则(两个集合的容斥原理)347

  6.1.5 除法法则349

  6.1.6 树图349

  练习350

 6.2 鸽巢原理354

  6.2.1 引言354

  6.2.2 广义鸽巢原理355

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

  练习359

 6.3 排列与组合361

  6.3.1 引言361

  6.3.2 排列361

  6.3.3 组合362

  练习365

 6.4 二项式系数和恒等式367

  6.4.1 二项式定理368

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

  6.4.3 其他的二项式系数

恒等式371

  练习372

 6.5 排列与组合的推广375

  6.5.1 引言375

  6.5.2 有重复的排列375

  6.5.3 有重复的组合375

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

  6.5.5 把物体放入盒子379

  练习382

 6.6 生成排列和组合385

  6.6.1 引言385

  6.6.2 生成排列385

  6.6.3 生成组合386

  练习387

 关键术语和结论388

 复习题389

 补充练习390

 计算机课题393

 计算和探索394

 写作课题394

第7章 离散概率395

 7.1 离散概率引论395

  7.1.1 引言395

  7.1.2 有限概率395

  7.1.3 事件组合的概率398

  7.1.4 概率的推理399

  练习399

 7.2 概率论402

  7.2.1 引言402

  7.2.2 概率指派402

  7.2.3 事件的组合403

  7.2.4 条件概率404

  7.2.5 独立性405

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

  7.2.7 随机变量407

  7.2.8 生日问题408

  7.2.9 蒙特卡罗算法409

  7.2.10 概率方法411

  练习412

 7.3 贝叶斯定理414

  7.3.1 引言414

  7.3.2 贝叶斯定理415

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

  练习420

 7.4 期望值和方差422

  7.4.1 引言422

  7.4.2 期望值422

  7.4.3 期望的线性性质424

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

  7.4.5 几何分布427

  7.4.6 独立随机变量428

  7.4.7 方差429

  7.4.8 切比雪夫不等式431

  练习433

 关键术语和结论435

 复习题436

 补充练习437

 计算机课题440

 计算和探索441

 写作课题441

第8章 高级计数技术442

 8.1 递推关系的应用442

  8.1.1 引言442

  8.1.2 用递推关系构造模型443

  8.1.3 算法与递推关系447

  练习450

 8.2 求解线性递推关系453

  8.2.1 引言453

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

  8.2.3 求解常系数线性非齐次递推关系458

  练习460

 8.3 分治算法和递推关系463

  8.3.1 引言463

  8.3.2 分治递推关系463

  练习469

 8.4 生成函数471

  8.4.1 引言471

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

  8.4.3 计数问题与生成函数474

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

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

  练习479

 8.5 容斥484

  8.5.1 引言484

  8.5.2 容斥原理484

  练习487

 8.6 容斥原理的应用488

  8.6.1 引言488

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

  8.6.3 埃拉托色尼筛489

  8.6.4 映上函数的个数490

  8.6.5 错位排列490

  练习492

 关键术语和结论493

 复习题494

 补充练习495

 计算机课题497

 计算和探索498

 写作课题498

第9章 关系500 9.1

 关系及其性质500

  9.1.1 引言500

  9.1.2 函数作为关系501

  9.1.3 集合的关系501

  9.1.4 关系的性质502

  9.1.5 关系的组合504

  练习506

 9.2 n元关系及其应用510

  9.2.1 引言510

  9.2.2 n元关系510

  9.2.3 数据库和关系511

  9.2.4 n元关系的运算512

  9.2.5 SQL514

  9.2.6 数据挖掘中的关联规则514

  练习516

 9.3 关系的表示518

  9.3.1 引言518

  9.3.2 用矩阵表示关系518

  9.3.3 用图表示关系521

  练习522

 9.4 关系的闭包524

  9.4.1 引言524

  9.4.2 不同类型的闭包524

  9.4.3 有向图中的路径525

  9.4.4 传递闭包526

  9.4.5 沃舍尔算法529

  练习531

 9.5 等价关系533

  9.5.1 引言533

  9.5.2 等价关系533

  9.5.3 等价类534

  9.5.4 等价类与划分536

  练习538

 9.6 偏序542

  9.6.1 引言542

  9.6.2 字典顺序544

  9.6.3 哈塞图545

  9.6.4 极大元与极小元546

  9.6.5 格548

  9.6.6 拓扑排序550

  练习551

 关键术语和结论556

 复习题557

 补充练习558

 计算机课题561

 计算和探索562

 写作课题562

第10章 图563

 10.1 图和图模型563

  10.1.1 图模型565

  练习570

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

  10.2.1 引言573

  10.2.2 基本术语573

  10.2.3 一些特殊的简单图575

  10.2.4 二分图576

  10.2.5 二分图和匹配577

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

  10.2.7 从旧图构造新图582

  练习584

 10.3 图的表示和图的同构587

  10.3.1 引言587

  10.3.2 图的表示588

  10.3.3 邻接矩阵588

  10.3.4 关联矩阵590

  10.3.5 图的同构590

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

  练习593

 10.4 连通性598

  10.4.1 引言598

  10.4.2 通路598

  10.4.3 无向图的连通性600

  10.4.4 图是如何连通的601

  10.4.5 有向图的连通性603

  10.4.6 通路与同构604

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

  练习606

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

  10.5.1 引言611

  10.5.2 欧拉通路与欧拉回路611

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

  10.5.4 哈密顿回路的应用618

  练习619

 10.6 最短通路问题623

  10.6.1 引言623

  10.6.2 最短通路算法625

  10.6.3 旅行商问题629

  练习630

 10.7 平面图633

  10.7.1 引言633

  10.7.2 欧拉公式634

  10.7.3 库拉图斯基定理637

  练习638

 10.8 图着色640

  10.8.1 引言640

  10.8.2 图着色的应用644

  练习645

 关键术语和结论648

 复习题650

 补充练习651

 计算机课题656

 计算和探索656

 写作课题657

第11章 树658

 11.1 树的概述658

  11.1.1 有根树659

  11.1.2 树作为模型662

  11.1.3 树的性质663

  练习666

 11.2 树的应用668

  11.2.1 引言668

  11.2.2 二叉搜索树668

  11.2.3 决策树671

  11.2.4 前缀码672

  11.2.5 博弈树674

  练习678

 11.3 树的遍历681

  11.3.1 引言681

  11.3.2 通用地址系统681

  11.3.3 遍历算法682

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

  练习690

 11.4 生成树693

  11.4.1 引言693

  11.4.2 深度优先搜索694

  11.4.3 宽度优先搜索696

  11.4.4 回溯的应用698

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

  练习701

 11.5 最小生成树704

  11.5.1 引言704

  11.5.2 最小生成树算法704

  练习707

 关键术语和结论709

 复习题710

 补充练习711

 计算机课题714

 计算和探索714

 写作课题715

第12章 布尔代数716

 12.1 布尔函数716

  12.1.1 引言716

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

  12.1.3 布尔代数恒等式718

  12.1.4 对偶性720

  12.1.5 布尔代数的抽象定义720

  练习721

 12.2 布尔函数的表示722

  12.2.1 积之和展开式723

  12.2.2 函数完备性724

  练习724

 12.3 逻辑门电路725

  12.3.1 引言725

  12.3.2 门的组合726

  12.3.3 电路的例子726

  12.3.4 加法器728

  练习729

 12.4 电路的极小化731

  12.4.1 引言731

  12.4.2 卡诺图732

  12.4.3 无须在意的条件737

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

  练习741

 关键术语和结论743

 复习题744

 补充练习744

 计算机课题746

 计算和探索746

 写作课题747

第13章 计算模型748

 13.1 语言和文法748

  13.1.1 引言748

  13.1.2 短语结构文法749

  13.1.3 短语结构文法的类型751

  13.1.4 派生树752

  13.1.5 巴克斯-诺尔范式754

  练习755

 13.2 带输出的有限状态机758

  13.2.1 引言758

  13.2.2 带输出的有限状态机759

  练习762

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

  13.3.1 引言764

  13.3.2 串的集合764

  13.3.3 有限状态自动机765

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

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

  练习773

 13.4 语言的识别777

  13.4.1 引言777

  13.4.2 克莱因定理778

  13.4.3 正则集合和正则文法781

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

  13.4.5 一些更强大的机器783

  练习784

 13.5 图灵机786

  13.5.1 引言786

  13.5.2 图灵机的定义787

  13.5.3 用图灵机识别集合789

  13.5.4 用图灵机计算函数790

  13.5.5 不同类型的图灵机790

  13.5.6 丘奇-图灵论题791

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

  练习794

 关键术语和结论796

 复习题797

 补充练习798

 计算机课题800

 计算和探索800

 写作课题800

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

附录B 指数与对数函数807

附录C 伪代码809

推荐读物813

参考文献817

奇数编号练习答案

 请访问华章网站www.hzbook.com下载。


按 Ctrl+p 打印本页】【关闭