第1章 命题逻辑 1
1.1命题与命题联结词 1
1.1.1命题 1
1.1.2命题联结词 2
习题1.1 6
1.2命题公式及其分类 7
1.2.1命题公式 7
1.2.2公式的赋值与分类 8
习题1.2 10
1.3等值演算 10
1.3.1基本等值式 10
1.3.2等值演算 12
习题1.3 14
1.4对偶与范式 15
1.4.1对偶 15
1.4.2范式 16
1.4.3主范式 18
习题1.4 21
1.5推理理论 22
1.5.1命题的蕴含关系 22
1.5.2构造推理的形式证明 24
习题1.5 27
1.6命题逻辑在门电路中的应用介绍 28
习题1.6 29
1.7例题解析 29
复习题一 32
第2章 谓词逻辑 35
2.1谓词逻辑的基本概念 35
2.1.1个体与谓词 35
2.1.2量词 36
习题2.1 39
2.2谓词合式公式及解释 40
2.2.1谓词公式 40
2.2.2谓词公式的解释 41
2.2.3谓词公式的类型 43
习题2.2 44
2.3谓词逻辑等值式 44
习题2.3 47
2.4谓词逻辑推理理论 47
习题2.4 52
2.5例题解析 53
复习题二 56
第3章 集合论 59
3.1预备知识——整数的性质 59
3.1.1整除与带余除法 59
3.1.2最大公因数与最小公倍数 61
3.1.3同余 64
习题3.1 65
3.2集合 65
3.2.1集合的基本概念 65
3.2.2集合的表示 66
习题3.2 67
3.3集合的关系与运算 68
3.3.1集合间的基本关系 68
3.3.2幂集 69
3.3.3集合的基本运算 70
3.3.4文氏图 70
3.3.5主要的运算律 70
3.3.6集合运算的成员表 72
习题3.3 74
3.4有限集合中元素的计数 75
3.4.1文氏图法计数 75
3.4.2容斥原理 76
习题3.4 77
3.5例题解析 77
复习题三 79
第4章 关系 81
4.1集合的笛卡尔积 81
习题4.1 82
4.2关系及其表示 83
4.2.1关系的基本概念 83
4.2.2关系的矩阵和图的表示 84
习题4.2 86
4.3复合关系与逆关系 87
4.3.1复合关系 87
4.3.2复合关系的性质 88
4.3.3关系的幂和逆关系 89
习题4.3 90
4.4关系的性质 91
习题4.4 95
4.5关系的闭包 96
4.5.1关系闭包及其性质 96
4.5.2关系闭包的求法 97
习题4.5 102
4.6等价关系 102
4.6.1集合的划分 102
4.6.2等价关系 104
4.6.3等价类 104
习题4.6 107
4.7偏序关系 107
4.7.1偏序关系和拟序关系 107
4.7.2哈斯图 109
4.7.3偏序集的特殊元素 110
4.7.4全序关系和良序关系 112
习题4.7 113
4.8例题解析 114
复习题四 120
第5章 函数 122
5.1函数的基本概念 122
习题5.1 124
5.2特殊函数与特征函数 125
5.2.1特殊函数 125
5.2.2特征函数 126
习题5.2 128
5.3逆函数与复合函数 129
5.3.1逆函数 129
5.3.2复合函数 130
习题5.3 132
5.4集合的势与无限集合 133
5.4.1集合的势 133
5.4.2可数集 134
习题5.4 136
5.5例题解析 136
复习题五 138
第6章 图论基础 140
6.1图的基本概念 140
6.1.1图的定义及相关概念 141
6.1.2结点的度 142
6.1.3完全图和补图 144
6.1.4子图与图的同构 145
习题6.1 147
6.2图的连通性 148
6.2.1通路 148
6.2.2图的连通性 149
6.2.3割边和割点 150
习题6.2 151
6.3图的矩阵表示 151
6.3.1无向图的关联矩阵 151
6.3.2无环有向图的关联矩阵 152
6.3.3有向图的邻接矩阵 153
6.3.4无向简单图的邻接矩阵 154
6.3.5有向图的可达矩阵 155
习题6.3 155
6.4欧拉图与哈密尔顿图 156
6.4.1欧拉图 156
6.4.2哈密尔顿图 160
习题6.4 162
6.5图论的应用 163
6.5.1最短路问题 163
6.5.2中国邮递员问题 1655
6.5.3旅行售货员问题 167
习题6.5 169
6.6例题解析 170
复习题六 173
第7章 特殊图类 176
7.1树 176
7.1.1树的定义及性质 176
7.1.2生成树 178
7.1.3最小生成树 180
习题7.1 181
7.2根树 182
7.2.1根树及相关概念 182
7.2.2二元树 183
7.2.3二元树的一个应用——前缀码 185
习题7.2 188
7.3二部图与匹配 189
7.3.1二部图的概念及性质 189
7.3.2二部图的匹配 189
习题7.3 190
7.4平面图 191
7.4.1平面图的定义 191
7.4.2欧拉公式 193
7.4.3库拉图斯基定理 195
习题7.4 196
7.5例题解析 196
复习题七 199
第8章 代数系统 201
8.1运算与代数系统 201
8.1.1运算 201
8.1.2二元运算的性质 203
8.1.3代数系统 207
习题8.1 208
8.2半群与独异点 209
8.2.1半群与独异点 209
8.2.2子代数 210
8.2.3幂 210
习题8.2 212
8.3群的定义与性质 213
8.3.1群的定义 213
8.3.2群的性质 216
习题8.3 217
8.4子群及其特征 218
习题8.4 220
8.5循环群与置换群 220
8.5.1循环群 220
8.5.2置换群 222
习题8.5 224
8.6陪集与拉格朗日定理 224
习题8.6 227
8.7同态与同构 227
习题8.7 231
8.8环和域 231
8.8.1环的定义及其性质 231
8.8.2子环 233
8.8.3整环和域 234
习题8.8 236
8.9例题解析 236
复习题八 238
第9章 格和布尔代数 240
9.1格的定义及性质 240
9.1.1偏序集的性质 240
9.1.2格的定义 241
9.1.3格的对偶原理和性质 243
习题9.1 245
9.2格的代数定义 245
习题9.2 247
9.3特殊格 247
9.3.1分配格 247
9.3.2有界格和有补格 248
9.3.3有补分配格 249
习题9.3 250
9.4布尔代数 251
习题9.4 253
9.5例题解析 253
复习题九 255
部分习题参考答案与提示 256
参考文献 281