3. Boolean Algebra and Logic Operations

We can now represent numbers in binary. But we need to operate on those numbers, combining them, transforming them, deciding things based on them. That is the job of Boolean algebra, named after the British mathematician George Boole, who introduced it in 1854 as a way of doing logic with algebraic notation. He had no idea he was inventing the foundation of every digital chip on the planet, because he had never seen a chip; transistors were 90 years away. He just thought logic should be more rigorous.

3.1 The fundamental operations

Three primitives form the basis of all digital logic:

NOT (also written ¬, !, ~, $\bar{A}$). Inverts a single bit. NOT 0 = 1, NOT 1 = 0. The simplest possible operation.

AND (also written ∧, ·, &). The output is 1 only when both inputs are 1.

OR (also written ∨, +, |). The output is 0 only when both inputs are 0; equivalently, 1 if at least one input is 1.

Real-world analogy. AND is the security guard. "The door is locked AND the alarm is armed → safe." Both have to be true. OR is the relaxed manager. "The user is admin OR the user owns this file → can edit." Either is enough. NOT is negation. "NOT logged in → redirect to login." Every &&, ||, and ! you have ever typed in a programming language is exactly this.

These operations also have electrical implementations in CMOS. An AND gate is two NMOS transistors in series (both must conduct for the output to pull low) followed by an inverter. An OR gate is two NMOS transistors in parallel followed by an inverter. NOT is a single CMOS inverter (one PMOS and one NMOS, the standard CMOS inverter you saw in Chapter 1). In real silicon, gate counts are physical, layout-area, propagation-delay realities, not abstractions.

3.2 Derived operations

From the three primitives we get a useful family of derived operations:

NAND (NOT AND). Output is 0 only when both inputs are 1. The complement of AND.

NOR (NOT OR). Output is 1 only when both inputs are 0.

XOR (exclusive OR, also written ⊕). Output is 1 when inputs differ.

XNOR (NOT XOR). Output is 1 when inputs are equal. Read as "A equals B."

XOR is special. It is the heart of binary addition (the sum bit of a half-adder), the heart of parity and CRC, and the heart of every stream cipher (encryption is plaintext XOR keystream; decryption is ciphertext XOR the same keystream). The XOR of two equal inputs is 0; the XOR of any input with 0 is itself; and XOR is its own inverse. These three properties make it astonishingly useful in symmetric cryptography.

3.3 Universal gates: a beautiful punchline

Here is a fact that should feel surprising at first: every Boolean function whatsoever can be implemented using only NAND gates. The same is true of NOR alone. They are called universal gates.

The verification is short:

• NOT $A$ = $A$ NAND $A$ (feed the same input to both inputs of a NAND).
• $A$ AND $B$ = NAND(NAND($A$, $B$)). The first NAND gives $\overline{AB}$; the second inverts it.
• $A$ OR $B$ = NAND(NOT $A$, NOT $B$) = NAND(NAND($A,A$), NAND($B,B$)). By De Morgan: $\overline{\bar{A} \bar{B}} = A + B$.

Why does this matter beyond a parlor trick? Because in real CMOS silicon, NAND and NOR are the cheapest gates to build. A two-input NAND uses 4 transistors; an AND uses 6 (a NAND followed by an inverter). NOR is similarly 4 transistors. Real chips use mostly NAND and NOR, with the synthesis tool gleefully transforming "A AND B" in your HDL into a NAND followed by an inverter, or further re-encoding the surrounding logic so the inverter cancels with the next gate.

A whole chip's worth of logic, all the AND/OR/XOR you ever wrote, is silently rebuilt from 4-transistor NAND blocks during synthesis. Understanding this is what lets you read a netlist after synthesis and not panic.

3.4 The fundamental laws

Boolean algebra obeys a set of identities. The ones you actually use:

• Identity: $A + 0 = A$, $A \cdot 1 = A$.
• Null: $A + 1 = 1$, $A \cdot 0 = 0$.
• Idempotent: $A + A = A$, $A \cdot A = A$.
• Complement: $A + \bar{A} = 1$, $A \cdot \bar{A} = 0$.
• Involution: $\overline{\bar{A}} = A$ (double negation).
• Commutative: $A + B = B + A$, $A \cdot B = B \cdot A$.
• Associative: $(A + B) + C = A + (B + C)$, $(A \cdot B) \cdot C = A \cdot (B \cdot C)$.
• Distributive: $A(B + C) = AB + AC$, and the dual $A + BC = (A+B)(A+C)$.
• Absorption: $A + AB = A$, $A(A + B) = A$.
• De Morgan's: $\overline{A + B} = \bar{A} \cdot \bar{B}$, $\overline{A \cdot B} = \bar{A} + \bar{B}$.
• Consensus: $AB + \bar{A}C + BC = AB + \bar{A}C$. The $BC$ term is redundant.

3.5 Duality and De Morgan in practice

Notice that every law above comes in pairs. If you take a law, swap every AND with OR, and swap every 0 with 1, you get another valid law. This principle of duality is built into Boolean algebra and is no coincidence: AND and OR are structurally symmetric, mirror images in a logical sense. The duality is why NAND and NOR are both universal, why SOP and POS are both canonical forms (next section), and why so much of digital design has a "flip everything" symmetry.

De Morgan's laws are the workhorses. They convert AND to OR (and vice versa) by complementing the inputs and the output. Symbolically:

$\overline{A \cdot B} = \bar{A} + \bar{B}, \qquad \overline{A + B} = \bar{A} \cdot \bar{B}.$

A practical consequence: an AND-OR expression can always be rewritten as NAND-NAND, and an OR-AND expression as NOR-NOR. These are the gate-level transformations the synthesis tool applies when "your" AND-OR logic comes out of the fab as a forest of NANDs. If you stare at a synthesized netlist and wonder where all the NANDs came from, De Morgan is your answer.

3.6 Algebraic simplification

Apply the laws repeatedly until you cannot simplify further. Example: simplify $f = ABC + AB\bar{C} + A\bar{B}C$.

Factor $C$ and $\bar C$ inside the first two terms: $f = AB(C + \bar{C}) + A\bar{B}C = AB \cdot 1 + A\bar{B}C = AB + A\bar{B}C$. Factor $A$: $f = A(B + \bar{B}C)$. Now $B + \bar{B}C = B + C$ (a useful identity, derivable from the consensus theorem, or by noting $B + \bar{B}C = B(1+C) + \bar B C = B + BC + \bar B C = B + C(B + \bar B) = B + C$). So $f = A(B + C)$.

The original needed three 3-input AND gates and a 3-input OR. The simplified version needs one OR and one AND. Smaller, faster, less power.

Algebraic simplification is exact but unstructured. For larger functions it is laborious and easy to get wrong. Two visual or algorithmic methods scale better.