Logic Gates & Binary Adders

Switches are either open or closed; a lamp is on or off; a statement is true or false. Build circuits that compute with just two values, 0 and 1, and you can make a machine that adds, and then one that does anything a computer does.

A world of 0s and 1s#

A logical variable can take only two values, written 0 and 1. A logical function of such variables is fully described by listing its value for every combination of inputs: its truth table.

AND, OR, NOT with switches

Let A and B be two switches (1 = closed) and C a lamp (1 = on), all powered by one battery.

• Switches in series: the lamp lights only if both are closed. C = A AND B, written A·B or AB.
• Switches in parallel: the lamp lights if either (or both) is closed. C = A OR B, written A + B.
• A switch across the lamp: closing it short-circuits the lamp. The lamp is on exactly when the switch is open: B = NOT A, written $\overline{A}$.

Here “+” means OR, not ordinary addition.

Logic gates#

AND and OR from diodes

AND: two diodes run from the output X to inputs A and B, and a resistor connects X to +5 V. If either input is at 0 V, its diode is forward-biased and (being ideal) connects X to 0 V: X = 0. Only when both inputs are at 5 V do both diodes stop conducting; then no current flows through the resistor and X sits at 5 V. That is AND.

OR: the diodes point from A and B to X, and the resistor goes from X to 0 V. If both inputs are 0 V nothing flows and X = 0. If either is at 5 V, its diode conducts and lifts X to 5 V. That is OR.

NOT from a transistor

Diodes alone cannot invert. Use an n-p-n transistor with its emitter at 0 V and its collector joined to +5 V through a resistor R_C; the output X is taken at the collector, and the input A drives the base.

• A = 0: no base–emitter bias, so no current anywhere, no drop across R_C, and X = 5 V, i.e. 1.
• A = 1: the base–emitter junction is forward-biased, a large collector current flows, R_C drops nearly the full 5 V, and X ≈ 0.

NAND, NOR and XOR#

• NAND is an AND followed by a NOT; NOR is an OR followed by a NOT. Their symbols add a small circle (a “bubble”) at the output.
• XOR (exclusive OR) is 1 when exactly one input is 1. It can be built from AND, OR and NOT gates using A XOR B = $A\overline{B} + \overline{A}B$.

Universal gates

Every logic gate can be built from NAND gates alone (or NOR gates alone), so each is called a universal building block:

• NOT: join both inputs of a NAND: NOT(A·A) = $\overline{A}$.
• AND: a NAND followed by a NAND-as-NOT, which inverts back to AB.
• OR: invert each input with a NAND-as-NOT, then NAND them: $\overline{\overline{A}\,\overline{B}} = A + B$.

Adding with gates#

Computers store numbers in binary, using only the digits 0 and 1: 1, 10, 11, 100, 101… stand for one, two, three, four, five. The addition rules are 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1 + 1 = 10 (“one zero”, i.e. two). When the answer has two digits, the left one is the carry C and the right one the sum S.

Compare with the gate tables: C = A AND B and S = A XOR B. One AND gate and one XOR gate make a half adder.

Adding multi-digit numbers needs columns that add three bits: two digits plus the carry from the right. A full adder does it with two half adders: add the first two bits (sum S₁, carry C₁), then add the third bit to S₁ (sum S, carry C₂). C₁ and C₂ can never both be 1, so the final carry is C₁ OR C₂.