A篇 集合论 1
第一章 集合论的基本概念 3
1.1 集合的概念 3
1.2 集合的规范说明方法 4
1.3 集合论中的等同与基数 8
1.4 子集合 10
1.5 幂集 11
1.6 集合的并与集合的交 11
1.7 集合的差与集合的补 15
1.8 集合论中的几个等式 17
练习 23
第二章 关系和函数 27
2.1 有序对与卡氏积 27
2.2 关系 28
2.3 函数 30
2.4 函数的组合 33
练习 36
第三章 关系的性质 39
3.1 自反性、对称性、传递性和连通性 39
3.2 关系的图示 43
3.3 关系的逆与关系的补的性质 44
3.4 等价关系与划分 45
3.5 序 47
练习 51
第四章 无限性 55
4.1 等价集合与基数 55
4.2 集合的可枚举性 58
4.3 不可枚举集合 62
4.4 无限与无界 70
练习 71
附录A：用集合论再构建数的系统 75
A.1 自然数 75
A.2 扩充到全部的整数集 78
A.3 扩充到全部的有理数集 80
A.4 扩充到全部的实数集 81
复习练习 83
3篇 逻辑和形式系统 85
第五章 逻辑和形式系统的基本概念 87
5.1 形式系统与模型 87
5.2 自然语言与形式语言 91
5.3 句法与语义 92
5.4 关于命题逻辑与谓词逻辑 93
第六章 命题逻辑 97
6.1 命题逻辑的句法 97
6.2 命题逻辑的语义：真值与真值表 99
6.2.1 否定 99
6.2.2 合取 100
6.2.3 析取 101
6.2.4 条件 102
6.2.5 双条件 103
6.3 重言命题、矛盾命题与相依命题 104
6.4 逻辑等价、逻辑结论与逻辑定律 108
6.5 命题逻辑中的自然演绎 112
6.5.1 条件证明 118
6.5.2 间接证明 120
6.6 命题逻辑中的贝思（Beth）表 121
练习 128
第七章 谓词逻辑 135
7.1 谓词逻辑的句法 135
7.2 谓词逻辑的语义 140
7.3 量词定律与前束范式 146
7.4 谓词逻辑中的自然演绎 152
7.5 谓词逻辑中的贝思（Beth）表 163
7.6 形式证明与非形式证明 168
7.7 数学证明中的非形式风格 170
练习 173
第八章 形式系统、公理化与模型理论 179
8.1 形式系统的句法方面 179
8.1.1 递归定义 179
8.2 公理系统与推导 183
8.2.1 扩展公理系统 186
8.3 半图厄（semi-Thue）系统 190
8.4 皮亚诺（Peano）公理与归纳证明 192
8.5 形式系统的语义方面：模型理论 198
8.5.1 理论与模型 198
8.5.2 一致性、完备性与独立性 200
8.5.3 同构 202
8.5.4 一个基础的形式系统 204
8.5.5 关于顺序关系的公理 206
8.5.6 关于符号串毗连的公理 211
8.5.7 皮亚诺（Peano）公理的模型 214
8.5.8 集合论的公理化 215
8.6 公理化逻辑 217
8.6.1 命题逻辑的公理化 217
8.6.2 一致性的证明与独立性的证明 220
8.6.3 谓词逻辑的公理化 223
8.6.4 关于完备性的证明 225
8.6.5 可判定性 227
8.6.6 哥德尔（G？del）不完备性定理 228
8.6.7 高阶逻辑 229
练习 232
附录B.Ⅰ：各种不同的逻辑符号与联结词 237
附录B.Ⅱ：克林（Kleene）的三值逻辑 239
复习练习 243
C篇 代数 245
第九章 代数的基本概念 247
9.1 代数的定义 247
9.2 运算的性质 248
9.3 几个特殊的元 249
9.4 映射与同型 251
练习 253
第十章 运算的结构 255
10.1 群 255
10.2 子群、半群与幺半群 261
10.3 整域 264
10.4 同型 269
练习 271
第十一章 格 275
11.1 部分有序集、对偶性与图 275
11.2 格、半格与子格 278
11.3 格论中的同型 283
11.4 筛选格与理想格 285
11.5 有补格、分配格与模块格 288
练习 293
第十二章 布尔（Boolean）代数与赫廷（Heyting）代数 295
12.1 布尔代数 295
12.2 布尔代数的模式 298
12.3 布尔代数的集合表示 299
12.4 赫廷代数 301
12.5 克里普克（Kripke）语义学 304
练习 307
复习练习 309
D篇 作为形式语言的英语 313
第十三章 基本概念 315
13.1 组成性原则 315
13.1.1 命题逻辑的组成性说明 317
13.1.2 谓词逻辑的组成性说明 321
13.1.3 自然语言与组成性原则 331
13.2 λ（Lambda）抽象 336
13.2.1 类型理论 336
13.2.2 λ抽象的句法与语义 339
13.2.3 一个样本的片段 341
13.2.4 λ演算 346
13.2.5 语言学应用 349
练习 365
第十四章 广义量词 371
14.1 限定词与量词 371
14.2 量词的条件 373
14.3 限定词与量词的性质 378
14.4 作为关系的限定词 388
14.5 上下文与量词化 392
练习 397
第十五章 内涵性 401
15.1 弗雷格（Frege）的两个问题 401
15.2 不透明性的形式 407
15.3 索引与可达性关系 412
15.4 时态与时间 421
15.5 索引性 425
练习 427
E篇 形式语言、形式语法与自动机 429
第十六章 基本概念 431
16.1 语言、语法和自动机 431
16.2 语法 435
16.3 树形图 437
16.3.1 支配关系 438
16.3.2 前于关系 439
16.3.3 标记 441
16.4 语法与树形图 444
16.5 乔姆斯基（Chomsky）层级 448
16.6 语言与自动机 451
第十七章 有限自动机、正则语言与3型语法 453
17.1 有限自动机 453
17.1.1 有限自动机的状态图 455
17.1.2 确定性有限自动机的形式定义 455
17.1.3 非确定性有限自动机 458
17.1.4 非确定性有限自动机的形式定义 460
17.1.5 确定性有限自动机与非确定性有限自动机的等价问题 460
17.2 正则语言 462
17.2.1 有限自动机语言（fal）的抽吸定理（Pumping Theorem） 468
17.3 3型语言与有限自动机语言（fal） 471
17.3.3.1 正则语言的性质 475
17.3.3.2 自然语言右线性语法的不足之处 477
练习 480
第十八章 下推自动机、上下文无关语法与上下文无关语言 485
18.1 下推自动机 485
18.2 上下文无关语法与上下文无关语言 490
18.3 上下文无关语言（cfl）的抽吸定理 492
18.4 上下文无关语言的闭包特性 495
18.5 上下文无关语言的可判定性问题 498
18.6 自然语言是上下文无关的吗？ 501
练习 503
第十九章 图灵机、递归可枚举语言与0型语法 505
19.1 图灵机（Turing machine） 505
19.1.1 图灵机的形式定义 508
19.2 图灵机的等价性阐释 512
19.3 非限定语法与图灵机 513
19.4 丘奇（Church）假设 515
19.5 递归集合与递归可枚举集合 517
19.6 通用图灵机 518
19.7 图灵机的停机问题 520
练习 523
第二十章 线性有界自动机、上下文有关语言与1型语法 527
20.1 线性有界自动机 527
20.1.1 线性有界自动机（Lba）与上下文有关语法 528
20.2 上下文有关语言与递归集合 529
20.3 上下文有关语言的闭包特性与判定特性 531
练习 532
第二十一章 介于上下文无关与上下文有关之间的语言 533
21.1 索引语法 534
21.2 树邻接语法 540
21.3 中心词语法 546
21.4 范畴语法 547
第二十二章 转换语法 553
附录E-Ⅰ：乔姆斯基（Chomsky）层级 559
附录E-Ⅱ：语义自动机 563
练习 570
复习练习 571
练习答案选 573
各篇参考文献 635
索引 647