数理逻辑

绪论

第1章 集合论基础

1.1 可数集

1.1.1 映射

1.1.2 可数集的概念

1.1.3 可数集概念的延伸

1.2 康拓尔对角线方法

1.2.1 波尔查诺的无穷观

1.2.2 康拓尔的证明

1.2.3 自然数集的幂集（N）

1.3 基数

1.3.1 基数的概念

1.3.2 基数大小关系性质

1.4 自然数与有穷集

1.4.1 集合论观点下的自然数

1.4.2 有穷集与有穷基数

1.5 无穷集与N。

1.5.1 最小的无穷量

1.5.2 无穷集的肚量

1.6 更高的超穷基数

1.6.1 幂集的基数

1.6.2 关于幂集的康拓尔定理

1.6.3 其他超穷集的基数

1.6.4 连续统与连续统假设

本章习题

第2章 可计算性理论基础

2.1 计算概念的形成与发展

2.1.1 计算概念的初识——抽象思维的进步

2.1.2 计算概念的定义——计算本质的揭示

2.1.3 计算概念的发展——计算方式的进化

7.2 算法与能行过程

2.2.1 算法概念的由来

2.2.2 算法概念的描述

2.2.3 能行过程与可计算性

2.2.4 停机问题

2.3 可计算性概念的数学描述

2.3.1 递归函数

2.3.2 图灵机与图灵可计算函数

2.4 理想计算机

2.4.1 URM模型与指令系统

2.4.2 URM可计算函数

本章习题

第3章 形式命题演算

3.1 命题与命题演算形式系统

3.1.1 命题的概念

3.1.2 命题的表示与翻译

3.1.3 命题演算形式系统

3.2 命题演算形式推理

3.2.1 命题演算形式证明与定理

3.2.2 相对证明与演绎定理

3.3 命题公式的等价与替换

3.3.1 等价命题公式

3.3.2 等价命题替换定理

3.4 对偶命题公式

3.4.1 命题公式的对偶式

3.4.2 对偶原则

3.5 形式系统再认识

3.5.1 形式系统理论

3.5.2 形式系统L的简化

3.6 形式系统的进一步讨论

3.6.1 赋值与重言式

3.6.2 L的可靠性定理

3.6.3 L的充分性定理

本章习题

第4章 谓词演算

4.1 谓词表达式

4.1.1 谓词与量词

4.1.2 谓词表达式与翻译

4.2 一阶语言

4.2.1 一阶语言g与谓词公式

……

第5章 谓词演算形式系统

第6章 一阶算术形式系统与哥德尔不完备性定理

附录A 习题解答

参考文献

本书共分7章。第0章绪论，介绍元数学的形成与发展，以及元数学与数理逻辑之间的关系，同时简要说明课程学习的目的和意义；第1章介绍集合论的基础知识，包括有穷集与无穷集的概念、可数集与不可数集的性质、集合的基数、无穷基数的比较等方面的内容；第2章介绍可计算性理论的基本知识，包括计算概念的形成与发展、算法的基本描述、计算概念的数学定义、可计算性函数的基本性质等；第3章～第5章是关于经典数理逻辑的内容，包括命题演算和谓词演算两个部分，重点介绍逻辑演算以及相关形式系统的基本性质，内容涉及形式证明、形式推理、形式系统的语法、语义等概念以及逻辑系统的可靠性与充分性等方面的知识；第6章以一阶算术系统为例，介绍基于逻辑系统扩展的数学应用系统的描述方法，最终给出“哥德尔不完备性定理”的证明。在本书的附录中给出了全书的习题解答。本书面向计算机科学与技术、软件工程以及相关专业的高等院校学生，尤其是高校相关专业的高年级本科生及研究生，可以作为教材，也可作为希望了解数理逻辑基础知识的高校学生和科研技术工作者的阅读材料或参考资料。

《数理逻辑/中国高等学校计算机科学与技术专业（应用型）规划教材》特色：
《数理逻辑/中国高等学校计算机科学与技术专业（应用型）规划教材》在内容组织上含纳集合论基础知识、可计算性理论基本知识和经典数理逻辑3个部分，其中集合论基础部分着重介绍可数集与不可数集的概念，并运用集合的基数以及基数的比较等有关知识，阐述“无穷可比”的思想，目的在于扩展学生的思维空间，深化学生对计算机有穷空间的认识；可计算性理论基础部分以递归函数、图灵计算和理想计算机为对象，从多个角度给出“计算”概念的精确描述，目的在于帮助学生深入了解“计算”的本质，并对计算机的计算“行为”与“能力”有一个充分认识；经典逻辑部分包括命题逻辑和谓词逻辑，着力于形式系统，重点介绍形式证明、形式推理，形式系统的语法、语义等概念以及逻辑系统的可靠性与充分性等疗面的知识，并以一阶算术系统为例介绍逻辑系统的扩展方法，旨在帮助学生了解和掌握形式化方法，以此为工具更好地开展计算机基础理论研究和计算机程序分析、设计与开发工作。