An introduction to Boolean logic
Introduction
Computers are made up of millions and millions of switches. These switches can be grouped together to form codes. These codes can be used to represent any piece of data. We can also use these switches to control what happens in a computer. A computer needs to be able to say things like:
-
- if both this switch and that switch is on, then do this action.
- if either one of these switches is on, do this action.
- if this switch is on, don't do that action. If it is off, do that action.
These kinds of sentences use 'logic'. The manipulation of statements that are either true or false and result in an output that is either true or false is called Boolean logic and is an area of algebra named after a 19th Century Mathematician. We can express Boolean logic using algebraic expressions and we can use logic diagrams as well. The component parts of a logic diagram are called 'logic gates'. Part of the arsenal of any programmer is the ability to manipulate Boolean expressions and that is what this part of the syllabus is about. We are going to introduce the notation that is used by exam boards and the basic logic gates. Unfortunately, there are a number of different versions of notation and different symbols in use but we will only use the ones that the exam boards have said they will use in exams!
Logic gates
Logic diagrams are made up of a number of smaller diagrams, known as 'logic gates'. A logic gate is a hardware component that has some inputs and an output and the gate controls the output depending upon the inputs. You can combine these gates into complicated electronic circuits, which are then added to other components into an 'integrated circuit'. You may have handled integrated circuits - that's what a CPU or a RAM is.
Each logic gates has at least one input and only a single output, which depends on the inputs. If a logic diagram has a total of two inputs, then there are two to the power two = 4 possible unique combinations of inputs. If a logic diagram has a total of three inputs, then there are two to the power three = 8 possible unique combinations of inputs. If a logic diagram has a total of four inputs, then there are two to the power four = 16 possible unique combinations of inputs. If a logic diagram has a total of S inputs, then there are 2s or two to the power S possible unique combinations of inputs. This is useful to know because it helps you draw up a truth table for any diagram (more on truth tables later)!
Before we look at more complicated diagrams, let's look at the basic logic gates first. The most important to get to know are the AND, OR and NOT logic gates.
The AND logic gate
This logic gate gives an output if *all* of the inputs are true. If any of the inputs are false then the output is a zero.
This kind of logic can be applied to all manner of situations apart from a computer. For example, pupils should stand up if they own a bicycle and own a skateboard. The output is 'standing up'. The inputs are 'owning a bicycle' and 'owning a skateboard'. You only stand up if you both own a bicycle AND you own a skateboard. This situation could be represented using the AND logic gate easily, rather than trying to write out accurately who should stand up.
We can represent all of the different possible situations using a 'truth table'. The truth table for the AND gate looks like this:
It simply shows the output for every possible permutation for the AND gate.
To show this logic in Boolean notation, we would write:
A Λ B = C
This is read as, 'A AND B equals C'.
The far easier notation to use is AB = C (and sometimes A.B), especially when working with Boolean algebraic equations.
The OR logic gate
This logic gate gives an output if *either* of the inputs are true (or both of them are true). If both of the inputs are false then the output is a zero.
Using our example from before, pupils should stand up if they own a bicycle OR own a skateboard. The output is 'standing up'. The inputs are 'owning a bicycle' and 'owning a skateboard'. You stand up if you either own a bicycle OR you own a skateboard (or indeed if you own both). You stay seated if you neither own a bicycle nor own a skateboard. Again, this situation could be represented using the OR logic gate easily, rather than trying to write out accurately who should stand up and who should stay in their seat.
We can represent all of the different possible situations using a 'truth table'. The truth table for the OR gate looks like this:
It shows the output for every possible permutation for the OR gate.
To show this logic in Boolean notation, we would write:
A V B = C
This is read as, 'A OR B equals C'.
The far easier notation to use is A + B = C especially when working with Boolean algebraic equations.
The NOT logic gate
This logic gate only has one input. If the input is true, the output if false. If the input is false, the output is true. The truth table for the NOT gate looks like this:
To show this logic in Boolean notation, we would write:
¬A = C
This is read as, NOT A equals C'.
The far easier notation to use is A = C especially when working with Boolean algebraic equations.
The XOR logic gate
This logic gate has two inputs. If both inputs are the same, then the output is a 0. If both inputs are different, then the output is a 1. The truth table for the XOR gate looks like this:
To show this logic in Boolean notation, we would write:
A V B = C
This is read as, 'A EXCLUSIVE OR B equals C' (EXCLUSIVE as opposed to a normal OR gate, which is INCLUSIVE i.e. the output is a 1 when both inputs are a 1.)
The far easier notation to use is A ⊕ B = C especially when working with Boolean algebraic equations.
The NAND gate
The NAND gate is the same as an AND gate followed by a NOT gate. It inverts the output from an AND gate.
The gate look like this:
The truth table looks like this:
To show this logic in the Boolean notation that OCR uses for questions, we would write:
A Λ B = C
The far easier notation to use in Boolean equations is A.B = C
The NOR gate
The NOR gate is the same as an inverted OR gate. It inverts the output from an OR gate.
The gate looks like this:
The truth table looks like this:
To show this logic in the Boolean notation that OCR uses for questions, we would write:
A V B = C
The far easier notation to use in Boolean equations is A + B = C