Fundamental Hardware Elements of Computers: Boolean identities

From Wikibooks, open books for an open world
Jump to navigation Jump to search

PAPER 2 - ⇑ Fundamentals of computer systems ⇑

← Simplifying boolean equations Boolean identities 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

Answer:

Answer:

Answer:

Answer:

Answer:

Answer:

Answer:


  1. applying the identity
  2. 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

  1. using the identity A = A.1
  2. taking the common denominator from both sides
  3. as B+1 = 1

Now for something that requires some 'multiplication'

  1. multiply it out
  2. cancel out the left hand side as
  3. using the identity
Exercise: Simplifying boolean expressions

Answer:

 multiplying out


Answer:

This takes some 'multiplying' out:





Answer:

This takes some 'multiplying' out:

 treat the brackets first and the AND inside the brackets first
 multiply it out
 as 
 as  

Answer:

 as 
 as 
 take A out as the common denominator
 as 

Answer:

This takes some 'multiplying' out:





Answer:

This takes some 'multiplying' out:


 multiplied out
 as 
 as 

Answer:

Take the common factor, from both sides:


As 
Then 
As 
Then