4
$\begingroup$

Hi I've been working through Applied Mathematics for Database Professionals and I'm stuck trying to proof this equivalence:

$$(P\Leftrightarrow Q)\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$$

I've tried to use distributivity property and De Morgan's theorem but I only got this:

$((P\wedge Q)\vee (\neg P \wedge \neg Q))\Leftrightarrow((P\Rightarrow Q)\wedge (Q\Rightarrow P))$

From this point I don't know what to do.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

We'll first apply, to the right-hand side of your biconditional, the following identity:

$$P \Rightarrow Q \equiv \lnot P \lor Q\quad \tag{logically equivalent}$$

Each side of the above equivalence implies the other (they are logically equivalent).

Applying this to the right had side of where you left off $(1)$, we get $(2)$:

$$((P\wedge Q)\vee (\neg P \wedge \neg Q))\iff((P\Rightarrow Q)\wedge (Q\Rightarrow P))\tag{1}$$

$$((P\wedge Q)\vee (\neg P \wedge \neg Q))\iff(\lnot P \lor Q)\wedge (\lnot Q \lor P))\tag{2}$$

Try using distribution on the right hand side (twice) until you arrive at an equivalent expression as the left hand side of the biconditional. Putting this all together, we get:

$$\begin{align} ((P\land Q) \lor (\lnot P \land \lnot Q)) & \iff ((P \Rightarrow Q) \land (Q \Rightarrow P)) \\ \\ & \iff ((\lnot P \lor Q) \land (\lnot Q \lor P)) \\ \\ & \iff [\lnot P \land (\lnot Q \lor P)] \lor [Q \land (\lnot Q \lor P)] \\ \\ & \iff [(\lnot P \land \lnot Q) \lor (\lnot P \land P)] \lor [(Q\land \lnot Q) \lor (Q \land P)] \\ \\ & \iff (\lnot P \land \lnot Q) \lor F \lor F \lor (Q \land P) \\ \\ & \iff (\lnot P \land \lnot Q) \lor (Q\land P) \\ \\ & \iff ((P \land Q) \lor (\lnot P \land \lnot Q)) \end{align}$$ By using the given identity, applying the distributive law twice, and remembering that $A \land \lnot A \equiv F\;$ and $\;A \lor F \equiv A$, we have obtained, from the right hand side of our biconditional, the equivalent expression on the left-hand side of $(2)$.

$\endgroup$
1
  • $\begingroup$ Let me know, Victor, if you're able to follow the above! ;-) $\endgroup$
    – amWhy
    Jun 15, 2013 at 23:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .