Eliminating Redundant Search Space on Backtracking for Forward Chaining Theorem Proving

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

An Improvement of Herbrand's Theorem and Its Application to Model Generation Theorem Proving

This paper presents an improvement of Herbrand's theorem.We propose a method for specifying a subuniverse of the Herbrand universe of a clause set S for each argument of predicate symbols and function symbols in S.We prove that a clause set S is unsatisfiable if and only if there is a finite unsatisfiable set of ground instances of clauses of S that are derived by only instantiating each variable,which appears as an argument of predicate symbols or function symbols,in S over its corresponding argument's sub-universe of the Herbrand universe of S.Because such sub-universes are usually smaller(sometimes considerably)than the Herbrand universe of S,the number of ground instances may decrease considerably in many cases.We present an algorithm for automatically deriving the sub-universes for arguments in a given clause set,and show the correctness of our improvement.Moreover,we introduce an application of our approach to model generation theorem proving for non-range-restricted problems,show the range-restriction transformation algorithm based on our improvement and provide examples on benchmark problems to demonstrate the power of our approach.