that the function       is a translation from to the class and is -hard.

## 3. Preliminaries On Default Logic

Default logic is one of the main formalizations of nonmonotonic reasoning (Reiter, 1980).

A default theory ∆ =
consists of a set of default rules  : 1 n where   (the precondition),   (the conclusion) and   i
(the justifications) are formulae of 1 the classical propositional logic, and a set    of objective facts that also are formulae of the classical propositional logic. A default rule  :  1 if has been derived, and none of the formulae    1 n can be derived. As fact derivability and underivability are mutually dependent, there is circularity in the definition of what is derivable in default logic. Unlike in monotonic logics, where the consequences of a set of formulae is defined as the formulae that can be derived by using the axioms of the logic and the inference rules, the conclusions of a default theory ∆ =
are defined as fixpoints of a nonmonotonic operator. The operator may have several fixpoints, none of which is the least fixpoint, and different fixpoints can be seen as a result of applying different mutually incompatible sets of default rules. The fixpoints of the operator for a default theory are the extensions of the default theory.

Informally, the construction of each extension of a default theory starts from the objective facts   , and proceeds by adding conclusions of default rules the preconditions of which have already been derived, and the justifications of which have not been and will not lter be contradicted. The construction ends when no more defaults can be applied.

Example 3.1 Define ∆ =
by

$$\begin{array}{r l}{={}}&{{}\left\{{\frac{p r i e s t:\quad d r i n k s\cdot v o d k a\quad m a\,n:\,d r i n k s\cdot v o d k a\quad p r i e s t:\,m a\,n}{d r i n k s\cdot v o d k a\quad d r i n k s\cdot v o d k a\quad p r i e s t:\,m a\,n}}\right\}\quad{\mathrm{and}}}\\ {={}}&{{}p r i e s t}\end{array}$$

can be interpreted as saying that an individual who has property –, can A default   :
be assumed to also have the property if this is consistent with what else is known. The default theory ∆ has two extensions, = Cn ( priest man   drinks-vodka ) and
/ =
Cn ( priest man drinks-vodka  ), that represent the two possibilities of resolving the conflict between the first two defaults in . The extension corresponds to the choice to apply the first default, and the extension ' to the choice to apply the second.

The fixpoint definition of extensions is given next. The language of the propositional logic is denoted by . The closure of a set of formulae under logical consequence is Cn( ) =
= . The set of default CONSIDER
n 0 rest to the rest is the sum of the lengths of the formulae in and in defaults in . A default theory is finite if . and are finite.

Definition 3.1 (Reiter, 1980) Let ∆ =
be a default theory.  For any set of for-
, let Γ(  ) be the smallest set such that      Γ(  ), Cn(Γ(  )) = Γ(  ), and if mula e L( ) and Γ( ). A set of
: 1 and
= , then l formula e is an extension for ∆ if and only if Γ(  ) =   .