作为一位终生思考如何以最好的方式表达数理逻辑问题的学者，作者在本书中由浅入深地介绍了命题逻辑、一阶逻辑、初等算术以及皮亚诺算术的基础知识；特别是以简单易懂的形式阐释了哥德尔不完全性定理，说明了由其本人发展的表列证明方法，并穿插大量习题，于每章末给出所有习题的答案，于结尾处附上术语对照表，使得本书非常适合作为数理逻辑入门教材。

除了学者的身份，作者还是一位趣味谜题专家，致力于面向普通读者写作，将深奥的思想以故事和谜题的形式讲述，这使得本书在介绍任何知识时都不设定专业基础，采取层层递进的方式，同时还有趣味十足的例子，适合作为数理逻辑普及读物。

本书译者还特别邀请作者的学生、美国逻辑学家与计算机科学家梅尔文·菲廷（Melvin　Fitting）为中文版撰写了序言，其以简单的语言指出了数理逻辑的关键以及本书的核心所在，便于读者整体把握数理逻辑的基本问题。

数理逻辑入门教材：作者是世界领衔的哥德尔不完全性定理研究专家，师承著名逻辑学家、数学家、理论计算机科学奠基人阿朗佐•丘奇（Alonzo Church，1903—1995）。

数理逻辑普及之选：作者也是一位趣味谜题专家、魔术师、钢琴演奏家，著有多部谜题书，擅长以讲故事的方式介绍深奥的数理逻辑。

作者简介

雷蒙德·M.斯穆里安（Raymond M. Smullyan，1919—2017）　世界著名逻辑学家、数学家，也是一位职业钢琴演奏家和职业魔术师。1959年于普林斯顿大学获得哲学博士学位。先后任教于达特茅斯学院、普林斯顿大学、印第安纳大学、纽约城市大学雷曼学院等。

哥德尔不完全性定理研究专家，系统地发展了表列证明方法，并致力于向普通读者普及数理逻辑。著有30余部著作，包括数理逻辑专业著作以及趣味逻辑谜题书，如《形式系统的理论》（Theory of Formal Systems，1961）、《一阶逻辑》（First-Order Logic，1968）、《哥德尔不完全性定理》（Gödel’s Incompleteness　Theorems，1992）、《元数学的递归论》（Recursion　Theory for Metamathematics，1993）、《对角化和自指》（Diagonalization and Self-Reference，1994）、《这本书叫什么？》（What Is the Name of This Book?，1978）、《逻辑迷宫》（Logical Labyrinths，2009）、《哥德尔谜题书》（The Gödelian Puzzle Book，2013）等。

译者简介

刘新文  中国社会科学院哲学博士，中国社会科学院哲学所研究员。主要研究方向为图式逻辑、模态逻辑、皮尔士逻辑与哲学等。出版有专著《图式逻辑》《谢弗函数研究》《可能世界的名字》等。

 序    言

一般来说，数理逻辑有两个引人注目的中心，一个是我们可以证明什么，另一个是我们不能证明什么。它们都来自库尔特·哥德尔（Kurt Gödel）在20世纪30年代的重要工作，互为补充，各具张力。

为了探究我们可以证明什么，我们就必须为称之为“证明”的形式对象创建某种装置。对此，我们还必须运用熟悉的数学方法来证明它确实做到了我们所要求它做的（从技术上说，是要证明这一形式装置是“可靠的”和“完备的”）。为了探究我们不能证明什么，我们也必须建立某种装置来刻画我们所说的“计算”是什么意思。今天，我们在讨论这些主题时，一般会想到计算机。但是，真实的计算机很难精确地进行分析，它们的速度和大小是有限制的。我们需要考虑一个理想化的计算机以忽略实践上的限制，我们想要一个适合于它的形式模型以尽可能简单地工作。然后，使用这一装置，我们可以从数学上建立各种不完备性结果，说明我们使用证明以理解数学真理具有很大的局限性。所有这些内容都在本书中以简单和直接的语言得以阐释，它不是写给专家的，而是写给初学逻辑者的，只需要一些关于数学如何运作的基础知识。

在1961年出版的《形式系统的理论》（Theory of Formal Systems）中，雷蒙德·斯穆里安引入了“初等形式系统”这一漂亮却非常简单的装置来刻画“计算”这个概念。这个系统很有力量，但又易于描述、易于使用。随后，在1968年出版的《一阶逻辑》 （First-Order Logic）中，斯穆里安给了“语义表列”决定性的现代表述形式，为发现和分析形式的逻辑证明提供了非常简单而直观的装置。事实上，这一装置及其衍生物目前在许多自动定理证明的计算机系统中居于核心地位。这本书既使用了初等形式系统，也使用了表列系统来分析数学逻辑中上述讨论的两个方面。

前述两种装置是本书的基础，在表述上既简单又直观，但完全精确。虽然所说的这两个主题处于中心地位，但随着论述的展开，很多非常有趣的结果也得到了讨论和证明。这本书包含了大量的习题，并且为此还提供了答案。

我们完全可以把本书看成是一个终生思考数理逻辑基本问题并且考虑如何最好地表述它们的人所贡献给我们的杰出成果。

集合论

数理逻辑的开端与19世纪集合论——特别是由著名数学家格奥尔格·康托尔（Georg Cantor）创立的无穷集（infinite set）理论——的发展密切相关。在讨论无穷集之前，我们通常要先看一下集合的一些基本理论。

集合是任何对象的汇集。集合论的基本概念是元素关系。集合A是一堆东西，并且说对象x是A的成员，或者A的元素，或者x属于A，或者A包含x，就是说x是那些东西之一。例如，如果A是从1到10的所有正整数的集合，则数字7是A的一个成员（4也是），但是12不是A的成员。元素关系的标准记法是符号∈（epsilon），“x是A的元素”的表达可以缩写为“x∈A”。

如果A的每个元素也是B的元素，那么集合A是集合B的子集。不幸的是，许多初学者学习集合会把子集与元素关系混淆。作为区分的一个例子，让H是所有人的集合，让W是所有女人的集合。显然W是H的一个子集，因为每个女人也是人。但W很难成为H的元素，因为W显然不是一个人。子集的符号是所谓的“包含于”（inclusion），记为⊆。因此，对于任何集合对A和B，短语“A是B的子集”被缩写为A⊆B。如果A是B的子集，则B被称为A的上集（superset）。因此，A的上集是包含A的所有元素的集合，并且可能也包含其他元素。如果A不是B的全部，换句话说，如果B包含一些不在A中的元素，则B的子集A被称为B的真子集（proper subset）。

集合A与集合B相同当且仅当它们包含完全相同的元素，换句话说，当且仅当它们是另一个的子集。两个集合可以不同，如果其中一个包含至少一个不在另一个中的元素。集合A无法成为集合B的子集的唯一方法是，A至少包含一个不在B中的元素。

如果一个集合不包含任何元素，则称为空集。例如，每个人离开后，剧院中所有人的集合。只能有一个空集，因为如果A和B都是空集，它们包含完全相同的元素，即根本没有元素。换句话说，如果A和B都是空的，那么任何一个都不包含另一个中的任何元素，因为都不包含任何元素。也就是说，如果A和B都是空集，那么A和B是相同的集合。因此，只有一个空集，并且在本书中将用符号“Ø”表示。

空集有一个特征，对于第一次遇到它的人来说似乎很奇怪。作为初步说明，设想这样一个俱乐部，其董事长说俱乐部的所有法国人都戴着贝雷帽。但是假设事实表明俱乐部里没有法国人。董事长的说法应被视为为真、为假还是两个都不是？更一般地说，给定一个任意属性P，说空集的所有元素都有属性P，应该被认为为真、为假还是两个都不是？在这里，我们必须最终做出选择，数学家和逻辑学家普遍认同的选择是，这样的陈述应该被当作真的！这样决定的一个原因是：给定任意集合S和任意属性P，P对于S的所有元素都不成立的唯一方式是，至少有一个S中的元素，其中P不成立。空集对刚刚的语句也不例外，因此，P对空集的所有元素不成立的唯一方法是，至少有一个空集的元素不存在属性P，但这不可能，因为空集没有元素！［正如已故数学家保罗·哈尔莫斯（Paul Halmos）所说的那样，“如果你不相信P对空集的所有元素都成立，只要试图找到一个空集的元素，P不成立！”］这样，从此我们将认为，对于任意属性P，空集的所有元素都具有属性P。这是另一种观察它的方式，预示了命题逻辑的一个重要原则，我们将在第二部分研究，即词语“蕴涵”或“如果……那么”的逻辑用法。

在经典逻辑中使用的短语“如果……那么”对第一次遇到它的人来说有点震撼，理所当然，因为它是否真的与短语通常的使用方式相对应是非常值得怀疑的。

假设一个男人告诉一个女孩：“如果我明年夏天找到工作，那么我会娶你。”如果他明年夏天找到了一份工作并娶了她，那么他遵守了诺言。如果他找到了一份工作但没有娶她，他显然违背了他的诺言。现在，假设他没有找到工作但无论如何都要和她结婚。我怀疑没有人会说他违背了诺言！所以，在这种情况下，我们会说他遵守了诺言。关键的情况是，他既没有找到工作，也没有娶她。你对这种情况有什么看法？他遵守诺言了吗？他违背诺言了吗？还是两个都不是？假设女孩抱怨说：“你说过如果找到工作就娶我，你没有找到任何工作，你就不娶我了！”男人可以理所当然地说：“我没有违背诺言！我从未说过我会娶你——我说的是，如果我找到工作，那么我会娶你。但是我没有找到工作，所以我没有违背诺言。”

就像我说的那样，我相信你不会因为他在这种情况下没有违背诺言而感到不适，但我想你们许多人会对他说自己遵守了诺言感到不舒服。

好吧，无论“如果”部分或“那么”部分为真还是为假，我们希望“如果……那么”形式的所有陈述都是或为真或为假的。根据这条规则，既然我们已经决定这个男人没有违背他的诺言，我们别无选择，只能说他遵守了他的诺言，这看起来很奇怪！

因此，在经典逻辑中，对于任何一对命题p和q，只有当p为真且q为假时，语句“如果 p，那么 q”（也称为“p蕴涵q”）才被认为为假。换句话说，“p蕴涵q”等同于“并非p为真且q为假”，或者同等地，“p为假或p和q都为真” 也等同于“p为假或q为真”。

这种蕴涵更明确地被称为实质蕴涵（material implication），它确实有假命题蕴涵任何命题的奇怪属性！例如，陈述“如果巴黎是英格兰的首都，则2+2=5”将被视为真的！

我必须告诉你一件有趣的事：有人曾经问过伯特兰·罗素，“你说假命题蕴涵任何命题。例如，从陈述2+2=5，你能证明你是教皇吗？”罗素回答说“是的” 并给出了以下证明：“假设2+2=5。我们也知道2+2=4，从而得出5=4。从等式的两边各减去3，得出2=1。现在，教皇和我是两个。既然两个等于一个，那么教皇和我就是一个！因此，我是教皇。”

具有各种奇怪属性的实质蕴涵确实有其优点，我想说明如下。假设我从一副牌中拿出一张牌，将其正面朝下放在桌子上并说：“如果这张牌是黑桃Q，那么它就是黑色的。你同意吗？”你当然会同意。然后我将牌翻过来，这是一张红色的牌——方块J。那么你会说认为我的陈述为真是错误的吗？我的例子到此为止！