Combining Gates & Solving Problems

Courses Computational Thinking, Algorithms & Programming Boolean Logic Combining Gates & Solving Problems

We have seen how logic circuits can be drawn as diagrams with inputs and outputs, and we can use truth tables to map out the range of possible results from these circuits.

However, we can also combine a series of logic gates to produce more complex circuits. This allows us to solve problems and identifies logical structures in how a computer works.

In this lesson, we’ll learn about:

  1. Combining logic gates to produce simple circuits.
  2. Applying logical diagrams & operators in truth tables to solve problems.
Media Attachments: Presentation Video

1. Producing Simple Circuits

We can start to put these logic gates together to make larger circuits. Each circuit can be represented as a Boolean expression, which will always start with an output, usually called Q.

To solve these, start with the brackets on the inside and work outwards.

Worked Example 1

Q = A AND (B AND C)

Step 1 – Start with the brackets, this is the “B AND C” part.

An AND gate
Figure 1 – an AND gate with the inputs B & C.

Step 2 – Add the outer expression, this is the “A AND” part.

An And gate leading into another And gate.
Figure 2 – the result of B AND C is used as input on another AND gate with A.

Worked Example 2

Q = NOT (A OR B)

Step 1 – Start with the brackets, this is the “A OR B” part.

An Or gate
Figure 3 – an OR gate with the inputs A & B.

Step 2 – Add the outer expression, this is the “NOT” part.

An Or gate leading into a Not gate.
Figure 4 – the result of A OR B is then NOTed.

Worked Example 3

Q = (A OR B) AND NOT C

Step 1 – Start with the brackets, this is the “A OR B” part.

An Or gate
Figure 5 – an OR gate with the inputs A & B.

Step 2 – Add the outer expression, this is the “AND NOT C” part.

An Or gate followed by an And gate with one of its inputs NOTed.
Figure 6 – the result of A OR B is used as input on an AND gate with NOT C.

Further Thought

Can you double NOT a circuit? Research this online.

2. Solving Problems

We have seen how we can use Boolean algebra to represent some circuits. We can build up truth tables to show all the inputs and all the possible outputs for any circuit. We can then use this to work out which combination of inputs will give us a TRUE output.

The way to do this is to start small and build up your truth table column by column.

In your exam you might need to complete a truth table for a given Boolean expression, or draw the circuit diagram for a Boolean expression and then plot the truth table.

In order to solve this you can follow some very simple steps:

  1. Build your inputs
  2. Check to see if any of your inputs have been NOTed
  3. Build your expressions from your initial inputs
  4. Look at the final output

Worked Example 1

Let’s look at a simple Boolean expression, Q = A AND NOT B.

Step 1 – Build your inputs

We have two inputs A and NOT B. So we need 4 rows.

ABQ
11
10
01
00

Step 2 – Check to see if any of your inputs have been NOTed

Yes – B has been NOTed, so add a column for NOT B.

ABNOT BQ
110
101
010
001

Notice how all we have done is flip the B column values.

Step 3 – Build your expressions from your initial inputs

Now we need to add the expression by comparing the A column and the NOT B column.

As it is an AND gate, the output will be true if both inputs are true.

ABNOT BA AND NOT BQ
1100
1011
0100
0010

Step 4 – Look at the final output

Our expression is Q = A AND NOT B, so the values in column four is our answer.

ABNOT BA AND NOT BQ
11000
10111
01000
00100

What this means is that there is only one possible input to this circuit that gives a TRUE output. When A = 1 and B = 0.

Worked Example 2

Consider the following expression, Q = (A OR B) AND C.

Step 1 – Build your inputs

First, we have three inputs, so let’s see the truth table outline. We should have 8 rows this time.

ABCQ
111
110
101
100
011
010
001
000

Step 2 – Check to see if any of your inputs have been NOTed

They haven’t so we can skip this step.

Step 3 – Build your expressions from your initial inputs

First, we have A OR B – ignore C for the moment.

ABCA OR BQ
1111
1101
1011
1001
0111
0101
0010
0000

Now we can add the AND C part.

Remember it’s AND – so it’s where we have a 1 in the A OR B column AND we have a 1 in the C column.

ABCA OR B(A OR B) AND CQ
11111
11010
10111
10010
01111
01010
00100
00000

Step 4 – Look at the final output

Our expression is Q = (A OR B) AND C, so the values in column five is our answer.

ABCA OR B(A OR B) AND CQ
111111
110100
101111
100100
011111
010100
001000
000000

This is a quite complex circuit. There are THREE combinations of A, B and C that will give us a TRUE output (remember this is like the lights going on).

The following table shows the combinations of A, B and C that give us a TRUE output.

ABC
111
101
011

Worked Example 3

Consider the following expression, Q = (A AND NOT B) OR (A AND NOT C).

Step 1 – Build your inputs

First, we have 3 inputs so let’s see the truth table outline. We should have 8 rows.

ABCQ
111
110
101
100
011
010
001
000

Step 2 – Check to see if any of your inputs have been NOTed

Yes – we have NOT B and NOT C, so we add these columns.

ABC NOT B NOT CQ
11100
11001
10110
10011
01100
01001
00110
00011

Step 3 – Build your expressions from your initial inputs

First, we have A AND NOT B, so we add this column – again the output is TRUE when both inputs are TRUE, as it is an AND gate.

ABCNOT BNOT CA AND NOT BQ
111000
110010
101101
100111
011000
010010
001100
000110

Now let’s add A AND NOT C.

ABCNOT BNOT CA AND NOT BA AND NOT CQ
1110000
1100101
1011010
1001111
0110000
0100100
0011000
0001100

Now we can build up our final expression where we have a 1 in the (A AND NOT B) column OR we have a 1 in the (A AND NOT C) column.

ABCNOT BNOT CA AND NOT BA AND NOT C(A AND NOT B) OR
(A AND NOT C)		Q
11100000
11001011
10110101
10011111
01100000
01001000
00110000
00011000

Step 4 – Look at the final output

Our expression is Q = (A AND NOT B) OR (A AND NOT C), so the values in column eight is our answer.

ABCNOT BNOT CA AND NOT BA AND NOT C(A AND NOT B) OR
(A AND NOT C)		Q
111000000
110010111
101101011
100111111
011000000
010010000
001100000
000110000

So here we can see that there are only 3 possible inputs to this gate that give us an output of true:

ABC
110
101
100

Further Thought

Why would programmers use truth tables to work out complex logical IF ELSE statements?

Lesson Summary

So to summarise what we’ve learnt in this lesson:

  • You can combine logic gates to draw Boolean expressions.
  • Truth tables can be used to work out the outputs of any Boolean circuit.
  • They can be used to work out the Boolean algebra of any circuit.
  • The truth tables follow four rules.
    • Step 1 – Build your inputs
    • Step 2 – Check to see if any of your inputs have been NOTed
    • Step 3 – Build your expressions from your initial inputs
    • Step 4 – Look at the final output.
Quizzes
Previous Lesson
Back to Module