“哲学前沿”第九讲：沈榆平老师阐发逻辑系统的简洁性问题

      2018年4月25日上午，中山大学哲学系18级研究生“哲学前沿”课程第九讲——《表达的边界——逻辑系统的简洁性》，在中山大学锡昌堂103室开讲，主讲人为我系沈榆平老师，主持人为我系陈少明老师。

▲讲座现场

▲沈榆平老师

报告开始时，沈老师先从真值表出发指出如何用0-1字符串表达逻辑公式的模型，并进一步用实例来展示如何通过约定的编码函数（如摩尔斯电码和五笔码等），将人类的文字信息表示为0-1字符串。同时，这些字符串也可以使用对应的逻辑公式清晰地表达出来。字符串是人类表达信息的一种基本载体，在数字时代，文字、声音、图像、视频等各类信息都可通过编码转化为字符串，进而本质上可以用逻辑的方式给予表达。广义上而言，这和维特根斯坦所称的“What can be said at all, can be said clearly”（“凡是可说的东西，都可以说清楚”）本质上是契合的。

紧接着，沈老师指出有些“可说的东西”“说清楚”是容易的，而另一些问题要“说清楚”可能非常困难，并抛出一个关键的思考——它们之间的边界在哪？沈老师列举了“棋盘与麦粒”，“汉诺塔”两个经典的难问题，并指出这些问题“困难”的特质在于解决它们需要指数增长的空间或时间资源；相对而言，“容易”的问题是指解决它只需要多项式增长的时间资源。此时，沈老师引入了逻辑系统简洁性的概念，简单说来，这是指逻辑系统公式紧凑表达问题的能力。对于两个不同的逻辑系统A和B，称A严格比B简洁，如果所有在B中容易表达的问题（只使用多项式尺度的公式），在A中都容易表达；同时存在着A中容易表达的问题，在B中难以表达（须使用指数尺度的公式）。

一个有趣的事实是，两个逻辑系统A和B的简洁性可能是不可比较的，即既存在A中容易表达的问题在B中难以表达，也存在B中容易表达的问题在A中难以表达。

最后，沈老师给大家介绍了逻辑系统简洁性方向上的一些前沿成果，如V.Lifshictz和A.Razborov、沈榆平和赵希顺在命题逻辑与非单调命题逻辑的简洁性比较结果，以及在此基础上对一些逻辑系统家族在简洁性上边界的区分及未来需要研究的问题等。报告最后引用了维特根斯坦的一句话做为总结：“ The limits of my language means the limits of my world”。

本次报告的内容横跨了哲学、逻辑和计算等领域，引起了听众们很大的兴趣，报告最后在陈少明老师的主持点评下圆满结束。