Default logic

Default logic is a non-monotonic logic proposed by Ray Reiter to formalize the human reasoning with default assumptions.

Default logic 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.

Restrictions

A default with no prerequisite is called categorical or prerequisite-free. A default with a single justification that is equivalent to its conclusion is called normal. If all justifications of a default entail the conclusion of the default, this default is called semi-normal. A default theory is called categorical, normal, or seminormal if all defaults it contains are categorical, normal, or seminormal, respectively.

Semantic of Default Logic

A default rule can be applied to a propositional theory if its precondition is entailed by the theory and its justifications are all consistent with the theory. What results from this application is a new propositional theory that includes the consequence of the default rule. To this theory, other default rules can be applied. When no other default can be applied, the propositional theory is called an extension of the default theory. The default rules may be applied in different order, and this may lead to different extensions. The Nixon diamond example is 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.

The original semantics of default logic was based on the fixed point of a function. The following is an equivalent definition. A default ${\frac {\alpha :\beta _{1},\ldots ,\beta _{n}}{\gamma }}$ is applicable to a propositional theory $T$ if $T\models \alpha$ and all theories $T\cup \{\beta _{i}\}$ are consistent. The application of this default to $T$ leads to the theory $T\cup \{\gamma \}$. An extension can be generated by applying the following algorithm:

T=W
A=0
while there is a default d that is not in A and is applicable to T
  add the consequence of d to T
  add d to A
if 
  for every default d in A
    T is consistent with all justifications of d
then
  output T

This algorithm is non-deterministic, as several defaults can be applicable to a given theory $T$. In the Nixon diamond example, the application of the first default leads to a theory to which the second default cannot be applied and vice versa. As a result, two extensions are generated: one in which Nixon is a pacifist and one in which Nixon is not a pacifist.

The final check of consistency of the justifications of all defaults that have been applied makes some theories not having any extension. In particular, this happens whenever this check fails for every possible sequence of applicable defaults. The following default theory has no extension:

$\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. According to the original semantic of default logic, this theory has no extensions.

A normal default theory is guaranteed to have at least one extensions. Furthermore, the extensions of a normal default theory are mutually inconsistent, i.e., inconsistent with each other.

Entailment

A default theory can have zero, one, or more extensions. Entailment of a formula from a default theory can be defined in two ways:

Skeptical

a formula is entailed by a default theory if it is entailed by all its extensions;

Credulous

a formula is entailed by a default theory if it is entailed by at least one of its extensions.

For example, the Nixon diamond example theory has two extensions, one in which Nixon is a pacifist and one in which he is not a pacifist. Consequently, neither $Pacifist(Nixon)$ nor $\neg Pacifist(Nixon)$ are skeptically entailed, which both of them are credulously entailed. As this example shows, the credulous consequences of a default theory may be inconsistent with each other.

Alternative Semantics

The following alternative semantics of default logic are all based on the same syntax of the original one.

Justified

differs from the original one in that a default $d$ is not added to the set $A$ if that would result in the set $T$ being inconsistent with a justification of a default in $A$;

Concise

a default $d$ is added to $A$ only if its consequence is not already entailed by $T$ (the exact definition is more complicated than this one; this is only the main idea behind it);

Constrained

a default $d$ is added to $A$ only if the set composed of the background theory, the justifications of all defaults and consequences of the defaults of $A\cup \{d\}$ is consistent;

Rational

similar to constrained default logic, but the consequence of the default to add is not considered in the consistency check.

The justified and constrained semantics assign at least an extension to every default theory.

Variants of Default Logic

The following variants of default logic differ from the original one both on syntax and on semantics.

Assertional variants

An assertion is a pair $\langle p:\{r_{1},\ldots ,r_{n}\}\rangle$ composed of a formula and a set of formulae. Such a formula has the meaning that $p$ is true while the formulae $r_{1},\ldots ,r_{n}$ are those that have been assumed true to prove that $p$ is true. An assertional default theory is composed of an assertional theory (a set of assertional formulae) called the background theory and a set of defaults defined as in the original syntax. Whenever a default is applied to an assertional theory, the pair composed of its consequence and its justifications is added to the theory. The following semantics use assertional theories:

• Cumulative default logic
• Committment to assumptions default logic
• Quasi-default logic

Disjunctive default logic

the consequence of a default, instead of a single formula is a set of formulae. Whenever the default is applied, at least one of the consequences is nondeterministically chosen and made true.

Probabilistic variants

Complexity

The computational complexity of the following problems about default logic is known:

Existence of extensions

deciding whether a propositional default theory has at least one extension is $NP^{NP}$-complete;

Skeptical entailment

deciding whether a propositional default theory skeptically entails a propositional formula is $co-NP^{NP}$-complete;

Credulous entailment

deciding whether a propositional default theory credulously entails a propositional formula is $NP^{NP}$-complete;

Extension checking

deciding whether a propositional formula is equivalent to an extension of a propositional default theory is $P^{NP[log]}$-complete;

Model checking

deciding whether a propositional interpretation is a model of an extension of a propositional default theory is $NP^{NP}$-complete.

References

• Schmidt, Charles F. Default Logic. Retrieved August 10th. 2004.

• Ramsay, Allan (1999). Default Logic. Retrieved August 10th. 2004.

Bibliography

G. Antoniou. A tutorial on default logics. ACM Computing Surveys, 31(4):337-359, 1999.

J. P. Delgrande, T. Schaub, and W. K. Jackson. Alternative approaches to default logic. Artificial Intelligence, 70(1-2):167-237, 1994.

G. Gottlob. Complexity results for nonmonotonic logics. Journal of Logic and Computation 2(3): 397-425. 1992

W. Lukaszewicz. Considerations on default logic: an alternative approach. Computational Intelligence, 4(1):1-16, 1988.

W. Marek and M. Truszczynski. Nonmonotonic Logics: Context-Dependent Reasoning. Springer, 1993.

A. Mikitiuk and M. Truszczynski. Constrained and rational default logics. In Proceedings of IJCAI'95, pages 1509-1517, 1995.

R. Reiter. A logic for default reasoning. Artificial Intelligence 13(1-2):81-132, 1980.