De Morgan’s Laws
Augustus De Morgan (1806 - 1871) was a British math professor at London University (now University College London) 1. Among his educational works, he formulated two logical equivalence rules that we recognize today as De Morgan’s Laws. 2 De Morgan’s Laws are equivalence relations, which mean they provide different ways of saying the same thing. We use the symbol ≡ as the equivalence operator, giving us a convenient shorthand for saying that two things mean the same thing.
Video Lecture
Optimization of Circuits
De Morgan’s laws appear in a variety of contexts, as they have applications in a number of different areas of logic and mathematics. You have likely encountered them before in classes on logic, set theory, and discrete mathematics. In programming, we use these laws to try to simplify code.
At the architectural level, a major use of De Morgan’s laws is to save money and improve performance. Each gate in a logical circuit has two costs associated with it: the upfront cost of producing the electronic component and the ongoing operational cost from the power required to operate the gate. While the costs of a single gate inside a single circuit are negligible, remember that computers contain billions of circuits and are found in nearly every modern device. Consequently, even tiny savings here and there add up to significant amounts at scale.
A second benefit to reducing the number of gates in a circuit is to increase the speed of the resulting system. Each gate in a circuit takes a small amount of time for its output to stabilize after the inputs are received. The successive small amounts of time spent waiting for gates connected to one another to produce a stable output is called propagation delay, and minimizing the number of gates in series tends to minimize this time.
A + B ≡ A·B
De Morgan’s Laws can be presented in either order. I’m going to start with the first one, which is to say that A+B is equivalent to A·B. In English, this relation can be expressed as (NOT A) OR (NOT B) is equivalent to NOT (A AND B), or A NAND B for short. Figure 1 shows a circuit built both ways, driving two different outputs.
If we trace this circuit, we can produce a truth table like the one given in Table 1. Notice that both output columns Q0 and Q1 are the same, proving that the two implementations are equivalent.
| A | B | Q0 | Q1 |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
What De Morgan is telling us here is that we can replace a circuit that contains 3 gates (2 NOTs and 1 OR) with a single NAND gate. This change would save us a little upfront cost and ongoing power, and it would also execute slightly faster.
A·B ≡ A+B
Another circuit that we can simplify with De Morgan’s Laws is A·B. As shown in Figure 2, a NOR gate is equivalent to this circuit. The English expression is that (NOT A) AND (NOT B) is equivalent to NOT (A OR B), which we can further shorten to A NOR B.
We can again prove the equivalence by making a truth table as shown in Table 2. Once again, we see that the two output columns are the same, proving the implementations to be equivalent.
| A | B | Q0 | Q1 |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Once again, De Morgan allows us to replace 3 gates with 1 gate, saving some money and improving performance.
Practice Problems
Try working these problems before revealing the answers.
- Draw a circuit containing only one gate that implements A + B.
Show Answer
Use De Morgan’s Laws to simplify A + B to A·B. The result is a NAND gate:
- Draw a circuit containing only one gate that implements A·B.
Show Answer
Use De Morgan’s Laws to simplify A·B to A+B. The result is a NOR gate:
References and Further Reading
-
Sophia Elizabeth De Morgan. Memoir of Augustus De Morgan. London: Longmans, Green, and Co. 1882. Available from the Internet Archive. ↩
-
Augustus De Morgan. First Notions of Logic. London: Taylor and Walton. 1839. Available from Project Gutenburg. ↩
