Default logic

Default logic is a non-monotonic logic proposed by Ray Reiter to formalize the way humans reason using default assumptions.

In default logic, one can express facts like “by default, something is true”; by contrast, standard logic can only express that something is true or false. This is a problem because inference is often done using facts that are only true in the majority of cases, but not always. For example, standard logic can express the fact that “everything that is a bird flies”, but such a rule would be inconsistent with the fact that penguins are birds that do not fly. Default logic can instead express “everything that is a bird, by default, flies”. Such a rule allows for concluding that a condor flies (because it is a bird), but is not inconsistent with the fact that a penguin does not fly.

Contents

1 Formal Definition of a Default Theory

2 Some Default Theories

3 Semantics

4 Restrictions

5 References

Formal Definition of a Default Theory

A default theory consists of a pair $\langle D, W \rangle$ , where $W$ is a set of logical formulae, called the background theory, and $D$ is a set of default inference rules called default rules, each one of the form:

$\frac{Prerequisite : Justification_1, ..., Justification_n}{Conclusion}$

This default rule expresses that if we know that $P r e r e q u i s i t e$ is true, and each of $J u s t i f i c a t i o n i$ is consistent with our current knowledge, then $C o n c l u s i o n$ is true.

The logical formulae in $W$ , and all formulae in a default were originally assumed to be in first-order logic, but can potentially be formulae in an arbitrary formal logic. The case in which they are formulae in propositional logic is one of the most studied.

Some Default Theories

The example of birds can be formalized using the following first-order default:

$D = \left\{ \frac{Bird(X) : Flies(X)}{Flies(X)} \right\}$

This default has a single justification, which is equal to its conclusion; this is not always the case. The background theory contains facts that are known. In the case of birds, a background theory might be the following one:

$W = \{ Bird(Condor), Bird(Penguin), \neg Flies(Penguin), Flies(Airplane) \}$ .

The default rule allows concluding that a condor flies because the precondition of the default $B i r d (C o n d o r)$ is true and its justification $F l i e s (C o n d o r)$ is not inconsistent with what is currently known.

On the contrary, $B i r d (P e n g u i n)$ does not allow concluding $F l i e s (P e n g u i n)$ . Indeed, even if the precondition of the default $B i r d (P e n g u i n)$ is true, the default rule cannot be applied because its justification $F l i e s (P e n g u i n)$ is inconsistent with what is known.

As in standard logic we cannot say anything about whether or not an airplane is a bird because we have no inference rules available to do that, default or otherwise.

The computer language Prolog uses a sort of default assumption when leading with negatation: if a negative atom cannot be proved to be true, then it is assumed to be false. This assumption is similar to the following default rule:

$D = \left\{ \frac{ : {\neg}X}{{\neg}X} \right\}$

Note, however, that Prolog uses the so-called negation as failure : when the interpreter has to evaluate the atom $\neg X$ , it tries to prove that $X$ is true, and conclude that $\neg X$ is true if it fails. In default logic, instead, a default having $\neg X$ as a justification can only be applied if $\neg X$ is consistent with the current knowledge.

Semantics

Semantics of default logic is defined in terms of extensions. Each extension represents the result of applying a number of default rules from the initial background theory until no other default rule can be applied. Default rules may be applied in different order, and this may lead to different extensions. The Nixon diamond example shows an example of a default theory with two extensions:

$\left\langle \left\{ \frac{Republican(X):\neg Pacifist(X)}{Pacifist(X)}, \frac{Quaker(X):Pacifist(X)}{Pacifist(X)} \right\}, \left\{Republican(Nixon), Quaker(Nixon)\right\} \right\rangle$

Since Nixon is both a republican and a quaker, both defaults can be applied. However, applying the first default leads to the conclusion that Nixon is not a pacifist, which makes the second default not applicable. In the same way, applying the second default we obtain that Nixon is a pacifist, thus making the first default not applicable. This particular default theory has therefore two extensions, one in which $P a c i f i s t (N i x o n)$ is true, and one in which $P a c i f i s t (N i x o n)$ is false.

In general, a default theory may have zero, one, or more extensions. The following is a default theory with no extensions:

$\left\langle \left\{ \frac{:A(b)}{\neg A(b)} \right\}, \emptyset \right\rangle$

Since $A (b)$ is consistent with the background theory, the default can be applied, thus leading to the conclusion that $A (b)$ is false. This result undermines the assumption that has been made for applying the first default. In default logic, according to the original semantics by Ray Reiter , the above default theory has no extensions.

Several other semantics for default logics have been defined. In some of them, every default theory has at least an extension.

Restrictions

A default with no prerequisite is called categorical. A default with a single justification that is equivalent to the conclusion is called normal. If every justification entails the conclusion the default is called semi-normal.

A default theory in which all defaults are normal is guaranteed to have at least one extensions. Furthermore, different extensions of the same default theory are mutually inconsistent, i.e., two extensions of the same normal theory are inconsistent with each other.

References

Schmidt, Charles F. Default Logic. Retrieved August 10th. 2004.
Ramsay, Allan (1999). Default Logic. Retrieved August 10th. 2004.

Categories: Logic