# Non-monotonic Logic

*First published Tue Dec 11, 2001; substantive revision Tue Dec 2, 2014*

The term “non-monotonic logic” (in short, NML) covers a family of
formal frameworks devised to capture and represent *defeasible
inference*, i.e., that kind of inference in which reasoners draw
conclusions tentatively, reserving the right to retract them in the
light of further information. Examples are numerous, reaching from
inductive generalizations to abduction to inferences on the basis of
expert opinion, etc. We find defeasible inferences in everyday
reasoning, in expert reasoning (e.g. medical diagnosis), and in
scientific reasoning.

Defeasible reasoning just like
deductive reasoning, can follow complex patterns. However, such
patterns are beyond reach for classical logic (CL), intuitionistic
logic (IL) or other logics that characterize deductive reasoning since
they—by their very nature—do not allow for a retraction
of inferences. The challenge tackled in the domain of NMLs is to
provide for defeasible reasoning forms what CL or IL provide for
mathematical reasoning: namely a *formally precise* account that
is *materially adequate*, where material adequacy concerns the
question of how broad a range of examples is captured by the
framework, and the extent to which the framework can do justice to our
intuitions on the subject (at least the most entrenched ones).

- 1. Dealing with the dynamics of defeasible reasoning
- 2. Dealing with conflicts
- 3. Non-monotonic formalisms
- 4. Non-monotonic logics and human reasoning
- 5. Conclusion
- Bibliography
- Academic Tools
- Other Internet Resources
- Related Entries

## 1. Dealing with the dynamics of defeasible reasoning

Defeasible reasoning is dynamic in that it allows for a retraction of inferences. Take, for instance, reasoning on the basis of normality or typicality assumptions. While we infer that Tweety flies on the basis of the information that Tweety is a bird and the background knowledge that birds usually fly, we have good reasons to retract this inference when learning that Tweety is a penguin or a kiwi.

Another example is abductive reasoning. Given the observation that the streets are wet we may infer the explanation that it has been raining recently. However, recalling that this very day the streets are cleaned and that the roof tops are dry, we will retract this inference.

As a last example take probabilistic reasoning where we infer
“*X* is a *B*” from “*X* is
an *A* and most *A*s are *B*s”. Clearly, we may
learn that *X* is an exceptional *A* with respect to being
a *B*.

Our previous examples are instances of *ampliative* reasoning. It
is based on inferences for which the truth of the premises does not
warrant the truth of the conclusion as in deductive reasoning, but for
which the conclusion nevertheless holds in most/typical/etc. cases in
which the premises hold.

Defeasible reasoning may also have a *corrective* character in
that the inferences are deductive or truth-preserving while
nevertheless being retractable. Suppose we reason classically on the
basis of a complex body of premises Γ (e.g., a mathematical or
scientific theory, or a code of law). If we do not know whether
Γ is consistent (i.e., whether a contradiction is derivable), we
may adopt a careful rationale for drawing inferences. Let us call a
formula φ in Γ free if it does not belong to a minimally
inconsistent subset of Γ (i.e., an inconsistent subset of
Γ which has no proper subset that is also inconsistent). We may
reason as follows: an inference in CL is retracted as soon as we find
out that it relies on premises that are not free. This way we only
accept consequences that are derivable on the basis of the consistent
part of our premise set. The resulting consequences are known as
the *free consequences*
(Benferhat et al. (1997)). For
instance, where *p*, *q*, *s*, *t* are logical
atoms and Γ = {*p* ∧ *q*, ¬*p*, *s*
∧ *t*}, the inference for *q* from *p ∧ q* will
be retracted since *p* ∧ *q* is not free in Γ,
while the inference to *s* from *s* ∧ *t* goes
through. In contrast to ampliative reasoning, each inference is in
accordance with CL and hence deductive. However, given an inconsistent
theory, not all deductive inferences will be accepted.

Most of scholarly attention has been paid to what has been called
the *synchronic* (Pollock (2008)) or
the *external dynamics* (Batens (2004))
of defeasible reasoning. For this, inferences are
retracted as a result of gaining new information. Formally this can be
expressed in terms of the consequence relation
of a logic
for defeasible reasoning. Consider the
following property that is characteristic of deductive reasoning and
holds, for instance, for the relation of logical consequence ⊨
of CL (see the entry on classical logic
for details on the relation ⊨):

**Monotony**: If Γ ϕ then Γ ∪ Γ′ ϕ.

Monotony states that if ϕ is a consequence of Γ then it is also a consequence of any set containing Γ as a subset. If we define a consequence function Cn(•) by Cn(Γ) = {ϕ ∣ Γ ϕ} we can equivalently express Monotony by:

- If ϕ ∈ Cn(Γ) then ϕ ∈ Cn(Γ ∪ Γ′).

In CL, Monotony follows immediately from the nature of the relation ⊨, for Γ ⊨ φ holds precisely when φ is true on every interpretation on which all sentences in Γ are true.

The import of monotony is that one cannot pre-empt conclusions by adding new premises. Clearly, most forms of defeasible reasoning are externally dynamic and hence most logics for defeasible reasoning violate Monotony: they have non-monotonic consequence functions. This feature is so central that the formal logical study of defeasible reasoning is often taken to be coextensive with the domain of NML where non-monotonicity is understood as a property of the consequence function of a logic.

It has been noted, that beside the external there is also
a *diachronic* (Pollock (2008))
or *internal* dynamics (Batens (2004)).
It is the result of retracting inferences without adding
new information in terms of new premises, but due to finding out more
about the given premises by means of further analyzing them.

Let us return to non-monotonicity as a property of the consequence function. Given that Monotony is abandoned in NMLs, we are naturally led to the question which formal properties are to replace Monotony. We state here two of the most central such properties considered in the literature:

**Cautious Monotony**: If Γ φ and Γ ψ, then Γ, φ ψ.**Rational Monotony**: If Γ ψ and it is not the case that Γ¬φ, then Γ, φ ψ.

Both Cautious Monotony and the stronger principle of Rational Monotony are special cases of Monotony, and are therefore not in the foreground as long as we restrict ourselves to the classical consequence relation ⊨ of CL.

Cautious Monotony is the converse of Cut:

**Cut**: If Γ φ and Γ, φ ψ then Γ ψ.

Cautious Montony (resp. Cut) states that adding a consequence φ to
the premise-set Γ does not lead to any *decrease*
(resp. *increase*) in inferential power. Taken together these
principles express that inference is a cumulative enterprise: we can
keep drawing consequences that can in turn be used as additional
premises, without affecting the set of
conclusions. In Gabbay (1985) it has been
shown that some basic and intuitive assumptions about non-monotonic
derivations give rise to consequence relations which satisfy Cautious
Monotony, Cut and Reflexivity (If φ ∈ Γ then Γ
φ.). Accordingly,
these properties are commonly taken to be central principles of
NML.^{[1]}

Rational Monotony states that no conclusions of Γ are lost when adding formulas φ to Γ that are not contradicted by Γ (i.e., it is not the case that Γ ¬φ). Rational Monotony is a more controversial property than Cautious Monotony. For instance, Stalnaker (1994) gave a counter-example to Rational Monotony (see the supplementary document) in view of which it is clear that in not all application contexts Rational Monotony is a desirable property of defeasible reasoning.

## 2. Dealing with conflicts

A separate issue from the formal properties of a non-monotonic
consequence relation, although one that is strictly intertwined with
it, is the issue of how *conflicts* between potential defeasible
conclusions are to be handled.

We can distinguish two types of conflict handling in defeasible reasoning both of which will be discussed in more detail below. On the one hand, we have conflict resolution principles such as the Specificity Principle or other measures of argument strength. On the other hand, we have reasoning types that deal in different ways with non-resolvable conflicts, most prominently the Credulous and the Skeptical reasoning types. In this section we still stay on an abstract level while concrete NMLs are discussed in the section Non-Monotonic Formalisms.

### 2.1 Conflict resolution

There are two different kinds of conflicts that can arise within a
given non-monotonic framework: (*i*) conflicts between defeasible
conclusions and “hard facts,” some of which possibly newly learned;
and (*ii*) conflicts between one potential defeasible conclusion
and another (many formalisms, for instance, provide some form of
defeasible inference rules, and such rules might have conflicting
conclusions). When a conflict (of either kind) arises, steps have to
be taken to preserve or restore consistency.

Conflicts of type (*i*) are to be resolved in favor of the hard
facts in the sense that the conflicting defeasible conclusion is to be
retracted. More interesting are mechanisms to resolve conflicts of
type (*ii*). In order to analyze these, we will make use of
schematic inference graphs (similar to the ones used
in Inheritance Networks, see below). For
instance, our previous example featuring the bird Tweety is
illustrated as follows:

We use the following conventions: double arrows signify deductive or strict (i.e., non-defeasible) inferences, single arrows signify defeasible inferences, and strikethrough single arrows signify that the negation of the pointed formula is defeasibly implied. So, we can read the diagram as follows: Penguins are birds (no exceptions); Birds usually fly; and Penguins usually don't fly.

We have a conflict between the following two arguments (where
arguments are sequences of inferences): *Penguin*
⇒ *Bird* → *flies* and *Penguin*
→ *not-flies*. Both arguments include a final defeasible
inference. What is important to notice is that a penguin is a specific
type of bird since *Penguin* ⇒ *Bird* (while
not *Bird* ⇒ *Penguin*). According to
the *Specificity Principle* an inference with a more specific
antecedent overrides a conflicting defeasible inference with a less
specific antecedent. Concerning the penguin Tweety we thus infer that
she doesn't fly on the basis of *Penguin* → *not-flies*
rather than that she flies on the basis of *Penguin*
⇒ *Bird* → *flies*.

Logicians distinguish between *strong* and *weak
specificity*: according to strong specificity *A*
↛ *C* overrides *A* ⇒ *B* → *C*;
according weak specificity *A* ↛ *C*
overrides *A* → *B* → *C*. Note that the
difference concerns the nature of the link between *A*
and *B*.

A preference for one defeasible inference *A* → *B*
over another conflicting one *C* → *D* may depend also
on other factors. For instance, in an epistemic context we may compare
the strengths of *A* → *B* and *C* → *D*
by appealing to the reliability of the source from which the
respective conditional knowledge stems. In the context of legal
reasoning we may have the principles *lex superior* resp. *lex
posterior*, according to which the higher ranked resp. the later
issued law dominates.

Given a way to compare the strength of defeasible inference steps by means of a preference relation ≺, there is still the question of how to compare the strength of conflicting sequences of inferences viz. arguments. We give some examples. For a systematic survey and classification of preference handling mechanisms in NML the interested reader is referred to Delgrande et al. (2004).

According to the *Weakest Link Principle*
(Pollock (1991)) an argument is preferred
over another conflicting argument if its weakest defeasible link is
stronger than the weakest defeasible link in the conflicting
argument. Take, for example, the situation in the following figure:

On the left we see an inference graph with two conflicting
arguments. On the right we see the preference ordering. The
argument *A* → *B* → *E* is stronger
than *C* → *D* ↛ *E* since for its weakest
link *D* ↛ *E* we have *D* ↛ *E*
≺ *A* → *B* and *D* ↛ *E*
≺ *B* → *E*.

Another approach to preferences is procedural. Roughly, it instructs
to always apply the rule with the highest priority first. (There may
be various such rules with highest priority, but for the sake of
simplicity we neglect this possibility in what follows.) Take the
following example that is frequently discussed in the literature. We
have the rules *A* → *B*, *A* ↛ *C*
and *B* → *C* where *A* → *B*
≺ *A* ↛ *C* ≺ *B* → *C* and
we take *A* to be given. We can apply *A* → *B*
and *A* ↛ *C*. Since *A* → *B*
≺ *A* ↛ *C* we apply *A* ↛ *C*
first and derive ¬*C*. Now only *A* → *B* is
applicable. So we derive *B*. Although the antecedent of *B*
→ *C* is already derived, we cannot apply this rule for the
sake of consistency. Brewka and Eiter (2000)
argue against the procedural approach and that it is more
intuitive to derive *B*
and *C*. Delgrande and Schaub (2000)
argue that the example presents an incoherent set of
rules. This is put in question in
Horty (2007)
where a consistent deontic reading in terms of conditional
imperatives is presented which also challenges the procedural approach
by favoring the conclusions *B* and *C*.

Ford (2004)
pointed out that the order of strict and defeasible links in arguments
matters. For instance, she argues that an argument of the
form *A* → *B* ⇒ *D* is stronger than an
argument of the form *A* ⇒ *C* ↛ *D*
(where *A* → *B* reads “Most *A*s are *B*s”
and *A* ⇒ *C* reads “All *A*s
are *C*s.”). The reason is that in the former case it is not
possible that no *A* is a *D* while in the second case it is
possible that no *A* is a not-*D*. This is illustrated in
the following figure:

The left diagram demonstrates that there are distributions such that
no *A*s are not-*D*s although *A* ⇒ *C*
and *C* ↛ *D* hold. The right diagram features a
distribution for *A* → *B* ⇒ *D*. Whenever
the extension of *A* is non-empty there will be *A*s that
are *D*s.

### 2.2 Reasoning with unresolved conflicts

We now discuss questions that arise in view of conflicts that are irresolvable since no available resolution principles applies. One can draw inferences either in a “cautious” or “bold” fashion (also known as “skeptical” or, respectively, “credulous”). These two options correspond to significantly different ways to construe a given body of defeasible knowledge, and yield different results as to what defeasible conclusions are warranted on the basis of such a knowledge base.

The difference between these basic attitudes comes to this. In the presence of potentially conflicting defeasible inferences (and in the absence of further considerations such as specificity — see above), the credulous reasoner always commits to as many defeasible conclusions as possible, subject to a consistency requirement, whereas the skeptical reasoner withholds assent from potentially conflicted defeasible conclusions.

A famous example from the literature, the so-called “Nixon diamond,” will help to make the distinction clear. Suppose our knowledge base contains (defeasible) information to the effect that a given individual, Nixon, is both a Quaker and a Republican. Quakers, by and large, are pacifists, whereas Republicans, by and large, are not. This is illustrated in the following figure:

The question is what defeasible conclusions are warranted on the basis of this body of knowledge, and in particular whether we should infer that Nixon is a pacifist or that he is not a pacifist.

Neither the skeptical nor the credulous reasoner have any logical grounds to prefer either conclusion (“Nixon is a pacifist”; “Nixon is not a pacifist”). While the credulous reasoner commits to both conclusions, the skeptical reasoner refrains from either.

A rationale behind the credulous reasoning type is to provide an overview of possible conclusions given the conflicting defeasible inferences in order to subsequently make a choice among them. This is especially interesting in practical reasoning contexts in which the choice determines a course of action and in which extra-logical considerations (based on preferences, values, etc.) further narrow down the choice.

In contrast, the rationale behind the skeptical reasoning type is to determine uncontested defeasible conclusions. The purpose may be of a more epistemological nature such as the updating of the agent's belief or knowledge base with the chosen conclusions.

### 2.3 Some advanced issues for skeptical reasoning

We now discuss some further issues that arise in the context of conflicting arguments. The first issue is illustrated in the following figure:

Consider the argument *Penguin* ⇒ *Bird* → *has
wings*. Since penguins do not fly, we know that penguins are
exceptional birds, at least with respect to the property of flying. A
very cautious reasoner may take this to be a reason to be skeptical
about attributing other typical properties of birds to penguins. NMLs
that do not allow to derive *has wings* are said to suffer from
the *Drowning Problem* or
to not satisfy the *Strong Independence* property.

The question whether the exceptional status of *Penguin* relative
to *flies* should spread also to other properties of *Bird*
may depend on specific relevance relations among these properties. For
instance, Koons (2014) proposes that causal
relations play a role: whereas *has strong forlimb muscles* is
causally related to *flies* and hence should not be attributed to
penguins, the situation is different with *is cold-blooded*.
Similarly, Pelletier and Elio (1994)
argue that explanatory relations play a significant role in
the way in which reasoners treat exceptional information in
nonmonotonic inference.

Another much discussed issue (e.g., Ginsberg (1994),
Makinson and Schlechta (1991),
Horty (2002)) concerns the
question whether a conclusion that is derivable via two conflicting
arguments should be derived. Such conclusions are called *Floating
Conclusions*. The following figure illustrates this with an
extended version of the Nixon Diamond.

The floating conclusion in question concerns *is political* which
is derivable via *Nixon* → *Quaker* → *Dove*
→ *is political* and via *Nixon*
→ *Republican* → *Hawk* → *is
political*. Both arguments are super-arguments of the
conflicting *Nixon* → *Quaker* → *Dove*
and *Nixon* → *Republican*
→ *Hawk*.^{[2]}
Horty (1994) argues that floating conclusions are acceptable in
reasoning contexts in which “the value of drawing conclusions is high
relative to the costs involved if some of those conclusions turn out
not to be correct” while they should be avoided “when the cost of
error rises” (p. 123).

We conclude our discussion with so-called *Zombie-Arguments*
(Makinson and Schlechta (1991),
Touretzky et al. (1991)).
Recall that a skeptical reasoner does not commit to a
conflicting argument.
Makinson and Schlechta (1991)
argue that super-arguments of such conflicted arguments
—although not acceptable— nevertheless still have the
power to undermine the commitment of a reasoner to an otherwise
unconflicted argument. We see an example in the following figure:

*F* is a consequence of the (unconflicted) argument *A*
→ *C* → *E* → *F*. It conflicts with the
zombie-argument *A* → *B* → *D*
↛ *F* which is a super-argument of the conflicted *A*
→ *B* → *D*. The name refers to undead beings
since an argument such as *A* → *B* → *D*
↛ *F* to which we have no commitment may still have the
power to influence our commitment to an otherwise unconflicted
argument such as *A* → *C* → *E*
→ *F*.

## 3. Non-monotonic formalisms

Pioneering work in the field of NMLs began with the realization that
in order to give a mathematically precise characterization of
defeasible reasoning CL is inadequate. Such a realization was
accompanied by the effort to reproduce the success of CL in the
representation of mathematical, or formal, reasoning. Among the
pioneers of the field in the late 1970's were J. McCarthy,
D. McDermott & J. Doyle, and R. Reiter
(see Ginsberg (1987) for a collection of
early papers in the field and Gabbay et al. (1994)
for a more recent collection of excellent survey
papers). In 1980, the *Artificial Intelligence Journal* published
an issue (vol. 13, 1980) dedicated to these new formalisms, an event
that has come to be regarded as the “coming of age” of NML.

In this section an overview will be provided on some important formalisms. Since the evolutionary tree of NMLs has grown extraordinarily rich, we will restrict the focus on presenting the basic ideas behind some of the most influential and well-known approaches.

### 3.1 The closed-world assumption

If one of the goals of non-monotonic logic is to provide a materially
adequate account of defeasible reasoning, it is important to rely on a
rich supply of examples to guide and hone intuitions. Database theory
was one of the earliest sources of such examples, especially as
regards the *closed world assumption*. Suppose a travel agent has
access to a flight database, and needs to answer a client's query
about the best way to get from Oshkosh to Minsk. The agents queries
the database and, not surprisingly, responds that there are no direct
flights. How does the travel agent know?

It is quite clear that, in a strong sense of “know,” the travel agent
does not *know* that there are no such flights. What is at work
here is a tacit assumption that the database is *complete*, and
that since the database does not list any direct flights between the
two cities, there are none. A useful way to look at this process is as
a kind of *minimization*, i.e., an attempt to minimize the
extension of a given predicate (“flight-between,” in this
case). Moreover, on pain of inconsistencies, such a minimization needs
to take place not with respect to what the database explicitly
contains but with respect to what it implies.

The idea of minimization is at the basis of one of the earliest
non-monotonic formalisms, McCarthy's *circumscription*
(McCarthy (1980)). Circumscription makes
explicit the intuition that, all other things being equal, extensions
of certain predicates should be *minimal*. Consider principles
such as “all normal birds fly”. Implicit in this principle is the idea
that specimens should not be considered to be abnormal unless there is
positive information to that effect. McCarthy's idea was to represent
this formally, using second-order logic (SOL). In SOL, in contrast to
first-order logic (FOL), one is allowed to explicitly quantify over
predicates, forming sentences such as
∃*P*∀*xPx* (“there is a universal predicate”)
or ∀*P*(*Pa* ≡ *Pb*) (“*a*
and *b* are indiscernible”).

In circumscription, given predicates *P* and *Q*, we
abbreviate ∀*x*(*Px* ⊃ *Qx*)
as *P*≤*Q*; similarly, we abbreviate *P*≤*Q*
∧ ¬*Q*≤*P*
as *P*<*Q*. If *A*(*P*) is a formula containing
occurrences of a predicate *P*, then the circumscription
of *P* in *A* is the second-order
sentence *A**(*P*):

A(P) ∧ ¬∃Q[A(Q) ∧Q<P]

*A**(*P*) says that *P* satisfies *A*, and that no
smaller predicate does. Let *Px* be the predicate “*x* is
abnormal,” and let *A*(*P*) be the sentence “All birds that
are not abnormal fly.” Then the sentence “Tweety is a bird,” together
with *A**(*P*) implies “Tweety flies,” for the
circumscription axiom forces the extension of *P* to be empty, so
that “Tweety is normal” is automatically true.

In terms of consequence relations, circumscription allows us to
define, for each predicate *P*, a non-monotonic
relation *A*(*P*)
φ that holds
precisely when *A*(P)* ⊨ φ. (This
basic form of circumscription has been generalized, for, in practice,
one needs to minimize the extension of a predicate, while allowing the
extension of certain other predicates to vary.) From the point of view
of applications, however, circumscription has a major computational
shortcoming, which is due to the nature of the second-order language
in which circumscription is formulated. The problem is that SOL,
contrary to FOL, lacks a complete inference procedure: the price one
pays for the greater expressive power of SOL is that there are no
complete axiomatizations, as we have for FOL. It follows that there is
no way to list, in an effective manner, all SOL validities, and hence
to determine whether *A*(*P*)
φ.

Another influential mechanism realizing the closed world assumption
is *Negation as Failure*
(or *Default Negation*). It can
nicely be explained if we take a look at *Logic Programming*. A
logic program consists of a list of rules such as:

τ ← φ

_{1}, …, φ_{n},notψ_{1}, …,notψ_{m}

In basic logic programs τ is a logical atom and φ_{1},
…, φ_{n}, ψ_{1}, …,
ψ_{m} are logical literals. This has been
generalized in various ways
(e.g., Alferes et al. (1995)) and
many ways of interpreting rules have been proposed, but for us it is
sufficient to stick to this simple form and an explanation on an
intuitive level. A concrete example for a rule is:

flies←bird,notpenguin

Such rules read as expected: if the formulas in the antecedent (right
hand side) hold, then the conclusion (left hand side) holds. Default
negation is realized as follows: if *penguin* cannot be proved
then *not penguin* is considered to hold. A logic program for our
Tweety example may consist of the rule above and

not-flies←penguin

bird←penguin

Suppose first all we know is *bird*. The latter two rules will
not be triggered, and the first rule be will interpreted with the
closed world assumption so that *flies* can be inferred. Now
suppose we know *penguin*. In this case the first rule is not
applicable but the latter two are and we derive *bird*
and *not-flies*.

### 3.2 Inheritance networks and argument-based approaches

Whenever we have a taxonomically organized body of knowledge, we presuppose that subclasses inherit properties from their superclasses: dogs have lungs because they are mammals, and mammals have lungs. However, there can be exceptions, which can interact in complex ways as in the following example: mammals, by and large, don't fly; since bats are mammals, in the absence of any information to the contrary, we are justified in inferring that bats do not fly. But if we learn that bats are exceptional mammals, in that they do fly, the conclusion that they don't fly is retracted, and the conclusion that they fly is drawn instead. Things can be more complicated still, for in turn, baby bats are exceptional bats, in that they do not fly (does that make them unexceptional mammals?). Here we have potentially conflicting inferences. When we infer that Stellaluna, being a baby bat, does not fly, we are resolving all these potential conflicts based on the Specificity Principle.

*Non-monotonic inheritance networks* were developed for the
purpose of capturing taxonomic examples such as the one above. Such
networks are collections of nodes and directed (“*is-a*”) links
representing taxonomic information. When exceptions are allowed, the
network is interpreted *defeasibly*. The following figure gives a
network representing this state of affair:

In such a network, links of the form *A* → *B*
represent the fact that, typically and for the most part, *A*s
are *B*s, and that therefore information about *A*s is more
specific than information about *B*s. More specific information
overrides more generic information. Research on non-monotonic
inheritance focuses on the different ways in which one can make this
idea precise.

The main issue in defeasible inheritance is to characterize the set of
assertions that are supported by a given network. It is of course not
enough to devise a representational formalism, one also needs to
specify how the formalism is to be interpreted. Such a
characterization is accomplished through the notion of
an *extension* of a given network. There are two competing
characterizations of extension for this kind of networks, one that
follows the credulous strategy and one that follows the skeptical
one. Both proceed by first defining the *degree* of a path
through the network as the length of the longest sequence of links
connecting its endpoints; extensions are then constructed by
considering paths in ascending order of their degrees. We are not
going to review the details, since many of the same issues arise in
connection with Default Logic (which is
discussed below), but Horty (1994) provides
an extensive survey. It is worth mentioning that since the notion of
degree makes sense only in the case of acyclic networks, special
issues arise when networks contain cycles
(see Antonelli (1997) for a treatment of
inheritance on cyclic networks).

Although the language of non-monotonic networks is expressively
limited by design (in that only links of the form “*is-a*”
— and their negations — can be represented in a natural
fashion), such networks provide an extremely useful setting in which
to test and hone one's intuitions and methods for handling defeasible
information. Such intuitions and methods are then applied to more
expressive formalisms.

In *argument-based approaches* to defeasible reasoning the notion
of a path through an inheritance network is generalized to the notion
of an argument. Abstracting from the specifics and subtleties of
formalisms proposed in the literature (for an excellent survey see
Prakken and Vreeswijk (2002))^{[3]},
an *argument*
can be thought of in the following way. Given a language L, a set of
L-formulas Γ, a set of strict rules *SRules* of the form
φ_{1}, …, φ_{n} ⇒ ψ
(where φ_{i} and ψ are L-formulas) and a set of
defeasible rules *DRules* of the form φ_{1},
…, φ_{n} → ψ (where
φ_{i} and ψ are L-formulas) an *argument*
(Θ,τ) *for* τ is a proof of τ from some Θ
⊆ Γ using the rules in *SRules* and *DRules*.

A central notion in argument-based formalism is *argumentative
attack*. We can, for instance, distinguish between rebuts and
undercuts. A *rebut* of an argument (Θ,τ) is an
argument that establishes that τ is not the case, viz. an argument
for ¬τ. An *undercut* of (Θ,τ) establishes that
Θ does not support τ. For instance, the argument that
concludes that an object is red from the fact that it looks red, is
undercut by means of the observation that that object is illuminated
by red light (Pollock (1995)). Note that
in order to undercut an argument for τ one need not establish that
τ doesn't hold.

On an intuitive level, the basic idea is that the question whether an
argument is *acceptable* concerns the question whether it is
defended from its argumentative attacks.
Dung (1995) proposed a way to address this question purely on the basis
of the attack relations between arguments while abstracting from the
concrete structure of the given arguments. Where *Args* is the
set of the arguments that are generated from Γ by the rules
in *SRules* and *DRules*, we define an *attack
relation* ↝ ⊆ *Args* × *Args* as
follows: *a* ↝ *b* if and only if *a* attacks
(e.g., rebuts or undercuts) *b*. This gives rise to a directed
graph, the *abstract argumentation framework*, where arguments
are nodes and arrows represent the attack relation. Note that at the
level of the directed graph arguments are treated in an abstract way:
the concrete structure of the arguments is not presented in the graph.

Various *argumentation semantics* have been proposed for such
graphs specifying criteria for selecting sets of arguments that
represent stances of rational agents. Clearly, a selected set of
arguments *S* ⊆ *Args* should satisfy the following
requirements:

*S*should be*conflict-free*, i.e., for all*a*,*b*∈*Args*,*a*does not attack*b*.*S*should be able to defend itself from all attackers. More precisely, a conflict-free*S*is*admissible*if for every*a*∈*Args*that attacks some*b*∈*S*there is a*c*∈*S*that attacks*a*.

For instance, given the following graph

{*a*} is admissible, while {*a*, *b*} is not conflict-free and
{*d*} is not admissible.

Given these basic requirements we can define, for instance, the following semantics that frequently appears in the literature:

- A
*preferred*set of arguments*S*is an admissible set of arguments that is maximal in*Args*relative to set-inclusion.

In our example {*a*, *d*} and {*b*, *d*} are the two preferred
sets. This shows that the preferred semantics does not determine a
unique selection. We can proceed either according to the credulous
rationale or according to the skeptical rationale in order to define a
consequence relation. Considering an abstract argumentation framework
based on Γ, *SRules*, and *DRules*, we give two
examples of how a consequence set can be characterized by means of the
skeptical approach (Prakken (2010)):

- τ is a consequence if in each preferred set
*S*of arguments there is an argument*a*for τ. - τ is a consequence if there is an argument
*a*for τ that is in every preferred set of arguments*S*.

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 τ.

### 3.3 Default logic

In *Default Logic*, the main representational tool is that of
a *default rule*, or simply a *default*. A default is a
defeasible inference rule of the form

(γ : θ) / τ

where γ, θ, τ are sentences in a given language,
respectively called the *pre-requisite*, the *justification*
and the *conclusion* of the default. The interpretation of the
default is that if γ is known, and there is no evidence that
θ might be false, then τ can be inferred.

As is clear, application of the rule requires that a consistency condition be satisfied. What makes meeting the condition complicated is the fact that rules can interact in complex ways. In particular, it is possible that an application of some rule might cause the consistency condition to fail for some, not necessarily distinct, rule. For instance, if θ is ¬τ then application of the rule is in a sense self-defeating, in that an application of the rule itself causes the consistency condition to fail.

Reiter's default logic (Reiter (1980)) uses
the notion of an *extension* to make precise the idea that the
consistency condition has to be met both before and after the rule is
applied. Given a set Δ of defaults, an extension for Δ
represents a set of inferences that can be *reasonably*
and *consistently* drawn using defaults from Δ. Such
inferences are those that are warranted on the basis of a maximal set
of defaults whose consistency condition is met both before and after
their being triggered.

More in particular, an extension is defined relative to a *default
theory*. The latter is a pair (Γ, Δ), where Δ is
a (finite) set of defaults, and Γ is a set of sentences (a world
description). The idea is that Γ represents the strict or
background information, whereas Δ specifies the defeasible
information. We say that Ξ is an *extension* for a default
theory (Γ, Δ) if and only if

Ξ = Ξ

_{0}∪ Ξ_{1}∪ … ∪ Ξ_{n}∪ …

where Ξ_{0} = Γ, and

Ξ

_{n+1}= Cn(Ξ_{n}) ∪ {τ ∣ (γ : θ) / τ ∈ Δ where ¬θ ∉ Ξ and γ ∈ Ξ_{n}}

where Cn(•) is the consequence relation of CL. It is important to
notice the occurrence of the limit Ξ in the definition of
Ξ_{n+1}: the condition above is not a garden-variety
recursive definition, but a truly circular characterization of
extensions.

This circularity can be made explicit by giving an equivalent definition of extension as solution of fixpoint equations. Given a default theory (Γ, Δ), let S be an operator defined on sets of sentences such that for any such set Φ, S(Φ) is the smallest set that satisfies the following three requirements:

- it contains Γ (Γ ⊆ S(Φ)),
- it is deductively closed (i.e., if S(Φ) ⊨ φ then φ ∈ S(Φ)),
- and it is closed under the default rules in Δ: whenever for a default (γ : θ) / τ ∈ Δ both γ ∈ S(Φ) and ¬θ ∉ Φ, then τ ∈ S(Φ).

Then one can show that Ξ is an extension for (Γ,Δ) if and only if Ξ is a fixed point of S, i.e., if S(Ξ) = Ξ.

Neither one of the two characterizations of extension for default logic (i.e., the fixpoint definition and the pseudo-iterative one) provides us with a way to “construct” extensions by means of anything resembling an iterative process. Essentially, one has to “guess” a set of sentences Ξ, and then verify that it satisfies the definition of an extension.

For any given default theory, extensions need not exist, and even when
they exist, they need not be unique. We start with an example of the
former situation: let Γ = ∅ and let Δ comprise the
single
default^{[4]}

(⊤ : θ) / ¬θ

If Ξ were an extension, then the justification θ of the
default above would either be consistent with Ξ or not, and either
case is impossible. For if θ were consistent with Ξ, then the
default would be applied to derive ¬θ in contradiction the
the consistency of Ξ with θ. Similarly, if Ξ were
inconsistent with θ then Ξ ⊨ ¬θ and hence, by
deductive closure, ¬θ ∈ Ξ. Our default would not be
applicable, in which case Ξ = Ξ_{1} = Cn(∅). But
then ¬θ ∉ Ξ,—a contradiction.

For normal default theories that only consist of *normal
defaults*, i.e., defaults of the form (γ : θ) /
θ, extensions always exist.

Lukaszewicz (1988) presents a modified definition of extension that avoids the previous two problems: it is defined in an iterative way and it warrants the existence of an extension. In a nutshell the idea is to keep track of the used justifications in the procedure. A default is applied in case its precondition is implied by the current beliefs and its conclusion is consistent with the given beliefs, its own justificiation, and each of the justifications of previously applied defaults. For normal theories Lukaszewicz's definition of extensions is equivalent to the definitions from above.

Let us now consider an example of a default theory with multiple extensions. Let Γ = ∅, and suppose Δ comprises the following two defaults

(⊤ : θ) / ¬τ and (⊤ : τ) / ¬θ

This theory has exactly two extensions, one in which the first default is applied and one in which the second one is. It is easy to see that at least one default has to be applied in any extension, and that both defaults cannot be applied in the same extension.

The fact that default theories can have zero, one, or multiple
extensions raises the issue of what inferences one is warranted in
drawing from a given default theory. The problem can be presented as
follows: given a default theory (Γ, Δ), what sentences can
be regarded as *defeasible consequences* of the theory?

Sometimes it may be useful to map out all the consequences that can be
drawn from *all* the extensions, for instance, in order to
identify extensions that give rise to undesired consequences (in view
of extralogical considerations). The credulous approach does just
that: (Γ, Δ)
φ if and only if φ belongs to *any* extension of the
theory. Clearly, in case of multiple extensions the consequence set
will not be closed under CL and it may be inconsistent.

Alternatively, one can adopt the skeptical strategy according to which
(Γ, Δ) φ
if and only if φ is contained in *every* extension of
(Γ, Δ).

Skeptical consequence, as based on Reiter's notion of extension, fails to be cautiously monotonic (Makinson (1994)). To see this, consider the default theory (∅, Δ), where Δ comprises the following two defaults:

(⊤ : θ) / θ and (θ ∨ γ : ¬θ) / ¬θ

This theory has only one extension, coinciding with the deductive closure of {θ}. Hence, according to skeptical consequence we have (∅, Δ) θ, as well as (∅, Δ) θ ∨ γ (by the deductive closure of extensions).

Now consider the theory ({θ ∨ γ}, Δ). We have two
extensions: one the same as before, but also another one coinciding
with the deductive closure of {¬θ}, and hence not containing
θ. It follows that the intersection of the extensions no longer
contains θ, so that ({θ ∨ γ}, Δ)
θ *fails*,
against Cautious Monotony. (Notice that the same example establishes a
counter-example for Cut for the credulous strategy, when we pick the
extension of ({θ ∨ γ}, Δ) that contains
¬θ.)

In Antonelli (1999) a notion
of *general extension* for default logic is introduced, showing
that this notion yields a well-behaved relation of defeasible
consequence that satisfies
Supraclassicality (if Γ ⊨ φ then Γ
φ) and the three
central requirements for NMLs Reflexivity, Cut, and Cautious Monotony
from Gabbay (1985). The idea behind general
extensions can be explained in a particularly simple way in the case
of *pre-requisite free* default theories (called “categorical”
in *Antonelli (1999)*). A general extension for such a default
theory is a *pair* (Γ^{+},
Γ^{−}) of sets of defaults (or conclusions
thereof) that simultaneously satisfies *two* fixpoint
equations. The set Γ^{+} comprises (conclusions of)
defaults that are explicitly triggered, and the set
Γ^{−} comprises (conclusions of) defaults that are
explicitly ruled out. The intuition is that defaults that are not
ruled out can still prevent other defaults from being triggered
(although they might not be triggered themselves). We thus obtain a
“3-valued” approach (not unlike that of Kripke's theory of truth
(Kripke (1975))), in virtue of which
general extensions are now endowed with a non-trivial (i.e., not
“flat”) algebraic structure. It is then possible to pick out, in a
principled way, a particular general extension (for instance, the
unique least one, which is always guaranteed to exist) on which to
base a notion of defeasible consequence.

A different set of issues arises in connection with the behavior of default logic from the point of view of computation. For a given semi-decidable set Φ of sentences, the set of all φ that are a consequence of Φ in FOL is itself semi-decidable (see the entry on computability and complexity). In the case of default logic, to formulate the corresponding problem one extends (in the obvious way) the notion of (semi-)decidability to sets of defaults. The problem, then, is to decide, given a default theory (Γ, Δ) and a sentence φ whether (Γ, Δ) φ, where is defined, say, skeptically. Such a problem is not even semi-decidable, since, in order to determine whether a default is triggered by a pair of sets of sentences, one has to perform a consistency check, and such checks are not computable.

Default logic as defined above does not prioritize among
defaults. In Poole (1985) we find an
approach in which the Specificity Principle is
considered. In Horty (2007) defaults are
ordered by a strict partial order ≺ where (γ : θ) /
τ ≺ (γ′ : θ′) / τ′ means
that (γ′ : θ′) / τ′ has priority
over (γ : θ) / τ. The ordering ≺ may express
—depending on the application— specificity relations, the
comparative reliability of the conditional knowledge expressed by
defaults, etc. An *ordered default theory* is then a triple
(Γ, Δ, ≺) where (Γ, Δ) is a default
theory. We give an example but omit a more technical explanation. Take
Γ = {*bird*, *penguin*}, Δ = {*bird*
→ *flies*, *penguin* → ¬*flies*} and
≺ = {(*bird* → *flies*, *penguin* →
¬*flies*)}, where φ → ψ represents the normal
default (φ : ψ) / ψ. We have two extensions of (Γ,
Δ), one in which *bird* → *flies* is applied and
one in which *penguin* → ¬*flies* is applied. Since
the latter default is ≺-preferred over the former, only the
latter extension is an extension of (Γ, Δ, ≺).

### 3.4 Autoepistemic logic

Another formalism closely related to default logic is
Moore's *Autoepistemic Logic* (Moore (1985)).
It models the reasoning of an ideal agent reflecting on
her own beliefs. For instance, sometimes the absence of a belief in
φ may give an agent a reason to infer ¬φ. Moore gives the
following example: If I had an older brother, I would know about
it. Since I don't, I believe not to have an older brother.

An autoepistemic theory consists of the beliefs of an agent including
her reflective beliefs about her beliefs. For the latter an
autoepistemic belief operator B is used. In our example such a theory
may contain ¬B*brother* ⊃
¬*brother*. Autoepistemic logic specifies ideal properties of
such theories. Following Stalnaker (1993),
an autoepistemic theory Γ should be *stable*:

- Γ should be closed under classical logic: if Γ ⊨ φ then φ ∈ Γ;
- Γ should be introspectively adequate:
- if φ ∈ Γ then Bφ ∈ Γ;
- if φ ∉ Γ then ¬Bφ ∈ Γ.

Given Γ is consistent, stability implies that

- φ ∈ Γ if and only if Bφ ∈ Γ, and
- φ ∉ Γ if and only if ¬Bφ ∈ Γ.

Let us, for instance, consider the two types of consistent stable sets
that extend Ξ_{1} = {¬B*brother* ⊃
¬*brother*}:

- Γ
_{1}for which*brother*∈ Γ_{1}and by introspection also B*brother*∈ Γ_{1}. - Γ
_{2}for which*brother*∉ Γ_{2}. Hence, ¬B*brother*∈ Γ_{2}and by closure, ¬*brother*∈ Γ_{2}. Thus, by introspection also B¬*brother*∈ Γ_{2}.

The second option seems more intuitive since given only
¬B*brother* ⊃ ¬*brother* the belief
in *brother* seems intuitively speaking ungrounded in view of
Ξ_{1}. To make this formally precise, Moore defines

- Γ is
*grounded in a set of assumptions Ξ*if for each ψ ∈ Γ, Ξ ∪ {Bφ ∣ φ ∈ Γ} ∪ {¬Bφ ∣ φ ∉ Γ} ⊨ ψ.

Stable theories that are grounded in a set of assumptions Ξ are
called *stable expansions of Ξ* or *autoepistemic extensions
of Ξ*. Stable expansions Γ of Ξ can equivalently be
characterized as fixed points:

Γ = Cn(Ξ ∪ {Bφ ∣ φ ∈ Γ} ∪ {¬Bφ ∣ φ ∉ Γ})

where Cn(•) is the consequence function of CL.

Clearly, there is no stable theory that is grounded in
Ξ_{1} and that contains *brother* and/or
B*brother* like our Γ_{1} above. The reason is that
we fail to derive *brother* from Ξ_{1} ∪ {Bψ
∣ ψ ∈ Γ_{1}} ∪ {¬Bψ ∣
ψ ∉ Γ_{1}}. The only stable extension of
Ξ_{1} contains ¬B*brother* and
¬*brother*.

Just as in default logic, some sets of assumptions have no stable
extensions while some have multiple stable extensions. We demonstrate
the former case with Ξ_{2} = {¬Bφ ⊃
φ}. Suppose there is a stable extension Γ of
Ξ_{2}. First note that there is no way to ground φ in
view of Ξ_{2}. Hence φ ∉ Γ which means that
¬Bφ ∈ Γ. But then φ ∈ Γ by modus
ponens and since ¬Bφ ⊃ φ ∈ Γ,—a
contradiction.

Moore's notion of groundedness allows for a type of epistemic
bootstrapping. Take Ξ_{3} = {Bφ ⊃ φ}. Suppose
an agent adopts the belief that she believes φ, i.e. Bφ. Now
she can use Bφ ⊃ φ to derive φ. Hence, on the basis of
Ξ_{3}, she can ground her belief in φ on her belief
that she believes φ. Indeed, there is a stable extension of
Ξ_{3} containing φ and Bφ. In view of this, weaker
forms of groundedness have been proposed
in Konolige (1988) that do not allow for
this form of bootstrapping and according to which we only have the
extension of Ξ_{3} that contains neither φ nor Bφ.

The centrality of autoepistemic logic in NML is emphasized by the fact that several tight links to other seminal formalism have been established. Let us mention three such links.

First, there are close connections between autoepistemic logic and logic programming. For instance, Gelfond's and Lifschitz's stable model semantics for logic programming with negation as failure which serves as the foundation for the answer set programming paradigm in computer science has been equivalently expressed by means of autoepistemic logic (Gelfond and Lifschitz (1988)). The result is achieved by translating clauses in logic programming

φ ← φ

_{1}, …, φ_{n},notψ_{1}, …,notψ_{m}

in such a way that negation as failure (*not* ψ) gets the
meaning “it is not believed that ψ” (¬Bψ):

(φ

_{1}∧ … ∧ φ_{n}∧ ¬Bψ_{1}∧ … ∧ ¬Bψ_{m}) ⊃ ψ

A second link has been established in Konolige (1988) with default logic which has been shown inter-translatable and equi-expressive with Konolige's strongly grounded variant of autoepistemic logic. Default rules (γ : θ) / τ are translated by interpreting consistency conditions θ by ¬B¬θ which can be read as “θ is consistent with the given beliefs”:

(Bγ ∧ ¬B¬θ) ⊃ τ

Especially the latter link is rather remarkable since the subject matter of the given formalisms is quite different. While default logic deals with defeasible rules, i.e., rules that allow for exceptions (such as 'Birds fly'), the non-monotonicity of autoepistemic logic is rooted in the indexicality of its autoepistemic belief operator (Moore (1984), Konolige (1988)): it refers to the autoepistemic theory into which it is embeded and hence its meaning may change when we add beliefs to the theory.

Various modal semantics have been proposed for autoepistemic logic
(see the entry on modal logic for more
background on modal logics). For instance, Moore (1984)
proposes an S5-based Kripkean possible world semantics
and Lin and Shoham (1990) propose
bi-modal preferential semantics (see
Section Selection Semantics below) for both
autoepistemic logic and default
logic. In Konolige (1988) it has been
observed that the fixed point characterization of stable expansions
can be alternatively phrased only on the basis of the set of formulas
Γ_{0} in Γ that do not contain occurrences of the
modal operator B:

Γ = Cn[K45](Ξ ∪ {Bφ ∣ φ ∈ Γ

_{0}} ∪ {¬Bφ ∣ φ ∉ Γ_{0}})

where Cn[K45](•) is the consequence function of the modal logic K45.

### 3.5 Selection semantics

In CL a formula φ is entailed by Γ (in signs Γ ⊨
φ) if and only if φ is valid in all classical models of
Γ. An influential idea in NML is to define non-monotonic
entailment not in terms of *all* classical models of Γ, but
rather in terms of a *selection* of these models
(Shoham (1987)). Intuitively the idea is to
read

Γ φ

as

“φ holds in the most normal/natural/etc. models of Γ.”

In the seminal paper Kraus et al. (1990) this idea is investigated systematically.

#### 3.5.1 The core properties

The authors introduce various semantic structures, among them
preferential ones. A *preferential structure* S consists of

- a set Ω of states
- and an irreflexive and transitive relation ≺ on Ω.

In the context of preferential structures one may think of states in
terms of labelled models M_{s} of classical
propositional logic, where each label *s* is attached to a unique
model M but a model may occur under various labels in
Ω.^{[5]}
For the ease of demonstration we
will henceforth just talk about 'models in Ω' and not anymore
refer to states or labelled models.

Intuitively, M ≺ M′ if M is more normal than M′. The
relation ≺ can be employed to formally realize the idea of
defining a consequence relation in view of the most normal models,
namely by focusing on ≺-minimal models. Formally, where [ψ]
is the set of all models of ψ in Ω,
^{S} is defined as follows:

ψ

^{S}φ if and only if φ holds in all ≺-minimal models in [ψ].

In order to warrant that there are such minimal states, ≺ is
considered to be *smooth* (also sometimes
called *stuttered*), i.e., for each M either M is ≺-minimal
or there is a ≺-minimal M′ such that M′ ≺ M.

Preferential structures enjoy a central role in NML since they
characterize *preferential consequence relations*, i.e.,
non-monotonic consequence relations
that fulfill the following central properties,
also referred to as the *core properties* or the *conservative
core* of non-monotonic reasoning systems or as
the *KLM-properties* (in reference to the authors
of Kraus, Lehmann, Magidor (1990)):

**Reflexivity**: φ φ**Cut**: If φ ∧ ψ τ and φ ψ, then φ τ.**Cautious Monotonicity**: If φ ψ and φ τ then φ ∧ ψ τ.**Left Logical Equivalence**: If ⊨ φ ≡ ψ and φ τ, then ψ τ.**Right Weakening**: If ⊨ φ ⊃ ψ and τ φ, then τ ψ.

The former three properties we have already seen above. According to Left Logical Equivalence, classically equivalent formulas have the same non-monotonic consequences. Where ψ is classically entailed by φ, Right Weakening expresses that whenever φ is a non-monotonic consequence of τ then so is ψ.

Without further commentary we state two important derived rules:

**AND**: If φ ψ and φ τ then φ ψ ∧ τ.**OR**: If φ ψ and τ ψ then φ ∨ τ ψ.

In Kraus et al. (1990) it is shown
that a consequence relation
is preferential if and
only if =
^{S}
for some preferential structure S.

Given a set of conditional assertions **K** of the type φ
ψ one may be
interested in investigating what other conditional assertions
follow. The following two strategems lead to the same results. The
first option is to intersect all preferential consequence relations
that extend **K** (in
the sense that the conditional assertions in **K** hold for
) obtaining
the *Preferential Closure*
^{P}
of **K**. The second option is to
use the five defining properties of preferential consequence relations
as deduction rules for syntactic units of the form φ
ψ. This way we obtain
the deductive *system P* with its consequence relation
⊢^{P} for which:

K⊢^{P}φ ψ if and only if φ^{P}ψ

#### 3.5.2 Various semantics

One of the most remarkable facts in the study of NMLs is that various other semantics have been proposed —often independently and based on very different considerations— that also adequately characterize preferential consequence relations. This underlines the central status of the core properties in the formal study of defeasible reasoning.

Many of these approaches use structures S = (Ω, Π) where
Ω is again a set of classical models and Π is a mapping with
the domain ℘(Ω) (the set of subsets of Ω) and an
ordered co-domain (D, <). The exact nature of (D, <) depends on
the given approach and we give some examples below. The basic common
idea is to let φ
^{S} ψ
in case Π([φ∧ψ]) is preferable to
Π([φ∧¬ψ]) in view of <. The following table
lists some proposals which we discuss some more below:

Π | φ ^{S} ψ iff |
Structures |
---|---|---|

possibility measure | π([φ]) = 0 or | possibilistic structures |

π: ℘(Ω) → [0,1] | π([φ ∧ ψ]) > π([φ ∧ ¬ψ]) | |

ordinal ranking function | κ([φ]) = ∞ or | ordinal ranking structures |

κ: ℘(Ω) → {0,1,…,∞} | κ([φ ∧ ψ]) < κ([φ ∧ ¬ψ]) | |

plausibility measure | Pl([φ]) = ⊥ or | plausibility structures |

Pl: ℘(Ω) → D | Pl([φ ∧ ψ]) > Pl([φ ∧ ¬ψ]) |

Possibility measures assign real numbers in the interval [0,1] to
propositions in order to measure their possibility, where 0
corresponds to impossible states and 1 to necessary states
(Dubois and Prade (1990)). Ordinal
ranking functions rank propositions via natural numbers closed with
∞ (Goldszmidt and Pearl (1992)).
One may think of κ([φ]) as the level of
surprise we would face were φ to hold, where ∞ represents
maximal surprise. Finally, plausibility measures
(Friedman and Halpern (1996))
associate propositions with elements in a partially ordered domain
with bottom element ⊥ and top element ⊤ in order to compare
their plausibilities. Given some simple constraints on Pl (such as: If
Pl(X) = Pl(Y) = ⊥ then Pl(X ∪ Y) = ⊥) we speak
of *qualitative plausibility structures*. The following
statements are all equivalent which emphasizes the centrality of the
core properties in the study of NMLs:

**K**⊢^{P}φ ψ- φ
^{S}ψ for all preferential structures S for which^{S}extends**K** - φ
^{S}ψ for all possibilistic structures S for which^{S}extends**K** - φ
^{S}ψ for all ordinal ranking structures S for which^{S}extends**K** - φ
^{S}ψ for all qualitative plausibility structures S for which^{S}extends**K**

Yet another well-known semantics that characterizes preferential
consequence relations makes use of *conditional
probabilities*. The idea is that φ
ψ holds in a structure if the conditional
probability P(ψ|φ) is closer to 1 than an arbitrary ε,
whence the name ε-*semantics*
(Adams (1975),
Pearl (1989)).

The following example demonstrates that the intuitive idea of using a threshold value such as ½ instead of infinitesimals and to interpret φ ψ as P(ψ∣φ) > ½ does not work in a straightforward way. Let α abbreviate “being a Pennsylvania Dutch”, β abbreviate “being a native speaker of German”, and γ abbreviate “being born in Germany”. Further, let our knowledge base comprise the statements “αs are usually βs,” “α∧β's are usually γs”. The following Euler diagram illustrates the conditional probabilities in a possible probability distribution for the given statements.

We have for instance: P(β∣α) = ¾, P(γ∣α∧β) = ⅔ and P(γ∣α) = ½. Hence, under the proposed reading of , we get α β, α∧β γ while we do not have α γ. This means that Cut is violated. Similarly, it can be shown that other properties such as Or are violated under this reading (e.g., Pearl (1988)).

In view of these difficulties it is remarkable that there is a
probabilistic account according to which φ
ψ is interpreted as P(ψ∣φ) >
½ and that nevertheless characterizes preferential consequence
relations (Benferhat et al. (1999)).
The idea is to restrict the focus to structures S =
(Ω, P, ≺) that come with specific probability
distributions known as *atomic bound systems* or *big-stepped
probabilities*. First, a linear order ≺ is imposed on the
set of classical models in Ω over which the probability measure
P is defined. Second, P is required to respect this order by “taking
big steps”, i.e., in such a way that for any M ∈ Ω, P({M})
> ∑{P({M′}) ∣ M′ ≺ M}. This warrants
that φ ψ holds if
and only if the unique ≺-maximal model in [φ] validates
ψ (in signs, max[φ] ⊧
ψ).^{[6]} Here
is how this helps us with the problematic example above: α
β means that
max[α] ⊧ β and hence that max[α] =
max[α∧β]. α∧β
γ means that max[α∧β]
⊧ γ and hence max[α] ⊧ γ which implies
α γ.

In Gilio (2002) an approach is presented in
which conditionals α
β are characterized by *imprecise conditional probabilities*
0 ≤ τ_{1} ≤ P(β∣α) ≤
τ_{2} ≤ 1 with a lower bound τ_{1} and an
upper bound τ_{2} on the conditional probabilities. In
this approach it is possible to determine how the probability bounds
degrade in view of applications of specific inference
rules. In Ford (2004) this is used to
distinguish argument strengths (see above).

#### 3.5.3 Beyond the core properties

Preferential consequence relations do not in general validate

**Rational Monotonicity**: If φ τ and it is not the case that φ ¬ψ, then φ ∧ ψ τ.

A preferential consequence relation
that satisfies Rational Monotonicity is called
a *rational consequence relation*. These are characterized
by *ranked structures* which are preferential structures S =
(Ω, ≺) for which ≺ is *modular*, i.e., for all
M, M′, M′′ ∈ Ω, if M ≺ M′
then either M′′ ≺ M′ or M ≺
M′′. One can picture this as follows: models in Ω
are arranged in linearly ordered levels and the level of a model
reflects its degree of normality (its rank).

The seminal Kraus et al. (1990) inspired a huge variety of subsequent work. We briefly highlight some contributions.

While in Kraus et al. (1990) the standard of deduction was classical propositional logic, in Arieli and Avron (2000) also nonclassical monotonic core logics and variants with multiple conclusions are considered. Various publications investigate the preferential and rational consequence relations in a first-order language (e.g., Lehmann and Magidor (1990), Delgrande (1998), Friedman et al. (2000)).

As we have seen, the properties of preferential or rational
consequence relations may also serve as deductive rules for syntactic
units of the form φ
ψ under the usual readings such as “If φ then usually ψ.”
This approach can be generalized to gain *conditional logics* by
allowing for formulas where a conditional assertion φ
ψ is within the scope
of classical connectives such as ∧, ∨, ¬,
etc. (e.g., Delgrande (1987),
Asher and Morreau (1991),
Friedman and Halpern (1996),
Giordano et al. (2009)).
We state one remarkable result obtained
in Boutilier (1990) that closely links
the study of NMLs to the study of modal logics in the Kripkean
tradition. Suppose we translate the deduction rules of system P into
Hilbert-style axiom schemes such that, for instance, Cautious
Monotonicity becomes

⊢ ((φ ψ) ∧ (φ τ)) ⊃ ((φ ∧ ψ) τ)

It is shown that conditional assertions can be expressed in standard Kripkean modal frames in such a way that system P (under this translation) corresponds to a fragment of the well-known modal logic S4. An analogous result is obtained for the modal logic S4.3 and the system that results from strengthening system P with an axiom scheme for Rational Monotonicity.

Various contributions are specifically devoted to problems related to
relevancy. Consider some of the conditional assertions in the Nixon
Diamond: **K** = {*Quaker*
*Pacifist*, *Republican*
¬*Pacifist*}. It
seems desirable to derive e.g. *Quaker* ∧ *worker*
*Pacifist* since in
view of **K**, being a worker is *irrelevant* to the
assertion *Quaker*
*Pacifist*. Intuitively speaking, *Quaker*
¬*worker* should
fail in which case Rational Monotonicity yields *Quaker*
∧ *worker*
*Pacifist* in view of *Quaker*
*Pacifist*. Hence, prima facie we may want
to proceed as follows: let ^{R}
be the result of intersecting all rational consequence
relations that
extend **K** (in the sense that the conditional assertions
in **K** hold for ).
Unfortunately it is *not* the case that *Quaker*
∧ *worker* ^{R}
*Pacifist*. The reason is simply that there are
rational consequence relations for which *Quaker*
¬*worker* and
whence Rational Monotonicity does not yield the desired *Quaker*
∧ *worker*
*Pacifist*. Moreover, it has been shown that
^{R} is identical
to the preferential closure ^{P}.

In Lehmann and Magidor (1992)
a *Rational Closure* for conditional knowledge bases such
as **K** is proposed that yields the desired consequences. We omit
the technical details. The basic idea is to assign natural numbers,
i.e., ranks, to formulas which indicate how exceptional they are. Then
the ranks of formulas are minimized which means that each formula is
interpreted as normally as possible. A conditional assertion φ
ψ is in the Rational
Closure of **K** if the rank of φ is strictly less than the
rank of φ ∧ ¬ψ. In our example *Quaker ∧
worker* will get the same rank as *Quaker* which will be
stricly less than the ranks of *Quaker ∧ ¬Pacifist*
and *Quaker ∧ worker ∧ ¬Pacifist*. This means that
the desired *Quaker* ∧ *worker*
*Pacifist* is in the Rational Closure of
our **K**.

A system equivalent to Rational Closure has been independently
proposed under the name *system Z* based on
ε-semantics in Pearl (1990).

One may consider it a drawback of Rational Closure that it suffers
from the Drowning Problem (see above). This
problem has been tackled in Lehmann (1995)
with the formalism *Lexicographic Closure*. For
instance, *Penguin ∧ Bird*
*has wings* is in the Lexicographic Closure
but not in the Rational Closure of **K** = {*Penguin*
*Bird*, *Penguin*
¬*flies*, *Bird*
*flies*, *Bird*
*has wings*}.

Lexicographic Closure also implements a *quantitative rationale*
according to which in cases of conflicts as many conditional
assertions as possible are validated. Suppose our knowledge
base **K** consists of

*Party**Anne*,*Party**Phil*, and*Party**Frank*.

We expect from each, Anne, Phil, and Frank, to come to the party.
Suppose moreover we know that *Party* ∧ ((¬ *Anne*
∧ ¬ *Phil*) ∨ ¬ *Frank*). In view of this
fact not all three assertions hold. At best either the former two hold
or the latter. If we try to validate as many conditional assertions as
possible we will prefer the situation in which only the latter is
violated. This happens in the Lexicographic Closure of **K** which
contains

*Party*∧ ((¬*Anne*∧ ¬*Phil*) ∨ ¬*Frank*) ¬*Frank*and*Party*∧ ((¬*Anne*∧ ¬*Phil*) ∨ ¬*Frank*)*Anne*∧*Phil*.

Similar quantitative considerations play a role in the *Maximum
Entropy Approach* in Goldzsmidt et
al. (1993) which is based on ε-semantics. A difference to
Lexicographic Closure is, for instance, that *Penguin* ∧
(*flies* ∨ ¬*has wings*)
*bird* is in the Lexicographic Closure of
our example above but doesn't follow according to the
entropy-maximizing approach. The reason is a more rigorous
application of the specificity principle in the Lexicographic Closure.
Given the antecedent *Penguin* ∧ (*flies* ∨
¬*has wings*) we have various choices, such as
violating *Bird*
*has wings* and *Bird*
*flies*, or to merely violate *Penguin*
*Bird*. The latter
assertion is more specific than the previous two. In such a situation
Lexicographic Closure will always opt for avoiding the violation of
the more specific assertion. Although the approach
in Goldzsmidt et al. (1993) also
applies the Specificity Principle, it does so in a different way,
namely by minimizing the weigthed sum of violations where weights are
attributed to violations in view of specificity considerations. E.g.,
in our example, the violation of two less specific assertions
counter-balances the violation of the more specific assertion.

### 3.6 Assumption-based approaches

In a family of approaches defeasible inferences are encoded as material inferences with explicit assumptions:

[†] (φ ∧ π) ⊃ ψ

expresses that φ defeasibly implies ψ on the assumption that π holds. Assumptions are interpreted as valid “as much as possible”. There are various ways to give a more precise meaning to this.

One such approach is offered by *Adaptive Logics*
(Batens (2007),
Strasser (2014)). An adaptive
logic AL is given by a triple consisting of

- a
*lower limit logic*LLL with a consequence relation ⊢ that is supraclassical, reflexive, monotonic, satisfies Cut, and is compact (If Γ ⊢ φ then there is a finite Γ′ ⊆ Γ such that Γ′ ⊢ φ); - a set of
*abnormalities*Ω which are specified by a logical form; and - an
*adaptive strategy*.

LLL defines the deductive core of AL in that all LLL-valid inferences are also AL-valid. AL strengthens LLL by allowing for defeasible inferences by means of the following scheme:

[‡] Where υ is an abnormal formula in Ω: if φ ⊢ ψ ∨ υ then ψ follows defeasibly from φ on the assumption that υ is false (or, equivalently, that ¬υ is true).

Where π = ¬υ, by the supraclassicality of ⊢ the antecedent of [‡] is equivalent to ⊢ (φ ∧ π) ⊃ ψ which is [†] above.

Here are some examples of concrete adaptive logics:

*Inconsistency-Adaptive Logics*(Batens (1980), Batens (1999)): In domains in which contradictions may occur it is useful to work with a paraconsistent core logic LLL that has a negation ∼ that is non-explosive (*p*, ∼*p*⊬*q*) and for which disjunctive syllogism doesn't hold (φ ∨ ψ, ∼φ ⊬ ψ and ∼φ ∨ ψ, φ ⊬ ψ). Let Ω consist of ∼-contradictions in logical atoms (*p*∧ ∼*p*). Then we have*p*∨*q*, ∼*p*⊢*q*∨ υ where υ =*p*∧ ∼*p*by the supraclassicality of ⊢. This means, disjunctive syllogism can be applied on the assumption that there is no ~-contradiction in*p*. This way LLL is significantly strengthened in a non-monotonic way.*Adaptive Logics of Inductive Generalizations*: Let LLL be CL and consider a Ω that contains, for instance, formulas of the form ∃*xP*(*x*) ∧ ¬∀*xP*(*x*). Then we have, for example,*P*(*a*) ⊢ ∀*xP*(*x*) ∨ υ where υ = ∃*xP*(*x*) ∧ ¬∀*xP*(*x*). This means we inductively generalize from*P*(*a*) to ∀*xP*(*x*) based on the assumption that the abnormality υ does not hold. (This is a simplified account compared to the more subtle logics presented in Batens (2011).)- There are numerous adaptive logics for other defeasible reasoning forms such as abductive reasoning, normative reasoning, belief revision, diagnosis, etc.

Adaptive logics implement the idea behind [‡] syntactically in
terms of a *dynamic proof theory*. A dynamic proof for an
adaptive logic of inductive generalizations may look as follows:

1. | P(a) |
PREM | ∅ |

✓2. | ∀xP(x) |
1; RC | {∃xP(x) ∧ ¬∀xP(x)} |

3. | ¬P(b) |
PREM | ∅ |

4. | ∃xP(x) ∧ ¬∀xP(x) |
1,3; RU | ∅ |

The last column of each line of the proof contains its condition,
i.e., a set of abnormalities Υ that encodes the assumptions
used to derive the formula in the second column of the line: each
υ ∈ Υ is assumed to be false. The generic rule RU
(rule unconditional) represents any inference that is licenced by
LLL. The generic rule RC (rule conditional) follows scheme [‡]
where υ is pushed to the condition of the line. Sometimes
there are good reasons to consider assumptions as violated in which
case the corresponding lines are ✓-*marked* as
retracted. This is clearly the case if the condition of a line is
Υ while for a {υ_{1}, …,
υ_{n}} ⊆ Υ, υ_{1}
∨ … ∨ υ_{n} is derived without
defeasible steps (i.e., on the condition ∅). This means that (at
least) one of the formulas in Υ is false. Thus, line 2 is
marked as retracted in view of line 4.

Not all cases of retraction are of this straightforward
kind. Various *adaptive strategies* come with marking mechanisms
to handle more complicated cases such as the one in the following
proof:

1. | P(a) |
PREM | ∅ |

2. | Q(a) |
PREM | ∅ |

3. | ¬P(b) ∨ ¬Q(c) |
PREM | ∅ |

4. | ∀xP(x) ∨ ∀xQ(x) |
1; RC | {∃xP(x) ∧ ¬∀xP(x)} |

5. | ∀xP(x) ∨ ∀xQ(x) |
2; RC | {∃xQ(x) ∧ ¬∀xQ(x)} |

6. | (∃xP(x) ∧
¬∀xP(x)) ∨
(∃xQ(x) ∧ ¬∀xQ(x)) |
1–3; RU | ∅ |

The formula ∀*xP*(*x*) ∨
∀*xQ*(*x*) is derived at line 4 and 5 on two
respective conditions: {∃*xP*(*x*) ∧
¬∀*xP*(*x*)} and {∃*xQ*(*x*)
∧ ¬∀*xQ*(*x*)}. Neither
∃*xP*(*x*) ∧ ¬∀*xP*(*x*) nor
∃*xQ*(*x*) ∧ ¬∀*xQ*(*x*) is
derivable on the condition ∅. However, both are part of the
(minimal) disjunction of abnormalities derived at line 6. According to
the *minimal abnormality strategy* the premises are interpreted
in such a way that as many abnormalities as possible are considered to
be false, which leaves us with two interpretations: one in which
∃*xP*(*x*) ∧ ¬∀*xP*(*x*)
holds while ∃*xQ*(*x*) ∧
¬∀*xQ*(*x*) is false, and another one in which
∃*xQ*(*x*) ∧ ¬∀*xQ*(*x*)
holds while ∃*xP*(*x*) ∧
¬∀*xP*(*x*) is false. In both interpretations
either the assumption of line 4 or the assumption of line 5 holds
which means that in either interpretation the defeasible inference to
∀*xP*(*x*) ∨ ∀*xQ*(*x*) goes
through. Thus, according to the minimal abnormality strategy neither
line 4 nor line 5 is marked (we omit the technical
details). The *reliability strategy* is more cautious. According
to it any line that involves an abnormality in its condition that is
part of a minimal disjunction of abnormalities derived on the
condition ∅ is marked. This means that in our example, lines 4
and 5 are marked.

Lines may get marked at specific stages of a proof just to get
unmarked at latter stages and vice versa. This mirrors the internal
dynamics of defeasible reasoning. In order to define a consequence
relation, a stable notion of derivability is needed. A formula derived
at an unmarked line *l* in an adaptive proof from a premise set
Γ is considered a *consequence of Γ* if any extension
of the proof in which *l* is marked is further extendable so that
the line is unmarked again.

Such a consequence relation can equivalently be expressed semantically
in terms of a preferential semantics (see
Section Selection Semantics). Given an LLL-model
M we can identify its *abnormal part* Ab(M) = {υ ∈
Ω ∣ M ⊧ υ} to be the set of all
abnormalities that hold in M. The selection semantics for minimal
abnormality can be phrased as follows. We order the LLL-models by M
≺ M′ if and only if Ab(M) ⊂ Ab(M′). Then we
define that φ is a semantic consequence of Γ if and only if
for all ≺-minimal LLL-models M of Γ, M ⊧ φ. (We
omit selection semantics for other strategies.)

A similar formulation makes use of maximally consistent
sets. In Makinson (2003) it was developed
under the name *default assumptions*. Given a set of assumptions
Ξ,

Γ [Ξ] φ if and only if Ξ′ ∪ Γ ⊨ φ for all Ξ′ ⊆ Ξ that are maximally consistent with Γ (i.e., Ξ′ ∪ Γ is consistent and there is no Ξ″ ⊆ Ξ such that Ξ′ ⊂ Ξ″ and Ξ″ ∪ Γ is consistent).

If we take Ξ to be {¬υ ∣ υ ∈ Ω} then we have an equivalent characterization of adaptive logics with the minimal abnormality strategy and the set of abnormalities Ω (Van De Putte (2013)).

*Conditional Entailment* is another assumption-based approach
(Geffner and Pearl (1992)). Suppose
we start with a theory T = (Δ, Γ, Λ) where Δ
= {φ_{i} → ψ_{i}
∣ *i* ∈ *I*} consists of default rules, Γ
consists of necessary facts, while Λ consists of contingent
facts. It is translated into an *assumption-based theory*
T′ = (Δ′, Γ′, Λ) as follows:

- For each φ
_{i}→ ψ_{i}∈ Δ we introduce a designated assumption constant π_{i}and encode φ_{i}→ ψ_{i}by φ_{i}∧ π_{i}⊃ ψ_{i}and the default φ_{i}→ π_{i}. The former is just our scheme [†] while the latter makes sure that assumptions are —by default— considered to hold. - The set of defaults Δ′ is {φ
_{i}→ π_{i}∣*i*∈*I*} and our background knowledge becomes Γ′ = Γ ∪ {φ_{i}∧ π_{i}⊃ ψ_{i}∣*i*∈*I*}.

Just as in the adaptive logic approach, models are compared with
respect to their abnormal parts. For a classical model M of
Γ′ ∪ Λ, Ab(M) is the set of all
π_{i} for which M ⊧
¬π_{i}. One important aspect that distinguishes
conditional entailment from adaptive logics and default assumptions,
is the fact that it implements the Specificity Principle. For this,
assumptions are ordered by means of a (smooth) relation <. Models
are then compared as follows:

M ⋖ M′ if and only if Ab(M) ≠ Ab(M′) and for all π

_{i}∈ Ab(M)∖Ab(M′) there is a π_{j}∈ Ab(M′)∖Ab(M) such that π_{i}< π_{j}.

The idea is: M is preferred over M′ if every assumption
π_{i} that doesn't hold in M but that holds in
M′ is 'compensated for' by a more specific assumption
π_{j} that holds in M but doesn't hold in M′.

For this to work, < has to include specificity relations among
assumptions. Such orders < are called *admissible* relative to
the background knowledge Γ′ if they satisfy the following
property: for every set of assumptions Π ⊆
{π_{i} ∣ *i* ∈ *I*}, if Π
violates some default φ_{j} →
π_{j} in view of the given background knowledge
Γ′ (in signs, Π, φ_{j},
Γ′ ⊨ ¬π_{j}) then there is a
π_{k} ∈ Π for which π_{k}
< π_{j}.

This is best understood when put into action. Take the case with
Tweety the penguin. We have Δ′ = {*p* →
π_{1}, *b* → π_{2}}, Γ′ =
{*p* ⊃ *b*, *p* ∧ π_{1} ⊃
¬*f*, *b* ∧ π_{2} ⊃ *f*} and
Λ = {*p*}. Take Π = {π_{2}}, then
Π,Γ′,*p* ⊨ ¬π_{1} and thus
for < to be admissible, π_{2} < π_{1}. We
have two types of models of Γ′ ∪ Λ: models
M_{1} for which M_{1} ⊧ π_{1} and
therefore M_{1} ⊧ ¬*f* and models M_{2}
for which M_{2} ⊧ π_{2} and thus
M_{2} ⊧ *f*. Note that M_{1} ⋖
M_{2} since for the only assumption in Ab(M_{1})
—namely π_{2}— there is π_{1} ∈
Ab(M_{2})∖Ab(M_{1}) for which π_{2}
< π_{1}.

Analogous to adaptive logics with the minimal abnormality strategy, conditional entailment is defined via ⋖-minimal models:

(Δ′, Γ′, Λ) φ if and only if for each admissible < (relative to Γ′) and all ⋖-minimal models M of Γ′ ∪ Λ, M ⊧ φ.

In our example, ¬*f* is a conditionally entailed since all
⋖-minimal models have the same abnormal part as M_{1}.

A consequence of expressing defeasible inferences via material
implication in assumption-based approaches is that defeasible
inferences are *contrapositable*. Clearly, if φ ∧ π
⊃ ψ then ¬ψ ∧ π ⊃ ¬φ. As a
consequence, formalisms such as default logic have a more greedy style
of applying default rules. We demonstrate this with conditional
entailment. Consider a theory consisting of the
defaults *p*_{1}
→ *p*_{2}, *p*_{2}
→ *p*_{3}, *p*_{3}
→ *p*_{4} and the factual information Λ =
{*p*_{1}, ¬*p*_{4}}
(where *p _{i}* are logical atoms). In assumption-based
approaches such as conditional entailment the defeasible rules will be
encoded as

*p*

_{1}∧ π

_{1}⊃

*p*

_{2},

*p*

_{2}∧ π

_{2}⊃

*p*

_{3}, and

*p*

_{3}∧ π

_{3}⊃

*p*

_{4}. It can easily be seen that < = ∅ is an admissible ordering which means that for instance a model M with Ab(M) = {π

_{1}} is ⋖-minimal. In such a model we have M ⊧ ¬

*p*

_{3}and M ⊧ ¬

*p*

_{2}by reasoning backwards via contraposition from ¬

*p*

_{4}∧ π

_{3}to ¬

*p*

_{3}and from ¬

*p*

_{3}∧ π

_{2}to ¬

*p*

_{2}. This means that neither

*p*

_{2}nor

*p*

_{3}is conditionally entailed.

The situation is different in default logic where
both *p*_{2} and *p*_{3} are derivable. The
reasoning follows a greedy policy in applying default rules: whenever
a rule is applicable (i.e., its antecedent holds by the currently held
beliefs Ξ and its consequent doesn't contradict with Ξ) it is
applied. There is disagreement among scholars whether and when
contraposition is a desirable property for defeasible inferences
(e.g., Caminada (2008),
Prakken (2012)).

## 4. Non-monotonic logic and human reasoning

In view of the fact that test subjects seem to perform very poorly in various paradigmatic reasoning tests (e.g., Wason's Selection Task (Wason (1966)) or the Supression Task (Byrne (1989))), main streams in the psychology of reasoning have traditionally ascribed to logic at best a subordinate role in human reasoning. In recent years this assessment has been criticized as the result of evaluating performances in tests against the standard of classical logic whereas other standards based on probabilistic considerations or on NMLs have been argued to be more appropriate.

This resulted in the rise of a new probabilistic paradigm
(Oaksford and Chater (2007),
Pfeifer and Douven (2014))
where probability theory provides a calculus for rational
belief update. Although the program is sometimes phrased in decidedly
anti-logicist terms,^{[7]}
logic is here usually understood as
monotonic and deductive. The relation to NML is less clear and it has
been argued that there are close connections especially to
probabilistic accounts of NML (Over (2009),
Pfeifer and Kleiter (2009)).
Politzer and Bonnefon (2009)
warn against the premature acceptance of the probabilistic
paradigm in view of the rich variety of alternatives such as
possibility measures, plausibility measures, etc. (see
also above).

Another argument for the relevance of NML is advocated
in Stenning and Van Lambalgen (2008)
who distinguish between reasoning *to* and
reasoning *from* an interpretation. In the former process agents
establish a logical form that is relative both to the specific context
in which the reasoning takes place and to the agent's goals. When
establishing a logical form agents choose—inter alia—a
formal language, a semantics (e.g., extensional vs. intensional), a
notion of validity, etc. Once a logical form is established, agents
engage in lawlike rule-based inferences which are based on this
form. It is argued that in the majority of cases in standard reasoning
tasks, subjects use non-monontonic logical forms that are based on
closed world assumptions.

Nonmonotonic logicians often state that their motivation stems from observing the defeasible structure of actual commonsense reasoning. Empirical studies have been explicitly cited as both inspiration for working on NMLs and as standards against which to evaluate NMLs. However, it has also been noted that logicians often rely too much on their own intuitions without critically assessing them against the background of empirical studies (Pelletier and Elio (1997)).

Various studies investigate their test subjects' tendency to reason according to specific inference principles of NMLs. Most studies support the descriptive adequacy of the rules of system P. There are, however, some open or controversial issues. For instance, while some studies report results suggestive of the adequacy of weakened monotonicity principles such as Cautious Monotonicity (Schurz (2005), Neves et al. (2002), Pfeifer and Kleiter (2005)) and Rational Monotonicity (Neves et al. (2002)), Benferhat et al. (2005) report mixed results. Specificity considerations play a role in the reasoning process of test subjects in Schurz (2005), whereas according to Ford and Billington (2000) they do not. Benferhat et al. (2005) are specifically interested in the question whether the responses of their test subjects corresponded better to Lexicographic Closure or to Rational Closure. While the results were not fully conclusive they still suggest a preference for the former.

Pelletier and Elio (1994)
investigate various relevant factors that influence subjects'
reasoning about exceptions of defaults or inheritance relations. Their
study makes use of the benchmark problems for defeasible reasoning
proposed in Lifschitz (1989). It is, for
instance, observed that the exceptional status of an object *A*
with respect to some default is more likely to spread to other objects
if they share properties with *A* that may play a role in
explaining the exceptional status. For example, when confronted with a
student club that violates the default that student clubs only allow
for student members, subjects are more likely to ascribe this
exceptional status also to another club if they learn that both clubs
have been struggling to maintain minimum membership requirements.

The question of the descriptive adequacy of NMLs to human reasoning is also related to questions concerning the nature and limits of cognitive modules in view of which agents are capable of logical reasoning. For instance, the question arises, whether such modules could be realized on a neurological level. Concerning the former question there are successful representations of NMLs in terms of neural networks (see Stenning and Van Lambalgen (2008) for logic programming with closed world assumptions and Leitgeb (2001) for NMLs in the tradition of Selection Semantics).

## 5. Conclusion

There are three major issues connected with the development of logical
frameworks that can adequately represent defeasible reasoning:
(*i*) materially adequacy; (*ii*) formal properties; and
(*iii*) complexity. A non-monotonic formalism is material
adequate to the extent to which it captures examples of defeasible
reasoning and to the extent to which it has intuitive properties. The
question of formal properties has to do with the degree to which the
formalism gives rise to a consequence relation that satisfies
desirable theoretic properties such as the above mentioned
Reflexivity, Cut, and Cautious Monotony. The third set of issues has
to do with computational complexity of the most basic questions
concerning the framework.

There is a potential tension between (*i*) and (*ii*): the
desire to capture a broad range of intuitions can lead to *ad
hoc* solutions that can sometimes undermine the desirable formal
properties of the framework. In general, the development of NMLs and
related formalisms has been driven, since its inception, by
consideration (*i*) and has relied on a rich and well-chosen
array of examples. Of course, there is some question as to whether any
single framework can aspire to be universal in this respect.

More recently, researchers have started paying attention to
consideration (*ii*), looking at the extent to which NMLs have
generated well-behaved relations of logical
consequence. As Makinson (1994) points
out, practitioners of the field have encountered mixed success. In
particular, one abstract property, Cautious Monotony, appears at the
same time to be crucial and elusive for many of the frameworks to be
found in the literature. This is a fact that is perhaps to be traced
back, at least in part, to the above-mentioned tension between the
requirement of material adequacy and the need to generate a
well-behaved consequence relation.

The complexity issue appears to be the most difficult among the ones that have been singled out. NMLs appear to be stubbornly intractable with respect to the corresponding problem for classical logic. This is clear in the case of default logic, given the ubiquitous consistency checks. But besides consistency checks, there are other, often overlooked, sources of complexity that are purely combinatorial. Other forms of non-monotonic reasoning, besides default logic, are far from immune from these combinatorial roots of intractability. Although some important work has been done trying to make various non-monotonic formalism more tractable, this is perhaps the problem on which progress has been slowest in coming.

## Bibliography

- Adams, Ernest W., 1975.
*The Logic of Conditionals*. Dordrecht: D. Reidel Publishing Co. - Alferes, Jose Julio, Damasio,
Carlos Viegas, & Pereira, Luis Moniz, 1995. A
Logic Programming System for Nonmonotonic Reasoning.
*Journal of Automated Reasoning*, 14(1): 93–147. - Antonelli, Gian Aldo, 1999. A
directly cautious theory of defeasible consequence for default logic
via the notion of general extension.
*Artificial Intelligence*, 109(1): 71–109. - –––, 1997.
Defeasible inheritance on cyclic networks.
*Artificial Intelligence*, 92(1): 1–23. - Arieli, Ofer, & Avron,
Arnon, 2000. General Patterns for Nonmonotonic Reasoning: From
Basic Entailments to Plausible Relations.
*Logic Journal of the IGPL*, 8: 119–148. - Asher, Nicholas, & Morreau,
Michael, 1991. Commonsense entailment: A modal theory of
nonmonotonic reasoning. In
*Logics in AI*, Berlin: Springer, pp. 1–30. - Batens, Diderik, 1980. Paraconsistent
extensional propositional logics.
*Logique at Analyse*, 90–91: 195–234. - Batens, Diderik, 1999.
Inconsistency-Adaptive Logics. In
*Logic at Work. Essays Dedicated to the Memory of Helena Rasiowa*, Heidelberg, New York: Physica Verlag (Springer), pp. 445–472. - Batens, Diderik, 2004. The need for
adaptive logics in epistemology. In
*Logic, epistemology, and the unity of science*. Berlin: Springer, pp. 459–485. - Batens, Diderik, 2007. A Universal
Logic Approach to Adaptive Logics.
*Logica Universalis*, 1: 221–242. - Batens, Diderik, 2011. Logics for
qualitative inductive generalization.
*Studia Logica*, 97(1): pp. 61–80. - Benferhat, Salem, Dubier, Didier,
& Prade, Henri, 1997. Some Syntactic Approaches to the
Handling of Inconsistent Knowledge Basis: A Comparative Study. Part I:
The Flat Case.
*Studia Logica*, 58: 17–45. - Benferhat, Salem, Dubois, Didier,
& Prade, Henri, 1999. Possibilistic and standard
probabilistic semantics of conditional knowledge bases.
*Journal of Logic and Computation*, 9(6): 873–895. - Benferhat, Salem, Bonnefon,
Jean F, & da Silva Neves, Rui, 2005. An
overview of possibilistic handling of default reasoning, with
experimental studies.
*Synthese*, 146(1–2): 53–70. - Boutilier, Craig, 1990.
Conditional Logics of Normality as Modal Systems.
*AAAI*(Volume 90), pp. 594–599. - Brewka, Gerhard, & Eiter,
Thomas, 2000. Prioritizing Default Logic. In
*Intellectics and Computational Logic*, Applied Logic Series (Volume 19), Dordrecht: Kluwer, 27–45. - Byrne, Ruth M.J., 1989. Suppressing
valid inferences with conditionals.
*Cognition*, 31(1): 61–83. - Caminada, M., 2008. On the issue of
contraposition of defeasible rules.
*Frontiers in Artificial Intelligence and Applications*, 172: 109–115. - Delgrande, James, Schaub, Torsten,
Tompits, Hans, & Wang, Kewen, 2004. A classification and
survey of preference handling approaches in nonmonotonic reasoning.
*Computational Intelligence*, 20(2): 308–334. - Delgrande, James P., 1987. A
first-order conditional logic for prototypical properties.
*Artificial Intelligence*, 33(1): 105–130. - Delgrande, James P., 1998. On
first-order conditional logics.
*Artificial Intelligence*, 105(1): 105–137. - Delgrande, James P, &
Schaub, Torsten, 2000. Expressing preferences in default logic.
*Artificial Intelligence*, 123(1): 41–87. - Dov, Gabbay, Hogger, C., &
Robinson, J. (eds.), 1994.
*Handbook of Logic in Artificial Intelligence and Logic Programming*(Volume 3), Oxford and New York: Oxford University Press. - Dubois, Didier, & Prade,
Henri, 1990. An introduction to possibilistic and fuzzy logics.
In
*Readings in Uncertain Reasoning*. San Francisco: Morgan Kaufmann Publishers Inc., pp. 742–761. - Dung, Phan Minh, 1995. On the
Acceptability of Arguments and its Fundamental Role in Nonmonotonic
Reasoning, Logic Programming and n-Person Games.
*Artifical Intelligence*, 77: 321–358. - Dung, P.M., Kowalski, R.A., & Toni,
F., 2009. Assumption-based argumentation.
*Argumentation in Artificial Intelligence*, 199–218. - Ford, Marilyn, 2004. System LS: A
Three-Tiered Nonmonotonic Reasoning System.
*Computational Intelligence*, 20(1): 89–108. - Ford, Marilyn, & Billington,
David, 2000. Strategies in human nonmonotonic reasoning.
*Computational Intelligence*, 16(3): 446–468. - Friedman, Nir, & Halpern,
Joseph Y., 1996. Plausibility measures and default reasoning.
*Journal of the ACM*, 48: 1297–1304. - Friedman, Nir, Halpern,
Joseph Y., & Koller, Daphne, 2000. First-order
conditional logic for default reasoning revisited.
*ACM Trans. Comput. Logic*, 1(October): 175–207. - Gabbay, Dov M., 1985. Theoretical
foundations for non-monotonic reasoning in expert systems.
*Logics and models of concurrent systems*. New York: Springer-Verlag, pp. 439–457. - Geffner, Hector, & Pearl,
Judea, 1992. Conditional entailment: bridging two approaches to
default reasoning.
*Artifical Intelligence*, 53(2–3): 209–244. - Gelfond, Michael, &
Lifschitz, Vladimir, 1988. The stable model semantics for logic
programming. In
*ICLP/SLP*(Volume 88), pp. 1070–1080. - Gilio, Angelo, 2002. Probabilistic
reasoning under coherence in System P.
*Annals of Mathematics and Artificial Intelligence*, 34(1–3): 5–34. - Ginsberg, Matt, 1994.
*Essentials of Artificial Intelligence*. San Francisco: Morgan Kaufmann Publishers Inc. - Ginsberg, Matthew L. (ed.),
1987.
*Readings in nonmonotonic reasoning*. San Francisco: Morgan Kaufmann. - Giordano, Laura, Gliozzi,
Valentina, Olivetti, Nicola, & Pozzato, Gian Luca, 2009.
Analytic tableaux calculi for KLM logics of nonmonotonic reasoning.
*ACM Transactions on Computational Logic (TOCL)*, 10(3): 18. - Goldszmidt, Moisés, &
Pearl, Judea, 1992. Rank-based Systems: A Simple Approach to
Belief Revision, Belief Update, and Reasoning about Evidence and
Actions. In
*Proceedings of the Third International Conference on Knowledge Representation and Reasoning*. San Francisco: Morgan Kaufmann, pp. 661–672. - Goldzsmidt, Moisés,
Morris, Paul, & Pearl, Judea, 1993. A Maximum Entropy
Approach to Nonmonotonic Reasoning.
*IEEE Transactions on Pattern Analysis and Machine Intelligence*, 15(3): 220–232. - Horty, John, 2007. Defaults with
Priorities.
*Journal of Philosophical Logic*, 36: 367–413. - Horty, John F., 1994. Some direct
theories of nonmonotonic inheritance. In Gabbay, Dov M., Hogger,
Christopher J., & Robinson, J. A. (eds.),
*Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3: Nonmonotonic Reasoning and Uncertain Reasoning*. Oxford: Oxford University Press, pp. 111–187. - Horty, John F., 2002. Skepticism
and floating conclusions.
*Artifical Intelligence*, 135(1–2): 55–72. - Jeffry, Pelletier Francis,
& Renee, Elio, 1994. On Relevance in Nonmonotonic Reasoning:
Some Empirical Studies. In Russ, Greiner, & Devika, Subramanian
(eds.),
*Relevance: AAAI 1994 Fall Symposium Series*. Palo Alto: AAAI Press, pp. 64–67. - Konolige, Kurt, 1988. On the
relation between default and autoepistemic logic.
*Artifical Intelligence*, 35(3): 343–382. - Koons, Robert, 2014. Defeasible
Reasoning. In
*The Stanford Encyclopedia of Philosophy*(Spring 2014 Edition), Edward N. Zalta (ed.), URL = <http://plato.stanford.edu/archives/spr2014/entries/reasoning-defeasible/>. - Kraus, Sarit, Lehmann, Daniel, &
Magidor, Menachem, 1990. Nonmonotonic Reasoning, Preferential
Models and Cumulative Logics.
*Artifical Intelligence*, 44: 167–207. - Kripke, Saul, 1975. Outline of a
Theory of Truth.
*Journal of Philosophy*, 72: 690–716. - Lehmann, Daniel J., 1995.
Another Perspective on Default Reasoning.
*Annals of Mathematics and Artificial Intelligence*, 15(1): 61–82. - Lehmann, Daniel J., & Magidor,
Menachem, 1990. Preferential logics: the predicate calculus case.
In
*Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge*, San Francisco: Morgan Kaufmann Publishers Inc., pp. 57–72. - Lehmann, Daniel J., &
Magidor, Menachem, 1992. What does a conditional knowledge base
entail?
*Artificial Intelligence*, 55(1): 1–60. - Leitgeb, Hannes, 2001. Nonmonotonic
reasoning by inhibition nets.
*Artifical Intelligence*, 128(May): 161–201. - Lifschitz, Vladimir, 1989. Benchmark
problems for formal nonmonotonic reasoning. In
*Non-Monotonic Reasoning*. Berlin: Springer, pp. 202–219. - Lin, Fangzhen, & Shoham, Yoav,
1990. Epistemic semantics for fixed-points non-monotonic logics. In
*Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning About Knowledge (TARK'90)*, Pacific Grove, CA: Morgan Kaufmann Publishers Inc, pp. 111–120. - Lukaszewicz, Witold, 1988.
Considerations on default logic: an alternative approach.
*Computational intelligence*, 4(1): 1–16. - Makinson, David, 1994. General
patterns in nonmonotonic reasoning. In:
*Handbook of Logic in Artificial Intelligence and Logic Programming, vol. III*, D. Gabbay, C. Hogger, J.A. Robinson (eds.), pp. 35–110, Oxford: Oxford University Press. - Makinson, David, 2003. Bridges
between classical and nonmonotonic logic.
*Logic Journal of IGPL*, 11(1): 69–96. - Makinson, David, &
Gärdenfors, Peter, 1991. Relations between the logic of
theory change and nonmonotonic logic.
*The logic of theory change*, Berlin: Springer, pp. 183–205. - Makinson, David, &
Schlechta, Karl, 1991. Floating conclusions and zombie paths: two
deep difficulties in the “directly skeptical” approach to
defeasible inheritance nets.
*Artifical Intelligence*, 48(2): 199–209. - McCarthy, J., 1980.
Circumscription – A Form of Non-Monotonic Reasoning.
*Artifical Intelligence*, 13: 27–29. - Moore, Robert C., 1984.
Possible-World Semantics for Autoepistemic Logic. In
*Proceedings of the Workshop on non-monotonic reasoning*, AAAI, pp. 344–354. - Moore, Robert C., 1985. Semantical
considerations on nonmonotonic logic.
*Artifical Intelligence*, 25(1): 75–94. - Neves, Rui Da Silva, Bonnefon,
Jean-François, & Raufaste, Eric, 2002. An empirical
test of patterns for nonmonotonic inference.
*Annals of Mathematics and Artificial Intelligence*, 34(1–3): 107–130. - Nute, D., 1994. Defeasible logics. In
*Handbook of Logic in Artificial Intelligence and Logic Programming*(Vol. 3). Oxford: Oxford University Press, pp. 353–395. - Oaksford, Mike, & Chater,
Nick, 2007.
*Bayesian rationality the probabilistic approach to human reasoning*. Oxford: Oxford University Press. - Oaksford, Mike, & Chater,
Nick, 2009. Précis of Bayesian rationality: The
probabilistic approach to human reasoning.
*Behavioral and Brain Sciences*, 32(01): 69–84. - Orlowska, Ewa (ed.), 1999.
*Logic at Work. Essays Dedicated to the Memory of Helena Rasiowa*. Heidelberg, New York: Physica Verlag (Springer). - Over, David E., 2009. New paradigm
psychology of reasoning.
*Thinking & Reasoning*, 15(4): 431–438. - Pearl, Judea, 1988.
*Probabilistic reasoning in intelligent systems: networks of plausible inference*. San Francisco: Morgan Kaufmann. - Pearl, Judea, 1989. Probabilistic
semantics for nonmonotonic reasoning: a survey. In
*Proceedings of the first international conference on Principles of knowledge representation and reasoning*. San Francisco: Morgan Kaufmann Publishers, pp. 505–516. - Pearl, Judea, 1990. System Z: a natural
ordering of defaults with tractable applications to nonmonotonic
reasoning. In
*TARK '90: Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge*. San Francisco: Morgan Kaufmann Publishers, pp. 121–135. - Pelletier, Francis Jeffry,
& Elio, Renée, 1997. What should default reasoning be,
by default?
*Computational Intelligence*, 13(2): 165–187. - Pfeifer, Niki, & Douven,
Igor, 2014. Formal Epistemology and the New Paradigm Psychology
of Reasoning.
*Review of Philosophy and Psychology*, 5(2): 199–221. - Pfeifer, Niki, & Kleiter,
Gernot D., 2005. Coherence and nonmonotonicity in human
reasoning.
*Synthese*, 146(1–2): 93–109. - Pfeifer, Niki, & Kleiter,
Gernot D., 2009. Mental probability logic.
*Behavioral and Brain Sciences*, 32(01): 98–99. - Politzer, Guy, & Bonnefon,
Jean-François, 2009. Let us not put the probabilistic cart
before the uncertainty bull.
*Behavioral and Brain Sciences*, 32(01): 100–101. - Pollock, John, 1991. A Theory of
Defeasible Reasoning.
*International Journal of Intelligent Systems*, 6: 33–54. - Pollock, John, 1995.
*Cognitive Carpentry*, Cambridge, MA: Bradford/MIT Press. - Pollock, John, 2008. Defeasible
Reasoning. In
*Reasoning: Studies of Human Inference and its Foundations*, J. E. Adler and L. J. Rips (eds.), Cambridge: Cambridge University Press, pp. 451–470. - Poole, David, 1985. On the Comparison
of Theories: Preferring the Most Specific Explanation.
In
*IJCAI*(Volume 85), pp. 144–147. - Prakken, H., 2010. An abstract
framework for argumentation with structured arguments.
*Argument & Computation*, 1(2): 93–124. - Prakken, H., 2012. Some reflections on
two current trends in formal argumentation. In A. Artikis, et al.
(ed.),
*Logic Programs, Norms and Action*. Dordrecht: Springer, pp. 249–272. - Prakken, Henry, & Vreeswijk,
Gerard A. W., 2002.
*Logics for Defeasible Argumentation*(Vol. 4), Dordrecht: Kluwer, pp. 219–318. - Reiter, Raymond, 1980. A
Logic for Default Reasoning.
*Artifical Intelligence*, 13: 81–132. - Schurz, Gerhard, 2005. Non-monotonic
reasoning from an evolution-theoretic perspective: Ontic, logical and
cognitive foundations.
*Synthese*, 146(1–2): 37–51. - Shoham, Yoav, 1987. A Semantical
Approach to Nonmonotonic Logics. In Ginsberg,
M. L. (ed.),
*Readings in Non-Monotonic Reasoning*. Los Altos, CA: Morgan Kaufmann, pp. 227–249. - Simari, Guillermo R, & Loui,
Ronald P., 1992. A mathematical treatment of defeasible
reasoning and its implementation.
*Artificial intelligence*, 53(2): 125–157. - Stalnaker, Robert, 1993. A note on
non-monotonic modal logic.
*Artificial Intelligence*, 64(2): 183–196. - Stalnaker, Robert, 1994. What is a
nonmonotonic consequence relation?
*Fundamenta Informaticae*, 21(1): 7–21. - Stenning, Keith, &
Van Lambalgen, Michiel, 2008.
*Human reasoning and cognitive science*. Cambridge, MA: MIT Press. - Straßer, Christian, 2014.
*Adaptive Logic and Defeasible Reasoning. Applications in Argumentation, Normative Reasoning and Default Reasoning*(Trends in Logic, Volume 38). Dordrecht: Springer. - Touretzky, David S.,
Thomason, Richmond H., & Horty, John F., 1991. A
Skeptic's Menagerie: Conflictors, Preemptors, Reinstaters, and Zombies
in Nonmonotonic Inheritance.
In
*IJCAI*, pp. 478–485 of. - Van De Putte, Frederik, 2013.
Default Assumptions and Selection Functions: A Generic Framework for
Non-monotonic Logics. In
*Advances in Artificial Intelligence and Its Applications*, Dordrecht: Springer, pp. 54–67. - Verheij, Bart, 1996.
*Rules, Reasons, Arguments. Formal Studies of Argumentation and Defeat*, Ph.D. thesis, Universiteit Maastricht. - Wason, P. C., 1966. Reasoning. in
B. Foss (ed.),
*New horizons in psychology I*, Harmondsworth: Penguin, pp. 135–151.

## Academic Tools

How to cite this entry. Preview the PDF version of this entry at the Friends of the SEP Society. Look up this entry topic at the Indiana Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers, with links to its database.

## Other Internet Resources

[Please contact the author with suggestions.]