Click here to download the episode worksheet.
Welcome to the Geek Author series on Computer Organization and Design Fundamentals. I’m David Tarnoff, and in this series we are working our way through the topics of Computer Organization, Computer Architecture, Digital Design, and Embedded System Design. If you’re interested in the inner workings of a computer, then you’re in the right place. The only background you’ll need for this series is an understanding of integer math, and if possible, a little experience with a programming language such as Java. And one more thing. Due to the computational nature of this episode, you might want to visit the transcript page found at intermation.com to download the episode worksheet.
In Episode 4.06 – Properties of Boolean Algebra, we proved a rather odd version of the distributive law. Using a truth table, we showed that the distributive law also works when distributing an OR operation across an AND, in other words, A + B · C is equal to (A + B) · (A + C). Let’s prove that property again, except this time using the identities and laws discussed over the past three episodes.
To the student of traditional algebra, (A + B) · (A + C) just looks like a factored quadratic equation. We can get back to the expanded quadratic equation by applying the FOIL method. FOIL is an acronym defining an order by which we can multiply the expression’s terms: First, Outside, Inside, Last. Basically, it’s three applications of the distributive law where we distribute a product across a sum. Well we know that the distributive law works when distributing an AND across an OR, so let’s apply FOIL to the right side of our Boolean expression, (A + B) · (A + C). It works this way:
AND-ing the first terms gives us A · A; AND-ing the outside terms gives us A · C; AND-ing the inside terms gives us B · A; and AND-ing the last terms gives us B · C. This makes the expanded expression A · A + A · C + B · A + B · C (read A AND A OR A AND C OR B AND A OR B AND C).
Before going further, let’s introduce a trick we can use to help us spot where we can simplify an expression using an identity, red flags so to speak. First, anytime a term is combined with itself (the idempotent law), something will drop out. Second, when a term is combined with its inverse (the inverse law), something will drop out. Lastly, when a term is combined with a constant one or zero (the annulment law or identity law), something will drop out. Therefore, if we search our expression for constants or terms combined with themselves or their inverses, we know we’ve found something to simplify.
In the case of the expanded quadratic expression we determined earlier, we see a term combined with itself. The idempotent law for the AND operation states that anytime we AND something with itself, it equals itself. In other words, one of the terms drops out. This means that A AND A equals A. This simplifies our expression to A + A · C + B · A + B · C (read A OR A AND C OR B AND A OR B AND C).
It doesn’t look like the expression has any more cases where the identity, inverse, idempotent, or annulment laws can cancel out a term, so we need to manipulate the expression a bit until one of them shows up. It looks like the A input is contained in a number of the products that make up this expression. In order to make this clearer, let’s apply the commutative law to the third term, B AND A, so that we can switch the order to A AND B. This makes the expression A + A · C + A · B + B · C (read A OR A AND C OR A AND B OR B AND C).
The first three terms or products of this expression each contain the input A, so let’s pull A out of all three using the distributive law. Like multiplication, when you pull and A out of A, you’re left with one. That means after we pull A out of A + A · C + A · B, we’re left with A · (1 + C + B) (read A AND-ed with the sum of one OR C OR B). Inserting this back into our expression gives us A · (1 + C + B) + B · C (read A AND-ed with the sum of one OR C OR B, then OR-ed with B AND C).
Now another of our identities is showing itself. The annulment law for the OR operation states that anything OR-ed with one equals one. That means that the sum (1 + C + B) equals one, which simplifies the expression further to A · 1 + B · C (read A AND one OR B AND C).
A single application of the identity law for the AND operation turns A AND one into A, and we get A + B · C (read A OR B AND C), which equals the left side of our initial expression. Therefore, by using the properties of Boolean algebra, we have shown that A + B · C is equal to (A + B) · (A + C).
Let’s try another one. How far can we simplify the Boolean expression (A + B) · (B + A) (read the sum of A OR B AND-ed with the sum of B OR A-bar)?
Once again, we have what looks like a factored quadratic expression, so let’s multiply through using FOIL. AND-ing the first terms gives us A AND B; AND-ing the outside terms gives us A AND A-bar; AND-ing the inside terms gives us B AND B; and AND-ing the last terms gives us B AND A-bar. The expanded expression is A · B + A · A + B · B + B · A (read A AND B OR A AND A-bar OR B AND B OR B AND A-bar).
Remember that if an expression contains constants or contains terms combined with themselves or their inverses, something is going to simplify. The expanded expression contains two of these situations. First, the second product of our expression is A AND A-bar. The inverse law of the AND operation states that anytime something is AND-ed with its inverse, the result is zero. So we replace this term with zero.
The third product of our expression is B AND B. The idempotent law of the AND operation states that anything AND-ed with itself is itself. That means that the third term becomes B. After performing these substitutions, the expression becomes A · B + 0 + B + B · A (read A AND B OR zero OR B OR B AND A-bar).
The zero in our sum is another red flag. The identity law states that a zero drops out of an OR expression. This simplifies the expression to A · B + B + B · A (read A AND B OR B OR B AND A-bar).
Since there is a B in all three terms, we can pull it out of the sum using the distributive law. This gives us B · (A + 1 + A) (read B AND-ed with the sum of A OR one OR A-bar).
The summation inside the parenthesis, A OR one OR A-bar, has two red flags. First, there’s a term, A, that is being OR-ed with its inverse. That simplifies to one based on the inverse law. Second, there’s a constant one being OR-ed with the other terms. If we apply the annulment law to this, which in the case of an OR states that a one OR-ed with anything equals one, we see that the other terms drop out leaving the one. That means the terms inside the parenthesis simplify to one, and we now have B · 1 (read B AND one).
Lastly, the identity law for the AND operation states that anything AND-ed with one is itself, and B AND one simplifies to B. That means that by using the properties of Boolean algebra, we have simplified (A + B) · (B + A) (read the sum of A OR B AND-ed with the sum of B OR A-bar) to just B.
Because of the difficulties that many students of Boolean algebra experience when learning to simplify Boolean expressions, our next episode is going to be dedicated to more examples of simplification. For transcripts, links, worksheets, or other podcast notes, please visit us at intermation.com where you will also find links to our Instagram, Twitter, Facebook, and Pinterest pages. Until the next episode, remember that while the scope of what makes a computer is immense, it’s all just ones and zeros.