Two values, and the operations on them
Digital electronics works with exactly two values, written 1 and 0, or true and false, or high and low voltage. Boolean algebra is the mathematics of those two values, and a logic gate is the physical circuit that carries out one Boolean operation.
Everything a computer does is built from these. An adder is gates. A memory cell is gates. The whole processor is millions of them wired together, which is why this chapter sits underneath everything else in the subject.
| Gate | Symbol in algebra | Output is 1 when… |
|---|---|---|
| NOT | A′ or Ā | the input is 0 — it simply inverts |
| AND | A · B | both inputs are 1 |
| OR | A + B | at least one input is 1 |
| NAND | (A · B)′ | NOT both — the opposite of AND |
| NOR | (A + B)′ | neither input is 1 |
| XOR | A ⊕ B | the inputs differ |
Toggle the inputs and watch the output. XOR is the one worth studying — it outputs 1 only when the inputs disagree, which is exactly the behaviour a binary adder needs.
Truth tables
A truth table lists every possible combination of inputs and the output for each. Two inputs give 2² = 4 rows; three inputs give 8. Write the rows in a fixed order — 00, 01, 10, 11 — and none will be missed.
For a circuit made of several gates, add one column per intermediate signal. Fill the columns left to right, and the final column is the circuit's behaviour. This is how you prove two different circuits do the same job: build both tables and compare them row by row.
Build the truth table for X = (A · B)′ + C.
- Three inputs, so there are
2³ = 8rows.Count the rows before drawing the table; an incomplete table cannot score full marks. - Add a column for
A · B, which is 1 only in the rows where both A and B are 1.Work outward from the innermost bracket, exactly as in arithmetic. - Add a column for
(A · B)′, which is the previous column inverted.The NOT applies to the whole bracket, not to A alone. - The output is that column OR C: 1 wherever either is 1.X is 0 only in the two rows where A and B are both 1 and C is 0.
X = 0 only when A = 1, B = 1 and C = 0; X = 1 in the other six rows.
Boolean algebra and simplification
Circuits cost money and power, so a design that uses four gates is worse than an equivalent one using two. Boolean algebra is how you get from the first to the second, and the laws below are the tools.
Most of them look like ordinary algebra. Two do not, and those two are where the marks are.
Simplify X = A·B + A·B′.
- Both terms share the factor A, so take it out:
A·(B + B′).Factorising is the first move in almost every simplification. B + B′ = 1by the complement law — B is either true or false, so one of the two must hold.This is the law that does the real work here.X = A · 1 = A.Two gates and an inverter reduced to a plain wire. Verify with a truth table: X matches A in all four rows ✓
X = A
The two that are not like ordinary algebra
A + A = A, not 2A — there is no 2 in Boolean algebra. And A + 1 = 1, not 2: once one input to an OR is true, the output is true whatever else happens. Students carry decimal habits into these and lose marks on the very first line of a simplification.
Building arithmetic from gates
The reason gates matter is that they can add. A half adder takes two bits and produces a sum and a carry: the sum is A ⊕ B and the carry is A · B. Check it against the binary rules — 1 + 1 gives sum 0, carry 1, which is exactly what XOR and AND produce.
A half adder cannot accept a carry coming in from the column to its right, so it is useless beyond the first column. A full adder takes three inputs — A, B and carry-in — and chaining eight of them together builds an 8-bit adder. That circuit is inside the ALU of every processor.
Before you leave this chapter
- AND needs both, OR needs at least one, NOT inverts, XOR needs them to differ.
- n inputs give 2ⁿ rows in the truth table — write them in a fixed order.
- A + A = A and A + 1 = 1. Boolean algebra has no 2.
- De Morgan: (A·B)′ = A′ + B′ and (A+B)′ = A′·B′.
- Half adder = XOR for sum, AND for carry. A full adder also takes a carry in.
From a problem in words to a circuit
The examinable skill that ties this chapter together is turning a description into a Boolean expression and then into a circuit. The method is mechanical once you see it.
Write a truth table with one row per input combination. For every row where the output is 1, write the product of the inputs — using the variable where it is 1 and its complement where it is 0. Then OR all those products together. The result is called the sum of products form, and it always works.
An alarm sounds when the door is open (D = 1) AND either the system is armed (A = 1) or the panic button is pressed (P = 1). Write the expression and simplify.
- Translate directly: "door open AND (armed OR panic)" becomes
X = D · (A + P).Read the sentence for the word "and" and the word "or"; the brackets follow the grouping in the English. - Expanding gives
X = D·A + D·P, the sum-of-products form.Both forms are correct. The bracketed one uses fewer gates; the expanded one is easier to read off a truth table. - Gate count: the bracketed version needs one OR and one AND — two gates.The expanded version needs two ANDs and one OR — three gates for identical behaviour.
- So the factorised form is the better circuit.Fewer gates means lower cost, less power and less delay. That is why simplification is worth doing at all.
X = D · (A + P), using two gates rather than three
Reading the English carefully
The word "or" in a specification is almost always inclusive — armed or panic or both. If a question genuinely means one or the other but not both, it will say so, and that is XOR rather than OR. Underline the ands and ors in the question before writing a single symbol.