Logic basics
Logic gates and their truth tables
A logic gate is a tiny machine that looks at one or two bits and produces one bit. Seven of them have names worth knowing. Here they are, each with a truth table and a demo you can click.
A bit is a value that is either 0 or 1: off or on, false or true, low voltage or high. A gate takes bits in and gives one bit out, according to a fixed rule. The rule is usually written as a truth table, which lists every possible input and the output for each. Gates have no memory and no hidden state. The same inputs always give the same output.
NOT: the inverter
One input, one output, and the output is always the opposite of the input. In Boolean algebra it is written ¬A, A′ or Ā. In code it is !a.
| A | Q |
|---|---|
| 0 | 1 |
| 1 | 0 |
Everyday version: a “door open” warning light is the NOT of a “door closed” sensor.
AND: all of them
The output is 1 only when every input is 1. Written A ∧ B or A · B, and a && b in code.
Everyday version: a machine that starts only when the guard is closed and the start button is pressed.
OR: at least one
The output is 1 when any input is 1, including when all of them are. Written A ∨ B or A + B, and a || b in code. This “inclusive” OR is not quite the same as the English “or” in “tea or coffee?”, which usually means one but not both. That one is XOR.
Everyday version: a car’s interior light comes on if any door is open.
XOR: exactly one (or: are they different?)
Exclusive OR gives 1 when its two inputs differ. Written A ⊕ B, and a ^ b in most programming languages. With more than two inputs, XOR gives 1 when an odd number of them are 1, which is why it is the heart of parity checks.
Everyday version: a staircase light with a switch at the top and another at the bottom. Flipping either switch toggles the light. XOR shows up all over computing: in addition (a sum bit is 1 when an odd number of bits are 1), in checksums and error-detecting codes, in simple ciphers (XOR a message with a key, then XOR it with the same key again to get the message back), and in graphics tricks.
NAND, NOR, XNOR: the inverted three
Put an inverter on the output of AND, OR or XOR and you get NAND, NOR and XNOR.
NAND
| A | B | Q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
NOR
| A | B | Q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
XNOR
| A | B | Q |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
XNOR is the equality gate: 1 when the inputs are the same. NAND and NOR are special because each one is universal: either one alone is enough to build all the others, and from them, any digital circuit. Why NAND can build every other gate explains why, and the NAND page explains why chips favour it.
Rectangular (IEC) symbols
Many European textbooks and datasheets use the IEC 60617 symbols instead of the curved ANSI shapes. Every gate is a rectangle with a label inside: & for AND, ≥1 for OR, =1 for XOR, and 1 for a plain buffer. A small circle (or a triangle flag) on the output marks inversion, so a NAND is an & box with a circle. The logic is identical. Only the drawing differs.
Sixteen functions, seven names
There are 16 possible gates with two inputs, one for each way of filling in a four-row truth table. Seven have common names. A few of the others are worth knowing: implication (A → B, false only when A is 1 and B is 0) is a staple of logic courses, and inhibition (A AND NOT B) turns up wherever one signal needs to veto another.
From gates to everything else
Gates are the bottom layer. Combine a few and you can choose between signals (a multiplexer), add numbers (an adder) or compare them. Feed outputs back to inputs and you get memory (flip-flops). Add a clock and you get a machine that steps through a program (a CPU).