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

Question

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.

Answer 1

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.

Answer 2

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:

Adjacency

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

Answer 3

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$