计算理论与符号逻辑
2011-10
科学出版社
张兴元 等编著
无
《计算理论与符号逻辑》对计算理论和数理逻辑中一组最为基本的问题和重要概念进行详细介绍．以boolos等的经典教材computability
and
logic为出发点，从教学效果出发，对内容做了简化和充实．本书注重体现数理逻辑在计算机科学研究中的应用，强调直观感受与理论分析相结合．对定义、定理的引入进行了精心设计，采用了易于理解的证明体例，重要章节之后都有小结．力图引导读者超越技术细节，更多地关注定义、定理背后所隐藏的一般思维模式和思想方法，使理论学习不再枯燥乏味．
《计算理论与符号逻辑》可作为数学、计算机科学相关专业的教材，对软件工程、形式化方法、人工智能、数理逻辑等领域的研究者和工程技术人员提升理性思维的层次和分析能力大有裨益．
第1章 绪论
1.1 符号逻辑与计算机科学
1.2 全书结构
第2章 集合、关系和函数
2.1 集合的基本概念
2.2 集合的笛卡儿积
2.3 关系
2.4 函数
习题
第3章 集合的可数性
3.1 可数性的基本概念
3.2 有结构集合的可数性
3.3 不可数性
习题
第4章 图灵可计算性
4.1 能行可计算
4.2 图灵可计算性
4.3 图灵机的例子
4.4 图灵机的多种表示方法
4.5 对定义4.2的进一步讨论
4.6 不可计算性
4.7 图灵论题与通用图灵机
习题
第5章 算盘可计算性
5.1 算盘机的定义
5.2 算盘机例子程序
5.3 算盘可计算性
5.4 将算盘机编译为图灵机
习题
第6章 递归函数可计算性
第7章 递归函数与递归关系
第8章 不同计算模型之间的等价性
第9章 一阶谓词逻辑的基本概念
第10章 蕴涵关系的不可判定性
第11章 模型
第12章 紧致性定理的证明
第13章 形式化推理系统
第14章 计算行为的逻辑刻画
第15章 godel不完全性定理
参考文献
索引
版权页：插图：人们自然会想到，前面所说的形式化方法是否会受到Godel不完全性定理的负面影响？是否存在这样的程序，尽管其正确性断言是真的，但在我们所使用的形式系统中根本就不存在其证明？从工程实践的角度看，这种担心是不必要的。如果人们在编程时足够负责，一定会认真考虑为什么自己的程序是正确的，并给出充分的理由，这就是在试图以某种方式构造该程序的正确性证明。尽管这个证明可能有错，并且只是短暂地出现在人们的脑海中，但它毕竟是存在的。人们绝对不会交付一个连自己都看不懂的程序。仍然以前面的哥德巴赫猜想的反例程序为例，我们构造这个程序的目的只是想说明该程序的终止性问题与哥德巴赫猜想同构，并不是真的要证明哥德巴赫猜想，因为我们的需求只是为了说明与哥德巴赫猜想的同构，我们也知道为什么自己所写的程序能满足这一需求，所以，该程序与哥德巴赫猜想的同构性证明是存在的，是可以被证明搜索程序找到的。在实际的软件开发中，人们对软件的需求以及软件正确性的理由都是清楚的，只是没有完整地表达出来而已，而形式化方法的本意只是借助于计算机辅助技术将不够明晰的需求和正确性证明用符号逻辑中的断言和推理显式地表达出来并检查其合法性，因此，形式化方法是可行的。也许人们还有这样的疑问，是否会有这样的情况：尽管我们知道软件的正确性理由，但现有的形式系统表达能力不够强，无法表述这些理由，这种担心也是不必要的。因为形式系统总是可以扩展的。以Godel不完全性定理为例，虽然一个形式系统不能表述自己的一致性证明，但该证明可以在该系统之外的另外一个形式系统中表述，当然，这个另外的系统如果是一致的，也同样不能表述自己的一致性证明。如果人们能发现某个命题是不可证明的，往往意味着他们对命题所在领域的认识有了升华，此时，为了继续对该命题的讨论，往往需要对形式系统进行修改扩展，引入新的公理或者新的推理规则构成新的形式系统。Godel不完全性定理只是说：人类在认识上的升华是没有止境的，认识升华导致新的形式系统，新的形式系统又会带来新的问题，有待于认识上新的升华，落实到形式化方法，即使程序的正确性证明不能在现有的形式系统中表述，如果人们真的清楚自己的程序为什么是正确的，他们也应该知道如何对现有的系统进行扩展来表述其正确性证明。基于上述认识，形式化方法是完全可行的。
《计算理论与符号逻辑》是普通高等教育“十一五”国家级规划教材之一。
无
王元元的书，毋庸多说！受益匪浅。