Boolean Logic

The previous chapter established that every value inside a computer is, at the lowest level, a string of bits. We now turn to the rules by which those bits can be combined. The mathematics of true and false predates the electronic computer by nearly a century, and yet it fits the hardware so naturally that the two are almost impossible to separate in modern teaching. By the end of this chapter, you should be able to read a logical expression, build a truth table from it, simplify it by hand, and recognize the gates that implement it in silicon. These skills are the foundation for every digital circuit we will encounter from Chapter 4 onward.

01. Boolean Algebra

In 1854 the English mathematician George Boole published An Investigation of the Laws of Thought, in which he argued that logical reasoning could be carried out by manipulating symbols according to algebraic rules. His insight was that statements which can be either true or false behave a great deal like numbers that can be either 1 or 0, and that the connectives and, or, and not play roles analogous to multiplication, addition, and negation. Almost a century later, in 1937, Claude Shannon noticed that Boole's algebra described exactly the behavior of switching circuits made of relays. The marriage of the two ideas gave us the modern digital computer.

A Boolean variable is a variable that can take only the values 0 (false) and 1 (true). The three primitive operations are:

• AND, written $A \cdot B$ or simply $AB$, which is 1 when both operands are 1.
• OR, written $A + B$, which is 1 when at least one operand is 1.
• NOT, written $\overline{A}$ or $A'$, which inverts its operand.

The choice of $\cdot$ and $+$ for AND and OR is deliberate. Boolean AND distributes over Boolean OR exactly as multiplication distributes over addition in ordinary arithmetic, and many algebraic manipulations look familiar:

$A \cdot (B + C) = A \cdot B + A \cdot C.$

The analogy is not perfect, however. Boolean OR also distributes over Boolean AND, which is not true of arithmetic addition over multiplication:

$A + (B \cdot C) = (A + B) \cdot (A + C).$

This second distributive law is one of several places where Boolean algebra is more symmetric than ordinary algebra, and it is worth keeping in mind.

The basic identities of Boolean algebra are easy to state and worth memorizing. They come in dual pairs, where each pair is obtained from the other by swapping AND with OR and 0 with 1.

The principle of duality is more than a notational coincidence. Any theorem of Boolean algebra remains a theorem when AND is exchanged with OR and 0 is exchanged with 1. This means proofs come in pairs, and a circuit designer who has solved a problem one way often gets a second, equally valid solution for free.

02. Logic Gates

A logic gate is a physical circuit that implements a Boolean operation on electrical signals. A signal close to the supply voltage represents 1; a signal close to ground represents 0. Every gate takes one or more such signals as input and produces a signal as output, and it does so continuously: as soon as the inputs settle, the output settles to the corresponding value, with only a small physical delay.

There are seven gates that every architect should recognize on sight.

The NOT gate, also called an inverter, has one input. Its output is the logical negation of the input.

The AND gate has two or more inputs and outputs 1 only when all of them are 1.

The OR gate has two or more inputs and outputs 1 when at least one of them is 1.

The NAND gate is an AND followed by a NOT. Its output is 0 only when all inputs are 1.

The NOR gate is an OR followed by a NOT. Its output is 1 only when all inputs are 0.

The XOR gate, exclusive-or, outputs 1 when the inputs differ. With two inputs, $A \oplus B$ is 1 if exactly one of $A$ and $B$ is 1.

The XNOR gate is the negation of XOR; its output is 1 when the inputs match. It is sometimes called equivalence because it answers the question "are these two bits equal?".

Two of these gates, NAND and NOR, are special. Each of them is functionally complete, meaning that any Boolean function whatsoever can be built using only that one type of gate. This sounds like a curiosity but is in fact a deep practical advantage. CMOS, the technology used to fabricate almost every integrated circuit today, builds NAND and NOR gates more naturally and more cheaply than AND and OR gates, so the lower levels of real chips are dominated by them.

A short demonstration of completeness will make the point concrete. With NAND alone:

• $\overline{A} = \overline{A \cdot A}$ — connect both inputs of a NAND together.
• $A \cdot B = \overline{\overline{A \cdot B}} = \overline{(A \,\text{NAND}\, B) \,\text{NAND}\, (A \,\text{NAND}\, B)}$ — invert a NAND with another NAND used as a NOT.
• $A + B = \overline{\overline{A} \cdot \overline{B}} = \overline{A} \,\text{NAND}\, \overline{B}$ — by De Morgan's law, which we will meet in a moment.

In schematics, gates are drawn with conventional shapes that have not changed in fifty years.

Figure: Schematic symbols for the three primitive gates: AND, OR, and NOT, with their inputs A and B labeled and outputs written in Boolean notation

The small circle on the output of NOT, NAND, NOR, and XNOR is the universal symbol for inversion. When you see it on a wire, read it as "negate this signal."

03. Truth Tables

A truth table is the most direct way to specify a Boolean function: list every possible combination of input values and write down the output for each. For $n$ input variables there are $2^n$ rows.

The truth tables for the basic two-input gates are as follows.

A truth table is more than a teaching aid. It is a complete specification of any combinational function. If two expressions produce identical truth tables, they are logically equivalent, no matter how different they look on paper, and the simpler of the two is preferable.

There is a useful counting argument that follows immediately. A function of $n$ Boolean inputs has $2^n$ rows in its truth table, and each row's output can independently be 0 or 1, so there are $2^{2^n}$ distinct Boolean functions of $n$ variables. For $n = 2$ that is sixteen functions, of which the seven gates above are the most useful. For $n = 3$ it is 256, and for $n = 4$ it is already 65,536. The space of possible functions grows astronomically with the number of inputs, which is why we need algebra to reason about them rather than brute-force enumeration.

A function can always be reconstructed from its truth table in two canonical ways. The sum-of-products form takes every row whose output is 1, writes the minterm for that row (an AND of all the inputs, with each input negated if it is 0 in that row), and ORs the minterms together. The product-of-sums form is the dual: take every row whose output is 0, write the maxterm (an OR of all the inputs, negated if 1 in that row), and AND the maxterms together. These two canonical forms are not minimal — they are usually quite wasteful — but they are mechanical, and they prove that the basic gates are enough to build any function from its truth table.

For example, the XOR function $A \oplus B$ has its truth table above. The two rows where the output is 1 are $(A, B) = (0, 1)$ and $(1, 0)$. The corresponding minterms are $\overline{A} \cdot B$ and $A \cdot \overline{B}$, giving the canonical sum-of-products form

$A \oplus B = \overline{A} \cdot B + A \cdot \overline{B}.$

This is exactly the algebraic identity most textbooks use as the definition of XOR.

04. De Morgan's Laws

Of all the identities of Boolean algebra, two stand out as so frequently useful that they have their own name. They were stated in the mid-1800s by the English mathematician Augustus De Morgan, who was a contemporary of Boole.

$\overline{A \cdot B} = \overline{A} + \overline{B}$ $\overline{A + B} = \overline{A} \cdot \overline{B}$

In words: the negation of an AND is the OR of the negations, and the negation of an OR is the AND of the negations. These rules generalize to any number of inputs and to nested expressions. They are the formal basis of the duality principle and the technical reason why NAND and NOR each suffice on their own.

Both laws can be verified by exhaustion on a four-row truth table, but it is more illuminating to read them in plain English. "It is not the case that both rained and snowed today" means the same thing as "either it did not rain today, or it did not snow today." "It is not the case that either rained or snowed today" means the same as "it did not rain today, and it did not snow today." Logic textbooks find an endless supply of these examples; the point is that the rules are about meaning, not about silicon.

In practice, De Morgan's laws are how engineers move inversions around a circuit. If a chunk of a design has a NAND output but the next block expects an OR with one of its inputs negated, no work is needed: the two are the same circuit, just drawn differently. A schematic with bubbles on its inputs is often more readable than the algebraically equivalent one with bubbles on its outputs, and a fluent designer flips between them without thinking.

05. Universal Gates and Functional Completeness

We have already noted in passing that NAND and NOR are each functionally complete: any Boolean function can be built using only one or the other. This deserves a closer look, because it is the reason real silicon looks the way it does.

A set of operations is functionally complete, or universal, if every possible Boolean function can be expressed using only operations from that set. The set $\{\text{AND}, \text{OR}, \text{NOT}\}$ is obviously complete, since the canonical sum-of-products form uses exactly those three. The set $\{\text{AND}, \text{NOT}\}$ is also complete, because OR can be built from AND and NOT through De Morgan's laws: $A + B = \overline{\overline{A} \cdot \overline{B}}$. By the same trick, $\{\text{OR}, \text{NOT}\}$ is complete. Take away the NOT, however, and neither AND alone nor OR alone is universal — you cannot build an inverter from a circuit that only ever outputs 0 when given all-zero inputs.

The striking result is that a single two-input gate suffices, provided it is the right one. NAND alone is universal: NOT is a NAND with both inputs tied together, AND is two NANDs in series, and OR is built from three NANDs by De Morgan's law. NOR alone is universal by an identical argument. No other two-input gate has this property. AND and OR fail to produce inversions; XOR and XNOR can produce inversions but cannot independently produce the constants 0 and 1.

In CMOS — the silicon technology used for essentially all modern integrated circuits — NAND and NOR are also the cheapest two-input gates to fabricate, requiring four transistors apiece, while AND and OR each require six (a NAND or NOR followed by an inverter). Combined with their universality, this is why standard-cell libraries are dominated by NAND, NOR, and inverter cells, with the other gates derived. When a synthesis tool maps a design onto silicon, it typically rewrites everything into NAND/NOR/inverter form before optimizing.

A related notion is the multiplexer-only style. A 2-to-1 multiplexer with the right constant inputs can implement NOT, AND, OR, and any other two-input function, so multiplexers themselves are universal. Some FPGA architectures take this further and implement all combinational logic as small lookup tables, which are themselves multiplexers with programmable data inputs. The lesson is that universality does not pin down a unique implementation strategy; it just guarantees that whichever building block the technology happens to favour, it is enough.

06. XOR and Its Algebra

The seven gates introduced earlier put AND, OR, and NOT at the centre of the discussion, with XOR appearing almost as an afterthought. In practice, XOR has an outsized role in computer architecture, and its algebra deserves a section of its own.

The most useful identities are

$A \oplus 0 = A, \qquad A \oplus 1 = \overline{A}, \qquad A \oplus A = 0, \qquad A \oplus \overline{A} = 1.$

XOR is commutative and associative — a chain $A \oplus B \oplus C \oplus D$ has the same value regardless of how you parenthesize or reorder the operands — and it has its own distributive relationship with AND:

$A \cdot (B \oplus C) = (A \cdot B) \oplus (A \cdot C).$

The algebra of $\{\text{AND}, \text{XOR}, 0, 1\}$ is in fact the algebra of $GF(2)$, the two-element finite field, with AND playing the role of multiplication and XOR the role of addition. This is not a curiosity. Cyclic redundancy checks, Hamming codes, Reed–Solomon codes, AES encryption, and a great deal of the cryptographic and error-correction machinery introduced in the previous chapter all rely on $GF(2)$ arithmetic, with XOR as the only addition operation in sight.

Two concrete uses of XOR are worth pointing out now. Conditional inversion uses one XOR per bit to flip a value or pass it through, depending on a control signal: if $S$ is the control bit, then $A \oplus S$ is $A$ when $S = 0$ and $\overline{A}$ when $S = 1$. We will see this exact construction in Chapter 4 when a single adder is reused for both addition and subtraction. Parity, also covered in the previous chapter, is just the XOR of all the bits of a word: $p = b_0 \oplus b_1 \oplus \cdots \oplus b_{n-1}$ is 0 when an even number of bits are 1 and 1 when an odd number are. A tree of XOR gates computes this in $\log_2 n$ levels.

07. Shannon's Expansion and Cofactors

A powerful tool for reasoning about Boolean functions, and for breaking large ones into smaller pieces, is Shannon's expansion theorem (sometimes called the Boole expansion). Given any Boolean function $f(x_1, x_2, \ldots, x_n)$, the theorem says

$f(x_1, \ldots, x_n) = \overline{x_1} \cdot f(0, x_2, \ldots, x_n) + x_1 \cdot f(1, x_2, \ldots, x_n).$

In words: pick any variable, split the function into the case where the variable is 0 and the case where it is 1, and recombine them with a multiplexer driven by that variable. The two simpler functions $f(0, \ldots)$ and $f(1, \ldots)$ are called the cofactors of $f$ with respect to $x_1$.

This identity has three faces.

As a circuit-construction technique, it shows that any Boolean function can be implemented as a tree of 2-to-1 multiplexers driven by the input variables, with constants 0 and 1 at the leaves. This is essentially how FPGA lookup tables work: a $k$-input LUT is a $2^k$-to-1 multiplexer whose data inputs are programmable bits storing the truth-table column for $f$.

As an analytical tool, it lets a designer reason about a complicated function by considering the cases of one variable at a time. If both cofactors are equal, the function does not depend on that variable at all, and any logic that nominally uses it is wasted. If one cofactor is constant, the function reduces to a simpler form involving only the variable itself.

As the core of modern logic synthesis, recursive Shannon expansion underlies binary decision diagrams (BDDs), the canonical data structure that synthesis and verification tools use to represent Boolean functions internally. Two functions are equivalent if and only if their BDDs (under a fixed variable ordering and with appropriate reduction rules) are identical, which makes equivalence checking after optimization a routine, automated step.

08. Hazards and Glitches in Combinational Logic

Up to this point we have treated combinational circuits as if their outputs settled instantly when the inputs changed. They do not. Each gate has a small but real delay, and during the time it takes for the network to settle, the output can briefly take on the wrong value. These transient errors are called hazards or glitches.

A static-1 hazard occurs when an output should remain at 1 across an input transition but momentarily dips to 0. A static-0 hazard is the dual: the output should stay at 0 but momentarily rises to 1. Both are caused by the same underlying mechanism: two paths through the network with different delays. The output briefly disagrees with itself while the slower path catches up.

A classic small example is the function $f = AB + \overline{B}C$. Suppose $A = C = 1$ and $B$ transitions from 1 to 0. Algebraically, the function should remain at 1 throughout: with $B = 1$ the term $AB$ is 1; with $B = 0$ the term $\overline{B}C$ is 1. But during the transition, the input $B$ falls before $\overline{B}$ rises, because $\overline{B}$ is computed by an inverter and lags slightly. For an instant, both products are 0, and the output drops to 0 before recovering. The fix is to add a redundant consensus term $AC$, giving $f = AB + \overline{B}C + AC$. Algebraically the new term is implied by the others and changes nothing; physically it provides a third path that holds the output high during the transition.

Dynamic hazards, multiple unwanted transitions during a single input change, occur in more deeply nested logic and are harder to eliminate.

Hazards matter to two audiences. In asynchronous designs that read the combinational output directly, a glitch can be latched as a real value and corrupt the state; eliminating hazards is therefore a critical part of asynchronous design. In synchronous designs that read the output only at clock edges, glitches are usually invisible to the rest of the chip — they settle long before the next sampling instant — but they still consume power, since every spurious transition charges and discharges parasitic capacitance. Power-conscious designs sometimes restructure logic specifically to suppress glitches.

09. Active-High, Active-Low, and Logic Conventions

A Boolean variable in this chapter has been a pure mathematical object: 1 or 0, true or false. In real hardware, those values are voltages on wires, and which voltage represents which logical value is a convention that must be chosen and stated explicitly.

In positive logic, also called active-high, the higher voltage represents 1 and the lower voltage represents 0. In negative logic, also called active-low, the assignment is reversed. For ordinary signals on a chip, positive logic is the default, but plenty of important signals — reset, chip-select, output-enable, write-enable, interrupt request — are conventionally active-low, and a small bar over the signal name (or a trailing letter $n$ or $b$, as in $\overline{\text{RST}}$, $RST_n$, or $RST\_b$) marks them as such.

The choice is not just cosmetic. Active-low signals were historically preferred when the dominant logic family was TTL, whose outputs could sink current more strongly than they could source it, and whose default state on a disconnected wire pulled high. A reset that is asserted by pulling the wire low therefore cannot be falsely activated by a broken connection. Modern CMOS does not have this asymmetry, but the convention has stuck for compatibility and for the safety reasoning above.

On the same wire, an active-high reading and an active-low reading describe the same physical voltages with logically inverted meanings. De Morgan's laws turn out to be exactly the algebra of moving between these readings: a NAND gate read with active-high inputs and active-high outputs is, when its inputs and outputs are reinterpreted as active-low, an OR gate. The bubbles on a schematic, which we earlier called a notation for inversion, are equivalently a notation for change of convention.

Getting the convention wrong is one of the most common sources of bugs in board-level digital design. A signal that is active-low in a datasheet but driven from an active-high register in HDL will produce a chip that does the right thing exactly when the programmer expected it to do the wrong thing. A discipline of always stating, in a comment or a signal name, which polarity is intended is a small price to pay for avoiding a class of bugs that is otherwise extremely persistent.

10. Combinational Logic

A circuit is combinational if its outputs depend only on its current inputs, with no memory of the past. Given the same inputs, a combinational circuit produces the same outputs every time. The seven gates above are combinational, and so are any networks built from them, provided there are no loops in the wiring.

The design problem for a combinational circuit is straightforward in principle. Given a truth table or a Boolean expression, find a network of gates that realizes it, ideally with as few gates and as little delay as possible.

Consider, as a small worked example, a majority function: three inputs, output 1 if at least two of the inputs are 1.

Reading off the four 1-rows gives the canonical sum-of-products form

$M = \overline{A} B C + A \overline{B} C + A B \overline{C} + A B C.$

That has four three-input ANDs and a four-input OR, plus three inverters: at least eight gates. A little algebra simplifies it dramatically. Notice that the last term $ABC$ can be combined with each of the others using the identity $X + XY = X$ on shared pairs:

$M = AB(\overline{C} + C) + AC(\overline{B} + B) + BC(\overline{A} + A) = AB + AC + BC.$

Now we have three two-input ANDs and a three-input OR — five gates instead of eight, and only two levels of logic from input to output instead of three. Combinational design is, to a large extent, the discipline of producing such simplifications systematically.

The number of levels through which a signal must pass on its way from input to output is called the logic depth of the circuit, and it directly determines how fast the circuit can run. Each gate adds a small but unavoidable propagation delay, perhaps a few tens of picoseconds in modern silicon. A circuit ten gates deep can settle in under a nanosecond; a circuit a hundred gates deep cannot. Much of high-performance digital design consists of trading off depth against width — using more gates in parallel to reduce the number of stages a signal has to pass through.

11. Sequential Logic

Combinational logic alone is not enough to build a computer, because a computer must remember things. The current value of a register is determined not just by the wires presently feeding it, but by what was loaded into it at some past instant. Circuits whose outputs depend on past inputs as well as present ones are called sequential.

The minimum ingredient required to add memory to a circuit is a feedback loop: a wire from the output of a gate back to one of its inputs. Once such a loop exists, the circuit can settle into more than one stable state, and its current state encodes information about what happened earlier.

The simplest example is the SR latch, built from two cross-coupled NOR gates:

Figure: SR latch built from two cross-coupled NOR gates, with S and R inputs on the left and complementary Q and Q-bar outputs on the right

When $S$ (set) is briefly raised, the latch flips to $Q = 1$ and stays there even after $S$ returns to 0. When $R$ (reset) is briefly raised, the latch flips back to $Q = 0$. With both inputs at 0, the latch holds whatever state it was last set to. The combination $S = R = 1$ is forbidden because it produces an inconsistent state. This circuit, with two gates and two wires, is the kernel of every register, every cache cell, and every flip-flop in a modern processor.

Real designs almost never use bare latches. They use flip-flops, which capture their input only on the rising or falling edge of a clock signal and ignore it the rest of the time. A flip-flop and the rules surrounding its use turn the messy world of feedback loops into something an engineer can reason about cleanly. We will give flip-flops their own treatment in Chapter 4 alongside registers and counters, and Chapter 5 will explain the discipline of synchronous design that organizes an entire chip around them. For now the point is only that adding a single feedback loop crosses the line from combinational to sequential, and that this line is what separates circuits that compute from circuits that remember.

12. Boolean Simplification

A correct circuit is not enough; circuits must also be small and fast. Boolean simplification is the process of finding the minimal expression for a given Boolean function. There are three techniques worth knowing in detail: algebraic manipulation, Karnaugh maps, and the Quine–McCluskey method.

Algebraic manipulation

The most flexible approach, and the only one that scales to large designs, is to apply the identities of Boolean algebra directly. The example with the majority function above used this technique: starting from a sum of minterms, we factored, used the inverse law $\overline{X} + X = 1$, and used the identity law $1 \cdot Y = Y$ to collapse the expression. With practice, a small set of moves does most of the work:

• Combine two terms that differ in exactly one variable: $XY + X\overline{Y} = X$.
• Absorb a term contained in another: $X + XY = X$.
• Apply De Morgan's laws to push inversions inward or outward.
• Factor common subexpressions.

The downside of pure algebraic manipulation is that it is easy to miss simplifications; there is no guarantee that you have reached the minimum.

Karnaugh maps

For functions of up to four or five variables, Karnaugh maps give a graphical procedure that finds the minimum almost mechanically. A Karnaugh map (or K-map) is a truth table redrawn as a two-dimensional grid in which the rows and columns are labeled in Gray code order — that is, adjacent rows and columns differ in exactly one bit. The trick that makes K-maps work is that adjacent cells differ by a single variable, so a pair of adjacent 1-cells corresponds to a term where that variable can be eliminated.

For the three-input majority function, the K-map is:

Figure: Karnaugh map for the three-input majority function with A on the rows and BC on the columns in Gray-code order, showing the four 1-cells

The four 1-cells form three overlapping pairs, each of which corresponds to one of the simplified terms:

• The two cells with $B = 1, C = 1$ give $BC$.
• The two cells with $A = 1, C = 1$ give $AC$.
• The two cells with $A = 1, B = 1$ give $AB$.

ORing them gives $M = AB + AC + BC$, which agrees with the algebraic derivation. Note also that the Karnaugh map's columns wrap around — 10 is adjacent to 00 — because the encoding is cyclic. Beginners often miss simplifications by failing to notice this wraparound.

K-maps stop being practical beyond about five variables, because the human eye loses the ability to spot adjacencies in higher dimensions.

Quine–McCluskey

For larger functions, the Quine–McCluskey method provides an algorithmic procedure that is guaranteed to find a minimum sum-of-products form. It works in two phases. First, it tabulates all the minterms and repeatedly combines pairs that differ in a single variable, producing larger and larger prime implicants. Second, it solves a covering problem to choose a minimal subset of those prime implicants that together cover every 1-row of the truth table. The method is tedious by hand but straightforward to program, and modern logic synthesis tools use sophisticated descendants of it.

For the majority function the procedure produces the same three terms $AB$, $AC$, $BC$ that the K-map gave us. For functions with dozens of variables, the algorithm is essential; no human can spot the patterns reliably.

Don't-cares

In real designs, some input combinations cannot occur — perhaps the rest of the system guarantees they will never happen — and the output for those rows of the truth table is irrelevant. These rows are marked with an X and are called don't-cares. The simplifier is free to assign them whichever value produces the smaller circuit. A designer who knows where the don't-cares are can often shrink a function dramatically, and a designer who fails to declare them ends up with hardware that wastes silicon producing values nobody will ever read.

13. Summary

Boolean algebra is the mathematics of values that are 1 or 0 and the operations AND, OR, and NOT. Its identities — commutativity, distributivity, and especially De Morgan's laws — let us manipulate logical expressions the way we manipulate ordinary algebra, with the added beauty of duality. Truth tables specify Boolean functions completely and let us reduce any function to a canonical sum-of-products or product-of-sums form. Logic gates are the physical circuits that implement these operations, with NAND and NOR each capable of building anything on their own — a fact that, together with their cheapness in CMOS, dictates the cell library of every real chip. XOR has its own rich algebra, the algebra of $GF(2)$, which underlies parity, error correction, and cryptography. Shannon's expansion theorem turns any Boolean function into a tree of multiplexers and is the basis of both FPGA lookup tables and the binary decision diagrams used by modern synthesis tools. Networks of gates without feedback are combinational: their outputs are pure functions of their inputs, but in the real world they pass through transient hazards as those functions settle. Add a feedback loop and the circuit becomes sequential, capable of remembering past inputs. Engineers reading and drawing schematics also have to keep in mind the active-high or active-low convention attached to every signal, since the same wire can encode either sense. Simplification, whether by algebraic manipulation, by Karnaugh maps, or by the Quine–McCluskey procedure, is the discipline that turns correct circuits into small and fast ones.

These are the bricks. In Chapter 4 we begin laying them into the larger structures — adders, multiplexers, decoders, registers — that the rest of computer architecture takes for granted.