IGCSE Computer Science · Area 2 · Algorithms, programming and logic

Boolean logic

Logic gates take binary inputs and produce a binary output, and this topic is about moving confidently between the four ways the same circuit can be described: the symbol, the function in words, the truth table and the logic expression. You need to know all six gates, build a truth table for a circuit, and write an expression from a circuit or a problem statement. The marks usually go on the gates with a bubble - NAND and NOR - and on forgetting that a circuit with three inputs needs eight rows, not four.

Not started

Syllabus coverage

  • Identify and use the standard symbols for the logic gates NOT, AND, OR, NAND, NOR and XOR (EOR)
  • Define and understand the functions of the logic gates
  • Use logic gates to create given logic circuits from a problem statement, a logic expression or a truth table
  • Complete a truth table from a problem statement, a logic expression or a logic circuit
  • Write a logic expression from a problem statement, a logic circuit or a truth table
  • NOT is a single-input gate; all of the other gates are limited to two inputs
  • Logic circuits are limited to a maximum of three inputs and one output
  • Circuits must be drawn for the statement given, without simplification
  • The output is the binary output produced from all of the possible binary inputs

Part of the IGCSE Computer Science syllabus 0478.

Boolean logic: the six gatesEach gate has one standard symbol and one Boolean expression. Learn both exactly as they are drawn and written.For a circuit, work out the output one gate at a time rather than trying to see the whole answer at once.ANDboth inputs 1A and B0 = off, 1 = onOReither input 1A or B0 = off, 1 = onNOTinverts the inputnot A0 = off, 1 = onNANDnot bothnot (A and B)0 = off, 1 = onNORneithernot (A or B)0 = off, 1 = onXORone or the other, not bothA xor B0 = off, 1 = onWork out the output gate by gate, writing the intermediate values down. Guessing the whole circuit at once is how marks are lost.
The six logic gates - AND, OR, NOT, NAND, NOR and XOR - drawn side by side with their standard symbols and their function in words, showing that NAND is AND with a circle on the output, NOR is OR with a circle on the output, and XOR has an extra curved line across its inputs.

Binary inputs, one output, and the six gates

A logic circuit takes one or more binary inputs - each input is either 0 or 1 - and produces a single binary output, which is also 0 or 1. Each logic gate in the circuit carries out one simple function on its inputs, and the gates are joined so that the output of one gate becomes an input to the next. The syllabus limits a circuit to a maximum of three inputs and one output.

There are six gates to know: NOT, AND, OR, NAND, NOR and XOR, which is also written EOR for exclusive OR. NOT is the only gate with a single input; every other gate takes exactly two inputs. NAND and NOR are the AND and OR functions with a NOT added on the end, which is where their names come from.

The behaviour of a gate can be written in words, drawn as a symbol, or listed in a truth table - a table that gives the output for every possible combination of inputs. Two inputs give four combinations, so four rows; three inputs give eight combinations, so eight rows. A circuit is completely described by its truth table, which is why examiners keep asking for one.

  • Every input is 0 or 1 and every output is 0 or 1; there are no other values.
  • NOT has one input; AND, OR, NAND, NOR and XOR each have two.
  • A circuit has at most three inputs and exactly one output.
  • Two inputs mean four rows in the truth table; three inputs mean eight rows.
NAND and NOR are the AND and OR symbols with a small circle on the output. The circle means NOT, so it reverses the output of the gate.

The six gates: symbols and functions

NOT is drawn as a triangle with a small circle at the pointed end, and it has one input. Its function is to invert the input: the output is 1 when the input is 0, and 0 when the input is 1.

AND is drawn with a flat back and a rounded front, like a capital D. Its output is 1 only when both inputs are 1, and 0 in every other case. OR is drawn with a curved input edge coming to a point at the output. Its output is 1 when either input is 1, or both are 1, and 0 only when both inputs are 0.

NAND is an AND symbol with a circle on the output, and its output is the exact opposite of AND: 0 only when both inputs are 1, and 1 in every other case. NOR is an OR symbol with a circle on the output, and its output is 1 only when both inputs are 0, and 0 in every other case.

XOR is drawn like OR but with a second curved line across the inputs. Its output is 1 when the two inputs are different, and 0 when they are the same. That is the whole difference between OR and XOR: when both inputs are 1, OR outputs 1 but XOR outputs 0.

GateInputsHow the symbol looksThe output is 1 when
NOT1A triangle with a small circle on the outputThe input is 0, because NOT always inverts its input
AND2Flat back, rounded front, like a capital DBoth inputs are 1
OR2Curved input edge coming to a point at the outputEither input is 1, or both are 1
NAND2An AND symbol with a circle on the outputEither input is 0, because the output is 0 only when both inputs are 1
NOR2An OR symbol with a circle on the outputBoth inputs are 0
XOR2An OR symbol with a second curved line across the inputsThe two inputs are different
Learn the bubble. An AND with a bubble is NAND and an OR with a bubble is NOR, and the bubble flips every output in that gate's truth table.

Truth tables for the six gates

A truth table lists every combination of inputs and the output for each one. For two inputs there are four combinations, and the convention is to count up in binary: 0 0, then 0 1, then 1 0, then 1 1. Writing the rows in that order means you can never repeat a combination or leave one out.

The table below gives all six gates at once. Read down the column for the gate you want and check it against the function in words: AND is 1 only in the last row, OR is 1 in every row except the first, XOR is 1 in the two middle rows because those are the rows where the inputs are different, NAND is the reverse of AND, and NOR is the reverse of OR.

NOT is shown as its own column, because it has only one input. In every row, the NOT A column holds the opposite of A.

ABNOT AA AND BA OR BA NAND BA NOR BA XOR B
00100110
01101101
10001101
11011000
Two facts worth memorising: NAND outputs 0 in exactly one row, where both inputs are 1, and NOR outputs 1 in exactly one row, where both inputs are 0.

Building a truth table for a circuit

A circuit with more than one gate has intermediate outputs, and the truth table for it needs a column for each of them. Work in stages and the final column looks after itself.

Step 1: count the inputs. Three inputs mean 2 to the power 3 = 8 rows, and two inputs mean 2 to the power 2 = 4 rows. Step 2: write the input combinations in binary counting order, so every combination appears exactly once. Step 3: add a column for the output of each gate, working through the circuit from the inputs towards the output. Step 4: fill the final column from the last gate by reading across its two input columns.

Here is the method on the circuit for Q = (A AND B) OR NOT C. The three inputs A, B and C give eight rows. The first gate is A AND B and the second is NOT C, so the table needs a column for each of those before the Q column. The last column is 1 in five of the eight rows, which is worth knowing: it means the circuit is on most of the time.

ABCA AND BNOT CQ = (A AND B) OR NOT C
000011
001000
010011
011000
100011
101000
110111
111101
Add the intermediate columns even when the question only asks for the output. Working out A AND B and NOT C first is how you fill the last column without guessing, and the intermediate columns can still earn marks if the final one goes wrong.

Writing a logic expression from a circuit

To turn a circuit into an expression, name the output of every gate and work from the inputs towards the output. Write the expression for the first gate, then use it as an input to the next gate, putting brackets round each sub-expression so the order is clear.

Here it is on a circuit. Inputs A and B go into an OR gate, input C goes into a NOT gate, and the outputs of those two gates go into an AND gate whose output is Q. The OR gate gives (A OR B), the NOT gate gives NOT C, and the AND gate combines them, so Q = (A OR B) AND NOT C.

Brackets are not decoration. (A AND B) OR C is a different circuit from A AND (B OR C): when A is 0, B is 0 and C is 1, the first gives 1 and the second gives 0. If a circuit has three gates in a chain, your expression will have three parts, and each one must be bracketed so a marker can see the structure.

Cambridge writes the expression using the gate names in capitals, as in Q = (A OR B) AND NOT C. Some textbooks use shorthand symbols instead of the gate names - recognise them if you meet them, but write the gate names in the exam.

Write the expression gate by gate, in the order the signals travel. An expression written straight off the final gate, with the intermediate gates skipped, is where the brackets go missing.

From a problem statement to a circuit

A problem statement describes what a circuit must do in words, and your job is to find the gates that do it. Look for the clue words: and means an AND gate, or means an OR gate, not or is not means a NOT gate, exactly one of or either but not both means XOR, not both means NAND, and neither means NOR.

Take a car warning light that comes on when the engine is running and the driver's seat belt is not fastened. Let E = 1 mean the engine is running and S = 1 mean the seat belt is fastened. The light comes on when E is 1 AND S is 0, so the circuit has E into an AND gate and S into a NOT gate, with the output Q = E AND NOT S. Reading the statement back against the circuit is the check: with the engine off the light stays off, and with the belt fastened the light stays off too.

One rule catches people out. Circuits must be drawn for the statement given, without simplification. If a statement asks for a warning that comes on when A and B are both on, or when A and C are both on, you draw two AND gates and one OR gate. You do not tidy it up into A AND (B OR C), even though that circuit would behave in exactly the same way. Draw what the statement says.

When the question gives you a truth table and asks for the circuit, work from the rows where the output is 1. Each of those rows gives one combination of inputs joined by AND gates, and the rows are then joined by an OR gate. A truth table with the output 1 in two rows therefore becomes two AND gates feeding one OR gate.

Clue words decide the gate: and -> AND, or -> OR, not -> NOT, exactly one -> XOR, not both -> NAND, neither -> NOR.

Key terms you must be able to define

Logic gate
A component of a logic circuit that performs a single logical function on one or two binary inputs and produces one binary output.
Binary input
An input to a logic circuit that can only be 0 or 1. Every input and every output in this topic is binary.
Truth table
A table that gives the output of a gate or circuit for every possible combination of binary inputs. Two inputs give four rows; three inputs give eight rows.
NOT gate
A single-input gate that inverts its input: the output is 1 when the input is 0, and 0 when the input is 1. Its symbol is a triangle with a circle on the output.
AND gate
A two-input gate whose output is 1 only when both inputs are 1, and 0 in every other case.
OR gate
A two-input gate whose output is 1 when either input is 1, or when both are 1, and 0 only when both inputs are 0.
NAND gate
An AND gate followed by NOT: the output is 0 only when both inputs are 1, and 1 in every other case. Its symbol is an AND symbol with a circle on the output.
NOR gate
An OR gate followed by NOT: the output is 1 only when both inputs are 0, and 0 in every other case. Its symbol is an OR symbol with a circle on the output.
XOR gate (EOR)
The exclusive OR gate: the output is 1 when the two inputs are different and 0 when they are the same. Its symbol is an OR symbol with a second curved line across the inputs.
Bubble
The small circle drawn on the output of the NOT, NAND and NOR symbols. It means the output of the gate is inverted.
Logic circuit
One or more logic gates connected together. On this syllabus a circuit has a maximum of three inputs and one output.
Logic expression
A statement of what a circuit does, written with the gate names, for example Q = (A OR B) AND NOT C.

Applied to real systems

Cambridge sets 0478 in systems you already use - a phone, a school network, a supermarket till, a website, a bank. Use these as models for how to apply the theory to a context you have not seen before, then write your own.

In a car

The light comes on when the engine is running and the seat belt is not fastened, so the engine signal E goes into an AND gate and the seat belt signal S goes into a NOT gate. The output is Q = E AND NOT S. Read the statement back against the circuit: with the engine off the light is off whatever the belt is doing, and with the belt fastened the light is off too, because the NOT gate outputs 0 and an AND gate needs both inputs at 1.

In a house alarm

The alarm sounds when a sensor is active and the system is armed. With two sensors, the two sensor signals go into an OR gate, because either one being active should trigger the alarm, and the output of that OR gate goes into an AND gate with the armed signal. The alarm only sounds when the armed signal is 1 and at least one sensor is 1, so an active sensor on a disarmed system does nothing.

At a vending machine

The machine dispenses an item when the correct money has been inserted and an item button has been pressed, which is a single AND gate: both inputs must be 1. If the machine also had to check that it is not already dispensing, that signal would pass through a NOT gate before joining the AND gate, and the truth table for the circuit would show that pressing a button without paying, or paying without pressing a button, never dispenses anything.

At an automatic door

The door opens when the sensor inside the shop detects a person or the sensor outside detects a person, so the two sensor signals go into an OR gate whose output drives the motor. The output is 1 for three of the four possible combinations of the two sensors and 0 only when neither sensor detects anything, which is the behaviour the shop wants.

On a factory machine

A machine starts only when the start button is pressed and the guard is closed and the power is on. That is three conditions, and an AND gate takes only two inputs, so the circuit needs two AND gates: the start button and the guard signal go into the first gate, and its output goes into the second gate with the power signal. The output is Q = (S AND G) AND P, and it is 1 in exactly one row of the eight-row truth table.

Flashcards

Click a card to flip it. Mark honestly — the tracker uses this.

Q1How many inputs does a NOT gate have, and how many do the other five gates have?
NOT has one input. AND, OR, NAND, NOR and XOR each have exactly two.
Q2When is the output of an AND gate 1?
Only when both inputs are 1. In every other case the output is 0.
Q3When is the output of an OR gate 0?
Only when both inputs are 0. If either input is 1, or both are, the output is 1.
Q4What is the difference between an OR gate and an XOR gate?
OR gives 1 when both inputs are 1; XOR gives 1 only when the inputs are different, so it gives 0 when both are 1.
Q5When is the output of a NAND gate 0?
Only when both inputs are 1. In the other three rows the output is 1, which is the opposite of AND.
Q6When is the output of a NOR gate 1?
Only when both inputs are 0. In every other row the output is 0.
Q7How many rows does the truth table for a three-input circuit need, and why?
Eight rows, because there are 2 to the power 3 = 8 different combinations of three binary inputs.
Q8How should the input combinations be listed in a truth table?
In binary counting order: 00, 01, 10, 11 for two inputs and 000 up to 111 for three, so no combination is missed or repeated.
Q9What does the small circle on the output of a NAND or NOR symbol mean?
It means NOT, so the output of the gate is inverted: NAND is AND with its output reversed and NOR is OR with its output reversed.
Q10A circuit has A and B into an OR gate, and the output of that gate goes into an AND gate with C. Write the logic expression.
Q = (A OR B) AND C. The brackets show that the OR gate's output is worked out first.
Q11Which gate does the phrase 'exactly one of the two switches is on' describe?
XOR, because its output is 1 when the two inputs are different, which is the case when only one of them is on.
Q12What does the syllabus say about simplifying a logic circuit you have been asked to draw?
Do not simplify it. Draw the circuit for the statement given, using every gate the statement implies.
0 of 12 marked as known

Exam-style questions

7 questions, 20 marks. Write your answer, then reveal the mark scheme and tick each point you actually made. Answering honestly here is what makes the rest of the site useful.

StateAO11 mark
A logic circuit has three inputs. State how many rows the truth table for this circuit must have.

Mark scheme — tick each point you actually made

Examiner tip: The number of rows is 2 to the power of the number of inputs: 4 rows for two inputs, 8 rows for three. Say the number, and the reason if the question is worth a mark for it.
IdentifyAO12 marks
Identify the logic gate described in each case. (i) The output is 1 only when both inputs are 0. (ii) The output is 1 when the two inputs are different.

Mark scheme — tick each point you actually made

Examiner tip: 'Only when both inputs are 0' is the single row where NOR outputs 1. 'Different' is the key word for XOR: it outputs 1 in the two rows where the inputs differ.
StateAO22 marks
In a circuit, input A and input B are connected to an XOR gate. State the output of the gate when A = 1 and B = 1, and state the output when A = 0 and B = 1.

Mark scheme — tick each point you actually made

Examiner tip: XOR is the 'different' gate: different inputs give 1, the same inputs give 0. Do not fall back on the OR rule, which would give 1 for both of these.
StateAO23 marks
A circuit has three inputs A, B and C. Inputs A and B are connected to an AND gate, input C is connected to a NOT gate, and the outputs of those two gates are connected to an OR gate whose output is Q. State the value of Q for each of these combinations. (i) A = 0, B = 1, C = 0 (ii) A = 1, B = 1, C = 0 (iii) A = 1, B = 0, C = 1

Mark scheme — tick each point you actually made

Examiner tip: Work out the output of each gate separately for each row before you touch the final gate. Write the intermediate values down; guessing the final answer is how these marks are lost.
DemonstrateAO24 marks
A circuit has three inputs A, B and C. Inputs A and B are connected to an OR gate, input C is connected to a NOT gate, and the outputs of those two gates are connected to an AND gate whose output is Q. Demonstrate how the output Q is derived from the inputs, and give the logic expression for this circuit.

Mark scheme — tick each point you actually made

Examiner tip: Name the output of each gate in turn and then combine them. The brackets round A OR B are what show the marker that the OR is worked out before the AND.
GiveAO25 marks
A circuit has three inputs A, B and C. Inputs A and B are connected to an XOR gate, the output of the XOR gate and input C are connected to an AND gate, and the output of the AND gate is Q. Give the value of Q for each of these combinations: (i) A = 0, B = 1, C = 1 (ii) A = 1, B = 0, C = 1 (iii) A = 1, B = 1, C = 0 (iv) A = 0, B = 0, C = 1. State also how many of the eight rows of the truth table have Q = 1.

Mark scheme — tick each point you actually made

Examiner tip: Work out the XOR output first for every row, then apply the AND. A question like this is testing whether you can handle an intermediate output, which is exactly what the extra column in a truth table is for.
ExplainAO23 marks
A machine must switch on only when all three of these conditions are met: the start button has been pressed (S), the guard is closed (G) and the power is on (P). Explain how logic gates could be used to produce the output that switches the machine on, and write the logic expression for it.

Mark scheme — tick each point you actually made

Examiner tip: Three conditions mean two AND gates, because no gate except NOT has more than two inputs. Say why the second gate is needed - that is the mark most candidates leave behind.

Exam technique for this topic

  • Learn all six symbols, including which ones carry a bubble. NAND and NOR are drawn as AND and OR with a circle on the output, and that circle is the only difference between them and the gate they are named after.
  • Count the rows before you start writing: two inputs mean four rows and three inputs mean eight rows. List the input combinations in binary counting order (00, 01, 10, 11) so that no combination is missed or repeated.
  • For a circuit with more than one gate, add a column to your truth table for the output of every gate. Even if the final column goes wrong you can still earn marks for the intermediate ones, and it stops you guessing the output.
  • Do not simplify. The syllabus asks for the circuit for the statement given, so draw every gate the statement implies, even when a smaller circuit would behave in the same way.
  • Match the clue words to the gate: and -> AND, or -> OR, not -> NOT, exactly one -> XOR, not both -> NAND, neither -> NOR. Most problem statement questions are solved by that list alone, and when you write the expression from the circuit, bracket the output of every gate - Q = (A AND B) OR C and Q = A AND (B OR C) are different circuits.

Why students lose marks here

A student wroteA student wrote: 'A NAND gate gives an output of 1 when both of its inputs are 1.'
Why it loses marksThis is the AND gate's function, not NAND's. The student has ignored the circle on the output of the NAND symbol, and that circle is a NOT, which reverses the output of the gate.
The answer that scoresA NAND gate outputs 0 only when both inputs are 1, and 1 in the other three rows of its truth table, which makes it the exact opposite of AND. The circle on the output of the symbol is the NOT that reverses AND's output. For inputs 0 and 1, an AND gate gives 0 and a NAND gate gives 1.
A student wroteA student wrote: 'An XOR gate gives an output of 1 when both of its inputs are 1, because it works like OR.'
Why it loses marksThe student has read XOR as if it were OR. XOR is the exclusive OR, and the word exclusive is the whole point: it excludes the case where both inputs are 1.
The answer that scoresAn XOR gate outputs 1 when the two inputs are different, so it gives 1 for inputs 0 and 1 and for inputs 1 and 0, and 0 when both inputs are 1 or both are 0. An OR gate, by contrast, outputs 1 when both inputs are 1. The extra curved line across the inputs of the XOR symbol is what marks this difference.
A student wroteA student wrote: 'A circuit with three inputs needs six rows in its truth table, one for each input plus one for each combination.'
Why it loses marksThe number of rows is not related to the number of inputs in that way. Every combination of three binary inputs must appear, and there are 2 to the power 3 = 8 of them.
The answer that scoresA truth table needs one row for every possible combination of the inputs: 2 to the power 3 = 8 rows for three inputs, and 2 to the power 2 = 4 rows for two inputs. Write them in binary counting order, 000, 001, 010, 011, 100, 101, 110, 111, so that every combination appears exactly once.
A student wroteA student wrote: 'I used one AND gate instead of two, because the two circuits do the same thing.'
Why it loses marksThe syllabus requires the circuit to be drawn for the statement given, without simplification. A neat circuit that behaves in the same way is still not the circuit the question asked for, and the marks are for the gates the statement implies.
The answer that scoresCircuits must be drawn for the statement given, without simplification. If the statement says the output is 1 when A and B are both on, or when A and C are both on, the circuit is two AND gates feeding an OR gate. Simplifying that to A AND (B OR C) would give the same output but is not the circuit the statement describes.
A student wroteA student wrote the expression for a circuit as: Q = A AND B OR C
Why it loses marksWithout brackets the expression can be read in two ways, and the two readings are different circuits: (A AND B) OR C gives 1 when A is 0, B is 0 and C is 1, while A AND (B OR C) gives 0 for the same inputs.
The answer that scoresBracket the output of every gate so the order is unambiguous. If the circuit has A and B into an AND gate and the output of that gate into an OR gate with C, the expression is Q = (A AND B) OR C. If the circuit has B and C into an OR gate and the output of that gate into an AND gate with A, it is Q = A AND (B OR C).