第1章 命题逻辑 1
1.1命题的表示与逻辑联结词 1
1.2命题合适公式与真值表 6
1.3命题公式的等价 9
1.4命题公式的范式表示 13
1.5命题公式的蕴含 17
1.6命题逻辑的推理方法 20
1.7逻辑联结词的功能完备集 24
1.8应用：数字逻辑电路设计 26
第2章 一阶谓词逻辑 30
2.1量词化逻辑 30
2.2谓词合适公式及其解释 33
2.3谓词公式的等价与范式表示 37
2.4谓词公式的蕴含 42
2.5谓词逻辑的推理方法 45
2.6应用：逻辑程序设计 49
第3章 集合及其运算 52
3.1集合的基本概念 52
3.2集合间的运算 55
3.3集合的范式表示 58
3.4集合的幂集和笛卡尔集 60
3.5应用：形式语言 62
第4章 初等数论和证明方法 66
4.1整数集合 66
4.2商和余数 68
4.3整除和素因子分解 70
4.4最大公因子 72
4.5数学归纳法 74
4.6应用：随机数 77
第5章 二元关系 79
5.1二元关系及其表示 79
5.2二元关系的性质 82
5.3关系的运算 84
5.4二元关系的闭包 87
5.5等价关系 91
5.6偏序关系 94
5.7应用：关系数据库管理系统 99
第6章 函数 101
6.1一般集合的函数概念 101
6.2单射、满射和双射 104
6.3函数的递归定义 108
6.4集合的基数、可数集和不可数集 111
6.5应用：算法的复杂性表示 116
第7章 基本计数方法 120
7.1排列计数 120
7.2组合计数 123
7.3组合恒等式 126
7.4容斥原理 128
7.5鸽巢原理 131
第8章 生成函数和递推关系 134
8.1序列与生成函数 134
8.2组合问题的生成函数 137
8.3递推关系式及其解 141
8.4递推关系式的生成函数求解 146
8.5应用：排序算法 150
第9章 无向图和有向图 153
9.1图的基本概念 153
9.2图的道路与连通性 161
9.3图的矩阵表示 166
9.4独立集、点团和极图问题 174
9.5图的着色 179
第10章 基本图类和算法 186
10.1树与生成树 186
10.2根树及其应用 190
10.3图的生成树构造和计数 196
10.4平面图与对偶图 203
10.5欧拉图及其应用 207
10.6哈密顿图及其应用 212
10.7图的匹配与匈牙利算法 217
10.8网络 222
第11章 群和环 230
11.1运算与代数系统 230
11.2半群 233
11.3群和子群 236
11.4交换群和循环群 239
11.5陪集与拉格朗日定理 241
11.6同态与同构 243
11.7环和域 246
11.8应用：群码 250
第12章 格与布尔代数 253
12.1格的两个等价定义 253
12.2格的性质和格同态 256
12.3分配格和有补格 259
12.4布尔代数 262
附录 266
一、本书使用记号一览 266
二、离散数学术语的中、英文对照（以汉语拼音为序） 268
三、离散数学自测试题 276
参考文献 279