Logic Gates

A logic gate is a physical or abstract device that computes a single Boolean Algebra function of one or two input bits, producing exactly one output bit. Inputs and outputs take only two values, conventionally written `0` and `1`, and corresponding physically to two voltage ranges (e.g., "low" near 0V and "high" near the supply voltage). Because gates operate on discrete voltage levels rather than continuous ones, small amounts of electrical noise are automatically suppressed — this is the foundational reason digital circuits are reliable where analog ones are fragile. The behavior of a gate is completely and unambiguously specified by its truth table: a table listing every possible combination of input values together with the corresponding output. For $n$ input bits there are $2^n$ rows, since each bit independently takes one of 2 values. A gate with 2 inputs has 4 rows; a gate with 3 inputs has 8 rows. Because a truth table is exhaustive — it lists every input combination, not just typical ones — two gates with identical truth tables are functionally indistinguishable no matter how differently they are built internally. This is precisely why we can reason about circuits abstractly (with Boolean algebra) while manufacturers reason about them physically (with transistors), and both descriptions agree. The primitive gates are:

• NOT (inverter): one input, flips it. $Y = \overline{A}$.
• AND: output is 1 only if all inputs are 1. $Y = A \cdot B$.
• OR: output is 1 if at least one input is 1. $Y = A + B$.

From these, three derived gates matter enormously in practice:

• NAND = NOT(AND): output is 0 only if all inputs are 1.
• NOR = NOT(OR): output is 1 only if all inputs are 0.
• XOR (exclusive OR): output is 1 if the inputs differ. $Y = A \oplus B$.
• XNOR = NOT(XOR): output is 1 if the inputs are equal.

A set of gates is functionally complete (or universal) if, by composing gates from that set alone, you can build a circuit realizing any Boolean function of any number of inputs. AND, OR, and NOT together are trivially complete — this is essentially the statement that every Boolean function has a sum-of-products (disjunctive normal form) expression. The deeper and more useful fact is that NAND by itself is complete, and separately, NOR by itself is complete. This is why NAND and NOR are called universal gates: a fabrication line that can manufacture only one of these two gate types can, in principle, build any digital circuit at all, including every gate in this article.

Truth tables of the primitive and derived gates

For two inputs $A, B \in \{0,1\}$:

NOT has a single input:

Notice the row-by-row relationships: NAND's column is exactly AND's column with every bit flipped, and NOR's column is exactly OR's column flipped — this is literally what "NOT-AND" and "NOT-OR" mean, and it is verifiable by direct inspection of the table above.

Building any gate from NAND alone

The claim that NAND is universal is not mysterious once you see the constructions. Each of the following can be checked by tracing signals through the small circuit and confirming the resulting truth table matches the target gate exactly.

NOT from NAND. Tie both inputs of a NAND gate to the same signal $A$. Then NAND$(A,A) = \overline{A \cdot A} = \overline{A}$.

AND from NAND. Feed $A,B$ into a NAND gate to get $\overline{A\cdot B}$, then invert that result using a NOT-from-NAND (i.e., another NAND with both inputs tied together): $\overline{\overline{A \cdot B}} = A \cdot B$.

OR from NAND. By De Morgan's law, $A + B = \overline{\overline{A}\cdot\overline{B}}$. So invert $A$, invert $B$ (each with a NAND-as-NOT), then NAND the two inverted signals together.

XOR from NAND. A standard 4-NAND construction: ``` n1 = NAND(A, B) n2 = NAND(A, n1) n3 = NAND(B, n1) Y = NAND(n2, n3) ``` Tracing all four input rows confirms $Y = A \oplus B$ (worked in detail below). Since NOT, AND, and OR can each be built from NAND, and {AND, OR, NOT} is already complete (every Boolean function has a sum-of-products form built from ANDs, ORs, and NOTs), it follows that NAND alone is complete. The symmetric argument, using $A\cdot B = \overline{\overline{A}+\overline{B}}$, shows NOR alone is also complete.

Algorithm: evaluating any gate network (simulation)

In practice, digital designers verify gate networks by simulation: propagate known input values forward through a directed acyclic graph of gates and confirm the outputs match a specification. This is the algorithmic heart of every hardware simulator, from a classroom truth-table checker to full SPICE-level tools. ```

# Represent a combinational circuit as a DAG of gates.

# Each gate node has: a type (AND, OR, NOT, NAND, NOR, XOR, XNOR),

# a list of input wires, and one output wire. function SIMULATE(circuit, input_assignment): value = {} # wire -> 0/1 for wire, bit in input_assignment.items(): value[wire] = bit order = TOPOLOGICAL_SORT(circuit) # gates ordered so inputs are ready for gate in order: ins = [value[w] for w in gate.inputs] value[gate.output] = APPLY(gate.type, ins) return {w: value[w] for w in circuit.output_wires} function APPLY(gate_type, ins): if gate_type == NOT: return 1 - ins[0] if gate_type == AND: return 1 if all(b == 1 for b in ins) else 0 if gate_type == OR: return 1 if any(b == 1 for b in ins) else 0 if gate_type == NAND: return 1 - APPLY(AND, ins) if gate_type == NOR: return 1 - APPLY(OR, ins) if gate_type == XOR: return ins[0] ^ ins[1] # 2-input case if gate_type == XNOR: return 1 - APPLY(XOR, ins) function TOPOLOGICAL_SORT(circuit):

# circuit must be acyclic (combinational logic has no feedback);

# standard Kahn's-algorithm / DFS topological sort on the gate DAG ... ``` The topological sort is required because a gate's output cannot be computed until every one of its inputs has already been assigned a value — exactly the dependency structure of a DAG.

Time complexity of gate evaluation. A single gate is evaluated in $O(1)$ time (bounded by the number of literal inputs, typically 1–3). Simulating an entire circuit with $G$ gates and $W$ wires takes $O(G + W)$ time: topological sort visits every gate and wire once (standard for DAG algorithms), and each gate is then evaluated once in $O(1)$. This is optimal — you cannot correctly simulate a circuit without at least reading every gate and wire once, so $\Omega(G+W)$ is a matching lower bound.

Space complexity. $O(W)$ to store the value of every wire, plus $O(G)$ for the gate list itself — linear in the size of the circuit description.

Correctness of gate simulation. The correctness argument rests on an invariant maintained by the topological order: by the time gate $g$ is processed, every wire feeding into $g$ has already been assigned its correct final value. This holds by construction of a topological sort — a gate is only listed after all gates producing its input wires (or the input wires are primary inputs, given up front). Since combinational logic is required to be acyclic (no feedback path — feedback is what turns gates into memory elements, covered in Latches and Flip-Flops), a valid topological order always exists. By induction on the topological order, every gate computes its output from already-correct inputs, so the whole simulation is correct.

Correctness of the NAND-completeness claim. This is a genuine theorem, not a hand-wave, and it is worth stating the two-step proof precisely. Step 1 — {AND, OR, NOT} is complete. Any Boolean function $f(x_1,\dots,x_n)$ can be written in disjunctive normal form: for each input row where $f = 1$, form the AND of all variables (complemented where the row has a 0), then OR all such terms together. Every function equals the OR of its "minterms," so AND, OR, and NOT together realize every possible function. This is a direct consequence of the definition of a truth table: it is a listing of the rows where the function is 1, and DNF just encodes that listing as a formula. Step 2 — NAND builds NOT, AND, and OR. Shown explicitly above: NOT$(A)$ = NAND$(A,A)$; AND$(A,B)$ = NOT(NAND$(A,B)$); OR$(A,B)$ = NAND(NOT$(A)$, NOT$(B)$) by De Morgan's law $A + B = \overline{\overline A \cdot \overline B}$. Chaining Steps 1 and 2: since NAND can build NOT, AND, OR, and {NOT, AND, OR} can build any function, NAND alone can build any function. The dual argument with $A \cdot B = \overline{\overline A + \overline B}$ shows NOR is likewise complete.

Honest tradeoffs. Universality is a statement about what is expressible, not about efficiency. A NAND-only implementation of a function may use many more gates, and much more circuit depth (hence propagation delay), than a design using a rich mixture of gate types. Real standard-cell libraries include dozens of gate variants (including multi-input gates and complex "compound" gates like AND-OR-INVERT) precisely because using the "right" gate directly is faster and smaller than always reducing to NAND. Universality guarantees feasibility; it says nothing about optimality.

Trace the 4-NAND XOR circuit from the diagram through all four input combinations, not just the one pictured, to confirm it truly implements XOR everywhere. Recall the construction: ``` n1 = NAND(A, B) n2 = NAND(A, n1) n3 = NAND(B, n1) Y = NAND(n2, n3) ```

Every row matches the XOR truth table exactly, so this 4-gate NAND network really is a correct implementation of XOR — not merely correct on the one case drawn in the figure. Note the asymmetric-looking middle rows ($A=0,B=1$ and $A=1,B=0$) both correctly yield $Y=1$ despite following different internal value paths, which is exactly the kind of non-trivial case a hasty check might skip. As a second, smaller trace, verify NOR-based construction of AND using $A \cdot B = \overline{\overline{A}+\overline{B}}$:

(Here NOT and OR are themselves built from NOR the same way NOT and AND were built from NAND, by symmetry.)

The theoretical bridge between Boolean algebra and physical switching circuits was built by several people working on telephone relay networks and symbolic logic in the early-to-mid 20th century.

Every digital integrated circuit — from a microcontroller in a toaster to a data-center CPU — is fabricated as a network of logic gates realized in transistors, almost universally using CMOS technology today because of its extremely low static power draw. Hardware description languages (Verilog, VHDL, SystemVerilog) let engineers describe circuits at a high level, but synthesis tools compile that description down into a gate-level netlist drawn from a standard-cell library — literally a catalog of pre-characterized AND, OR, NAND, NOR, XOR, and compound gates, each with known area, speed, and power. Arithmetic Logic Units use XOR gates as the core of binary adders (a full adder is built from XOR and AND/OR gates); parity bits and simple error-detection codes in memory and networking hardware are direct applications of XOR's "detect a difference" property. Field-Programmable Gate Arrays (FPGAs) are literally arrays of reconfigurable lookup tables that can be programmed to emulate any small logic function, echoing the universality principle at a coarser grain. The next layers of digital design — Combinational Logic Design, building Multiplexers and Decoders, and using controlled feedback to build Latches and Flip-Flops — all start from exactly the gates defined here.

Ask the tutor: How do you mechanically convert a truth table into a minimal NAND-only circuit?