3
$\begingroup$

How it the following logic equation $$(B \land \lnot C) \lor (A \land B) \lor (A \land C)\tag 1$$ simplified into $$(B \land \lnot C) \lor (A \land C)\tag 2$$

I'm simplifying a boolean equation for a breadboard circuit-work and I've used a couple of online boolean equation simplifiers to verify my solution but I just can't seem to understand how the equation $(1)$ is simplified to equation $(2)$? What happened to $A \land B$? I'm not yet fully knowledgeable on certain boolean algebra laws. I would really appreciate it if someone could show a clear solution together with what law was used.

$\endgroup$

2 Answers 2

4
$\begingroup$

If $A\land B$ is true, then one of $A\land C$ or $B\land\neg C$ will also be true already, depending on the truth value of $C$.

So adding an $A\land B$ disjunct will not make the expression more true than it already was.

You can show this symbolically by $$ \begin{align} & (B\land \neg C) \lor (A\land B)\lor (A\land C) \\ ={}& (B\land \neg C) \lor [(A\land B)\land (\neg C\lor C)]\lor (A\land C) \\ ={}& (B\land \neg C) \lor (A\land B\land \neg C) \lor (A\land B\land C) \lor (A\land C) \\ ={}& [(B\land \neg C)\land(1\lor A)] \lor [(A\land C)\land(1\lor B)] \\ ={}& [(B\land \neg C)\land1] \lor [(A\land C)\land1] \\ ={}& (B\land \neg C)\lor (A\land C) \end{align}$$

$\endgroup$
2
  • $\begingroup$ I greatly appreciate the step-by-step solution you've given since it made everything clear as day. (A∧B)∧(¬C∨C) seems to be making use of the multiplicative identity if I'm not mistaken? $\endgroup$ Aug 29, 2018 at 16:00
  • 1
    $\begingroup$ @JuliusFabrique: Yes, you could say it that way. $\endgroup$ Aug 29, 2018 at 16:21
2
$\begingroup$

If you make a Karnaugh map, and put an "X" into each place where $(B \land \lnot C) \lor (A \land B) \lor (A \land C)$ is true, these cells are also covered by $(A \land C) \lor (B \land \lnot C)$.

   | A | -A |  
   ------------------------------------------
 B | X |    |   C
   ------------------------------------------
 B | X | X  |  -C
   ------------------------------------------
-B | X |    |  C
   ------------------------------------------
-B |   |    |  -C     
   ------------------------------------------

To show that $(B\land \lnot C) \lor (A \land B) \lor (A \land C)$ implies $(B\land \lnot C) \lor (A \land C)$, we can reason by cases. If the first or third disjunct holds, we are done. If $(A \land B)$ holds, then there are two subcases: if $C$ holds then $(A \land C)$ holds, and if $\lnot C$ holds then $B \land \lnot C$ holds.

This reasoning can be written using Boolean algebra laws as:

  • Given $(B\land \lnot C) \lor (A \land B) \lor (A \land C)$
  • because $C \lor \lnot C = 1$, and $X \land 1 = X$, is equivalent to $(B\land \lnot C) \lor [ (A \land B) \land (C \lor \lnot C)] \lor (A \land C)$
  • by distributivity, is equivalent to $(B\land \lnot C) \lor [ (A \land B \land C) \lor (A \land B \land \lnot C) ] \lor (A \land C)$
  • by weakening $\land$ twice, implies $(B\land \lnot C) \lor [ (A \land C) \lor (B \land \lnot C) ] \lor (A \land C)$
  • is equivalent to $(B\land \lnot C) \lor (A \land C)$

You can see how using $C \lor \lnot C$ and then applying distributivity allows us to use Boolean algebra laws to simulate proof by cases.

The reverse implication, that $(B\land \lnot C) \lor (A \land B) \lor (A \land C)$ is implied by $(B\land \lnot C) \lor (A \land C)$, follows from weakening the $\lor$.

$\endgroup$

You must log in to answer this question.

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