第1章 命题逻辑 1
1.1命题和联结词 1
1.1.1命题的概念 1
1.1.2联结词 2
1.2合式公式与真值表 6
1.2.1合式公式 6
1.2.2真值表 6
1.3永真式和等价式 7
1.3.1永真式 7
1.3.2等价式 8
1.3.3代入规则和替换规则 9
1.4对偶式与蕴涵式 11
1.4.1对偶式 11
1.4.2蕴涵式 12
1.5范式和判定问题 13
1.5.1析取范式和合取范式 13
1.5.2主析取范式和主合取范式 15
1.6命题演算的推理理论 18
习题 21
第2章 谓词逻辑 25
2.1基本概念和表示 25
2.1.1个体、谓词和谓词形式 25
2.1.2量词 26
2.1.3合式谓词公式 28
2.1.4自由变元和约束变元 28
2.2谓词逻辑的翻译与解释 29
2.2.1谓词逻辑的翻译 29
2.2.2谓词公式的解释 30
2.3谓词逻辑的等价式与蕴涵式 31
2.4谓词逻辑中的推论理论 32
2.4.1推理规则 33
2.4.2推理实例 34
2.5谓词逻辑中公式范式 37
2.5.1前束范式 37
2.5.2斯柯林范式 38
习题 39
第3章 集合论 41
3.1集合的概念及其表示 41
3.2集合的运算及恒等式 43
3.3有穷集的计数和包含排斥原理 49
习题 51
第4章 二元关系 55
4.1多重序元与笛卡儿乘积 55
4.2关系的基本概念 57
4.3关系的运算 58
4.4关系的性质 63
4.5关系的表示 66
4.6关系的闭包运算 70
4.7特殊关系 73
4.7.1集合的划分和覆盖 73
4.7.2等价关系 75
4.7.3相容关系 79
4.7.4次序关系 82
4.7.5偏序集合与哈斯图 84
4.8关系型数据库 87
习题 88
第5章 函数 94
5.1函数的基本概念和性质 94
5.2函数的合成和合成函数的性质 97
5.3特殊函数 99
5.4反函数 101
5.5特征函数 103
5.6基数 105
5.7不可解问题 108
5.7.1不可解问题的存在性 108
5.7.2停机问题 108
习题 109
第6章 代数系统 112
6.1代数系统的一般概念 113
6.1.1二元运算 113
6.1.2代数系统 114
6.2代数系统的基本性质 115
6.3同态与同构 122
6.3.1同态 122
6.3.2同构 124
6.3.3同态与同构的性质 127
6.4同余关系 128
6.5商代数 129
6.6积代数 130
6.7代数系统实例 131
习题 132
第7章 群与环 134
7.1半群与群的定义 134
7.2群的性质 136
7.3子群与群的陪集分解 139
7.3.1子群的概念 139
7.3.2群的陪集与拉格朗日定理 139
7.4循环群与置换群 140
7.4.1循环群 140
7.4.2置换群 141
7.5环与域 142
7.5.1环的概念与性质 142
7.5.2域的概念 143
7.6应用：群与网络安全 144
第8章 格与布尔代数 146
8.1格的定义与性质 147
8.2分配格、有补格与布尔代数 148
8.3应用 150
习题 151
第9章 图的基本概念及其矩阵表示 152
9.1图的基本概念 152
9.1.1图的定义及相关概念 152
9.1.2节点的度 154
9.2子图和图的运算 157
9.2.1子图和补图 157
9.2.2图的运算 158
9.3路径、回路和连通性 160
9.3.1路径和回路 160
9.3.2图的连通性 162
9.4图的矩阵表示 165
9.4.1邻接矩阵 165
9.4.2可达性矩阵 169
9.4.3关联矩阵 172
习题 174
第10章 几种图的介绍 179
10.1欧拉图 179
10.2哈密尔顿图 181
10.3二部图及匹配 184
10.3.1二部图的概念及性质 184
10.3.2二部图匹配 185
10.4平面图 187
10.4.1平面图的概念及性质 187
10.4.2多边形图、对偶图及平面图着色 189
10.5网络 192
10.5.1网络的基本概念 192
10.5.2网络流 193
10.5.3网络最大流求解 194
10.5.4开关网络 201
10.6图的实例分析 208
10.6.1中国邮递员问题 208
10.6.2旅行售货员问题 210
10.6.3排课问题 211
10.6.4延时容忍网络问题 213
10.6.5最短路径问题 214
习题 216
第11章 树 221
11.1树与生成树 221
11.1.1树及其性质 221
11.1.2生成树与最小生成树 223
11.2有向树及其应用 224
11.2.1有向树 224
11.2.2m叉树 225
11.2.3有序树 227
11.2.4二叉树的遍历 228
11.2.5搜索树 230
习题 232
参考文献 235