Logic Gates and Logic Circuits

A logic gate is a basic building block of a digital circuit. Each gate has one or more inputs and produces a single output that depends on its input or inputs. Many logic gates can be joined together to make complex circuits that carry out processing.

Each logic gate has a symbol, which is used in circuit diagrams, and its own truth table, which shows the output for every possible combination of inputs.

You can think of the inputs to a logic gate as 1s and 0s. These values come from the voltage in the circuit: a high voltage counts as 1 (True) and a low voltage counts as 0 (False). The output is usually labelled Q.

Note In Paper 1, logic expressions are written with the words AND, OR, NOT, NAND, NOR and XOR, for example X = (A AND B) OR NOT C. Some books also use the Boolean algebra symbols: A . B for AND, A + B for OR, A ⊕ B for XOR, and a bar over a letter for NOT. These notes use the words.

A logic expression (also called a Boolean expression) describes, with letters for the inputs and these operators, which combinations of inputs give an output of 1.

The NOT gate takes a single input and flips it to its logical opposite:

• if the input is 1 (True), the output is 0 (False)
• if the input is 0 (False), the output is 1 (True).

The logic expression for this gate is Q = NOT A. In symbols it is written as A with a bar over it.

The AND gate takes two inputs and gives an output of 1 (True) only if both inputs are 1 (True). This is what you would expect: if you asked for fish and chips and did not get both, you would be disappointed.

The logic expression for this gate is Q = A AND B. In symbols it is written Q = A . B, where the dot means AND.

The OR gate takes two inputs and gives an output of 1 (True) if either one of the inputs is 1 (True), or both are.

The logic expression for this gate is Q = A OR B. In symbols it is written Q = A + B, where the plus sign means OR.

The XOR gate takes two inputs and gives an output of 1 (True) if either input is 1 (True), but not both. Its name is short for exclusive OR, and it is sometimes called EOR. Put another way, the output is 1 only when the two inputs are different.

The logic expression for this gate is Q = A XOR B. In symbols it is written Q = A ⊕ B, where ⊕ means XOR.

The NAND gate (NOT AND) combines the logic of an AND gate and a NOT gate: it gives the opposite of the output of an AND gate. So its output is 0 only when both inputs are 1.

The symbol for a NAND gate combines the symbols for the two gates: the AND shape, with the small circle from the NOT gate on its output.

The logic expression for this gate is Q = A NAND B, which is the same as Q = NOT (A AND B).

The NOR gate (NOT OR) combines the logic of an OR gate and a NOT gate: it gives the opposite of the output of an OR gate. So its output is 1 only when both inputs are 0.

The symbol for a NOR gate combines the symbols for the two gates: the OR shape, with the small circle from the NOT gate on its output.

The logic expression for this gate is Q = A NOR B, which is the same as Q = NOT (A OR B).

This table puts the truth tables of the five two-input gates together, so you can compare them:

In Paper 1, every gate except the NOT gate has exactly two inputs. So an expression such as A AND B AND C is drawn with two AND gates: the first works out A AND B, and the second ANDs that result with C. In the same way, A OR B OR C needs two OR gates.

A digital electronic circuit in a computer system is usually made up of millions of logic gates, and each circuit is designed to carry out a particular job. A logic circuit is a set of logic gates joined together to produce outputs from inputs. Real circuits can be very complex, so the ideas are shown here with a control circuit made of just a few gates.

This circuit controls an alarm. The alarm sounds if motion is detected and it is between 20:00 and 06:00. It also sounds if the temperature goes above 30 °C, whatever the time.

The circuit has three inputs, labelled T, M and C:

• The temperature sensor (T) gives 1 if the temperature is over 30 °C, otherwise 0.
• The motion sensor (M) gives 1 if motion is detected, otherwise 0.
• The clock (C) gives 1 if the time is between 20:00 and 06:00, otherwise 0.

There is one output: the alarm (A), which sounds if it receives a 1 and stays silent otherwise.

A whole circuit also has a truth table. It shows every possible combination of inputs together with the output each one gives. Remember: T is temperature, M is motion, C is the clock and A is the alarm.

There are eight possible combinations of inputs, and five of them make the alarm sound: the rows where A is 1. They are:

• whenever T is 1 (the temperature is above 30 °C)
• whenever M is 1 (the motion sensor detects movement) and C is 1 (the time is between 20:00 and 06:00).

Every logic circuit can also be written as a logic expression. A logic expression describes the combinations of inputs that give an output of 1. From the truth table, that happens when T is 1, or when M is 1 and C is 1. So the expression for the circuit is:

A = (M AND C) OR T

In symbols this is A = (M . C) + T.

Notice that you do not write (M = 1 AND C = 1) OR T = 1. The "= 1" is understood: a letter on its own in an expression means that input is 1. To say an input must be 0, write NOT in front of it. For example, A = M AND NOT C means the output is 1 when M is 1 and C is 0.

Each input can only be 1 or 0. So a circuit with 2 inputs has 2² = 4 possible combinations of inputs, and its truth table has 4 rows. With 3 inputs there are 2³ = 8 combinations. In general, n inputs give 2ⁿ combinations.

To make a truth table for a circuit with 3 inputs, A, B and C, first work out how many rows you need: 2³ = 8. Then draw a column for each input, with 8 rows. Fill in the inputs by counting up in binary from 000 to 111: column C goes 0, 1, 0, 1, ..., column B goes in pairs 0, 0, 1, 1, ..., and column A is four 0s then four 1s. This way no combination is missed or repeated.

When you are given a circuit diagram, break down the logic of each gate in the circuit. Take this circuit:

• The truth table needs 4 rows, because there are 2 inputs (A and B): 2² = 4.
• The truth table needs 5 columns: 2 for the inputs (A and B) and 3 for the logic gates in the diagram (AND, OR and NOT).

Before you fill in the truth table, work out the expression for the output of each gate. For example, the AND gate has inputs A and B, so its output is A AND B. Keep track of each gate’s output by writing it on the line in the circuit diagram. Do not try to keep it all in your head, or you may make a mistake. Here is the diagram with the output of each gate written on it:

Now use these expressions as column headings. The final output is called Q.

Take this logic expression:

Q = (A OR B) AND (NOT C AND A)

• The truth table needs 8 rows, because there are 3 inputs (A, B and C): 2³ = 8.
• The truth table needs 7 columns: 3 for the inputs and 4 for the operators in the expression (two ANDs, one OR and one NOT).

Start by drawing the table. Put the inputs in the first columns, on the left.

Next, there are two parts of the expression in brackets. These must be worked out first, before the AND that joins them. It does not matter which bracket you do first. A OR B is straightforward. However, before you can work out NOT C AND A, you must work out NOT C.

Finally, work out the AND that joins the two brackets. This table shows the operations in a logical order:

Look at the last two columns: they are identical. This is an example of spotting, from the truth table, that an expression can be simplified. A simpler expression can carry out the same logic as a more complex one. Here, NOT C AND A gives the same output as (A OR B) AND (NOT C AND A).

Circuit diagrams, truth tables and problem statements can all be written as a logic expression. From any one of them you can work out the logic expression, and the other way round: from an expression you can make a truth table or a circuit diagram, or even write a problem statement.

Take this circuit diagram:

Take each gate in turn, working from left to right, and write an expression for that part of the circuit on its output line.

The NOT gate (blue box). The input is C, so the output is NOT C. Write NOT C on the output line.

The first AND gate (pink box). One input is A and the other is NOT C, so the output is A AND NOT C. Write A AND NOT C on the output line.

The OR gate (yellow box). One input is A and the other is B, so the output is A OR B. Write A OR B on the output line.

The second AND gate (purple box). One input is A OR B and the other is A AND NOT C, so the output is (A OR B) AND (A AND NOT C). Write this on the output line.

This final output is the expression for the whole circuit:

Q = (A OR B) AND (A AND NOT C)

• You do not actually need the brackets around A AND NOT C, but they do no harm and make the expression easier to read.
• Breaking the expression up like this is also useful when you need to draw a truth table for part of a circuit.

A problem statement describes in words when a system should switch something on. Take this one:

Sam and Zac live in a house with a smart heating system. The system turns the heating on if either of them is at home and the temperature drops below 18 °C. The smart system can be switched off completely with an override button.

• A temperature sensor returns 1 if the temperature drops below 18 °C, and 0 otherwise.
• Sam’s and Zac’s mobile phones connect to the WiFi when they are at home, and the system can sense this: 1 means the phone is connected to the WiFi, 0 means it is not.
• The override button returns 1 if the system is switched off, and 0 otherwise.
• The heating is switched on and off by an actuator. When the actuator is 1, the heating is on.

In Boolean algebra symbols, the same expression is written with . for AND, + for OR and a bar over B for NOT B.

Once you have the expression, you can build the logic circuit and the truth table from it in the usual way. For the heating system the circuit needs four gates: a NOT gate on B, an OR gate for S and Z, an AND gate that joins the OR output with T, and a final AND gate that joins NOT B with that result to give H. With four inputs, its truth table would have 2⁴ = 16 rows.

Sometimes you are given a truth table and asked to write the logic expression. Take this one:

First check whether the table matches the truth table of one of the two-input gates. It is useful to learn the gate truth tables by heart for questions like this. This table does not match any of them.

Next, look only at the rows with an output of 1, because an expression describes the combinations of inputs that give an output of 1. This is very important: you do not need to worry about the 0s.

In this table, the output is 1:

• whenever A is 0: this logic is NOT A
• or whenever B is 1: this logic is B.

So the expression is:

Q = NOT A OR B

Now take a truth table with three inputs. The rows are numbered so they can be talked about:

Focus on the rows where the output is 1 (rows 3, 4, 5, 7 and 8), and look for a pattern in their inputs.

If you cannot see a pattern, there is a method that always works. Write one AND term for each row where the output is 1, using NOT for each input that is 0 in that row, and join the terms with OR. For the simple truth table in the last section this gives (NOT A AND NOT B) OR (NOT A AND B) OR (A AND B). It is longer than NOT A OR B, but it is also correct, because it gives exactly the same truth table.

The operators in a logic expression have an order of precedence, which says which operations are worked out first:

1. Brackets
2. NOT
3. AND
4. OR

Some gates combine more than one basic logic operation. For example, a NAND gate combines AND and NOT. So you must also know where these extra operators come in the order. Operators on the same line have equal precedence and can be worked out in any order:

1. Brackets
2. NOT
3. AND, NAND
4. OR, NOR, XOR

Note You may sometimes see a different order of precedence, especially for XOR. In an exam you should not lose marks if the order of precedence is not completely clear, and exam expressions usually use brackets to make the order clear.

Think about how you would draw the logic circuit for this expression:

Q = A AND B OR C

You might draw it in one of two ways:

The correct diagram is option A. The order of precedence says AND is worked out before OR, so the AND must be carried out first.

It is very easy to make a mistake with precedence when you are given an expression. It helps to add brackets to remind you of the order: Q = (A AND B) OR C.

The two options are not the same. You can prove this with a truth table for each one: the outputs are different in rows 2 and 4.

Now work through a harder example. Here is the expression:

Q = (A OR B) AND (NOT C AND A)

Remember the order of precedence: brackets, then NOT, then AND and NAND, then OR, NOR and XOR.

A circuit diagram normally has the inputs on the left and the output or outputs on the right. So start by writing A, B and C on the left of the page and Q on the right.

Before you add any gates, count how many of each gate you need. This expression has two AND operators, one OR operator and one NOT operator, so the diagram needs these four gates.

Step 1: the final AND gate. The last operator to be worked out is the one between the two brackets: an AND. Start by drawing an AND gate just before the output Q, and connect its output to Q.

Step 2: the OR gate. Now look at either of the brackets that feed into this AND gate. On the left is (A OR B). This needs an OR gate, so draw it to the left of the AND gate, with inputs A and B, and connect its output to one of the inputs of the AND gate. It does not matter which input you use.

Step 3: the NOT gate and the second AND gate. Now take the bracket on the right: (NOT C AND A). NOT has a higher precedence than AND, so NOT C must happen first. Draw a NOT gate with its input from C, and its output going into one input of a second AND gate. Place this second AND gate between the NOT gate and the final AND gate, and connect its output to the final AND gate.

Step 4: the final connection. Connect the other input of the second AND gate to A. When several gates take the same input, like A here, draw a branch in the line, with a dot to show the join.

In a busy circuit, lines may cross. Look at the small curve in the branch from A where it crosses the line from B to the OR gate: the curve shows that the two lines are not connected.

To draw a circuit diagram from a truth table, you need to write the logic expression first. Take this truth table:

Here, Q is 1 when A is 1 AND (B is 1 OR C is 1). So the expression for the truth table is:

Q = A AND (B OR C)

Now draw the circuit diagram from the expression in the usual way: an OR gate for B OR C, and an AND gate that joins A with the output of the OR gate.