# Logical Equivalences with quantifiers

• Feb 13th 2013, 10:20 PM
aprilrocks92
Logical Equivalences with quantifiers
Hello

I am running into problems with the following:

x(P (x) ⇒ (Q(x) R(x)))⇐⇒ (¬∀xP (x) ∨ ¬∀yQ(y) ∨ ∃zR(z))

Although I do not master logical equivalences, I have been able to solve some earlier. However, since this problem has quantifiers, I don't know how to approach it.

Any help is highly appreciated.
• Feb 14th 2013, 06:08 AM
emakarov
Re: Logical Equivalences with quantifiers
P(x) => (Q(x) => R(x)) is equivalent to ~P(x) \/ ~Q(x) \/ R(x).

Existential quantifier distributes over disjunction (because existential quantifier is basically a disjunction over all elements of the domain): \$\displaystyle \exists x\,(A(x)\lor B(x))\iff(\exists x\,A(x))\lor(\exists x\,B(x))\$.

Next, existential quantifier changes into universal quantifier and vice versa when it is moved through a negation: \$\displaystyle \exists x\,(\neg A(x))\iff\neg(\forall x\,A(x))\$.

These equivalences are sufficient to derive the one you need.