# 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. Sep 22, 2016 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. :) Sep 22, 2016 at 14:03
• @Raphael. It's sometimes called "idempotent". Sep 22, 2016 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? Sep 23, 2016 at 6:05
• @EmilJeřábek The OP being "not sure about" it? Sep 23, 2016 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. Sep 22, 2016 at 13:51
• @Raphael. Heh. Yes, I suppose so. Sep 22, 2016 at 13:54
• Isn't it easier (more natural) to apply distributivily directly to $A \lor(\lnot A\land B)$ ? Sep 22, 2016 at 16:34
• @HendrikJan. Yup, that would work too. Wonder why I didn't think of that first? Sep 22, 2016 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. Sep 22, 2016 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. Sep 22, 2016 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, 2016 at 17:10