Default logic
Encyclopedia
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.
. 
is a set of logical formulae, called the background theory, that formalize the facts that are known for sure. 
is a set of default rules, each one being of the form:
According to this default, if we believe that
is true, and each of 
is consistent with our current beliefs, we are led to believe that 
is true.
The logical formulae in
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.
This rule means that, if
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:
.
According to this default rule, a condor flies because the precondition
is true and the justification 
is not inconsistent with what is currently known. On the contrary, 
does not allow concluding 
: even if the precondition of the default 
is true, the justification 
is inconsistent with what is known.
From this background theory and this default,
cannot be concluded because the default rule only allows deriving
from 
, 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
.
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
, it tries to prove that 
is true, and conclude that 
is true if it fails. In default logic, instead, a default having 
as a justification can only be applied if 
is consistent with the current knowledge.
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.
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
nor 
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.
Justified: differs from the original one in that a default is not applied if thereby the set
becomes inconsistent with a justification of an applied default;
Concise: a default is applied only if its consequence is not already entailed by
(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.
Assertional variants : An assertion is a pair
composed of a formula and a set of formulae. Such a pair indicates that 
is true while the formulae 
have been assumed consistent to prove that 
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:
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
has the model in which 
is true just because, assuming 
true, the formula 
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.
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:
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 exists or not depending on whether modularity or the use of the same alphabet is required.
of the following problems about default logic is known:
Existence of extensions : deciding whether a propositional default theory has at least one extension is
-complete;
Skeptical entailment : deciding whether a propositional default theory skeptically entails a propositional formula
is
-complete;
Credulous entailment : deciding whether a propositional default theory credulously entails a propositional formula is
-complete;
Extension checking : deciding whether a propositional formula is equivalent to an extension of a propositional default theory is
-complete;
Model checking : deciding whether a propositional interpretation is a model of an extension of a propositional default theory is
-complete.
[ftp://www.cs.engr.uky.edu/cs/manuscripts/deres.ps DeReS],
XRay and
GADeL
Non-monotonic logic
A non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a...
proposed by Raymond Reiter
Raymond Reiter
Raymond Reiter , was a Canadian computer scientist and logician. He was one of the founders of the field of non-monotonic reasoning with his work on default logic, model-based diagnosis, closed world reasoning, and truth maintenance systems...
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. is a set of logical formulae, called the background theory, that formalize the facts that are known for sure. is a set of default rules, each one being of the form:
According to this default, if we believe that
is true, and each of is consistent with our current beliefs, we are led to believe that is true.The logical formulae in
and all formulae in a default were originally assumed to be first-order logicFirst-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate 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:This rule means that, if
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:.According to this default rule, a condor flies because the precondition
is true and the justification is not inconsistent with what is currently known. On the contrary, does not allow concluding : even if the precondition of the default is true, the justification is inconsistent with what is known.From this background theory and this default,
cannot be concluded because the default rule only allows deriving from , 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 reasoningAbductive reasoning
Abduction is a kind of logical inference described by Charles Sanders Peirce as "guessing". The term refers to the process of arriving at an explanatory hypothesis. Peirce said that to abduce a hypothetical explanation a from an observed surprising circumstance b is to surmise that a may be true...
.
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
Closed world assumption
The closed world assumption is the presumption that what is not currently known to be true, is false. The same name also refers to a logical formalization of this assumption by Raymond Reiter. The opposite of the closed world assumption is the open world assumption , stating that lack of knowledge...
, and is formalized in default logic using a default like the following one for every fact
.
For example, the computer language Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
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
, it tries to prove that is true, and conclude that is true if it fails. In default logic, instead, a default having as a justification can only be applied if 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 diamondNixon diamond
In nonmonotonic reasoning, the Nixon diamond is a scenario in which default assumptions can lead to mutually inconsistent conclusions. This scenario is:* usually, Quakers are pacifist* usually, Republicans are not pacifist...
example is a default theory with two extensions:
Since Nixon
Richard Nixon
Richard Milhous Nixon was the 37th President of the United States, serving from 1969 to 1974. The only president to resign the office, Nixon had previously served as a US representative and senator from California and as the 36th Vice President of the United States from 1953 to 1961 under...
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 onein which
is false.The original semantics of default logic was based on the fixed point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
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 andall 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
Nondeterministic algorithm
In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different...
, 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.Entailment
A default theory can have zero, one, or more extensions. EntailmentEntailment
In logic, entailment is a relation between a set of sentences and a sentence. Let Γ be a set of one or more sentences; let S1 be the conjunction of the elements of Γ, and let S2 be a sentence: then, Γ entails S2 if and only if S1 and not-S2 are logically inconsistent...
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
nor 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
becomes inconsistent with a justification of an applied default;Concise: a default is applied only if its consequence is not already entailed by
(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
composed of a formula and a set of formulae. Such a pair indicates that is true while the formulae have been assumed consistent to prove that 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
Autoepistemic logic
The autoepistemic logic is a formal logic for the representation and reasoning of knowledge about knowledge. While propositional logic can only express facts, autoepistemic logic can express knowledge and lack of knowledge about facts....
, where a theory
has the model in which is true just because, assuming true, the formula 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
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
collapses. Translations to autoepistemic logic exists or not depending on whether modularity or the use of the same alphabet is required.
Complexity
The computational complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
-complete;Skeptical entailment : deciding whether a propositional default theory skeptically entails a propositional formula
Propositional formula
In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value...
is
-complete;Credulous entailment : deciding whether a propositional default theory credulously entails a propositional formula is
-complete;Extension checking : deciding whether a propositional formula is equivalent to an extension of a propositional default theory is
-complete;Model checking : deciding whether a propositional interpretation is a model of an extension of a propositional default theory is
-complete.Implementations
Three systems implementing default logics are[ftp://www.cs.engr.uky.edu/cs/manuscripts/deres.ps DeReS],
XRay and
GADeL
External links
- Schmidt, Charles F. RCI.Rutgers.edu, Default Logic. Retrieved August 10, 2004.
- Ramsay, Allan (1999). UMIST.ac.uk, Default Logic. Retrieved August 10, 2004.
- Stanford.edu, Defeasible reasoning, Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
.