# Problem with converting predicate expression to Prenex Normal Form

if I have the following predicate:

$$\exists x \neg P(x) \lor (\exists{x} \neg Q(x) \land \forall x \neg R(x))$$

What I did:

First, I used the tautology $$\forall x A(x) \land \exists x B(x) = \forall y \exists x(A(y) \land B(x))$$ to transform the right part of the disjunction, so I got

$$\exists x \neg P(x) \lor \forall y \exists x( \neg Q(x) \land \neg R(y))$$

Now, I put the leftmost existential quantifier before the brackets so I get:

$$\exists x (\neg P(x) \lor \forall y \exists x( \neg Q(x) \land \neg R(y)))$$

Now, we can move the universal quantifier also to the left so we get:

$$\exists x \forall y( \neg P(x) \lor \exists x( \neg Q(x) \land \neg R(y)))$$

Now comes my problem:

I was taught that if I want to move the existential quantifier $$\exists x$$ to the left, I need to rename the variable $$x$$ because by moving to the left, we encounter a predicate that has $$x$$ in it (which is $$\neg P(x)$$). So, I rename $$x$$ and all occurences of it after the existential quantifier to $$z$$:

$$\exists x \forall y( \neg P(x) \lor \exists \color{red}z( \neg Q(\color{red} z) \land \neg R(y)))$$ so finally I get:

$$\exists x \forall y \exists z( \neg P(x) \lor ( \neg Q(z) \land \neg R(y)))$$.

However, my workbook got a different solution. They didn't employ the usage of the same tautology I used in step 1 so instead of getting $$\forall y \exists x (\neg R(y) \land \neg Q(x))$$, they simply got $$\exists x(\neg Q(x) \land \forall y \neg R(y))$$, so they ended up with the final result being

$$\exists x \forall y (\neg P(x) \lor (\neg Q(x) \land \neg R(y)))$$

Can anyone tell me what I'm missing?

• Terminological nitpick: A predicate is e.g. $P$; what you have there is a formula. Commented Jul 8, 2023 at 17:27

Observe that your result $$∃x∀y∃z\,\big(¬Px∨(¬Qz∧¬Ry)\big)$$ and your workbook's result $$∃x∀y\,\big(¬Px∨(¬Qx∧¬Ry)\big)$$ are both equivalent to $$∃a¬Pa∨(∃a¬Qa∧∀a¬Ra),$$ which is equivalent to $$∃a¬Pa∨∃a\,(¬Qa∧∀b¬Rb),$$ which is equivalent to $$∃a\,\big(¬Pa∨(¬Qa∧∀b¬Rb)\big).$$
$$\exists x (P(x) \lor Q(x)) \Leftrightarrow \exists x \ P(x) \lor \exists x \ Q(x)$$
(so they ‘undistribute’ the $$\exists x$$ in the first step)