Circuits, expressions and truth tables

Reading and drawing circuits, defining a problem in Boolean logic, and sum of products from a truth table.

A8.2Boolean algebra and logic circuitsA level20 min

A circuit diagram, a Boolean expression and a truth table are three views of the same function. A level questions ask you to move between all three in any direction, and to start from a problem described in words. This lesson practises each move, and ends with the one that always works: turning any truth table into an expression.

From circuit to expression

Work from the inputs towards the output, writing the expression each gate produces on its output wire.

• The top gate is a NOR of A and B: its output is ¬(A ∨ B).
• The bottom gate is an AND of B and C: B ∧ C. The dot on the B wire is a junction: B feeds both gates. Wires that cross without a dot are not connected.
• The last gate ORs the two: Q = ¬(A ∨ B) ∨ (B ∧ C).

In AQA notation the same circuit is Q = (a bar over A + B) + B · C. Always keep the brackets that show which gate each part came from.

From expression to truth table

For three inputs there are 2³ = 8 rows. Add a column for each gate, then combine:

The in-between columns are worth their space: a mark scheme gives credit for the final column, and the extra columns are how you get it right.

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

print("A B C | NOR  AND | Q")
for a in [0, 1]:
    for b in [0, 1]:
        for c in [0, 1]:
            n = NOR(a, b)
            m = b & c
            print(a, b, c, "|", n, "   ", m, "  |", n | m)

Run this in the simulator

From expression to circuit

Draw the gate that is applied last at the output end, then work back towards the inputs. For Q = (A ⊻ B) ∧ ¬C:

1. The last operation is ∧, so the output comes from an AND gate.
2. Its first input is A ⊻ B, from an XOR gate fed by A and B.
3. Its second input is ¬C, from a NOT gate fed by C.

Count the operators to count the gates: one XOR, one NOT and one AND. Each NOT in front of a bracket is a gate on the output of that bracket's circuit, or a bubble drawn on it.

Defining a problem with Boolean logic

Real problems arrive in words. The method is always the same: name each condition that can be true or false with a letter, then turn the sentence into an expression, checking every "and", "or" and "unless".

"BugBot sounds an alarm if it has bumped into something, or if it is close to a wall while its battery is low."

• K: the robot has bumped. C: it is close to a wall. L: the battery is low.
• Alarm = K ∨ (C ∧ L).

"While" here means "at the same time as", which is AND. Watch for "unless", which means "or not": "drive unless blocked" is Drive = ¬Blocked. And "either ... or ... but not both" is XOR.

Now each letter is a sensor reading turned into a bit:

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

forward(50, distance=30)
K = 1 if bumped() else 0
C = 1 if distance() < 25 else 0
L = 1 if battery() < 20 else 0
alarm = K | (C & L)
print(f"K={K} C={C} L={L} alarm={alarm}")
if alarm == 1:
    tone(880, 0.5)

Run this in the simulator

From truth table to expression: sum of products

Sometimes you are given only the truth table, for example a list of the situations in which a robot must stop. There is a method that always works.

1. Find every row where the output is 1.
2. For each such row, write an AND of all the inputs, putting NOT on each input that is 0 in that row. This term, called a minterm, is 1 on that row and on no other.
3. OR all the terms together.

The result is called sum of products form, because in AQA notation AND looks like multiplication and OR looks like addition. For this table:

the 1 rows are 010, 110 and 111, so:

Q = (¬A ∧ B ∧ ¬C) ∨ (A ∧ B ∧ ¬C) ∨ (A ∧ B ∧ C)

This expression is correct, but it is long: three three-input ANDs and a three-input OR. The rest of the module is about making it shorter. By lesson A8.6 you will be able to see at a glance that it equals (B ∧ ¬C) ∨ (A ∧ B).

Task: truth table to expression

Write sum_of_products(outputs). Its input outputs is a list of eight integers, each 0 or 1: the Q column of a truth table for inputs A, B and C, with the rows in binary order, so outputs[0] is the row A=0 B=0 C=0 and outputs[7] is A=1 B=1 C=1. It returns a string: Q = followed by the minterms joined with OR. Each minterm is in brackets, lists A, B and C in that order joined with AND, and writes an input that is 0 in that row as NOT and a space before the letter. If no row is 1, it returns Q = 0.

For example, [0, 0, 1, 0, 0, 0, 0, 1] gives Q = (NOT A AND B AND NOT C) OR (A AND B AND C).

Print the result for these three tables, one per line, in this order: [0, 1, 1, 1, 1, 1, 1, 1], then [0, 0, 1, 0, 0, 0, 1, 1], then [0, 0, 0, 0, 0, 0, 0, 0].

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

def sum_of_products(outputs):
    return "Q = "

print(sum_of_products([0, 1, 1, 1, 1, 1, 1, 1]))
print(sum_of_products([0, 0, 1, 0, 0, 0, 1, 1]))
print(sum_of_products([0, 0, 0, 0, 0, 0, 0, 0]))

Challenges

1. The first table gives seven minterms. What short expression has that truth table? What does that tell you about sum of products?
2. Extend sum_of_products to any number of inputs, taking the variable names as a second parameter.
3. Write the alarm expression K ∨ (C ∧ L) in AQA notation, draw its circuit, and use your function to print its sum of products form.