• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

Application of multi-clause dynamic deduction in Prover9

CAO Feng1,3,XU Yang2,3,WU Guan-feng1,3,ZHONG Jian1,3   

  1. (1.School of Information Science and Technology,Southwest Jiaotong University,Chengdu 610031;
    2.School of Mathematics,Southwest Jiaotong University,Chengdu 610031;
    3.National-Local Joint Engineering Laboratory of System Credibility Automatic Verification,Chengdu 610031,China)
  • Received:2018-10-08 Revised:2019-01-25 Online:2019-09-25 Published:2019-09-25

Abstract:

Prover9 only adopts the binary resolution method, which is a static and partial inference rule. Based on the contradiction separation rule, we propose a multi-clause dynamic deduction algorithm. This algorithm uses a holistic deduction framework, plans the deduction path according to clause deduction weight and literal deduction weight, and employs the backtracking mechanism to search for the optimal path. The Conference on Automated Deduction 2017 competition theorems (First-Order Form division) are used as the test object, and the theorems solved by the Prover9 with the multi-clause dynamic deduction algorithm  is increased by 40.7%, and the average time used is reduced by 7.46 seconds. Experiments show that the proposed algorithm is an effective inference method, and can improve the ability of first-order logic automated theorem prover.
 

Key words: binary resolution, contradiction separation, multi-clause dynamic deduction, deduction weight