第一部分离散数学基础/ 1

第1章计数基本原理/3

1.1加法原理与乘法原理/3

1.2排列/5

练习1.1和1.2/9

1.3组合： 二项式定理/12

练习1.3组合：二项式定理/21

1.4可重复组合/24

练习1.4可重复组合/31

1.5Catalan数（可选）/33

练习1.5Catalan数（可选）/36

1.6本章小结和历史回顾/37

补充练习1/38

第2章逻辑基础/42

2.1基本联结词与真值表/42

练习2.1基本联结词与真值表/48

2.2逻辑等价： 逻辑定律/49

练习2.2逻辑等价：逻辑定律/58

2.3逻辑蕴涵命题： 推理规则/59

练习2.3逻辑蕴涵命题：推理规则/74

2.4量词的应用/76

练习2.4量词的应用/87

2.5量词、定义和定理证明/91

练习2.5量词、定义和定理证明/101

2.6本章小结和历史回顾/103

补充练习2/104

第3章集合论/107

3.1集合与子集/107

练习3.1集合与子集/117

3.2集合运算与集合论定律/119

练习3.2集合运算与集合论定律/128

3.3计数与文氏图/129

练习3.3计数与文氏图/131

3.4概率初步/132

练习3.4概率初步/136

3.5概率公理（可选）/137

练习3.5概率公理（可选）/144

3.6条件概率： 独立（可选）/145

练习3.6条件概率：独立（可选）/152

3.7离散随机变量（可选）/154

练习3.7离散随机变量（可选）/163

3.8本章小结和历史回顾/164

补充练习3/167

第4章整数的性质： 数学归纳法/171

4.1良序原理： 数学归纳法/171

练习4.1良序原理：数学归纳法/183

4.2递归定义/185

练习4.2递归定义/193

4.3除法算法： 素数/195

练习4.3除法算法：素数/203

4.4最大公因子： 欧几里德算法/204

练习4.4最大公因子：欧几里德算法/209

4.5算术基本原理/210

练习4.5算术基本原理/213

4.6本章小结和历史回顾/214

补充练习4/216

第5章关系和函数/219

5.1笛卡尔积和关系/220

练习5.1笛卡尔积和关系/223

5.2函数： 普通函数和一对一函数/223

练习5.2函数：普通函数和一对一函数/228

5.3到上函数： 第二类Stirling数/230

练习5.3到上函数：第二类Stirling数/235

5.4特殊函数/236

练习5.4特殊函数/240

5.5鸽巢原理/241

练习5.5鸽巢原理/244

5.6函数复合和逆函数/246

练习5.6函数复合和逆函数/253

5.7计算复杂性/255

练习5.7计算复杂性/258

5.8算法分析/259

练习5.8算法分析/264

5.9本章小结和历史回顾/266

补充练习5/268

第6章语言： 有限状态机/272

6.1语言： 字符串的集合理论/272

练习6.1语言：字符串的集合理论/280

6.2有限状态机： 初步认识/281

练习6.2有限状态机：初步认识/286

6.3有限状态机： 再次认识/287

练习6.3有限状态机：再次认识/292

6.4本章小结和历史回顾/293

补充练习6/294

第7章关系： 再次认识/297

7.1再论关系： 关系的性质/297

练习7.1再论关系：关系的性质/302

7.2计算机识别： 零么矩阵和有向图/303

练习7.2计算机识别：零幺矩阵和有向图/311

7.3偏序： 哈斯图/313

练习7.3偏序：哈斯图/320

7.4等价关系与划分/322

练习7.4等价关系与划分/325

7.5有限状态机： 最小化过程/326

练习7.5有限状态机：最小化过程/330

7.6本章小结和历史回顾/331

补充练习7/333

第二部分计数的深入主题/ 337

第8章容斥原理/3398.1容斥原理的概念/339

练习8.1容斥原理的概念/348

8.2容斥原理的推广/350

练习8.2容斥原理的推广/353

8.3错排： 都不在正确位置/353

练习8.3错排：都不在正确位置/354

8.4车多项式/355

8.5带禁止位置的排列/357

练习8.4车多项式和8.5带禁止位置的排列/360

8.6本章小结和历史回顾/361

补充练习8/362

第9章生成函数/364

9.1一些启发性例子/364

练习9.1一些启发性例子/366

9.2定义与例子： 计算技巧/367

练习9.2定义与例子：计算技巧/378

9.3整数的拆分/380

练习9.3整数的拆分/382

9.4指数生成函数/383

练习9.4指数生成函数/386

9.5求和算子/387

练习9.5求和算子/388

9.6本章小结和历史回顾/388

补充练习9/390

第10章递推关系/392

10.1一阶线性递推关系/392

练习10.1一阶线性递推关系/399

10.2二阶线性齐次常系数递推关系/400

练习10.2二阶线性齐次常系数递推关系/410

10.3非齐次递推关系/412

练习10.3非齐次递推关系/421

10.4生成函数方法/422

练习10.4生成函数方法/426

10.5一种特殊的非线性递推关系（可选）/427

练习10.5一种特殊的非线性递推关系（可选）/431

10.6分治算法（可选）/434

练习10.6分治算法（可选）/440

10.7本章小结和历史回顾/442

补充练习10/443

第三部分图论及其应用/ 449

第11章图论简介/451

11.1定义和例子/451

练习11.1定义和例子/455

11.2子图、补图和图的同构/457

练习11.2子图、补图和图的同构/463

11.3顶点度： 欧拉迹和欧拉闭迹/465

练习11.3顶点度：欧拉迹和欧拉闭迹/470

11.4平面图/473

练习11.4平面图/483

11.5哈密顿路径和哈密顿圈/486

练习11.5哈密顿路径和哈密顿圈/491

11.6图着色和色多项式/493

练习11.6图着色和色多项式/497

11.7本章小结和历史回顾/499

补充练习11/501

第12章树/506

12.1定义、性质和例子/506

练习12.1定义、性质和例子/509

12.2根树/511

练习12.2根树/522

12.3树和排序/525

练习12.3树和排序/528

12.4带权树和前缀码/528

练习12.4带权树和前缀码/532

12.5重连通分支和关节点/532

练习12.5重连通分支和关节点/538

12.6本章小结和历史回顾/539

补充练习12/540

第13章最优化和匹配/545

13.1Dijkstra最短路径算法/545

练习13.1Dijkstra最短路径算法/550

13.2最小生成树： Kruskal算法和Prim算法/551

练习13.2最小生成树：Kruskal算法和Prim算法/554

13.3运输网络： 最大流最小割定理/555

练习13.3运输网络：最大流最小割定理/566

13.4匹配定理/567

练习13.4匹配定理/573

13.5本章小结和历史回顾/574

补充练习13/576

第四部分现代应用代数/ 579

第14章环和模算术/581

14.1环结构： 定义和例子/581

练习14.1环结构：定义和例子/585

14.2环性质和子结构/586

练习14.2环性质和子结构/590

14.3整数模n/592

练习14.3整数模n/600

14.4环同态与环同构/602

练习14.4环同态与环同构/608

14.5本章小结和历史回顾/608

补充练习14/611

第15章布尔代数和开关函数/614

15.1开关函数： 析取范式与合取范式/614

练习15.1开关函数：析取范式与合取范式/620

15.2门网络： 乘积最小和与卡诺图/621

练习15.2门网络: 乘积最小和与卡诺图/628

15.3进一步的应用： 无关情况/629

练习15.3进一步的应用：无关情况/632

15.4布尔代数的结构（可选）/633

练习15.4布尔代数的结构（可选）/640

15.5本章小结和历史回顾/640

补充练习15/641

第16章群、编码理论和Polya计数法/644

16.1定义、例子和基本性质/644

练习16.1定义、例子和基本性质/649

16.2同态、同构和循环群/650

练习16.2同态、同构和循环群/653

16.3陪集和拉格朗日定理/653

练习16.3陪集和拉格朗日定理/654

16.4RSA密码系统（可选）/655

练习16.4RSA密码系统（可选）/657

16.5编码理论基础/657

练习16.5编码理论基础/661

16.6Hamming距/661

16.7奇偶校验与生成矩阵/664

练习16.6Hamming距和16.7奇偶校验与生成矩阵/667

16.8群码： 利用陪集首项译码/668

16.9Hamming矩阵/671

练习16.8群码：利用陪集首项译码和16.9Hamming矩阵/672

16.10计数与等价： Burnside定理/673

练习16.10计数与等价：Burnside定理/677

16.11循环指标/678

练习16.11循环指标/680

16.12方案清单： Polya计数法/681

练习16.12方案清单：Polya计数法/684

16.13本章小结和历史回顾/685

补充练习16/687

第17章有限域和组合设计/690

17.1多项式环/690

练习17.1多项式环/696

17.2不可约多项式： 有限域/697

练习17.2不可约多项式：有限域/702

17.3拉丁方/704

练习17.3拉丁方/707

17.4有限几何和仿射平面/708

练习17.4有限几何和仿射平面/711

17.5区组设计和射影平面/711

练习17.5区组设计和射影平面/714

17.6本章小结和历史回顾/715

补充练习17/717

附录1指数函数与对数函数/719

附录2矩阵、矩阵运算和行列式/727

附录3可数集与不可数集/739

奇数练习答案与提示/749

中英文名词对照表/870

ⅩⅦ记号