Week 4: Logical Cameleons

Suppose that you walk into the forest today and see a purple chameleon.  Then next week, you walk by into same forest and see an orange chameleon.  The orange chameleon looks similar to the purple chameleon except for its colour.  Surely they are not the same chameleon, right?

A Purple Panther Chameleon

An Orange Panther Chameleon

            In logic, a similar problem occurs.  Consider these two logical sentences.  Let $D $ be a set and $P, Q$ be sentences:

                        (1) $\exists x \in D, P(x) \implies Q(x)$

                        (2)  $( \forall x \in D, P(x)) \implies ( \exists x \in D, Q(x))$

These two sentences look very different.  Surely they are not the same sentence, right? 

            For chameleons, you are out of luck but for logic, we can use logical axioms, which link together logical statements that are equivalent, to determine if two logical sentences are saying the same thing.  Let $S$ be a set and $P, Q, R$ be sentences.  These are our axioms:

Table of Logical Axioms for Dummies

Axiom	Result
Commutativity	$P \vee Q \iff Q \vee P$ $P \wedge Q \iff Q \wedge P$
Associativity	$P \vee (Q \vee R) \iff (P \vee Q) \vee R$ $P \wedge (Q \wedge R) \iff (P \wedge Q) \wedge R$
Distributivity	$P \vee (Q \wedge R) \iff (P \vee Q) \wedge (P \vee Q)$ $P \wedge (Q \vee R) \iff (P \wedge Q) \vee (P \wedge Q)$
Implication	$(P \implies Q) \iff (\neg P \vee Q)$
Bi-implication	$(P \iff Q) \iff ((P \implies Q) \wedge (Q \implies P))$
Identity	$P \wedge (Q \vee \neg Q) \iff P$ $P \vee (Q \wedge \neg Q) \iff P$
Idempotency	$P \wedge P \iff P$ $P \vee P \iff P$
DeMorgan’s Law	$\neg (P \wedge Q) \iff \neg P \vee \neg Q$ $\neg (P \vee Q)  \iff \neg P \wedge \neg Q$
Quantifier Commutativity	$\forall x \in S, \forall y \in S, P(x, y) \iff$ $\forall y \in S, \forall x \in S, P(x, y)$ $\exists x \in S, \exists y \in S, P(x, y) \iff$ $\exists y \in S, \exists x \in S, P(x, y)$
Quantifier Distributivity	$\forall x \in S, P(x) \wedge Q(x) \iff$ $(\forall x \in S, P(x)) \wedge (\forall x \in S, Q(x))$ $\exists x \in S, P(x) \vee Q(x) \iff$ $(\exists x \in S, P(x)) \vee (\exists x \in S, Q(x))$

Our job is determine if (1) and (2) are equivalent with these axioms.  Start with (1):

$\exists x \in D, P(x) \implies Q(x)$

By the implication axiom, then (1) has the same meaning as this sentence:

$\exists x \in D, \neg P(x) \vee Q(x)$

By the quantifier distributivity axiom, then (1) camouflages into this sentence :

$(\exists x \in D, \neg P(x)) \vee (\exists x\in D, Q(x))$

Use the implication axiom again so that (1) looks like this sentence:

$(\forall x \in D, P(x)) \implies (\exists x\in D, Q(x))$

We see that sentences (1) and (2) are equivalent even though they look different.  Appearances are always deceiving!