ON THE CONSISTENCY OF DEFEASIBLE DATABASES

We propose a norm of consistency for a mixed set of defeasible and strict sentences which, guided by a probabilistic interpretation of these sentences, establishes a clear distinction between exceptions, ambiguities and outright contradictions. A notion of entailment is then defined which represents a minimal core of beliefs that must follow from the database if one is committed to avoid inconsistencies. The paper establishes necessary and sufficient conditions for consistency, and provides a simple decision procedure for testing the consistency of a database or whether a given sentence is entailed by the database. It is also shown that if all sentences are of Horn type, consistency and entailment can be tested in polynomial time. Finally, we discuss procedures for reasoning with inconsistent databases and identifying sentences directly responsible for the inconsistency.