第一部分 数理逻辑 3
第1章 命题逻辑 3
1.1 命题及联结词 3
1.1.1 命题的概念 3
1.1.2 命题联结词 5
1.1.3 命题的符号化 9
1.2 命题公式 9
1.2.1 命题公式的定义 9
1.2.2 命题公式的赋值与真值表 11
1.2.3 命题公式的类型 12
1.3 命题公式等值演算 13
1.3.1 等值式与等值演算 13
1.3.2 范式 17
1.3.3 主范式 19
1.4 命题逻辑的推理理论 26
1.4.1 推理的形式结构及推理规则 26
1.4.2 证明方法和策略 30
习题1 31
拓展练习1 34
第2章 谓词逻辑 36
2.1 谓词逻辑命题符号化 36
2.1.1 个体词、谓词 36
2.1.2 量词 37
2.2 谓词公式及解释 38
2.2.1 基本定义 38
2.2.2 谓词公式的解释 39
2.2.3 谓词公式的类型 41
2.3 谓词逻辑等值演算 42
2.3.1 等值式与等值演算 42
2.3.2 前束范式 44
2.4 谓词逻辑的推理理论 45
2.4.1 推理的形式结构及推理规则 45
2.4.2 证明方法和策略 46
习题2 48
拓展练习2 50
第二部分 集合论 53
第3章 集合论基础 53
3.1 集合的基本概念 53
3.1.1 集合的概念及特征 53
3.1.2 集合间的关系 55
3.1.3 幂集合 56
3.2 集合的运算与恒等式 57
3.2.1 集合的运算 57
3.2.2 集合恒等式 58
3.3 有限集合的计数问题 61
3.3.1 两个有限集合的计数问题 61
3.3.2 三个有限集合的计数问题 62
3.3.3 n个有限集合的计数问题 63
3.4 计算机表示集合的方法 64
习题3 66
拓展练习3 68
第4章 关系 69
4.1 关系的概念 69
4.1.1 有序对 69
4.1.2 笛卡儿积 70
4.1.3 关系的定义 71
4.2 关系的表示、性质及运算 72
4.2.1 关系的表示方法 72
4.2.2 关系的性质 74
4.2.3 关系的运算 75
4.3 等价关系与划分 82
4.3.1 等价关系 82
4.3.2 等价类及其性质 82
4.3.3 商集和划分 83
4.4 偏序关系 84
4.4.1 偏序关系的定义 84
4.4.2 哈斯图 85
4.4.3 偏序集中的特殊元素 87
4.4.4 拓扑排序 88
习题4 88
拓展练习4 90
第5章 函数与集合的势 91
5.1 函数 91
5.1.1 函数的定义 91
5.1.2 函数的类型 92
5.1.3 常用函数 94
5.2 函数的运算 95
5.2.1 函数的复合 95
5.2.2 函数的逆运算 96
5.3 集合的势 97
5.3.1 集合的等势 98
5.3.2 可数集合与不可数集合 99
5.3.3 集合的优势 101
习题5 102
拓展练习5 102
第三部分 代数系统 107
第6章 代数系统的基本概念 107
6.1 运算 107
6.1.1 运算的定义与表示方法 107
6.1.2 二元运算的性质 110
6.1.3 二元运算的特殊元素和消去律 111
6.2 代数系统简介 114
6.2.1 代数系统的定义 114
6.2.2 代数系统的分类 114
6.2.3 子代数和积代数 115
6.2.4 代数系统的同态与同构 116
习题6 117
拓展练习6 119
第7章 几个典型的代数系统 120
7.1 半群和群 120
7.1.1 半群与独异点 120
7.1.2 群 121
7.2 环与域 126
7.2.1 环 126
7.2.2 域 127
7.3 格与布尔代数 128
7.3.1 格 128
7.3.2 布尔代数 132
习题7 132
拓展练习7 134
第四部分 图论 139
第8章 图论基础 139
8.1 图的基本概念 139
8.1.1 图的定义 139
8.1.2 顶点的度与握手定理 141
8.1.3 完全图与正则图 145
8.1.4 图的同构 146
8.1.5 子图、补图与图的运算 147
8.2 图的连通性 148
8.2.1 通路与回路 149
8.2.2 无向图的连通性 151
8.2.3 有向图的连通性 152
8.3 图的矩阵表示 153
8.3.1 关联矩阵 153
8.3.2 邻接矩阵 154
8.3.3 可达矩阵 157
8.4 图的应用 157
8.4.1 渡河问题 158
8.4.2 均分问题 158
8.4.3 赋权图的最短通路问题 159
8.4.4 通信网络问题 160
习题8 160
拓展练习8 161
第9章 树 163
9.1 无向树及其应用 163
9.1.1 无向树的定义和性质 163
9.1.2 生成树 165
9.1.3 最小生成树 167
9.2 根树及其应用 168
9.2.1 根树的定义及分类 168
9.2.2 根树的遍历 170
9.2.3 最优二元树与哈夫曼编码 172
9.2.4 根树的应用 174
习题9 177
拓展练习9 178
第10章 几种特殊的图 180
10.1 欧拉图 180
10.1.1 欧拉图的定义 180
10.1.2 欧拉图的判定及欧拉回路的求解算法 181
10.1.3 欧拉图的应用 182
10.2 哈密顿图 186
10.2.1 哈密顿图的定义 186
10.2.2 哈密顿图的判定 187
10.2.3 哈密顿图的应用 188
10.3 二部图 189
10.3.1 二部图的定义 189
10.3.2 二部图的判定 190
10.3.3 二部图的匹配及其应用 191
10.4 平面图 193
10.4.1 平面图的定义及性质 193
10.4.2 平面图的判定 195
10.4.3 平面图的应用——着色问题 197
习题10 199
拓展练习10 203
参考文献 204