Prove $p ↔ q$ and $(p ∧ q) ∨ (¬p ∧ ¬q)$ are equivalent using logic laws

Question

I know that we can show this using a truth table but I can't prove it using logic laws.

p ↔ q ≡ (p→q)∧(q→p)

p ↔ q ≡ (¬p∨q)∧(¬q∨p)

p ↔ q ≡ ¬p∨(p∧q) ∧ ¬q∨(q∧p)

I go this far and then I'm stuck.

Answer 1

From the second line on use distributivity and

• $a \wedge \lnot a = F$
• $a \vee F = a$

\begin{eqnarray*} (\lnot p \vee q) \wedge (\lnot q \vee p) & = & (\lnot p \wedge \lnot q) \vee (\lnot p \wedge p) \vee (q \wedge \lnot q) \vee (q \wedge p) \\ & = & (\lnot p \wedge \lnot q) \vee F \vee F \vee (q \wedge p) \\ & = & (\lnot p \wedge \lnot q) \vee (q \wedge p) \\ \end{eqnarray*}

Answer 2

Oh my goodness, you were almost there! You had to take just one more step! You had:

$p ↔ q ≡ (p→q)∧(q→p)$ ... By rewriting $\equiv$ ('Equivalence')

$≡ (¬p∨q)∧(¬q∨p)$ ... By rewriting $\to$ ('Implication')

$≡ ¬p∨(p∧q) ∧ ¬q∨(q∧p)$ ... By 'Reduction', which states that $¬p∨(p∧q) \equiv ¬p∨q$

... OK, and now just do:

$≡ (¬p∧ ¬q)∨(p∧q)$ ... By 'Distribution'!!

... ok , ok, it isn't just Distribution,; you also need to realize that $p∧q$ and $q∧p$ are the same term .. so you need Commutation as well.

More importantly though, you really needed to add some parentheses to line 3:

$≡ (¬p∨(p∧q)) ∧ (¬q∨(q∧p))$

And, had you done, that, I think it would have been more likely that you would have noticed the possibility or recognizing that the two terms here both share the term $p \land q$ (again, after commutation), and hence that Distribution would have gotten you there!