How to prove this logical equivalence in predicate logic?

Question

Prove that:

$ ( \forall x)(\forall y)(\exists z)((P(x)\Rightarrow Q(y)) \wedge \neg Q(z))$

is equivalent with

$ \neg((\exists xP(x) \lor \forall zQ(z))$

How should I attempt such problems? I tried a lot like changing the implication in a disjunction. I applied Morgan rules here and there...

It looks like I should use the transitivity rule to get rid of the Y but I didn't find how

EDIT: Corrected question, thanks to Mauro

Answer 1

Hint

We have to work with Prenex normal form equivalences.

The first formula is equivalent to :

$((∃x)P(x) \to (∀y)Q(y)) ∧ (∃z)¬Q(z)$.

By De Morgan, the second formula is :

$¬(∃x) P(x) ∧ ¬(∀z)Q(z)$, i.e. $¬(∃x) P(x) ∧ (∃z)¬Q(z)$.

The first one implies the second : if we have that $(∃z)¬Q(z)$ holds, then it is false that $(∀y)Q(y)$ and thus also $(∃x)P(x)$ is false.

Thus : $¬(∃x) P(x)$ holds.

The second one implies the first : if $¬(∃x) P(x)$ holds, then $(∃x)P(x) \to R$ holds, for $R$ whatever.

Thus : $(∃x)P(x) \to (∀y)Q(y)$ holds.

Answer 2

$ \forall x \ \forall y \ \exists z((P(x)\rightarrow Q(y)) \land \neg Q(z)) \overset{Prenex}{\Leftrightarrow}$

$ \forall x \ \forall y \ ((P(x)\rightarrow Q(y)) \land \exists z \ \neg Q(z)) \overset{Implication}{\Leftrightarrow}$

$ \forall x \ \forall y ((\neg P(x) \lor Q(y)) \land \exists z \ \neg Q(z))) \overset{Distribution}{\Leftrightarrow}$

$ \forall x \ \forall y ((\neg P(x) \land \exists z \ \neg Q(z)) \lor ((Q(y) \land \exists z \ \neg Q(z)) \overset{Prenex \ x \ 2}{\Leftrightarrow}$

$ \forall x (\neg P(x) \land \exists z \ \neg Q(z)) \lor \forall y (Q(y) \land \exists z \ \neg Q(z)) \overset{Prenex \ x \ 2}{\Leftrightarrow}$

$ ( \forall x \ \neg P(x) \land \exists z \ \neg Q(z)) \lor (\forall y \ Q(y) \land \exists z \ \neg Q(z)) \overset{Quantifier Negation}{\Leftrightarrow}$

$ (\neg \exists x \ P(x) \land \neg \forall z \ Q(z)) \lor (\forall y \ Q(y) \land \neg \forall z \ Q(z)) \overset{Replacing Variables}{\Leftrightarrow}$

$ (\neg \exists x \ P(x) \land \neg \forall z \ Q(z)) \lor (\forall y \ Q(y) \land \neg \forall y \ Q(y)) \overset{Complement}{\Leftrightarrow}$

$ (\neg \exists x \ P(x) \land \neg \forall z \ Q(z)) \lor \bot \overset{Identity}{\Leftrightarrow}$

$ \neg \exists x \ P(x) \land \neg \forall z \ Q(z)\overset{DeMorgan}{\Leftrightarrow}$

$ \neg( \exists x \ P(x) \lor \neg \forall z \ Q(z))$