How to convert formulas to rectified prenex form?

388 Views Asked by At

I'm preparing to an exam and I haven't understood this question:

Convert the following formulas into rectified prenex form:
a) $F = (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z)) \impliedby \forall x\, R(x, y)$.
b) $F = \exists z(\exists x\,Q(x, z) \lor \exists x\, P(x)) \implies \neg(\neg\exists x\, P(x) \land \forall x \exists z\, Q(z, x))$.

Can somebody explain me how to do this?

I'm trying to do the first problem:

So:

$F = (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z)) \impliedby \forall x\, R(x, y)$.

  1. Remove all $\impliedby$ : $\neg (\forall x\, R(x, y))\lor (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z))$.
  2. Push all $\neg$: $(\exists x\, \neg R(x, y))\lor (\forall x \exists y\, P(x, g(y, f(x))) \lor \neg Q(z))$.
  3. Don't understand what is it?
  4. $(\exists x\, \neg R(x, y))\lor (\forall x (\exists y\, P(x, g(y, f(x))) \lor \neg Q(z)))$. $(\exists x\, \neg R(x, y))\lor (\forall x (\exists y\,( P(x, g(y, f(x))) \lor \neg Q(z))))$. Here just parethesis?