Logic circuits and expressions

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

F9.2Logic and computer systemsGCSE15 min

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

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:

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:

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).

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:

# 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

Chain 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

# 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(20):
    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

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

1. 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.
2. 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.
3. Show that NOT (A AND B) is always the same as (NOT A) OR (NOT B) by printing both columns.