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

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

• I feel you've missed, or perhaps forgotten, something more important here. In your parenthetical comment you talk about constructing a truth table for sanity purposes. The term sanity basically means health of mind. One can say that truth tables can help you keep your logical thinking healthy. You haven't layed down a formal system or even set of laws which to use so that you know you can prove this in some theory, so I don't see it necessary to solve the problem in any particular way. Due to the (relevant) completeness result you can use truth tables... – Doug Spoonwood Aug 4 '13 at 14:14
• And you have two variables here, in a 2-valued system. So, your truth table only has 4 rows. And since you've implicitly adopted an algebraic approach for a finite logical system, I will add that it turns out that you can always, in principle, use truth tables to solve any such problem once you have the tables for the connectives. So, I ask you to consider solving this problem in the "healthy" way by writing out the truth table. I do not believe Velleman would object at all to you doing that here. – Doug Spoonwood Aug 4 '13 at 14:19
• I understand that providing a truth table for both statements is sufficient to prove that both statements are indeed logically equivalent. I, however, feel that one my of weakest points is proving these types of problems algebraically, thus I chose this proof method over truth tables. Thank you for your thoughtful comment. – Bryan Baraoidan Aug 4 '13 at 16:04

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

• Ah thank you. I did not know you could apply the distributive law like that. – Bryan Baraoidan Aug 4 '13 at 16:15
• You're welcome! – Namaste Aug 4 '13 at 16:16
• @amWhy: It is nice to receive that FB! +1 – Amzoti Aug 5 '13 at 0:10
• @BryanBaraoidan Well, when you have something of the form $(a\color{blue}\vee b)\color{red}\wedge (c\color{blue}\vee d)$ and wish to derive something of the form $(w\color{red}\wedge x)\color{blue}\vee(y\color{red}\wedge z)$, well, not only may you attempt distribution to see what cancels, it is almost mandatory to try. – Graham Kemp Apr 16 '18 at 0:33

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}

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

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