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.
Best Answer
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)$.