目录

●第1章 集合 1
1.1 集合的基本概念 1
1.2 集合的运算及性质 3
1.3 有限集的计数 6
1.4 本章小结 11
第1章习题 12

第2章 二元关系 16
2.1 关系的定义及运算 16
2.2 关系的性质 22
2.3 等价关系与划分 25
2.4 偏序关系 29
2.5 本章小结 34
第2章习题 35

第3章 函数 41
3.1 函数的基本概念 41
3.2 函数的复合与逆函数 46
3.3 无限集的计数 49
3.4 本章小结 55
第3章习题 56

第4章 初等数论基础 60
4.1 整除性 60
4.2 素数 66
4.3 同余 71
4.4 在信息科学中的应用 78
4.5 本章小结 82
第4章习题 83

第5章 图 88
5.1 无向图 88
5.2 通路和连通性 93
5.3 图的矩阵表示 99
5.4 有向图 101
5.5 本章小结 105
第5章习题 106

第6章 树 112
6.1 树的基本概念 113
6.2 生成树与很优树 119
6.3 树的遍历 128
6.4 本章小结 133
第6章习题 133

第7章 图论经典问题 137
7.1 欧拉图 137
7.2 哈密顿图 143
7.3 二部图及匹配 149
7.4 平面图与图的着色 154
7.5 本章小结 163
第7章习题 164

第8章 鸽巢原理与拉姆齐定理 172
8.1 鸽巢原理的基本形式 172
8.2 鸽巢原理的加强形式 175
8.3 拉姆齐定理 178
8.4 本章小结 182
第8章习题 183

第9章 基本计数方法 185
9.1 集合的排列和组合 185
9.2 多重集的排列和组合 189
9.3 二项式定理及应用 193
9.4 斯特林数 202
9.5 本章小结 207
第9章习题 208

第10章 高级计数方法 210
10.1 递推关系 210
10.2 普通型生成函数及应用 219
10.3 指数型生成函数及应用 230
10.4 卡塔兰数及其生成函数 232
10.5 正整数分拆数的生成函数 234
10.6 本章小结 237
第10章习题 237

第11章 群 240
11.1 半群及群 240
11.2 置换群 243
11.3 循环群 247
11.4 正规子群及商群 249
11.5 群同态及同构基本定理 254
11.6 伯恩赛德引理及波利亚计数定理 257
11.7 本章小结 263
第11章习题 264

第12章 环与域 267
12.1 环的定义及性质 267
12.2 理想及商环 269
12.3 环同态和同构基本定理 272
12.4 分式域 274
12.5 多项式环 276
12.6 单代数扩域 278
12.7 本章小结 281
第12章习题 281

第13章 命题逻辑 284
13.1 命题与联结词 284
13.2 命题公式语法及语义 286
13.3 命题公式的等价 289
13.4 命题公式的范式 294
13.5 本章小结 298
第13章习题 299

第14章 谓词逻辑 301
14.1 个体、谓词和量词 301
14.2 谓词公式语法及语义 306
14.3 谓词公式的等价 309
14.4 谓词公式的范式 314
14.5 本章小结 317
第14章习题 318

第15章 逻辑推理 321
15.1 语义蕴涵与自然演绎 321
15.2 命题逻辑后继式规则 324
15.3 谓词逻辑后继式规则 330
15.4 归结原理 334
15.5 本章小结 337
第15章习题 338

第16章 形式语言与文法 340
16.1 形式语言 340
16.2 文法 344
16.3 文法的分类 348
16.4 自动机 350
16.5 本章小结 354
第16章习题 355

第17章 有限状态自动机与正则语言 358
17.1 有限状态自动机 358
17.2 非确定性有限状态自动机 365
17.3 正则表达式 370
17.4 正则语言的泵引理 373
17.5 本章小结 376
第17章习题 377

第18章 上下文无关语言 382
18.1 上下文无关文法 382
18.2 文法分析和二义性 388
18.3 巴克斯－诺尔范式 397
18.4 下推自动机 401
18.5 本章小结 407
第18章习题 409

第19章 图灵机 411
19.1 标准图灵机 411
19.2 图灵机的变种 421
19.3 通用图灵机 426
19.4 可计算性和计算复杂性介绍 428
19.5 本章小结 431
第19章习题 432

参考文献 435

名词索引 437