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 one place predicates. Literals built from one place 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 structure for sorted unification. Sorted unification exploits the sort restrictions of variables. As the occurrence of sort literals is not restricted, it might be necessary to add additional literals to resolvents and factors and to dynamically change the set of positive sort literals used by sorted unification during the deduction process. The calculus I propose thus extends the standard resolution method by sorted unification, residue literals and a dynamic processing of the sort 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.