一种基于矛盾体分离演绎的一阶逻辑自动定理证明器研究

来源 :西南交通大学 | 被引量 : 0次 | 上传用户:guoguangyun_09
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
自动推理是人工智能重要的组成部分,主要包括命题逻辑求解和一阶逻辑定理证明。一阶逻辑系统相比命题逻辑系统具有更丰富的表达能力,许多的现实问题都可用一阶逻辑表示。因此,对于一阶逻辑自动定理证明器的研究具有重要的学术价值和广泛的应用前景。目前一阶逻辑自动定理证明器普遍采用浸透算法演绎框架和二元归结方法。浸透算法是一种局部的演绎框架,其子句的选择效率对于启发式策略的要求非常高。二元归结方法每次有且只有2个子句进行归结,只消去一组互补对文字,导致归结式文字数较多,其演绎机制存在潜在的提升空间。矛盾体分离规则是徐扬教授提出的一种多元演绎方法,该方法突破了传统二元归结方法每次限定只有2个子句参与演绎,每次只消去1组互补对文字的限制,具有很多优良的演绎特性。本文重点研究了基于矛盾体分离理论的一阶逻辑自动定理证明器的各个组成部分、系统构建、演绎过程验证和实验评估,设计实现了基于矛盾体分离演绎的一阶逻辑自动定理证明器、基于矛盾体分离演绎的一阶逻辑自动定理证明融合系统、基于矛盾体分离演绎的一阶逻辑自动定理证明验证检查工具,包含了用于一阶逻辑自动定理证明的整个体系。在矛盾体分离理论方面,提出了一种矛盾体分离演绎子句约简规则,能通过分析演绎特点高效地对子句进行约简,并证明了方法的可靠性。提出了几种矛盾体分离演绎方法,缩减了矛盾体分离演绎的路径搜索空间。在一阶逻辑子句集预处理方法上,针对当前一阶逻辑自动定理证明器中的预处理技术采用基于符号相关性的方法,提出了一种基于刻画文字间演绎距离的子句集预处理方法,能有效地对子句集进行约简。将该方法应用于一阶逻辑自动定理证明器Vampire(国际证明器竞赛排名第一)中,一定程度上提高了其定理证明的能力。研究了基于矛盾体分离演绎的启发式策略,通过分析矛盾体分离演绎过程中的路径搜索决策,提出了子句选择策略、文字选择策略、矛盾体分离式评估策略、矛盾体分离式演绎控制策略,有效地优化了矛盾体分离演绎路径的搜索。基于不同的路径搜索方案,提出了3种有效的矛盾体分离演绎算法,分别称为基于较优子句的矛盾体分离演绎算法、基于优化演绎路径的矛盾体分离演绎算法,基于充分使用子句的矛盾体分离演绎算法。在演绎过程中能通过回溯机制搜索较优的路径,从而提高了路径搜索的效率。在定理证明过程中,提出了一种基于起步子句迭代演绎的路径搜索算法,有效地规划了矛盾体分离演绎的搜索路径,且能提升子句参与矛盾体分离演绎的充分性。设计和实现了基于矛盾体分离演绎的一阶逻辑自动定理证明器CSE,并正式发布3个符合国际标准的版本(CSE 1.0、CSE 1.1和CSE 1.2),并参加了近2年的国际一阶逻辑自动定理证明竞赛,其性能都超过了知名证明器Prover9。CSE证明器可用于对一阶逻辑定理进行自动证明,支持命令行运行方式和界面运行方式,支持策略的多种使用方法。以来自TPTP中的定理作为测试例,CSE证明器超过了许多知名的一阶逻辑自动定理证明器,能证明一些其它证明器无法证明的定理。研究了CSE与其它证明器的融合方法,提出了2种融合方法用于不同难度系数的一阶逻辑定理判定。选取了一阶逻辑自动定理证明器Vampire(国际证明器竞赛排名第一)和Eprover(国际证明器竞赛排名第二)进行融合,设计实现了2套融合系统CSE_V和CSE_E,其中CSE_E在参与的2018年国际一阶逻辑自动定理证明器竞赛中获得了第二名(标准一阶逻辑问题组)。支持不可满足问题和可满足问题判定。以一阶逻辑自动定理证明器国际竞赛例进行测试评估,CSE_V和CSE_E定理证明能力都超过了融合的证明器本身(Vampire、Eprover)。此外,CSE融合系统还证明了一批Rating等于1的定理。研究了CSE证明器和CSE融合系统的演绎过程验证方法,设计实现了2套系统的演绎过程验证检查工具,有效地保障了演绎的正确性。
其他文献
随着科技的快速发展,高维数据广泛地出现在众多科学领域当中,例如基因工程、图像处理、基因芯片、蛋白质工程和金融领域等,而且高维数据收集也越来越方便。作为处理高维数据
当今世界越来越成为你中有我、我中有你的命运共同体。党的十八大以来,习近平总书记立足携手构建人类命运共同体的战略高度,强调要不断加强中外文明交流互鉴,大力推动教育对
特里·伊格尔顿(Terry Eagleton)是英国著名的马克思主义文学和文化理论家,他的文化政治批评是20世纪马克思主义文学和文化理论最重要的贡献之一,国内外的伊格尔顿研究因此主
多元统计分析(Multivariate statistical analysis,MSA)是农学、医学、工程学、气象学、地质学、心理学等众多科学的问题的基本研究办法之一,在生产以及实际生活中有重要的应
目的:肥胖可引起胰岛素抵抗、肝脏异位脂质沉积等代谢紊乱。巨噬细胞介导的慢性低烈度炎症反应在肥胖相关性代谢紊乱中起关键作用,但具体的调控机制仍不完全清楚。穹窿主体蛋
近年来具有脉冲效应的确定性传染病模型得到了广泛的研究并取得了深入的成果.脉冲传染病模型的研究为人们理解疾病在脉冲影响下的动力学行为、制定和检验传染病的防控策略提
医学是一门人学,是关系人类幸福的事业,对人的全面关怀为医学应有之意。医学人文素养是医学的灵魂,反映了人类对生命的根本态度,医师人文素养的高低直接影响民众的幸福感、获
新中国成立70年来,中国共产党带领占世界五分之一人口的中国人民,实现了从“站起来”“富起来”到“强起来”的飞跃,创造了人类历史上前所未有的发展奇迹。站在新时代新的历
随着人类对建筑美观和功能的需求,高层建筑的表面普遍采用了包括遮阴条、阳台、竖框及其它装饰条在内的各种粗糙条。很明显,这些粗糙条会极大地影响建筑表面的风压分布,从而
随着人类社会发展,重金属离子污染成为严重威胁人类健康的重要因素,通过食品进入人体是人体内重金属的主要来源之一,因此对食品中重金属离子的检测尤为重要。然而当前的重金