计算理论与符号逻辑

内容简介

　　《计算理论与符号逻辑》对计算理论和数理逻辑中一组基本的问题和重要概念进行详细介绍．以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不性定理

参考文献

索引