Simplifying P AND (P OR NOT Q)

Question

How can I simplify this? I've tried invoking Demorgan's Law and I get

P AND (NOT (NOT P AND Q)) but I can't seem to simplify this further.

The answer is P, but how can I prove this?

Answer 1

$$P(P+\overline{Q})=P+P\overline{Q}=P$$

Answer 2

You can think of it as (P AND P) OR (P AND NOT Q).

This is true if and only if P is true. If P is false, it makes both arguments of the 'OR' false.

Answer 3

$P \land (P \lor \lnot Q) = (P \land P) \lor (P \land \lnot Q) = P \lor (P\land \lnot Q)$

If $P$ then clearly this expression holds. If $\lnot P$ then $\lnot (P\land \lnot Q)$ so we see the expression depends entirely on $P$.

Stuff below is why you were confused, be cause it is not equal to $P$.

$P \land \lnot (\lnot P \land Q) = P \land (\lnot (\lnot P) \lor \lnot Q) = P \land (P \lor \lnot Q) = (P\land P) \lor (P \land \lnot Q) = P\land \lnot Q$

Answer 4

Shahar's answer is the most direct. However, sometimes, these can be a bit tricky when first starting out. What I frequently like to do when handling these sort of problems is to use this identity:

phi(a, b, c, d, ...) = a AND phi(TRUE, b, c, d, ...) OR
                       NOT a AND phi(FALSE, b, c, d, ...)

I call this the 'factor' identity for lack of a better name, but there is probably an 'official' name out there somewhere.

Applying this to your problem, I would see that:

P AND (NOT (NOT P AND Q)) = P AND (P OR NOT Q))  /* Demorgan's */
                          = P AND (TRUE AND (TRUE OR NOT Q)) OR
                            NOT P AND (FALSE AND (FALSE OR NOT Q)) /*Factor*/
                          = P AND TRUE OR NOT P AND FALSE
                          = P

Be warned that this process is not necessarily the fastest method, but it always leads to simpler expressions.