数理逻辑十二讲

本书介绍数理逻辑的基础知识和基本理论，主要讲授命题演算和谓词演算。通过本课程的学习，学生将掌握相关的基本概念、基本理论、基本推理，以及公理系统和形式化方法。数理逻辑是以公理系统和数学证明为研究对象的数学分支，对信息科学与技术的发展具有指导作用。本课程为计算机科学的基础，对培养学生的素养以及提高解决问题的能力有重要的意义。

宋方敏，南京大学计算机科学与技术系教授，博士生导师。主要研究领域是数理逻辑和量子计算，曾主持国家自然科学基金项目，863项目和中法合作项目的研究，在国内外核心刊物上发表论文50余篇。在教学上，为本科生主讲“离散数学”和“数理逻辑”课程，为研究生主讲“计算理论”课程。

吴骏，南京大学计算机科学与技术系讲师。主要研究领域是逻辑在人工智能中的应用、算法博弈论与机制设计，曾主持及参与国家自然科学基金、科技部重点研发计划等多项科研项目，在国内外学术会议与期刊上发表论文十余篇。在教学上，为本科生主讲“数理逻辑”课程，为研究生主讲“智能Agent”课程。

前言
第一讲 命题逻辑
第二讲 Boole代数
第三讲 一阶逻辑语言
第四讲 一阶逻辑的自然推理系统
第五讲 集合论的公理系统
第六讲 完全性定理
第七讲 Herbrand定理
第八讲 命题逻辑的永真推理系统
第九讲 一阶逻辑的永真推理系统
第十讲 Gentzen的Hauptsatz
第十一讲 紧性定理
第十二讲 模态逻辑概述
参考文献

数理逻辑是用数学研究逻辑推理的一门学科，旨在为推理思维建立数学模型。19世纪中叶，数理逻辑就已作为一门科学存在，在20世纪中叶它得到蓬勃发展，由于Russell、Hilbert和Brouwer代表的三大学派的建立，数理逻辑迎来了一个新时代。1931年Godel“两个不完备定理”的发表、1933年Tarski关于形式语言中的“真”概念的发表、1934年Herbrand-Godel“一般递归函数”概念的发表，以及1936年Turing关于“判定性问题”的论文，使数理逻辑开始了一个更新的时代。
此后数理逻辑对数学基础、哲学和计算机科学都产生了重大影响。
本书主要介绍命题逻辑和一阶逻辑，这是非常重要的基础理论。为了使学生易学易懂，我们既介绍Gentzen系统，又介绍Hilbert系统。然后讲解数理逻辑的4个基本定理：
完全性定理、紧性定理、Hauptsatz和Herbrand定理。最后我们介绍了模态逻辑。
本书源于作者在南京大学已试用多年的讲义，许多同学对讲义内容和习题提出了大量宝贵意见，在此作者表示衷心感谢。最后感谢我们的家人一直以来的支持和关心。
由于作者才疏学浅，本书内容一定存在不足和错误，希望读者批评指正。
作者2016年于南京大学仙林校区