Logic Gates and Truth Tables

A gate's output depends only on its inputs right now. Present the same inputs a second time and you get the same output, because there is nowhere for anything else to be stored. That property is called combinational, and it is what separates this module from the sequential one, where a feedback path lets a circuit remember.

Since a gate's behaviour is a function from a finite set of input combinations to one bit, it is completely described by listing every combination. That list is a truth table, and with n inputs it has 2ⁿ rows.

The bubble on a gate symbol always means inverted. NAND, NOR and XNOR are AND, OR and XOR wearing one — which is four of the seven learned for free.

• A · 0 = 0 and A · 1 = A — AND masks: a 0 forces the bit off, a 1 passes it through.
• A + 1 = 1 and A + 0 = A — OR sets: a 1 forces the bit on, a 0 passes it through.
• A ⊕ 0 = A and A ⊕ 1 = A′ — XOR is a controllable inverter.
• A ⊕ A = 0 — which is why XOR-ing twice with the same value gets you back where you started.
• 1 + 1 = 1. The + is Boolean, not arithmetic: the question is *any*, not *how many*.

XOR is the odd one out — it is not any gate with a bubble on it — and it turns up everywhere because "do these two differ?" is a question hardware constantly asks.

• The sum output of a half adder is A ⊕ B; the carry is A · B. Every adder in every CPU starts here.
• Parity: XOR of all bits is 1 exactly when an odd number of them are 1.
• CRC is XOR arithmetic and nothing else — the networking topic on it is this gate, applied repeatedly.
• XNOR is an equality test, so eight XNORs and an AND make an 8-bit comparator.

A set of gates is functionally complete when every Boolean function can be built from it. {AND, OR, NOT} obviously is. The surprising result is that {NAND} alone is, and the proof is three constructions:

1. 1NOT — tie both inputs together: (A · A)′ = A′. One gate.
2. 2AND — NAND, then invert with a second NAND: ((A · B)′)′ = A · B. Two gates.
3. 3OR — invert both inputs, then NAND: (A′ · B′)′ = A + B by De Morgan. Three gates.

With NOT, AND and OR all available, anything is. NOR is universal by the mirror-image argument. Neither AND alone nor OR alone is — without a way to produce an inversion, no amount of either will ever give you one.

This is not a curiosity. NAND is the cheapest gate in CMOS — an AND is literally a NAND followed by an inverter, so it costs *more* transistors — so a fabrication process only has to be excellent at making one kind of gate.

Fan-in

How many inputs one gate has. Large fan-in gates are slower and harder to build, so a wide AND is usually a tree of narrow ones.

Fan-out

How many gate inputs one output can drive while still holding valid logic levels. Exceed it and the voltage sags into the forbidden band.

Propagation delay

The time between an input changing and the output settling. It is why a circuit's speed is set by its longest path, and it is the entire reason clocks exist.