I am currently working through Velleman's book How To Prove It and was asked to prove the following
$(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$
This is my work thus far
$(P \to Q) \wedge (Q \to P)$
$(\neg P \vee Q) \wedge (\neg Q \vee P)$ (since $(P \to Q) \equiv (\neg P \vee Q)$)
$\neg[\neg(\neg P \vee Q) \vee \neg (\neg Q \vee P)]$ (Demorgan's Law)
$\neg [(P \wedge \neg Q) \vee (Q \wedge \neg P)]$ (Demorgan's Law)
At this point I am little unsure how to proceed.
Here are a few things I've tried or considered thus far:
I thought that I could perhaps switch some of the terms in step 3 using the law of associativity however the $\neg$ on the outside of the two terms prevents me from doing so (constructing a truth table for $\neg (\neg P \vee Q) \vee (\neg Q \vee P)$ and $\neg (\neg P \vee \neg Q) \vee \neg (P \vee Q)$ for sanity purposes)
I can't seem to apply the law of distribution since the corresponding terms are negated.
Applying demorgans law to one of the terms individually on step 2 or 3 doesnt seem to get me very far either.
Did I perhaps skip something? Am I even on the right track? Any help is appreciated
Best Answer
I'll start with your initial work, but instead of employing DeMorgan's as you did, we'll use the Distributive Law (DL), in two "steps":
$$\begin{align} (P \leftrightarrow Q) &\equiv (P \to Q) \wedge (Q \to P) \tag{correct}\\ \\ &\equiv (\color{blue}{\bf \lnot P \lor Q}) \land (\color{red}{\bf \lnot Q \lor P})\tag{correct} \\ \\ &\equiv \Big[\color{blue}{\bf \lnot P} {\land} \color{red}{\bf(\lnot Q \lor P)}\Big] \color{blue}{\lor} \Big[\color{blue}{\bf Q} \land \color{red}{\bf (\lnot Q \lor P)}\Big]\tag{DL}\\ \\ & \equiv \Big[(\color{blue}{\bf \lnot P} \land \color{red}{\bf\lnot Q)} \lor (\color{blue}{\bf\lnot P} \land \color{red}{\bf P})\Big] \lor \Big[(\color{blue}{\bf Q} \land \color{red}{\bf \lnot Q}) \lor (\color{blue}{\bf Q} \land \color{red}{\bf P})\Big]\tag{DL} \\ \\ &\equiv \Big[({\lnot P}\land \lnot Q) \lor \text{False}\Big] \lor \Big[\text{False} \lor (Q \land P)\Big]\tag{why?} \\ \\ &\equiv (P \land Q) \lor (\lnot P \land \lnot Q)\tag{why?}\end{align}$$