# Proof of logical equivalence of biconditional and other proposition

I am working on a problem where I need to show the logical equivalence of two propositions. One is a biconditional: $p \leftrightarrow q$. And the other is this: $(p \land q) \lor (\lnot p \land \lnot q)$

I can get the biconditional down to this: $(\lnot p \lor q) \land (\lnot q \lor p)$

And I don't know how to change the second proposition. Can someone give me a place to start?

-
I think you mean ($p$ AND $q$) OR (NOT $p$ AND NOT $q$). –  Joshua Ciappara Jan 19 '13 at 5:22
Oops! Yup. Made the change, thanks –  KKendall Jan 19 '13 at 5:23

$p$ iff $q$ is true precisely when either: (both $p$ and $q$ are true) or (both $p$ and $q$ are false).

This can be seen by just making truth tables. In any event, this is exactly the identity in question.

-

Without using truth tables, the following calculation shows that both forms are equivalent:

\begin{align} & (\lnot p \lor q) \land (\lnot q \lor p) \\ \leftrightarrow & \;\;\;\;\;\text{"distribute $\;\land\;$ over $\;\lor\;$, three times"} \\ & (\lnot p \land \lnot q) \lor (\lnot p \land p) \lor (q \land \lnot q) \lor (q \land p) \\ \leftrightarrow & \;\;\;\;\;\text{"contradiction, twice"} \\ & (\lnot p \land \lnot q) \lor \textrm{false} \lor \textrm{false} \lor (q \land p) \\ \leftrightarrow & \;\;\;\;\;\text{"simplify"} \\ & (\lnot p \land \lnot q) \lor (q \land p) \\ \end{align}

Note that we use implicitly that both $\;\land\;$ and $\;\lor\;$ are symmetric and associative.

-