Year 10 · Computer Science · Autumn 2 · Data transmission and Boolean logic

Logic gates, truth tables and circuits

Exam practicePresent ▶

What this lesson covers

10.1 The six logic gates

Cambridge IGCSE Computer Science 0478 · Topic 10: Boolean logic · Paper 2

10.2 Truth tables

Cambridge IGCSE Computer Science 0478 · Topic 10: Boolean logic · Paper 2

10.3 Expressions and circuits

Cambridge IGCSE Computer Science 0478 · Topic 10: Boolean logic · Paper 2

You will learn to

State the rule, symbol and truth table for NOT, AND, OR, NAND, NOR and XOR.
Calculate the number of rows a truth table needs: 2 to the power of the number of inputs.
Write a logic expression from a circuit, and draw a circuit from an expression.
Complete a truth table for a three-input circuit, using working columns.

Success criteria

I can draw all six gates and fill in their truth tables from memory.
I can list the 8 input rows for three inputs in order, from 000 to 111.
I can turn a past-paper circuit into an expression and a truth table.

The syllabus points for these sections

State the rule for each gate: NOT, AND, OR, NAND, NOR, XOR.
Draw the standard symbol for each gate.
Complete the truth table for each gate.
Recognise a gate from its truth table.
Work out how many rows a truth table needs.
List all input combinations for 3 inputs in the standard order.
Use working columns to complete a truth table for a circuit.
Write a logic expression from a problem statement.
Draw a logic circuit from an expression, without simplifying.
Write a logic expression from a circuit.
Write a logic expression from a truth table using the 1 rows.

Key words

Say each word, then read what it means. Every one is in the glossary too.

Boolean logic: Logic that uses only two values, 1 (true, on) and 0 (false, off).
Logic gate: An electronic component that takes one or two inputs and gives one output by a fixed rule.
Truth table: A table that lists every possible input combination and the output for each one.
Logic circuit: Two or more logic gates joined together to give one output.
Logic expression: A written description of a circuit using gate names, such as X = A AND NOT B.
NOT: A one-input gate whose output is the opposite of its input; also called an inverter.
AND: A gate whose output is 1 only when both inputs are 1.
OR: A gate whose output is 1 when at least one input is 1.
NAND: NOT AND: the output is 0 only when both inputs are 1.
NOR: NOT OR: the output is 1 only when both inputs are 0.
XOR (EOR): Exclusive OR: the output is 1 when the two inputs are different.
Input: A signal going into a gate or circuit, such as a sensor reading of 1 or 0.
Output: The single result signal that comes out of a gate or circuit.
Working column: An extra truth-table column holding the output of one gate inside a circuit.
Sum of products: An expression made by AND-ing the inputs of each row with output 1, then OR-ing those groups together.

The explanation

Read it here, or open the study page below to go one step at a time with things to try.

10.1 The six logic gates

1 and 0: the language of logic

Boolean logic works with only two values: 1 and 0. 1 means on, true or yes. 0 means off, false or no.

A logic gate is a tiny electronic switch inside a chip. It takes one or two inputs and gives one output.

A truth table lists every possible input combination and the output for each one. It is the full description of what a gate or circuit does.

e.g.Example

A door sensor: door open = 1, door closed = 0. A light: on = 1, off = 0. A gate decides whether the light goes on, using the sensor values.

?Why?

Computers use 1 and 0 because an electric signal is easy to read as two states, high voltage or low voltage. Two states leave little room for error.

NOT gate: flips the input

NOT has one input. The output is the opposite of the input.

Input 1 gives output 0. Input 0 gives output 1. It is also called an inverter.

Symbol: a triangle with a small circle at the tip. The small circle always means "flip it".

A	Q = NOT A
0	1
1	0

e.g.Example

A night light: X = NOT L, where L = 1 when it is light outside. Daytime: L = 1, so X = 0 (light off). Night: L = 0, so X = 1 (light on).

AND and OR

AND: the output is 1 only when input A and input B are both 1. Think of two switches in a row: both must be closed for the bulb to light.

OR: the output is 1 when A or B is 1, or both are. Think of two switches side by side: either one lights the bulb.

AND has a flat back and a round front. OR has a curved back and a pointed front.

A	B	A AND B	A OR B
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

e.g.Example

A metro ticket gate opens (1) only if the card is valid AND the card has credit → AND. A shop bell rings (1) if the front door OR the back door opens → OR.

NAND and NOR: AND and OR, then flipped

NAND means NOT AND. Work out AND, then flip the answer. The output is 0 only when both inputs are 1.

NOR means NOT OR. Work out OR, then flip the answer. The output is 1 only when both inputs are 0.

Their symbols are the AND and OR symbols with the small "flip" circle on the output.

A	B	A NAND B	A NOR B
0	0	1	1
0	1	1	0
1	0	1	0
1	1	0	0

?Why?

Put the NAND column next to the AND column and every value is flipped. The same is true for NOR and OR. This is a quick way to check your table.

!Watch out

NAND is not "NOT A AND NOT B". You do the AND first, then flip the single answer.

XOR: one or the other, not both

XOR (exclusive OR, also written EOR) gives 1 when the inputs are different.

If both inputs are the same, both 0 or both 1, the output is 0.

Symbol: the OR symbol with an extra curved line behind it.

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

e.g.Example

A landing light with a switch at the top and bottom of the stairs. Flip either switch and the light changes. This is XOR. Both down (0, 0) → off. One up (0, 1) → on. Both up (1, 1) → off.

!Watch out

OR and XOR only differ in the last row. When A = 1 and B = 1, OR gives 1 but XOR gives 0.

All six symbols together

Learn to draw these exactly. Examiners mark the shape, so a sloppy OR that looks like an AND loses marks.

All gates except NOT have exactly two inputs. Every gate has one output.

Notice the patterns. A small circle means "flip". An extra curved line at the back means XOR.

!Watch out

Do not draw a three-input AND or OR gate. At IGCSE each gate has at most two inputs, so A AND B AND C needs two AND gates.

There is a diagram for this step in the IGCSE library.

10.2 Truth tables

How many rows?

Each input can be 0 or 1. So every new input doubles the number of combinations.

1 input → 2 rows. 2 inputs → 4 rows. 3 inputs → 8 rows.

In the formula, n is the number of inputs and the answer is the number of rows (not counting the heading row).

e.g.Example

rows = 2ⁿ n = 2 inputs (A, B): 2² = 2 × 2 = 4 rows n = 3 inputs (A, B, C): 2³ = 2 × 2 × 2 = 8 rows

?Why?

With 8 rows you have tried every possible situation, so nothing can surprise the circuit later.

Filling in the inputs: count in binary

Write the input rows as the binary numbers 0 to 7. This way you never miss or repeat a row.

Column C (on the right) changes every row: 0, 1, 0, 1…

Column B changes every 2 rows: 0, 0, 1, 1… Column A changes every 4 rows: 0, 0, 0, 0, 1, 1, 1, 1.

Row	A	B	C
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

!Watch out

Exam truth tables already show the inputs in this order. Keep the same order in your own tables, or the examiner cannot match your rows.

Working columns for a 3-input circuit

For a circuit with more than one gate, add a working column for the output of each gate. Fill these in first.

Then use the working columns as the inputs to the final gate.

Example: `X = (A AND B) OR NOT C`. Working columns: P = A AND B, and R = NOT C. Then X = P OR R.

A	B	C	P = A AND B	R = NOT C	X = P OR R
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

e.g.Example

Row A = 1, B = 1, C = 1: P = 1 AND 1 = 1 R = NOT 1 = 0 X = 1 OR 0 = 1

?Why?

Each working column needs only one gate rule. Small steps make mistakes rare, and the examiner can often still give you marks for the working.

10.3 Expressions and circuits

From a statement to an expression

A logic expression describes a circuit in words, like `X = (A AND B) OR NOT C`.

Read the statement and turn each condition into a letter = 1 or letter = 0. "is on" or "is open" means the letter itself. "is off" or "is not" means NOT and the letter.

Join the conditions with the words the statement uses: "and" → AND, "or" → OR. Use brackets to keep each group together.

e.g.Example

Statement: a garden pump P switches on if the soil is dry (D = 1) and it is not raining (R = 0), or if the timer is on (T = 1). soil is dry → D not raining → NOT R timer is on → T Expression: P = (D AND NOT R) OR T

!Watch out

"R = 0" in a statement means you must write NOT R. Writing R on its own is the opposite of what the statement says.

From an expression to a circuit

Draw one gate for every operator in the expression. Start with the brackets, then work outwards to the final gate.

Every NOT is its own gate. NAND, NOR and XOR are drawn as single gates, not built from others.

Draw exactly what is written. Do not simplify, even if you can see a shorter circuit. Label every input and the output.

e.g.Example

X = (A AND B) OR NOT C Operators: AND, NOT, OR → 3 gates 1. A and B go into an AND gate. 2. C goes into a NOT gate. 3. The AND output and the NOT output go into an OR gate. 4. The OR output is X.

?Why?

Cambridge marks one gate at a time, checking each gate has the right inputs. A simplified circuit has different gates, so it loses marks even if it works.

!Watch out

Every gate except NOT needs exactly two inputs. If one input, such as B, feeds two gates, branch its wire and mark the join with a dot.

From a circuit to an expression

Start at the inputs on the left. Write the expression for the first gates' outputs.

Move right one gate at a time. Put each earlier part in brackets and join it with the next gate's name.

Finish at the output on the right.

A	B	C	A NOR B	B AND C	X
0	0	0	1	0	1
0	0	1	1	0	1
0	1	0	0	0	0
0	1	1	0	1	1
1	0	0	0	0	0
1	0	1	0	0	0
1	1	0	0	0	0
1	1	1	0	1	1

e.g.Example

Circuit: A and B go into a NOR gate. B and C go into an AND gate. Both outputs go into an OR gate, output X. NOR gate → (A NOR B) AND gate → (B AND C) OR gate → X = (A NOR B) OR (B AND C)

!Watch out

Brackets matter. Without them, `A NOR B OR B AND C` could be read in several ways. Always put each gate's output in brackets.

From a truth table to an expression

Look only at the rows where the output is 1.

For each of those rows, write the three inputs joined by AND. Put NOT in front of any input that is 0 in that row.

Then join all these groups with OR. This is called sum of products. It is long, but always correct.

Try the toy: type the final expression for X from the example. Its truth table should match the one below.

A	B	C	X
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

e.g.Example

Output is 1 in three rows: A=0, B=1, C=1 → (NOT A AND B AND C) A=1, B=0, C=1 → (A AND NOT B AND C) A=1, B=1, C=0 → (A AND B AND NOT C) X = (NOT A AND B AND C) OR (A AND NOT B AND C) OR (A AND B AND NOT C)

?Why?

Each bracket is 1 for exactly one row and 0 for every other row. OR-ing them gives 1 in exactly the rows you need.

There is something to try for this step in the IGCSE library.

Study it

Open the study page and go one step at a time.

Computer Science topic 2

The steps for this lesson

Topic 9, step 2: NOT, AND, OR (Play with logic gates)
Topic 9, step 4: Truth tables (Rows in a truth table)
Topic 1, step 6: Switches → logic → maths (Logic gates as arithmetic)

Try it

The maths

Symbols first, then the words, then the equation. Change the numbers to try your own.

Build it

Tinkercad · Intermediate

Logic gates

Two buttons go in, AND, OR and XOR come out. First with blocks, then in C++, then with real logic-gate chips and no code at all.

Check yourself

One question at a time. The reason shows after each answer.

Saved on this device.