Boolean logic
Quick links 
Hardware and software 
Boolean logic 
Software classification 
Systems architecture 

Syllabus content
Content  Additional Information  

Construct truth tables for the following logic

Students do not need to know about or use NAND, NOR and XOR logic gates. 

Construct truth tables for simple logic circuits. Interpret the results of simple truth tables.  Students should be able to construct truth tables which contain up to three inputs.  
Create, modify and interpret simple logic circuit diagrams. 
Students should be able to construct simple logic circuit diagrams which contain up to three inputs. Students will only need to use AND, OR and NOT gates within logic circuits. Students will be expected to understand and use the following logic circuit symbols: 
Boolean logic (from the BBC)
Boolean
The Boolean data type has only two values: true or false. These values are used to control the flow of the execution of programs. Boolean values are found by comparing other data values. The results of these comparisons may be combined in Boolean expressions.
Logic gates
Many electronic circuits have to make decisions. They look at two or more inputs and use these to determine the outputs from the circuit. The process of doing this uses electronic logic, which is based on digital switches called gates.
Logic gates allow an electronic system to make a decision based on a number of its inputs. They are digital electronic devices. Each input and output of the gates must be one of two states:
 true or 1 or 'on'
 false or 0 or 'off'
A single digital signal can be either on or off  for example, a light with one switch can be on or off. However, if there is more than one signal, there are more than two possible states. For example, if two signals are present there are four possible combinations: on/on, on/off, off/on and off/off.
Logic gates are the building blocks of digital technology. There are many types of logic gates, which all work in different ways.
This is a NOT gate. The output is always exactly the opposite to the input.


This one is an AND gate. It needs both inputs ‘on’ to work.


This is an OR gate. It has two inputs and either input – or both – need to be ‘on’ to give a positive output.


This is an XOR gate. Either input – but not both – needs to be on to get a positive output.

In a logic gate, each combination can be made to produce a different outcome. Binary numbers reflect the two states  on and off, 1 and 0, true and false  within the CPU's transistors. Logic gate calculations can also be represented as truth tables.
Boolean algebra
NOT gate
A NOT gate has just one input. The output of the circuit will be the opposite of the input. If 0 is input, then the output is 1. If 1 is input, then 0 is output.
If A is the input and Q is the output, the truth table looks like this:
A  Q 

1  0 
0  1 
The Boolean expression is written as Q = NOT A.
There is only a single input to this logical circuit (A) and so there can only be two optoins for the truth table. A can be 0 or A can be 1.
AND gate
An AND gate can be used on a gate with two inputs. AND tells us that both inputs have to be 1 in order for the output to be 1.
The truth table would look like this:
A  B  Q 

0  0  0 
0  1  0 
1  0  0 
1  1  1 
The Boolean expression is written as Q = A AND B.
For this truth table there are two inputs so there will be four options, (A can be 0 or 1 and B can be 0 or 1) when all of the possibilities are combined.
OR gate
The OR gate has two inputs. One or both inputs must be 1 to output 1, otherwise it outputs 0.
The truth table would look like this:
A  B  Q 

0  0  0 
0  1  1 
1  0  1 
1  1  1 
The Boolean expression is written as Q = A OR B.
XOR gate
The exclusive OR gate works the same as an OR gate, but will output 1 only if one or the other (not both) inputs are 1.
The XOR gate is indicated with the extra curved line to the left of the main shape.
The truth table would read like this:
A  B  Q 

0  0  0 
0  1  1 
1  0  1 
1  1  0 
The Boolean expression is written as Q = A XOR B.
Boolean logic  Complex logic gates
Logic gates can be built up into chains of logical decisions. Some logic gates may have more than two inputs. The diagram below shows a complex logic gate combining three simple gates.
Altogether there are three inputs and eight possible outcomes. To solve the truth table below, first find D, then E and finally Z. Complete a whole column before moving on to the next column. D depends only on A, E depends on B and C, and Z depends on E or D.
This logic gate truth table is written as:
A  B  C  D = NOT A  E = B AND C  Z = D OR E 

0  0  0  1  0  1 
0  0  1  1  0  1 
0  1  0  1  0  1 
0  1  1  1  1  1 
1  0  0  0  0  0 
1  0  1  0  0  0 
1  1  0  0  0  0 
1  1  1  0  1  1 
This circuit would be written as Z = D OR E or Z = NOT A OR (B AND C).
In the example above there are three possible inputs, A, B, C. For this truth table there will be eight potential options, (A can be 0 or 1 B can be 0 or 1 and C can be 0 or 1) when all of the possibilities are combined.
Logic gates in the CPU
The following example demonstrates how the ALU uses logic gates to perform binary addition. It combines two gates, in parallel. There are two inputs and each gate has a single output  so in total there are two outputs, with four possible outcomes.
The Boolean expressions for this circuit are:
S = A XOR B
C = A AND B
The truth table for this circuit is:
A  B  S = A XOR B  C = A AND B 

0  0  0  0 
0  1  1  0 
1  0  1  0 
1  1  0  1 
Half adder  binary addition
This gate models a 1bit binary sum. The possible calculations of a 1bit binary sum are:
 0+0=0
 0+1=1
 1+0=1
 1+1=10
S and C together represent the output of the sum of 'A + B'. Each gate can only output a single bit  a number with one binarey place value. 1+1 creates 10 which needs 2 place values, so this is an overflow number. In overflow sums, the result is recorded as 0 and the 1 has to be carried. S represents the recorded 0 and C represents the carried 1.
This configuration is called a binary half adder. It is a good way to begin to understand how an ALU is able to perform arithmetic. To perform complete arithmetic that can take account of carry bits and add more than two bits together, two half adders must be combined together to make a full adder.
An ALU uses millions or billions of circuits like this cascaded together to perform calculations.
Boolean logic
Boolean in programming
Boolean algebra is used frequently in computer programming. A Boolean expression is any expression that has a Boolean value. For example, the comparisons 3 < 5, x < 5, x < y and Age < 16 are Boolean expressions.
 The comparison 3 < 5 will always give the result true, because 3 is always less than 5.
 The comparison x < 5 will give the result true when the variable x contains a number less than 5, and false when it contains any number that is greater than or equal to 5. The variable x must contain a number for this comparison to make sense.
 The comparison x < y will give the result true when the variable x contains a value that is 'less than' the value contained by the variable y. Note that in some programming languages the 'less than' operation is only defined for numbers, but in others it is defined for other data types as well.
Computer programmers use Boolean values to control selection and repetition in programs. For example, in a cinema computer system Boolean could be used to program the type of tickets people should get. Here it is written in pseudocode:
NOT, AND, OR
Boolean expressions may combine two or more Boolean values using the operations NOT, AND and OR. This is used in many different algorithms.
For example, a cinema computer system could assess if people under 16 and over 65 are charged the concession rate. This is the algorithm in pseudocode:
In this example, the expression Age < 16 OR Age > 65 will give the value 'true' when the user's age is less than 16 or when it is greater than or equal to 65, otherwise it will give the value 'false'.
It is also possible to create variables that will hold Boolean values for later use.
The variables in this scenario are 'Age', 'EntranceFee' and 'Concession'. 'Age' can be any integer, 'Concession' is used to hold a Boolean value and 'EntranceFee' is set according to the status of 'Concession' (500 or 1000). This can be expressed in pseudocode as follows:
The truth table for this system will be:
Age under 16?  Age 65+?  Concession? 

Yes  No  Yes 
No  Yes  Yes 
No  No  No 
Boolean operations in programming languages
This resource will help with understanding Boolean operations in programming languages. It supports Section 3.2.5 of our current GCSE Computer Science specification (8520). The resource is designed to address the following learning outcomes:
 Use AND, OR and NOT in Boolean expressions
 Combine Boolean operators and relational operators to build complex Boolean expressions.
The AND operator
Let’s start with two expressions that on their own are either True or False:
1. I am 14 years old
2. I am under 1.5 metres tall
You know whether expressions 1 and 2 are correct and so you can answer this expression that joins them with an AND:
3. I am 14 years old AND I am under 1.5 metres tall
We can show the result of this expression with a table that has all of the four permutations, that the True/False values for sentences 1 and 2 can be put together:
Sentence 3 is only True if both sentences 1 and 2 are also True. We can use AND with sentences 1 and 2 because they are both Boolean expressions. In fact the AND operator takes any two Boolean expressions and evaluates to True only if both expressions themselves are True, otherwise it evaluates to False.
To evaluate the overall value of a Boolean expression involving an AND you have to first evaluate the Boolean expressions to the left and the right side of the AND and then use the rules above to work out if it is True or False, for example:
The left hand expression evaluates to False.
There is no need to evaluate the right hand side, regardless of whether it is True or False the whole expression must be False.
The OR operator
Using OR is a very commonplace logical device whenever people are offered a choice:
 Do you take the road on the left or the road on the right?
 Do you have custard or cream?
Each of these choices will (probably) involve choosing one or the other, but not both. This is where the use of OR in computer science differs from its use in natural language  logical OR evaluates to True if one or other of the choices is True, as well as if they are both True. An alternative way to view this is that OR only evaluates to False if the Boolean expressions to the left and the right are both False. There is a further logical operator called XOR (or exclusiveOR) that True AND True True True AND False False False AND True False False AND False False requires either the left or the right side to be True but not both, however, this operator is beyond the requirements of the specification.
In exactly the same way as when evaluating expressions with AND, to evaluate OR you need to evaluate the Boolean expressions to either side of it.
The left hand expression evaluates to True so it doesn’t matter if the right hand expression evaluates to True or False as the overall value will evaluate to True.
The NOT operator
AND and OR are both binary Boolean operators which means they take two Boolean expressions and then give the result. There is another very useful operator that takes only one input (a unary operator) called NOT. NOT is the easiest of the Boolean operators to understand – whatever a Boolean expression evaluates to, if you put a NOT in front of it then it evaluates to the opposite. This is exactly how it is used in natural language: ‘it is raining’ is the opposite to ‘it is not raining’.
NOT is the easiest to evaluate as it inverts whatever Boolean value it precedes as these examples show:
Combining Boolean operators
All three Boolean operators (AND, OR, NOT) can be combined to create complex Boolean expressions. No matter how complicated they become, and how many operators they use, they will always evaluate to either True or False. They can be evaluated by working ‘inside out’. The following examples explain this:
Common pitfall
It makes sense to say ‘3 and 5 are both less than 7’, but if we were to write this directly as a program we would have:
(3 AND 5) < 7
Programming languages have formal ‘grammars’ that require expressions and statements to be written in specific ways and most programming languages have a rule that the left and right side of an AND have to themselves be Boolean expressions and here they are both integers. The correct way to write this expression follows the alternative way of saying the same thing in English, ‘3 is less than 7 and 5 is less than 7’:
(3 < 7) AND (5 < 7)
This is a common mistake when creating complex Boolean expressions in programs. To further complicate things many programming languages have Boolean interpretations of numbers (typically 0 means False and any nonzero number is True) so the expression (3 AND 5) < 7 is logically incorrect but may still be a valid expression in your language. When code is syntactically correct (it does not break any of the rules of the language such as misspelling a variable name or using one = sign instead of ==) but the code does not do what it is intended to, it contains logical errors. They are generally far harder to find than syntax errors.
Boolean logic resources and questions
Slightly helpful video
OK it starts quite straightforwardly and then gets a little tricky when referring to some of the boolean theorems that you do not need to know so do not panic. But its nice to see how it works if you are curious (which you should be if you are taking this course). The equations and theorems that he is using are shown near the bottom of the page.
Boolean algebra can be confusing. This page may help.
Try this interactive question.
We use a form of algebra to write down these circuits, called Boolean Algebra or (logic) named after the mathematician George Boole. In the late 1840's he derived the notation to express in a mathematical form the logical concepts that the early Greek mathematicians and philosophers had identified.
George Boole and Aristotle
Independent Task
Draw the Boolean expression below in your books as a truth table and a diagram.
P = (A OR B) AND C
P = (A AND B) OR (A AND C)
P = (A OR B) AND (A OR C)
Logic in Programming
We need to understand Boolean algebra in order to use many facilities within programming languages. Writing a program requires us to identify a logical process that the computer can follow and we need to be able to provide suitable Boolean expressions for the computer to use when making decisions about what to do next.
We might want our program to stop if one of two things happens, for example if we find a matching item in some data or we reach the end of a data file.
The computer might be given the instruction that says for example, to output the numbers 1 to 5 using a REPEATUNTIL loop:
count =0
REPEAT
count = count +1
OUTPUT count
UNTIL count = 5
This loop REPEATS a block until the variable "count" gets to five.
The computer's CPU will evaluate this expression using the logic:
This is, of course using the OR gate logic.
We will often require the computer to evaluate a logical expression in order to make a decision.
IF x > 10 AND y > 12 THEN .........
This tells the computer to check the values of x and y in the program and to do 'something' if both x is bigger than 10 and y is bigger than 12.
WHILE x < 10 AND NOT(end of file) DO
This tells the computer to check if x is less than 10 and that it has not reached the end of the data file. If both things are true it carries on and does what it is asked, but if they are not both true it will stop and move on to the next instruction in the program.
Using your Python Programming booklet and in your books:
 Find a program in Python that demonstrated an AND gate.
 Write the code, describe the logic below it and draw a logic diagram and truth table.
 Extension: Do the same for an OR, NOT, NAND, AND OR or any other combinations you can find.
Now in your books try these questions:
1. Draw a truth table for each of the following Boolean expressions:
a) NOT(A OR B) b) NOT(A)OR NOT(B)
c) A AND NOT(B) d) A AND NOT(B OR C)
2. Draw the logic circuits for each of the expressions above.
3. Draw truth tables for A AND (B OR C) and for (A AND B) OR (A AND C)
a) Calculate: 3x(5+6) and 3x5 + 3x6
b) What do you notice?
4. Draw the logic circuit for the logic statement with the inputs L, F and A and the output X:
x = 1 if (L is NOT 1 and F = 1) Or (F IS NOT 1 AND A is 1)
Example answer
1. Draw a truth table for each of the following Boolean expression NOT(A OR B)
A  B  A OR B  NOT(A OR B) 

0  0  0  1 
0  1  1  0 
1  0  1  0 
1  1  1  0 
Extension
 Draw a logic circuit for A OR (B AND C) OR D
 How many rows must the truth table have?
 Complete the truth table
 De Morgan's Law says NOT(B OR C) is the same as NOT(B) AND NOT(C). Show this is true by completing the truth tables.
 The NAND gate is an important type of gate and is used to create a circuit called a flipflop. Investigate what is a flipflop, what does it do and why is it important?
Additional work/ideas
Use Logic.ly to show the universality of the NAND gate. Screenshot the appropriate evidence.
You should construct the truth tables for each logical arrangement and then create the logic circuit for each arrangement using logic.ly and demonstrate that the outputs for each arrangement is identical.
In a similar way use Logicly to show the universality of the NOR gate. Screenshot the appropriate evidence.
You should construct the truth tables for each logical arrangement and then create the logic circuit for each arrangement using logic.ly and demonstrate that the outputs for each arrangement is identical.
Use truth tables and logic.ly to confirm that the following are all true. Note the algebraic form of the gate or symbol. These equations may be used in the examination. While you may only be asked questions using the first 3 symbols, as the other 4 can be made from the first 3 one never knows...
Use Logicly to show that all of the following Laws of Logic are true.
Please note the use use of the algebraic form of these logical theorems and the use of a constant in the example below showing the Identity Law.
X  0  X OR 0  

0  0  0  
1  0  1 
Please note the use use of the apostrophe (as NOT) in the algebraic form of these logical theorems in the example below showing the Complement Law.
X  X'  X OR X'  

0  1  1  
1  0  1 
Finally use logic.ly to create two cascading full adders. You should be able to add two double digit binary numbers and get the right anwer, whatever the input. In this example1 1 is being added to 10 and gives the answer 1 0 0.
Further reading
Here are a few links to web sites and intersting things that you really should read in your own time. There may be a sentence or two in one of these sites that might spark a difficult concept or resolve a confusing idea or may simply be a better explanation that suits you and eanables you to fully understand the points that the examiner is trying to make.
A history of early programming that explains compilers and assemblers in more detail.
3.1 Fundamentals of algorithms
 3.1.1 Representing algorithms
 3.1.2 Efficiency of algorithms
 3.1.3 Searching algorithms
 3.1.4 Sorting algorithms
3.2 Programming
 3.2.1 Data types
 3.2.2 Programming concepts
 3.2.3 Arithmetic operations in a programming language
 3.2.4 Relational operations in a programming language
 3.2.5 Boolean operations in a programming language
 3.2.6 Data structures
 3.2.7 Input/output and file handling
 3.2.8 String handling operations in a programming language
 3.2.9 Random number generation in a programming language
 3.2.10 Subroutines (procedures and functions)
 3.2.11 Structured programming
 3.2.12 Robust and secure programming
 3.2.13 Classification of programming languages
3.3 Fundamentals of data representation
 3.3.1 Number bases
 3.3.2 Converting between number bases
 3.3.3 Units of information
 3.3.4 Binary arithmetic
 3.3.5 Character encoding
 3.3.6 Representing images
 3.3.7 Representing sound
 3.3.8 Data compression
3.4 Computer systems
 3.4.1 Hardware and software
 3.4.1 Operating systems
 3.4.2 Boolean logic
 3.4.3 Software classification
 3.4.4 Systems architecture
3.5 Fundamentals of computer networks
3.6 Fundamentals of cyber security
3.7 Ethical, legal and environmental impacts of digital technology on wider society, including issues of privacy
 3.7.1 Ethical impacts of digital technology on wider society
 3.7.2 Legal impacts of digital technology on wider society
 3.7.3 Environmental impacts of digital technology on wider society
 3.7.4 Issues of privacy
3.8 Aspects of software development
Glossary and other links
Why does a computer need an operating system?