# Proof that $(P \lor Q) \land \lnot(P \land Q) \equiv (P \land \lnot Q) \lor (Q \land \lnot P)$

I am trying to solve the following problem in Ted Sundstrom's Mathematical Reasoning, Writing and Proof:

If $$P$$ and $$Q$$ are statements, is the following statement true? $$(P \lor Q) \land \lnot(P \land Q) \equiv (P \land \lnot Q) \lor (Q \land \lnot P)$$

$$\equiv$$ here denotes logical equivalence (i.e the truth table of the right hand side expression is equivalent to that of the right side expression). Constructing a truth table indicates that these statements are indeed equivalent:

$$\begin{array} {|r|r|} \hline P & Q & P \lor Q & P \land Q & \lnot P & \lnot Q & \lnot (P \land Q) & (P \land \lnot Q) & (Q \land \lnot P) & (P \lor Q) \land \lnot(P \land Q) & (P \land \lnot Q) \lor (Q \land \lnot P)\\ \hline T & T & T & T & F & F & F & F & F & F & F\\ \hline T & F & T & F & F & T & T & T & F & T & T\\ \hline F & T & T & F & T & F & T & F & T & T & T\\ \hline F & F & F & F & T & T & T & F & F & F & F\\ \hline \end{array}$$

However I would like to see if they can be proved using first principles as summarized by the properties shown in the book. I copy these properties below for reference:

Here's what I came up with so far: \begin{align*} (P \lor Q) \land \lnot(P \land Q) &\equiv (P \lor Q) \land (\lnot P \lor \lnot Q) && \text{De Morgan's First law}\\ &\equiv \left[(P \lor Q) \land (\lnot P)\right] \lor \left[(P \lor Q) \land (\lnot Q) \right]&& \text{Distributive law}\\ &\equiv \left[ \lnot P \land (P \lor Q) \right] \land \left[\lnot Q \land (P \lor Q) \right] && \text{rearranging/grouping (is this legal?)} \\ &\equiv (\lnot P \land P) \lor (\lnot P \land Q)\lor (\lnot Q \land P)\lor (\lnot Q \land Q)&& \text{rearranging/grouping (is this legal?)} \end{align*}

The second and third terms in the very last step look interesting/similar to what I would like to prove, but I have no idea what to do with the first and last terms. Also I am not sure if the last two steps in my reasoning are actually valid statements, since the book says nothing about changing the order of and and or statements. Just my gut feeling is that it should be possible...

How can I finalize my proof that $$(P \lor Q) \land \lnot(P \land Q) \equiv (P \land \lnot Q) \lor (Q \land \lnot P)$$?

• What's $P\land \lnot P$? Can you simplify it? Commented Apr 5, 2021 at 10:04
• I don't know... Can you? Technically it is defined as a "contradiction" Commented Apr 5, 2021 at 10:04
• That's means that's equivalent to false $\bot$, whats $\bot \lor p$? Commented Apr 5, 2021 at 10:06
• So what's $(\lnot P\land P) \lor (\lnot P \land Q)$? and what's $(\lnot Q\land P) \lor (\lnot Q \land Q)$? And just "piece" those together. Commented Apr 5, 2021 at 10:23
• Yes to all questions. You also have $P\land \top \equiv P$ and $P\lor \top \equiv \top$, they weren't needed here but they are useful as well. Commented Apr 5, 2021 at 10:33

$$\begin{equation*} \begin{split} & (P \vee Q)\land \neg(P\land Q) \equiv [(P \vee Q)\land \neg P]\vee [(P\vee Q)\land \neg Q] \\[10pt] & \equiv [\underbrace{(P\land \neg P)}_{= F}\vee (Q\land \neg P)] \vee[(P\land \neg Q)\vee \underbrace{(Q \land \neg Q)}_{= F}] \\[10pt] & \equiv (Q \land \neg P)\vee(P \land \neg Q) = (P \land \neg Q) \vee (Q \land \neg P) \end{split} \end{equation*}$$
• I edited my answer to make it easier to understand. If yous till dont get it, it's basically this: Since $P \land \neg P =$ False, then you have: False $\vee (Q \land \neg P)$ which is $(Q \land \neg P)$ (in every possible case)