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

Prove that

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

without using truth tables. Instead, use various logic properties like De Morgan's, etc.

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.$$

$$\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$$

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?