Using Theory Resolution to Simplify Interpreted Formulae

Abstract

Loveland & Shostak (1980) gave an algorithm for converting a decision procedure for ground formulae in a first-order theory to a simplifier for such formulae. The algorithm is supposed to produce a simplest clause set among all formulae built from atoms of the original formula. In this paper it is shown that this method does not meet this requirement. Furthermore we show that theory resolution can be used to extend Quine’s method to an algorithm that really accomplishes the task of simplifying interpreted formulae.