Logic circuits and expressions

Combining gates, Boolean expressions, XOR, and the half adder.

F9.2Logic and computer systemsGCSE15 min

Covers OCR J277 2.4.1 Boolean logic · AQA 8525 3.4.2 Boolean logic · Edexcel 1CP2 1.3.1 Truth tables

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Logic gates and truth tables explained

One gate makes one small decision. Wire gates together, so that the output of one is the input of another, and you get a logic circuit that can make any decision at all, or even add numbers. This lesson reads and writes circuits, their Boolean expressions, and their truth tables, and ends by building the circuit that adds two bits.

A circuit and its expression

Q = (A AND B) OR (NOT C)

The circuit and the expression say the same thing: Q = (A AND B) OR (NOT C). To work out a circuit's truth table, work out each gate's output in a column of its own, then combine:

A	B	C	A AND B	NOT C	Q
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

The in-between columns are optional, but they stop mistakes.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def AND(a, b): return 1 if a and b else 0
def OR(a, b): return 1 if a or b else 0
def NOT(a): return 1 - a

print("A B C | A.B  NOT C | Q")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            ab = AND(a, b)
            nc = NOT(c)
            print(a, b, c, "|", ab, "   ", nc, "   |", OR(ab, nc))

Run this in the simulator

XOR

XOR, exclusive OR, gives 1 when the inputs are different, and 0 when they are the same:

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

It is OR without the case where both are 1. It can be built from the gates you already have: (A OR B) AND NOT (A AND B).

The top branch is 1 when at least one input is 1. The bottom branch is 1 unless both are 1. The last AND needs both branches, so only inputs that are different get through: that is XOR, which has a symbol of its own, an OR with a second curved line at the back.

Adding two bits

Look at what adding two single bits gives, from lesson F8.4: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10 in binary, which is 0 carry 1.

The sum bit is 1 when the inputs are different: that is XOR. The carry bit is 1 only when both are 1: that is AND. So two gates add two bits. This circuit is a half adder:

A half adder: S = A XOR B, C = A AND B

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def AND(a, b): return 1 if a and b else 0
def XOR(a, b): return 1 if a != b else 0

print("A B | carry sum")
for a in [0, 1]:
    for b in [0, 1]:
        print(a, b, "|  ", AND(a, b), "  ", XOR(a, b))

Run this in the simulator

A half adder has no input for a carry coming in, so the other columns use a full adder (challenge 1 builds one). Chain full adders together, one per bit, and they add whole 8-bit numbers: the adder you wrote in F8.4 is what the processor's gates do in the arithmetic logic unit, the ALU, of lesson F9.4.

From a problem to a circuit

To design a circuit, write the rule as an expression in words, then turn each word into a gate. "Beep if the robot is close to the wall and moving, or has bumped into something":

beep = (close AND moving) OR bumped

Each word of the rule becomes a gate. The brackets group close and moving, so they meet at the AND gate; the OR gate then lets a bump beep on its own, whatever the other two are.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def AND(a, b): return 1 if a and b else 0
def OR(a, b): return 1 if a or b else 0

forward(40)
for step in range(70):
    close = 1 if distance() < 40 else 0
    moving = 1
    hit = 1 if bumped() else 0
    if OR(AND(close, moving), hit) == 1:
        tone(880, 0.05)
    wait(0.1)
stop()

Run this in the simulator

The robot starts about 80 cm from the far edge of the mat, so it drives quietly for the first 5 seconds or so. Once the edge is under 40 cm away, close is 1 and it beeps on every step: 11 beeps before it stops, 28 cm short of the edge.

In the exam

Questions give a circuit and ask for its truth table or its Boolean expression, give an expression and ask you to draw the circuit, or describe a situation for you to turn into a circuit. Add a column for each gate's output when working out a truth table.

OCR 2.4.1

OCR asks you to combine AND, OR and NOT gates into logic diagrams, write the Boolean expression for a diagram, and complete truth tables for circuits with up to three inputs. XOR is not on J277.

AQA 3.4.2

AQA asks you to construct truth tables and simple logic circuits using NOT, AND, OR and XOR, with up to three inputs, and to write Boolean expressions for them. The half adder is a classic example.

Edexcel 1.3.1

Edexcel asks you to produce truth tables for logic statements with AND, OR and NOT, with up to three inputs, and to use them to solve problems.

Task: a half adder

Write AND(a, b) and XOR(a, b) as functions of 0s and 1s. XOR must be built from AND, OR and NOT functions you also write, as (A OR B) AND NOT (A AND B), not with !=. Print the half adder's truth table as four lines in the form A=1 B=1 carry=1 sum=0.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def AND(a, b): return 1 if a and b else 0
def OR(a, b): return 1 if a or b else 0
def NOT(a): return 1 - a

Challenges

A full adder adds three bits: A, B and a carry in. Build one from two half adders and an OR gate, and print its eight-row truth table.
Write the expression for "the LED is green if the battery is OK and the way is clear, or the robot is parked", and print its truth table.
Show that NOT (A AND B) is always the same as (NOT A) OR (NOT B) by printing both columns.

Past paper questions on this

Real exam questions that test this, each worked through with a program you can run.