第1篇 数理逻辑 3
第1章 命题逻辑 3
1.1命题及其表示 3
1.1.1命题的基本概念 3
1.1.2命题分类 4
1.1.3命题标识符 4
1.2逻辑联结词 5
1.2.1否定联结词 5
1.2.2合取联结词 5
1.2.3析取联结词 6
1.2.4条件联结词 7
1.2.5双条件联结词 8
1.3命题公式与翻译 8
1.3.1命题公式 8
1.3.2命题的符号化 9
1.4真值表与命题公式分类 10
1.4.1真值表 10
1.4.2命题公式分类 12
1.5等价式与蕴含式 13
1.5.1等价式 13
1.5.2蕴含式 17
1.6逻辑联结词与联结词组 20
1.6.1其他逻辑联结词 20
1.6.2最小功能完备联结词组 23
1.7对偶式与范式 24
1.7.1对偶式与对偶原理 24
1.7.2命题公式的范式 25
1.7.3命题公式的主析取范式和主合取范式 27
1.8命题逻辑的推理理论 35
1.8.1推理规则 36
1.8.2推理定律 36
1.8.3推理方法 37
本章小结 41
习题 41
第2章 谓词逻辑 48
2.1个体、谓词和量词 48
2.1.1个体和谓词 48
2.1.2量词 51
2.2谓词公式与翻译 52
2.2.1谓词公式 52
2.2.2谓词逻辑的翻译 53
2.3约束变元与自由变元 54
2.4谓词公式的解释与分类 56
2.4.1谓词公式的解释 56
2.4.2谓词公式的分类 58
2.5谓词逻辑的等价式与蕴含式 59
2.5.1谓词逻辑的等价式 59
2.5.2谓词逻辑的蕴含式 63
2.6谓词公式范式 64
2.6.1前束范式 64
2.6.2斯柯林范式 66
2.7谓词逻辑的推理理论 66
2.7.1推理定律 66
2.7.2推理规则 67
2.7.3推理方法 69
本章小结 72
习题 72
第2篇 集合论 79
第3章 集合与关系 79
3.1集合的概念和表示法 79
3.1.1集合与元素 79
3.1.2集合间的关系 80
3.1.3幂集 82
3.1.4集合的数码表示 83
3.2集合的运算 84
3.2.1集合的几种基本运算 84
3.2.2集合运算的文氏图表示 84
3.2.3集合的运算定律 85
3.3有限集合中元素的计数 86
3.3.1文氏图法 86
3.3.2容斥原理法 87
3.4序偶与笛卡尔积 89
3.4.1序偶 89
3.4.2笛卡尔积 90
3.5关系及其表示 92
3.5.1关系的定义 93
3.5.2关系的表示 94
3.6复合关系和逆关系 96
3.6.1复合关系 96
3.6.2逆关系 99
3.7关系的性质与表示方法 100
3.7.1关系的性质 100
3.7.2关系图、关系矩阵与关系的性质 101
3.8关系的闭包运算 104
3.9集合的划分与等价关系 108
3.9.1集合的划分和覆盖 108
3.9.2等价关系与等价类 110
3.9.3相容关系 113
3.10偏序关系 115
3.10.1偏序关系的定义 115
3.10.2偏序关系的哈斯图 116
3.10.3偏序集中特殊的元素 118
3.10.4两种特殊的偏序集 120
本章小结 120
习题 121
第4章 函数 129
4.1函数的基本概念 129
4.2特殊的函数及特征函数 131
4.2.1特殊性质的函数 131
4.2.2特征函数 132
4.3逆函数与复合函数 133
4.3.1逆函数 133
4.3.2复合函数 134
4.4集合的势与无限集合 136
4.4.1集合的势 136
4.4.2可数集 137
本章小结 139
习题 139
第3篇 代数系统 143
第5章 代数系统 143
5.1代数系统的概念 143
5.1.1运算的概念 143
5.1.2代数系统的概念 144
5.2二元运算 145
5.2.1二元运算的性质 145
5.2.2集合上关于二元运算的特异元素 146
5.2.3利用运算表判断代数运算的性质 148
5.3半群与独异点 149
5.3.1半群及其性质 149
5.3.2含幺半群及其性质 150
5.4群与子群 151
5.4.1群的基本概念 151
5.4.2群的基本性质 152
5.4.3群的元素的阶 154
5.4.4子群及其判定定理 154
5.5同态与同构 155
5.6特殊群 158
5.6.1阿贝尔群 158
5.6.2循环群 158
5.6.3置换群 160
5.7 Lagrange定理与正规子群 162
5.7.1陪集与Lagrange定理 162
5.7.2正规子群、商群 164
5.8环与域 166
5.8.1环 166
5.8.2域 168
5.9群在编码理论中的应用 169
本章小结 174
习题 175
第6章 格与布尔代数 180
6.1格的概念及性质 180
6.1.1格的概念 180
6.1.2格的性质 182
6.2分配格与模格 188
6.2.1分配格 188
6.2.2模格 190
6.3有界格与有补格 191
6.3.1有界格 191
6.3.2有补格 192
6.4布尔代数 193
6.4.1布尔代数的概念 193
6.4.2布尔代数的性质 195
6.4.3子布尔代数 198
6.4.4布尔代数的同态与同构 199
6.4.5有限布尔代数的原子表示 199
6.5布尔表达式与布尔函数 203
6.5.1布尔表达式 203
6.5.2布尔函数 207
6.6布尔函数在电路设计中的应用 207
本章小结 209
习题 209
第4篇 图论 213
第7章 图论 213
7.1图的基本概念 213
7.1.1图的定义 213
7.1.2子图与补图 214
7.1.3结点的度 216
7.1.4图的同构 219
7.2路、回路与连通性 220
7.2.1路与回路 220
7.2.2图的连通性 220
7.3图的矩阵表示 223
7.3.1邻接矩阵 223
7.3.2可达矩阵 225
7.3.3关联矩阵 227
7.4欧拉图与哈密尔顿图 229
7.4.1欧拉图 229
7.4.2哈密尔顿图 232
7.5二部图及匹配 234
7.5.1二部图 234
7.5.2匹配 235
7.6平面图 237
7.6.1平面图定义 237
7.6.2欧拉公式 238
7.6.3平面图的对偶与着色 240
7.7树与生成树 243
7.7.1无向树的定义与性质 243
7.7.2无向图中的生成树与最小生成树 244
7.8根树及其应用 246
7.8.1有向树 246
7.8.2 m叉树 247
7.8.3最优二叉树 249
7.8.4二叉树在计算机中的应用 250
7.9最短路径问题 251
7.9.1问题的提出 251
7.9.2 Dijkstra算法 251
本章小结 253
习题 253
参考文献 262