By the end of this chapter you should be able to:
- State the postulates of a two-valued Boolean algebra and say where they differ from ordinary algebra.
- Prove any single- or two-variable theorem by perfect induction, and explain why a finite check constitutes a complete proof here.
- Form the dual of an expression, distinguish the dual from the complement, and use duality to halve the number of theorems you must remember.
- Apply De Morgan's theorems to two and to \(n\) variables, and carry out the same operation graphically as bubble-pushing.
- Obtain the complement of a function by De Morgan and by the dual-and-complement-literals method, and simplify a given expression algebraically, checking the result against a truth table.
Chapter 5 gave you seven gates and a way of tabulating what each does. That is enough to describe a circuit but not to improve one: two circuits with completely different gate counts can have identical truth tables, and no amount of staring at the schematics will show it. What is needed is an algebra — rules for transforming one expression into another guaranteed to have the same truth table.
That algebra was published by George Boole in 1854 as a calculus of logical propositions, and Claude Shannon showed in 1937 that it describes relay switching networks exactly. Everything in Part 2 rests on it. This chapter sets out the postulates, proves the theorems that follow, and develops the two results — De Morgan's theorems and the consensus theorem — that do most of the work in practice.
1 The Postulates of a Two-Valued Algebra
A Boolean algebra is defined on the set \(B = \{0, 1\}\) with two binary operations — OR written \(+\), AND written \(\cdot\) — and one unary operation, complement, written with an overbar. These are exactly the gates of Chapter 5. What makes the system an algebra is a short list of postulates, given by E. V. Huntington in 1904, from which every other rule follows.
| Postulate | OR form (a) | AND form (b) |
|---|---|---|
| P1 Closure | \(A + B\) is in \(\{0,1\}\) | \(A \cdot B\) is in \(\{0,1\}\) |
| P2 Identity element | \(A + 0 = A\) | \(A \cdot 1 = A\) |
| P3 Commutative | \(A + B = B + A\) | \(A B = B A\) |
| P4 Distributive | \(A + BC = (A+B)(A+C)\) | \(A(B + C) = AB + AC\) |
| P5 Complement | \(A + \overline{A} = 1\) | \(A \cdot \overline{A} = 0\) |
Notice that the postulates come in pairs, one with \(+\) and one with \(\cdot\). That pairing is not an accident of presentation; Section 3 shows it is the whole content of the principle of duality.
Two of these look wrong to a reader coming from ordinary algebra. The first is P4(a), \(A + BC = (A+B)(A+C)\): addition does not distribute over multiplication in the real numbers, since \(2 + 3\times 4 \neq (2+3)(2+4)\), but it does here, and the identity is one of the most useful in the chapter. The second is that there are no inverse operations. Ordinary algebra has subtraction to undo addition and division to undo multiplication; this algebra has neither, so a term may never be cancelled from both sides, and \(A + B = A + C\) does not imply \(B = C\) — take \(A = 1\) and it holds for every \(B\) and \(C\). The complement is not an inverse either: P5 says only that a variable and its complement OR to 1 and AND to 0, and everything about inversion follows from those two statements.
One piece of housekeeping: where parentheses do not force the order, the precedence is complement, then AND, then OR. So \(\overline{A}B + C\) means \((\overline{A} \cdot B) + C\). A long overbar is itself a grouping symbol, so \(\overline{A + B}\) means complement the whole sum — a different function from \(\overline{A} + \overline{B}\), as Section 4 shows.
2 Theorems and Proof by Perfect Induction
Every theorem here can be proved from the postulates, but a shortcut is available that ordinary algebra does not offer. Each variable takes only two values, so an identity in \(n\) variables makes only \(2^n\) distinct claims. Check them all and it is proved — not supported by evidence but proved, because nothing is left to check. This is proof by perfect induction: the construction of a truth table for each side of the proposed identity.
| Theorem | OR form (a) | AND form (b) |
|---|---|---|
| T1 Idempotence | \(A + A = A\) | \(A \cdot A = A\) |
| T2 Dominance | \(A + 1 = 1\) | \(A \cdot 0 = 0\) |
| T3 Involution | \(\overline{\overline{A}} = A\) (self-dual — it has no partner) | |
| T4 Associativity | \(A + (B + C) = (A + B) + C\) | \(A(BC) = (AB)C\) |
| T5 Absorption | \(A + AB = A\) | \(A(A + B) = A\) |
| T6 Simplification | \(A + \overline{A}B = A + B\) | \(A(\overline{A} + B) = AB\) |
| T7 De Morgan | \(\overline{A + B} = \overline{A}\,\overline{B}\) | \(\overline{AB} = \overline{A} + \overline{B}\) |
| T8 Consensus | \(AB + \overline{A}C + BC = AB + \overline{A}C\) | \((A+B)(\overline{A}+C)(B+C) = (A+B)(\overline{A}+C)\) |
Take T6(a), \(A + \overline{A}B = A + B\) — the most useful theorem in the list and the one students most often distrust. Perfect induction settles it in four rows:
| A | B | A′ | A′B | A + A′B | A + B |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
The last two columns agree in every row, so the theorem holds. The algebraic proof is worth seeing too, since it shows the technique of multiplying by 1 in a useful form:
The first step is P4(a) read from right to left, the second is P5(a), and the third is P2(b). Every step is a postulate, so the result is established for any Boolean algebra, not merely for the two-valued one.
Absorption, T5(a), removes gates fastest in practice:
In words: if \(A\) alone already makes the function 1, any product containing \(A\) is redundant whatever else it contains. Recognising absorption in a long expression is most of the skill of algebraic simplification.
Idempotence, T1(a), separates this algebra from arithmetic most clearly: \(A + A = A\), because there is no value above 1 for a second 1 to carry into. Its practical use runs the other way — since \(A = A + A = A + A + A\), a term may be duplicated as often as convenient, and Worked Example 6.2 uses one product term three times over.
3 The Principle of Duality
Look again at the tables in Sections 1 and 2. Every postulate and every theorem except involution appears twice, in an OR form and an AND form, and the two are related by a fixed recipe: interchange \(+\) and \(\cdot\), interchange 0 and 1, leave the variables and their complements alone. The result is the dual of the original statement.
Because the postulates were given in dual pairs, any proof written using them can be rewritten line by line into its dual, and each line remains a legitimate application of the dual postulate. There is therefore never any need to prove both halves of a theorem: prove one, and the other is free.
So the dual of \(A + AB = A\) is \(A(A+B) = A\), proved the moment the first is, and the dual of \(A + \overline{A}B = A + B\) is \(A(\overline{A} + B) = AB\). Duality halves the memory load of Section 2, and is why this chapter never proves an AND-form theorem separately.
There is one trap here, and it causes a great deal of confusion. The dual of an expression is not its complement. Consider
\(F\) is 1 for exactly two of the eight input combinations, \(ABC = 100\) and \(111\); its dual is 1 for six. They are different functions, and nothing requires a statement and its dual to agree on any input.
What is true, and what Section 5 uses, is the following relation between the three ideas. Taking the dual and then complementing every literal gives the complement of the original function:
Check it on the example: \(F_D(\overline{A},\overline{B},\overline{C}) = \overline{A} + (B + C)(\overline{B} + \overline{C})\), which is 1 for six input combinations — precisely the six on which \(F\) is 0.
4 De Morgan's Theorems and Bubble-Pushing
De Morgan's theorems bridge the AND world and the OR world, and are used more often than every other theorem in this chapter combined. For two variables:
In words: the complement of a sum is the product of the complements, and the complement of a product is the sum of the complements. Perfect induction proves both at once, and the table also disposes of the commonest error in the subject — that \(\overline{A+B}\) might equal \(\overline{A} + \overline{B}\), which columns four and eight show it does not.
| A | B | A + B | (A + B)′ | A′B′ | A · B | (A · B)′ | A′ + B′ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
The theorems extend to any number of variables, and the extension is proved by ordinary mathematical induction on the two-variable case. Suppose the result holds for \(n\) variables. Then for \(n+1\), grouping the first \(n\) together,
The middle step is the two-variable theorem applied to the bracketed sum and \(A_{n+1}\); the last is the inductive hypothesis. The base case \(n = 2\) is the table above, so the result holds for every \(n\), and the dual follows without further work.
The graphical form of the theorem is what a designer actually uses. Since a bubble means inversion, De Morgan says that a bubble may be moved from the output of a gate to all of its inputs, provided the body of the gate is changed between the AND shape and the OR shape. This is bubble-pushing.
The pay-off comes when bubbles are pushed through a whole network. Because two inversions in series cancel — T3, involution — a bubble pushed forward from one gate can annihilate a bubble on the gate it feeds, transforming the network without changing its function.
Read the lower circuit of Figure 6.2 the way its bubbles ask. The second-level gate is an OR shape with input bubbles, which by Figure 6.1 is a NAND, and those input bubbles cancel the output bubbles of the two first-level NAND gates, leaving \(F = AB + CD\). Algebraically:
Every two-level AND-OR circuit converts to an all-NAND circuit with the same number of gates, and every two-level OR-AND circuit converts to an all-NOR circuit. Chapter 10 makes this a formal procedure and Chapter 5's remark about CMOS explains why it is worth doing.
5 The Consensus Theorem and the Complement of a Function
The consensus theorem identifies a product term that can be deleted outright. If one term contains a variable and another contains its complement, the term made from their remaining literals — the consensus term — is redundant:
The proof needs the trick of multiplying by 1 in a chosen form:
The argument in words is shorter. For \(BC\) to matter, \(B\) and \(C\) must both be 1; but then either \(A = 1\) and \(AB\) is already 1, or \(A = 0\) and \(\overline{A}C\) is already 1. The consensus term is never the only term making \(F\) equal 1, so deleting it removes a gate and nothing else.
| A | B | C | AB | A′C | BC | AB + A′C + BC | AB + A′C |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
Two warnings. The pattern must be exact: in \(AB + \overline{A}C + BD\) the term \(BD\) is not the consensus of the first two and cannot be deleted. And the redundant term is sometimes worth putting back — Chapter 11 shows that it is precisely what prevents a static hazard, so a circuit minimised by this theorem may glitch where one that keeps the term will not. Minimal and correct are not always the same circuit.
The other standing problem of this section is the complement of a function. Two methods work, and both are worth having.
Find \(\overline{F}\) for \(F = A(\overline{B}\,\overline{C} + BC)\).
Method 1 — De Morgan, applied repeatedly from the outside in. The outermost operation is an AND of \(A\) with a bracket, so
Expanding gives \(B\overline{B} + B\overline{C} + C\overline{B} + C\overline{C} = B\overline{C} + \overline{B}C\), so \(\overline{F} = \overline{A} + B\overline{C} + \overline{B}C = \overline{A} + (B \oplus C)\).
Method 2 — dual, then complement every literal. The dual is \(F_D = A + (\overline{B} + \overline{C})(B + C)\); barring each literal gives \(\overline{A} + (B + C)(\overline{B} + \overline{C})\), the same expression. Method 2 is faster on a long expression because it is purely mechanical.
Both answers were checked against \(F\) over all eight rows: \(F = 1\) for \(ABC = 100\) and \(111\) only, and \(\overline{F} = 1\) for the other six.
6 Algebraic Simplification in Practice
Algebraic simplification has no algorithm: you look for a theorem that applies, apply it, and look again. That is exactly why Chapters 8 and 9 exist — the Karnaugh map turns the search into a picture and the Quine–McCluskey method into a procedure a computer can run. The algebra is still worth practising, because a designer who cannot see \(A + \overline{A}B = A + B\) in an expression will not recognise it on a K-map either. Three habits carry most of the work: factor out common literals, look for absorption, and expand a term deliberately when doing so creates something that will absorb.
Simplify \(F = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC\).
No term absorbs another and no pair combines without help. The move is to duplicate the last term twice, which idempotence permits:
Now pair each of the first three terms with one copy of \(ABC\):
Twelve literals and five gates become six literals and four gates. The function is the majority of three inputs — 1 whenever at least two of \(A\), \(B\), \(C\) are 1 — which is the voting element of a triple-redundant sensor system and, as Chapter 16 shows, the carry-out of a full adder. Verification over all eight rows:
| A | B | C | A′BC | AB′C | ABC′ | ABC | original F | AB + BC + CA |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
The last two columns agree in every row, which is the only acceptable proof that a simplification is correct.
Simplify \(F = (A + B)(A + \overline{B})(\overline{A} + C)\).
Apply P4(a) to the first two factors, treating \(A\) as the common term:
The expression is now \(A(\overline{A} + C)\), which is T6(b) directly:
Three OR gates and a three-input AND collapse to one two-input AND. Over all eight rows the original and \(AC\) agree: both are 1 only for \(ABC = 101\) and \(111\).
Simplify \(F = \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{B}\,\overline{C}D + \overline{A}B\overline{C}\,\overline{D} + \overline{A}B\overline{C}D + A\overline{B}\,\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}D\).
Take the terms in pairs, each pair differing only in \(D\):
The first two now differ only in \(B\):
The bracket is T6(a) with \(\overline{A}\) in the role of \(A\), so \(\overline{A} + A\overline{B} = \overline{A} + \overline{B}\), and
Twenty-four literals and seven gates become four literals and three gates, and the last form — a NAND feeding a two-input AND — is cheaper still. All sixteen rows of the original and of \(\overline{A}\,\overline{C} + \overline{B}\,\overline{C}\) agree: both are 1 for the six combinations in which \(C = 0\) and \(A\) and \(B\) are not both 1.
Notice what has no counterpart in ordinary algebra in these three examples: terms were duplicated, terms were expanded by multiplying by \((X + \overline{X})\), and factors were absorbed away entirely. Those moves, with De Morgan and consensus, are the whole toolkit.
7 Summary and Key Results
| Result | Statement | Where it is used |
|---|---|---|
| Absorption | \(A + AB = A\) | Deletes a whole product term; the fastest gate saving |
| Simplification | \(A + \overline{A}B = A + B\) | Removes a literal; appears constantly in K-map work |
| De Morgan | \(\overline{A+B} = \overline{A}\,\overline{B}\), \(\overline{AB} = \overline{A}+\overline{B}\) | Bubble-pushing; NAND/NOR conversion in Chapter 10 |
| Consensus | \(AB + \overline{A}C + BC = AB + \overline{A}C\) | Deletes a redundant term; restored to kill hazards in Chapter 11 |
| Duality | Swap \(+\) and \(\cdot\), swap 0 and 1 | Halves the theorem list; relates SOP and POS in Chapter 7 |
| Complement | \(\overline{F}(A,B,C) = F_D(\overline{A},\overline{B},\overline{C})\) | Converting between a function and its inverse form |
8 Common Mistakes
The bar must break and the operator must change. The correct results are \(\overline{A+B} = \overline{A}\,\overline{B}\) and \(\overline{AB} = \overline{A}+\overline{B}\). The two sides of the wrong version agree only when \(A = B\), so the error survives half of any casual test. A quick check on \(A = 1, B = 0\) exposes it: \(\overline{1+0} = 0\) but \(\overline{1} + \overline{0} = 1\).
The dual is obtained by swapping the operators and the constants and leaving the literals alone; the complement additionally bars every literal. They are different functions. The dual of \(A + \overline{A}B\) is \(A(\overline{A}+B)\), which equals \(AB\), whereas the complement is \(\overline{A}\,\overline{B}\). Only the combination — dual, then complement each literal — gives the complement of the function.
There is no subtraction, so \(A + B = A + C\) does not give \(B = C\), and \(AB = AC\) does not give \(B = C\). Both fail at \(A = 1\) and \(A = 0\) respectively. Every legitimate step replaces an expression with an equal one using a postulate or a theorem; if you cannot name the theorem you have just used, the step is probably not valid.
9 Chapter Review
1. Prove \(A(A + B) = A\) by perfect induction and again from the postulates.
By perfect induction: with \(A=0\) the left side is \(0 \cdot (0+B) = 0 = A\) for either value of \(B\); with \(A=1\) it is \(1 \cdot (1+B) = 1 = A\). All four rows agree. From the postulates: \(A(A+B) = AA + AB = A + AB = A(1+B) = A \cdot 1 = A\), using P4(b), T1(b), P4(b) again, T2(a) and P2(b).
2. Find the complement of \(F = AB' + CD\) and express it as a sum of products.
By De Morgan, \(\overline{F} = \overline{(A\overline{B})} \cdot \overline{(CD)} = (\overline{A} + B)(\overline{C} + \overline{D})\). Multiplying out gives \(\overline{F} = \overline{A}\,\overline{C} + \overline{A}\,\overline{D} + B\overline{C} + B\overline{D}\). Both forms were checked against \(F\) over all sixteen input combinations and complement it in every row.
3. State the dual of \(A + \overline{A}B = A + B\), and say whether the dual is a statement about the same function.
The dual is \(A(\overline{A} + B) = AB\), obtained by interchanging \(+\) and \(\cdot\). It is a valid identity, guaranteed by the principle of duality. It is not a statement about the same function: \(A + B\) is 1 for three input pairs and \(AB\) for one. Duality preserves validity, not the function.
4. Simplify \(F = \overline{A}B + AB + A\overline{B}\) to two literals, and identify the gate.
Duplicate \(AB\): \(F = (\overline{A}B + AB) + (AB + A\overline{B}) = B(\overline{A}+A) + A(B + \overline{B}) = B + A\). Alternatively \(\overline{A}B + AB = B\) and then \(B + A\overline{B} = B + A\) by T6(a). The result \(A + B\) is a single OR gate, replacing two inverters, three AND gates and a three-input OR.
5. In \(F = AB + \overline{A}C + BC\) the consensus theorem deletes \(BC\). Under what circumstances would you deliberately keep it?
When the circuit must be free of static hazards. If \(B = C = 1\) and \(A\) changes from 1 to 0, the output passes from being held by \(AB\) to being held by \(\overline{A}C\); if the inverter that produces \(\overline{A}\) is slower than the direct path, both terms are briefly 0 and the output produces a spurious 0 pulse. The redundant \(BC\) term stays at 1 throughout that transition and covers the gap. Chapter 11 develops this.