TITLE: Going from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨~q)
QUESTION [3 upvotes]: I am confused on how to go from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨ ~q). I know they are equal because I plugged them into a truth table and all of the rows have the same values. What would be some of the rules I could use to prove these two to be logically equivalent? I think I would need to use DeMorgan's Law at some point but I think there may be a step before that.

REPLY [4 votes]: You can just expand everything out:
\begin{align*}
(p \land \neg q) \lor (\neg p \land q)
&\equiv (p \lor \neg p) \land (p \lor q) \land (\neg q \lor \neg p) \land (\neg q \lor q) &\text{by Distributivity Law}\\
&\equiv (p \lor \neg p) \land (p \lor q) \land (\neg p \lor \neg q) \land (q \lor \neg q) &\text{by Commutativity Law}\\
&\equiv (\top) \land (p \lor q) \land (\neg p \lor \neg q) \land (\top) &\text{by Inverse Law}\\
&\equiv (p \lor q) \land (\neg p \lor \neg q) &\text{by Identity Law}\\
\end{align*}
{"set_name": "stack_exchange", "score": 3, "question_id": 921061}