绪论 1
第1章 命题逻辑 4
1.1 命题及其表示 5
1.1.1 命题 5
1.1.2 命题的分类 6
1.1.3 命题标识符 6
习题1.1 7
1.2 常用逻辑联结词 7
1.2.1 否定联结词 7
1.2.2 合取联结词 8
1.2.3 析取联结词 8
1.2.4 条件联结词 9
1.2.5 双条件联结词 10
习题1.2 11
1.3 命题公式与翻译 12
1.3.1 命题公式 12
1.3.2 命题的符号化 13
习题1.3 14
1.4 真值表与等价公式 15
1.4.1 真值表 15
1.4.2 等价公式 16
习题1.4 21
1.5 命题公式的分类与蕴涵式 21
1.5.1 命题公式的分类 21
1.5.2 重言式与矛盾式的性质 22
1.5.3 蕴涵式 22
习题1.5 25
1.6 其他逻辑联结词和最小功能完备联结词组 26
1.6.1 其他逻辑联结词 26
1.6.2 最小功能完备联结词组 28
习题1.6 28
1.7 对偶与范式 28
1.7.1 对偶 28
1.7.2 范式 30
1.7.3 主范式 32
习题1.7 42
1.8 推理理论 43
1.8.1 直接证明法 43
1.8.2 间接证明法 46
习题1.8 48
本章解析 48
第2章 谓词逻辑 51
2.1 谓词的基本定义 51
2.1.1 个体和谓词 52
2.1.2 量词 53
习题2.1 54
2.2 谓词公式与翻译 54
2.2.1 谓词公式 54
2.2.2 谓词公式的翻译 55
习题2.2 56
2.3 自由与约束 57
习题2.3 59
2.4 谓词逻辑的等价式与蕴涵式 59
2.4.1 谓词公式的赋值 59
2.4.2 谓词公式的分类 60
2.4.3 谓词逻辑的等价式 61
2.4.4 谓词逻辑的蕴涵式 65
习题2.4 66
2.5 谓词公式范式 67
2.5.1 前束范式 67
2.5.2 前束析取范式和前束合取范式 68
2.5.3 斯柯林范式 69
习题2.5 69
2.6 谓词逻辑的推理理论 70
习题2.6 75
本章解析 75
第3章 集合 78
3.1 集合的基本定义 78
3.1.1 集合与元素 78
3.1.2 集合间的关系 79
3.1.3 幂集 81
习题3.1 82
3.2 集合的运算 83
3.2.1 集合的交与并 83
3.2.2 集合的差与补 85
3.2.3 集合的对称差 87
习题3.2 89
3.3 包含排斥原理 90
习题3.3 94
本章解析 95
第4章 关系 97
4.1 序偶与笛卡尔积 97
4.1.1 序偶 97
4.1.2 笛卡尔积 98
习题4.1 100
4.2 关系及其表示 101
4.2.1 关系的定义 101
4.2.2 几种特殊的关系 102
4.2.3 关系的表示 103
习题4.2 105
4.3 关系的性质 105
4.3.1 关系的性质 105
4.3.2 关系性质的判定 107
习题4.3 108
4.4 复合关系和逆关系 110
4.4.1 复合关系 110
4.4.2 逆关系 113
习题4.4 116
4.5 关系的闭包 116
习题4.5 120
4.6 等价关系与相容关系 120
4.6.1 集合的划分和覆盖 120
4.6.2 等价关系与等价类 122
4.6.3 相容关系 126
习题4.6 129
4.7 偏序关系 130
4.7.1 偏序关系 130
4.7.2 哈斯图 130
4.7.3 特殊元素 132
4.7.4 全序和良序 134
习题4.7 135
本章解析 136
第5章 函数 138
5.1 函数的定义 138
习题5.1 143
5.2 几种特殊函数 143
习题5.2 145
5.3 函数的运算 146
5.3.1 复合运算 146
5.3.2 逆运算 148
习题5.3 150
5.4 置换 151
习题5.4 152
5.5 基数 153
5.5.1 无限集合 153
5.5.2 基数的定义 154
5.5.3 可数集与不可数集 155
习题5.5 156
本章解析 157
第6章 代数结构 158
6.1 代数系统 159
6.1.1 n元运算 159
6.1.2 代数系统的定义 161
习题6.1 163
6.2 二元运算与特殊元素 164
6.2.1 二元运算的性质 164
6.2.2 代数系统中的特殊元素 168
6.2.3 利用运算表判断代数系统的性质 173
习题6.2 174
6.3 半群与含幺半群 176
6.3.1 半群及其性质 176
6.3.2 含幺半群及其性质 178
习题6.3 180
6.4 群与子群 182
6.4.1 群的定义 182
6.4.2 群的基本性质 183
6.4.3 群的元素的阶 187
6.4.4 子群 187
习题6.4 189
6.5 阿贝尔群、循环群和置换群 190
6.5.1 阿贝尔群 190
6.5.2 循环群 190
6.5.3 置换群 192
习题6.5 193
6.6 代数系统的同态与同构 194
习题6.6 197
6.7 环与域 198
6.7.1 环 198
6.7.2 域 200
习题6.7 200
本章解析 201
第7章 格与布尔代数 203
7.1 格 203
7.1.1 格的定义 203
7.1.2 格的性质 207
7.1.3 格的同态与同构 210
习题7.1 213
7.2 分配格与模格 214
7.2.1 分配格 214
7.2.2 模格 217
习题7.2 218
7.3 有界格与有补格 219
7.3.1 有界格 219
7.3.2 有补格 220
习题7.3 221
7.4 布尔代数 222
7.4.1 布尔代数的定义 222
7.4.2 布尔代数的性质 223
7.4.3 子布尔代数 225
7.4.4 布尔代数的同态与同构 226
7.4.5 布尔代数在电路设计中的应用 226
习题7.4 228
本章解析 229
第8章 图论 230
8.1 图的相关概念 230
8.1.1 图的基本定义 230
8.1.2 补图与子图 234
8.1.3 图的握手定理 235
8.1.4 图的同构 237
习题8.1 239
8.2 路与图的连通性 239
8.2.1 路与回路 239
8.2.2 图的连通性 241
习题8.2 244
8.3 图的存储矩阵 245
8.3.1 邻接矩阵 245
8.3.2 可达矩阵 247
8.3.3 关联矩阵 249
习题8.3 250
8.4 欧拉图与哈密顿图 251
8.4.1 欧拉图 251
8.4.2 哈密顿图 254
习题8.4 256
8.5 二部图与平面图 258
8.5.1 二部图 258
8.5.2 二部图的匹配 259
8.5.3 平面图 261
8.5.4 平面图的着色 266
习题8.5 267
8.6 树与生成树 268
8.6.1 无向树 268
8.6.2 生成树 271
8.6.3 最小生成树 272
习题8.6 274
8.7 根树及其应用 275
8.7.1 有向树 275
8.7.2 m叉树 276
8.7.3 最优二叉树 279
8.7.4 二叉树在计算机中的应用 280
习题8.7 285
8.8 图的应用 285
8.8.1 最短路径 285
8.8.2 关键路径 288
习题8.8 290
本章解析 291
参考文献 293