proving logical equivalence $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$

Question

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

Answer 1

$$(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$$

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}$$

Answer 2

That's a great book. You'll learn a lot from it.

Justify the following: $$\begin{align} (\neg P \lor Q) \land (\neg Q \lor P) &\equiv[(\neg P\lor Q) \land \neg Q] \lor [(\neg P\lor Q)\land P] \\ &\equiv [(\neg P \land \neg Q) \lor (Q\land \neg Q)]\lor [(\neg P\land P)\lor (Q\land P)] \\ &\equiv (\neg P\land \neg Q) \lor (Q\land P).\end{align}$$

Answer 3

You can also "reverse" amWhy solution, starting with :

$(P \land Q) \lor ( \lnot P \land \lnot Q)$

you can use the distributivity laws to obtain :

$$[(P \land Q) \lor \lnot P] \land [(P \land Q) \lor \lnot Q]$$

and again :

$$(P \lor \lnot P) \land (Q \lor \lnot P) \land (P \lor \lnot Q) \land (Q \lor \lnot Q]$$

i.e.

$$T \land (Q \lor \lnot P) \land (P \lor \lnot Q) \land T$$

i.e.

$$(Q \lor \lnot P) \land (P \lor \lnot Q)$$

Now we use the equivalence between $(\lnot A \lor B) \quad$ and $\quad (A \rightarrow B)$, and get :

$$(P \rightarrow Q) \land (Q \rightarrow P)$$

that is

$P \leftrightarrow Q$.

Answer 4

For an alternative approach you can make the truth table of both logical expressions. $$ \begin{array}{|c|c| c|c| c|c| c|c| c|} \hline P & Q & \neg P & \neg Q & (P \wedge Q) & (\neg P \wedge \neg Q) & (P \wedge Q ) \vee (\neg P \wedge \neg Q) \\\hline V & V &F & F &V & F &V \\\hline V & F & F & V & F & F & F \\\hline F & V & V & F & F & F & F \\\hline F & F & V & V & F & V & V \\\hline \end{array} $$ and $$ \begin{array}{|c|c|c|} \hline P&Q& P \leftrightarrow Q \\\hline V&V&V \\\hline V&F&F \\\hline F&V&F \\\hline F&F&V \\\hline \end{array} $$