杨英锐：学术散文之十九  逻辑与数学

学术散文之十九

                          逻辑与数学

                            杨英锐

（一）馥蕾相变，以微见著

    四十多年前，在北师大数学系念书的时候，主管我们班教学的是严士健先生。有一天离下课还有点时间，严老师给班上出了一道趣味智力题，算是调剂一下。说的是有12个乒乓球，其中有且只有一个次品。这些乒乓球其他条件都一样，只是那个次品球略轻或略重于好球，但轻重不知，这区别得用天秤才称的出来。现给一台精度适用的天秤可在天秤两端按任意组合放球，要求称三次即找出次品球来。后来我知道，这道小球题出自一本前苏联出版的趣味数学智力题集，很多人都知道，很多人都会做。

    当时在课上，一会儿班里一位学霸（后来跟严先生读了博士）做出来了。我脑袋慢点儿，再过一会儿也做出来了。大家的解法其实和那本题集给出的方法差不多，略述如次。把12个小球从1到12编上号，分为三组。第一称，天秤一边放第一组小球1-4，天秤另一边放第二组小球5-8。若第一称二组重量相等，后面二称的情形简单。若第一称二组重量不等，情况就复杂些，一般的做法是在第二称时即要用若干在第一称中用过的球，还要用到若干第一称中没用过的球（即从第三组球9-12中任意选用）。第三称的技巧与第二称类似。有兴趣的朋友读到这里，可以停一下，试解此题，趣味趣味。

    那天晚上，我躺在被窝里琢摸这小球题。先是觉得这题我解的出，别人也解的出而且比我解的还快，觉得没劲。再说了，这解法怎么看都觉得是凑出来的，既无美感，也无快感，凭的就是个小聪明，这叫什么数学呢。快瞇糊着的时候，我想出了以下解法。

    第一称左边放第一组球1-4，右边放第二组球5-8。此处忽略结果等重的简单情况。若所称结果两边重量不等，不失一般性地可假设左组轻右组重。关键在于第二称，左组取球1、球2和球5，右组取球3、球4和球6。此处仍然忽略结果等重的简单情况。若第二称结果两边重量不等，不失一般性地可假设左组轻右组重。如此，球3、球4和球5都曾又在轻组又在重组，必为好球。坏球必在球1、球2或球6中。第三称，左球1右球2，若等重则球6为坏球。若不等重，轻者为坏球，因为重者曾既在轻组又在重组必为好球。解毕。

    此解一出，我顿时心里一阵兴奋。我当时立刻意识，这是最美解，其美感源于逻辑排中律贯彻始终而带来的对称性。此即题目中所指的“馥相”。我当时还立刻意识到，这是最优解，其优势在于随即得到称球题的强化版，即可增加一个条件：对于任意一称，若结果为两边不等重，下一称则不得使用此称未用之球。此即题目中所指的“蕾相”。馥相即出，蕾相相随，以微见著，就是追求数学美与数学发现的般配。

（二）逻辑数学，楚河汉界

    我在课上给学生讲哥德尔不完全性定理之前，总是先用最简单的方法讲清逻辑与数学之异同。下面是我独创的一种讲法。

    逻辑学中有逻辑联结词，比如合取和析取，这些亦称为逻辑算子。数学中有数学运算，比如加法和乗法。逻辑算子与数学运算有本质的不同，这通过以下简单比较可以看出來。先看逻辑算子。析取式有 “P或者非P”，是重言式，永真，可用于定义布尔代数的单位元1。合取式有 “P并且非P”, 是矛盾式，永假，可用于定义布尔代数的单位元0。再看数学运算。加法有 “A加负A等于0”，乘法有 “A乘A的倒数等于1”。不难看出，析取与加法，合取与乘法都是不能互相置换功能的，因为得出的单位元不同。进一步看，析取和乘法，合取与加法也都不能做功能置换。因为，真与Q的析取还是真，而1乘b却等于b。类似的，假与Q的合取还是假，而0加b却等于b。究其原因，竟是逻辑里的单位元与数学中的单位元有本质的不同，数学负不同于逻辑非。真是一言不合，便使逻辑与数学分家，成楚河汉界之隔。

    以上说明，在逻辑与数学之间横隔着一条鸿沟。由于命题逻辑和布尔代数是等价的，而布尔代数是计算机科学的语言句法，所以这条鸿沟也是计算机科学与数学之间的鸿沟。

    这种铺垫，简单明了，看似小技，却非雕虫。知道了鸿沟之深隔，才能体会到哥德尔配数法（见杨英锐，《哥德尔与塔斯基双子定理赏析》）如何一桥飞架南北的如虹气势。

（三）元逻辑，元数学

    元逻辑是指一个逻辑系统的整体性质，如可靠性，协调性和完全性。元数学一词是罗素和希尔伯特的用法，指的是关于数学基础问题的研究，如数学系统性质的独立性问题。哥德尔1930年证明了一阶逻辑的完全性，是元逻辑硏究。哥德尔1931年证明了一阶理论的不完全性及其协调性的独立性，是元数学研究。

    数学系的博士生，哪个不是题海里血拼出来的百战之余。数学系的教授，哪个不是驰骋黑版的领袖，公式堆里的班头，运剑气于粉笔，杀数横刀如麻，证明跃马遍踏。可在世纪数学难题阵前，能百万军中取敌上将首级者又有几人。元逻辑，尤其是元数学思维，往往能助人于无声处听惊雷，有事半功倍的效果。哥德尔，希尔伯特和冯·诺伊曼都个中高手。

    久悬而未决的数学难题，如克雷千禧迷题中的黎曼猜想，P/NP问题和质量缺口问题，其难点在逻辑上是相通，而且难点越突出越相通。在这个意义上，前面说到的“乒乓球秤重”问题是一个超级缩影。举例说来，黎曼猜想直接涉及所谓的二阶逻辑，恐怕就是一些数学家朋友未曾意识到，或始料不及的。这些数学谜题的迷惑之处似乎都在于元数学性质缺失或元逻辑性质模糊， 而这也正是其迷人之处。

（2019-8-23 初稿，2021-3-4 改写稿）