模型论及其在计算机科学中的应用

第一章　模型论的发生与发展

1.1　模型论在科学发展中的地位

1.2　模型论的发展概述

1.3　模型论与计算机科学的关系

1.4　模型论研究的方法与特点

1.5　语法与语义

第二章　关于集合论的准备知识

2.1　完整的集合论公理系统

2.2　有限集与无限集

2.3　集合之间元素个数的比较

2.4　选择公理和可良序化定理

2.5　基数的定义和性质

2.6　序数定义和超限归纳过程

2.7　可数集的性质

2.8　序数，基数的运算

2.9　实数的不可数性

2.10　连续统假设简介

练习题

第三章　模型论的形式语言

3.1　形式逻辑中的命题演算

3.2　一阶逻辑简介

3.3　命题演算的模型论的补充性质

3.4　模型论的形式语言

3.5　模型论的式子和它们的构成

3.6　模型论的式子推演

练习题

第四章　模型的基本性质

4.1　形式语言的解释与模型

4.2　模型的同构，同态，子模型，扩张，膨胀，归约

4.3　式子的代入与验证

4.4　理论，公理，定理和模型的理论

4.5　语言和理论的模型数

4.6　模型的同构嵌入

4.7　模型的初等等价

练习题

第五章　紧致性定理与LST定理

5.1　从理论构造模型

5.2　紧致性定理

5.3　紧致性定理的应用

5.4　模型的图像

5.5　模型论的内语言与外语言

练习题

第六章　初等子模型与模型完全的理论

6.1　初等子模型

6.2　初等图像和它的应用

6.3　强LST定理

6.4　完全的理论

6.5　模型完全的理论

练习题

第七章　初等链的构造与应用

7.1　模型的链的构造

7.2　模型的链的并

7.3　初等链定理

7.4　式子集的实现与省略

练习题

第八章　保持性定理

8.1　研究保持性定理的意义和方法

8.2　子模型的保持性定理

8.3　模型链的并保持性定理

8.4　同态象的保持性定理

8.5　保持性的部分表

练习题

第九章　可数语言的几种特殊模型

9.1　素模型与原子模型

9.2　齐次模型

9.3　可数饱和模型

练习题

第十章　一些具体的模型和逻辑性质

10.1　模型与语言的关系

10.2　偏序、全序集模型

10.3　布尔代数模型

10.4　群，环，域系列的模型

10.5　其他系列的模型

练习题

第十一章　量词消去法和可判定的理论

11.1　量词消去法的重要性

11.2　量词消去法的一般步骤

11.3　无端稠密有序集的量词消去法

11.4　整数加运算的量词消去法

11.5　代数模型的模型数

11.6　布尔代数模型的模型数

11.7　W-范畴的可数完全的理论

11.8　范畴性研究介绍

练习题

第十二章　不可判定的理论

12.1　自然数理论系统□□的不可判定性

12.2　有理数加法、乘法系统的不可判定性

12.3　自由群T-理论的不可判定性

练习题

第十三章　无原子布尔代数理论的计算复杂度

13.1　一个系统的定理判定的计算复杂度

13.2　无原子布尔代数的公理系统

13.3　量词消去法的作用与过程

13.4　无原子布尔代数的性质

13.5　无原子布尔代数的量词消去法

13.6　无原子布尔代数的计算复杂度

第十四章　可换群定理判定的计算复杂度

14.1　可换群的理论和结构

14.2　模型的Ehrenfeucht博弈

14.3　群Dp博弈的准备工作

14.4　群Dp的Ferrente和：Rackoff博弈

14.5　群Dp的计算复杂度上界

14.6　可换群理论的计算复杂度

第十五章　对数论模型的研究

15.1　广义中国剩余定理

15.2　□的w-和模型

15.3　孪生准素数问题

15.4　对Goldbach猜想和孪生素数问题的研究

第十六章　有限模型论的保持性定理

16.1　模型的初等性质

16.2　保持性定理

第十七章　集合论的可数模型

17.1　实数的相对性

17.2　集合论的可数模型

17.3　ZFG模型中元素的不可区分群组

17.4　无限小数的不确定性

17.5　康托尔实数的局限性

17.6　计算机科学与无限概念的关系

第十八章　非良基集合论模型悖论

18.1　集合论的新悖论

18.2　良基性定理与非良基的集合论模型

18.3　非良基的集合论模型的精确化

18.4　非良基集合论模型中的良序集与类

18.5　结论

第十九章　可数多个单元关系的研究

19.1　可数多个独立单元关系系统

19.2　可数多个单元关系的完全理论

第二十章　多项式复杂度的计算问题

20.1　一些引理

20.2　二次模方程的解

参考文献

索引

《模型论及其在计算机科学中的应用》是为了给数学系和计算机科学系的本科生和研究生开设模型论课而写的，它的主要内容是模型论的基本原理和它在计算机科学中的计算复杂度理论和机器证明等方面的应用。本书共二十章节，内容包括模型论的发生与发展、关于集合论的准备知识、模型论的形式语言、模型的基本性质、紧致性定理与LST定理等。本书给供相关人员参考阅读。