第一部分 集合论 1
第一章 集合论的基本概念 3
1.1 集合的概念 3
1.2 集合的性质 5
1.3 集合论的恒等和势 10
1.4 子集 12
1.5 幂集 15
1.6 并和交 15
1.7 差和补 18
1.8 集合论的等式 21
练习 27
第二章 关系与函数 32
2.1 序偶与笛卡尔乘积 32
2.2 关系 34
2.3 函数 35
2.4 函数的复合运算 39
练习 42
第三章 关系的性质 44
3.1 自反性、对称性、传递性和连通性 44
3.2 关系图 50
3.3 逆和补的性质 51
3.4 等价关系与划分 52
3.5 序关系 55
练习 60
第四章 无限 63
4.1 等价集与势 63
4.2 集合的可列性 67
4.3 不可列集合 71
4.4 无限与无界 80
练习 82
附录A 数系统的集合论重构 86
A.1 自然数 86
A.2 扩展至全部整数的集合 89
A.3 扩展至全部有理数的集合 93
A.4 扩展至全部实数的集合 94
复习题 96
第二部分 逻辑和形式系统 99
第五章 逻辑和形式系统的基本概念 101
5.1 形式系统和模型 101
5.2 自然语言和形式语言 106
5.3 句法学和语义学 107
5.4 关于命题逻辑和谓词逻辑 109
第六章 命题逻辑 115
6.1 句法 115
6.2 语义学：真值和真值表 117
6.2.1 否定 118
6.2.2 合取 119
6.2.3 析取 121
6.2.4 条件 122
6.2.5 充要条件 124
6.3 永真式、永假式和可能式 126
6.4 逻辑等价、逻辑结论和逻辑定律 130
6.5 自然演绎 135
6.5.1 条件证明 142
6.5.2 间接证明 144
6.6 贝思表 146
练习 155
第七章 谓词逻辑 163
7.1 句法 163
7.2 语义 170
7.3 量词定律与前束范式 178
7.4 自然演绎 187
7.5 贝思表 202
7.6 形式化证明和非形式化证明 209
7.7 数学证明中的非形式化风格 211
练习 216
第八章 形式系统、公理化与模型理论 223
8.1 形式系统的句法方面 223
8.1.1 递归定义 223
8.2 公理系统和推导 228
8.2.1 扩展的公理系统 232
8.3 半图厄系统 237
8.4 皮亚诺公理与归纳证明 240
8.5 形式系统的语义方面：模型论 248
8.5.1 理论与模型 248
8.5.2 一致性、完备性和独立性 250
8.5.3 同构 253
8.5.4 一个初等的形式系统 255
8.5.5 关于定序关系的公理 258
8.5.6 关于符串联结的公理 265
8.5.7 皮亚诺公理的模型 268
8.5.8 集合论的公理化 270
8.6 公理化逻辑 273
8.6.1 命题逻辑的公理化 273
8.6.2 一致性和独立性证明 277
8.6.3 谓词逻辑的公理化 280
8.6.4 关于完备性证明 283
8.6.5 可判定性 285
8.6.6 哥德尔的不完备性定理 287
8.6.7 高阶逻辑 289
练习 293
附录B-Ⅰ 各种不同的逻辑符号与联结词 298
附录B-Ⅱ 克林的三值逻辑 300
复习题 304
第三部分 代数 307
第九章 代数的基本概念 309
9.1 代数的定义 309
9.2 运算的性质 311
9.3 特殊元素 312
9.4 映射和态射 314
练习 317
第十章 运算结构 318
10.1 群论 318
10.2 子群、半群和幺半群 325
10.3 整环 328
10.4 态射 334
练习 337
第十一章 格理论 342
11.1 偏序集、对偶性和图表 342
11.2 格、半格和子格 347
11.3 格中的态射 352
11.4 滤子和理想 355
11.5 有补格、分配格和模格 358
练习 364
第十二章 布尔代数和海廷代数 366
12.1 布尔代数 366
12.2 BA的模型 370
12.3 用集合表征BA 372
12.4 海廷代数 375
12.5 克里普克语义学 378
复习题 384
第四部分 作为形式语言的英语 389
第十三章 基本概念 391
13.1 组合性 392
13.1.1 命题逻辑的组合性解释 394
13.1.2 谓词逻辑的组合性解释 398
13.1.3 自然语言和组合性 412
13.2 兰姆达抽象 419
13.2.1 类型论 419
13.2.2 λ-抽象的句法和语义 422
13.2.3 一个样本片段 424
13.2.4 兰姆达演算 431
13.2.5 语言学应用 435
练习 457
第十四章 广义量词 462
14.1 限定词与量词 462
14.2 量词的条件 465
14.3 限定词与量词的特性 472
14.4 作为关系的限定词 491
14.5 语境与量化 496
练习 503
第十五章 内涵性 506
15.1 弗雷格的两个问题 506
15.2 不透明性的形式 515
15.3 索引与可及性关系 522
15.4 时态与时间 537
15.5 索引性 543
练习 545
第五部分 语言、语法与自动机 547
第十六章 基本概念 549
16.1 语言、语法与自动机 549
16.2 语法 554
16.3 树形图 557
16.3.1 支配 558
16.3.2 居先 560
16.3.3 标记 562
16.4 语法与树形图 566
16.5 乔姆斯基层级 571
16.6 语言与自动机 574
第十七章 有限自动机、正则语言与3型语法 577
17.1 有限自动机 577
17.1.1 有限自动机的状态图 580
17.1.2 确定的有限自动机的形式定义 580
17.1.3 不确定的有限自动机 584
17.1.4 不确定的有限自动机的形式定义 585
17.1.5 确定的有限自动机与不确定的有限自动机的等价 586
17.2 正则语言 588
17.2.1 有限自动机语言的泵定理 596
17.3 3型语法与有限自动机语言 599
17.3.1 正则语言的性质 603
17.3.2 用右线性语法描述自然语言的不充分性 607
练习 610
第十八章 后进先出自动机、上下文无关语法与上下文无关语言 616
18.1 后进先出自动机 616
18.2 上下文无关语法与上下文无关语言 622
18.3 上下文无关语言的泵定理 625
18.4 上下文无关语言的闭合性 629
18.5 上下文无关语言的可判定性问题 632
18.6 自然语言是上下文无关的吗？ 636
练习 641
第十九章 图灵机、递归可枚举语言与0型语法 643
19.1 图灵机 643
19.1.1 图灵机的形式定义 647
19.2 图灵机的等价阐述 652
19.3 无限制语法与图灵机 653
19.4 丘奇假说 657
19.5 递归集合与递归可枚举集合 658
19.6 通用图灵机 660
19.7 图灵机的停机问题 663
练习 668
第二十章 线性有界自动机、上下文有关语言及1型语法 671
20.1 线性有界自动机 671
20.1.1 线性有界自动机和上下文有关语法 672
20.2 上下文有关语法和递归集合 674
20.3 闭包和可判定性 676
练习 677
第二十一章 介于上下文无关语言和上下文有关语言之间的语言 678
21.1 索引语法 679
21.2 树邻接语法 686
21.3 中心语语法 692
21.4 范畴语法 694
第二十二章 转换语法 700
附录E-Ⅰ 乔姆斯基层级 705
附录E-Ⅱ 语义自动机 707
练习 714
复习题 715
部分习题答案 717
第一章 717
第二章 720
第三章 722
第四章 724
第一部分复习题 725
第六章 729
第七章 736
第八章 746
第二部分复习题 750
第九章 755
第十章 756
第十一章 762
第十二章 764
第三部分复习题 766
第十三章 773
第十四章 775
第十五章 780
第十七章 781
第十八章 788
第十九章 791
第二十章 793
附录E-Ⅱ 794
第五部分复习题 795
参考书目 797
英文索引 818
译名表 846