Boolean values and logic gates: NOT, AND, OR
Boolean logic (after George Boole) has only two values: 1 = true, 0 = false. A logic gate is a tiny circuit that takes Boolean inputs and gives one output.
- NOT (A' or Ā): one input; flips it.
- AND (A·B): 1 only when all inputs are 1.
- OR (A + B): 1 when at least one input is 1.
NAND, NOR and XOR gates
- NAND = NOT AND: (A·B)'. 0 only when all inputs are 1.
- NOR = NOT OR: (A + B)'. 1 only when all inputs are 0.
- XOR (exclusive OR, A ⊕ B): 1 when the inputs are different. A ⊕ B = A·B' + A'·B.
NAND and NOR are called universal gates because any other gate can be built using only NAND gates (or only NOR gates).
Truth tables
A truth table lists every combination of inputs and the output. With n inputs there are 2n rows (2 inputs → 4 rows, 3 inputs → 8 rows).
| A | B | AND | OR | NAND | NOR | XOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
NOT: A = 0 → 1, A = 1 → 0.
De Morgan's laws
Law 1: (A·B)' = A' + B' — NOT of an AND equals OR of the NOTs.
Law 2: (A + B)' = A'·B' — NOT of an OR equals AND of the NOTs.
Proof by truth table: write columns for A, B, A·B, (A·B)', A', B', A' + B'. The columns (A·B)' and A' + B' are 1, 1, 1, 0 in every row, so they are equal. Law 2 is checked the same way.
Trick: break the bar over the whole expression, put a bar on each variable, and change · to + (or + to ·).
Logic circuits
A logic circuit joins gates so the output of one becomes the input of another. Every circuit matches a Boolean expression.
Example: X = A·B + C'. The circuit has an AND gate for A·B, a NOT gate for C, and an OR gate that joins the two results.
To draw a circuit from an expression: do the innermost brackets and NOTs first, then AND, then OR (just like BODMAS, NOT has the highest priority, then AND, then OR). To find the expression from a circuit: write the output of each gate, moving left to right.
Board exam focus
Expect: draw the truth table of a 2- or 3-input expression, prove De Morgan's law by truth table (3 marks), draw the circuit for an expression like (A + B)·C', write the expression of a given circuit.
Key formulas and definitions
- NOT: A' AND: A·B OR: A + B
- NAND: (A·B)' NOR: (A + B)' XOR: A ⊕ B = A·B' + A'·B
- De Morgan 1: (A·B)' = A' + B'
- De Morgan 2: (A + B)' = A'·B'
- Rows in a truth table = 2ⁿ
- Priority: NOT > AND > OR
Worked examples
1. Find the output of A·B + A' when A = 0, B = 1.
A·B = 0·1 = 0. A' = 1. Output = 0 + 1 = 1.
2. How many rows does the truth table of a 3-input expression have?
2³ = 8 rows.
3. Make the truth table of X = (A + B)'.
A=0,B=0: A+B=0 → X=1. A=0,B=1: 1 → 0. A=1,B=0: 1 → 0. A=1,B=1: 1 → 0. This is the NOR gate.
4. Prove (A + B)' = A'·B' using a truth table.
Rows (A,B): 00, 01, 10, 11. A + B: 0,1,1,1 → (A+B)': 1,0,0,0. A': 1,1,0,0; B': 1,0,1,0 → A'·B': 1,0,0,0. Both columns are 1,0,0,0, so the law is proved.
5. Simplify using De Morgan: (A'·B)'.
(A'·B)' = (A')' + B' = A + B'.
6. Draw (in words) the circuit for X = (A·B) + (B'·C) and find X when A=1, B=0, C=1.
Gates: AND1(A, B); NOT(B); AND2(B', C); OR(AND1, AND2). A·B = 0; B' = 1; B'·C = 1; X = 0 + 1 = 1.
Common mistakes
- Thinking OR means 'only one'. OR is 1 also when both inputs are 1; 'only one' is XOR.
- Applying De Morgan without changing the sign: (A·B)' is NOT A'·B'.
- Writing only 4 rows for 3 inputs. You need 2³ = 8.
- Doing OR before AND in an expression. AND has higher priority than OR.