# Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$

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?

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.

• 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. – user1480135 Sep 22 '16 at 13:45
• @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. :) – Raphael Sep 22 '16 at 14:03
• @Raphael. It's sometimes called "idempotent". – Rick Decker Sep 22 '16 at 16:29
• 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? – Emil Jeřábek Sep 23 '16 at 6:05
• @EmilJeřábek The OP being "not sure about" it? – Raphael Sep 23 '16 at 7:47

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}

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

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

• That's essentially my answer. – Raphael Sep 22 '16 at 19:55

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

• 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. – Evil Sep 22 '16 at 17:10