Helpful context:

Every calculation your computer performs - adding two numbers, checking whether a password matches, rendering a pixel - ultimately happens through arrangements of a few extremely simple circuits. Each circuit asks one question: given some inputs that are either on or off, what should the output be? These circuits are logic gates, and they are the atoms from which all computation is built.

From Transistors to Gates

A transistor is a switch. Apply a voltage to its control terminal and current flows through; remove it and current stops. That is it - on or off. Modern CPUs contain tens of billions of them.

Wire two transistors in series (both must be on for current to flow) and you have an AND gate. Wire them in parallel (either one allows current to flow) and you have an OR gate. Wire one so it inverts its input and you have a NOT gate.

We do not think about transistors directly. We think about gates - the logical abstractions one level up.

The Six Fundamental Gates

AND A B Out 0 0 0 0 1 0 1 0 0 1 1 1 1 only if both inputs are 1 OR A B Out 0 0 0 0 1 1 1 0 1 1 1 1 1 if at least one input is 1 NOT A Out 0 1 1 0 flips the input XOR A B Out 0 0 0 0 1 1 1 0 1 1 1 0 1 when inputs differ NAND A B Out 0 0 1 0 1 1 1 0 1 1 1 0 AND with inverted output NOR A B Out 0 0 1 0 1 0 1 0 0 1 1 0 OR with inverted output

AND outputs 1 only when both inputs are 1. Think of two switches in series: both must be closed for current to flow.

OR outputs 1 when at least one input is 1. Two switches in parallel: either one allows current.

NOT inverts its single input. Also called an inverter.

XOR (exclusive or) outputs 1 when the inputs differ. Identical inputs give 0.

NAND and NOR are AND and OR with their outputs inverted. The small circle on the output symbol denotes the inversion.

NAND Is Enough for Everything

One of the strangest facts in digital logic: you can build any other gate entirely from NAND gates. AND, OR, NOT, XOR - all of them can be constructed from NAND alone.

NOT from NAND: connect both NAND inputs together. $\text{NAND}(A, A) = \overline{A \cdot A} = \overline{A}$.

AND from NAND: NAND followed by NOT (which is itself a NAND with tied inputs).

OR from NAND: by De Morgan’s law, $A + B = \overline{\overline{A} \cdot \overline{B}}$ - NOT both inputs, then NAND.

This is called universality. NOR is also universal by the same reasoning. Chip manufacturers often fabricate only NAND or NOR gates and build everything else from them, since it is cheaper to produce one type of transistor structure at scale.

Boolean Algebra

Logic gates implement Boolean algebra - the algebra of true and false, 1 and 0.

De Morgan’s laws are the most important identities:

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

In words: NOT(A AND B) = (NOT A) OR (NOT B), and vice versa. These let you push negations through expressions and convert between AND-based and OR-based forms.

Other useful identities:

Identity Meaning
$A \cdot A = A$ AND with itself is itself
$A + A = A$ OR with itself is itself
$A \cdot \overline{A} = 0$ Something AND its opposite is always 0
$A + \overline{A} = 1$ Something OR its opposite is always 1
$A \cdot 1 = A$ AND with 1 preserves the value
$A + 0 = A$ OR with 0 preserves the value

Combining Gates

A single gate is not very useful. Power comes from connecting gates: the output of one feeds the input of another. The output at any point depends only on the current inputs - there is no memory, no state. This is called combinational logic.

For example: the expression $A \cdot B + C$ (A AND B, then OR with C) is implemented as an AND gate whose output feeds one input of an OR gate. The output is 1 if either both A and B are 1, or C is 1.

The number of possible outputs for $n$ inputs is $2^{2^n}$ - there are $2^n$ input combinations and each could independently be 0 or 1. For just 2 inputs there are 16 possible functions; for 3 inputs, 256. Gates let you implement any of them.

The simplest real example is a half adder - a circuit that adds two single bits. It produces two outputs: a sum bit ($A \oplus B$, which is XOR) and a carry bit ($A \cdot B$, which is AND, indicating whether the addition overflowed into the next bit position). The entire chip is two gates: half adder chip XOR AND A B Sum Carry

Both inputs (A and B) fan out to both gates. The filled dots mark where a wire branches - a crossing without a dot is just wires passing over each other with no connection. The XOR gate produces the sum bit; the AND gate produces the carry. If A=1 and B=1: sum = $1 \oplus 1 = 0$, carry = $1 \cdot 1 = 1$, meaning $1 + 1 = 10$ in binary (decimal 2). This is what the inside of a chip looks like - gates wired together, each doing one small thing, the combination doing something useful.

Discomfort check. Are these gates physically separate components? In modern CPUs, no. Individual gates are formed directly from groups of transistors on silicon - there is no distinct physical “AND gate” you could point to. But the logical abstraction holds precisely: the transistors are arranged so that the input-output relationship matches the gate’s truth table. We reason about gates; the hardware implements the truth tables.

Summary

Gate Symbol Output is 1 when…
AND $A \cdot B$ Both inputs are 1
OR $A + B$ At least one input is 1
NOT $\overline{A}$ Input is 0
XOR $A \oplus B$ Inputs differ
NAND $\overline{A \cdot B}$ Not both inputs are 1
NOR $\overline{A + B}$ Both inputs are 0

NAND and NOR are each sufficient to build any other logic function. All digital computation - arithmetic, comparison, memory, control - is built by composing these basic elements.

Read next: