内容介绍
用户评论
全部咨询
本书是为大学三、四年级学生而写，并且曾在南开大学计算机系、数学系作为教材讲授多年。重点介绍了计算机科学与技术的数学基础——可计算理论、数理逻辑与集合论，以及三者之间的关系，主要内容包括：理想计算机与有穷性原则、有穷性逻辑和有穷性数学、一般逻辑与一般数学、集合论等。书末还附有一定的习题。
本书读者对象：高校计算机系、数学系、哲学系师生，计算机工作者。
目录
- 第一章引言
第二章理想计算机与有穷性原则
第一节递归函数
1.1原始递归函数集
1.2原始递归算子
1.3原始递归函数集的分层
1.4Arckermann函数
1.5递归函数
1.6递归函数集的分层
第二节理想计算机
2.1几个计算实例
2.2计算的分析和理想计算机
第三节Turing机器
3.1Turing机定义
3.2Turing机和递归函数
3.3通用函数和递归定理
3.4通用Turing机
3.5通过Turing机定义的非递归函数
3.6Turing机的子类——有穷自动机
3.7计算复杂性与PNP问题
3.8Post系统和Turing机
第四节计算机的数学模型(MMCM)
4.1进一步分析Turing机和Post系统
4.2MMCM定义
4.3MMCM和其他理想计算机
4.4MMCM的一般性
4.5递归集、递归可枚举集和通用MMCM
4.6递归可枚举集与递归不可解性
4.7一致可分(简记作US)和MMCM
第三章有穷性逻辑和有穷性数学
第一节数理逻辑和数学
1.1群的定义和一个定理
1.2语言和推理规则
1.3数理逻辑和数学
第二节一阶逻辑
2.1一阶语言
2.2一阶逻辑语言的语义
2.3一阶逻辑的推理系统
2.4形式推导的正确性和协调性
2.5不含量词公式的合取(析取)范式和含量词公式的前束范式
2.6形式推导的完全性
2.7一阶逻辑的局限 性、G?del不完全定理
2.8二阶逻辑和Q量词逻辑
第三节有穷性逻辑和有穷性数学
3.1有性逻辑和有穷性数学
3.2注记和评论
第四节有穷和无穷命题演算
4.1有穷命题演算
4.2无穷命题演算
第四章一般逻辑和一般数学
第一节一般逻辑和一般数学的定义
1.1一般逻辑L的定义
1.2一般数学M(L)的定义
第二节一般逻辑L和一般数学M(L)的解释
2.1公式和推理规则的解释
2.2M(L)的结构
2.3M(L)的模型
2.4一般数学M(L)的语义完全性
第三节总结和讨论
第五章集合论
第一节朴素集合论
1.1集合之势(基数)
1.2有序集
1.3序型
1.4序型的运算
1.5良序集
1.6序数
1.7可数的超限数
1.8序数和基数
1.9超限归纳法和良序定理
第二节公理集合论(非形式公理系统)
2.1集合论公理
2.2序数
2.3序数和基数
2.4超穷归纳法
第三节ZF系统
3.1公理和说明
3.2选择公理AC
3.3集合全域(或称集合的论域)
3.4ZF的可构成模型L，ZF与AC、GCH的协调性
3.5ZF的其他模型，ZF与V≠L，┐AC，┐CH的协调性
练习题
参考文献
京公网安备 11010102004214号