# How to prove this logical equivalence in predicate logic?

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

• Is there an $y$ missing in the first formula ? – Mauro ALLEGRANZA Jan 30 at 13:51
• Indeed, thanks! – Ayoub Rossi Jan 30 at 13:54
• Well in the case that $Q(y)$ for all $y$, then it is true for any specific choice of $y$, namely $z$. Hence we can replace $\forall y(P(x) \rightarrow Q(y))$ with $(P(x) \rightarrow Q(z))$ – NazimJ Jan 30 at 14:37

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.

• One question: You say we have to work with prenex normal form but your first step switches to a non-prenex normal form if I'm not wrong? – Ayoub Rossi Jan 30 at 17:04
• Second question: If I recognize a prenex normal form, should I always switch to an equivalent in non-prenex form – Ayoub Rossi Jan 30 at 17:06

$$\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))$$