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/AWe 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. Mr Boole to thank once again!
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.
From this investigation, you should have seen that the following statements are
True ...
From this investigation, you should have seen that the following statements are True ...
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 lawsThere are further implications to the combinations of logic gates which form a set of Laws ... - Associative laws
- Distributive laws
- Commutative laws
- Precedence laws
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'
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.
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.
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
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!)
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
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
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.
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
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!
END OF TOPIC ASSESSMENT |