2024年11月15日下午3时，上海交通大学计算机系陈翌佳教授应邀于华南师范大学文科楼211讲学厅为到场师生带来了一场题为“First-order Logic through the Lens of Computer Science”的学术讲座。本次讲座主持人为中山大学哲学系的赵希顺教授。讲座吸引了众多师生参与，现场气氛热烈。

讲座伊始，陈教授以哲学家维特根斯坦的名言“语言的界限就是世界的界限”，引出计算机科学中一个相似的现象：我们使用怎样的逻辑，决定了我们拥有怎样的表达能力和计算能力。

陈翌佳教授在讲座中

首先，陈教授展示了一阶逻辑具有的表达能力。陈教授指出，一阶逻辑是数学和计算机科学领域最重要、使用最广泛的逻辑，它能定义一个数据结构中元素具有的性质。在简要介绍串和图两种数据结构的概念之后，陈教授使用一阶逻辑表达了几种串和图上的性质。接着，陈教授举出了一些一阶逻辑不能表达的性质，表明一阶逻辑的表达能力存在局限，如不能计数、不能定义传递闭包等。而将一阶逻辑扩展为MSO后，语言的表达能力随之增强，可以表达一些原本无法表达的性质。通过介绍计算机科学领域的几条著名定理，陈教授说明了MSO的表达能力与有限自动机有紧密联系。

陈教授进一步指出，MSO的表达能力仍有局限。为了表达串上的某些重要性质，一阶逻辑被扩展为SO、ESO、LFP等更强的逻辑，并且，每一种逻辑的表达能力都对应某一类图灵机的识别能力。陈教授逐一展示了描述性的逻辑与机械的、构造性的图灵机之间这种完美的、精确的对应，印证了讲座开头的那句名言。

另一方面，鉴于一阶逻辑的重要性，我们也可以不扩展一阶逻辑，保持语言的表达能力不变，而把要表达的性质限制在特定的范围。陈教授介绍了一些前沿性的研究成果，这些成果表明，如果对图作出某种限制，那么图上能被MSO表达的性质也能被一阶逻辑表达。简要介绍证明思路后，陈教授总结了此次讲座的内容：计算机科学中，一阶逻辑的表达能力存在局限，因而或者我们将其扩充为其他逻辑，或者我们将研究的对象的性质限制在一阶逻辑的表达能力之内。

赵希顺教授主持互动环节

熊明教授参与互动

讲座最后的讨论环节，在场师生积极提问。针对“是否有一般的方法将不同种类的图灵机与不同表达能力的逻辑对应起来”等问题，陈教授做了专业且详尽的解答。至此，本次学术讲座在师生互动中落下帷幕，在场师生受益匪浅，对逻辑与其表达能力有了更深入的认识。

文字｜蒋卓炎

图片｜陈抒帆

编辑｜廖彦霖

审核｜高贝贝