Boolean Algebra: How does $\bar A\bar BC+\bar A\bar C\bar D+A\bar CD+\bar AB\bar C$ become $\bar A\bar BC + \bar A\bar C\bar D+A\bar CD+B\bar CD$?

Question

I'm trying to understand one of the steps taken during the process of getting a cnf in Boolean algebra but I just cant understand what is happening here.

$$\bar A \bar B C + \bar A \bar C \bar D + A \bar C D + \bar A B \bar C$$ $$\bar A \bar B C + \bar A \bar C \bar D + A \bar C D + B \bar C D$$

It seems like they just exchange the !A for D , but I cannot understand which of the Boolean algebra laws they used.

Could someone help me understand it ?

Answer 1

Here is why:

$$A'B'C+A'C'D'+AC'D+A'BC'\overset{Absorption}{=}$$

$$A'B'C+A'C'D'+(AC'D+ABC'D)+(A'BC'D+A'BC'D')\overset{Association, Commutation}{=}$$

$$A'B'C+(A'C'D'+A'BC'D')+AC'D+(ABC'D+A'BC'D)\overset{Absorption, Adjacency}{=}$$

$$A'B'C+A'C'D'+AC'D+BC'D$$

Answer 2

Another trick:

The Consensus Theorem says:

$XY+X'Z=XY+X'Z+YZ$

which can be generalized to:

Nested Consensus

$WXY+WX'Z=WXY+WX'Z+WYZ$

Applying this to your statement:

$$A'B'C+A'C'D'+AC'D+A'BC'$$

$$\overset{Consensus: AC'D+A'BC' = AC'D+A'BC'+BC'D}{=}$$

$$A'B'C+A'C'D'+AC'D+A'BC'+BC'D$$

$$\overset{Consensus: A'C'D'+BC'D = A'C'D'+BC'D+A'BC'}{=}$$

$$A'B'C+A'C'D'+AC'D+BC'D$$

Answer 3

$$ \bar{A}B\bar{C} = \bar{A}B\bar{C}D + \bar{A}B\bar{C}\bar{D} $$

the second piece $\bar{A}B\bar{C}\bar{D}$ is already a subset of $\bar{A}\bar{C}\bar{D}$ so you get

$$ \begin{align} \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + \bar{A}{B}\bar{C} &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + (\bar{A}B\bar{C}D + \bar{A}B\bar{C}\bar{D}) \\ &= \bar{A}\bar{B}{C} + (\bar{A}\bar{C}\bar{D} + \bar{A}B\bar{C}\bar{D}) + {A}\bar{C}{D} + \bar{A}B\bar{C}D \\ &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + \bar{A}B\bar{C}D \end{align} $$

Now, ${A}B\bar{C}D$ is a subset of ${A}\bar{C}D$ so you can split it out:

$$ \begin{align} \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + \bar{A}{B}\bar{C} &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + (\bar{A}B\bar{C}D + \bar{A}B\bar{C}\bar{D}) \\ &= \bar{A}\bar{B}{C} + (\bar{A}\bar{C}\bar{D} + \bar{A}B\bar{C}\bar{D}) + {A}\bar{C}{D} + \bar{A}B\bar{C}D \\ &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + \bar{A}B\bar{C}D \\ &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + ({A}\bar{C}{D} + {A}B\bar{C}D) + \bar{A}B\bar{C}D \\ &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + ({A}B\bar{C}D + \bar{A}B\bar{C}D) \\ &= \bar{A}\bar{B}{C} + \bar{A}\bar{C}\bar{D} + {A}\bar{C}{D} + B\bar{C}D \end{align} $$