Towards abductive reasoning in first-order logic

Abstract

Abductive problems have been widely studied in propositional logic. First order abduction, however, has been viewed as intractable, for the undecidability of logical consequence. In this paper, we propose a notion of abductive problem, N-abductive problem, which is relative to the cardinality of the minimal model satisfying the given theory. We use a notion of restricted satisfaction, also relative to a domain cardinality. Finally, we propose an effective procedure for the searching of abductive solutions, by means of a modification of Beth's tableaux.