Logical considerations on default semantics

Abstract

We consider a reinterpretation of the rules of default logic. We make Reiter’s default rules into a constructive method of building models, not theories. To allow reasoning in first order systems, we equip standard first-order logic with a (new) Kleene 3-valued partial model semantics. Then, using our methodology, we add defaults to this semantic system. The result is that our logic is an ordinary monotonic one, but its semantics is now nonmonotonic. Reiter’s extensions now appear in the semantics, not in the syntax. As an application, we show that this semantics gives a partial solution to the conceptual problems with open defaults pointed out by Lifschitz [16], and Baader and Hollunder [2]. The solution is not complete, chiefly because in making the defaults model-theoretic, we can only add conjunctive information to our models. This is in contrast to default theories, where extensions can contain disjunctive formulas, and therefore disjunctive information. Our proposal to treat the problem of open defaults uses a semantic notion of nonmonotonic entailment for our logic, deriving from the idea of “only knowing”. Our notion is “only having information” given by a formula. We discuss the differences between this and “minimal-knowledge” ideas. Finally, we consider the Kraus-Lehmann-Magidor [14] axioms for preferential consequence relations. We find that our consequence relation satisfies the most basic of the laws, and the Or law, but it does not satisfy the law of Cut, nor the law of Cautious Monotony. We give intuitive examples using our system, on the other hand, which on the surface seem to violate these laws, no matter how they are interpreted. We make some comparisons, using our examples, to probabilistic interpretations for which the laws are true, and we compare our models to the cumulative models of Kraus, Lehmann, and Magidor. We also show sufficient conditions for the laws to hold. These involve limiting the use of disjunction in our formulas in one way or another. We show how to make use of the theory of complete partially ordered sets, or domain theory. We can augment any Scott domain with a default set. We state a version of Reiter’s extension operator on arbitrary domains as well. This version makes clear the basic order-theoretic nature of Reiter’s definitions. A three-variable function is involved. Finding extensions corresponds to taking fixed points twice, with respect to two of these variables. In the special case of precondition-free defaults, a general relation on Scott domains induced from the set of defaults is shown to characterize extensions. We show how a general notion of domain theory, the logic induced from the Scott topology on a domain, guides us to a correct notion of “affirmable sentence” in a specific case such as our first-order systems. We also prove our consequence laws in such a way that they hold not only in first-order systems, but in any logic derived from the Scott topology on an arbitrary domain.