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?

Improve this question
$\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.

Improve this answer
$\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}$$

Improve this answer
$\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$$

Improve this answer
$\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

Improve this answer
$\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.