Fundamental Hardware Elements of Computers: Simplifying boolean equations

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

UNIT 2 - ⇑ Fundamental Hardware Elements of Computers ⇑

← Boolean algebra Simplifying boolean equations Boolean identities →

A common question is to give you a complex boolean equation, which you will then have to work out a simpler exact equivalent. This is useful when you are designing circuits and want to minimise the number of gates you are using or make circuits that only use particular types of gates. To simplify boolean equations you must be familiar with two methods. You can normally use either, but try to master both:

  • Truth tables
  • Boolean algebra - identities and De Morgans Law
Example: Simplifying boolean equations with Truth Tables

Draw the truth table for the following:

(A . B) + A

We are going to solve this using a truth table and we need to break the problem down into its component parts:

As the equation uses A and B list the different values they can take (4 in total)

A B
0 0
0 1
1 0
1 1

Next we are going to work out the brackets first: A.B and add this to our truth table

A B A.B
0 0 0
0 1 0
1 0 0
1 1 1

Finally we will OR this result (A.B) with A to find (A.B)+A, the final column of the truth table

A B A.B (A.B)+A
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1

Now that our truth table is complete, look at the final column, is there a simpler way of writing this? Why aye! The final column is true when, and only when, A is true, it doesn't require B's input at all. So we can simplify to A telling us that:

(A.B)+A = A
Example: Simplifying boolean equations with Truth Tables

Let's look at another example

\overline{A . \overline{B}}

We first of all need to break down the equation into its component parts. Starting off with A and B we the work out \overline{B}, then A.\overline{B} and finally \overline{A . \overline{B}}.

A B \overline{B} A.\overline{B} \overline{A . \overline{B}}
0 0
1
0
1
0 1
0
0
1
1 0
1
1
0
1 1
0
0
1

This can be simplified to \overline{A} + B telling us that: \overline{A . \overline{B}} = \overline{A} + B. How did we jump to this conclusion? Let's take a look at all the places where the result is true:

A B \overline{A . \overline{B}}
0 0
1
0 1
1
1 0
0
1 1
1

We need to get a combination of A, B that gives the result shown above. We can see that whenever A is false (\overline{A})the answer is true:

A B \overline{A . \overline{B}}
0 0
1
0 1
1
1 0
0
1 1
1

We can also see that whenever the B value is true then the answer is also true:

A B \overline{A . \overline{B}}
0 0
1
0 1
1
1 0
0
1 1
1

So we know that we need to combine \overline{A} with B to get an equation solving all cases.

If we AND them \overline{A} . B this only gives us one of the scenarios, so that's not the answer.

If we OR them \overline{A} + B then this gives us three answers, matching all the responses above. This is our solution.

Exercise: Simplifying boolean equations with Truth Tables

Give a simplified boolean description, ?, for the following truth tables:

A B ?
0 0 0
0 1 1
1 0 0
1 1 1

Answer :

B

A B ?
0 0 0
0 1 0
1 0 0
1 1 1

Answer :

A.B

A B ?
0 0 1
0 1 1
1 0 1
1 1 1

Answer :

1

A B ?
0 0 1
0 1 0
1 0 1
1 1 1

Answer :

A+\overline{B}

Simplify the following boolean equations using truth tables:

(\overline{A.B}).A

Answer :

A B {A.B} \overline{A.B} \overline{A.B}.A
0 0
0
1
0
0 1
0
1
0
1 0
0
1
1
1 1
1
0
0

This can be simplified to: A.\overline{B}

(\overline{A.B})+A

Answer :

A B {A.B} \overline{A.B} \overline{A.B}+A
0 0
0
1
1
0 1
0
1
1
1 0
0
1
1
1 1
1
0
1

The answer in all cases is a plain 1

(A.\overline{B})+B

Answer :

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

This can be simplified to: \overline{\overline{A}.\overline{B}} OR A+B (because of De Morgan's Laws)

\overline{B}+A.B

Answer :

Remember that we deal with the AND before the OR, meaning we can read the equation as: \overline{B}+(A.B)

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

This can be simplified to: A+\overline{B}

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

Answer :

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

This can be simplified to: \overline{A}.B