“哲学前沿”第九讲 | 沈榆平：表达的边界：逻辑系统的简洁性研究

【内容提要】

逻辑系统是用符号对知识进行表示与推理的演算系统。通常，逻辑学家们除了研究逻辑系统的语法和语义，还以表达能力来衡量不同的逻辑系统。一般而言，表达能力指该系统刻画问题的能力。比如命题逻辑可以刻画所有的布尔函数，或者说，对任意（具有固定长度）的0-1字符串集，都能找到命题逻辑公式，使得其模型集恰好是该0-1字符集。事实上，存在着许多和命题逻辑有相同表达能力的逻辑/符号系统，如一些非经典逻辑、布尔线路、二元判定图等，而且这些系统往往在推理难度上和命题逻辑也是相同的。因此，研究上述逻辑之间的本质的区别成为数理逻辑方向的研究热点。

近期，人们发现使用简洁性这一标准可有效对上述逻辑作进一步区分。简洁性指一个逻辑系统的语言紧凑刻画问题的能力。具体而言，对某个给定（数学）问题，如果可以证明一个逻辑系统可能需要“相当长”的公式才能实现准确刻画（“相当长”为“指数函数”长度），而在另一个逻辑系统中仅需要短小的公式就可实现刻画。我们便可称此问题从简洁性上将两个逻辑系统进行了区分。

通过相关的证明，我们可发现在表达能力一样的前提下，有些逻辑系统严格比另外一些简洁，而有些逻辑系统之间简洁性互相不可比较（各有优势）。我们将介绍一些近期研究成果，并指出这些结果在语言哲学、人工智能、以及计算机理论和方面的意义。