可计算性与数理逻辑学习讲义

《可计算性与数理逻辑学习讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、可计算性与数理逻辑ComputabilityandLogic周晓聪(isszxc@mail.sysu.edu.cn)中山大学计算机科学系,广州5102752011年10月22日2版权所有，翻印必究前言本讲稿是阅读研究生教材“可计算性理论与数理逻辑（第四版及第五版，英文版，以下简称教材）”[?]的笔记，并结合刘咏梅老师的讲稿（以下简称讲稿）而撰写，供研究生数理逻辑课程学习参考或供教师讲课时参考。iii前言目录前言i目录iii第一部分可计算性1第一章可枚举集31.1可枚举集..........................................31.2对角线方法............

2、.............................61.3习题.............................................8第二章图灵机与算盘机112.1图灵机............................................112.2不可计算性.........................................202.3算盘机............................................212.4图灵机模拟算盘机.....................................242.

3、5算盘机与递归函数.....................................292.6习题.............................................29第三章递归函数与图灵机313.1递归函数..........................................313.2递归集与递归关系.....................................353.3图灵机与递归函数.....................................413.4半递归关系与半递归集.......................

4、............453.5习题.............................................52第二部分数理逻辑55第四章一阶逻辑的语法与语义574.1一阶逻辑的语法.......................................574.2一阶逻辑公式的语义....................................59iiiiv目录4.3习题.............................................60第五章紧致性定理635.1一阶公式的模型.............................

5、..........635.2紧致性定理.........................................675.3项模型的构造........................................695.4封闭性句子集的构造....................................725.5习题.............................................73第六章证明系统与完备性756.1矢列演算..........................................756.2完备性定理............

6、.............................776.3习题.............................................80第七章算术系统与不完备性定理817.1公式的歌德尔数.......................................817.2递归函数的可表示性....................................837.3极小算术与可表示性....................................947.4不完备性定理........................................1

7、017.5习题.............................................106第一部分可计算性1第一章可枚举集1.1可枚举集一个集合是可枚举的(enumerable)，或说可数的(countable)，非形式化地说，如果它的元素可以被枚举，即排列为一个单一的列表(list)：x1,x2,···,xn,···，等等。定义1.1.1集合A称为可枚举集(enumerabl