Logical Equivalence: $\exists x((P(x) \land \lnot Q(x))\Leftrightarrow R(x)) \iff (\forall xP(x)\Rightarrow \exists y(Q(y) \lor R(y)))$

Question

I am trying to show LHS equivalent to RHS however, but I am unsure on this specific example.

Any help would be appreciated.

$$\exists x((P(x) \land \lnot Q(x))\Rightarrow R(x)) \iff (\forall xP(x)\Rightarrow \exists y(Q(y) \lor R(y)))$$

Answer 1

We will apply the principle that two sentences are equivalent iff they are false in precisely the same situations. One could also say that we show the negations to be equivalent.

Instrumental to achieving this is the equivalence:

$$\neg(\phi\to \psi) \iff \phi \land \neg \psi$$

---

Thus: \begin{align*} &\neg\exists x\,((P(x) \land \neg Q(x))\to R(x))\\ \iff&\forall x \,\neg((P(x) \land \neg Q(x))\to R(x))\\ \iff& \forall x\,(P(x) \land \neg Q(x) \land \neg R(x)) \end{align*} Similarly: \begin{align*} &\neg(\forall x \,P(x) \to \exists y\,(Q(y)\lor R(y)))\\ \iff&\forall x\, P(x) \land \neg(\exists y\,(Q(y)\lor R(y)))\\ \iff&\forall x\, P(x) \land \forall y\, (\neg Q(y) \land \neg R(y))\\ \iff&\forall x\, P(x) \land \forall x\, (\neg Q(x)\land \neg R(x))\\ \iff&\forall x\,(P(x) \land \neg Q(x) \land \neg R(x)) \end{align*}