Show that $(P\land\lnot Q)\lor(\lnot P \land Q)$ is equivalent to $(\lnot(P \land Q))\land(P \lor Q)$ without using truth tables

Question

I'm trying to show that $$(P\wedge \lnot Q)\vee(\lnot P\wedge Q) \equiv (\lnot(P \wedge Q)) \wedge (P\vee Q)$$ without using truth tables. I've been trying to expand either side through distribution and De Morgan's but I'm getting stuck with how to actually show that these are equivalent? Any tips would be great.

@JohnDouma : I guess you mean the RHS to be $\sim(A\land\sim B)$, with parentheses — MPW, May 18 '21 at 21:05
@MPW Yes. I got lazy with the parentheses. The not sign should distribute to give not A or B equals not A and not B. — John Douma, May 18 '21 at 21:27

score 2 · Accepted Answer · answered May 18 '21 at 20:51

You're on the right path with de Morgan and distributivity.

If you use de Morgan on the RHS you get $$(\neg P\vee\neg Q)\wedge(P\vee Q)=*$$ by distribution $$*\equiv ((\neg P\vee \neg Q)\wedge P)\vee ((\neg P\vee \neg Q)\wedge Q)=*$$ again, using distribution $$*\equiv (\neg P\wedge P)\vee(\neg Q\wedge P)\vee (\neg P\wedge Q)\vee (\neg Q\wedge Q)=*$$ finally $\neg P\wedge P\equiv\neg Q\wedge Q\equiv 0$, so you can remove them (since $0$ is the unit of $\vee$), so finally $$*\equiv (\neg P\wedge Q)\vee(\neg Q\wedge P)$$

Show that $(P\land\lnot Q)\lor(\lnot P \land Q)$ is equivalent to $(\lnot(P \land Q))\land(P \lor Q)$ without using truth tables

1 Answers1