Boolean Algebraic Identities
Like mathematical expressions, Boolean expressions can be manipulated to simplify them, make them easier to understand or implement, or reveal useful properties. As long as you follow certain rules, you can change the form of an expression without changing the underlying logic that it describes.
These are the main rules of Boolean algebraic manipulation (available as a pdf here: Boolean Identities). You don’t need to memorize them (though some of them will be used so often that you certainly will); what you need to be able to do is recognize where they apply and be able to use them.
Keep in mind that identities can be applied to subexpressions, not just single inputs. For example, A∙B∙C+A∙B∙C simplifies to 1 because of the inverse rule for OR.
One way to visualize these identities is using switch networks. For example, consider the "disapppearing opposite" rule. It claims that these two switch networks should be logically equivalent:
The top path of both networks creates a connection if A is true (active), so that much is clearly equivalent. And if A is false (inactive), both networks are then dependent on B, so that is also equivalent. The networks implement the same logic.
Algebraic Manipulation
A common use for algebraic manipulation is simplifying expressions. Consider the following expression:
A∙C+B∙C+A∙B∙C
Applying DeMorgan's to A∙B gives A∙C+B∙C+(A+B)∙C. Be careful -- the new parentheses are mandatory here to preserve the original order of operations!
Then C can be pulled out (reverse distribution) from the first two OR'd terms, giving (A+B)∙C+(A+B)∙C. It doesn't matter if the C is placed on the left or the right because AND is commutative.
Then (A+B) can be pulled out (reverse distribution again) to get (A+B)∙(C+C). If this looks confusing, remember that the identities can be applied to subexpressions; in this case A+B.
The inverse identity reduces C+C to '1', and then identity of AND means that the '1' can be removed, giving a final result of (A+B). Quite an improvement!
DeMorgan's Theorem
DeMorgan's theorem is one of the most-used and most important identities, so it is worth covering specifically. DeMorgan's theorem can be derived using the following process:
Start with the AND function (this works with any function, but AND is simple and convenient):
| A | B | AND |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Invert all of the inputs and also the output:
| ? | ? | ? |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Based on what we did (invert the inputs and the output), this function is A∙B, but a quick examination of the truth table reveals that it is logically equivalent to OR. And the process above can be repeated starting with OR to show that A+B is logically equivalent to AND.
These two form aren't the ones shown in the table above though, and there are actually four forms that DeMorgan's theorem can take. You don't need to memorize the different forms though, because it is better explained by the process we just used: "if you invert all of the inputs, invert the output, and change AND to OR or OR to AND, the logic remains the same."
This can all be summarized in DeMorgan's square. In these four truth tables, moving horizontally inverts the outputs, and moving vertically inverts the inputs.
One thing that DeMorgan's theorem can help us accomplish is to swap between ANDs and ORs in an expression without changing the logic. For example, the expression A+B·C can be changed by applying DeMorgan's to the AND to get A+B+C, or by applying DeMorgan's to the OR to get A·B·C. You can confirm by creating a truth table for all of these expressions that they describe the same logic.
Another thing that DeMorgan's can do is break down "big bars" (inversions over subexpressions). This is needed, in particular, for implementing logic in switch networks, because it is not possible to create a switch network for an expression with big bars. Consider something seemingly simple like A+B. This has an OR in it, so you might think that a parallel connection of switches would work, but then there is no way to implement the inversion over the result of that subexpression. However, DeMorgan's says that instead of implementing the expression directly, you can implement A·B instead, and this can be accomplished by connecting two normally-closed switches in series.
Note that if using the "invert the inputs, invert the output, and switch ANDs and ORs" technique directly, this expression would first be in a form with two bars over the entire expression (one bar from the original expression and one bar from the "invert the output" step), but since two inversions cancel (double complement), that cancelling is usually done immediately instead of keeping it as an intermediate step.
Here is a more complicated example: create a switch network that implements the expression
A∙(B∙C+D+E)
To implement this with a switch network, the expression must first be manipulated to only have inversions over individual inputs by applying DeMorgan's theorem to big bars.
When applying DeMorgan's theorem, it is usually beneficial to start on the outside and work your way down. To avoid making mistakes, be very careful to only apply the manipulation to the operator(s) directly under the bar you are working on (i.e., directly before that bar in order of operations). In this example, that means first applying DeMorgan's to the bar over the whole expression, and the operator directly under it is the AND on the left, because everything on the right would come before that AND in order of operations.
One input to that AND is A and the other inputs is B∙C+D+E, so those get inverted. Inverting the output cancels with the bar over the whole expression, leaving a result of
A+B∙C+D+E
There is still a big bar (more than one, but again, work from the outside in), so apply DeMorgan's to it. The operator directly under that bar is a three-input OR with inputs B∙C, D, and E. As before, applying DeMorgan's to this will cancel the big bar, but notice that it also cancels the bar over the B∙C term. The result is
A+B∙C∙D∙E
At this point, a switch network can be created.
Summary
- Like with mathematical expressions, Boolean expressions can be manipulated by following rules that preserve the logic. Some of these look very similar to mathematical manipulations, but some are quite different.
- Manipulating expressions can be beneficial to simplify or to change to a different form, such as a form that uses specific operations (e.g. only ANDs and NOTs) or a form without any "big bars" (inversions over subexpressions).
- DeMorgan's theorem is particularly useful for those two goals. DeMorgan's theorem can be described as "inverting the inputs, inverting the output, and switching ANDs for ORs and vice versa preserves the logic."
- You should be able to apply the Boolean identities to achieve any of the above goals.