Default Logic - Semantics of 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:

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 is true, and one in which 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 is applicable to a propositional theory if and all theories are consistent. The application of this default to leads to the theory . 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 . 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:

Since is consistent with the background theory, the default can be applied, thus leading to the conclusion that 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 . 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.