第一部分 数理逻辑 3
第1章 命题逻辑 3
1.1命题与逻辑联结词 3
1.2命题公式及其赋值 7
1.3命题公式的等价 9
1.4联结词的完备集 12
1.5命题公式的范式表示 13
1.6命题公式的蕴涵 19
1.7命题逻辑的推理方法 21
习题一 23
第2章 一阶谓词逻辑 27
2.1量词化逻辑 27
2.2谓词公式及其赋值 30
2.3谓词公式的等价与范式表示 33
2.4谓词公式的蕴涵 37
2.5谓词逻辑的推理方法 39
习题二 42
第二部分 集合与关系 47
第3章 集合代数 47
3.1集合的基本概念 47
3.2集合的运算 49
3.3幂集和笛卡儿集 51
习题三 53
第4章 二元关系 55
4.1二元关系及其表示 55
4.2关系的性质 57
4.3关系的运算 59
4.4关系的闭包 61
习题四 65
第5章 特殊关系 67
5.1等价关系 67
5.2偏序关系 69
5.3全序集与良序集 71
习题五 73
第6章 函数 75
6.1函数的定义与性质 75
6.2单射、满射和双射 77
6.3函数的复合与逆函数 78
6.4集合的基数、可数集和不可数集 81
习题六 85
第三部分 数论与组合论 89
第7章 初等数论 89
7.1整数集合 89
7.2商和余数 90
7.3整除和素因子分解 92
7.4最大公因子 93
7.5数学归纳法 95
习题七 97
第8章 基本计数方法 99
8.1排列计数 99
8.2组合计数 101
8.3组合恒等式 104
8.4容斥原理 106
8.5鸽巢原理 108
习题八 110
第9章 生成函数和递推关系 112
9.1序列与生成函数 112
9.2组合问题的生成函数 115
9.3递推关系式及其解 118
9.4递推关系式的生成函数求解 123
习题九 126
第四部分 图论 131
第10章 图的基本概念 131
10.1图 131
10.2通路与回路 136
10.3图的连通性 138
10.4图的矩阵表示 141
习题十 146
第11章 树及其应用 148
11.1无向树及其性质 148
11.2生成树 149
11.3根树及其应用 151
习题十 155
第12章 平面图及其应用 157
12.1平面图的基本概念 157
12.2欧拉公式 158
12.3平面图的判断 159
12.4平面图的对偶图 160
12.5平面的点着色与图的着色 161
习题十二 163
第13章 欧拉图与哈密顿图 164
13.1欧拉图与中国邮递员问题 164
13.2哈密顿图与推销商问题 168
习题十三 173
第五部分 代数结构 177
第14章 代数系统 177
14.1二元运算及其性质 177
14.2代数系统的定义与特异元 178
习题十四 179
第15章 半群与群 181
15.1半群 181
15.2群和子群 183
15.3交换群和循环群 186
15.4陪集与拉格朗日定理 187
15.5正规子群与商群 189
15.6群的同态与同构 190
习题十五 193
第16章 环与域 195
16.1环的定义及其性质 195
16.2整环与域 197
习题十六 198
第17章 格与布尔代数 199
17.1格的定义与性质 199
17.2子格与格同态 201
17.3分配格与有补格 204
17.4布尔代数 206
17.5布尔表达式 209
习题十七 214
第六部分 应用 218
第18章 典型应用 218
18.1数字逻辑电路设计 218
18.2形式语言 220
18.3有限状态自动机 229
18.4关系数据库管理系统 235
18.5网络 236
18.6群码 242
习题十八 244
附录 离散数学模拟试题 248
参考文献 259