1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You need a "preliminary" textbook on mathematical logic; there are many. You can see also Stephen Simpson, Mathematical Logic (2013). $\endgroup$ – Mauro ALLEGRANZA Jan 20 '15 at 15:25
  • $\begingroup$ @MauroALLEGRANZA great link, I do need it. Thank you! $\endgroup$ – chibro2 Jan 20 '15 at 15:30
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.