Logic Functions
Is It Important To Consider Better Methods?
Minterm Expansions
Simplifying A Minterm Expansion
Don't Care Terms
Problems
You are at:  Elements - Logic Circuits - Minterms
Logic Functions

In the first lesson on digital logic we examined how you could use truth tables and gates to produce an electrical implementation of a given truth table.  In this lesson you will examine that process more formally.

Larger logic problems require a systematic approach for solution.  Modern integrated circuit chips - for example CPU chips for personal computers - can use millions of logic devices.  The sheer magnitude of these designs is a clear sign that a formal approach to the design is needed.

In this lesson you will learn some ways of using Boolean algebra expressions that point directly to a particular logic circuit implementation.  We will finish the lesson by examining a way to simplify circuits so that they use a minimum number of components and gates.

Here are your goals for this lesson - what you should be able to do.

Given a Boolean function described by a truth table,
Be able to determine the smallest sum of products function that  has the same truth table.
Be able to determine the AND-OR-NOT circuit that implements that smallest sum of products function.
Be able to determine the all-NAND circuit that implements that smallest sum of products function.

Minterm Expansions

There are usually numerous ways any Boolean function can be expressed, and each expression leads fairly naturally to a circuit with AND gates, OR gates and inverters.  Different ways of expressing a function can have widely varying levels of complexity.  More complex circuits will require more gates and inverters, so it's a reasonable goal to learn how to devise circuits that are as simple as possible.

In this section we are going to look at how you can represent circuits differently using Boolean algebra.  We'll move from that to a consideration of how you can implement circuits based on different Boolean expressions.  Those concepts are important because any given circuit, even one as complex as a CPU chip, will be better if you can design it to use fewer components.  That's expecially important in large circuits involving millions of transistors or gates.  Savings of a small percentage of components can translate into thousands of transistors or gates.

An Example Function

Let's look at a simple Boolean function of three variables.  We'll describe this function with a truth table.  Here's the truth table.  The input variables are X, Y and Z, and the function output is F.

 X Y Z F 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0

Let's examine this function in some detail.  The only non-zero entries are at:

X = 0, Y = 1, Z = 0

and
X = 1, Y = 0,  Z = 1

The function is 1 for those two input conditions and zero for all other input conditions.

Now, lets' think about how we can implement this function.  Here's a description of what we want to implement:

• We want the output to be 1 whenever we have either
• X=0 AND Y=1 AND Z=0
• OR when we have
• X=1 AND Y=0 AND Z=1.
This word statement is very close to the function we want.  We've highlighted the important aspects of the function.  Here's the function:

This function is read as (NOT-X AND Y AND NOT-Z) OR (X AND NOT-Y AND Z) and when we read NOT-X that means we have to have X=0 to make the three terms ANDed together work out to 1.

Now, let's look at a circuit that will implement this function.  Here's the circuit.  Notice how the inputs are grouped into groups of 3, ANDed together (after taking inverses where appropriate) and the results ORed at the end.

Defining Minterms

In producing our circuit we had to use the form:

.  This form is composed of two groups of three.  Each group of three is a minterm.  What the expression minterm is intended to imply it that each of the groups of three in the expression takes on a value of 1 only for one of the eight possible combinations of X, Y and Z and their inverses.  Important points about minterms include the following.

• In a minterm, each variable, X, Y or Z appears once, either as the variable itself or as the inverse.
• Each minterm corresponds to exactly one entry (row!) in the truth table.
Implications of the two points above are that you can build any Boolean function at all by building it up from minterms.  There is no qualification to this statement.  Truly any Boolean function can be constructed using minterms, and the construction process is simple.

To build any Boolean function from minterms do the following.

• Get a truth table for the function.  Be sure that all possible combinations of variables and inverses are accounted for.
• For each entry of the truth table for which the function takes on a value of 1, determine the corresponding minterm expression remembering that every variable of its inverse will appear in every minterm.
• OR all the minterms from the second step together.
We can sum up this conclusion with the following:
• A truth table gives a unique sum-of-products function that follows directly from expanding the ones in the truth table as minterms.

An Example Using Minterms

To illustrate the use of minterms to get an electrical implementation of a logic circuit, consider this problem.  Three young graduates have formed a company.  The three graduates, Alisha, Ben and Corey have a system to minimize friction.  For all minor decisions they want to use a circuit that will determine when a majority of the three of them has voted for a proposal.  Essentially, they want a box with three inputs that will produce a 1 at the output whenever two or more of the inputs are 1.

The solution process starts by getting the truth table.  That's shown below.  Notice that there are four 1 entries in the table.  Those 1s occur when two people vote Yes together or when all three vote together.

 A B C V 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

After getting the truth table, the next step is to identify the minterms.  That's shown below where the minterms are to the right of the corresponding entries in the truth table.  There are four 1 entries in the truth table and four corresponding minterm expressions.

 A B C V 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

The first term, where Ben and Corey vote YES, and Alisha votes NO is this term.  Note that this term corresponds to:

• A = 0 - which means NOT-A is 1
• B = 1
• C = 1
so, when you AND all these terms together, you get 1 under the conditions here.

There are three other terms and we could make similar observations about them.

Now, with the minterm expressions, we can write an expression for the 3-person voting function, V.  We have:

This expression leads directly to a circuit implementation using ANDs, ORs and Inverters.  Each minterm can be generated using a 3-input AND gate.  The first minterm is shown below.

You'll need three more circuits somewhat like this one for the complete solution.  Now, you should be able to construct the other three.  They are similar to the one above.  Here they are.  Each circuit shows the output term from the truth table.

Next, consider how these small circuits must interact.  The function is 1 whenever the first term is 1, OR when the second term is 1, OR when the third term is 1, OR when the fourth term is 1.  To implement that you need the following circuit.

Keep in mind how this circuit comes about.  Each AND gate senses just one of the terms in the truth table, and is 1 whenever that corresponding element in the table is selected (by selecting the correct inputs for that point in the truth table.  In the expression we saw earlier, the outputs of each AND gate are ORed together to produce the output.  Here's that function again.

Be sure that you can see how the circuit above implements this function.

This function is composed of four minterms, and as noted above each minterm corresponds to one entry of 1 in the truth table.  That implies the following algorithm for generating a Boolean algebra function from a truth table.

• Given a truth table with one or more places in which the function takes on a value of 1,
• Write out the minterms for each place in the table where the function takes on a value of 1.
• OR all of those minterms together.
Note the properties of this algorithm:
• It will always work to allow you to generate a Boolean function from a truth table.
• The Boolean function will be a number of minterms ORed together
• The number of minterms will be the number of places (1s) in the truth table where the function takes on a value of 1.
• This kind of function is often referred to as a "sum of products" form.
• The sum of products form leads directly to a "two layer" implementation with ANDs in the first layer and a single OR in the second layer.
• The number of ANDs will be the number of places (1s) in the truth table where the function takes on a value of 1.
• That's one AND gate for every minterm in the sum of products form you get for the function.
• When we say two layers, we are ignoring the possibility that you might require some inverters (NOTs) to complement some of the input signals.  (On the other hand, those inverted signals might be available in the system, and you might not need the inverters!)
Using minterms is not always the most efficient way to implement a circuit.  Although a minterm expansion will always produce a function you can implement, for any truth table, there are better ways - ways that use fewer gates and which therefore cost less to implement.  We'll look at those next.

Circuit Simplification

Boolean functions are somewhat peculiar because a complex Boolean function can often be a simple function masquerading in a more complex form.  In this section we're going to examine that phenomenon.

It's important to look at this because simpler Boolean functions translate directly into less expensive circuits with fewer gates.  It's economically important to produce the simplest possible circuit for any design work that you do!  We'll begin by looking at the example function for the voting circuit.  Here's the function again in all its glory.

There are some things in the function that suggest some actions to take.  For example, the last two terms in the function are:

Let's work on those last two terms.  These two terms differ just in the way A enters the two terms.  It shows up both as A and as its inverse.  You are probably tempted to write this expression as:

Actually, that will prove to be a good strategical move, but we have to consider some basic Boolean algebra first.  There are some simple Boolean algebra facts we need to know first.  Be sure you understand why these are true.

• For ANDs
• In the X-terms, X can be either 0 or 1.
• If X = 0, the inverse is 1 & vice versa.
• For ORs
• In the X-terms, X can be either 0 or 1.

• If X = 0, the inverse is 1 & vice versa.
Going back to the last two terms of the voting function, we have:

Last two terms =

=

Here, we take advantage of the last item in the table for the OR function to eliminate the A-terms.

Using the results we have been able to generate, we can now note that the voting function, F, can be simplified.

can be simplified to:

We can combine the last two terms into one, simpler, term, eliminating A in that term.  However, we are still stuck with terms that involve three variables for the first two terms in F.

If you think about what we did, you realize that the term, ABC (the term with no inverted variables), could have been combined with any of the other three terms.  Each such combintation would have eliminated a different variable in the shorter result.  It was an arbitrary decision to combine it with the third term.

However, by combining with one of the three terms, we "used up" the ABC term.  Or did we?

It would have been nice if we could have combined the term ABC with all three of the other terms.  It seems a shame to have used it up with just one term.

There's something peculiar with logic expressions however.  We can actually do what we want to do - combine ABC with all three of the other terms.  To do that we have to notice that

ABC = ABC + ABC

This is just a restatement that if you OR anything with itself, you get the original quantity back (X + X = X).  Remember  0 + 0 = 0 and 1 + 1 = 1 and the expression ABC is either 0 or 1.

Now, we can generate a much simpler expression for the voting function.  We start with the original voting function.

Expand R with multiple copies of the last term.

Then use our earlier method to get a simpler version of the voting function:

Here's a circuit that implements the simplified form we found.  Putter with this circuit to see how it works.  Notice how the circuit is wired, and notice that we had to "snake" the A line around the entire circuit to get it inot the lowest AND gate.

What If?

There are obvious "What If?" questions here.  What if the circuit is really large?  Then you will need to have formal algorithms that are programmed and use the program.  That's what is done.  There are sets of design tools to help you do that.  Of course, those sets of design tools usually use templates of smaller circuits, and large circuits often have large parts that are just repeated use of a template of a smaller circuit.

There is some hope that you can understand a really large circuit.  The material in this lesson should help you understand how the small, but reusable, parts of a large circuit are designed.

On the Structure of the Result and Points to Note

The structure that comes out of our approach is a two-layer structure, with all AND gates in the first layer and all OR gates in the output layer.  You will always get that kind of structure if you use the minterm-based approach.  Minterms are often referred to as sum-of-product expressions.  Sum-of-product expressions give rise naturally to two layer AND-OR structures when they are implemented.

Secondly you should note that the structure we found is not necessarily always the simplest.  There may be, for example, simpler three layer structures.

Finally, you may be a bit perplexed at all this.  Maybe we were just lucky to get an expression that was simpler.  It's not clear how to do that consistently, and how to figure out how to do it when it's possible.  In the next section we'll look at Karnaugh maps which are a way of visualizing how to group terms in a way that permits you to simplify complex expressions.

Two Layer Structures

Here is an example of a two-layer circuit we saw earlier.  The input layer is composed of ANDS and the output layer is a single OR.  This circuit implements a sum of products expression.

What needs to be stressed here is that you can always use the algorithm we indicated above.

• Given a truth table with one or more places in which the function takes on a value of 1,
• Write out the minterms for each place in the table where the function takes on a value of 1.
• OR all of those minterms together.
and this algorithm will always result in a two-layer structure like the one above.  (We don't count the inverters as a layer.)  This is a straight forward procedure that guarantees that you will be able to build a circuit for any function you have that is represented with a truth table.  While this process guarantees a circuit, it does not guarantee the best circuit!

Consider a simple example.  Here is a simple truth table.

 P Q F 0 0 1 0 1 0 1 0 1 1 1 0

Next, look at the minterms that are represented in the truth table.

 P Q F Minterms 0 0 1 0 1 0 1 0 1 1 1 0

Once you have the table like this, then:

• Form the function represented by the truth table by determining the minterm that produces each one in the truth table.
• The minterms are shown to the right of the entries which are ones in the table above.
• From the minterm expression, generate a two layer circuit that implements the function found in the previous step.
• From the minterm expression, generate a two layer circuit that implements the function found in the previous step.
There are some cautions here.
• The function consists of variables and complements of variables ANDed
•  together.
• This assumes you have the complements.  But you can generate complements
•  by inverting signals.
Now, consider this circuit in light of deMorgan's Theorem.  Click here if you want to review deMorgan's Theorem.  deMorgan's Theorem says:

deMorgan's Theorem also can be construed to say the following if we invert both sides of the above equation.

If we consider the function earlier, we have:

If we are to implement this function, it would look like this:

Now, apply the inverted form of deMorgan's Theorem, and we have:

In words, we can NAND the input terms (at the very left) and then NAND the result.  Note the structure of this result.

• There are multiple NAND operations.  For example, P and Q are NANDed, as are their inverses.
• In effect, both minterms are inverted.  Those are the two terms ANDed and inverted on the right hand side of the last equation above.
• After the minterms are inverted they are inverted and ANDed again, effectively NANDing them.
• That implies that the entire thing can be implemented using only NAND gates.
This function (above) can be implemented with the circuit below.

Can we generalize this approach?
• Functions of more variables will have larger truth tables, but every entry that is a one corresponds to a minterm - even in larger truth tables.
• Every minterm can be generated by ANDing together variables and complements of variables (NOT the variable!).
• Thus, a minterm can be implemented with an AND gate, as long as the complements are available as necessary.
• Complements can be generated by inverting a variable - passing the signal through an inverter.

Don't Cares

There is one thing we need to point out about truth tables.  Sometimes we don't care about certain elements in the truth table.  You might have trouble visualizing that, so consider the following.

• If you are wearing a digital wristwatch, look at it.  Somewhere within the watch there is a counter that drives each digit displayed.  If the digit runs from zero to nine, it takes a four bit counter.  However, the count will never be 10 or anything higher, so when you design the decoder, you don't care about those numbers that will never be seen.  It will never be thirty-eleven minutes after fourteen o'clock.
There are many other situations in which Don't Cares arise.  The problem is what to do about them when they arise.  What to do is this.
• If you have a function with Don't Cares in the truth table, you may do whatever works best for you.  Choose any Don't Care as a one or zero as you wish.  You don't have to choose all of the Don't Cares as ones or as zeroes, and if you truly want you can choose them randomly.  (That might not be wise, but you can do it if you want.)
• When you get to circuit simplification you will find that there is an art to choosing Don't Cares to give the simplest possible circuit implementation.

Problems

Here are links to some problems in digital logic.

Here are some links to lab problems in digital logic.
1. Checking out a Quad-NAND chip.
Part 1
Part2
2. Implement the voting circuit.

Links to Other Lessons on Digital Logic Send your comments on these lessons.