# Logical equivalences of quantifiers

This is an excerpt from the Kenneth Rosen book of Discrete Mathematics.

Show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧ ∀xQ(x) are logically equivalent (where the same domain is used throughout). This logical equivalence shows that we can distribute a universal quantifier over a conjunction. Furthermore, we can also distribute an existential quantifier over a disjunction. However, we cannot distribute a universal quantifier over a disjunction, nor can we distribute an existential quantifier over a conjunction.

Ques: Why we cannot distribute a universal quantifier over a disjunction, nor can we distribute an existential quantifier over a conjunction ?

Please, explain by an appropriate example. Thank You.

• You can try with some simple example, like "all (natural) numbers are either even or odd"... – Mauro ALLEGRANZA Jul 1 '16 at 17:50
• @MauroALLEGRANZA thanks man, you are saving my day. – Navneet Srivastava Jul 1 '16 at 17:52

Take the domain of interpretation to be the integers, let $P(x)$ be "$x$ is even", and let $Q(x)$ be "$x$ is odd", so in fact $Q(x) \leftrightarrow \neg P(x)$. Then $$\forall x\,(P(x) \lor Q(x))$$ is valid. However, it's false that $\forall x\,P(x) \lor \forall x\,Q(x)$: not every integer is even, and not every integer is odd.
The latter is a stronger statement. $\forall x\,P(x) \lor \forall x\,Q(x)$ implies $\forall x\,(P(x) \lor Q(x))$, but the converse is false.
Similarly, $\exists x\,(P(x) \land Q(x))$ implies $\exists x\,P(x) \land \exists x\,Q(x)$, but the latter doesn't imply the former. It's perhaps easier to see this if we rename a variable in the latter and write it as $\exists x\,P(x) \land \exists y\,Q(y)$. The same $P, Q$ work as a counterexample: there is an even integer $x$, and there is an odd integer $y$; but there is no integer that's both even and odd.