蔡少伟(中国科学院软件研究所/北京航空航天大学):大模型辅助的命题逻辑可满足性研究:复杂性与求解器
命题逻辑可满足性(SAT)问题要求判定一个给定的命题逻辑公式是否存在一组赋值使公式为真,SAT问题是数理逻辑与理论计算机科学的基础问题,其理论和工程研究都广受关注。近年来,大语言模型在理论分析和算法研发方面展现了优秀的能力,为SAT研究提供了新思路。本报告介绍我们在大模型辅助下进行的相关研究,包括理论算法复杂度分析和求解器研发,得到了3-SAT问题最好的理论复杂度上界,研发的SAT求解器在标准数据集上明显超过SAT比赛人类设计的冠军求解器,并且首次解决了密码学中关于ASCON四轮活跃盒数目的开放问题。
刘路(中南大学):Complexity of Variable Word Theorems
我们介绍variable word类型定理以及它们与Ramsey染色定理的联系。通过构造ordered variable word定理的弱解,Patey和我们证明Carlson-Simpson引理、open dual ramsey定理具有算术解;以及Carlson-Simpson引理(在某些参数情况下)不证明ACA。另一方面,Miller与Solomon等人提出问题, variable word infinite是否有可计算解。我们证明这一问题与一个纯粹组合数学问题等价。该组合数学问题是组合数学知名定理Hales-Jewett定理的推广。我们介绍该组合数学问题上的一些进展和困难。
周北海(山西大学/北京大学):认知逻辑与认知主义:认知科学时代逻辑学的新面向
20世纪后半期在认知科学新的时代背景下,逻辑学出现了新的发展动向。van Benthem认为,“现代逻辑正在经历一场认知转向”。“认知转向”在什么意义上成立还需考察,但至少出现了新的面向,这就是认知逻辑(cognitive logic)和关于逻辑的认知主义。
什么是认知逻辑尚未取得共识。从产生和实际发展的情况看,认知逻辑是人类推理的逻辑,包括以人类推理为中心的各种扩展逻辑。在我国epistemic logic常被译为“认知逻辑”,也译为“知识逻辑”“认识论逻辑”等。谁该叫“认知逻辑”,这不是译名问题,而是对epistemic logic与cognitive logic两种逻辑的认识和理解问题。epistemic logic是模态逻辑的技术性扩展,在系统构造的前期会关心知识的概念和定义等问题,在一定程度上与认知有关,但就这些逻辑本身来说,它所关心的是特定知识的真值组合问题,与人类认知意义下的知识推理基本脱节。今天cognitive logic的研究在我国也已然开始。正本清源,“认知逻辑”的称号当然应该归位于cognitive logic。
认知逻辑的发展必然会引起关于逻辑学的哲学思考,表现为引发了新心理主义和汉纳逻辑认知主义。新心理主义者中有两位著名逻辑学家Gabbay和van Benthem,他们认为,逻辑学应该搁置弗雷格的反心理主义,面对人类推理开展研究,并且在这一方向的研究中必须迎回心理主义。汉纳逻辑认知主义属于来自心理学和哲学关于逻辑学的意见。汉纳首先提出“逻辑认知主义”这一术语,并提出相对完整的哲学主张和理由,包括试图将所有逻辑都归为人类的认知建构。
新心理主义和汉纳逻辑认知主义本质上是逻辑观问题。要对这些“主义”给予回应,有必要扩大视野,从逻辑的基本概念和整个逻辑学的发展历程出发,才有可能给出恰当的分析和评论。逻辑是推理的规律。逻辑学是关于逻辑的学问,有社会历史文化属性。今天回看逻辑学的发展,可以概括为2+1个起点、两种形态、两大领域和三个时代。起点中的“2”指的是《工具论》和《概念文字》,“+1”指的是《王港逻辑》;两种形态即传统逻辑学和现代逻辑学;两大领域即思想逻辑学与思维逻辑学;三个时代即早期科学时代、数学基础时代和认知科学时代。
认知逻辑在思想上可以上溯到《王港逻辑》,属思维的逻辑。因为以现代逻辑的方法和理论为基础,认知逻辑属现代逻辑,是思维逻辑的“现代版”,其主要目的不是教导个人思维,而是人类推理规律的揭示和刻画。epistemic logic是弗雷格思想逻辑的延续,与认知逻辑分属不同领域,二者有本质区别。如何面对认知科学时代的逻辑学新发展,向前看是认知科学带来的认知主义,但是新心理主义选择了向回看,回归心理主义。认知主义是认知科学时代逻辑学在哲学思想上的必然结果。逻辑学有思想的逻辑和思维的逻辑。认知主义只适用于思维的逻辑,这决定了认知主义只能是限于思维逻辑的有界认知主义。汉纳逻辑认知主义将所有逻辑都置于认知之下,有越界问题。