Logic gates and truth tables

Why this matters

A computer makes every decision from yes or no answers. Is the password right? Is the key pressed? Is the number larger than the last one? The answers are produced by small electronic circuits called logic gates. Each gate takes one or two signals in and gives one signal out, following a fixed rule.

If you can read a truth table, you can predict what a gate does before you build it. You can also check your own if conditions the same way. The next lesson, on the tiny adder, chains these gates together to add numbers. This lesson covers only the gates and how to describe them.

You do not need electronics for any of this. Each gate is fully described by a small table, and that table is all you need.

Signals that are either 0 or 1

Inside a chip, a wire carries a voltage. The chip treats a high voltage as "on" and a low voltage as "off". Engineers write "on" as 1 and "off" as 0. These two values are the bits from the binary lesson earlier in this module. A signal is a bit travelling along a wire.

A gate reads its input wires and drives one output wire. Every input and output is either 0 or 1. There is no third state in this lesson.

An everyday comparison is a vending machine's coin slot. The machine has a rule: it releases a drink only when enough coins are in. The rule is fixed, so the same coins always give the same result. A logic gate is a rule like that, built into hardware, with each input being a yes or no.

The truth table

A truth table lists every possible combination of inputs and the output for each one. It is the complete definition of a gate. Nothing else is needed to know what the gate does.

The number of rows follows a simple pattern. With one input there are 2 rows, with two inputs there are 4, and with three inputs there are 8. In general, n inputs need 2 to the power n rows. If a table has fewer rows than that, it is missing a case.

Rows are written in counting order. For two inputs, the order is 0 0, 0 1, 1 0, 1 1. Writing the rows in this fixed order makes it hard to skip one.

NOT: flip the input

NOT has one input. Its output is the opposite of its input. Some people call it an inverter, because it inverts the signal.

Here is a plain example. A light sensor reads 1 when it is dark. The light should be on when it is not dark. That is NOT applied to the sensor.

Read the table as: if the input is 0, the output is 1. If the input is 1, the output is 0.

AND: both inputs must be 1

AND has two inputs. Its output is 1 only when both inputs are 1. In every other row, the output is 0.

Example: an alarm arms only when the front door is shut and the window is shut. The door sensor gives 1 when the door is shut. The window sensor gives 1 when the window is shut. The alarm is armed when both are 1.

Only one row gives 1. That is the quickest way to recognise AND: find the row where both inputs are 1, and it is the only one with an output of 1.

OR: at least one input must be 1

OR also has two inputs. Its output is 1 when at least one input is 1. The only row that gives 0 is the one where both inputs are 0.

Example: a hallway light is switched on by a switch at either end of the hall. Pressing either switch turns the light on. If both are pressed, the light stays on. The OR rule matches this, because one or both being on is enough.

Everyday English uses "or" in two ways. Sometimes it means "one or both", and sometimes "one or the other but not both". The OR gate means "one or both". The next gate covers the other meaning.

XOR: exactly one input must be 1

XOR stands for "exclusive or". Its output is 1 when the inputs are different. When both inputs are 1, the output is 0. XOR is not the same as OR, and the difference is only in the last row.

Example: a staircase light has one switch at the top and one at the bottom. Flipping either switch changes the light. Think of each switch as a bit that is 0 or 1 depending on its position. The light is on when the two switches are in different positions. If you flip both, the light goes back to off.

XOR matters later in the course because it is how a computer adds two bits without the carry. The adder lesson uses it directly.

Reading a truth table to name a gate

Sometimes you are given a table and asked what it does. The method is to look at the rows that give 1, because those rows are what the gate is for.

Worked example 1. Here is a table with an unknown gate.

Step 1: count the rows. There are four, so there are two inputs.

Step 2: list the rows that give 1. They are 0 1 and 1 0.

Step 3: compare with the known gates. AND has only 1 1 giving 1, so it is not AND. OR gives 1 for three rows, so it is not OR. The only gate whose output is 1 for exactly 0 1 and 1 0 is XOR.

Answer: this is XOR.

The same method works for any table of two inputs. Count the 1s in the output column first. One 1 suggests AND, three 1s suggests OR, and two 1s suggests XOR or one of its relatives.

Gates in Python

Python can run a gate on 0 and 1 values. The operators &, | and ^ work on whole numbers bit by bit. For single bits, they give exactly the AND, OR and XOR results above. NOT is not a Python operator on bits, so we write it as 1 - a. If a is 0, the result is 1. If a is 1, the result is 0.

The block below defines the gates and prints the four truth tables. The product function from the standard library produces every combination of inputs, so the code cannot skip a row.

Output:

NOT
0 -> 1
1 -> 0
 
AND
0 0 -> 0
0 1 -> 0
1 0 -> 0
1 1 -> 1
 
OR
0 0 -> 0
0 1 -> 1
1 0 -> 1
1 1 -> 1
 
XOR
0 0 -> 0
0 1 -> 1
1 0 -> 1
1 1 -> 0
 

Compare the printed rows with the tables earlier in this lesson. They match row for row. That check is how you know your gate definition is right: write the table by hand from the rule, then run the code and compare.

Worked example 2: a porch light with three inputs

Now a rule with more than two inputs. A porch light should turn on in two cases. The first is when it is dark and someone is near the door, as read by a motion sensor. The second is when the owner presses an override switch. The light is on if either case is true.

Name the inputs. dark is 1 at night. motion is 1 when someone is near. override is 1 when the switch is pressed. The rule is: light = (dark AND motion) OR override.

Work it in two steps, the same way you would write code. First compute the inner part, dark AND motion. It is 1 only when dark is 1 and motion is 1. Then combine it with override using OR. The light is on if the inner part is 1 or override is 1.

With three inputs there are 8 rows. Writing them out by hand is slow but reliable. The code below does the same work and prints every row.

Output:

dark motion override | light
0 0 0 | 0
0 0 1 | 1
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

Read the rows where the light is 1. Rows 0 0 1, 0 1 1, 1 0 1 and 1 1 0 and 1 1 1 are the on cases. Check one row against the rule. Row 1 0 1 means dark is 1, motion is 0, and override is 1. The AND part is 0 because motion is 0. The override part is 1. OR of 0 and 1 is 1, so the light is on. That matches the table.

Worked example 3: a rule with NOT inside

The third example has a NOT. A heater should run when the room is cold and the window is not open. Name the inputs: cold is 1 when the room is cold, and window_open is 1 when the window is open. The rule is: heater = cold AND NOT window_open.

Notice that the rule says "not open", not "open". So the window input is flipped before it reaches the AND gate. This is the step most beginners miss.

Write the table by hand, one row at a time.

Only the third row gives 1. In that row the room is cold and the window is shut. The heater runs only when both conditions hold.

A useful habit is to write the NOT column first. It keeps the NOT step from being forgotten, and it turns a three-input problem into a simple AND of two columns.

Common mistakes

Using ~ for NOT. In Python, ~ is a different operator. It flips every bit of a whole number, including the sign, so it does not stay in 0 and 1.

Output:

~1 is -2
~0 is -1
1 - 1 is 0

The result of ~1 is -2, not 0. For a gate, use 1 - a.

Using and and or instead of & and |. Python's and and or return one of their inputs, not a bit. For 0 and 1 they give the right answer, so the bug only shows up when a value other than 0 or 1 gets in.

Output:

1 and 0 is 0
2 and 1 is 1
2 & 1 is 0

The value 2 and 1 returns 1, which is the second input. The value 2 & 1 is 0, because the bits of 2 (10) and 1 (01) share no 1 in the same place. The two operators only agree when every input is already 0 or 1. The gates in this lesson take only 0 and 1, so the &, | and ^ forms are the correct ones.

Passing a value that is not a bit. A gate is only defined for 0 and 1. A check at the top of each gate makes the mistake visible at once.

Output:

1
ValueError: a gate input must be 0 or 1, got 2

Without the check, passing text gives a different and harder error. The NOT gate in the next block takes 1 - a, and the string "1" is not a number.

Output:

0
TypeError: unsupported operand type(s) for -: 'int' and 'str'

The message names the operation (-) and the two types, which points to the cause. The fix is to make sure the input is 0 or 1 before it reaches the gate.

Mixing up OR and XOR. The two tables differ in one row, 1 1. If you use OR where the rule says "exactly one", the light turns on when both switches are on. Check the rule for the words "both" and "exactly one" before choosing the gate.

Writing a table with missing rows. Three inputs need 8 rows. A table with 6 rows is wrong, even if the rows it has are correct. Count the rows first, and generate them in order rather than typing them from memory.

Practice

Exercise 1. A gate has inputs a and b. Its output is 1 only for the rows 0 1 and 1 0. Which gate is it?

Show the answer

It is XOR. The two rows with output 1 are the two rows where the inputs differ, and that is what XOR means.

Exercise 2. Write the truth table for NOT NOT a, meaning NOT applied to the output of another NOT. What does this gate do?

Show the answer

The output always equals the input. Two inversions cancel out, so the double NOT is the same as no gate at all.

Exercise 3. An alarm sounds when door_open AND armed is 1, or when panic is 1. Find the output for these three input sets: door_open 1, armed 0, panic 0; door_open 1, armed 1, panic 0; door_open 0, armed 0, panic 1.

Show the answer

The first set gives 0. The AND part is 1 AND 0, which is 0, and panic is 0, so the OR is 0. The second set gives 1, because the AND part is 1 AND 1, which is 1. The third set gives 1, because panic is 1 and the OR is 1 whatever the AND part is.

Exercise 4. Using the gate functions from the block in the Gates in Python section, what does XOR(1, 1) return, and why?

Show the answer

It returns 0. The two inputs are the same, so they are not different, and XOR gives 0 when both inputs are 1. The Python ^ operator on 1 and 1 gives 0, which matches the table.

Exercise 5. How many rows does a truth table need for a gate with five inputs?

Show the answer

It needs 32 rows, which is 2 to the power 5. Each of the five inputs can be 0 or 1 independently, so the number of combinations doubles for each input.

Summary

• A logic gate takes 0 and 1 inputs and gives one 0 or 1 output by a fixed rule.
• NOT flips its input. AND is 1 only when both inputs are 1. OR is 1 when one or both inputs are 1. XOR is 1 when the inputs differ.
• A truth table has 2 to the power n rows for n inputs, and writing it in counting order makes it hard to miss a row.
• Python's &, | and ^ match AND, OR and XOR on 0 and 1 values, but ~ does not, and and and or only work for 0 and 1.
• Check a gate by writing its table by hand, then running the code and comparing the rows.