基于多属性决策的一阶逻辑子句选择方法

基于一阶逻辑的自动定理证明器(ATP)在知识表达和自动推理研究中占据重要地位,而启发式策略则是提升ATP性能的关键研究方向.主流的启发式策略通常通过描述子句属性来确定属性优先级,从而选择子句,但属性优先级受人为因素影响,且评估子句耗时较长.为此,本文基于矛盾体分离(S-CS)规则,提出一种新的多属性决策(MCDM)子句评估方法.首先,利用熵权法对子句属性进行客观赋权;其次,结合偏好顺序结构评估法(PROMETHEEⅡ)对子句进行评估,得到子句的完全排序;最后,将提出的MCDM方法加入自动定理证明器CSE 1.5(contradiction separation extension 1.5)、Vampire 4.7和Eprover(E 2.6)中,分别形成新的证明器MCDM_CSE、MCDM_V和MCDM_E.对MCDM_CSE测试了国际定理证明器问题库TPTP(Thousands of Problems for Theorem Provers)中一阶逻辑格式的定理,并对MCDM_V和MCDM_E测试了2022年CADE(Conference on Automated Deduction)竞赛例(一阶逻辑组).实验表明:MCDM_CSE比CSE 1.5多证明了151个定理(来自TPTP),并且能够证明Vampire 4.7无法证明的5个定理、E 2.6无法证明的41个定理以及Prover9无法证明的293个定理;在更短的平均时间内,MCDM_V比Vampire 4.7多证明了6个定理(来自CADE 2022),MCDM_E比E 2.6多证明了8个定理.

基于有限谓词追踪的民机系统需求一致性检查方法

针对民机安全关键系统在正向研发过程中,系统级需求的正确性难以在设计早期全部完成确认的问题,提出一种基于有限谓词追踪的功能需求一致性检查体系。首先,引入一阶逻辑中的谓词追踪,建立系统内部功能需求与交互功能需求形式化规约方法。其次,针对单条、多条需求内容正确性以及需求关系一致性,构建需求一致性检查形式化规约,开展需求自冲突、集冲突与需求关系一致性检验,并生成可解释的检查反例进行需求迭代。最后,以机载平视显示(head-up display,HUD)系统飞行信息符号生成与显示功能为例,验证该方法的正确性与有效性。研究结果表明,基于有限谓词追踪的功能需求一致性检查方法能够提高需求一致性检查效率、降低研发成本,为民机系统级需求确认提供支持。

一种基于子句稳定度的多元动态演绎算法及应用

一阶逻辑自动定理证明是人工智能领域的核心基础。启发式策略在提升一阶逻辑自动定理证明器方面备受关注,其中根据子句属性选择较优子句参与演绎为重要的研究内容。基于矛盾体分离规则,将子句中的文字分为构建标准矛盾体的文字和构建矛盾体分离式的文字,通过分析变元项、函数项、基项之间的联系与差异,本文提出一种基于稳定度的子句评估方法,其核心思想是通过所含项的组成部分度量子句参与演绎的稳定程度;同时提出一种基于子句稳定度的多元动态演绎算法(clause stability algorithm,CFA),旨在搜索当前演绎过程中的较优路径;将提出的CFA算法应用于国际著名证明器Prover9(CFA_P证明器)和国际顶尖证明器Eprover2.6(CFA_E证明器),使用CFA_P和CFA_E对国际CASC-26 FOF组竞赛例进行测试,相比原始Prover9和原始Eprover2.6,CFA_P多证明119个定理、CFA_E多证明11个定理;在证明相同定理总数的情况下,CFA_P缩短了证明时间14.76 s、CFA_E则缩短了2.54 s;针对Eprover2.6未证明的94个定理进行单独测试,CFA_E能证明27个定理,占定理总数的28.7%。实验表明,CFA算法是有效的,其在优化演绎路径方面具有良好作用,能提高一阶逻辑自动定理证明器的性能。

矛盾体分离单元结果演绎方法及应用

一阶逻辑自动定理证明是人工智能领域重要的研究内容。为提高单元结果归结演绎效率,提出了一种新的基于多元、动态、协同的单元结果演绎方法,称为矛盾体分离单元结果演绎方法,并详细地给出了其演绎定义、演绎方法、演绎的优势分析及算法实现;提出的演绎方法允许多个子句同时参与演绎,且允许多个非单元子句参与1次单元结果演绎,能较好地处理长子句;提出的演绎算法能使用策略选定较优的子句和动态设定变元合一的复杂度,并通过回溯机制优化搜索的演绎路径。以近2年国际一阶逻辑自动定理证明器竞赛例(分别为500个)和TPTP问题库中难度系数为1的问题作为测试对象,加入了矛盾体分离单元结果演绎算法的Eprover和原始Eprover相比分别多证明了10个定理,分别能证明Eprover无法证明的17个定理和13个定理,能证明出9个其他所有证明器都无法证明难度系数为1的定理。实验结果表明,提出的矛盾体分离单元结果演绎方法能有效提高一阶逻辑自动定理证明的效率。

一阶逻辑定理证明器中的无效子句删除策略

在一阶逻辑定理证明器中,子句预处理是不可或缺的步骤,而子句的消去规则是预处理中极其重要的部分。传统的基于纯文字规则的子句消去方法在理论上存在子句删除过多的问题,在算法实现上又存在子句删除不充分的情况。为了提高子句删除的精确率,在理论上,基于纯文字规则对子句进行再分类。第一类称为无效子句,该类子句不能通过等词替换与某个子句形成互补对,此类子句应完全删除;第二类为相对无效子句,该类子句无法与当前子句集中的子句形成互补对,但能进行等词替换,此类子句应在参与演绎后综合考虑是否删除。在算法实现中,考虑到子句的消去应是动态的过程,当前消去的子句会影响已判断的子句的无效性,提出一种用于判定子句无效性的递归遍历算法。将上述子句约简规则应用于证明器CSE1.5(Contradiction Separation Extension 1.5)中,以2019—2022的CADE(Conference on Automated DEduction)自动定理证明(ATP)系统竞赛中一阶逻辑问题组为测试对象。在300 s内,应用所提算法的CSE1.5_IC比原始CSE1.5总共多证明了27个问题。在两个版本证明器共同证明的所有FNE(FOF theorems without Equality)测试例中,CSE1.5_IC比CSE1.5平均每个问题多约简了28个子句,平均求解时间减少了7.07 s。实验结果表明,所提无效子句约简算法是一种有效的预处理方式,能够提高一阶逻辑子句集的约简精确率,同时能够提高自动定理证明器的证明能力和缩短证明时间。

策略动态组合优化多元演绎算法及应用

一阶逻辑自动定理证明是人工智能领域重要的研究分支,其中子句选择策略对于提升定理证明能力具有重要作用。多元矛盾体分离演绎具有许多良好的演绎特性。为更好地指导多元演绎中的子句选择,提出了一种策略动态组合优化多元演绎方法,通过将子句文字数大小和函数项深度进行动态组合并迭代优化,在充分发掘现有多元演绎启发式策略的同时,提升策略应对不同问题的自适应性,实现多元演绎中的子句高效选择。基于该方法给出了相应的算法实现,根据不同问题的演绎过程动态调整子句的选择策略,提升了多元演绎的定理证明能力。同时,将该算法应用于国际先进的证明器Eprover 2.6,形成了改进的证明器SDCO_E,进一步通过2组实验评估SDCO_E的性能。实验1用2021—2023年国际一阶逻辑自动定理证明器竞赛组的共1500个问题进行测试,结果表明,SDCO_E比Eprover 2.6多证明了35个问题,证明定理总数增加了3.06%;实验2用TPTP库中难度系数为1的问题进行测试,结果表明,SDCO_E能证明其他证明器无法证明的6个数论与集合论领域的问题。实验结果表明,策略动态组合优化多元演绎算法能有效应用于一阶逻辑自动定理证明。

面向前提选择的新型图约简表示与图神经网络模型

自动定理证明器在证明问题时其搜索空间通常会呈现爆炸式增长,前提选择为该问题提供了新的解决思路。针对现有前提选择方法中逻辑公式图、图神经网络模型难以捕捉到公式图潜在信息的问题,提出了一种基于删除重复量词的简化逻辑公式图表示和具有注意力机制的项游走图神经网络模型,充分利用逻辑公式的语法和语义信息提高前提选择问题的分类精度。首先,将一阶逻辑猜想和前提公式转化为基于删除重复量词的简化一阶逻辑公式图;其次,利用消息传递图神经网络对节点和节点的项游走特征信息进行聚合和更新,随后使用注意力机制为图上的节点分配权重,进而调整图节点嵌入信息;最后,将前提图向量和猜想图向量拼接并输入二元分类器中实现前提分类。实验结果表明,所提方法在MPTP数据集和CNF数据集上的准确率分别达到了88.61%和84.74%,超越现有最优的前提选择方法。

可满足性模理论综述

可满足性模理论(SMT)是指判定一阶逻辑公式在特定背景理论下的可满足性问题。基于一阶逻辑的SMT相比SAT描述能力更强、抽象能力更高,能处理更加复杂的问题。SMT求解器在各个领域都有应用,已经成为重要的形式化验证引擎。目前,SMT已被广泛应用在人工智能、硬件RTL验证、自动化推理和软件工程等领域。根据近些年SMT的发展,首先阐述SMT基本知识和常见的背景理论;然后分析总结Eager方法、Lazy方法和DPLL(T)方法的实现流程,并进一步介绍主流求解器Z3、CVC5和MathSAT5的实现过程;接着介绍SMT的扩展问题#SMT、SMT应用在深度神经网络的SMTlayer方法和量子SMT求解器;最后对SMT的发展进行展望,并讨论其面临的挑战。

一阶逻辑中基于treelet图神经网络的前提选择

前提选择是解决自动定理证明器面对大规模问题时性能降低的有效方法。当前面向一阶逻辑中前提选择的主流图神经网络忽略了逻辑公式图内部的节点顺序信息。针对此问题,将一种面向高阶逻辑公式的保序方法拓展到一阶逻辑中,并提出了一种基于treelet的图神经网络模型。该模型在信息聚合时一部分聚合中心节点的父、子节点信息,另一部分聚合节点顺序信息。实验分析表明:基于treelet的图神经网络模型在前提选择任务中比最优的主流图神经网络模型的分类准确率提高了约2%。

基于一阶谓词逻辑的结构设计规范表示方法

目前,基于BIM模型的合规性审查采用人工方式,工作量繁重且自动化程度低,开展自动合规性审查研究具有重要意义。在结构设计领域能够有效支撑规范知识表示与推理并支持设计审查自动化的设计规范表达方法有待开发。基于一阶谓词逻辑,通过转译《混凝土结构设计规范》中的设计条款,提出一种结构设计规范规则表达和推理方法。该方法可实现将半结构化设计规范条款转换为结构化知识并支持灵活查询与推理,通过“谓词定义”和“函数定义”转译设计规范中语言类、表格类和计算公式类设计条款,提出两种规范条款谓词定义方式。对于语言模糊类、表后注释类和条款补充类的设计条款给出转译解决方案。提出的方法有效地解决了传统一阶谓词对于结构设计条款表示不充分和不精确的问题,进而为设计规范的计算机表达提供一种参考方法。

On decidability and model checking for a first order modal logic for value-passing processes

A semantic interpretation of a first order extension of Hennessy-Milner logic for value-passing processes, named HML(FO), is presented. The semantics is based on symbolic transition graphs with assignment. It is shown that the satisfiability of the two-variable sub-logic HML(FO2) of HML(FO) is decidable, and the complexity discussed. Finally, a decision procedure for model checking the value-passing processes with respect to HML(FO2) is obtained.

The Expressibility of First Order Dynamic Logic

This paper resolved an open problem proposed by A .P. Stolboushkin and M .A. Taitslin. We studied the expressibility of first order dynamic logic, and constructed infinite recursive program classes K_1 , K_2, …, RG K_1 K_2 … RF, such that L (RG)<L (K_1)<L (K_2) < … < L (RF), where RG, RF are regular program class and finitely generated recursively enumerable program class respectively, and L (K) is the first order dynamic logic of program class K.

COMBINATORY LOGIC AS THE FIRST-ORDER MATHEMATICAL THEORY

I. INTRODUCTION The exploration for a unified basis of the combinatory logic and the predicate calculus will promote laying a strict and thorough mathematical foundation of the programming language possessing itself of the functional and logic paradigms. The purpose of this note, proceeding from the algebraic oersoective, is to formulize the first-order mathematical

使用本体和SWRL验证作战计划的方法

计划验证是计划编制过程的重要环节。从知识管理的角度,在已有计划表示和计划推理相关研究的基础上,提出了一种基于本体和规则的计划验证方法框架,通过对计划知识进行基于本体的表示、基于描述逻辑、一阶谓词逻辑的规则知识抽取和计划推理,以实现对计划的验证。并以某排雷作战计划的验证为例进行了实验。实验表明,该方法实现了对专家知识的扩展,提高了作战计划正确性检验的效率。

不同逻辑间翻译的逻辑性质

如果考虑逻辑间模型的翻译并且一个逻辑的模型类被翻译为另一个逻辑的模型类的真子类,那么可靠的(the soundness)和完备的(the completeness)翻译可以将不可满足的公式翻译为可满足的公式.针对上述问题,该文提出了语义忠实(the faithfulness)和语义满(the fullness)两条逻辑性质来确保可满足的公式翻译为可满足的公式,不可满足公式翻译为不可满足公式.该文例证了二阶逻辑在标准语义下到一阶逻辑的翻译是语义忠实的但不是语义满的,在Henkin语义下是语义忠实的和语义满的.

统计关系学习模型Markov逻辑网综述

统计关系学习是人工智能研究的热点,在生物信息学、地理信息系统和自然语言理解等领域有着重要应用,Markov逻辑网是将Markov网与一阶逻辑相结合的一种全新的统计关系学习模型。介绍了Markov逻辑网的理论模型和学习方法,并探讨了目前存在的问题和研究方向。

基于本体论的电子商务知识描述语言

应用本体论对电子商务知识建模 ,提出电子商务知识描述的分层框架 ,并结合描述逻辑、框架系统设计面向电子商务的知识描述语言 (KDL) .介绍了KDL的语法 ,从一阶逻辑的角度分析KDL的语义特征 ,提供KDL描述到一阶逻辑表达式的映射方法 .最后 ,通过实例证明KDL具有规范的语法、精确的语义和较强的逻辑推理能力 .

基于深度学习框架的隐藏主题变量图模型

隐藏主题变量图模型是一种用节点表示潜在主题或者潜在主题变化的概率图模型.针对当前隐藏主题变量图模型只能提取单层主题节点的缺陷,提出一种基于深度学习框架的提取多层主题节点的概率图模型.该模型在隐藏主题变量图模型的底层增加预处理结构层,即引入自组织映射层,可以有效地提取不同层次的主题状态.另外,隐藏主题变量图模型使用了隐马尔可夫网络和条件随机场的相结合的模型.针对条件随机场,提出了一阶逻辑子句定义的特征函数.弥补了长距离依存特性的缺失.在此基础上提出了一种分层次提取主题状态的新深度学习算法.在国际通用的亚马逊情感分析数据、Tripadvisor情感分析数据上的实验表明,新算法可以提升情感分析的准确率.同时实验结果也表明,提取多层主题状态可以更好地挖掘宏观主题分布信息和评论的局部主题信息.

格值一阶逻辑系统LF(X)中带广义量词的α-归结原理

讨论格值一阶逻辑系统LF(X)中带广义量词的α-归结,证明了带广义量词的Herbrand-定理,为格值一阶逻辑系统中带广义量词的不确定性自动推理作了理论的准备。

格值一阶逻辑系统的α广义归结原理

在基于格蕴涵代数的格值逻辑系统框架下,笔者扩展了基于格值逻辑系统的α归结原理,将广义子句集上的归结扩展到一般广义子句集上,提出了基于格值一阶逻辑系统LF(X)的α广义归结原理,建立了格值一阶逻辑系统中α广义归结原理的可靠性定理.通过给出的提升引理,证明了该原理的弱完备性定理.这将为建立基于格值逻辑系统的广义归结方法提供新的自动推理技术.