CS15 : Mr Boole, I presume

So we should have learnt about logic gates and be able to cope quite well with those. However, sometimes, the logic circuits that we make are simply too complicated. They cost too much money and the same logical output could be achieved using less gates - a simplified circuit.

NOTE : Need to add a section on Karnaugh Maps for OCR AS/A

We are learning ...
  • About the laws of Boolean algebra
So that we can ...
  • State the Boolean identities
  • State De Morgan's laws, distribution, association, commutation, double negation
  • Manipulate and simplify Boolean expressions
  • Construct more complex logical expressions / logic gate diagrams / truth tables
  • Understand that logic gates translate Boolean concepts into physical uses.

Complicated logic circuits cost money to produce. The more gates, the more expensive. The more types of gate, the more expensive. When computer scientists / engineers design logic circuits, it is cheaper and simpler for them to use only one type of logic gate. The most flexible gates they can use are NAND or NOR gates so this is generally the goal for most electronic engineers - to make logic circuits out of just NAND and NOR gates.

But wait! What about the other gates? Can we express those in terms of NAND and NOR? We have Mr Boole to thank once again!

Activity 1 Deriving Boole's Identities (120)

Certain combinations of logic gates and inputs always give the same outputs. In some cases, the output is much simpler that you may expect. This element of simplification allows us to remove complexity from logic circuits and make them, well, more simple.

Task 1.1 AND operations

Make the following logic circuits using Logicly.

Click to view

Investigate the nature of the output and how it relates to the value of the single input, A.

OUTCOME : Give evidence that you have constructed the circuits and used a simple truth table for each one.

From this investigation, you should have seen that the following statements are True ...

Task 1.2 OR Operations

Make the following logic circuits using Logicly. I'm not going to give you the circuit diagrams this time - sneaky or what?
  • An OR gate with one input which is always '0'.
  • An OR gate with one input which is always '1'.
  • An OR gate with 'tied' inputs.
  • An OR gate with 'tied' inputs, one of which is inverted with a NOT gate.
OUTCOME : Give evidence that you have constructed the circuits and used a simple truth table for each one.

From this investigation, you should have seen that the following statements are True ...

Task 1.3 NOT Operation

Make the following logic circuit using Logicly. It's not hard!
  • A NOT gate with a single input which is inverted with a NOT gate.
OUTCOME : Give evidence that you have constructed the circuits and used a simple truth table for each one.

Yes, I know this one seems silly - why bother? However, it does come in handy when you 'doubly' invert an input.

Using these identities, it is possible to remove gates from a logic expression - just look for the RHS of any of these equations and replace it with the LHS.

Boolean laws

There are further implications to the combinations of logic gates which form a set of Laws ...
  • Associative laws
  • Distributive laws
  • Commutative laws
  • Precedence laws
Yes, it does sound complicated, but let's investigate them using Logicly again ...

Task 1.4 Laws with funny names. Ha, Ha.

Follow the instructions on the popup ...

Click to view

 : Provide proof that you have proved the laws are valid.

So, when we see the RHS, we can replace it with the LHS. Remember that 'A', 'B' or 'C' could be the output of other logic gate - that's where it gets complicated.

Factorisation (The Absorption Law)

Factorisation is the opposite of expansion (the distributive law). Sometimes spotting factorisation opportunities is awkward, especially then you can't see The Magic δ (don't use this in your exam, I've made it up!)

Simplify AND with a Magic '1'

Simplify OR with a Magic '0'

Task 1.5 The Magic δ

Use the concept of the Magic δ to simplify the following expressions.
  1. Q = Y+(Y.X)
  2. Q = M.(N+M)
OUTCOME : Provide proof that you have proved the laws are valid.

Activity 2 De Morgan's Theorem (120)

Even with the laws we have just seen, there comes a problem if I want to find an equivalent logic expression which uses different logic gates.

This is where a famous 19th century mathematician, Augustus De Morgan comes in ...

Click to view

This so called De Morgan's Theorem (DMT) allow us to do some powerful things when simplifying logic expressions. But are they really the same? How can an AND be the same as an OR?

The 'NOT, SWAP, NOT' procedure can be seen in operation in the following funky gifs.

Task 2.1 Proving De Morgan's Theorem

Copy and complete the truth tables to prove De Morgan’s Theorem. You should find that the shaded columns in the tables agree with each other in both cases ...

Click to view
Click to view

 : Copy and complete the tables in your notes. Use a suitable title and include some notes if you wish.

So now that we know that they are equivalent, how can we make use of them? You can remember the identities above or you can learn how to apply the rules. That's a lot better,

You can apply the NOT-SWAP-NOT rule to any part of a Boolean expression. Note that one logical operation can form the input to another so you can apply DMT to parts of more complicated expressions.

Task 2.2 De Morgan Practice
Pencil and paper

For this exercise, you need to work with a partner. Together you should come up with a variety of different Boolean expressions to 'set' each other and practice performing De Morgan's operations on them. Work together and check with me if you need some guidance.

OUTCOME : A greater understanding of the application of DMT. You should have note in your books on what you have worked on. Get your partner to mark what you have done, sign it and date it.

To reiterate ... De Morgan's allows us to change AND operations to OR operations and vice versa. In the process, we may introduce other operations (like NOTs) but that's ok, we can cope. Given an expression containing both AND operations and OR operations, we can convert this to one containing simply OR (and NOT) operations or simply AND (and NOT) operations. Look ...

Click to enlarge

Task 2.3 De Morgan this, mate.
Knowledge of De Morgan's Theorem

Use De Morgan's Theorem (DMT) to produce two logical expressions, one of which does not contain OR operations and one which does not contain AND operations.

OUTCOME : Written proof of what you have done.

Now you must print off Rules of Boolean Algebra.docx and keep it really safe. It contains a summary of the rules you have learnt do far. Use this resources in the exercises that follow.If you are still struggling, this website will explain things a little more (or you can ask your teacher for help!)

Activity 3 Practice makes perfect! (60)

There is nothing like practice to make perfect. Your teacher will lead you through at least the first one of these examples. You have to use the sheet you printed off in the last Activity.

Choices you can use are ...
  • Boolean simplification
  • Factorisation (The Absorption Law)
  • Associative laws
  • Distributive laws
  • Commutative laws
  • Precedence laws
  • De Morgan's theorem

Task 3.1 Simplifying Boolean Expressions
Rules of Boolean Algebra

Open up the following popup and get ready for a challenge!

Click to enlarge

OUTCOME : Step by step written simplification of each Boolean expression. Ask your teacher for the solutions either to check if you are correct or to get a 'direction' if you are struggling.

Activity 4 Using truth tables to simplified logical expressions (20)

Consider the situation where you don't actually have any idea what the logic in a circuit you have created is. You have switches / inputs that you toggle on and off in such a way as to effect an output. You create a truth table for your electronic circuit. Boom. How do you evaluate and simplify the Boolean logic you have designed?

Click to enlarge

Task 4.1 Truth table to logical circuit

Construct a simplified Boolean expression to represent the logic in the following truth table ...

OUTCOME : Written, step by step working out.

Activity 5 Karnaugh maps - a pictorial simplification method 

A Karnaugh map is a special type of truth table which encourages pattern recognition and is used to quickly simplify Boolean expressions or complex truth tables.

Activity 6 The Power of NAND and NOR (50)  Optional, but quite interesting

If we aim to produce an equivalent circuit composed of only NAND operations, we need to change any OR operations to AND operations using DMT. Conversely, if we aim to produce an equivalent expression using only NOR gates, we need to convert all AND operations in the original expression into OR operations.

The goal of all this nonsense is to simplify electronic circuits so they can be made using one gate and one gate only. Even though this might lead to circuits which contain more logic gates overall, it is cheaper to make circuits using one type of gate than using more than one.

Click to enlarge

Task 6.1  I have the power!
  • Convince yourself that both the power of NAND and the power of NOR is as great as it seems to be. Make the circuits in Logicly and test their logic.

  • Make the following circuit in logicly ...

    a) Test it's logic using a truth table.
    b) Now convert the circuit to one which uses only NAND gates (replace each gate with it's NAND gate equivalent from the popup above). Do the same for NOR gates. You will find that there are more gates needed in each case but they are of only one type rather than three.
OUTCOME : Screenshots of the two equivalent circuits you have created, one with only NAND gates and one with only NOR gates.

Extension Activities 

A multiplexer (or mux) is a digital device which acts as a switch to route particular inputs (I) to an output (Q) depending on the state of a switch (S). A simple 2x1 multiplexer has a truth table like this ...

... where 'S' is the switch line, 'I0' and 'I1' are the two inputs and 'Q' is the output. Multiplexers are used in situations where input lines share a common, low bandwidth transmission medium and are given equal time slots (time-division multiplexer).
  • Using only the lines from the truth table where the output is True (1), construct a simplified Boolean expression for a 2x1 multiplexer and use this to draw a circuit diagram of how it may be constructed (you need 4 gates). 

  • Test the inputs to make sure that the output is correct in all cases.

  • Use De Morgan's theorem to construct a valid Multiplexer using ONLY NAND gates.
If you can do this, you are cookin!

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.