第1篇 数理逻辑 1
第1章 命题逻辑 1
1-1命题与联结词 1
1-1-1命题 1
1-1-2联结词 2
1-2命题公式及其赋值 5
1-2-1命题公式 5
1-2-2命题公式的真值表 6
1-2-3语句的形式化 8
1-3重言式 9
1-3-1重言式 10
1-3-2等价式 10
1-3-3蕴含式 13
1-4对偶与范式 16
1-4-1对偶 16
1-4-2范式 17
1-4-3联结词完备集 23
1-5推理理论 26
1-6小结 29
习题 30
第2章 谓词逻辑 32
2-1谓词逻辑基本概念 32
2-1-1个体和谓词 32
2-1-2量词 34
2-1-3谓词公式及语句的符号化 35
2-2谓词逻辑永真式 38
2-2-1公式的解释 38
2-2-2谓词演算永真式 39
2-3谓词公式的前束范式 42
2-4谓词演算推理理论 43
2-5消解原理 48
2-5-1化为子句集 48
2-5-2消解推理规则 49
2-5-3含有变量的消解式 51
2-5-4消解反演求解过程 52
2-3小结 56
习题 57
第2篇 集合论 59
第3章 集合 59
3-1集合的概念与表示 59
3-1-1集合及其元素 59
3-1-2集合的表示 60
3-1-3集合之间的关系 61
3-2集合的基本运算 63
3-2-1集合的交、并、补及对称差 63
3-2-2证明集合相等的方法 67
3-3集合的笛卡儿积运算 68
3-4有限集合中元素的计数 71
3-4-1鸽笼原理 71
3-4-2容斥原理 71
3-5集合的覆盖与划分 73
3-6小结 74
习题 75
第4章 关系 77
4-1n元组与关系 77
4-1-1关系的基本概念 77
4-1-2二元关系的表示 78
4-2二元关系的性质与类型 80
4-2-1自反性与反自反性 80
4-2-2对称性与反对称性 81
4-2-3传递性 81
4-2-4关系性质的等价描述 82
4-2-5关系性质的证明 83
4-3关系的运算 84
4-3-1关系的基本运算 84
4-3-2关系的复合运算 84
4-3-3关系的逆运算 86
4-3-4利用关系矩阵求解复合关系 87
4-4关系的闭包运算 89
4-4-1特性闭包 89
4-4-2特性闭包的求解 90
4-5等价关系 94
4-5-1等价关系与等价类 95
4-5-2等价关系与划分 96
4-6相容关系 97
4-6-1相容关系与最大相容类 98
4-6-2相容关系与完全覆盖 99
4-7偏序关系 100
4-7-1偏序关系与盖住关系 100
4-7-2偏序集上的特殊元素 101
4-7-3全序关系与良序关系 102
4-8小结 103
习题 104
第5章 函数 106
5-1函数的定义 106
5-2函数的性质 108
5-3函数的逆运算与复合运算 109
5-3-1函数的逆运算与逆函数 109
5-3-2函数的复合运算与复合函数 110
5-3-3特殊函数 111
5-4特征函数与一致性函数 112
5-5有限集和无限集 114
5-5-1有限集、可数集与不可数集 115
5-5-2无限集的特性 118
5-6基数 119
5-6-1有限集、可数无限集和连续统的基数 119
5-6-2基数比较 120
5-7小结 122
习题 123
第3篇 代数系统 124
第6章 代数系统 124
6-1代数系统的基本概念 124
6-1-1代数运算 124
6-1-2代数运算的基本性质 125
6-1-3代数系统的定义 126
6-2代数系统的同态与同构 131
6-2-1同态与同构 131
6-2-2同态与同构的基本性质 132
6-3小结 133
习题 134
第7章 群、环、域 136
7-1半群与独异点 136
7-1-1半群与独异点的概念 136
7-1-2半群的基本性质 136
7-1-3子半群与半群的同态 137
7-2群与子群 139
7-2-1群的基本概念 139
7-2-2群的基本性质 140
7-2-3子群 142
7-3陪集与拉格朗日定理 144
7-3-1陪集定义及基本性质 144
7-3-2拉格朗日定理及其应用 146
7-4正规子群与商群 147
7-4-1正规子群的定义及实例 147
7-4-2商群 148
7-5群的同态与同构 149
7-5-1基本概念 149
7-5-2同态映射的性质 150
7-5-3同态基本定理 151
7-6特殊群 152
7-6-1交换群 153
7-6-2循环群 153
7-7环和域 155
7-7-1环 155
7-7-2域 156
7-8小结 158
习题 158
第8章 格与布尔代数 160
8-1格 160
8-1-1格的定义 160
8-1-2格的对偶原理与格的基本性质 163
8-1-3格的同态与同构 163
8-2特殊格 165
8-2-1分配格 165
8-2-2模格 167
8-2-3有界格 167
8-2-4有补格 168
8-3布尔代数与布尔表达式 169
8-3-1布尔代数 169
8-3-2布尔表达式 171
8-4小结 173
习题 174
第4篇 图论 175
第9章 图 175
9-1图的基本概念 175
9-1-1图的定义 175
9-1-2结点的度数 178
9-1-3子图与补图 179
9-1-4图的同构 180
9-1-5图的操作 181
9-2通路、回路与连通性 182
9-2-1通路与回路 182
9-2-2无向图的连通性 184
9-2-3有向图的连通性 186
9-3图的矩阵表示 189
9-3-1邻接矩阵 189
9-3-2可达性矩阵 194
9-3-3完全关联矩阵 197
9-4小结 199
习题 200
第10章 特殊图 202
10-1二部图 202
10-1-1二部图的基本概念 202
10-1-2匹配 203
10-2欧拉图与汉密尔顿图 205
10-2-1欧拉图 205
10-2-2汉密尔顿图 207
10-3平面图 211
10-4对偶图与图的着色 215
10-4-1对偶图 216
10-4-2图的着色 216
10-5树与生成树 220
10-5-1无向树 220
10-5-2生成树 222
10-5-3最小生成树 223
10-6根树及其应用 225
10-6-1有向树与根树 225
10-6-2有序树、最优树与二叉树 227
10-6-3前缀码问题 230
10-7小结 232
习题 233
附录A 初等数论 234
附录B 计数原理 242
参考文献 252