Prenex normal form question right?

336 Views Asked by At

Just to see if I'm on the right track here, I did this sample problem in my book which unfortunately has no answers. It is asking to find an equivalent formula in prenex normal form for this formula...

$$\forall xX=0\lor(\neg\exists z(x+z=x))$$

After some working I got to this answer...

$$\forall z(\forall xX=0\lor\neg(x+z=x))$$

Is this right?

1

There are 1 best solutions below

5
On BEST ANSWER

Your answer is correct, cheers!

But, from the looks of it, it is important to realise that you did the following:

\begin{align} \forall x(x =0 \lor (\neg\exists z(x+z=x))) &\iff \forall x(x=0\lor (\forall z \neg (x+z=x)))\\ &\iff \forall x(\forall z(x = 0\lor \neg(x+z=x)))\\ &\iff \forall z(\forall x(x=0\lor \neg(x+z=x))) \end{align}

i.e., the last step is not necessary. Now if you went from the second to the fourth expression in one go, you'd be mistaken in general -- particularly if it were $\exists x$ rather than $\forall x$.

It is only warranted to widen the scope of a quantification over $\lor$ or $\land$ (provided the other expression is free in the quantified variable). It is in general not warranted to widen the scope of a quantifier over another quantification: $\forall x \exists y (x=y)$ is not equivalent to $\exists y \forall x (x=y)$.