Truth Tables and Logic
NOT, AND and OR, how to build a truth table for a combined expression without losing a row, and how the same logic turns up inside program conditions.
The three logical operators
Boolean logic deals in exactly two values: true and false, usually written as 1 and 0. Every decision a computer makes reduces to combinations of three operators.
NOT
NOT inverts its input. True becomes false and false becomes true.
| A | NOT A |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND
AND gives 1 only when both inputs are 1. Think of two switches in series: the current only flows if both are closed.
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR
OR gives 1 when at least one input is 1. Two switches in parallel: current flows if either path is open.
| A | B | A OR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
AND is true only when everything is true. OR is false only when everything is false. NOT flips whatever it is given. If you can say those three from memory you can build any truth table on the paper.
Building a truth table that is right
A truth table lists every possible combination of inputs and the output each one produces. Getting one wrong is almost never a failure of understanding, it is a failure of method, so use a method.
Step 1: work out how many rows
With n inputs there are 2 to the power n rows. One input gives 2 rows, two inputs give 4, three inputs give 8. If your table has any other number of rows it is already wrong.
Step 2: fill the input columns in the standard pattern
For three inputs the reliable pattern is: the last column alternates 0, 1, 0, 1 and so on; the middle column alternates in pairs, 0, 0, 1, 1; the first column alternates in fours, 0, 0, 0, 0 then 1, 1, 1, 1. Doing it this way guarantees you produce all eight combinations and never repeat one.
Step 3: add a working column for each bracket
Do not try to evaluate a combined expression in your head. Give every sub expression its own column and fill it in before you touch the final answer.
Here is (A AND B) OR (NOT C) done properly.
| A | B | C | A AND B | NOT C | (A AND B) OR (NOT C) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |
The working columns cost about thirty seconds and remove almost every chance of an error. Look at the last row: the AND is true, so the OR is true even though NOT C is false. That is the row people get wrong when they rush.
A AND (B OR C) and (A AND B) OR C are different expressions. Set A to 0, B to 0 and C to 1, and the first gives 0 while the second gives 1. Always evaluate the brackets first.
Logic gate simulator
Build a circuit from gates, wire it up, and see the truth table fill in as you go. This tool needs JavaScript, so turn it on to use it. Everything you need to answer the exam question is explained in the text above.
Logic in real systems and real programs
Reading a scenario into an expression
Exam questions describe a system in English and expect an expression or a truth table. Translate one clause at a time.
"A fire door unlocks if the fire alarm is sounding, or if the manual release is pressed and the building is not in lockdown."
- Let A be "fire alarm sounding", M be "manual release pressed", L be "building in lockdown".
- Unlock =
A OR (M AND NOT L).
Check it against sense: with the alarm sounding the door unlocks whatever else is true, which is what a fire door must do. With the manual release pressed during a lockdown it stays locked, because NOT L is 0. The expression behaves like the description, so it is right.
The same logic inside a program
Program conditions are Boolean expressions, and every rule above applies to them unchanged.
if age >= 13 and (has_consent or is_supervised):
allow_access()That condition is A AND (B OR C). Removing the brackets changes its meaning completely: age >= 13 and has_consent or is_supervised would let an unsupervised infant in, because and binds more tightly than or, so it reads as (A AND B) OR C.
Common patterns worth recognising
| English | Expression |
|---|---|
| Both conditions must hold | A AND B |
| Either condition will do | A OR B |
| Neither condition holds | NOT A AND NOT B |
| Exactly one of the two holds | (A OR B) AND NOT (A AND B) |
| The condition must not hold | NOT A |
In a truth table question the marks are usually awarded per column, not per table. An intermediate column that is correct earns its mark even if the final column contains a slip.
- Two inputs, one AND gate, one NOT gate, one output.
- A = 1 and B = 0. AND needs both, so it gives 0.
- NOT flips it, so Q becomes 1.
- A = 1 and B = 1. AND gives 1, NOT flips it, Q is 0.
- Q = NOT (A AND B). That is a NAND gate, written out.
Key terms you must be able to define
- Boolean
- A data type or value that can only be true or false, often represented as 1 and 0.
- Logical operator
- A symbol or keyword such as AND, OR or NOT that combines or inverts Boolean values.
- AND
- A logical operation whose output is true only when every input is true.
- OR
- A logical operation whose output is true when at least one input is true.
- NOT
- A logical operation that inverts its input, turning true into false and false into true.
- Truth table
- A table listing every possible combination of inputs to a logical expression together with the resulting output.
- Logic gate
- An electronic component that performs a logical operation on one or more binary inputs and produces one binary output.
- Condition
- A Boolean expression tested by a program to decide which instructions to execute next.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
Truth table marks are lost to carelessness rather than to ignorance, so the top grade here is a matter of discipline.
Count your rows before you write anything. Two inputs is four rows, three inputs is eight. Half the errors in this topic are a missing combination.
Give every bracket its own column. Evaluating (A AND B) OR NOT C in your head across eight rows is a guaranteed slip, and the working columns are separately creditable.
Translate scenarios one clause at a time. Define your letters explicitly, write the expression, then test it against two or three sentences from the question to check it behaves as described. Stating what each letter stands for takes one line and often earns a mark on its own.
Know the effect of the brackets. Being able to say that A AND (B OR C) differs from (A AND B) OR C, and give a set of inputs that proves it, is the kind of specific detail that separates the top band.
- Be able to write the truth tables for NOT, AND and OR from memory in under a minute
- Be able to produce all eight input combinations for three inputs in the standard order without thinking
- Be able to build a truth table for an expression with two operators and brackets, with working columns
- Be able to turn a described system such as an alarm or a door lock into a Boolean expression
Mistakes that cost marks here
- Producing six or seven rows for a three input table. There are always exactly eight.
- Treating OR as meaning one or the other but not both. In Boolean logic OR is true when both inputs are true as well.
- Ignoring brackets and evaluating an expression left to right, which changes the answer.
- Applying NOT to the whole expression when it only applies to one variable, or the other way round.
- Writing an expression without saying what each letter stands for, so the examiner cannot tell whether it matches the scenario.
- Assuming AND and OR mean in code what they mean in casual English. 'Under 13 or over 65' is an OR, but 'between 13 and 65' is two conditions joined by AND.
George Boole worked out this algebra in 1854 in a book called An Investigation of the Laws of Thought. There were no electronic computers and no transistors. It took until 1937 for Claude Shannon, then a master's student, to notice that Boole's algebra described exactly what a network of electrical switches does.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LShows all four combinations of A and B
- LIdentifies that the output is 1 only when A is 1 and B is 0
The table has four rows because there are two inputs. When A is 0 and B is 0 the output is 0, when A is 0 and B is 1 the output is 0, when A is 1 and B is 0 the output is 1, and when A is 1 and B is 1 the output is 0. The output is therefore 1 for exactly one combination, where A is 1 and B is 0, because AND requires both of its inputs to be true and NOT B is only true when B is false.
- LAND outputs true only when all of its inputs are true
- LOR outputs true when at least one of its inputs is true
- LOR is therefore true in more cases, and is only false when every input is false
AND produces an output of true only when every one of its inputs is true, so with two inputs it is true in just one of the four possible combinations. OR produces an output of true whenever at least one of its inputs is true, including the case where both are true, so with two inputs it is true in three of the four combinations. Put the other way round, AND is false as soon as any input is false, while OR is false only when every input is false.
- LDefines a variable for each condition, such as T for high temperature, H for high humidity and F for the fan running
- LUses AND to combine the humidity condition with the fan condition
- LApplies NOT to the fan variable only
- LUses OR to combine the temperature condition with the humidity and fan condition, with correct bracketing
Let T represent the temperature being above 28 degrees, H represent the humidity being above 80 per cent, and F represent the fan running. The vent opens when T is true on its own, or when H is true at the same time as F is false. The expression is therefore vent equals T OR (H AND NOT F). The brackets are essential, because they keep the humidity and fan conditions together as a single requirement: without them the expression would open the vent whenever the humidity was high, regardless of the fan.
- LRecognises that three inputs give eight rows
- LEvaluates A OR B correctly as true whenever A or B is 1
- LEvaluates NOT C correctly as the inverse of C
- LStates that the output is 1 only when C is 0 and at least one of A and B is 1
There are three inputs so the table has eight rows. The column for A OR B is 0 only in the two rows where both A and B are 0, and 1 in the other six. The column for NOT C is 1 in the four rows where C is 0 and 0 in the four where C is 1. The final column is the AND of those two working columns, so it is 1 only where both are 1. That gives an output of 1 in exactly three rows: A equals 0 with B equals 1 and C equals 0, A equals 1 with B equals 0 and C equals 0, and A equals 1 with B equals 1 and C equals 0. In words, the output is true only when C is false and at least one of A and B is true.
- LIdentifies that AND is evaluated before OR
- LSo the condition is treated as age > 65 OR (age < 16 AND has_pass)
- LStates that this actually matches the intention for the under 16 case
- LNotes the risk that a reader cannot see the grouping, so the code is easy to misread and to break when edited
- LCorrects it by adding brackets, for example if age > 65 or (age < 16 and has_pass)
In Python the AND operator has higher precedence than OR, so the condition is evaluated as age greater than 65, OR the pair age less than 16 AND has_pass taken together. In this particular case that grouping happens to match what the student wanted, since a person under 16 does need a pass while a person over 65 does not. The problem is that nothing in the code says so. Anyone reading the line has to know the precedence rules to work out the grouping, and a small future edit, such as adding a third condition, can silently change the meaning and introduce a fault that produces no error message. The correction is to make the grouping explicit by writing if age > 65 or (age < 16 and has_pass), which behaves identically but states the intention on the page rather than leaving it to be inferred.