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) ...It should also be possible to represent all situations as a series of decision problems with only True / False responses ...Thus was born a new way of thinking.
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
Venn diagrams to visually represent all possible combinations of objects in our little culinary world.
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.
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).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
For all those Minecrafters out there, here is a couple of videos showing how to make logic gates using Redstone in our favourite game ...
I've included two resources for you to play with ...
- The Minecraft world containing the logic gates :
**MC Logic Gates.zip** - An image containing designs for the Minecraft logic gates :
**RS Logic Gate Designs.png**
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)
values of output =
2^{number 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) ... 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 ...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.
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. We work from 'the inside out' making sure that we calculate the result of a Boolean operation before it is used.
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!
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.
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 sameThe 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)
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)
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/.
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-FlopThere 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)
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 changesas long as the level of the clock is high.
Edge Triggered D-Type Flip-FlopEnter 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 changesonly if the clock signal is changing from 0 to 1The 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.
How about these .. Creating a nybble adderIt's all well and good adding two binary digits together using a full adder. What about adding two nybbles together? Consider the following diagram ... 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 bookIf 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-FlopsVisit this website and find out more about simple memory circuits.
END OF TOPIC ASSESSMENT |