Default logic

Default logic is a non-monotonic logic proposed by Ray Reiter to formalize the human reasoning with 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 that something is false. This is a problem because humans often do inference using facts that are true only in the majority of cases, but not always. A classical example of a fact that cannot be easily expressed in standard logic is that “birds typically fly”. This rule can be expressed in standard logic either by “all birds fly”, which is inconsistent with the fact that penguins do not fly, or by “all birds that are not penguins and not ostriches and ... fly”, which requires all exceptions to the default rule to be specified. Default logic aims at formalizing inference rules like this one without explicitely mention every exception to them.

Syntax of Default Logic

A default theory is a pair $\langle D,W\rangle$. $W$ is a set of logical formulae, called the background theory, that formalize the facts that are known for sure. $D$ is a set of default inference rules called default rules, each one of the form:

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

Such a default rule formalize the fact that, if we know that $Prerequisite$ is true, and each of $Justification_{i}$ is consistent with our current knowledge, then $Conclusion$ 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.

Examples

The default rule “birds typically fly” is formalized by the following first-order default:

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

This rule means that, if $X$ is a bird, and it can be assumed that it flies, then we can conclude that it flies. A background theory containing some facts about birds is the following one:

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

The default rule allows concluding that a condor flies because the precondition of the default $Bird(Condor)$ is true and its justification $Flies(Condor)$ is not inconsistent with what is currently known. On the contrary, $Bird(Penguin)$ does not allow concluding $Flies(Penguin)$. Indeed, even if the precondition of the default $Bird(Penguin)$ is true, the default rule cannot be applied because its justification $Flies(Penguin)$ is inconsistent with what is known. From this background theory and this default, $Bird(Eagle)$ cannot be concluded because the default rule only allows deriving $Flies(X)$ from $Bird(X)$, but not vice versa. Deriving the antecedents from the consequences is a form of explanation of the consequences, and is the aim of Abductive reasoning.

A common default inference is that something that is not known to be true is believed to be false. This is known as the Closed World Assumption, and is formalized in default logic using a default like the following one for every fact $X$.

${\frac {:{\neg }X}{{\neg }X}}$

For example, 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. 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)}{\neg 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.