## Boolean logic

 Quick links 3.4.1 Hardware and software 3.4.2 Boolean logic 3.4.3 Software classification 3.4.4 Systems architecture Useful links

### Syllabus content

Construct truth tables for the following logic
gates:

• NOT
• AND
• OR.
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

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

Boolean algebra and truth tables can be used to describe logical expressions. The most common Boolean operators are ANDOR and NOT (always in capitals). Each operator has a standard symbol that can be used when drawing logic gate circuits.

# 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

This gate models a 1-bit binary sum. The possible calculations of a 1-bit binary sum are:

1. 0+0=0
2. 0+1=1
3. 1+0=1
4. 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 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 exclusive-OR) 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 non-zero 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

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.

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

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 REPEAT-UNTIL 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.

1. Find a program in Python that demonstrated an AND gate.
2. Write the code, describe the logic below it and draw a logic diagram and truth table.
3. 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)

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

1. Draw a logic circuit for A OR (B AND C) OR D
2. How many rows must the truth table have?
3. Complete the truth table
4. 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.
5. The NAND gate is an important type of gate and is used to create a circuit called a flip-flop. Investigate what is a flip-flop, what does it do and why is it important?

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. 