8.3 Characterizing Default Reasoning

In this section, I consider an axiomatic characterization of default reasoning. To start with, consider a very simple language for representing defaults. Given a set Φ of primitive propositions, let the language ^def (Φ) consist of all formulas of the form φ→ψ, where φ, ψ ∈ ^Prop (Φ); that is, φ and ψ are propositional formulas over Φ. Notice that ^def is not closed under negation or disjunction; for example, (p → q) is not a formula in ^def, nor is (p → q) ⇔ (p → (q ∨ q′)) (although, of course, p → q and p → (q ⇔ q′) are in ^def).

The formula φ → ψ can be read in various ways, depending on the application. For example, it can be read as "if φ (is the case) then typically ψ (is the case)," "if φ, then normally ψ," "if φ, then by default ψ," and "if φ, then ψ is very likely." Thus, the default statement "birds typically fly" is represented as bird → fly. ^def can also be used for counterfactual reasoning, in which case φ → ψ is interpreted as "if φ were true, then ψ would be true."

All these readings are similar in spirit to the reading of the formula φ ⇔ ψ in propositional logic as "if φ then ψ." How do the properties of ⇔ (often called a material conditional or material implication) and → compare? More generally, what properties should → have? That depends to some extent on how → is interpreted. We should not expect default reasoning and counterfactual reasoning to have the same properties (although, as we shall see, they do have a number of properties in common). In this section, I focus on default reasoning.

There has in fact been some disagreement in the literature as to what properties → should have. However, there seems to be some consensus on the following set of six core properties, which make up the axiom system P:

LLE. If φ ⇔ φ′ is a propositional tautology, then from φ → ψ infer φ′ → ψ (left logical equivalence).

RW. If ψ ⇔ ψ′ is a propositional tautology, then from φ → ψ infer φ → ψ′ (right weakening).

REF. φ → φ (reflexivity).

AND. From φ → ψ₁ and φ → ψ₂ infer φ → ψ₁ ∧ ∧₂.

OR. From φ₁ → ∨ and φ₂ → ψ infer φ₁ ∨ φ₂ → ψ.

CM. From φ → ψ₁ and φ → ψ₂ infer φ ∧ ψ₂ → ψ₁ (cautious monotonicity).

The first three properties of P seem noncontroversial. If φ and φ′ are logically equivalent, then surely if ψ follows by default from φ, then it should also follow by default from φ′. Similarly, if ψ follows from φ by default, and ψ logically implies ψ′, then surely ψ′ should follow from φ by default as well. Finally, reflexivity just says that φ follows from itself.

The latter three properties get more into the heart of default reasoning. The AND rule says that defaults are closed under conjunction. For example, if an agent sees a bird, she may want to conclude that it flies. She may also want to conclude that it has wings. The AND rule allows her to put these two conclusions together and conclude that, by default, birds both fly and have wings.

The OR rule corresponds to reasoning by cases. If red birds typically fly ((red ∧ bird) → fly) and nonred birds typically fly (( red ∧ bird) → fly), then birds typically fly, no matter what color they are. Note that the OR rule actually gives only ((red ∧ bird) ∨ ( red ∧ bird)) → fly here. The conclusion bird → fly requires LLE, using the fact that bird ⇔ ((red ∧ bird) ∨ ( red ∧ bird)) is a propositional tautology.

To understand cautious monotonicity, note that one of the most important properties of the material conditional is that it is monotonic. Getting extra information never results in conclusions being withdrawn. For example, if φ ⇔ ψ is true under some truth assignment, then so is φ ∧ φ′ ⇔ ψ, no matter what φ′ is (Exercise 8.12). On the other hand, default reasoning is not always monotonic. From bird → fly it does not follow that bird ∧ penguin → fly. Discovering that a bird is a penguin should cause the retraction of the conclusion that it flies.

Cautious monotonicity captures one instance when monotonicity seems reasonable. If both ψ₁ and ψ₂ follow from φ by default, then discovering ψ₂ should not cause the retraction of the conclusion ψ₁. For example, if birds typically fly and birds typically have wings, then it seems reasonable to conclude that birds that have wings typically fly.

All the properties of P hold if → is interpreted as ⇔, the material conditional (Exercise 8.13). However, this interpretation leads to unwarranted conclusions, as the following example shows:

Example 8.3.1

Consider the following collection of defaults:

It is easy to see that if → is interpreted as ⇔, then penguin must be false (Exercise 8.14). But then, for example, it is possible to conclude penguin → fly; this is surely an undesirable conclusion!

In light of this example, I focus here on interpretations of → that allow some degree of nontrivial nonmonotonicity.

If Σ is a finite set of formulas in ^def, write Σ ⊢_P φ → ψ if φ → ψ can be deduced from Σ using the rules and axioms of P, that is, if there is a sequence of formulas in ^def, each of which is either an instance of REF (the only axiom in P), a formula in Σ, or follows from previous formulas by an application of an inference rule in P. Roughly speaking, Σ ⊢_P φ → ψ is equivalent to ⊢_P ∧Σ ⇔ (φ → ψ), where ∧Σ denotes the conjunction of the formulas in Σ. The problem with the latter formulation is that ∧Σ ⇔ (φ → ψ) is not a formula in ^def, since ^def is not closed under conjunction and implication. In Section 8.6, I consider a richer language that allows such formulas.