Digital Systems
3 min read
Boolean algebra
Boolean algebra is arithmetic on 0 and 1 with AND, OR and NOT. A few laws let you shrink a circuit or a condition without changing what it does, and De Morgan's rule is the one you will use most in code.
The notation
Write AND as a dot (A·B), OR as a plus (A + B) and NOT as an apostrophe (A'). Every variable is 0 or 1, so each law can be proved by trying all the input combinations in a truth table.
The laws that matter
| Law | AND form | OR form |
|---|---|---|
| Identity | A·1 = A | A + 0 = A |
| Null | A·0 = 0 | A + 1 = 1 |
| Complement | A·A' = 0 | A + A' = 1 |
| Absorption | A·(A + B) = A | A + A·B = A |
| De Morgan | (A·B)' = A' + B' | (A + B)' = A'·B' |
AND and OR also commute and distribute, much like multiplication and addition, with one twist: OR distributes over AND too.
Simplifying a circuit
Take Y = A·B + A·B'. Factor out A to get A·(B + B'). The complement law says B + B' = 1, and the identity law says A·1 = A. So Y = A: the output ignores B entirely. Two AND gates, a NOT and an OR collapse into a wire. Fewer gates mean less area, less power and less delay.
De Morgan in your code
De Morgan's laws say that inverting an AND turns it into an OR of the inverted inputs, and the other way round. In C, !(a && b) is the same as !a || !b, and !(a || b) is the same as !a && !b. Use it to flip a condition that reads awkwardly, for example when a pin is active low:
// "not (ready and enabled)" ...
if (!(ready && enabled)) { wait(); }
// ... is the same as "not ready, or not enabled"
if (!ready || !enabled) { wait(); }Try every combination of two inputs to convince yourself; a four-row truth table settles any doubt.