When Logical Conclusions Do Not Hold True. Inference rules are called nonmonotonic when they allow intelligent systems "to augment their beliefs by new ones that do not logically follow from their explicit ones" and this or another inference may have to be retracted.
Ordinary inference rules are monotonic "because the set of theorems derivable from premises is not reduced by adding to the premises."
– from Logical foundations of artificial intelligence by MR Genesereth and NJ Nilsson (1987)
Clearly, the second approach is more cautious. Intuitively, it demands that there is a specific argument for τ that is contained in each rational stance a reasoner can take given Γ, DRules, and SRules. The first option doesn't bind the acceptability of τ to a specific argument: it is sufficient if according to each rational stance there is some argument for τ. In Default Logic, the main representational tool is that of a default rule, or simply a default.
We give an overview of the multifaceted relationship between nonmonotonic logics and preferences. We discuss how the nonmonotonicity of reasoning itself is closely tied to preferences reasoners have on models of the world or, as we often say here, possible belief sets. 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. We discuss how such conflicts can be resolved based on implicit specificity or on explicit rankings of defaults. 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.
Given the variety of underlying systems, assumptions, motivations, and intuitions, it is difficult to compare or relate one approach with another. Here we present an overview and classification for approaches to dealing with preference. A set of criteria for classifying approaches is given, followed by a set of desiderata that an approach might be expected to satisfy. A comprehensive set of approaches is subsequently given and classified with respect to these sets of underlying principles.
We then analyze the nonmonotonic and semantic properties of the new notions of entailment. In particular, we show that they satisfy the rationality postulates of System P and the property of Rational Monotonicity. Moreover, we show that model-theoretic probabilistic entailment is stronger than the new notion of lexicographic entailment, which in turn is stronger than the new notion of entailment in System Z. As an important feature of the new notions of entailment in System Z and lexicographic entailment, we show that they coincide with modeltheoretic probabilistic entailment whenever there are no local inconsistencies. We also show that the new notions of entailment in System Z and lexicographic entailment are proper generalizations of their classical counterparts. Finally, we present algorithms for reasoning under the new formalisms, and we give a precise picture of its computational complexity.