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

Question

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?

Answer 1

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:

Adjacency

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

Answer 2

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.