Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize 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 reasoning often involves facts that are true in the majority of cases but not always. A classical example is: “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 rule to be specified. Default logic aims at formalizing inference rules like this one without explicitly mentioning all their exceptions.

Syntax of default logic

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

${\displaystyle {\frac {\mathrm {Prerequisite:Justification} _{1},\dots ,\mathrm {Justification} _{n}}{\mathrm {Conclusion} }}}$

According to this default, if we believe that Prerequisite is true, and each ${\displaystyle \mathrm {Justification} _{i}}$ for ${\displaystyle i=1,\dots ,n}$ is consistent with our current beliefs, we are led to believe that Conclusion is true.

The logical formulae in W and all formulae in a default were originally assumed to be first-order logic formulae, but they 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 default:

${\displaystyle D=\left\{{\frac {\mathrm {Bird} (X):\mathrm {Flies} (X)}{\mathrm {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:

${\displaystyle W=\{\mathrm {Bird} (\mathrm {Condor} ),\mathrm {Bird} (\mathrm {Penguin} ),\neg \mathrm {Flies} (\mathrm {Penguin} ),\mathrm {Flies} (\mathrm {Bee} )\}}$.

According to this default rule, a condor flies because the precondition Bird(Condor) is true and the justification Flies(Condor) is not inconsistent with what is currently known. On the contrary, Bird(Penguin) does not allow concluding Flies(Penguin): even if the precondition of the default Bird(Penguin) is true, the justification Flies(Penguin) is inconsistent with what is known. From this background theory and this default, Bird(Bee) cannot be concluded because the default rule only allows deriving Flies(X) from Bird(X), but not vice versa. Deriving the antecedents of an inference rule from the consequences is a form of explanation of the consequences, and is the aim of abductive reasoning.

A common default assumption is that what 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 F.

${\displaystyle {\frac {:{\neg }F}{{\neg }F}}}$

For example, the computer language Prolog uses a sort of default assumption when dealing with negation: 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 ${\displaystyle \neg F}$, it tries to prove that F is true, and conclude that ${\displaystyle \neg F}$ is true if it fails. In default logic, instead, a default having ${\displaystyle \neg F}$ as a justification can only be applied if ${\displaystyle \neg F}$ is consistent with the current knowledge.

Restrictions

A default is categorical or prerequisite-free if it has no prerequisite (or, equivalently, its prerequisite is tautological). A default is normal if it has a single justification that is equivalent to its conclusion. A default is supernormal if it is both categorical and normal. A default is seminormal if all its justifications entail its conclusion. A default theory is called categorical, normal, supernormal, or seminormal if all defaults it contains are categorical, normal, supernormal, or seminormal, respectively.

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\langle \left\{{\frac {\mathrm {Republican} (X):\neg \mathrm {Pacifist} (X)}{\neg \mathrm {Pacifist} (X)}},{\frac {\mathrm {Quaker} (X):\mathrm {Pacifist} (X)}{\mathrm {Pacifist} (X)}}\right\},\left\{\mathrm {Republican} (\mathrm {Nixon} ),\mathrm {Quaker} (\mathrm {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 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},\ldots ,\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 */
 
              /* apply a sequence of defaults */
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
 
              /* final consistency check */
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 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\langle \left\{{\frac {:A(b)}{\neg A(b)}}\right\},\emptyset \right\rangle }$

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 {\phi :\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 $$Zdroj:https://en.wikipedia.org?pojem=Default_logic
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---