Skip to content
LumenaryAcademy
Digital 60 min

Logic gates and Boolean algebra

Why engineers squeeze a voltage into two values, the algebra those values obey, and the transistors that compute it.

Code tested · 7AI-draftedAwaiting review by an electrical engineer

Your guides: Chloe · The Physicist, Margaret · The Bench Engineer, Gideon · The Design Reviewer

MotivationH

Why squeeze a voltage into two values?

A wire can carry any voltage between 0 V and its supply. An audio cable uses that freedom: every millivolt means something. Digital electronics throws almost all of it away and keeps two meanings, low and high, 0 and 1. That looks wasteful. It is the single most important decision in electronics, and this lesson starts by seeing why.

Every real signal picks up noise: a neighbouring wire couples a few tens of millivolts in, the ground under one chip sits a little above the ground under another, a supply droops when a thousand gates switch at once. An analog signal that passes through a hundred amplifiers collects a hundred doses of that noise, and nothing can tell the noise from the signal afterwards. A digital signal that passes through a hundred gates arrives as clean as it started, because each gate decides "low or high?" and drives a fresh, full-strength low or high to the next one. A copy of a copy of a digital file is perfect; a photocopy of a photocopy is not.

That restoring property is what lets a chip chain billions of transistors and still get the right answer. This lesson starts from the CMOS inverter of Transistors and covers why it restores, the algebra gates compute, NAND and NOR at transistor level, the voltage levels of real chips, and Verilog, the language the rest of this level uses. Lumenary CS's From logic gates to a processor climbs the same tower quickly, from a programmer's side; here we stay on the hardware.

DefinitionsH

Logic levels and noise margins

A gate's output is never exactly 0 V or exactly the supply, and a gate's input must make a decision even when the voltage it sees is somewhere in between. So a logic family specifies four numbers.

Definition— Logic levels

For a given family and supply:

  • VOHV_{OH} is the lowest voltage a driving output is guaranteed to produce for a 1, and VOLV_{OL} the highest it produces for a 0 (each at a stated load current);
  • VIHV_{IH} is the lowest input voltage a receiver is guaranteed to read as 1, and VILV_{IL} the highest it is guaranteed to read as 0.

Inputs between VILV_{IL} and VIHV_{IH} are forbidden: the receiver may read them either way, or not cleanly at all.

Definition— Noise margins

The high noise margin NMH=VOH−VIHNM_H = V_{OH} - V_{IH} and the low noise margin NML=VIL−VOLNM_L = V_{IL} - V_{OL} are how much noise can be added to a valid output, in the worst direction, before a receiver might misread it.

driver outputreceiver inputvalid 1valid 0read as 1forbiddenread as 0NMH = 0.4 VNML = 0.4 V3.3 VVOH 2.4 VVOL 0.4 V0 VVIH 2.0 VVIL 0.8 V
Logic levels for a typical 3.3 V interface (the LVTTL-compatible levels many 3.3 V parts use). A valid output 1 is at least 2.4 V; an input of at least 2.0 V is read as 1. The 0.4 V gaps on each side are the noise margins.

Example— Margins at 3.3 V and at 1.8 V

Many 3.3 V parts guarantee VOH≥2.4V_{OH} \ge 2.4 V and VOL≤0.4V_{OL} \le 0.4 V at a few milliamps of load, and read VIH=2.0V_{IH} = 2.0 V and VIL=0.8V_{IL} = 0.8 V. Then NMH=2.4−2.0=0.4NM_H = 2.4 - 2.0 = 0.4 V and NML=0.8−0.4=0.4NM_L = 0.8 - 0.4 = 0.4 V. With a light load, CMOS outputs swing much closer to the rails (within about 0.2 V), and the margins grow to 0.6 V low and 1.1 V high.

The usual 1.8 V CMOS levels scale with the supply: VIH=0.65×1.8=1.17V_{IH} = 0.65 \times 1.8 = 1.17 V, VIL=0.35×1.8=0.63V_{IL} = 0.35 \times 1.8 = 0.63 V, and outputs within 0.45 V of the rails, so VOH=1.35V_{OH} = 1.35 V and VOL=0.45V_{OL} = 0.45 V. Both margins are 0.180.18 V. Cutting the supply from 3.3 V to 1.8 V has cut the margins by more than half, which is one reason low-voltage boards need careful layout and why fast low-voltage links switch to differential signalling. These figures follow the JEDEC interface standards; a real design takes them from each part's datasheet, at the load current it will actually see.

Where do the forbidden band and the margins come from physically? From the inverter's voltage transfer characteristic, the curve of output voltage against input voltage. Near the rails it is almost flat: a change at the input barely moves the output. In the middle it is steep: the gain is large. The natural place to put VILV_{IL} and VIHV_{IH} is where the slope is exactly −1-1, because outside those points the gate shrinks any disturbance and between them it amplifies it.

The code below models an inverter's curve with a smooth function (a real one comes from the transistor equations or a SPICE simulation, but the shape is what matters), finds the unity-gain points, and then sends a 1 through eight stages with 0.2 V of noise pushing the signal towards the middle before every stage. It compares the CMOS inverter with a linear inverting stage, one that simply outputs VDD−VinV_{DD} - V_{\text{in}} with gain −1-1.

python
import numpy as np

VDD = 1.8          # supply voltage, volts
GAIN = 8.0         # magnitude of the inverter's slope at its switching point

def inverter(v_in):
    """A smooth model of a CMOS inverter's voltage transfer characteristic."""
    k = 2 * GAIN / VDD
    return VDD / 2 * (1 - np.tanh(k * (v_in - VDD / 2)))

# The two inputs where the slope is exactly -1 define V_IL and V_IH.
v = np.linspace(0, VDD, 180001)
slope = np.gradient(inverter(v), v)
crossings = v[np.where(np.diff(np.sign(slope + 1)) != 0)[0]]
V_IL, V_IH = crossings[0], crossings[-1]
V_OH, V_OL = inverter(V_IL), inverter(V_IH)
print(f"V_IL = {V_IL:.3f} V  V_IH = {V_IH:.3f} V  V_OH = {V_OH:.3f} V  V_OL = {V_OL:.3f} V")
print(f"noise margins: NM_L = {V_IL - V_OL:.3f} V, NM_H = {V_OH - V_IH:.3f} V\n")

# Send a 1 through eight stages. Between stages, 0.2 V of noise pushes the signal
# towards the middle, the worst direction. Compare a linear inverting stage
# (out = VDD - in, gain -1) with the regenerating CMOS inverter.
analog = digital = VDD
ideal = 1
print("stage | linear stage   bit | CMOS inverter   bit")
for stage in range(1, 9):
    analog, digital, ideal = VDD - analog, float(inverter(digital)), 1 - ideal
    push = -0.2 if ideal == 1 else 0.2
    analog, digital = analog + push, digital + push
    a_bit, d_bit = int(analog > VDD / 2), int(digital > VDD / 2)
    flag = "  <- wrong" if a_bit != ideal else ""
    print(f"{stage:5} | {analog:8.3f} V  {a_bit:5} | {digital:9.3f} V  {d_bit:5}{flag}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The linear chain keeps every dose of noise: its error grows by 0.2 V per stage and the bit is wrong from the fifth stage on. The inverter chain sits at 0.2 V or 1.6 V forever, because each stage receives a signal 0.2 V off the rail, well outside its unity-gain points, and restores it to within a few millivolts before the next dose arrives.

DefinitionsH

Boolean algebra

Once signals are two-valued, a circuit without memory computes a Boolean function: each output is 0 or 1 for every combination of inputs. Engineers write AND as a product, A⋅BA \cdot B or just ABAB; OR as a sum, A+BA + B; and NOT with a bar, A‾\overline{A} (or A′A' when typing). Logicians write the same operations ∧\land, ∨\lor and ¬\lnot; the CS lesson used those. AND binds more tightly than OR, so AB+CAB + C means (AB)+C(AB) + C.

NameForm with +Dual form with ·
IdentityA+0=AA + 0 = AA⋅1=AA \cdot 1 = A
Null (annihilation)A+1=1A + 1 = 1A⋅0=0A \cdot 0 = 0
IdempotenceA+A=AA + A = AA⋅A=AA \cdot A = A
ComplementA+A‾=1A + \overline{A} = 1A⋅A‾=0A \cdot \overline{A} = 0
Commutativity, associativityA+B=B+AA + B = B + A, (A+B)+C=A+(B+C)(A + B) + C = A + (B + C)the same with ·
DistributivityA(B+C)=AB+ACA(B + C) = AB + ACA+BC=(A+B)(A+C)A + BC = (A + B)(A + C)
AbsorptionA+AB=AA + AB = AA(A+B)=AA(A + B) = A
De MorganA+B‾=A‾ B‾\overline{A + B} = \overline{A}\,\overline{B}AB‾=A‾+B‾\overline{AB} = \overline{A} + \overline{B}
ConsensusAB+A‾C+BC=AB+A‾CAB + \overline{A}C + BC = AB + \overline{A}C(A+B)(A‾+C)(B+C)=(A+B)(A‾+C)(A + B)(\overline{A} + C)(B + C) = (A + B)(\overline{A} + C)
InvolutionA‾‾=A\overline{\overline{A}} = A

Two entries surprise people used to ordinary algebra. The second distributive law, A+BC=(A+B)(A+C)A + BC = (A + B)(A + C), has no counterpart for numbers. And there is no cancellation: A+B=A+CA + B = A + C does not imply B=CB = C (try A=1A = 1).

The table has a symmetry worth naming. Duality: swap ++ with ⋅\cdot and 0 with 1 throughout a true identity (leaving variables and bars alone), and the result is also a true identity. Every row's two columns are duals of each other, so each law needs proving only once.

Theorem— De Morgan's laws for n variables

For any n≥1n \ge 1, A1+A2+⋯+An‾=A1‾ A2‾⋯An‾\overline{A_1 + A_2 + \cdots + A_n} = \overline{A_1}\,\overline{A_2}\cdots\overline{A_n} and A1A2⋯An‾=A1‾+A2‾+⋯+An‾\overline{A_1 A_2 \cdots A_n} = \overline{A_1} + \overline{A_2} + \cdots + \overline{A_n}.

Proof

The left side of the first law is 1 exactly when A1+⋯+An=0A_1 + \cdots + A_n = 0, that is, when every AiA_i is 0. The right side is 1 exactly when every Ai‾\overline{A_i} is 1, that is, again, when every AiA_i is 0. The two sides are 1 on the same input combinations, so they are the same function. The second law is the dual of the first. (Checking that two expressions agree on every input is called perfect induction; it is a complete proof because a Boolean function is nothing more than its values.)

∎

Theorem— Shannon expansion

For any Boolean function ff and any one of its inputs AA: f=A⋅f∣A=1+A‾⋅f∣A=0f = A \cdot f|_{A=1} + \overline{A} \cdot f|_{A=0}, where f∣A=1f|_{A=1} is ff with AA fixed at 1.

Proof

If A=1A = 1 the right side is 1⋅f∣A=1+0=f∣A=11 \cdot f|_{A=1} + 0 = f|_{A=1}, which is ff at that input. If A=0A = 0 it is 0+1⋅f∣A=0=f∣A=00 + 1 \cdot f|_{A=0} = f|_{A=0}. Both cases agree with ff.

∎

Shannon expansion says that any function is a multiplexer choosing between two simpler functions, selected by one input. Apply it to every input in turn and you have a binary decision tree; share identical subtrees and you have a binary decision diagram, the data structure behind many equivalence checkers used in chip design. It is also exactly how an FPGA's look-up tables compute, as Verilog and FPGAs will show.

Example— Simplifying with the laws

A door alarm sounds when the door is open (DD) and the system is armed (RR), or when the system is armed and a window sensor (WW) trips while the door is open, or when the door is open and a tamper switch (TT) is set and the system is armed. As written: F=DR+RWD+DTRF = DR + RWD + DTR. Factor out DRDR by distributivity: F=DR(1+W+T)F = DR(1 + W + T). By the null law 1+W+T=11 + W + T = 1, so F=DRF = DR. The window and tamper inputs were redundant in this specification, which an engineer should report back, because the person who wrote it probably meant something else.

A second, subtler one: F=AB+A‾C+BCF = AB + \overline{A}C + BC. The term BCBC is covered already: if B=C=1B = C = 1, then whichever value AA has, one of ABAB or A‾C\overline{A}C is 1. That is the consensus theorem, and F=AB+A‾CF = AB + \overline{A}C. Keep this example in mind: in Combinational logic you will see that the "redundant" BCBC is sometimes put back on purpose.

A truth table is easy to generate by machine, and perfect induction is a loop. The program below prints the truth table of a three-input majority voter (the circuit that outvotes one faulty copy in a triple-redundant system) and then checks several of the laws above, plus one plausible-looking false "law", on all eight input rows.

python
from itertools import product

def truth_table(f, names):
    """Print the truth table of f, one row per input combination, in binary counting order."""
    print(" ".join(names), "| f")
    for values in product((0, 1), repeat=len(names)):
        print(" ".join(str(v) for v in values), "|", f(*values))

def counterexample(f, g, n):
    """Perfect induction: try all 2**n rows. Return the first row where f and g differ, or None."""
    for values in product((0, 1), repeat=n):
        if f(*values) != g(*values):
            return values
    return None

NOT = lambda a: 1 - a

# A majority voter: the output is 1 when at least two of the three inputs are 1.
majority = lambda a, b, c: (a & b) | (a & c) | (b & c)
truth_table(majority, ["a", "b", "c"])

claims = {
    "De Morgan:    ~(a b) = ~a + ~b": (lambda a, b, c: NOT(a & b), lambda a, b, c: NOT(a) | NOT(b)),
    "De Morgan:    ~(a + b) = ~a ~b": (lambda a, b, c: NOT(a | b), lambda a, b, c: NOT(a) & NOT(b)),
    "absorption:   a + a b = a": (lambda a, b, c: a | (a & b), lambda a, b, c: a),
    "distributive: a + b c = (a + b)(a + c)": (lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & (a | c)),
    "consensus:    a b + ~a c + b c = a b + ~a c": (lambda a, b, c: (a & b) | (NOT(a) & c) | (b & c),
                                                   lambda a, b, c: (a & b) | (NOT(a) & c)),
    "Shannon:      f = a f(1,b,c) + ~a f(0,b,c)": (majority,
                                                  lambda a, b, c: (a & majority(1, b, c)) | (NOT(a) & majority(0, b, c))),
    "(a guess)     a + b c = (a + b) c": (lambda a, b, c: a | (b & c), lambda a, b, c: (a | b) & c),
}
print()
for name, (f, g) in claims.items():
    bad = counterexample(f, g, 3)
    print(f"{name:46} {'holds' if bad is None else 'fails at a, b, c = ' + str(bad)}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Perfect induction costs 2n2^n evaluations, which is nothing for three inputs and impossible for the 64-bit adder of a processor (21282^{128} rows). Industrial equivalence checkers therefore reason symbolically, with decision diagrams and SAT solvers, rather than enumerating.

ComputationC

Sixteen gates, and the two that can build everything

With two inputs there are four rows in a truth table and so 24=162^4 = 16 possible functions. Six of them have their own gate symbols, shown below; the others are constants, single inputs, or forms of implication.

NOTANDORNANDNORXOR
The standard (distinctive-shape) gate symbols. A small circle, or bubble, on a terminal means inversion: NAND is AND followed by NOT. XOR outputs 1 when its inputs differ.

A set of gates is functionally complete (or universal) if circuits built from it alone can compute every Boolean function. AND, OR and NOT together are complete, because any truth table can be written as an OR of AND terms, one per row where the output is 1; the CS lesson proved that, and that NAND alone is complete. Here we ask a sharper question: which of the sixteen two-input gates are complete on their own?

A program can answer it. Represent each function of aa and bb by its 4-bit truth table. Start with the two functions every circuit has for free, aa and bb themselves. Feed every pair of functions found so far into the gate, add any new results, and repeat until nothing new appears. The gate is universal exactly when all 16 functions turn up, because a circuit that can make every two-input function can make NOT and AND, and from those everything.

python
# Each two-input function is a 4-bit truth table: bit i is f(a, b) where i = 2a + b.
# So a = 0b1100 and b = 0b1010 are the "columns" of the inputs themselves.
A, B = 0b1100, 0b1010
NAMES = {0b0000: "0 (constant)", 0b0001: "NOR", 0b0010: "b and not a", 0b0011: "not a",
         0b0100: "a and not b", 0b0101: "not b", 0b0110: "XOR", 0b0111: "NAND",
         0b1000: "AND", 0b1001: "XNOR", 0b1010: "b", 0b1011: "a implies b",
         0b1100: "a", 0b1101: "b implies a", 0b1110: "OR", 0b1111: "1 (constant)"}

def apply(table, x, y):
    """Feed the functions x and y (as truth tables) into the gate with the given truth table."""
    out = 0
    for i in range(4):
        xi, yi = (x >> i) & 1, (y >> i) & 1
        out |= ((table >> (2 * xi + yi)) & 1) << i
    return out

def reachable(table):
    """Every function of a and b that circuits made only of this gate can compute."""
    found = {A, B}
    while True:
        new = {apply(table, x, y) for x in found for y in found} - found
        if not new:
            return found
        found |= new

print("gate           functions of a, b it can build   universal?")
for table in range(16):
    n = len(reachable(table))
    print(f"{NAMES[table]:14} {n:>16}                     {'YES' if n == 16 else ''}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Only NAND and NOR reach all sixteen. XOR is stuck at four (aa, bb, a⊕ba \oplus b and 0), because XOR of XORs is always a linear function modulo 2 and can never make AND. AND and OR are stuck at three, because they are monotone: raising an input never lowers the output, so they can never make NOT. Emil Post classified all of this in 1941: a set of gates is complete exactly when, for each of five properties (preserving 0, preserving 1, being monotone, being linear, being self-dual), it contains at least one gate without that property. NAND and NOR are the only two-input gates that fail all five at once.

Worked examplesH

CMOS gates at transistor level

In Transistors you built the CMOS inverter from one PMOS and one NMOS transistor. Every static CMOS gate follows the same plan, with two networks of switches:

  • a pull-down network of NMOS transistors between the output and ground, which conducts when the output should be 0;
  • a pull-up network of PMOS transistors between the supply VDDV_{DD} and the output, which conducts when the output should be 1.

The two networks are complementary: for every input combination exactly one of them conducts. So the output is always driven firmly to one rail, and in steady state there is no path from supply to ground, which is why a CMOS gate that is not switching draws almost no current. Complementary networks are built as duals: transistors in series in one network appear in parallel in the other.

An NMOS transistor conducts when its gate is high. Two in series conduct only when both inputs are high, which pulls the output low exactly when A=B=1A = B = 1: that is NAND. The pull-up network must then conduct whenever either input is low, so it has two PMOS transistors (which conduct when their gate is low) in parallel.

VDDABABYGNDpull-up:PMOS in parallelpull-down:NMOS in series
A static CMOS two-input NAND gate. The two PMOS transistors (bubbles on their gates) are in parallel between VDD and the output, so either low input pulls Y high. The two NMOS transistors are in series between Y and ground, so Y is pulled low only when A and B are both high. Swapping series and parallel gives a NOR gate.

The NOR gate is the dual: two NMOS in parallel (either high input pulls the output low) and two PMOS in series (the output goes high only when both inputs are low). Both gates use four transistors.

Notice what a single CMOS stage cannot do. Raising an input can only turn an NMOS on and a PMOS off, which can only pull the output down. So every single-stage static CMOS gate is inverting: NOT, NAND, NOR, and compound gates such as the AND-OR-INVERT gate AB+C‾\overline{AB + C} (six transistors: NMOS AA and BB in series, in parallel with CC; the PMOS network is the dual). An AND gate is a NAND followed by an inverter, six transistors and two stages. That is why cell libraries are full of NAND, NOR, AOI and OAI cells, and why logic synthesis thinks in inverting gates.

Example— Why designers prefer NAND to NOR

Holes in a PMOS channel are less mobile than electrons in an NMOS channel, so a PMOS needs roughly twice the width to pass the same current. Take as reference an inverter with NMOS width 1 and PMOS width 2; it pulls up and down equally hard.

To make a gate as strong as that inverter in its worst case, transistors in series must be widened: two in series behave like one of double length, so each needs double width. In a NAND2 the series NMOS get width 2 each and the parallel PMOS keep width 2 (in the worst case only one is on). In a NOR2 the parallel NMOS keep width 1 and the series PMOS need width 4 each.

The capacitance an input presents is proportional to the transistor width it drives. Each NAND2 input drives 2+2=42 + 2 = 4 units, each NOR2 input 1+4=51 + 4 = 5, against the inverter's 3. The ratio, 4/34/3 for NAND2 and 5/35/3 for NOR2, is the gate's logical effort: how much worse than an inverter it is at driving a load for the same input capacitance. The gap widens with more inputs, because NOR stacks the slow PMOS.

python
# Size each gate so its worst-case pull-down and pull-up are as strong as a reference
# inverter's (NMOS width 1, PMOS width 2: a PMOS needs about twice the width for the
# same current). Transistors in series must be wider: n in series need width n each.
MOBILITY_RATIO = 2

def nand_sizes(n):
    return n, MOBILITY_RATIO          # NMOS in series, PMOS in parallel

def nor_sizes(n):
    return 1, MOBILITY_RATIO * n      # NMOS in parallel, PMOS in series

inverter_input = 1 + MOBILITY_RATIO
print("gate   transistors  width per input  total width  logical effort")
for n in (2, 3, 4):
    for name, sizes in (("NAND", nand_sizes), ("NOR", nor_sizes)):
        wn, wp = sizes(n)
        per_input = wn + wp           # each input drives one NMOS gate and one PMOS gate
        print(f"{name}{n:<3} {2 * n:>8}  {per_input:>13}  {n * per_input:>13}  {per_input / inverter_input:>11.2f}")

# Energy drawn from the supply each time a node is charged: C * V**2.
C = 10e-15   # a 10 fF node: a gate input plus a short wire
for V in (5.0, 3.3, 1.8, 0.75):
    print(f"V = {V:4} V: {C * V**2 * 1e15:6.1f} fJ per charge, {(V / 0.75)**2:5.1f} times the 0.75 V figure")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

A NOR4's logical effort is 3 against a NAND4's 2, which is why synthesis tools lean on NANDs, and why gates rarely stack more than four transistors in series.

The last four lines are the reason supplies keep falling. Charging a node of capacitance CC to VV draws energy CV2CV^2 from the supply (half is lost in the pull-up as it charges, the other half in the pull-down when it later discharges). A chip's dynamic power is therefore about αCV2f\alpha C V^2 f, where ff is the clock frequency and α\alpha the fraction of nodes that switch per cycle. Logic that ran at 5 V in the 1980s now runs at under 1 V on a leading-edge chip, and the same switching event costs over forty times less energy.

ExplanationH

Logic families and voltage levels

A logic family is a set of chips built the same way, so that any output can drive any input of the same family. The families tell the history of the field:

FamilyEraSupplyNotes
RTL, DTLearly 1960svariousresistor- and diode-transistor logic; used in early integrated computers
TTL (the 7400 series)from the mid-1960s5 Vbipolar transistors; the standard glue logic of the 1970s and 1980s
ECL1960s to 1990snegative supplybipolar, never saturated: very fast, very power-hungry; used in mainframes and supercomputers
CMOS 4000 seriesfrom 19683–15 Vlow power, slow; first mass CMOS logic
74HC, 74ACfrom the 1980s2–6 VCMOS at TTL speeds; the HCT variants accept TTL input levels
74LVC, 74AUC and similarfrom the 1990s1.65–3.6 V and lowerlow-voltage CMOS for 3.3 V, 2.5 V and 1.8 V systems

Inside a chip, in 2026, everything is CMOS. Leading-edge processors run their cores at roughly 0.6–1.0 V, varying the voltage with the workload. But chips still talk to each other at standard interface voltages, and a board often mixes several: 3.3 V for general-purpose pins and many sensors, 1.8 V for newer parts and flash memories, 1.2 V and below for memory interfaces, and differential standards such as LVDS for fast links, where the receiver reads the difference between two wires and so ignores noise common to both.

Example— Connecting a 1.8 V sensor to a 3.3 V microcontroller

A sensor powered at 1.8 V drives a pin of a microcontroller powered at 3.3 V, and the microcontroller's pin drives back.

Sensor to microcontroller. The sensor's high output is at least 1.8−0.45=1.351.8 - 0.45 = 1.35 V. The 3.3 V input needs at least VIH=2.0V_{IH} = 2.0 V to be sure of a 1. So 1.35 V lies in the forbidden band: the link may work on the bench and fail on a cold morning. Some microcontrollers have inputs with lower thresholds, which the datasheet will say; otherwise a level translator is needed.

Microcontroller to sensor. The 3.3 V output is far above the 1.8 V part's supply. Its input pins have protection diodes to their supply, and 3.3 V would forward-bias them, pushing current into the sensor's supply rail. That is outside the absolute maximum ratings, which typically allow only a few tenths of a volt above the supply, and can damage the part or power it up through the pin. Again, use a translator, or an input the datasheet marks as tolerant of higher voltages.

A common, cheap solution for slow signals is an open-drain output with a pull-up resistor to the receiver's supply: the driver only ever pulls low, and the resistor sets the high level. Buses and interfaces uses exactly this for I²C.

If you want to try gates yourself, a breadboard, a 74HC00 (four NAND gates), a few LEDs with resistors and a current-limited bench supply or USB power at 5 V are a safe start, as in Building and measuring safely. Tie every unused input to the supply or ground, and never power such circuits from anything but a low-voltage, current-limited source.

ComputationC

A first Verilog check

Drawing gates gets tedious quickly, and a drawing cannot be tested. Engineers describe hardware in a hardware description language, and simulate it before building it. This level uses Verilog (with a few conveniences from SystemVerilog, its successor standard); Verilog and FPGAs covers it properly. For now, three ideas are enough:

  • A module is a piece of hardware with input and output ports, like a chip with pins.
  • Inside, Verilog's built-in gate primitives such as nand g1 (out, in1, in2); place a gate and connect it with wires. Order matters only for the ports: the output comes first.
  • A testbench is a module with no ports that drives the design's inputs, waits for the gates to settle, and checks the outputs. A good testbench checks itself: it compares every output with an independent expectation and stops with an error on the first mismatch.

The check below builds XOR from four NANDs (the circuit the CS lesson found in Python), builds a full adder from two of those XORs and three more NANDs, and compares both, on all eight input combinations, with Verilog's own ^ and + operators. It ends with a glimpse of something Python's 0 and 1 do not have.

verilog
// XOR and a full adder made only of NAND gates, checked against Verilog's own operators.
module xor_nand (input a, b, output y);
  wire n1, n2, n3;
  nand g1 (n1, a, b);        // primitive gates: output first, then inputs
  nand g2 (n2, a, n1);
  nand g3 (n3, b, n1);
  nand g4 (y, n2, n3);
endmodule

module full_adder_nand (input a, b, cin, output sum, cout);
  wire t, n_ab, n_tc;
  xor_nand x1 (.a(a), .b(b),   .y(t));
  xor_nand x2 (.a(t), .b(cin), .y(sum));
  nand g1 (n_ab, a, b);
  nand g2 (n_tc, t, cin);
  nand g3 (cout, n_ab, n_tc);  // NAND of NANDs = ab + t cin, by De Morgan
endmodule

module tb;
  logic a, b, cin;
  wire  y, sum, cout;
  xor_nand        u1 (.a(a), .b(b), .y(y));
  full_adder_nand u2 (.a(a), .b(b), .cin(cin), .sum(sum), .cout(cout));

  wire floating;             // nothing drives this wire, so its value is z
  wire w1, w0;
  nand p1 (w1, floating, 1'b1);
  nand p0 (w0, floating, 1'b0);

  initial begin
    $display("a b cin | a^b | cout sum");
    for (int i = 0; i < 8; i++) begin
      {a, b, cin} = i[2:0];
      #1;
      $display("%b %b  %b  |  %b  |  %b    %b", a, b, cin, y, cout, sum);
      if (y !== (a ^ b))            $fatal(1, "XOR is wrong for a=%b b=%b", a, b);
      if ({cout, sum} !== a + b + cin) $fatal(1, "adder is wrong for %b %b %b", a, b, cin);
    end
    $display("all 8 rows match a ^ b and a + b + cin");
    $display("NAND(z, 1) = %b   NAND(z, 0) = %b", w1, w0);
    if (w1 !== 1'bx || w0 !== 1'b1) $fatal(1, "unexpected four-valued result");
    $finish(0);
  end
endmodule

It prints:

text
a b cin | a^b | cout sum
0 0  0  |  0  |  0    0
0 0  1  |  0  |  0    1
0 1  0  |  1  |  0    1
0 1  1  |  1  |  1    0
1 0  0  |  1  |  0    1
1 0  1  |  1  |  1    0
1 1  0  |  0  |  1    0
1 1  1  |  0  |  1    1
all 8 rows match a ^ b and a + b + cin
NAND(z, 1) = x   NAND(z, 0) = 1

The carry logic deserves a second look. The textbook carry is AB+T CinAB + T\,C_{\text{in}} (with T=A⊕BT = A \oplus B), an OR of two ANDs. By De Morgan, AB‾⋅TCin‾‾=AB+TCin\overline{\overline{AB}\cdot\overline{T C_{\text{in}}}} = AB + T C_{\text{in}}, so a NAND of two NANDs computes it directly. This NAND–NAND form of any sum of products is how such logic is usually built in CMOS.

The last line shows Verilog's four-valued logic. Besides 0 and 1, a signal can be z (high impedance: nothing drives it) and x (unknown). A NAND with a floating input and a 1 on the other gives x, the simulator's honest "it depends"; with a 0 on the other input the output is 1 whatever the floating input does. The !== operator compares all four values exactly, which is why careful testbenches use it instead of !=.

Common misconceptionsH

Common misconceptions

Misconception

"A 1 is 5 volts (or 3.3 volts)." A 1 is any voltage above the family's VIHV_{IH} at an input, or above VOHV_{OH} at an output, and the numbers differ between families and supplies. Inside a modern chip a 1 may be 0.7 V.

Misconception

"AND and OR are the basic gates; NAND and NOR are AND and OR with something added." In CMOS it is the other way round. NAND and NOR are single stages of four transistors; AND and OR are NAND and NOR followed by an inverter, six transistors and two delays.

Misconception

"An unconnected input reads as 0." A floating CMOS input is a tiny capacitor that drifts wherever leakage and nearby fields push it, often into the forbidden band, where both transistors of the input stage are partly on: the gate draws current it should not and may oscillate. Every CMOS input must be driven, or tied to a rail. (Old TTL inputs tended to float high, which is how this belief started, and they were not reliable either.)

Misconception

"Boolean algebra is ordinary algebra with 0 and 1." Several familiar rules fail (A+A=AA + A = A, not 2A2A; there is no cancellation), and some Boolean laws, such as A+BC=(A+B)(A+C)A + BC = (A + B)(A + C), have no counterpart in arithmetic. Check any new manipulation by perfect induction.

History & global context

A short history

George Boole published his algebra of logic in 1854. Augustus De Morgan, his contemporary, stated the laws that carry his name. Charles Sanders Peirce noticed around 1880, in notes not published until much later, that a single operation, which we now call NOR, could express all the others; Henry Sheffer published the same fact for NAND in 1913, and NAND is still sometimes called the Sheffer stroke. Edward Huntington gave Boolean algebra its axioms in 1904, and Emil Post characterised every complete set of operations in 1941.

Claude Shannon's 1937 master's thesis showed that relay circuits obey Boole's algebra, so that switching circuits could be designed on paper. Frank Wanlass at Fairchild Semiconductor described complementary MOS logic in 1963, noting that it drew almost no power when idle; RCA's 4000 series made it a product in 1968. By the late 1980s CMOS had displaced bipolar logic almost everywhere, because when a chip holds millions of gates, the gate that draws no power while waiting wins.

Exercises

Exercises

1. Logic gates and Boolean algebra

Warm-upHuman

A logic family guarantees VOH=2.0V_{OH} = 2.0 V, VOL=0.2V_{OL} = 0.2 V, VIH=1.7V_{IH} = 1.7 V and VIL=0.7V_{IL} = 0.7 V. What is its worst-case noise margin, in millivolts?

2. Logic gates and Boolean algebra

Warm-upHuman

Which expression equals AB+C‾\overline{AB + C}, the output of an AND-OR-INVERT gate?

Choose one

3. Logic gates and Boolean algebra

CoreHuman

How many transistors does a single-stage static CMOS gate computing Y=AB+CD‾Y = \overline{AB + CD} need? (Each input drives one NMOS and one PMOS.)

4. Logic gates and Boolean algebra

CoreComputational

Write counterexample(f, g, n), which checks two nn-input Boolean functions (Python functions of nn arguments, each 0 or 1, returning 0 or 1) by perfect induction. Try the rows in binary counting order (first argument most significant: (0, 0, 0), (0, 0, 1), (0, 1, 0), …) and return the first row, as a tuple, where they differ; return None if they agree on every row.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

5. Logic gates and Boolean algebra

CoreHuman

A sensor powered at 1.8 V (VOH=1.35V_{OH} = 1.35 V) drives an input of a chip powered at 3.3 V (VIH=2.0V_{IH} = 2.0 V, VIL=0.8V_{IL} = 0.8 V). What happens?

Choose one

6. Logic gates and Boolean algebra

CoreHuman

A block of logic has 500 pF of total switchable capacitance and an activity factor of 0.1 (on average a tenth of it is charged each cycle). It runs at 0.8 V with a 2 GHz clock. Using P=αCV2fP = \alpha C V^2 f, what is its dynamic power, in milliwatts?

Further reading and resources

  • A symbolic analysis of relay and switching circuits · Claude E. Shannon · 1938The master's thesis that turned Boole's algebra into a design method for circuits.
  • JEDEC Solid State Technology AssociationThe standards body whose interface standards define logic levels such as 3.3 V LVCMOS and 1.8 V CMOS.
  • Logical effort: designing fast CMOS circuits · Ivan Sutherland, Bob Sproull and David Harris · 1999The book behind the gate-sizing numbers in this lesson; a method for estimating and minimising delay in CMOS logic.
  • SkyWater SKY130 open-source process design kitA real, openly published 130 nm CMOS process, with standard-cell libraries of NAND, NOR and AOI gates you can inspect.
  • Icarus VerilogThe open-source Verilog simulator that runs this lesson's check.