0
$\begingroup$

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:

enter image description here

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)$?

$\endgroup$
13
  • 1
    $\begingroup$ What's $P\land \lnot P$? Can you simplify it? $\endgroup$
    – kingW3
    Commented Apr 5, 2021 at 10:04
  • $\begingroup$ I don't know... Can you? Technically it is defined as a "contradiction" $\endgroup$
    – user32882
    Commented Apr 5, 2021 at 10:04
  • 2
    $\begingroup$ That's means that's equivalent to false $\bot$, whats $\bot \lor p$? $\endgroup$
    – kingW3
    Commented Apr 5, 2021 at 10:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – kingW3
    Commented Apr 5, 2021 at 10:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – kingW3
    Commented Apr 5, 2021 at 10:33

1 Answer 1

2
$\begingroup$

Hope this helps:

\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*}

$\endgroup$
2
  • $\begingroup$ Could you provide more supporting evidence about why you are allowing yourself to simply drop those two terms $\endgroup$
    – user32882
    Commented Apr 5, 2021 at 10:07
  • $\begingroup$ 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) $\endgroup$
    – xyz
    Commented Apr 5, 2021 at 10:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .