CS14 : That is logical, captain

Computers are built using electronic components. These include resistors, capacitors and logic gates. Logic gates and combinations of logic gates perform the basic operations of all modern computers. But how do they work? How are they manufactured?

We are learning ...
  • How to construct simple logical operations using atomic logical operations
  • How to represent logic gates as symbols
  • How to construct truth tables for atomic and compound logic operations
  • About basic logic circuits.
So that we can ...
  • Be familiar with the operations ...
    - NOT (negation)
    - AND (conjunction - pessimistic)
    - OR (disjunction - optimistic)
    - XOR (exclusive disjunction)
  • Appreciate that logic operations have precedence
  • State / draw logic gate representations of atomic logical operations
  • Apply compound logical operations NAND and NOR
  • Construct simple truth tables for atomic and compound logical operations
  • Write Boolean expressions for logic circuits (and vice versa)
  • Draw and implement physical electronic logic gates using transistors (theoretically, not electrically!)
    - Half adder
    - Full adder
    - Edge triggered D-Type flip-flop (memory unit)

In 1847, George Boole proposed a new system of thinking called 'propositional logic'. Now it's often called Boolean logic in his honour. One fundamental aspect of Boolean logic involves the use of Boolean variables to represent the existence (True / 1) or absence (False / 0) of objects or events in the real world. For instance, if we represent all sheep using the variable X and all things with horns with the variable Y (Laws of Though, Page 20) ...

Click to enlarge

It should also be possible to represent all situations as a series of decision problems with only True / False responses ...

Click to enlarge

Thus was born a new way of thinking.

Activity 1 Pies (15)

Let's consider a real example of how we can apply propositional logic to the world of Cheese and Onion pies.

From left to right ...
  • Pie
  • Venn diagram showing all components in the world of Cheese and Onion pies
  • A boy crying
  • A speech bubble explaining why the boy is crying
We can use Venn diagrams to visually represent all possible combinations of objects in our little culinary world. 

Task 1.1 Simply a resource

If we consider our world, we have 4 entities to consider; all pies, pies with cheese, pies with onion and pies with cheese and onion.  This gives us 16 different combinations (think binary!)

Download Cheese and Onion Pies.docx for this activity.

OUTCOME : Download, print and discuss the resources.  Stick it in your notebook for reference.

Activity 2 Boolean operations (45)

There are 7 basic logical operations that you need to know ...

Click to enlarge

Task 2.1 Operations, please?

It's often useful to think of logical operations in terms of real world situations. For instance ...

Statement : I will get wet if it's raining AND I'm outside.

This statement only caters for one of the four possibilities for the 'output' (since there are two inputs). The other possible outcomes are ...
  • I won't get wet if it's raining AND I'm not outside
  • I won't get wet if it's not raining AND I'm not outside
  • I won't get wet if it's not raining AND I'm outside.
Boolean variable assignment
  • A = It is raining
  • B = I'm outside
  • Q = I get wet
Boolean expression : Q = A AND B

Try to come up with one example like this (but not necessary to do with raining) for each type of logic operation in the table above. Some of the later ones are a little tricky so don't worry too much if you can't do it.

 : A written explanation in your book including logic statement, Boolean variable assignment and a Boolean expression for each Boolean operation from the table.

Because mathematicians (and computer scientists) like using symbols to confuse other people into thinking they are more intelligent then they are (and also actually for brevity), there are a number of symbols which are used to represent the Boolean operations ...

Click to enlarge

Like in maths, there are precedence rules for Boolean operations (brackets > NOT > AND > OR), however, brackets are normally used around expressions to force precedence where it may be ambiguous.

As we shall see, it is possible and quite expected, that we should be able to chain together this logical atoms to form more complex Boolean expressions.

Activity 3 Logic gates (60)

Logic gates are electronic components which are designed to evaluate Boolean operations in registers, memory chips and processors. There are 7 accepted Logic gate symbols to represent each of the 7 Boolean operation (there is an 8th called a buffer which I haven't included).

Click to enlarge

Note that the last three are combinations of other gates - they have logical equivalence with them. If you want to use these logic gate symbols in your own documents, I've given you them in a zip file called Logic Gate Diagrams.zip which is available from the resources for the lesson.

We can model the operation of these 7 logic gates using software called Logicly.

The Logicly interface
Click to visit

Task 3.1 Jiminys Challenge

Read the following popup and carry out Jiminys Challenge ...

Click to enlarge

You may use Logicly to help you. When you finish, your teacher will check whether your solutions are correct and give you a copy of Logic Gates and Associated Stuff.docx for your notes.

You must take special note of the contents of this document. Read it!

OUTCOME : Hand drawn logic gate symbols and truth tables for all 7 logic gates plus a copy of the worksheet stuck in your notes which you have read. I will ask questions.

For all those Minecrafters out there, here is a couple of videos showing how to make logic gates using Redstone in our favourite game ...

... and here is Steve with is creations.

I've included two resources for you to play with ...

Activity 4 Logic circuits (110)

Logic circuits are made from a series of logic gates connected together with the output from one logic gate often becoming the input for another.

We can represent logic circuits as ...
  • Diagrams composed of one or more logic gates (easy)
  • Boolean expressions composed of one or more Boolean operations (hard)
For logic circuits with 1 input, there are two possible value for the output. For logic circuits with 2 inputs, there are 4 possible outputs. What about 3 inputs? Yes, that's right, 8 possible outputs. In general ...

values of output = 2number of inputs

So, we can combine logic gates into more complex circuits. However, this leads to more complicated behaviour. Luckily, Logicly can help us again!

Consider the following logic system (can you see the relationship with the Boolean expression? More of this later on in the lesson) ...

Click to enlarge

Using Logicly, we can trace the operation of the system one state at a time as shown in the animation which leads to the truth table shown alongside. Take a moment to check that you see the connection ...

Click to enlarge

If we don't have the luxury of a tool to model our logic circuit in, we can use a step-by-step method using the truth table to help us ...

Click to enlarge

Basically, work through each logic gate one at a time and record the output. Assign this a new Boolean variable and use that as the input for the next gate. Build up your truth table a bit at a time.

Task 4.1 Logic circuits as diagrams

Using Logicly (if you need to), construct Truth tables for the following logic circuits. For each one ...
  • Assign Boolean variables to the inputs;
  • Construct a simple truth table by toggling the inputs;
  • Construct a step-by-step truth table using the step-by-step method.
  1. Example one / three inputs / truth table has 8 lines / step-by-step table has 6 columns

  2. Example two / four inputs / truth table has 16 lines / step-by-step table has 7 columns

  3. Example three / three inputs / truth table has 8 lines / step-by-step truth table has 7 columns.

OUTCOME : Sketch of each circuit plus two truth tables whose outputs should agree.

When we do not have the luxury of a diagram to help us, things can get a little trickier. For instance, consider the following proper complicated Boolean expression ...

... and bask in the glory of the animation which explains how to convert it to a logic circuit.

Click to enlarge

We work from 'the inside out' making sure that we calculate the result of a Boolean operation before it is used.

Task 4.2 Expression to diagram to truth table

Using the example above to help you, convert the following Boolean expressions into Logic circuits and then write a step-by-step truth table for each one.  They get successively harder so don't worry if you can't quite manage the last one!

OUTCOME : Screenshots of the logic circuits you built together with the step-by-step truth tables.

Activity 5 Boolean expressions from logic statements (25)

Putting all this together, we should now be able to take a written logical statements consisting of decision problems, convert it into a Boolean expression composed of one or more Boolean operations and represent this as a logic circuit made from logic gates! Nice. Consider ...

Can you see the connection between the written statement and the logic statement? Shout 'yeah' if you can!

Task 5.1 Constructing logic circuits
  1. Construct a logical expression for the following situation ...

    I would like to generate an output, Q, from three inputs, X, Y and Z, such that Q is TRUE if X is FALSE and Z is TRUE or Y is FALSE and Z is FALSE or X is TRUE and Y is TRUE. 

    Now construct a logic circuit and a truth table for this situation

  2. Next, a real world example. 

    Imagine an alarm system with two sensors, A and B and an override switch, C. Construct a logical expression, logic circuit and truth table for the following situation ...

    - The alarm sounds when either of the two sensors are triggered.
    - If the override switch is pressed, the alarm will not sound.

OUTCOME : Suitable notes in your book explaining what you have done.

Activity 6 Physical logic circuits (50)  A Level Only

It is with gratitude that we introduce the transistor.  The transistor is a tiny electronic component which makes all this logical tomfoolery a practical reality.

Click to enlarge

Task 6.1 A video. A LONG video ...

You seriously don't have to watch this video if you haven't got time.  It's nearly an hour long but it's great because it shows how all the logic gates are actually made from tiny electronic components called transistors (and a few resistors thrown in for good measure!).

An introduction to logic gates (47:08)

OUTCOME : Nothing from this.

Activity 7 Half and Full Adders (45)  A Level Only

One practical application of logic circuits is to add binary numbers together inside a component of the microprocessor called the Arithmetic and Logic Unit (ALU) which we shall meet later.

Arithmetic uses logic but it is not the same

The basic component of an binary addition circuit is called a half adder. The circuit comprises one XOR gate and an AND gate, takes to binary inputs and produces two outputs - a sum and a carry bit.

Half adder circuit implemented in Logisim (BinaryAdder.circ)

Task 7.1
 Half Adder

The half adder uses logic gates to simulate the addition of two binary digits. Sketch out a truth table for a half adder in your notebooks using the following headings ...

Explain how this truth table represents the binary addition of two bits.

OUTCOME : Truth table for a half adder

The half adder does not handle the possibility of a carry bit from a previous calculation. Chaining two half adders together gives you a full adder as shown below. This simple circuit is the basis of all mathematical operations in computer systems. 

Behold, the full adder ...

Full adder implemented in Logisim (BinaryAdder.circ)

Task 7.2
 Full Adder

The full adder extends the operation of the half adder to include the option of a carry in from a previous calculation. Therefore, the full adder uses logic gates to simulate the addition of three binary digits. Sketch out a truth table for a full adder in your notebooks using these headings ...

Explain how this truth table represents the binary addition of two bits and a carry in.

OUTCOME : Truth table for a half adder

Because we are combining smaller circuits together now, we need another piece of software called Logisim which is available as a portable application from http://www.cburch.com/logisim/.

Task 7.3 Binary adders

Your teacher will more than likely have to show you how to use Logisim as it's a little fiddly at first. Nevertheless, when you have figured it out, download the BinaryAdder.circ file from the lesson resources. Your task is to use the demo's to simulate the half and full adder operation and make notes on how they work.

OUTCOME : Screenshots and written explanation, truth tables, diagrams, words, pictures, songs, dances to explain how these beautiful little circuits work.

Activity 8 Flip-Flop (50)  A Level Only

One issue with any electronic circuit like a binary adder is that once the input values change, the output values alter as well. The challenge for early computer scientists was to design a circuit which remembered the last value of the input until the hardware decided to forget it. The 'flip-flop' is a circuit which allows the values of a high and a low output to 'toggle' or 'flip' and 'flop' based on the value of an input and for the last state to be remembered (for a certain length of time). Flip-flop circuits are a simple type of 1-bit computer memory and are known as bi-stable devices because they have two stable states.

Level Triggered D-Type Flip-Flop

There is absolutely no need to either a) understand how these circuits work, or, b) remember how they are constructed (phew!). Suffice to say that they all use a clever combination of feedback to 'lock' the position of an output (the Data in D-type) in a HIGH or LOW state based on a particular combination of the inputs to the circuit.

Before we consider an edge triggered flip-flop, we really need to understand a simpler, level triggered version.

Level triggered D type flip-flop (no clock) implemented in Logisim (FlipFlop.circ)

Task 8.1 Level triggered D-type flip-flop (no clock) 

Download and open up the FlipFlop.circ Logisim file and double click on the 'Level Triggered D-Type Flip-Flop (No Clock)' circuit. Make sure you have selected the 'Poke' tool and investigate the operation of the 'SET' and 'DATA' pins. Your teacher will simulate this circuit to you. Copy the diagram of the circuit into your notebooks and describe it's behaviour.

This circuit could be used to implement a simple memory in, say, a burglar alarm. If the alarm is 'SET', any signal on the 'DATA' line (say from a pressure pad) will set the output 'HIGH', sounding the alarm. If this trigger also unset the 'SET' bit, the state of the alarm would be locked, even though the 'DATA' trigger is no longer present.

OUTCOME : Circuit diagram, a description of the behaviour of a simple, level triggered D-type flip-flop and it's application to a burglar alarm.

This, simple level triggered flip flop only allows the data line to toggle the high and low outputs when the 'SET' signals is high. In a computer system, the use of a common clock circuit in the electronics helps to synchronise the operation of all dependent circuits. This version, replaces the 'SET' trigger with a 'CLOCK'.

Level triggered flip-flop (clock) implemented in Logisim (FlipFlop.circ)

So, every time the clock pulse is high, the data bit is free to be changed ready for, say, another calculation. However, the main problem with these types of circuit occurs because they allow multiple output signal changes per clock cycle which is bad. The circuit will only remember the last data signal change that occured during the clock pulse and may miss subtle changes in data.

Level triggered flip-flops respond to data signal changes
as long as the level of the clock is high.

Task 8.2 Level triggered D-type flip-flop (clock)

You should have already downloaded the FlipFlop.circ file from the lesson resources. Double click on the 'Level Triggered D-Type Flip-Flop (Clock)' circuit. Make sure you have selected the 'Poke' tool and investigate the operation of the circuit using the simulation feature of Logisim. Your teacher will demonstrate how to do this. Copy the diagram of the circuit into your notebooks and describe how it operates.

OUTCOME : Diagram and description of a simple clock driven level triggered D-type flip-flop.

Edge Triggered D-Type Flip-Flop

Enter the edge triggered flip-flip. Hurrah! Due to it's more complicated design, this circuit only allows the data line to toggle the outputs when the clock changes from 0 to 1 (the so called 'rising edge' of the clock pulse, hence the name). Once the clock signal has settled, no further changes in output can occur until the next rising edge clock signal.

Edge triggered flip-flop (clock) implemented in Logisim (FlipFlop.circ)

Edge triggered flip-flops respond to data signal changes
only if the clock signal is changing from 0 to 1

The effect of this is that the flip-flop locks (and therefore remembers) the state of the outputs for the duration of the clock cycle and does not allow it to be changed until the next clock cycle begins.

Task 8.3 Flip flops

You should have already downloaded the FlipFlop.circ file from the lesson resources. Double click on the 'Edge Triggered D-Type Flip-Flop' circuit and investigate it's operation. Your teacher will demonstrate how to do this if necessary. Print out a diagram of the circuit for your notebooks and describe it's operation.

OUTCOME : Circuit diagram and description of an edge triggered D-type flip-flop.

Extension Activities   A Level Only

How about these ..

Creating a nybble adder

It's all well and good adding two binary digits together using a full adder. What about adding two nybbles together? Consider the following diagram ...

This is basically a nybble adder consisting of 4 full adders chained together. This time, the inputs are labelled P0 - P3 for the first nybble and Q0 - Q3 for the second nybble to be added. We can assume that CI (Carry In) is 0. Make a nybble adder using Logisim or Logicly and amaze me and your friends. Produce a screencast video to show off your electronic prowess (and give me a copy so I can pretend I did it!) It's a short (and less tedious) step to creating a byte adder. Have a go. If you make it in Logisim, is might look like this ...

[Image of Logisim byte adder]

If you really fancy a challenge, how about making it in Minecraft?

Read a book

If you are interested in learning more about the electronics behind computer design, I've learnt everything I know from a book called Code : The hidden language of computer hardware and software. Buy it NOW!

Research some more about Flip-Flops

Visit this website and find out more about simple memory circuits.

What's next?

Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.