On the Use of Subgoal Clauses in Bottom-up and Top-down Calculi

Abstract

The use of lemmas is a major control tool for automated theorem proving. Many approaches for top-down or bottom-up theorem proving employ lemmas for improving the proof search. Commonly the lemmas used can be derived in a bottom-up manner using merely the given axioms. That is, top-down lemmas which represent decompositions of original proof goals did not receive much attention. We propose to systematically generate and use such goal decompositions. We introduce a notion of top-down lemmas, so-called subgoal clauses, and examine their potential to reduce proof lengths and searches in top-down and bottom-up theorem proving. Furthermore, we develop some heuristics so as to make the use of subgoal clauses efficient in practice. A case study conducted in TPTP domains with the state-of-the-art provers SPASS and SETHEO demonstrates the strength of our approach.