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?

score 3 · Accepted Answer · answered Dec 18 '14 at 02:40

3

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

answered Dec 18 '14 at 02:40

Shahar

3,302

How did you go from P OR (P AND Q) to P? – Jason Dec 18 '14 at 02:42
3

@Jason In an intuitive sense, $P\overline{Q}$ will only be true if $P$ is true, and will be false if it isn't, so $P\overline{Q}$ will be obsolete in $P+P\overline{Q}$ since we don't need to care about the values of $Q$. More "algebraic" explanation: $$P+P\overline{Q}=P(\underbrace{1+\overline{Q}}_{1})=P$$ – Shahar Dec 18 '14 at 02:51
It's also known as the law of Absorption. You can also verify it directly with truth-tables. – Bill Province Dec 18 '14 at 03:30
@Bill Province Yes I tried to use the absorption law, but can't I only use it when Q isn't negated? I.e., P + PQ = P, but P + P~Q can't be simplified by the absorption law, can it? – Jason Dec 18 '14 at 05:54
@Jason If you call R = ~Q then you have P + PR. – Cthulhu Dec 18 '14 at 08:43
This may somewhat depend on how strict the deductive system is that you are using. However, in many deductive systems I have seen, you can substitute expressions for the variables in the axioms freely. Hence, as @Jason suggests, treating R as ~Q allows this operation. Similarly, if you had P + P(ABC + DE), you should still be able to use absorption. Or, if you are able to introduce new variables via definitions (as Jason has done), you can accomplish the same. – Bill Province Dec 18 '14 at 21:33

turkeyhundt · Answer 2 · 2014-12-18T02:43:36.840

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.

edited Dec 18 '14 at 02:43

answered Dec 18 '14 at 02:38

turkeyhundt

7,733

user62748 · Answer 3 · 2014-12-18T03:10:39.717

2

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

edited Dec 18 '14 at 03:10

answered Dec 18 '14 at 02:43

user62748

340

The answer in the book says P, and so does the truth table, if you draw one – Jason Dec 18 '14 at 02:47
I was confused too and so I deleted my answer. The question is in the title, the text is what he tried. – MathMajor Dec 18 '14 at 02:47
@Jason A truth table would be sufficient to show that the statements are equivalent. – MathMajor Dec 18 '14 at 02:47
I need to do it with the basic laws though, such as demorgans, commutative, idempotent, etc – Jason Dec 18 '14 at 02:50
O ha ha. That's what I get for not reading the question more carefully! – user62748 Dec 18 '14 at 03:02

score 1 · Answer 4 · answered Dec 18 '14 at 04:10

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.

Simplifying P AND (P OR NOT Q)

4 Answers4