The question is composed of 2 sub-questions, I've already answered the first one but I'm gonna write it since it's important for the rest of the question.
We will state that formula A is of CNF formation if there exists $A_{i,j}$ elementary formulas, or the negation of elementary formulas, so that:
$A = (A_{1,1} \vee ... \vee A_{1,n1}) \land ... \land (A_{k,1} \vee ... \vee A_{k,nk})$
Prove that for each quantifier-less formula A there exists a quantifier less formula B in CNF formation, so that $ \vdash A \leftrightarrow B$
This I proved, but this is necessary for the next question that I found some trouble in:
Show that if $\vdash A \leftrightarrow B$ then $\vdash QxA\leftrightarrow QxB $
For $ Q = \exists, \forall$
Thanks!
OK, not knowing the proof system but assuming it is sound and complete, i.e. for any $\varphi$ it holds that:
$\vdash \varphi$ iff $\vDash \varphi$
I'll show that:
(*) If $\vdash A \leftrightarrow B$ then $\vdash \forall x A \leftrightarrow \forall x B$
By showing that
If $\vDash A \leftrightarrow B$ then $\vDash \forall x A \leftrightarrow \forall x B$
For then we can simply do:
If
$\vdash A \leftrightarrow B$
then (sound)
$\vDash A \leftrightarrow B$
so (*)
$\vDash \forall x A \leftrightarrow \forall x B$
so (complete)
$\vdash \forall x A \leftrightarrow \forall x B$
OK, but how do we show (*)?
First, let's assume that $A$ and $B$ do not contain $x$ as a free variable. Then, by Null Quantification:
$\forall x A \Leftrightarrow A$ and $\forall x B \Leftrightarrow B$
Since for any $\varphi$ and $\psi$:
$\vDash \varphi \leftrightarrow \psi$ iff $\varphi \Leftrightarrow \psi$
We thus get that if
$\vDash A \leftrightarrow B$
then:
$A \Leftrightarrow B$
and so:
$\forall x A \Leftrightarrow \forall x B$
and thus:
$\vDash \forall x A \leftrightarrow \forall x B$
OK, but what if $A$ and $B$ do contain $x$ as a free variable?
Well, let's first assume they have the same free variables ... which actually doesn't have to be, e.g. if $A = P(x) \lor \neg P(x)$ and $B = P(y) \lor \neg P(y)$, then $\vDash A \leftrightarrow B$, but let's ignore those variables that 'do no interesting work'.
OK, so let $x,x_1,x_2,...$ be all the free variables in both $A$ and $B$.
Then by $A \Leftrightarrow B$ we mean that for any interpretation (structure) $I$ with domain $D$, it holds that the exact same tuples $<d,d_1,d_2,...>$ with $d,d_1,d_2, ... \in D$ will satisfy the formulas $A$ as well as $B$, defined as follows:
$<d,d_1,d_2,...>$ satisfies formula $A(x,x_1,x_2,...)$ in $I$ iff $I \vDash A(x,x_1,x_2,...)[d,d_1,d_2,...]$ and where we mean (in general):
$I \vDash A(x)[d/x]$ iff by extending our language with a new constant symbol $c$, and extending our interpretation $I$ to become a new interpretation $I[d/c]$ which is just like $I$, but in addition interprets $c$ as $d$, we have that $I[d/c] \vDash A(c/x)$ where $A(c/x)$ is the result of replacing all free variables $x$ in $a$ with constant symbol $c$.
OK, so if we assume that
$\vDash A(x,x_1,x_2,...) \leftrightarrow B(x,x_1,x_2,...)$
then:
$A(x,x_1,x_2,...) \Leftrightarrow B(x,x_1,x_2,...)$
and thus for any interpretation (structure) $I$ with domain $D$ it holds that:
For all tuples $<d,d_1,d_2,...>$ with $d,d_1,d_2, ... \in D$: $I \vDash A(x,x_1,x_2,...)[d/x,d_1/x_1,d_2/x_2,...]$ iff $I \vDash B(x,x_1,x_2,...)[d/x,d_1/x_1,d_2/x_2,...]$
So now we have that for any interpretation $I$ and all tuples $<d_1,d_2,...>$ with $d_1,d_2, ... \in D$:
$I \vDash \forall x A(x,x_1,x_2,...)[d_1/x_1,d_2/x_2,...]$ iff
for all $d \in D$: $I \vDash A(x,x_1,x_2,...)[d/x,d_1/x_1,d_2/x_2,...]$ iff
for all $d \in D$: $I \vDash B(x,x_1,x_2,...)[d/x,d_1/x_1,d_2/x_2,...]$ iff
$I \vDash \forall x B(x,x_1,x_2,...)[d_1/x_1,d_2/x_2,...]$ iff
So:
$\forall x A(x,x_1,x_2,...) \Leftrightarrow \forall x B(x,x_1,x_2,...)$
and thus:
$\vDash \forall x A(x,x_1,x_2,...) \leftrightarrow \forall x B(x,x_1,x_2,...)$ or simply put:
$\vDash \forall x A \leftrightarrow \forall x B$