# simplify boolean expression $(A \vee B) \wedge (\neg A \vee B)$ without truth table

How can I simplify $$(A \vee B) \wedge (\neg A \vee B)$$ (without a truth table)?

The result is $$B$$ but how can I show it?

Should I define $$C := (A \vee B)$$ and then use the distributive law?

$$C \wedge (\neg A \vee B) \Leftrightarrow (C \wedge \neg A) \vee (C \wedge B)$$ But after resubstitution it looks way more complicated.

Hint: One of the distributive laws says that $$(P\wedge Q)\vee R \equiv (P\vee R)\wedge (Q\vee R)$$.

Try to recognize the given expression as the right-hand side of such an expression and work back to the left.

After resubstitution you get:

$$((A \lor B) \land \neg A) \lor ((A \lor B) \land B)$$

Well, that's more complicated, yes, but still not too hard. For example, we can now apply Distribution on the left term:

$$(A \lor B) \land \neg A) \Leftrightarrow (A \land \neg A) \lor (B \land \neg A) \Leftrightarrow \bot \lor (B \land \neg A) \Leftrightarrow B \land \neg A$$

Plugging that back in, we get:

$$(B \land \neg A) \lor ((A \lor B) \land B)$$

Now, what about the right side? If you apply Distribuition here, you get:

$$(A \lor B) \land B \Leftrightarrow (A \land B) \lor (B \land B) \Leftrightarrow (A \land B) \lor B$$

... hmmm, that doesn't look too promising ... in fact, Distribution once more gets you to:

$$(A \land B) \lor B \Leftrightarrow (A \lor B) \land (B \lor B) \Leftrightarrow (A \lor B) \land B$$

... and we're back at where we were! ... OK, so that doesn't work.

Fortunately, here is something we can do:

$$(A \lor B) \land B \Leftrightarrow (A \lor B) \land (\bot \lor B) \Leftrightarrow (A \land \bot) \lor B \Leftrightarrow \bot \lor B \Leftrightarrow B$$

Aha! So, plugging that back in, we get:

$$(B \land \neg A) \lor B$$

and now we can do a similar trick:

$$(B \land \neg A) \lor B \Leftrightarrow (B \land \neg A) \lor (B \land \top) \Leftrightarrow B \land (\neg A \lor \top) \Leftrightarrow B \land \top \Leftrightarrow B$$

Now, the 'tricks' we did at the end actually reveal an important logical equivalence, known as:

Absorption

$$P \land (P \lor Q) \Leftrightarrow P$$

$$P \lor (P \land Q) \Leftrightarrow P$$

Also, the transformation at the beginning is known as:

Reduction

$$P \land (\neg P \lor Q) \Leftrightarrow P \land Q$$

$$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$$

So, with those, let's do the whole transformation again:

$$((A \lor B) \land \neg A) \lor ((A \lor B) \land B) \overset{Reduction, Absorption}{\Leftrightarrow} (B \land \neg A) \lor B \overset{Absorption}{\Leftrightarrow} B$$

Finally, though, I want to point out that the Distribution equivalence works both ways (it's an equivalence, remember?), so you could have done a 'Reverse' Distribution on your very original expression:

$$(A \lor B) \land (\neg A \lor B) \overset{Distribution}{\Leftrightarrow} (A \land \neg A) \lor B \Leftrightarrow \bot \lor B \Leftrightarrow B$$

And that equivalence actually has its own name as well:

$$(P \lor Q) \land (P \lor \neg Q) \Leftrightarrow P$$

$$(P \land Q) \lor (P \land \neg Q) \Leftrightarrow P$$

And with that, we can rework your transformation one more time:

$$(A \vee B) \wedge (\neg A \vee B) \overset{Adjacency}{\Leftrightarrow}B$$

Done!

But here's the moral: Put Absorption, Reduction, and Adjacency immediately into your 'Boolean Algebra Tool Box': they are very useful!

Your approach will also work. After expanding further we will get: $$A \neg A \vee B \neg A \vee A B \vee B B \Leftrightarrow B \neg A \vee A B \vee B \Leftrightarrow B (\neg A \vee A) \vee B \Leftrightarrow B \vee B=B$$