Why is: $\forall x(p(x)\vee q(x))\not\equiv\forall x(p(x))\vee \forall x(q(x))$?

1.4k Views Asked by At

Why is: $$\forall x(p(x)\vee q(x))\not\equiv\forall x(p(x))\vee \forall x(q(x))$$ Where as: $$\forall x(p(x)\wedge q(x))\equiv\forall x(p(x))\wedge \forall x(q(x))$$

And in the same manner, why is: $$\exists x(p(x)\vee q(x))\equiv\exists x(p(x))\vee \exists x(q(x))$$

But: $$\exists x(p(x)\wedge q(x))\not\equiv\exists x(p(x))\wedge \exists x(q(x))$$

2

There are 2 best solutions below

0
On BEST ANSWER

The universal quantifier distributes over conjunction but not necessarily over disjunction.   The existential quantifier distributes over disjunction but not necessarily over conjunction.   This is due to the associativity of the logical connectives and their relationship to the dual quantifiers.

A universal quantified predicate is true if the predicate is true for all elements in the domain of discourse.  This is in essence a logical conjunction, and that was an old fashioned way of writing the universal quantifier. $$\begin{align} \langle\, \forall x \, P(x) \,\rangle\;&\equiv \;\bigwedge_x\, P(x) \\[1ex] \langle\,\forall x \in \Bbb N : P(x)\,\rangle\;&\equiv\; P(0)\wedge P(1)\wedge P(2)\wedge \cdots \end{align}$$

Likewise the existential quantifier is essentially a disjunction over the domain of discourse.  It is held true if there is at least one element for which the predicate holds. $$\begin{align} \langle\, \exists x \, P(x) \,\rangle\;&\equiv \;\bigvee_x\, P(x) \\[1ex] \langle\, \exists x \in \Bbb N: P(x)\,\rangle\;&\equiv\; P(0)\vee P(1)\vee P(2)\vee \cdots \end{align}$$

Now, then, can you see why your statements are, or are not, equivalent?  It is basically a matter of where associativity holds.

$$\begin{align}\tag{Note: $\iff$} \because \langle \bigwedge_x \big( p(x)\wedge q(x) \big)\rangle \;&\iff\; \langle \bigwedge_x p(x) \rangle \wedge \langle \bigwedge_x q(x) \rangle \\[1ex] \tag{1} \therefore \langle \forall x \big( p(x)\wedge q(x) \big)\rangle \;&\iff\; \langle \forall x\, p(x) \rangle \wedge \langle \forall x\, q(x) \rangle \\[4ex]\tag{Note: $\impliedby$} \because \langle \bigwedge_x \big( p(x)\vee q(x) \big)\rangle \;&\impliedby \langle\bigwedge_x p(x) \rangle \vee \langle \bigwedge_x q(x) \rangle \\[1ex]\tag{2} \therefore \langle \forall x \big( p(x)\vee q(x) \big)\rangle \;&\impliedby \langle\forall x\, p(x) \rangle \vee \langle \forall x\, q(x) \rangle \\[4ex]\tag{Note: $\iff$} \because \langle \bigvee_x \big( p(x)\vee q(x) \big)\rangle \;&\iff\; \langle \bigvee_x p(x)\rangle \vee\langle \bigvee_x q(x) \rangle \\[1ex] \tag{3} \therefore \langle \exists x \big( p(x)\vee q(x)\big) \rangle \;&\iff\; \langle \exists x\, p(x)\rangle \vee\langle \exists x\, q(x) \rangle \\[4ex]\tag{Note: $\implies$} \because \langle \bigvee_x \big( p(x)\wedge q(x)\big) \rangle &\implies\; \langle \bigvee_x p(x) \rangle \wedge \langle \bigvee_x q(x) \rangle \\[1ex] \tag{4} \therefore \langle \exists x \big(p(x)\wedge q(x) \big)\rangle &\implies\; \langle \exists x\, p(x) \rangle \wedge \langle \exists x\, q(x) \rangle \end{align}$$

0
On

Hint. For the first one, let $p(x)$ be $x$ is even and $q(x)$ be $x$ is odd and let $x$ be any natural number.