1
$\begingroup$

I have the following boolean expression:

$$(A \land B) \lor (\lnot A \land C) \lor (B \land C)$$

I know this can be simplified to $$(A \land B) \lor (\lnot A \land C)$$ I can see that doing truth tables, drawing a circuit, a venn diagram. I understand it simplifies to that.

What I have trouble with are the actual steps of simplification using the boolean algebra laws. I'm probably missing something really really obvious, because I'm trying to freshen up my simplification skills via exercises and even with complex expressions don't have problems solving them, but this one leaves me stumped.

Could someone please provide a step by step simplification that displays how to simplify it?

Thank you very much for your time.

$\endgroup$
2
  • 3
    $\begingroup$ Without parentheses, your question is ambiguous. $\endgroup$
    – mrp
    Commented Apr 7, 2017 at 9:34
  • $\begingroup$ that's how I was given it. Or rather it had the form AB + !AC + BC = AB + !AC I just wanted to fancy format it on here. $\endgroup$
    – xNidhogg
    Commented Apr 7, 2017 at 9:48

3 Answers 3

2
$\begingroup$

The Concensus Theorem says:

$XY \lor Y'Z \lor XZ = XY \lor XZ$

So your exercise is really a particular application of this!

But let's assume the Concensus Theorem is not available for you to use.

Then you can do:

$(A \land B) \lor (\neg A \land C) \lor (B \land C) =$ (Adjacency)

$(A \land B) \lor (\neg A \land C) \lor (A \land B \land C) \lor (\neg A \land B \land C)=$ (Absorption x 2)

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

This assumes:

Adjacency

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

Absorption

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

$\endgroup$
1
$\begingroup$

$$(A \land B) \lor (\lnot A \land C) \lor (B \land C)$$ Insert a tautology: $$(A \land B) \lor (\lnot A \land C) \lor ((\lnot A \lor A) \land B \land C)$$ Expand: $$(A \land B) \lor (\lnot A \land C) \lor (\lnot A \land B \land C) \lor (A \land B \land C)$$ Reorder: $$(A \land B) \lor (A \land B \land C) \lor (\lnot A \land C) \lor (\lnot A \land B \land C)$$ Insert tautology: $$(A \land B \land true) \lor (A \land B \land C) \lor (\lnot A \land C \land true) \lor (\lnot A \land B \land C)$$ Extract: $$(A \land B \land (true \lor C)) \lor (\lnot A \land C \land (true \lor B))$$ Absorb: $$(A \land B \land true) \lor (\lnot A \land C \land true)$$ Simplify: $$(A \land B) \lor (\lnot A \land C)$$

$\endgroup$
2
  • $\begingroup$ oh I see! I had to un-simplify it first with the tautology. That was enough to help me simplify it down (funnily enough different than the rest of your approach). Any hints on how I could improve "spotting" when it would be good to make an expression more complex instead of straight up trying to simplify? $\endgroup$
    – xNidhogg
    Commented Apr 7, 2017 at 10:00
  • 1
    $\begingroup$ @xNidhogg: Once you know that the $B \land C$ is redundant, you know that it needs to be absorbed into the rest. However that rest consists of two terms, and neither term has both $B$ and $C$ (so neither one can absorb it on its own) but they do have $A$ or $\lnot A$. It therefore made sense to insert $A \lor \lnot A$ to get things started. $\endgroup$ Commented Apr 7, 2017 at 10:12
0
$\begingroup$

By looking at the similar part, you just want to show $$ C\,\vee \,B \wedge \, C = C$$

This identity is described on wikipedia as the absorption property :https://en.wikipedia.org/wiki/Boolean_algebra#Laws. Intuitively, you can say that $B$ is absorbed by $C$ (via truth table for example). Indeed: If $C = 1$, then $C \vee \cdots =1 $. If $C=0$, $B \wedge C = 0$ so the end result will be $0$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .