Selecting extended logic programming with the answer-set semantics as a "generic" nonmonotonic logic, we show how that logic defines preferred belief sets and how preferred belief sets allow us to represent and interpret normative statements. Conflicts among program rules (more generally, defaults) give rise to alternative preferred belief sets. Finally, we comment on formalisms which explicitly represent preferences on properties of belief sets. Such formalisms either build preference information directly into rules and modify the semantics of the logic appropriately, or specify preferences on belief sets independently of the mechanism to define them.
We characterize the complexity of several typical problems in propositional default logics. In particular, we examine the complexity of extension membership, extension existence, and extension entailment problems. We show that the extension existence problem is X; complete, even for semi-normal theories, and that the extension membership and entailment problems are X; complete and II; complete respectively, even when restricted to normal default theories. These results contribute to our understanding of the computational relationship between propositional default logics and other formalisms for nonmonotonic reasoning, e.g., autoepistemic logic and McDermott and Doyle's NML, as well as their relationship to problems outside the realm of nonmonotonic reasoning.
An approach to nonmonotonic inference, based on preference orderings between possible worlds or states of affairs, is presented. We begin with an extant weak theory of default conditionals; using this theory, orderings on worlds are derived. The idea is that if a conditional such as "birds fly" is true then, all other things being equal, worlds in which birds fly are preferred over those where they don't. In this case, a red bird would fly by virtue of redbird-worlds being among the least exceptional worlds in which birds fly. In this approach, irrelevant properties are correctly handled, as is specificity, reasoning within exceptional circumstances, and inheritance reasoning. A sound proof-theoretic characterisation is also given. Lastly, the approach is shown to subsume that of conditional entailment.