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$
3
$\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$
  • $\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$ – Julius Fabrique Aug 29 '18 at 16:00
  • 1
    $\begingroup$ @JuliusFabrique: Yes, you could say it that way. $\endgroup$ – Henning Makholm Aug 29 '18 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$

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.