In Unit 1 we learned that the CPU has a fixed set of instructions (an instruction set) and that these can be combined to make useful programs. The CPU then fetches, decodes and executes these instructions continuously until the power is turned off. This section takes the next step towards understanding how a CPU really works. How are these instructions turned into circuits on a CPU? Why are CPU instructions always really short and simple? Why can a computer only carry out mathematical or logical instructions?
The answer to all of these questions and more is… Boolean logic!
In this section:
- The need for Boolean Logic
- The operators and truth tables
- Circuits and problem solving
- Truth tables for expressions
The need for Boolean Logic
Way back at the start of Unit 1 we learned a fundamental concept – computers only understand the binary numbers zero and one.
Why? Well, you should also know that this is due to the fact that computers are electronic devices that contain many billions of switches called Transistors. A transistor, like any normal switch, may be in one of two positions – on or off. We represent “on” as the number one and “off” as the number zero. That is as far as our definition went at that point in your learning.
However, you probably noticed there’s quite a large gap between some switches and your favourite TikTok video or game which you’ve sunk 300 hours into recently. You’d be right, there is. We solved one mystery in Unit 1.2 when we learned about encoding, which is the process of turning real world information such as text, images and sound into binary data that can be stored and processed by a computer. Getting data in and out of a computer is only half the story.
Going all the way back to Unit 1.1 – Systems Architecture you learned that the CPU is a device which processes (carries out) program instructions. All computers require software in order to work or do something useful, a computer cannot and does not decide what to do by itself, it is always following instructions as defined by a programmer.
All CPU’s have a fixed “instruction set” – literally a set of instructions which they are able to carry out. These are very short, simple instructions such as “add two numbers” or “move this data from the memory to the CPU.” Simplifying things quite drastically, you can imagine that each one of these instructions refers to a circuit that has been designed to carry out the instruction inside the CPU.
We are almost there, finally we need to understand how each of these circuits are designed. The circuits inside the CPU are constructed using something called “logic gates.” As you may have realised by now, in Computing we don’t give things inspirational names, we call them what they are. A logic gate is a component which lets a one or a zero pass through (the gate opens) based on a logical rule – hence… logic gate.
Logic gates come from some seriously ancient maths. A very interesting man called George Boole published a book in 1854 called “The Laws of Thought.” In it, he proposed that everything in the real world could be described or boiled down to immutable, logical “truths.” In other words, George did not believe in grey areas. The entire world was black and white, right or wrong, on… or off… This work was itself built on the ideas of Aristotle, a Greek philosopher and Mathematician from 300ish BC. Like I said, old maths.
In proposing “Boolean Logic” Boole came up with fundamental rules called “truths” for what is effectively addition and multiplication. The idea being that for certain operations called AND and OR, there were definite, unbreakable rules for the relationship between each input (a pair of true or false values) and their outputs – a single true or false value.
Without going into degree level mathematics, it turns out that it is possible to combine these Boolean rules in such a way as to create circuits that carry out simple mathematical operations – the very foundation of CPU instructions. Furthermore, this has a significant advantage that because we know all possible inputs and all possible outputs, there can never be ambiguity. The outcome of a Boolean calculation or circuit can never be “maybe.” This is ideal for computing because the last thing you ever want is to run a program and the results be “err…. Not sure? Try that again?” or to get different results when you run a program twice on the same piece of data. This would be disastrous.
George Boole died after a walk in the rain. Let this be a lesson to you, when your mother nags at you to remember your coat, it’s for a good reason and furthermore, be grateful you didn’t marry Mrs Boole. She believed that the cure to a disease, in this case pneumonia, was to mimic the cause. So, she wrapped him in wet blankets and duly killed him.
The operators and truth tables
There are three Boolean operators (rules) that we need to know for GCSE. These are:
- AND
- OR
- NOT
Each of these has a special symbol associated with it. In the exam it is acceptable to use any widely accepted symbol, however they usually stick to one type as in the table below:
| Boolean Operator | Symbol probably used in the exam (that only OCR use for some weird reason) | Other symbols (that people actually use in the real world) |
| AND | ∧ | . |
| OR | ∨ | + |
| NOT | ‘ | ¬ or  |
Inputs are usually represented as letters, so the following are examples of Boolean Expressions:
| Boolean Expression | Meaning |
| ¬A | NOT A |
| NOT A |
| A + B A ∨ B | A OR B |
| P . Q P ∧ Q | P AND Q |
| A ∨ B ∧ C | A OR B AND C |
Each Boolean operator has its own “Truth Table” and circuit symbol. A Truth Table is simply a table which shows each and every possible input and its corresponding output. You will need to memorise both for the exam, there are no shortcuts and no ways around this. Fortunately, they are not difficult to remember.
NOT
Circuit diagram and symbol:
NOT gates are otherwise known as inverters, they flip whichever value is put in. There is only one input and one output in a NOT gate.
NOTE: can you see the little circle after the triangle? That’s essential – do NOT miss this off when you draw a NOT gate. If you leave it off, it becomes the symbol for a buffer and that’s something very different. OCR HAVE specified this in their mark schemes and you will be marked incorrect if you leave this out.
Truth Table:
AND
Circuit diagram and symbol:
AND gates perform multiplication on TWO inputs. They will only output a ONE if ALL inputs are ONE. They will otherwise output ZERO.
Truth Table:
OR
Circuit diagram and symbol:
OR gates perform addition on TWO inputs. They will output a ONE if ANY input is a ONE. They will otherwise output ZERO.
Truth Table:
Circuits and problem solving
On their own, a single logic gate doesn’t do a great deal. However, by combining them we can produce useful output. In the exam you will be shown diagrams consisting of multiple logic gates joined together (usually only two to three) and then you will need to do one of the following:
- Identify the gates used.
- Write out the logical expression for the circuit.
- Complete a truth table for the circuit shown.
Occasionally these are reversed. For example, you may be given a truth table which is complete and then you have to say which gate it belongs to or you may be given the expression and then you have to draw the diagram.
Identifying the gates is simple, but only possible if you have memorised the symbols used. There is nothing more to it – you either remember the symbols or… you don’t! There have been repeated exam questions where you have to simply write the name of a gate down.
Drawing circuits
If you are given a logic expression, it is possible to draw out the circuit that it represents by just reading through the expression and drawing gates as you go. Take the following exam question:
This question is ideal in that it shows you exactly how you should approach this kind of task. First, examine the expression you have been given and identify the inputs and outputs. In this case “P” is the output – and therefore needs to go at the end of the diagram. The inputs are any letters in the expression, in this case there are three different letters – A, B and C. Therefore, we need to draw three different inputs at the start (left) of the diagram.
To draw the circuit, break the expressions down and draw the appropriate symbol for each. In this case the expression is helpfully broken up using brackets and we all know from our Maths GCSE that brackets are used to show something that happens first. The expressions we have are:
- A OR B
- AND
- NOT C
First, tackle A OR B – because it’s in brackets! This results in:
Next, we need to deal with NOT C – which is a simple NOT gate:
We can now AND together the result of these two gates to achieve the final diagram:
You will not always be given a nice, partially completed diagram like this but if you follow the method of identifying outputs and inputs and placing these on your diagram first you should be fine.
What about doing this the other way around and writing out the expression for a given circuit?
What is the logical expression for the following circuit?
There are many ways of achieving the answer. One technique is to work backwards from the end – S.
The output in this diagram is the letter S and this comes directly out of an AND gate. We can begin by writing this down:
S = AND
This is deliberately spaced out. AND needs TWO inputs, therefore there must be something either side of it in the expression!
The next step is to continue backwards, following one line at a time, filling in each gate as we go. The next gate in line is an OR gate:
This OR gate has two inputs – A OR B. These are placed in brackets because they happen before the AND:
S = (A OR B) AND …
Finally, follow the second line from the AND gate and we find another OR gate:
This leaves us with the final expression for this circuit:
S = (A OR B) AND (C OR D)
Truth tables for expressions
To prove how a circuit will behave a truth table can be produced. Much like creating a logic expression for a given circuit, making a truth table is a matter of breaking the problem down into steps.
Using this circuit, we will now create the associated truth table:
S = (A OR B) AND (NOT C)
Step 1: Write out all inputs in a table.
| A | B | C |
Step 2: Write out all possible binary inputs – this is easier than it sounds, simply count up in binary from zero until all inputs are one.
| A | B | C |
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
Step3: Now take each of the expressions one at a time and add them to the truth table as a new column.
S = (A OR B) AND (NOT C)
| A | B | C | A OR B | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
S = (A OR B) AND (NOT C)
| A | B | C | A OR B | NOT C | |
| 0 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 1 | 0 | 0 | |
| 0 | 1 | 0 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 0 | |
| 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 |
Step 4: Now we have evaluated both sides of the expression, all that remains is a final AND. Add this to the table:
S = (A OR B) AND (NOT C)
| A | B | C | A OR B | NOT C | (A OR B) AND (NOT C) | |
| 0 | 0 | 0 | 0 | 1 | 0 | |
| 0 | 0 | 1 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | 1 | |
| 1 | 0 | 1 | 1 | 0 | 0 | |
| 1 | 1 | 0 | 1 | 1 | 1 | |
| 1 | 1 | 1 | 1 | 0 | 0 |