# Simplify [p∧ (¬(¬p v q)) ] v (p ∧ q) so that it become p, q, ¬p, or ¬q

Had a question on a test that asked for us to simplify (using rules of inference) the following proposition: [p∧ (¬(¬p v q)) ] v (p ∧ q)
to p, q, or their negation (¬p, ¬q). Here is what I did:

1) [p∧ (¬(¬p v q)) ] v (p ∧ q)

2) [p∧ (p ∧ ¬q)) ] v (p ∧ q) DeMorgan's Law

3) [(p∧ p) ∧ ¬q] v (p∧ q) Associative law

4) [p ∧ ¬q] v (p∧ q) Idempotent law

Step 4 is where I got stuck. I didn't know what to do afterwards. So I substituted S= (p∧ q) and did distributive law

5) [p ∧ ¬q] v S

6) (S v p) ∧ (S v ¬q) Distributive law

7) [ (p∧q) v p ] ∧ [ (p∧q) v ¬q] Substitute S=(p∧q) back in

8) [ (pvp) ∧ (pvq) ] ∧ [ (¬q v p) ∧ (¬q v q) ] Distributive law

9) [ p ∧ (pvq) ] ∧ [ (¬q v p) ∧ T ] Idempotent law and Domination law

10) p ∧ (¬q v p) Absorption and Identity law

I stopped there. I didn't know how to further simplify step 10 into p, q, ¬p, or ¬q. I was thinking maybe absorption law? But p ∧ (¬q v p) is not the same as p ∧ (q v p), so I couldn't simplify it to p, correct? Can someone help me further simplify it? Do you think I will get most the marks for this question or was my approach completely wrong?

This is a common 'mistake': to Distribute when you should really 'Un-Distribute'. That is, you can see:

$$(p \land \neg q) \lor (p \land q)$$

as the result of applying Distribution to:

$$p \land (\neg q \lor q)$$

But given that this is an equivalence, that means you can go the other way around as well (i.e. 'un-distribute' ... sometimes I call this 'reverse distribution' or 'factoring')

Note that from your last line we can do this as well:

$$p \land (\neg q \lor p) = (\bot \lor p) \land (\neg q \lor p) = (\bot \land \neg q) \lor p = \bot \lor p =p$$

Finally, the fact that $$(p \land q) \lor (p \land \neg q)$$ works out to just $$p$$ is such a common and handy equivalence that it has been given its own name:

$$(p \land q) \lor (p \land \neg q) =p$$

(and its dual form:) $$(p \lor q) \land (p \lor \neg q)=p$$

So, definitely put that one in your boolean algebra toolbox!

• Ohhhh you're totally right, that went right over my head. Judging by what I did for this question, do you think I'll lose all the marks? – Nev Feb 15 at 23:03
• @nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :) – Bram28 Feb 15 at 23:05

I'm going to use some shorthand notation: $$pq$$ for $$p \land q$$, and $$p + q$$ for $$p \lor q$$. Your proposition is $$p(\neg(\neg p + q)) + pq.$$ Distributing the negation on the left, we obtain $$p (\neg (\neg p + q)) + pq \equiv pp(\neg q) + pq.$$ Note that $$pp \equiv p$$. This now gives us $$p(\neg q) + pq.$$

We can "factor out" that $$p$$ to obtain $$p (\neg q) + pq \equiv p(\neg q + q) \equiv p,$$ and we're done.

• Yes I totally see that now, thanks! I really hope I get at least some partial marks. I was supposed to "undo" the distribution rather than distribute again – Nev Feb 15 at 23:04