Fundamental Hardware Elements of Computers: Boolean identities

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

UNIT 2 - ⇑ Fundamental Hardware Elements of Computers ⇑

← 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
A.A = A It is raining AND It is raining is the same as saying It is raining
A A A.A
0 0 0
1 1 1
A.\overline{A}=0 It is raining AND It isn't raining is impossible at the same time so the statement is always false
A \overline{A} A.\overline{A}
0 1 0
1 0 0
1+A=1 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 A 1+A
1 0 1
1 1 1
0+A=A 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 A 0+A
0 0 0
0 1 1
A+A=A It is raining OR It is raining is the equivalent of saying It is raining
A A A+A
0 0 0
1 1 1
0.A=0 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 A 0.A
0 0 0
0 1 0
1.A=A 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 A 1.A
1 0 0
1 1 1
A+B=B+A It is raining OR I have a cold, is the same as saying: I have a cold OR It is raining
A B A+B B+A
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 1
A.B=B.A It is raining AND I have a cold, is the same as saying: I have a cold AND It is raining
A B A.B B.A
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
A+(A.B)=A 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:

A+(A.B)=(1.A)+(A.B) Using the identity rule 1.A=A
(1.A)+(A.B)=A.(1+B) Take out the A, common to both sides of the equation
A.(1+B)=A.1 Using the identity rule 1+B=1
A.1=A Using the identity rule 1.A=A

A B A.B A+(A.B)
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1
A.(A+B)=A 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:

A.(A+B)=(0+A).(A+B) Using the identity rule 0+A=A
(0+A).(A+B)=A+(0.B) Take out the A, common to both sides of the equation
A+(0.B)=A+0 Using the identity rule 0.B=0
A+0=A Using the identity rule 0+A=A

A B {A+B} A.(A+B)
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:

A+B+B

Using the rule B + B = B

A+B+B = A+B

Trying a slightly more complicated example:

(A.0)+B

dealing with the bracket first

(0)+B as 0.A = 0
B as 0+B = B
(A.0)+B = B
Exercise: Simplifying boolean expressions

A+0

Answer :

A

A.0

Answer :

0

E+1

Answer :

1

A+A+B+B+C

Answer :

A+B+C

(A.B)+(A.B)

Answer :

A.B

A.A.B.B.C

Answer :

A.B.C

(A+\overline{A}).B

Answer :

  1. (A+\overline{A}).B applying the identity A+\overline{A} = 1
  2. (1).B applying the identity 1.B = B
  3. B

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
(A.B) + A

Where can we go from here, let's take a look at some identities

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

Now for something that requires some 'multiplication'

  1. (\overline{A}.B) + A
  2. (\overline{A}+A).(B+A)multiply it out
  3. 1.(B+A)cancel out the left hand side as (\overline{A}+A)=1
  4. B+Ausing the identity 1.Q = Q
Exercise: Simplifying boolean expressions

(A.\overline{B}) + B

Answer :

(A.\overline{B}) + B

(A+B).(\overline{B}+B) multiplying out
(A+B).(1)
(A+B)

(A+B).\overline{A}

Answer :

This takes some 'multiplying' out:

(A+B).\overline{A}
(A.\overline{A})+(\overline{A}.B)
0+(\overline{A}.B)
B.\overline{A}

B.(A+A.B)

Answer :

This takes some 'multiplying' out:

B.(A+(A.B)) treat the brackets first and the AND inside the brackets first
(B.A)+(B.A.B) multiply it out
(B.A)+(A.B) as B.A.B = A.B
A.B as  (B.A)=(A.B)

(A+B).(A+A)

Answer :

(A+B).(A+A)

(A+B).A as A = A+A
(A+B).(A+0) as A = A+0
A+(B.0) take A out as the common denominator
A as (B.0) = 0

(A.\overline{B})+\overline{A}

Answer :

This takes some 'multiplying' out:

(A.\overline{B})+\overline{A}
(A+\overline{A}).(\overline{B}+\overline{A})
1.(\overline{B}+\overline{A})
\overline{B}+\overline{A}

(A.B)+\overline{A}

Answer :

This takes some 'multiplying' out:

(A.B)+\overline{A}
(A+\overline{A}).(B+\overline{A}) multiplied out
(1).(B+\overline{A}) as (A+\overline{A}) = 1
B+\overline{A} as 1.Q = Q

(A.\overline{B})+(A.B)

Answer :

Take the common factor, A from both sides:

A.(\overline{B}+B)
As \overline{B}+B = 1
Then A.(\overline{B}+B) = A . 1
As A . 1 = A
Then (A.\overline{B})+(A.B) = A