Is It Important To Consider Better Methods?You are at: Elements  Logic Circuits  MintermsMinterm ExpansionsSimplifying A Minterm ExpansionDon't Care TermsProblems
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 ANDORNOT circuit that implements that smallest sum of products function.
Be able to determine the allNAND circuit that implements that smallest sum of products function.
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.




































Let's examine this function in some detail. The only nonzero entries are at:
X = 0, Y = 1, Z = 0
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:
This function is read as (NOTX AND Y AND NOTZ) OR (X AND NOTY AND Z) and when we read NOTX 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.
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.
To build any Boolean function from minterms do the following.
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.




































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.




































The first term, where Ben and Corey vote YES, and Alisha votes NO is this term. Note that this term corresponds to:
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 3person 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 3input 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.
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.
Last two terms =
Here, we take advantage of the last item in the table for the OR function to eliminate the Aterms.
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.
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.
The structure that comes out of our approach is a twolayer 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 mintermbased approach. Minterms are often referred to as sumofproduct expressions. Sumofproduct expressions give rise naturally to two layer ANDOR 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.
Here is an example of a twolayer 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.















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




















Once you have the table like this, then:
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 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.
Here are links to some problems in digital logic.
1. Checking out a QuadNAND chip.
Part 1
Part2
2. Implement the voting circuit.