Logic gates

Some questions only have two answers. Is the door open? Is the button pressed? Is the score over 50? The answer is true or false. Nothing in between.

1. George Boole (1815–1864) wrote maths for true/false statements. His book The Laws of Thought came out in 1854. Values that are only true or false are called Boolean in his honour.

2. In 1937, Claude Shannon noticed that Boole's maths fits electrical switches perfectly. Switch on = true = 1. Switch off = false = 0.

3. So a circuit of switches can make decisions. How you join the switches decides the rule. Try it below.

Engineers don't draw switches every time. Each rule gets its own symbol. Inputs come in on the left. The output, called Q, leaves on the right.

1. NOT has one input. It flips it: 0 → 1, 1 → 0. It is also called an inverter.

2. AND gives 1 only if both inputs are 1. One 0 is enough to make it 0.

3. OR gives 1 if at least one input is 1. It is only 0 when both are 0.

XOR means "exclusive OR": one or the other, but not both. It gives 1 when the inputs are different.

A truth table lists every pattern of inputs, one per row, and the output for each. The trick to never missing a row: count in binary.

1. Count the inputs: n.

2. Each input is 0 or 1: 2 choices. So there are 2 × 2 × … = 2ⁿ rows.

3. Write the row numbers 0 up to 2ⁿ − 1 in binary, with n digits. Those are your input columns.

4. Quick check: the rightmost input column goes 0, 1, 0, 1. The next one goes 0, 0, 1, 1. Each column to the left doubles the run.

Because the inputs are only 0 or 1, each gate is a tiny sum. This is a second way to remember the rules, and it shows why gates can do maths.

A Boolean expression writes a circuit as one line of text, like Q = A AND B. Different books use different symbols for the same idea.

Which part do you work out first?

1. Brackets first, like in maths.

2. Then NOT. It sticks to the thing right after it.

3. Then AND, then OR. Exam questions nearly always add brackets so you don't have to rely on this.

The output of one gate can feed into another. Work out the circuit one gate at a time, from the inputs on the left to Q on the right.

Exams ask both ways. Write the circuit as an expression, or draw the circuit for an expression.

Circuit → expression

1. Start at the gates that only touch inputs. Here: the OR gate (A, B) and the NOT gate (C).

2. Write what leaves each one: A OR B and NOT C.

3. Move right. The AND gate takes those two wires. Put each one in brackets if it has more than one part.

4. Answer: Q = (A OR B) AND NOT C. In AQA symbols: Q = (A + B) . C.

Expression → circuit

1. Find the operator that is done last: the one outside all brackets. In (A OR B) AND NOT C it is the AND. Draw it on the right, next to Q.

2. Its two inputs are the two sides: (A OR B) and NOT C.

3. Draw a gate for each side: an OR gate fed by A and B, and a NOT gate fed by C.

4. Join their outputs to the AND gate. Check one row: A = 1, B = 0, C = 0 → (1 OR 0) AND NOT 0 = 1 AND 1 = 1.

Adding two bits gives a 2-bit answer: a carry and a sum. 1 + 1 = 2, which is 10 in binary: carry 1, sum 0.

Extension: the full adder

A half adder can't take a carry in from the column to its right. A full adder can. It joins two half adders and an OR gate. It has 3 inputs (A, B, carry in), so its truth table has 2³ = 8 rows.

A gate is not a program. It is a real circuit made of transistors: electronic switches with no moving parts.

1. The first transistor was made in 1947 at Bell Labs. Today a phone's processor has billions on a chip the size of a fingernail.

2. Real chips use CMOS: pairs of transistors. A CMOS NAND gate needs 4 transistors. An AND gate is a NAND plus a NOT, so it needs 6.

3. You can buy gates on small chips. The 74HC08 has four AND gates. The 74HC32 has four OR gates, and the 74HC86 has four XOR gates. All three use the same pin layout.

The words and, or and not in your programs are the same gates. Python works them out with True and False instead of 1 and 0.

from microbit import *

while True:
    a = button_a.is_pressed()      # True or False
    b = button_b.is_pressed()
    if a and b:                     # AND: both buttons
        display.show(Image.HAPPY)
    elif a != b:                    # XOR: exactly one button
        display.show("1")
    else:                           # neither button
        display.clear()

1. button_a.is_pressed() returns a Boolean: True or False.

2. a and b is an AND gate. Both buttons → happy face.

3. a != b means "a is not equal to b": true when they are different. That's XOR. Python has no xor keyword.

4. Order matters. The AND test is first, so pressing both shows the face, not "1".

Print a truth table with Python

for a in (0, 1):
    for b in (0, 1):
        print(a, b, a and b, a or b, a ^ b)

The mistakes almost everyone makes at first. Read the left, then the right.

Quick questions first. Then endless practice: a wrong answer shows you the working, step by step.