MAXIMUM 2- QUANTIFIED FORMULA
l 2 where i is an abbreviation for an -tuple Instance:  Boolean formula of Boolean variables that corresponds to a valuation of " Output: Lexicographically maximal   1     0 1 n that satisfies

$$\exists\quad\ {\mathrm{{\bfl}}}\,\forall\quad\ 2\,($$
$$\begin{array}{r l r l}{1}&{{}}&{{}2}&{{}=1)}\end{array}$$

The following lemma points out a connection between quantified Boolean formulae with a universal quantifier as the outermost quantifier and the logical consequence relation in propositional logic.

Lemma 5.11 Let be a set containing exactly one of and for every n  where and  !! = 0 otherwise.  Then Let l =
l satisfies A 2 (
) if and only if 1 2 ). Hence for the choice of truth values for Proof: Assume that   1 satisfies ∀  2 (
1. In the indicated by 1 and any choice of truth values for l 2 is true.

Now let    be any model such that    =
1 2 , and by the definition of logical consequence n as 1. Now to i l 2 1 Assume that asigns l any truth-values to
= 
¹ and any   ² the formula      ¹    ²  is true, that is,    ¹ satisfies ∀  ² (
lae, for 口 The proof of the next lemma uses the same translation of quantified Boolean formulae to default theories as Gottlob's proof of Π 2 -hardness of cautious reasoning in Reiter's default logic (Gottlob, 1992).

Lemma 5.12 Computing a given component of   1 in MAXIMUM 2-QUANTIFIED FORMULA is polynomial time many-one reducible to the problem of testing whether a formula belongs to all T-preferred - extensions of a default theory for strict total orders T.

Proof: We construct a default theory ∆ =         and define a strict partial order P on so that the th component of
¹ in MAXIMUM 2-QUANTIFIED FORMULA is defined only if ∃  ¹∀  ²(
2 ) is satisfiable, so assume it is. Let be a propositional variable that is not in Define

![0_image_0.png](0_image_0.png)

46