第一篇 数理逻辑 3
第1章 命题逻辑 3
1.1 命题与联结词 3
1.1.1 基本知识 3
1.1.2 例题 5
1.1.3 习题 8
1.2 命题公式 9
1.2.1 基本知识 9
1.2.2 例题 10
1.2.3 习题 13
1.3 等值演算 14
1.3.1 基本知识 14
1.3.2 例题 16
1.3.3 习题 18
1.4 命题公式的范式 19
1.4.1 基本知识 19
1.4.2 例题 22
1.4.3 习题 25
1.5 联结词的功能完全集 25
1.5.1 基本知识 25
1.5.2 例题 27
1.5.3 习题 30
1.6 永真蕴涵式 30
1.6.1 基本知识 30
1.6.2 例题 32
1.6.3 习题 35
1.7 命题逻辑的推理理论 36
1.7.1 基本知识 36
1.7.2 例题 37
1.7.3 习题 39
1.8 命题逻辑推理的机械化方法 40
1.8.1 基本知识 40
1.8.2 例题 42
1.8.3 习题 46
第2章 一阶逻辑 47
2.1 一阶逻辑的基本概念 47
2.1.1 基本知识 47
2.1.2 例题 48
2.1.3 习题 50
2.2 一阶逻辑公式 52
2.2.1 基本知识 52
2.2.2 例题 54
2.2.3 习题 58
2.3 一阶逻辑的等值演算与前束范式 59
2.3.1 基本知识 59
2.3.2 例题 59
2.3.3 习题 62
2.4 一阶逻辑的推理理论 62
2.4.1 基本知识 62
2.4.2 例题 63
2.4.3 习题 69
第二篇 集合论 73
第3章 集合 73
3.1 集合的定义 73
3.1.1 基本知识 73
3.1.2 例题 74
3.1.3 习题 76
3.2 集合的基本运算 77
3.2.1 基本知识 77
3.2.2 例题 80
3.2.3 习题 84
3.3 有限集合的计数 86
3.3.1 基本知识 86
3.3.2 例题 87
3.3.3 习题 89
3.4 集合表达式的相等与包含 90
3.4.1 基本知识 90
3.4.2 例题 92
3.4.3 习题 95
3.5 集合的特征函数 96
3.5.1 基本知识 96
3.5.2 例题 97
3.5.3 习题 98
第4章 关系 99
4.1 二元关系 99
4.1.1 基本知识 99
4.1.2 例题 100
4.1.3 习题 101
4.2 二元关系的表示及按性质分类 102
4.2.1 基本知识 102
4.2.2 例题 104
4.2.3 习题 108
4.3 二元关系的运算 110
4.3.1 基本知识 110
4.3.2 例题 110
4.3.3 习题 113
4.4 二元关系的合成 114
4.4.1 基本知识 114
4.4.2 例题 115
4.4.3 习题 118
4.5 关系的闭包 119
4.5.1 基本知识 119
4.5.2 例题 120
4.5.3 习题 123
4.6 等价关系和偏序关系 124
4.6.1 基本知识 124
4.6.2 例题 126
4.6.3 习题 128
第5章 函数 130
5.1 函数的基本概念 130
5.1.1 基本知识 130
5.1.2 例题 130
5.1.3 习题 131
5.2 函数的性质 132
5.2.1 基本知识 132
5.2.2 例题 132
5.2.3 习题 135
5.3 函数的复合与反函数 136
5.3.1 基本知识 136
5.3.2 例题 137
5.3.3 习题 138
5.4 可逆函数集与置换 139
5.4.1 基本知识 139
5.4.2 例题 140
5.4.3 习题 141
5.5 二元运算 141
5.5.1 基本知识 141
5.5.2 例题 142
5.5.3 习题 144
5.6 基数 145
5.6.1 基本知识 145
5.6.2 例题 147
5.6.3 习题 148
第三篇 代数系统 153
第6章 半群、语言和自动机 153
6.1 半群与语言 153
6.1.1 基本知识 153
6.1.2 例题 155
6.1.3 习题 156
6.2 语言和文法 157
6.2.1 基本知识 157
6.2.2 例题 158
6.2.3 习题 160
6.3 有限状态机 161
6.3.1 基本知识 161
6.3.2 例题 162
6.3.3 习题 163
6.4 有限状态自动机 163
6.4.1 基本知识 163
6.4.2 例题 165
6.4.3 习题 167
6.5 语言与自动机的关系 169
6.5.1 基本知识 169
6.5.2 例题 170
6.5.3 习题 174
第7章 群、环和域 175
7.1 群的基本概念 175
7.1.1 基本知识 175
7.1.2 例题 177
7.1.3 习题 177
7.2 子群 177
7.2.1 基本知识 177
7.2.2 例题 178
7.2.3 习题 179
7.3 群的同态与同构 179
7.3.1 基本知识 179
7.3.2 例题 180
7.3.3 习题 181
7.4 子群的陪集 181
7.4.1 基本知识 181
7.4.2 例题 183
7.4.3 习题 183
7.5 对称群、置换群、正规性与商群 183
7.5.1 基本知识 183
7.5.2 例题 185
7.5.3 习题 186
7.6 群在集合上的作用 186
7.6.1 基本知识 186
7.6.2 例题 187
7.6.3 习题 189
7.7 同态基本定理与同构定理 190
7.7.1 基本知识 190
7.7.2 例题 190
7.7.3 习题 191
7.8 环的基本概念 191
7.8.1 基本知识 191
7.8.2 例题 192
7.8.3 习题 193
7.9 子环、理想与商环 194
7.9.1 基本知识 194
7.9.2 例题 195
7.9.3 习题 196
7.10 交换环中的因子分解 197
7.10.1 基本知识 197
7.10.2 例题 198
7.10.3 习题 199
7.11 多项式环 200
7.11.1 基本知识 200
7.11.2 例题 200
7.11.3 习题 201
7.12 多项式环的因子分解 202
7.12.1 基本知识 202
7.12.2 例题 203
7.12.3 习题 203
7.13 域的基本概念 204
7.13.1 基本知识 204
7.13.2 例题 205
7.13.3 习题 206
7.14 分裂域 206
7.14.1 基本知识 206
7.14.2 例题 207
7.14.3 习题 208
7.15 有限域 208
7.15.1 基本知识 208
7.15.2 例题 209
7.15.3 习题 210
第8章 格与布尔代数 211
8.1 格的概念 211
8.1.1 基本知识 211
8.1.2 例题 213
8.1.3 习题 214
8.2 分配格 215
8.2.1 基本知识 215
8.2.2 例题 216
8.2.3 习题 217
8.3 有补格 217
8.3.1 基本知识 217
8.3.2 例题 218
8.3.3 习题 218
8.4 布尔代数 219
8.4.1 基本知识 219
8.4.2 例题 220
8.4.3 习题 220
8.5 布尔表达式 221
8.5.1 基本知识 221
8.5.2 例题 222
8.5.3 习题 222
8.6 数字电路与最小化 223
8.6.1 基本知识 223
8.6.2 例题 225
8.6.3 习题 226
第四篇 组合分析与算法数论 229
第9章 组合分析 229
9.1 计数 229
9.1.1 基本知识 229
9.1.2 例题 229
9.1.3 习题 230
9.2 排列与组合 231
9.2.1 基本知识 231
9.2.2 例题 232
9.2.3 习题 235
9.3 递推序列 235
9.3.1 基本知识 235
9.3.2 例题 236
9.3.3 习题 241
9.4 抽屉原理 242
9.4.1 基本知识 242
9.4.2 例题 242
9.4.3 习题 245
9.5 生成函数 246
9.5.1 基本知识 246
9.5.2 例题 247
9.5.3 习题 250
第10章 算法数论 252
10.1 算法 252
10.1.1 基本知识 252
10.1.2 例题 257
10.1.3 习题 258
10.2 整数论 259
10.2.1 基本知识 259
10.2.2 例题 263
10.2.3 习题 264
10.3 与整数有关的典型算法 266
10.3.1 基本知识 266
10.3.2 例题 268
10.3.3 习题 269
10.4 素性测试、因数分解与公钥密码学 270
10.4.1 基本知识 270
10.4.2 例题 277
10.4.3 习题 280
10.5 有限域上的椭圆曲线算术和ECC 281
10.5.1 基本知识 281
10.5.2 例题 284
10.5.3 习题 286
10.6 配对和基于身份的公钥密码体制 287
10.6.1 双线性配对 287
10.6.2 基于身份的密码 291
第五篇 图论 297
第11章 图 297
11.1 图的基本概念 297
11.1.1 基本知识 297
11.1.2 例题 299
11.1.3 习题 302
11.2 连通性 303
11.2.1 基本知识 303
11.2.2 例题 304
11.2.3 习题 305
11.3 平面图 306
11.3.1 基本知识 306
11.3.2 例题 307
11.3.3 习题 308
11.4 欧拉道路与哈密顿道路 309
11.4.1 基本知识 309
11.4.2 例题 310
11.4.3 习题 312
第12章 有向图和树 314
12.1 有向图的基本概念 314
12.1.1 基本知识 314
12.1.2 例题 315
12.1.3 习题 317
12.2 有向图的连通性 317
12.2.1 基本知识 317
12.2.2 例题 318
12.2.3 习题 319
12.3 树 320
12.3.1 基本知识 320
12.3.2 例题 321
12.3.3 习题 323
12.4 二元树和Huffman树 323
12.4.1 基本知识 323
12.4.2 例题 324
12.4.3 习题 325
参考文献 327