Logic gates and notation

NOT, AND, OR, XOR, NAND and NOR, the notation each board uses, and why NAND alone can build anything.

A8.1Boolean algebra and logic circuitsA level20 min

At GCSE you met AND, OR and NOT, drew their truth tables, and built a half adder from XOR and AND (lessons F9.1 and F9.2). A level adds two more gates, NAND and NOR, asks you to write expressions in your board's notation, and then treats those expressions as algebra you can rearrange and simplify. This lesson sets out the six gates and the symbols, so the rest of the module has a shared language.

The six gates

A logic gate is a circuit with one or more binary inputs and one binary output. Its behaviour is defined completely by its truth table, which lists the output for every combination of inputs:

• XOR (exclusive OR) is 1 when the inputs are different.
• NAND is NOT AND: it is 0 only when both inputs are 1. Its symbol is an AND gate with a small circle, the inversion bubble, on the output.
• NOR is NOT OR: it is 1 only when both inputs are 0. Its symbol is an OR gate with a bubble.

A bubble anywhere on a diagram means "invert this signal". You will see bubbles on inputs too, later in the module.

Three ways to write the same thing

Exam papers do not write AND. Each board has its own notation, and you must read and write the one your board uses.

In AQA's notation the length of the bar matters. A̅ · B̅ has two short bars, one over each letter, and means (NOT A) AND (NOT B). A single long bar over A · B means NOT (A AND B). They are different functions, as lesson A8.4 shows.

Precedence works like arithmetic: NOT is applied first, then AND, then OR. So A ∨ B ∧ C means A ∨ (B ∧ C), just as 2 + 3 × 4 means 2 + (3 × 4). Exam questions usually add brackets anyway, and so should you when you write expressions.

Gates in Python

Python has two sets of operators. and, or and not work on any values and are what you use in if and while. The bitwise operators &, | and ^ work bit by bit on integers, so on 0 and 1 they behave exactly like AND, OR and XOR gates and always return 0 or 1.

There is a trap. Python's bitwise NOT, ~, flips every bit of the whole integer, and Python integers are signed, so ~1 is -2, not 0. On a single bit, write NOT as 1 - a or a ^ 1.

def NOT(a): return 1 - a
def NAND(a, b): return 1 - (a & b)
def NOR(a, b): return 1 - (a | b)

print("A B | NOT AND OR XOR NAND NOR")
for a in [0, 1]:
    for b in [0, 1]:
        print(a, b, "|", NOT(a), "  ", a & b, "  ", a | b, " ", a ^ b, "  ", NAND(a, b), "   ", NOR(a, b))

print("~1 is", ~1, "but NOT(1) is", NOT(1))

Run this in the simulator

NAND can build anything

NAND and NOR are called universal gates: any logic circuit at all can be built from NAND gates alone, or from NOR gates alone. That matters in manufacturing, because a chip made of millions of one identical gate is cheaper and simpler to make than one mixing several kinds.

The first step is NOT. Tie both inputs of a NAND together, so both are A: if A is 1 you get NAND(1, 1) = 0, and if A is 0 you get NAND(0, 0) = 1. That is NOT A. With NOT available, AND is just a NAND followed by a NOT, because NOT (NOT (A AND B)) is A AND B.

def NAND(a, b):
    return 1 - (a & b)

def NOT(a):
    return NAND(a, a)          # both inputs tied together

def AND(a, b):
    return NOT(NAND(a, b))     # undo the inversion

for a in [0, 1]:
    for b in [0, 1]:
        print(f"A={a} B={b} NOT A={NOT(a)} A AND B={AND(a, b)}")

Run this in the simulator

OR and XOR take a little more thought, and they are the task below. Lesson A8.4 explains why the OR construction works.

A robot example

BugBot's gates are hidden inside its processor, but the idea is the same in a program. Suppose the robot should sound a warning when exactly one of its two front sensors says something is close: that means one sensor sees an object the other misses, so the robot is at an angle to it. "Exactly one of two" is XOR.

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

grid = tof_grid()                  # 64 distances, row 3 (level) is grid[24:32]
left_close = 1 if min(grid[24:28]) < 30 else 0
right_close = 1 if min(grid[28:32]) < 30 else 0
warn = left_close ^ right_close
print("left", left_close, "right", right_close, "warn", warn)
if warn == 1:
    tone(660, 0.2)

Run this in the simulator

Task: everything from NAND

You are given NAND(a, b), which takes two bits (each 0 or 1) and returns 0 or 1. Write four functions, each taking bits and returning 0 or 1, built only by calling NAND or the gates you have already built from it: NOT(a), AND(a, b), OR(a, b) and XOR(a, b). Your program may not use and, or, not, comparisons such as ==, a minus sign, or the operators &, |, ^ and ~.

Then use loops to print one line for each of the four input combinations, in binary order, in exactly this form:

A=0 B=1 NOT_A=1 AND=0 OR=1 XOR=1

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

def NAND(a, b):
    return [1, 1, 1, 0][2 * a + b]

def NOT(a):
    return 0

def AND(a, b):
    return 0

def OR(a, b):
    return 0

def XOR(a, b):
    return 0

Challenges

1. Build NOT, AND and OR from NOR alone. Which is easier to build from NOR than from NAND?
2. How many NAND gates does your XOR use in total, counting the ones inside the gates it calls? Can you do it in four?
3. Write A ⊻ B using only AND, OR and NOT, in both OCR and AQA notation.