可计算性与数理逻辑

图书标准信息

• 作者 布勒斯
• 出版社 电子工业出版社
• 出版时间 2005-07
• 版次 1
• ISBN 9787121007798
• 定价 32.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 288页
• 字数 486千字

【内容简介】

本书是一本经典的逻辑教书，第四版已经过全面修订，提高了可读性。全书主要论述了可计算性理论、基础元逻辑及一些高级专题。此书同样适用于没有数学背景知识的学生，不仅包括了中等深度的逻辑教程所讨论的基本专题，如歌德尔不完全性定理等，而且涉及了从图灵的可计算性理论到Ramsey定理的大量选题，因而已成为一个本经典的教科书。该书在每章末尾还增加了习题，并重新组织和改写了某些章，以使各章更加相互独立，增加了教师授课的灵活性，进而扩大了本书的使用范围。

   本书适合数学、计算机科学、哲学等专业的学生使用。对于在人工智能、哲学、计算理论、离散结构、数理逻辑等领域进行研究的读者，此书也是大有裨益的。

【作者简介】

　　何自强，北京航空航天大学计算机学校教授，在国防科技大学和北京航空航天大学已从事数理逻辑、离散数学、可计算性理论的教学和研究20余年。

【目录】

第一部分 可计算性理论

　第1章 可枚举性

　　1.1 可枚举性

　　1.2 可枚举集

　　习题

　第2章 对角化

　　2.1 对角化

　　习题

　第3章 图灵可计算性

　　3.1 图灵可计算性

　　习题

　第4章 不可计算性

　　4.1 停机问题

　　4.2 *产出函数

　　习题

　第5章 算盘可计算性

　　5.1 算盘机

　　5.2 用图灵机模拟算盘机

　　5.3 算盘的计算能力

　　习题

　第6章递归函数

　　6.1 原始递归函数

　　6.2 极小化

　　习题

　第7章 递归集与递归关系

　　7.1 递归关系

　　7.2 半递归关系

　　7.3 *其他例子

　　习题

　第8章 可计算性的等价定义

　　8.1 为图灵计算编码

　　8.2 通用图灵机

　　8.3 *递归可枚举集

　　习题

第二部分 基础元逻辑

　第9章 一阶逻辑初阶：语法

　　9.1 一阶逻辑

　　9.2 语法

　　习题

　第10章 一阶逻辑初阶：语义

　　10.1 语义

　　10.2 元逻辑概念

　　习题

　第11章 一阶逻辑的不可判定性

　　11.1 逻辑与图灵机

　　11.2 逻辑与原始递归函数

　　习题

　第12章 模型

　　12.1 模型的规模与数目

　　12.2 等价关系

　　12.3 洛文海姆一斯科伦定理与紧致性定理

　　习题

　第13章 模型的存在性

　　13.1 证明概述

　　13.2 证明的第一阶段

　　13.3 证明的第二阶段

　　13.4 证明的第三阶段

　　13.5 *不可枚举语言

　　习题

　第14章 证明与完备性

　　14.1 矢列演算

　　14.2 可靠性与完备性

　　14.3 *其他证明系统与希尔伯特论题

　　习题

　第15章 算术化

　　15.1 语法的算术化

　　15.2 *哥德尔数

　　15.3 *再论哥德尔数

　　习题

　第16章 递归函数的可表示性

　　16.1 算术可定义性

　　16.2 极小算术与可表示性

　　16.3 数学归纳

　　16.4 *罗宾逊算术

　　习题

　第17章 不可定义性、不可判定性和不完全性

　　17.1 对角线引理和局限性定理

　　17.2 不可判定的语句

　　17.3 *不用对角线引理的不可判定语句

　　习题

　第18章 协调性的不可证性

　　18.1 协调性的不可证性

　　18.2 历史评论

第三部分 高级专题

　第19章 范式

　　19.1 析取范式与前束范式

　　19.2 斯科伦范式

　　19.3 赫布兰德定理

　　19.4 消去函数符号和等号

　　习题

　第20章 Craig内插定理

　　20.1 Craig定理及其证明

　　20.2 罗宾逊联合协调性定理

　　20.3 Beth可定义性定理

　　习题

　第21章 一目逻辑与二目逻辑

　　21.1 可解的与不可解的判定问题

　　21.2 一目逻辑

　　21.3 二目逻辑

　　习题

　第22章 二阶逻辑

　　22.1  一阶逻辑

　　习题

　第23章 算术可定义性

　　23.1 算术可定义性和真

　　23.2 算术可定义性与力迫

　　习题

　第24章 无乘法算术的可判定性

　　24.1 无乘法算术的可判定性

　　习题

　第25章 非标准模型

　　25.1 非标准模型中的序

　　25.2 非标准模型中的运算

　　25.3 分析的非标准模型

　　习题

　第26章 Ramsey定理

　　26.1 Ramsey定理：有限的与无限的

　　26.2 KSnig引理

　　习题

　第27章 模态逻辑与可证性

　　27.1 模态逻辑

　　27.2 可证性逻辑

　　27.3 不动点定理与范式定理

　　习题

部分问题提示

加注释的参考文献