Fundamental Hardware Elements of Computers: Simplifying boolean equations

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$