Default logic

Semantics of default logic

A default rule can be applied to a theory if its precondition is entailed by the theory and its justifications are all consistent with the theory. The application of a default rule leads to the addition of its consequence to the theory. Other default rules may then be applied to the resulting theory. When the theory is such that no other default can be applied, the 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:

${\displaystyle ⟨\left\{\frac{\mathrm{R}\mathrm{e}\mathrm{p}\mathrm{u}\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{n}(X):\mathrm{\neg }\mathrm{P}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{s}\mathrm{t}(X)}{\mathrm{\neg }\mathrm{P}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{s}\mathrm{t}(X)},\frac{\mathrm{Q}\mathrm{u}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{r}(X):\mathrm{P}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{s}\mathrm{t}(X)}{\mathrm{P}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{s}\mathrm{t}(X)}\right\},\left\{\mathrm{R}\mathrm{e}\mathrm{p}\mathrm{u}\mathrm{b}\mathrm{l}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{n}(\mathrm{N}\mathrm{i}\mathrm{x}\mathrm{o}\mathrm{n}),\mathrm{Q}\mathrm{u}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{r}(\mathrm{N}\mathrm{i}\mathrm{x}\mathrm{o}\mathrm{n})\right\}⟩}$

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 algorithmic definition. If a default contains formulae with free variables, it is considered to represent the set of all defaults obtained by giving a value to all these variables. A default ${\displaystyle \frac{\alpha :{\beta }_1,\dots ,{\beta }_n}{\gamma }}$ is applicable to a propositional theory T if ${\displaystyle T\models \alpha }$ and all theories ${\displaystyle T\cup \{{\beta }_i\}}$ are consistent. The application of this default to T leads to the theory ${\displaystyle T\cup \{\gamma \}}$. An extension can be generated by applying the following algorithm:

T = W /* current theory */ A = 0 /* set of defaults applied so far */ <span typeof="mw:Entity" id="mwWw"> </span> /* apply a sequence of defaults */ <b id="mwXA">while</b> 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 <span typeof="mw:Entity" id="mwXQ"> </span> /* final consistency check */ <b id="mwXg">if</b> <b id="mwXw">for</b> every default d in A T is consistent with all justifications of d <b id="mwYA">then</b> output T

This algorithm is non-deterministic, as several defaults can alternatively be applied 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 implies that some theories do not have any extensions. In particular, this happens whenever this check fails for every possible sequence of applicable defaults. The following default theory has no extension:

${\displaystyle ⟨\left\{\frac{:A(b)}{\mathrm{\neg }A(b)}\right\},\mathrm{\varnothing }⟩}$

Since ${\displaystyle A(b)}$ is consistent with the background theory, the default can be applied, thus leading to the conclusion that ${\displaystyle A(b)}$ is false. This result however undermines the assumption that has been made for applying the first default. Consequently, this theory has no extensions.

In a normal default theory, all defaults are normal: each default has the form ${\displaystyle \frac{\varphi :\psi }{\psi }}$. A normal default theory is guaranteed to have at least one extension. 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.

Thus, 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 ¬Pacifist(Nixon) are skeptically entailed, while both of them are credulously entailed. As this example shows, the credulous consequences of a default theory may be inconsistent with each other.

Alternative default inference rules

The following alternative inference rules for default logic are all based on the same syntax as the original system.

Justified

differs from the original one in that a default is not applied if thereby the set T becomes inconsistent with a justification of an applied default;

Concise

a default is applied 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 is applied only if the set composed of the background theory, the justifications of all applied defaults, and the consequences of all applied defaults (including this one) is consistent;

Rational

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

Cautious

defaults that can be applied but are conflicting with each other (like the ones of the Nixon diamond example) are not applied.

The justified and constrained versions of the inference rule assign at least an extension to every default theory.

Variants of default logic

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

Assertional variants

An assertion is a pair ${\displaystyle ⟨p:\{r_1,\dots ,r_n\}⟩}$ composed of a formula and a set of formulae. Such a pair indicates that p is true while the formulae ${\displaystyle r_1,\dots ,r_n}$ have been assumed consistent 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 set of justifications is added to the theory. The following semantics use assertional theories:

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

Weak extensions

rather than checking whether the preconditions are valid in the theory composed of the background theory and the consequences of the applied defaults, the preconditions are checked for validity in the extension that will be generated; in other words, the algorithm for generating extensions starts by guessing a theory and using it in place of the background theory; what results from the process of extension generation is actually an extension only if it is equivalent to the theory guessed at the beginning. This variant of default logic is related in principle to autoepistemic logic, where a theory ${\displaystyle ◻x\to x}$ has the model in which x is true just because, assuming ${\displaystyle ◻x}$ true, the formula ${\displaystyle ◻x\to x}$ supports the initial assumption.

Disjunctive default logic

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

Priorities on defaults

the relative priority of defaults can be explicitly specified; among the defaults that are applicable to a theory, only one of the most preferred ones can be applied. Some semantics of default logic do not require priorities to be explicitly specified; rather, more specific defaults (those that are applicable in fewer cases) are preferred over less specific ones.

Statistical variant

a statistical default is a default with an attached upper bound on its frequency of error; in other words, the default is assumed to be an incorrect inference rule in at most that fraction of times it is applied.

Translations

Default theories can be translated into theories in other logics and vice versa. The following conditions on translations have been considered:

Consequence-Preserving

the original and the translated theories have the same (propositional) consequences;

Faithful

this condition only makes sense when translating between two variants of default logic or between default logic and a logic in which a concept similar to extension exists, e.g., models in modal logic; a translation is faithful if there exists a mapping (typically, a bijection) between the extensions (or models) of the original and translated theories;

Modular

a translation from default logic to another logic is modular if the defaults and the background theory can be translated separately; moreover, the addition of formulae to the background theory only leads to adding the new formulae to the result of the translation;

Same-Alphabet

the original and translated theories are built on the same alphabet;

Polynomial

the running time of the translation or the size of the generated theory are required to be polynomial in the size of the original theory.

Translations are typically required to be faithful or at least consequence-preserving, while the conditions of modularity and same alphabet are sometimes ignored.

The translatability between propositional default logic and the following logics have been studied:

• classical propositional logic;
• autoepistemic logic;
• propositional default logic restricted to seminormal theories;
• alternative semantics of default logic;
• circumscription.

Translations exist or not depending on which conditions are imposed. Translations from propositional default logic to classical propositional logic cannot always generate a polynomially sized propositional theory, unless the polynomial hierarchy collapses. Translations to autoepistemic logic exist or not depending on whether modularity or the use of the same alphabet is required.

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 ${\displaystyle {\mathrm{\Sigma }}_2^P}$-complete;

Skeptical entailment

deciding whether a propositional default theory skeptically entails a propositional formula is ${\displaystyle {\mathrm{\Pi }}_2^P}$-complete;

Credulous entailment

deciding whether a propositional default theory credulously entails a propositional formula is ${\displaystyle {\mathrm{\Sigma }}_2^P}$-complete;

Extension checking

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

Model checking

deciding whether a propositional interpretation is a model of an extension of a propositional default theory is ${\displaystyle {\mathrm{\Sigma }}_2^P}$-complete.

Implementations

Four systems implementing default logics are DeReS, XRay, GADeL Archived 2007-04-06 at the Wayback Machine, and Catala.