Show every boolean combination of $\mathcal{L}$-formula is equivalent one with quantifiers.

Question

This is part 2 of a question I asked here:

Prove this claim about language and structures.

The setting is that suppose $\phi_1,\ldots,\phi_n$ are $\mathcal{L}$-formulas and $\psi$ is a Boolean combination of $\phi_1,\ldots,\phi_n$. Then we showed there is $S \subseteq \mathcal{P}(\{1,\ldots,n\})$ such that

$$\models \psi \Leftrightarrow \bigvee_{X \in S} \left(\bigwedge_{i \in X} \phi_i \wedge \bigwedge_{i \notin X} \neg \phi_i \right)$$

Now I would like to show that every formula is equivalent to one of the form

$$Q_1 v_1 \ldots Q_m v_m ~~\psi$$

Where $\psi$ is quantifier free and each $Q_i$ is either $\forall$ or $\exists$.

First, intuitively speaking, what is this question asking? In addition to proving this claim, I would like to know if there is any online reading material associated with what this question is asking, so I may read into it some more.

Answer 1

Regarding the "older" part of the question, you have to note that it speaks of "boolean combination" of formulae $\phi_1, \dots, \phi_n$.

The $\phi_i$ are not propositional letters and thus, nothing prevents that e.g. :

$\phi_i := \exists x \alpha(x)$.

Consider now the "old" formula :

$\psi := \lnot (\phi_1 \rightarrow \lnot \phi_2)$

and assume that $\phi_1 := \exists x \alpha(x)$ and $\phi_2 := \forall y \beta(y)$.

The previous proof showed us that :

$\psi \Leftrightarrow (\exists x \alpha(x) \land \forall y \beta(y))$.

The new question ask us to prove that :

$\psi \Leftrightarrow Q_1 v_1 Q_2 v_2 \psi'$,

where $\psi'$ is quantifier-free.

See Prenex normal form.