Logic gates and truth tables

AND, OR and NOT, their symbols and truth tables, and a robot decision as a circuit.

F9.1Logic and computer systemsGCSE15 min

Inside every processor are billions of tiny circuits called logic gates. Each takes one or two inputs that are on or off, 1 or 0, and produces an output that is on or off. Put enough of them together and you get a computer. This module goes inside BugBot's processor, and it starts with the gates.

AND, OR and NOT

• AND gives 1 only when both inputs are 1.
• OR gives 1 when at least one input is 1.
• NOT has one input and gives the opposite.

These are the same and, or and not you used in if statements in lesson F2.3. A processor makes every decision out of gates like these.

Truth tables

A truth table lists the output for every possible combination of inputs. Two inputs have four combinations:

A program can print a truth table, working out every row itself:

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

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

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

def NOT(a):
    return 1 - a

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

Run this in the simulator

The two nested loops try every combination, the way a truth table's rows do. Each gate is a function: two bits in, one bit out.

A robot decision as a circuit

BugBot should only drive when its battery is OK and the way is not blocked:

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

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

def NOT(a):
    return 1 - a

battery_ok = 1 if battery() > 20 else 0
blocked = 1 if distance() < 25 else 0
drive = AND(battery_ok, NOT(blocked))
print("battery OK:", battery_ok, " blocked:", blocked, " drive:", drive)
if drive == 1:
    forward(50, distance=20)

Run this in the simulator

Every input to the circuit is a sensor turned into a 1 or 0, and the output decides what the motors do. That is exactly how simple control circuits in real machines work, with no program at all.

Three inputs

With three inputs there are 2 × 2 × 2 = 8 combinations, so a truth table has 8 rows. With n inputs, it has 2 to the power n rows.

# 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

print("A B C | (A AND B) OR C")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            print(a, b, c, "|", OR(AND(a, b), c))

Run this in the simulator

Task: truth tables

Write AND(a, b), OR(a, b) and NOT(a) as functions that take and return 0 or 1. Print the truth table for A AND (NOT B), one row per line in the form A=0 B=1 Q=0, trying every combination with loops.

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

def AND(a, b):
    return 0

Challenges

1. Print the truth table for NOT (A OR B). Which gate does it match the opposite of?
2. Make the robot's circuit also require that it has not just bumped into something, using bumped().
3. How many rows does a truth table for 5 inputs have? Check by printing it.