Homework 3 problem 5

CLD-II, Chapter 3, problem 3.4, part b

What are the prime implicants for each of the expressions in Exercise 3.3?  Which are essential?  Are any redundant?  How many don’t cares are set to 1 in each case?

Problem 3.3 part b looks like this:

f(A,B,C,D) = sum{ m(0,1,4,10,11,14) } + sum{ d(5,15) }

The first thing to do is understand what an implicant is.  According to the book (page 99) an implicant is a single element of the on0set or any group of elements that can be combined together in a K-map.  This means that every one of the minterms is an implicant.  As is any combination that can be created from those minterms on the K-map.  By contrast, (page 99) a prime implicant is an implicant that cannot be combined with another one to eliminate a literal.  This means a prime implicant is the largest grouping that can be made on K-map.  On page 100, we find that an essential prime implicant is a prime implicant in which at least one of the literal terms is only covered by that prime implicant.  This means that the essential prime implicant must be part of the minimized expression.

After drawing the K-map for the function and reviewing the definitions, it should be clear that the prime implicants are as follows:

A’C’, AC

Both are essential prime implicants because there is no other prime implicant that covers any of those literals.  Since both prime implicants are essential, there is no redundancy.  Finally, both don’t cares have been set to 1.  (this can be seen easily from the K-map).