Eliminating Redundant Search Space on Backtracking for Forward Chaining Theorem Proving

摘要

This paper introduces some improvements on the intelligent backtracking strategy for forward chaining theorem proving. How to decide a minimal useful consequent atom set for a refutation derived at a node in a proof tree is discussed. In most cases, an unnecessary non-Horn clause used for forward chaining will be split only once. The increase of the search space by invoking unnecessary forward chaining clauses will be nearly linear, not exponential anymore. In this paper, the principle of the proposed method and its correctness are introduced. Moreover, some examples are provided to show that the proposed approach is powerful for forward chaining theorem proving.