A-level Computing/AQA/Paper 2/Fundamentals of computer systems/Boolean identities

Simplifying boolean equations De Morgan's Laws Sometimes a very complex set of gates can be simplified to save on cost and make faster circuits. A quick way to do that is through boolean identities. Boolean identities are quick rules that allow you to simplify boolean expressions. For all situations described below: A = It is raining upon the British Museum right now (or any other statement that can be true or false) B = I have a cold (or any other statement that can be true or false) Identity Explanation Truth Table It is raining AND It is raining is the same as saying It is raining 0 0 0 1 1 1 It is raining AND It isn't raining is impossible at the same time so the statement is always false 0 1 0 1 0 0 2+2=4 OR It is raining. So it doesn't matter whether it's raining or not as 2+2=4 and it is impossible to make the equation false 1 1 0 1 1 1 1 1+2=4 OR It is raining. So it doesn't matter about the 1+2=4 statement, the only thing that will make the statement true or not is whether it's raining 0 0 0 0 1 1 It is raining OR It is raining is the equivalent of saying It is raining 0 0 0 1 1 1 It is raining OR It isn't raining is always true 0 1 1 1 0 1 1+2=4 AND It is raining. It is impossible to make 1+2=4 so this equation so this equation is always false 0 0 0 0 1 0 2+2=4 AND It is raining. This statement relies totally on whether it is raining or not, so we can ignore the 2+2=4 part 1 0 0 1 1 1 It is raining OR I have a cold, is the same as saying: I have a cold OR It is raining 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 1 It is raining AND I have a cold, is the same as saying: I have a cold AND It is raining 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 It is raining OR (It is raining AND I have a cold). If It is raining then both sides of the equation are true. Or if It is not raining then both sides are false. Therefore everything relies on A and we can replace the whole thing with A. Alternatively we could play with the boolean algebra equation: Using the identity rule Take out the A, common to both sides of the equation Using the identity rule Using the identity rule 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 It is raining AND (It is raining OR I have a cold). If It is raining then both sides of the equation are true. Or if It is not raining then both sides are false. Therefore everything relies on A and we can replace the whole thing with A. Alternatively we could play with the boolean algebra equation: Using the identity rule Take out the A, common to both sides of the equation Using the identity rule Using the identity rule 0 0 0 0 0 1 1 0 1 0 1 1 1 1 1 1 Examples of manipulating and simplifying simple Boolean expressions. Example: Simplifying boolean expressions Let's try to simplify the following: Using the rule Trying a slightly more complicated example: dealing with the bracket first as as Exercise: Simplifying boolean expressions applying the identity applying the identity Sometimes we'll have to use a combination of boolean identities and 'multiplying' out the equations. This isn't always simple, so be prepared to write truth tables to check your answers: Example: Simplifying boolean expressions Where can we go from here, let's take a look at some identities using the identity A = A.1 taking the common denominator from both sides as B+1 = 1 Now for something that requires some 'multiplication' multiply it out cancel out the left hand side as using the identity Exercise: Simplifying boolean expressions multiplying out This takes some 'multiplying' out: This takes some 'multiplying' out: treat the brackets first and the AND inside the brackets first multiply it out as as as as take A out as the common denominator as This takes some 'multiplying' out: This takes some 'multiplying' out: multiplied out as as Take the common factor, from both sides: As Then As Then