1
$\begingroup$

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.

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

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.

$\endgroup$

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.