前言 1
第一章 基本概念 4
1 引言 4
2 命题 8
3 命题连接词 12
4 集合 14
5 量词 21
6 字母表与字 22
7 次序 24
8 计算程序 26
9 算法 28
10 逻辑运算与布尔矩阵 30
习题一 33
1 关系 36
第二章 关系与函数 36
2 关系的图形表示和矩阵表示 38
3 关系的运算 41
4 关系的性质 45
5 关系的闭包运算 50
6 等价关系 54
7 序关系 59
8 函数 67
9 两个集合之间的一一对应 73
习题二 74
第三章 信息图 78
1 基本概念与术语 78
2 路与连通性 80
3 无向图、加权图、多重图及同构 82
4 图的一些基本性质 86
5 图的矩阵表示 88
6 欧拉通路与汉密尔顿通路 98
7 根树 108
8 根树的应用 113
9 无向树 118
10 生成树与割集 119
习题三 122
第四章 代数系统与布尔代数 126
1 基本概念 126
2 群 134
3 环与域 138
4 格 140
5 布尔代数 143
6 二值布尔代数 148
7 逻辑结构 151
习题四 153
第五章 命题演算 156
1 原始符号及形成规则 156
2 形式公理与形式推演规则 160
3 形式证明与形式定理 161
4 形式推演 163
5 演绎定理 170
6 归谬律及反证法 174
7 斜式证明法 175
8 一些重要的形式定理 178
9 等值词 188
10 范式 189
习题五 194
1 原始符号与形成规则 196
第六章 谓词演算 196
2 形式公理与形式推演规则 201
3 形式证明与形式定理 203
4 形式推演 205
5 演绎定理 207
6 辅助导出规则 213
7 一些重要的形式定理 214
8 前束范式 224
习题六 227
第七章 一阶逻辑的语义与模型 228
1 真值概念 228
2 一致性与完全性 231
3 判定问题 234
4 真值表方法 235
5 检查范式法 237
6 分支法 239
7 归结法 246
8 论域与模型 249
9 归结法(续) 252
10 一阶逻辑的基本定理 254
习题七 256
第八章 形式语言与形式文法 257
1 形式命题语言 257
2 形式文法 258
3 文法的类型 263
4 1型文法的递归性 266
5 2型文法的派生树 269
6 3型文法的状态图 271
习题八 274
1 基本概念 275
第九章 有穷自动机 275
2 状态图 278
3 状态输出机 282
4 有穷自动机的简化 287
5 有穷识别器与正规语言 295
6 有穷识别器的模型 302
习题九 303
第十章 图灵机器 305
1 引言 305
2 指令形式的图灵机 307
3 图灵机的四元有序组形式 315
4 两种图灵机的等价性 321
5 可计算函数 324
6 图灵识别器 343
习题十 345
1 初等形式系统举例 346
第十一章 初等形式系统与递归关系 346
2 初等形式系统的定义 348
3 可表达性 350
4 形式命题集合的形式可表达性 354
5 命题演算中定理集合的形式可表达性 354
6 正整数的递归可枚举集合 356
7 哥德尔数 357
8 形式可表达的集合在存在可定义下的封闭性 358
9 存在可定义的几个实例 360
10 某些基本关系的递归可枚举性 362
11 递归函数 363
12 车赤论题与图灵论题 365
习题十一 367
参考文献 368