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.
Best Answer
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.