could you help me with transferring the following to normal prenex?
1) $\forall x \exists y p(x,y) \iff \exists x \forall y \exists z R(x,y,z)$
2) $((\exists x \forall y p(x) \lor ( \exists x \forall y (s(y) \to q(x,y))) \lor \exists x \exists y R(x,y)$
what i tried to do:
1) it looks like it's almost in the needed form, but needs to get rid of the iff: ${\equiv \exists y \forall x (p(x,y)) \iff \exists z \forall y \exists x(R(x,y,z)) \\ \equiv ∃y∀x(p(x,y) \to ∃z∀y∃x(R(x,y,z))) \land ∃z∀y∃x(R(x,y,z) \to ∃y∀x(p(x,y)) \\ \equiv \forall y \forall x \exists z \exists x \exists y(p(x,y) \to R(x,y,z)) \land \forall x \forall y \exists y \exists z \exists x(R(x,y,z) \to p(x,y) }$
...and in the world of {a,b,c}: $~~~~∀b∀a∃c∃a∃b(p(a,b)→R(a,b,c))∧∀a∀b∃b∃c∃a(R(a,b,c)→p(a,b)$
2)this one is way more complicated, and i'm sure i've done a mistake here: ${~~~((∃x∀yp(x)∨∃x∀y(s(y)) \to (∃x∀yp(x) ∨ q(x,y))) \lor (∃x∃yR(x,y))\\ \equiv \exists x \forall y((p(x) \lor s(y)) \to (p(x) \lor q(x,y))) \lor \exists y \exists x(R(x,y,z))\\ \equiv \exists y \exists x \forall y((p(x) \lor s(y)) \to (p(x) \lor q(x,y)) \lor R(x,y,z))}$
i am pretty sure i've done some mistakes along the way. please show me what i've done wrong and correct me by showing the right way so i can learn.
thank you very much for your help!
HINT
A basic mistake you make is that you do not change variables so as to make them unique, and as a result certain variables, which were once quantified by one quantifier, are now captured by a different quantifier.
As an example of what I mean, consider:
$\exists x \ P(x) \land \forall x \ Q(x)$
The meaning of this is: "something is a $P$, and everything is a $Q$'
Notice, though, what happens if you don't change the variables when bringing the quantifiers to the outside:
$\exists x \forall x (P(x) \land Q(x))$
In this sentence, the $x$ of $P(x)$ has been captured by the $\forall x$, while the $\exists x$ is no longer quantifying anything. Indeed, this latter statement is equivalent to simply:
$\forall x (P(x) \land Q(x))$
which means that 'everything is a $P$ as well as a $Q$' ... whch is clearly no longer the same thing as the original sentence.
To avoid this, you need to change variables so each quantifier quantifies a unique variable. So, for example, we can change the original sentence to:
$\exists x_1 \ P(x_1) \land \forall x_2 \ Q(x_2)$
And now we can bring the quantifiers to the front:
$\exists x_1 \forall x_2 (P(x_1) \land Q(x_2))$
And this is still equivalent to the original, since each variable is still quantified by the original quantifier.
Also: for the first one you still need to pull all quantifiers to the front ...
As an incentive, here is the final result for 1):
$\exists x_1 \forall x_2 \exists x_3 \forall x_4 \exists x_5 \forall x_6 \exists x_7 \forall x_8 \exists x_9 \forall x_{10} ((p(x_1,x_2) \rightarrow R(x_3,x_4,x_5)) \land (R(x_6,x_7,x_8) \rightarrow p(x_9,x_{10})))$