目录
第1章基础知识/1
1.1集合与序列1
1.1.1集合的基本概念1
1.1.2集合的运算及性质4
1.1.3序列7
习题1.18
1.2数论基础10
习题1.214
1.3计数基础16
1.3.1加法法则与乘法法则16
1.3.2排列与组合17
1.3.3鸽巢原理23
1.3.4有限集合的计数——容斥原理26
1.3.5递推关系29
习题1.333
1.4布尔矩阵及其运算37
习题1.439
扩展阅读39
第2章命题逻辑/41
2.1命题逻辑的基本概念42
习题2.146
2.2命题公式及其分类47
习题2.250
2.3命题逻辑的等值演算51
习题2.356
2.4对偶与范式57
2.4.1对偶57
2.4.2析取范式与合取范式58
2.4.3主范式60离散数学及应用(第3版)目录习题2.466
2.5命题联结词的完备集68
习题2.569
2.6命题逻辑的推理69
习题2.676
扩展阅读77
第3章谓词逻辑/79
3.1谓词与量词80
3.1.1谓词80
3.1.2量词81
习题3.182
3.2谓词公式及分类82
习题3.285
3.3自然语言形式化85
习题3.388
3.4谓词逻辑的等值演算89
习题3.494
3.5前束范式94
习题3.596
3.6谓词逻辑的推理96
习题3.6103
扩展阅读104
第4章二元关系/107
4.1关系及其表示107
4.1.1有序对与笛卡儿积107
4.1.2二元关系的定义109
4.1.3二元关系的表示112
习题4.1114
4.2关系的运算115
4.2.1关系的基本运算115
4.2.2关系的幂和道路119
习题4.2121
4.3关系的性质122
4.3.1关系性质的定义和判断122
4.3.2关系运算对性质的保持126
习题4.3127
4.4关系的闭包129
习题4.4134
4.5等价关系和集合的划分135
4.5.1等价关系、等价类和商集135
4.5.2集合的划分137
4.5.3等价关系与划分的一一对应137
习题4.5138
4.6相容关系与集合的覆盖140
习题4.6141
扩展阅读142
第5章函数/143
5.1函数的定义143
习题5.1145
5.2函数的性质146
习题5.2147
5.3函数的复合148
习题5.3150
5.4逆函数151
习题5.4152
5.5计算机科学中的常用函数153
习题5.5159
5.6双射函数及集合的势160
习题5.6165
扩展阅读165
第6章偏序关系、偏序集与格/167
6.1偏序关系和偏序集167
6.1.1偏序关系和偏序集的定义与性质167
6.1.2积偏序和字典序169
6.1.3哈斯图170
习题6.1172
6.2偏序集中的特殊元素173
6.2.1偏序集中的特殊元素173
6.2.2拓扑排序176
6.2.3有限偏序集的高度与宽度178
习题6.2180
6.3格与布尔代数181
6.3.1格的定义181
6.3.2特殊的格185
6.3.3布尔代数190
习题6.3193
扩展阅读196
第7章代数结构/197
7.1运算与代数结构198
7.1.1运算与代数结构的定义198
7.1.2二元运算的性质200
习题7.1204
7.2群206
7.2.1半群与亚群206
7.2.2群的概念207
7.2.3群的性质209
7.2.4子群210
7.2.5群的同态与同构211
7.2.6循环群213
7.2.7变换群与置换群215
7.2.8陪集与拉格朗日定理217
习题7.2220
7.3环与域224
7.3.1环224
7.3.2域226
习题7.3227
7.4作为代数结构的格与布尔代数228
习题7.4231
扩展阅读231
第8章图论/232
8.1基本概念233
8.1.1无向图、有向图和握手定理233
8.1.2图的同构与子图240
8.1.3道路、回路与连通性242
8.1.4图的矩阵表示244
习题8.1246
8.2欧拉图250
习题8.2254
8.3哈密顿图255
习题8.3261
8.4平面图262
习题8.4269
8.5顶点支配、独立与覆盖271
习题8.5275
8.6匹配275
8.6.1匹配与最大匹配275
8.6.2霍尔定理及其应用280
8.6.3匹配与边覆盖283
8.6.4匹配与点覆盖285
8.6.5二部图中的最佳匹配289
习题8.6292
8.7图的着色295
习题8.7301
8.8网络与流302
8.8.1最大流与最小割302
8.8.2网络流的应用317
习题8.8322
8.9图的连通度324
习题8.9325
扩展阅读325
第9章树及其应用/328
9.1无向树328
习题9.1332
9.2支撑树及其应用333
习题9.2346
9.3最短道路树347
习题9.3351
9.4根树及其应用352
9.4.1根树的定义和基本概念352
9.4.2二叉树的遍历357
9.4.3最优二叉树与霍夫曼编码361
习题9.4364
扩展阅读366
第10章形式语言、自动机与正则表达式/367
10.1语言368
习题10.1371
10.2文法372
习题10.2378
10.3巴科斯诺尔范式和语法图379
习题10.3381
10.4有限状态自动机382
习题10.4388
10.5语言与自动机的关系391
习题10.5393
10.6正则表达式393
习题10.6395
10.7图灵机396
习题10.7399
扩展阅读399
附录A离散数学综合性研讨专题/402
A.1邮资、分油、登阶、台球与波利亚的果园402
A.1.1邮资问题402
A.1.2分油问题404
A.1.3登阶问题408
A.1.4台球问题410
A.1.5波利亚的果园问题412
A.2基于模运算的校验码415
A.2.1EAN13码415
A.2.2国际标准书号416
A.2.3第二代居民身份证416
A.2.4国际标准刊号418
A.3应用鸽巢原理的两个纸牌魔术418
A.3.1纸牌魔术A419
A.3.2纸牌魔术B421
A.4完美洗牌法421
A.5百囚犯问题424
A.615谜题427
A.7Chomp游戏428
A.8安全信息流的格模型431
A.9麻花辫434
A.10伯恩赛德引理与波利亚定理438
A.11顿时错乱问题443
A.12博弈树与决策树447
A.12.1博弈树447
A.12.2决策树449
A.13抽芽游戏与抱子甘蓝游戏453
A.13.1抽芽游戏453
A.13.2抱子甘蓝游戏456
A.14存储器轮458
A.14.1存储器轮及解决方法458
A.14.2德布鲁因序列460
A.15中国邮路问题464
A.16格雷码、超立方体图中的哈密顿道路、九连环和龙曲线467
A.16.1格雷码467
A.16.2超立方体图中的哈密顿道路469
A.16.3九连环与格雷码471
A.16.4龙曲线474
A.17社会网络中的结构平衡475
A.18市场清仓与单品拍卖477
A.19汉诺塔杂谈480
A.19.1汉诺塔图480
A.19.2汉诺塔的非递归算法483
A.19.3汉诺塔与格雷码484
A.19.4汉诺塔与普通二进制码487
A.20谢尔宾斯基三角形488
A.21密码算法简介495
在线附录列表/500
