0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.