Default logic

Default logic is a non-monotonic logic proposed by Ray Reiter. Default logic seeks to better represent human methods of reasoning. It behaves like standard logic when complete information is available, but lets us infer things in the presence of incomplete information. Where in standard logic knowing that something is a bird tells us nothing of whether or not it can fly (since some birds do not fly, and many things that are not birds also fly), we have an intuitive notion that birds fly. Default logic lets us infer, barring evidence to the contrary, that anything which is a bird also flies.

Formal Definition of a Default Theory

A default theory consists of a pair $\langle D,W\rangle$, where $W$ is a set of expressions in first-order predicate calculus, called the background theory, and $D$ is a set of default inference rules called default rules. These are of the form

${\frac {Prerequisite(X):Justification_{1}(X),...,Justification_{n}(X)}{Conclusion(X)}}$

This rule means that if, for some $a$, we know that $Prerequisite(a)$ is true, and each of $Justification_{i}(a)$ is consistent with our current knowledge, then $Conclusion(a)$ is true.

Some Default Theories

Returning to the example of birds flying, we can define our default rules as

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

and our initial premises as D = { Bird(Condor), Bird(Penguin), ¬Flies(Penguin), Flies(Airplane) }.

(In our simple theory, our consistency requirements are identical to the conclusion. This is not always the case in more complicated theories.)

From these, we can safely infer that a condor flies, because a condor is a bird and we don't know that condors can't fly. However we cannot infer that penguins fly, because it is inconsistent with our knowledge that penguins can't fly. 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 default a 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 $Pacifist(Nixon)$ is true, and one in which $Pacifist(Nixon)$ 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.