Prove that $\neg (\neg P \lor (P \land \neg Q)) \equiv P \land Q$ without using truth tables

Using de Morgan's laws:

$$\neg(\neg P\lor (P\land \neg Q))\equiv \neg\neg P\land \neg(P\land \neg Q)$$

$$\equiv P\land (\neg P\lor \neg\neg Q)$$

$$\equiv P\land (\neg P\lor Q)$$

$$\equiv (P\land \neg P)\lor(P\land Q)$$

$$\equiv P\land Q.$$


Hint : a repeated application of DeMorgan's is all you need.

To start, $$\neg (\neg P \lor (P \land \neg Q)) = P \land (\neg{(P \land \neg Q))} $$

Can you proceed?


$$\neg(\neg P \lor (P\land\neg Q)) \leftrightarrow P\land Q$$ $$ P \land \neg(P\land\neg Q)\leftrightarrow P\land Q$$ $$ P \land (\neg P\lor Q)\leftrightarrow P\land Q$$ $$ (P \land \neg P )\lor( P\land Q)\leftrightarrow P\land Q$$ $$ P\land Q\leftrightarrow P\land Q$$