Extending the Resolution Method with Sorts

Abstract

In this paper I extend the standard first-order resolution method with special reasoning mechanisms for sorts. Sorts are unary predicates. Literals built from unary predicates are called sort literals. Negative sort literals can be compiled into restrictions of the relevant variables to sorts or can be deleted if they fulfill special conditions. Positive sort literals define the sort theory. Sorted unification exploits the sort restrictions of variables with respect to the sort theory. As occurrences of sort literals are not restricted, it may be necessary to add additional literals to resolvents and factors and to dynamically change the sort theory used by sorted unification during the deduction process. The calculus I propose thus extends the standard resolution method with sorted unification residue literals and a dynamic processing of thsort information. I show that this calculus generalizes and improves existing approaches to sorted reasoning. Finally, I give some applications to automated theorem proving and abduction.