3
$\begingroup$

I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow.

I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ using a truth table as it's easy to see.

However, I can't seem to turn $A \vee (\neg A \wedge B)$ into $A \vee B$ using steps such as distributive / absorption etc.

Can someone talk me through the steps that you would take to simplify this?

$\endgroup$
8
$\begingroup$

Note that

$\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$;

you can "multiply out". Add in

$\qquad (A \lor \lnot A) \land B \equiv B$

and you are done.

$\endgroup$
  • $\begingroup$ Thanks, I clearly need a little more work as I'm not sure about 'multiplying out' but it at least points me in the right direction. $\endgroup$ – user1480135 Sep 22 '16 at 13:45
  • $\begingroup$ @user1480135 It follows from distributivity: $(A \lor B) \land (A \lor C) \equiv (A \land A) \lor (A \land C) \lor (A \land B) \lor (B \land C)$ which simplifies to $A \lor (B\land C)$ using absorption. And $A \land A \equiv A$, whatever the name of that is. :) $\endgroup$ – Raphael Sep 22 '16 at 14:03
  • 2
    $\begingroup$ @Raphael. It's sometimes called "idempotent". $\endgroup$ – Rick Decker Sep 22 '16 at 16:29
  • $\begingroup$ The "multiplying out" property is just one of the two distributive laws, which is fair game game according to the question. So what's the need to prove it? $\endgroup$ – Emil Jeřábek Sep 23 '16 at 6:05
  • $\begingroup$ @EmilJeřábek The OP being "not sure about" it? $\endgroup$ – Raphael Sep 23 '16 at 7:47
6
$\begingroup$

I'll write your expression as $A\lor(\neg A\land B)$. Then $$\begin{align} A\lor B &= A\lor((A\lor\neg A)\land B) &\text{identity}\\ &=A\lor (A\land B)\lor(\neg A\land B) &\text{distributive}\\ &=(A\lor (A\land B))\lor(\neg A\land B)\\ &= A\lor(\neg A\land B) &\text{absorption} \end{align}$$

$\endgroup$
  • 2
    $\begingroup$ If we wanted to be really picky, we'd note the use of associativity in steps 2 and 3. $\endgroup$ – Raphael Sep 22 '16 at 13:51
  • $\begingroup$ @Raphael. Heh. Yes, I suppose so. $\endgroup$ – Rick Decker Sep 22 '16 at 13:54
  • 1
    $\begingroup$ Isn't it easier (more natural) to apply distributivily directly to $A \lor(\lnot A\land B)$ ? $\endgroup$ – Hendrik Jan Sep 22 '16 at 16:34
  • $\begingroup$ @HendrikJan. Yup, that would work too. Wonder why I didn't think of that first? $\endgroup$ – Rick Decker Sep 22 '16 at 16:37
  • 1
    $\begingroup$ Well I do not blame you: I once wrote a five line solution for what was actually an axiom of the logic. $\endgroup$ – Hendrik Jan Sep 22 '16 at 16:40
3
$\begingroup$

$$a \lor (\neg a \land b) \equiv (\underbrace{a \lor \neg a}_{\equiv \text{True}}) \land (a \lor b) \equiv \text{True} \land (a \lor b) \equiv a \lor b$$

$\endgroup$
  • $\begingroup$ That's essentially my answer. $\endgroup$ – Raphael Sep 22 '16 at 19:55
-1
$\begingroup$

absorption rule: (if P then Q) iff (if P then (P and Q)) identity: (if P then Q) iff ((not P) or Q) so: (A or B) iff (if(not A) then B) (by identity) hence: (A or B) iff (if(not A) then ((not A) and B)) (by absorption) hence: (A or B) iff (A or ((not A) and B)) (by identity)

Basically, (A or B) iff (A or ((not A) and B)) is the absorption rule

$\endgroup$
  • 2
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Thank you. $\endgroup$ – Evil Sep 22 '16 at 17:10

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.