Boolean Logic & Truth Tables
Deep inside every computer, all data — numbers, letters, images and sounds — is stored as Boolean values: long streams of 1s and 0s. Boolean logic is the set of rules a computer follows to make decisions using just these two values, where 1 means true (or ‘on’) and 0 means false (or ‘off’). Almost every action a machine takes, from unlocking a phone to deciding whether a game character can jump, comes down to combinations of trues and falses.
Each of those decisions is built from tiny electronic components called logic gates. A logic gate takes one or more binary inputs and produces a single binary output, always following the same fixed rule. Millions of these gates sit inside the arithmetic logic unit, the part of the processor that carries out calculations and logical comparisons. The whole system is named after George Boole, a 19th-century English mathematician who first set out this kind of algebra long before computers existed.
There are three fundamental logic gates you must know: AND, OR and NOT. Any circuit, however large or complex, can be built by combining just these three.
The AND gate
An AND gate has two inputs and one output. Its output is 1 only when both inputs are 1; if either input is 0, the output is 0. A helpful picture is two switches wired one after the other (in series) — the current can only flow when both switches are closed at the same time. To record how any gate behaves we use a truth table, which lists every possible combination of inputs and shows the output for each.
| Input A | Input B | Output Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Notice there is only a single 1 in the output column — on the bottom row, the one row where both inputs are 1.
The OR gate
An OR gate also has two inputs and one output, but its output is 1 when at least one input is 1. The only way to get an output of 0 is for both inputs to be 0 together. Picture two switches wired side by side (in parallel): the current flows if either one of them is closed.
| Input A | Input B | Output Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
This time there is only a single 0 in the output column, on the top row where both inputs are 0. Everywhere else the output is 1.
The NOT gate
A NOT gate works differently: it has just one input and one output. It simply reverses, or inverts, whatever it is given, so an input of 0 becomes 1 and an input of 1 becomes 0. Because it flips the signal, a NOT gate is often called an inverter. Its truth table is the shortest of the three.
| Input A | Output Q |
|---|---|
| 0 | 1 |
| 1 | 0 |
Each gate is drawn with its own distinctive shape inside a logic diagram. The AND gate is drawn with a flat back and a rounded front, so it looks like a capital letter D. The OR gate has a curved back and narrows to a point at the output, giving it a shield or spaceship shape.
The NOT gate is drawn as a small triangle pointing towards its output, with a tiny circle (called a bubble) on the very tip. That bubble is the giveaway that the signal is being inverted — if you ever see it, you know the gate flips its input.
The number of rows a truth table needs depends on how many inputs the circuit has. For a circuit with \(n\) inputs, the table needs \(2^n\) rows — so 1 input needs 2 rows, 2 inputs need 4 rows, and 3 inputs need 8 rows.
Combining logic gates
Real circuits usually join several gates together, and this is exactly the same idea as using AND, OR and NOT inside the conditions of a program. To read a combined circuit, work out the output of each gate one step at a time, following the signals from the inputs through to the final output. Writing the circuit as a Boolean expression first makes this much easier to track.
Take a circuit written as Q = (A AND B) OR C. To build its full truth table, first list all \(2^3 = 8\) possible combinations of A, B and C. Next add a helper column that works out A AND B for each row. Finally work out Q by applying OR to that helper column and to C. The brackets tell you to deal with the AND gate before the OR gate.
| A | B | C | A AND B | Q |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
A Boolean expression is a shorthand way of describing a circuit without drawing it. You can spell the operators out in words — A AND B — or use symbols, where a dot stands for AND, a plus sign stands for OR, and a bar written over a letter stands for NOT. Brackets show which operation to work out first, exactly as they do in ordinary maths.
The real skill is being able to move freely between four different ways of describing the same logic: a written description in plain English, a Boolean expression, a logic diagram of gates, and a completed truth table. Each one contains exactly the same information, just presented differently.