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

Question

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.

Answer 1

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

Answer 2

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?

Answer 3

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

Answer 4

I haven't seen this question until now, but I would like to propose another approach (essentialy same as any other): $$\neg (\neg P\lor (P\wedge \neg Q))\equiv\neg((\neg P\lor P)\wedge (\neg P\lor \neg Q))\equiv\neg(1\wedge (\neg P\lor \neg Q))\equiv P\wedge Q.$$ You can see it immediately, but I wrote the most just in case. Whenever you see something like $\neg P\lor P$, you should consider it when you have some disjunction. It might be useful.