Boolean Algebra, Logic Gates and Karnaugh Maps
Boolean algebra is the mathematics of logical (TRUE/FALSE, 1/0) values, built from the operators AND, OR and NOT (plus the derived gates XOR, NAND and NOR), and it underpins how digital logic circuits and processor hardware are built and simplified. A logic gate is a component that outputs a single Boolean value based on its inputs, according to a truth table; NAND and NOR are described as universal gates because either one alone can be combined to build any other gate. Boolean expressions can be simplified either algebraically, using laws such as De Morgan's laws, or visually, using a Karnaugh map (K-map), which arranges a truth table's outputs in a grid ordered so that any two adjacent cells differ in only one variable, letting groups of 1s sized in powers of two (1, 2, 4, 8) be circled to read off a minimal expression.
Before you start
Make sure you're comfortable with these topics first:
Method
- Learn the truth table for each gate (AND, OR, NOT, NAND, NOR, XOR) exactly, including that NAND is AND-then-NOT and NOR is OR-then-NOT.
- Learn the core Boolean laws (identity, complement, commutative, associative, distributive, and De Morgan's laws: NOT(A AND B) = (NOT A) OR (NOT B), and NOT(A OR B) = (NOT A) AND (NOT B)) before attempting an algebraic simplification.
- Simplify an expression algebraically by factorising common terms, then applying the complement law (X AND NOT X = 0, X OR NOT X = 1) and identity law (X AND 1 = X, X OR 0 = X) to eliminate terms, naming the law used at each step.
- To build a Karnaugh map, write the truth table outputs into a grid whose row and column headings are ordered in Gray code (e.g. 00, 01, 11, 10 for two variables), so adjacent cells always differ by only one variable.
- Circle the largest possible groups of 1s in the map, where every group's size is a power of two (1, 2, 4, 8...) and groups may wrap around the edges of the map and may overlap each other.
- For each group, write down only the variable(s) that stay constant (the same 0 or 1) across every cell in that group, dropping any variable that changes within the group, then OR the resulting terms together for the final simplified expression.
- Check the simplified expression against the original truth table for at least two rows, to confirm the simplification has not changed the logic.
Worked example
Simplify the Boolean expression X = (A AND B) OR (A AND NOT B) OR (NOT A AND B) using Boolean algebra laws, showing each law you apply.
- Write the expression using algebra notation: X = AB + AB' + A'B.
- Group the first two terms and factorise A out, using the distributive law: AB + AB' = A(B + B').
- Apply the complement law, B + NOT B = 1, so A(B + B') = A x 1 = A. The expression is now X = A + A'B.
- Apply the OR-distributive law to expand A + A'B as (A + A')(A + B).
- Apply the complement law A + NOT A = 1, so (A + A')(A + B) = 1 x (A + B) = A + B.
- Final answer: X simplifies to A + B (this can be checked directly: the original expression is TRUE for every row of the truth table where A is TRUE or B is TRUE, and FALSE only when A and B are both FALSE, which is exactly what A + B gives).
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1Complete the truth table row for A=1, B=0 for the expression A NAND B (state the single output value).Show answer
Answer: 1 (NAND is the complement of AND; A AND B = 1 AND 0 = 0, so NAND = NOT 0 = 1).
Q2State the Boolean law shown by: NOT (A AND B) = (NOT A) OR (NOT B).Show answer
Answer: De Morgan's law (specifically, De Morgan's law for AND).
Q3Simplify the Boolean expression Y = A AND (A OR B) using the absorption law, and state the simplified result.Show answer
Answer: Y = A (the absorption law: A AND (A OR B) always equals A, since if A is TRUE the whole expression is TRUE regardless of B, and if A is FALSE the whole expression is FALSE regardless of B).
Q4A half adder has inputs A and B, and outputs Sum and Carry, where Sum = A XOR B and Carry = A AND B. State the values of Sum and Carry when A=1 and B=1.Show answer
Answer: Sum = 0 (1 XOR 1 = 0) and Carry = 1 (1 AND 1 = 1), representing the binary result 1+1=10.
Q5State why NAND is described as a 'universal' logic gate.Show answer
Answer: Because any other logic gate (AND, OR, NOT, NOR, XOR and so on) can be built by connecting NAND gates together alone, so a circuit can, in principle, be constructed entirely from NAND gates.
Q6A 3-variable Karnaugh map orders its BC column headings as 00, 01, 11, 10, rather than 00, 01, 10, 11. Explain why.Show answer
Answer: So that every pair of horizontally adjacent columns (including the wrap-around from the last column back to the first) differs in only one variable; ordering them 00, 01, 11, 10 (Gray code order) achieves this, whereas 00, 01, 10, 11 would make the middle two columns differ in both variables at once.
Q7State how many variables are removed (dropped) from a Boolean term formed by a Karnaugh map grouping of two adjacent 1s, compared with writing the two cells as two separate minterms.Show answer
Answer: One variable is dropped from the term, because a group of two adjacent cells always differs in exactly one variable, which is therefore not constant across the group and so does not appear in the simplified term.
Q8Evaluate the Boolean expression NOT(A OR B) for A = FALSE and B = FALSE.Show answer
Answer: TRUE (A OR B = FALSE OR FALSE = FALSE, so NOT FALSE = TRUE).
Exam-style questions
Written in the style of a A Level Computer Science exam paper, with a full mark scheme.
Use a Boolean law to simplify the expression Z = (P OR Q) AND (P OR NOT Q), stating the law used at each step.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 3 available
The Boolean function F(A,B,C) has the truth table below (inputs A, B, C; output F). A B C | F 0 0 0 | 0 0 0 1 | 1 0 1 0 | 0 0 1 1 | 1 1 0 0 | 0 1 0 1 | 1 1 1 0 | 1 1 1 1 | 1 Draw a 3-variable Karnaugh map for F, with rows A = 0, 1 and columns BC ordered 00, 01, 11, 10. Identify the largest valid groupings of 1s, and state the fully simplified Boolean expression for F.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
A logic circuit currently uses one OR gate and two NOT gates to compute the expression (NOT A) OR (NOT B). A technician wants to rebuild the circuit using only NAND gates. Use De Morgan's law to rewrite (NOT A) OR (NOT B) as a single NAND expression, showing your working.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 4 available
See real A Level Computer Science past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the boolean algebra, logic gates and karnaugh maps worksheet pack - 11 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on boolean algebra, logic gates and karnaugh maps, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.