T-theorem proving. I

Abstract

In this paper we present a theoretical basis justifying the incorporation of decidability results for a first-order theory T into an automated theorem prover for T. We state rules which extend resolution using decidability results relative to T in both the ground and the non-ground case, and prove the correctness and completeness of these rules. This is done by considering the ground case of such theories first, and then by applying a straightforward lifting argument. Examples are given illustrating the inference speed-ups which can be obtained by considering decision procedures with resolution-based inference.