2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Nev Feb 15 at 23:03
  • 1
    $\begingroup$ @nev all your steps were correct, and you did get close, so I would give you a good chunk of the points! :) $\endgroup$ – Bram28 Feb 15 at 23:05
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Nev Feb 15 at 23:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.