【数理逻辑如何入门】：什么是数理逻辑

题外话
数理逻辑是一门看上去“高大上”的学问，许多人希望学习但是在几经尝试之后不得不放弃，很少有人能够长期忍受那些莫名其妙的名词术语和满篇的数学逻辑公式。有些人似乎学了一些，但也只是重复书中的语言。看过一些人的学习笔记，大部分只是囫囵吞枣地把原书中的公式、定义、定理抄写下来，最多也就是归纳总结，几乎没有人可以说个所以然。也许我的见识不够广，至少到现在，尚未见到一篇文章、一本书能够清清楚楚、明明白白地讲清楚哥德尔定理是什么，大部分说的都是云山雾罩，让人感觉是雾里行舟、秉烛夜游。
本人虽不才，但是一个基本理念就是——用简单的语言讲清楚复杂的理论，虽然因能力有限无法真正达到，但这是我最高的追求。四年前我曾说过：“本人对那些能用最粗浅的语言讲明白最深奥道理的人有着最崇高的敬意，对那些用最深奥的语言讲着最浅显道理的人表示不屑，对满嘴深奥名词短语、术语但听者不知所云者表示鄙夷。用最浅显的语言讲明白最深奥的道理，是本人和年轻学子互动时的最高追求。” 关于这一点，推荐一篇文章《为什么学者不会好好说话？》
小站改版以来，本栏目中尚没有全面介绍数理逻辑的文章，两年前写了《数理逻辑的三个核心概念》系列，但后来觉得切入点有问题，起点还是太高，文章中提出的问题太突兀，上不着天下不着地，没有我们熟悉的背景知识支持，故再没有写下去。后来又写了一系列集合论的笔记，对这个系列，至少我自己还算满意，打算继续写下去，如果把《Naive Set Theory》这部著名教科书的笔记完全写一遍还是非常有意义的。
如何全面、简要而又能抓住重点地介绍数理逻辑，确实不太容易。国内国外许多教科书有一个通病：只见树木不见森林，上来就是命题逻辑——谓词逻辑——推理论证——哥德尔定理这样的套路，令人好生困惑。
经过这些年的阅读、写作，对各种数理逻辑教科书大致上了然于胸，因此想在这里重开一个系列，从最基础讲到哥德尔定理，以及后续发展：根岑的证明论、塔尔斯基的真值语义论，和递归函数论。
这个系列注重语言的通俗和深入浅出，可以作为你阅读那些艰深著作时的一个‘精神支柱‘：在你已经透彻了解了那些天书般符号背后的思想之后，符号本身只不过是那些思想的一种特殊表达而已。这里给大家的一句鼓励的话便是：一些用高深的语言、难懂的符号、深奥的术语堆砌的所谓理论，完全可以用大白话————谁都听得懂的普通语言表述出来，也可以找到我们生活中大致的对应物。如果理解了实质，那些符号不过尔尔。如果有人用那种玄虚的语言、谁都听不懂的术语秀炫，只能说明此人对理论并没有完全理解，充其量只是鹦鹉学舌地会背诵而已。
一、什么是数理逻辑
首先，中文这个术语的意义就是语焉不详，逻辑就是逻辑，什么叫“数理”？英语的原文就比较好理解了——mathematical logic、数学的、和数学有关的逻辑。因此，mathematical logic，应当是数学逻辑，关于数学的逻辑。换句话说，没有数学，这个逻辑就失去了研究的内容，没有逻辑，这个数学就失去了依托。不过，语言的表达就是一种约定，既然大家都叫“数理逻辑”，我们也只好从众，但心里应当把这门学问理解为：关于数学的逻辑。
什么叫‘关于数学的逻辑’？我们把它拆开来看。首先，它是逻辑，而逻辑，我们知道，就是研究推理论证的学问。推理是逻辑研究的内容，论证是逻辑研究的形式。一个完整的逻辑论证，是由一组句子依次构成。前面的句子叫做前提，最后那个句子叫做结论，一个论证如果‘正确’，那么一定符合‘若前提为真则结论也为真’的规律。这是一般的逻辑。这种逻辑，如果我们用自然语言表达，通常叫做‘普通逻辑’，而我们中国人使用的‘自然语言’是中文，所以‘普通逻辑’是用中文表达的。为什么普通逻辑‘普通’，因为中文谁都会说，不那么高大上，所以显得‘普通’😀。如果不用自然语言，而是用拉丁、希腊字母、逻辑连接符加上括号、标点符号表达出来，我们称作‘符号逻辑’。有了符号，许多自然语言表达不清的概念就比较容易表达了。这就像数学方程中的未知数，如果没有x、y之类的字母，像2x=10这样的式子我们只能说：二乘以几等于十，这显然既不经济也不准确。如果是二元方程：2x - y = 10，用自然语言就更别扭了。逻辑学也有这个问题，例如，我们有时表达命题中的概念，自然语言我们可以说‘这个’、‘那个’、‘某个’，但是这些‘这个’、‘那个’、‘某个’一多，我们就很难表达了。因此，符号逻辑在表述同样的逻辑推理论证时，对逻辑中各个元素的表达更清晰。不过，这种清晰的代价就是丧失了可读性。人就是这样的矛盾体。做科学研究，概念、术语、命题越清楚越好，而学习阅读理解，文体越通俗易懂越好。总之，普通逻辑就是用自然语言表达的逻辑，而符号逻辑则是用各种字母、数字、外加一些辅助符号表示的逻辑，因此后者的特点是定义精确、明了，不会产生歧义，但是对初学者来说不像自然语言那么直观。
那数理逻辑是什么？在回答这个问题之前，请允许我先问个问题：普通逻辑也好、符号逻辑也好，既然是做推理论证，那么这些推理论证的内容是什么？换句话说，那些构成论证的句子的命题内容是什么？有些人会说，没有固定内容，什么内容都可以。是的，如果你看过普通逻辑的教科书，确实如此。普通逻辑教科书中的例句包括各种内容，政治、经济、军事、法律、数学、物理、工程、天文地理无所不包。但是，这种逻辑学其实没有特定的推理对象，用我们普通逻辑教科书最标准的说法就是：研究思维最一般的规律。什么叫‘思维最一般的规律’？天晓得！
数理逻辑，正如我们一开始说的，就是关于数学的逻辑，换句话说，就是我们在学习数学时所用的方法——老师教我们学习时用的方法，也是数学家研究数学所用的方法，更是数学教科书采用的方法。什么方法？我们随便打开一本大学的数学教科书，映入眼帘的基本上都是这种模式：
一、提出若干基本概念：
  基本概念1、基本概念2，基本概念n；
二、用前面的基本概念定义新概念，
  定义1、定义2、定义n；
三、提出若干基本命题：
  基本命题1，基本命题2，基本命题n；
四、从基本命题出发、提出若干派生命题:
  派生命题1：
  对派生命题1的证明：
  根据前面的基本概念、定义、基本命题和已经证明过的其它命题进行逻辑论证，得到结论；
  定理1：上面证明所得到的最后结论，这个结论是一个新命题；
  派生命题2：
  对派生命题2的证明：
  根据前面的基本概念、定义、基本命题和已经证明过的其它命题进行逻辑论证，得到结论；
  定理2：上面证明所得到的最后结论，这个结论是一个新命题；
  派生命题n：
  对派生命题n的证明：
  根据前面的基本概念、定义、基本命题和已经证明过的其它命题进行逻辑论证，得到结论；
  定理n：上面证明所得到的最后结论，这个结论是一个新命题；
五、举例：
  例题1、例题2、例题n；
六、习题
  习题1、习题2，习题n；
重复上面过程
所谓数学的方法，就是按照上面的程式、根据基本概念定义派生概念，从基本命题出发推导定理的方法，换句话说就是证明的方法。学习数理逻辑，本质上就是学习如何从理论上理解、从实践中掌握数学证明的方法。
什么是数学证明？说白了，证明就是逻辑学推理论证是另一种说法，在普通逻辑中我们称作论证，而在数理逻辑中，我们称作证明——其实只是换了个马甲，而实质没有变，仍然是论证：一组句子叫做前提，最后那个叫做结论。不过，进了数学的门，名字全换了——前提改称【公理】，结论改称【定理】，论证改称【证明】。
不过，这只是形式的改变，实质的改变是，命题句的内容不再海阔天空、包罗万象，而只集中在某些特定的数学对象。那么具体是哪些数学对象呢？学过数学分析的都知道其研究对象是实数，而要研究实数，归根结底要从自然数开始。这是整个数学大厦的基础。对这个问题的研究就成了一门专门的学问——数学基础，而数学基础有两个根本任务，第一，回答什么是数学的本原，能否从若干基本公理，派生出所有的数学理论？第二，如何解决数学命题中的悖论问题？因此，数理逻辑的命题都是关于自然数的，或者更精确地说，数理逻辑是【数学基础】这门数学分支的表述语言。换句话说，数理逻辑是数学基础的外在表达形式，而数学基础本身作为一门数学分支，其基本内容是以集合论为工具所描述的关于算术的数学结构，这样、就形成了以数理逻辑为表以数学基础为里的特定数学分支。当然，现代数学只要是可以用集合论形式化的，都可以用数理逻辑的语言描述，用逻辑演算作为证明的工具。
而数学基础中最基本的数学对象是自然数，其基本运算规律的研究称之为算术，而关于算术命题的研究称作数论，因而数理逻辑中许多命题的内容都是关于数论的。而到了现代，随着数学的高度抽象化，大部分数学理论都可以用集合论作为工具定义为特定的数学结构，同时数学对象已经不仅仅是数和传统意义上的空间，任何可以定义为“结构”的对象都可以作为代数理论研究的对象，因此，现代数理逻辑的命题内容，大都集中到了代数、特别是对群公理系统的研究。现代数理逻辑，随着研究的深入和拓宽，内容越来越多，已经可以根据其性质进一步细分。具体地说，大致可分为四个部分：
模型论：逻辑语言与特定数学结构之间的对应关系；
证明论：研究逻辑演算（论证的另一种说法）的形式侧面。证明可以看做是一个命题句集合（公理集合）与定理命题句之间的真值对应关系，因此证明本身也可以当做数学对象去研究；
集合论：逻辑学所要描述的任何数学结构、模型、其中的所有概念、基本元素、派生元素等都是用集合论定义的。特别是无穷性的概念，更是定义无穷模型的基本工具。而定义逻辑语言和模型之间的对应关系所需的工具是函数，而函数的定义，要靠集合、关系等，同时现代公理集合论要解决数学悖论的问题。因此，集合和函数是研究语言（数理逻辑中的一阶谓词语言）与结构（用集合论所定义的数学结构）之间相互关系最基本的工具。
递归论：又称作可计算理论，研究的是，什么样的函数是可计算的、什么样的函数是不可计算的，有没有什么确定性方法判断一个给定函数是否是可计算的。这里的所谓计算，又称算法，是指在有限步骤之内，完成确定的操作，并产生确定的结果。
从上面的讨论可知，所谓数理逻辑无非就是一种‘专业逻辑’，符号逻辑的数学版，专门描述数学的逻辑，或者说以数学作为命题内容的符号逻辑。在这种逻辑中，许多逻辑学的术语都改变了名称，而研究的方法则是将逻辑学的对象改造成了像数、多项式、向量、矩阵一样的数学对象，这是普通逻辑学所没有的。数理逻辑的最大特点是，不再将命题作为研究的重点，取而代之的是函数的概念，可以说，数理逻辑的四论，都和函数有关。这一点我们以后还会详细谈。
以上这些，只是数理逻辑的一个侧面——研究数学的形式侧面：数学语言和证明规则，以及语言与结构之间的关系。数理逻辑的另一个侧面是直接将逻辑作为数学的内容研究，这就是——布尔代数，或者称作逻辑代数。这种代数最直接应用就是数字电路理论中的组合逻辑。而作为数学分支，逻辑完全脱离了原本作为推理的研究，而只作为纯粹的代数结构，形成自成一体的代数理论。从这个角度来看，逻辑代数已经脱离了我们所熟悉的逻辑学的内容，成为代数的一个分支。我们在「离散数学」所学的「数理逻辑」内容基本上属于逻辑代数的范畴，主要研究逻辑式的代数性质和一些初级的恒等变换。
如果用一句话总结什么是数理逻辑的话，那就是：数理逻辑研究数学家所进行的逻辑推理论证，它的结果就是对数学语言、公理系统和推理规则的研究。
二、学习数理逻辑有哪些好的教科书
学习数理逻辑和普通逻辑的一个最大不同就是：你需要一定的数学知识，特别是离散数学和数论方面的知识，例如集合、函数、关系等，最理想的，是有一些初步的抽象代数的概念，例如群、环、域，结构、映射、同构、同态等，以及一些形式语言方面的知识，不过最重要的是学会数学证明的方法。这里有一个书单可作为参考：
【预备知识】
1. 华罗庚的《数学归纳法》：归纳法是逻辑学定义形式语言的基本方法，任何逻辑学的学习，数学归纳法是基础的基础。学习归纳法，这本书是最好的选择，没有之一。
2. Richard Hammack 《Book of Proof》：这本书通俗易懂，教你如何写证明，同时详细介绍了数理逻辑中常用的工具：集合、函数、关系。最暖心的是，这本书可以自由下载。
3. Daniel Velleman 《How to Prove it》：内容和2大同小异，只是多了命题逻辑和谓词逻辑部分。相比前一本，这本书更有名，过去学习数理逻辑没有一个不是从这本书入门的。
本书的国内版：人民邮电出版社《怎样证明数学题》
4. Larry Gerstein 《Introduction to Mathematical Structure and Proofs》：
这本书可以说是前两本的提高版，除了常规的一阶逻辑和集合函数等的内容外，还包括是组合数学、数论初步和公理集合论初步的内容。有了这些内容，基本上就有了学习数理逻辑的技术基础。
【背景知识】
5. 马丁·戴维斯的《逻辑的引擎》：这本书可作为了解近代数理逻辑起源的历史读物，当然这个了解是非常粗线条的。
6. 张家龙的《数理逻辑发展史：从莱布尼茨到哥德尔》：这是我看到的国人写的唯一一本数理逻辑史的著作，可读性比前一本要差一些，但是史料很丰富，虽说是从莱布尼茨开始，但实际内容是从亚里士多德开始，把亚氏逻辑的24个基本逻辑推理式也包括了。
7. 侯士达的《哥德尔、埃舍尔、巴赫：集异璧之大成》：这是一篇巨著，中文版有一千多页，基本内容是关于递归论和形式系统。个人认为你不会因为读这本书就可以理解哥德尔定理，本书对你的最大挑战不是逻辑，而是你对音乐理论的理解。如果你对乐理没有兴趣这本书恐怕不是你的第一选择。
【入门书】
8. Raymond Smullyan 《A Beginner’s Guide to Mathematical Logic》这本书是我最喜爱的数理逻辑书。Smullyan是阿隆佐·丘奇的关门弟子，和5的作者Martin Davis是同门师兄弟，但是Smullyan的名气和成就更大，特别是关于论证的tableau范式就是Smullyan提出的，除此之外，他还写了许多关于数理逻辑的科普读物——puzzle系列，只要有英语的阅读努力，你的逻辑知识允许是零。最大特点就是，他的所有读物都是面向逻辑门外汉的，而且是以讲故事为主。
Smullyan的另外一本书是专门讲哥德尔定理的《The Gödelian Puzzle Book》，虽然通俗易懂，但不敢保证读完以后你真的对哥德尔定理有透彻理解，但是他的写作风格确实讨人喜欢。
9. Gamut 《Logic, Language and Meaning》第一卷：这本书虽然不是直接讲数理逻辑，但是把一阶逻辑以符号逻辑的形式讲得清清楚楚，学完这本书，基本上具备了学习高端（研究生教科书）的能力。
【标准教科书】
以下这几本书，可以任选一，也可以互为参考，都是本人的最爱：
10. Joseph Shoenfield 《Mathematical Logic》
11. Peter Hinman 《Fundamentals of Mathematical Logic》
12. John Bell & Moshé Machover 《A Course in Mathematical Logic》
13. Yu Manin 《A Course in Mathematical Logic for Mathematicians》
14. Wolfgang Rautenberg 《A Concise Introduction to Mathematical Logic》
【古典教科书】
15. Stephen Kleene 《Introduction to Metamathematics》
本书的中译本：莫绍揆译《元数学导论（上、下）》
16. Rudolf Carnap 《Introduction to Symbolic Logic and Its Applications》
17. Alfred Tarski 《 Introduction to Logic and to the Methodology of Deductive Sciences》
本书的中译本：周礼全等译 《逻辑与演绎科学方法论导论》
18. Alonzo Church 《Introduction to Mathematical Logic》
19. Haskell Curry 《Foundations of Mathematical Logic》
其中15是必读。
以上教科书的一个共同特点就是，对数理逻辑是一门什么样的学科、它的性质、特征在逻辑学、数学中的地位都有非常宏观、详尽的论述，这是其它类似教科书所欠缺的。当然，在技术细节方面，还有很多好书，今后根据我们的话题推进会随时介绍。而古典教科书部分，学习的重点不是知识，而是方法，如何把握数理逻辑作为科学研究的一种基本素养的训练。
如果有了上述的基础，你就可以根据爱好，选择相应的分支理论，包括集合论、模型论、证明论和递归论进一步深入学习。考虑到这篇笔记仍然属于初级内容，四论方面的教科书就割爱了。
总结一下：数理逻辑，正确的表述应当是“数学的逻辑”，这个表述反映了这个学科的一体两面：关于数学的逻辑，和关于逻辑的数学。前者研究的是数学家们进行逻辑推理时使用的方法，后者研究的是逻辑作为一种数学结构的代数性质，又称逻辑代数。狭义上的数理逻辑通常是指前者，研究的重点是推理论证的数学形式：证明。研究方法是将证明看作是形式和内容的两面体，前者称为句法研究，后者称为语义研究。句法研究的基本内容就是符号逻辑，数学中所有证明的表述形式都应当或者可以转化为一阶逻辑语言，因此数理逻辑的基础部分的学习主要是包括一阶语言和一阶逻辑演算在内的一阶理论。语义研究，主要是研究由形式语言、推理规则和公理集合构成的形式系统与某个特定的数学结构之间的映射关系。
最后要补充的就是：数理逻辑除了研究证明，也要研究计算，因为只有证明和计算合在一起才能构成完整的数学。这一点是数理逻辑和普通逻辑的最大的不同。而计算，英语通常有两种表达方式：computation和calculation。前者偏重于计算模式、步骤，或者叫题型，专业一点叫做算法，后者偏重于具体的代数运算。数理逻辑是通过研究calculation来研究computation，以calculation的实践来获得computation的理论。不过作为初学入门，我们的重点仍然是证明而不是计算。只有到了学习证明论和递归论的时候计算才成为重点。
下一篇笔记，将根据上面的五部标准教科书，谈谈数理逻辑的基本性质和一阶语言。这五部教科书，只要详细通读一本，认真做练习，就可算是粗通数理逻辑，你至少可以到‘知乎’当‘专家’了。