多元协同演绎在一阶逻辑ATP中的应用

Application of Multi-Clause Synergized Deduction in First-Order Logic Automated Theorem Proving

一阶逻辑是数理逻辑中重要的分支,对其逻辑公式的自动推理是人工智能领域重要的研究热点之一.目前一阶逻辑自动定理证明大多采用二元归结方法,每次只有2个子句进行归结,只消去1组互补对,导致演绎归结式文字数较多,影响了演绎效率.为此,基于矛盾体分离规则提出了一种多元协同演绎算法,该算法每次允许多个子句进行协同演绎,消去多组互补对,从而演绎分离式文字数较少且可控,能有效提高推理能力;并且,该算法通过有效演绎权重和无效演绎权重调整子句演绎顺序,利用回溯机制搜索较优路径,有效规划演绎路径.将该算法应用于国际顶尖证明器Eprover 2.1,以CADE2017竞赛例(FOF组)为测试对象,对加入多元协同演绎算法的Eprover 2.1证明器进行试验.试验结果表明其能力超过了Eprover 2.1:多证明定理8个;能证明Eprover 2.1未证明定理31个,占未证明总数的28.2%.

First-order logic is an important branch in mathematical logic,and automated reasoning of its logical formula is one of the important research hotspots in the field of artificial intelligence. Most of the state of the art first-order logic automated theorem proving systems adopt binary resolution method. There are only two clauses involved,and therefore only a complementary pair of literals are eliminated during each resolution step. As a consequence,the resulted clause has many literals,which affects the deduction efficiency. In this paper,a multiclause synergized deduction algorithm is proposed based on contradiction separation rule. This algorithm allows multiple clauses used in deduction,and is able to eliminate more than one complementary pairs. The clause of contradiction separation is controllable and usually has less literals,which can effectively improve the inference ability. This multi-clause synergized algorithm adjusts the deduction order of clauses according to two kinds of weights,effective deduction weight and ineffective deduction weight. Backtracking mechanism is used to search for an optimal path,and effectively plan the deduction path. The algorithm is applied to the international top prover-Eprover 2.1,and Conference on Automated Deduction 2017 competition theorems(FOF division) are set as the test object. Eprover 2.1 with multi-clause synergized deduction algorithm outperformed Eprover 2.1 and solved 8 theorems more than Eprover 2.1. It also solved 31 theorems out of the 110 theorems unsolved by Eprover 2.1,accounting for 28.2% of the total.