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

  • $\begingroup$ Is there an $y$ missing in the first formula ? $\endgroup$ – Mauro ALLEGRANZA Jan 30 at 13:51
  • $\begingroup$ Indeed, thanks! $\endgroup$ – Ayoub Rossi Jan 30 at 13:54
  • $\begingroup$ 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)) $ $\endgroup$ – NazimJ Jan 30 at 14:37


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.

  • $\begingroup$ 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? $\endgroup$ – Ayoub Rossi Jan 30 at 17:04
  • $\begingroup$ Second question: If I recognize a prenex normal form, should I always switch to an equivalent in non-prenex form $\endgroup$ – 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))$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.