# Logical Equivalence

• October 21st 2010, 06:48 PM
DarK
Logical Equivalence
Can someone tell me off the bat if these 2 statements are logically equivalent or not. I am leaning towards "equivalent"

a) $\exists$x such that (p(x) or q(x))

b) $\exists$x such that p(x)) or $\exists$x such that q(x))
• October 21st 2010, 10:32 PM
PiperAlpha167
Quote:

Originally Posted by DarK
Can someone tell me off the bat if these 2 statements are logically equivalent or not. I am leaning towards "equivalent"

a) $\exists$x such that (p(x) or q(x))

b) $\exists$x such that p(x)) or $\exists$x such that q(x))

Yes, that would be a good way to lean.
But does getting agreement from me, or anyone else for that matter, really mean very much?
Maybe pick some system and establish it for yourself? There are systems that'll make life pretty easy.
In one that I have in mind you could reason informally as follows:

Necessity: (b) is a necessary condition for (a)
Take (a) as premiss. Pick an arbitrary name, say c, drop the existential quantifier and assume p(c) or q(c).
The 'or' (now as a main connective) should suggest "proof by cases". So derive (b) from p(c).
The second case (deriving (b) from q(c)) follows immediately from the first case by simply changing what needs to be changed. Except for tying up some loose ends, you're done (at least in one direction).

Sufficiency: (b) is a sufficient condition for (a)
Take (b) as premiss. I see another 'or' (and it's already the principal connective). Now what?
• October 22nd 2010, 01:43 AM
emakarov
Informally, existential quantification is similar to a (possibly infinite) disjunction. If the quantified variable ranges over the domain $\{a_1,a_2,\dots\}$, then $\exists x\,P(x)$ is $P(a_1)\lor P(a_2)\lor\dots$.

Viewed from this angle, $\exists x\,(P(x)\lor Q(x))$ is $(P(a_1)\lor Q(a_1))\lor (P(a_2)\lor Q(a_2))\lor\dots$, while $(\exists x\,P(x))\lor(\exists x\,Q(x))$ is $(P(a_1)\lor P(a_2)\lor\dots)\lor(Q(a_1)\lor Q(a_2)\lor\dots)$. Both of these big disjunctions have the same disjuncts, and since disjunction is commutative and associative, they are equivalent.

Similarly, universal quantification is similar to conjunction, so $\forall$ distributes over $\land$. (Universal quantification is also very similar to implication -- isn't it curious?) On the other hand $\forall x\,(P(x)\lor Q(x))$ is $(P(a_1)\lor Q(a_1))\land (P(a_2)\lor Q(a_2))\land\dots$, which is not equivalent to $(P(a_1)\land P(a_2)\land\dots)\lor(Q(a_1)\land Q(a_2)\land\dots)$. One can see from the distributivity of $\land$ over $\lor$ that the former formula includes the two disjuncts from the latter formula but also has other disjuncts. This means that the latter formula implies the former one, i.e., $(\forall x\, P(x))\lor(\forall x\, Q(x))$ implies $\forall x\,(P(x)\lor Q(x))$, as expected.