Obtain the set of prime implicants for f= ∑ (0,1,6,7,8,9,13,14,15)f= ∑ (0,1,6,7,8,9,13,14,15)

txmedteach | High School Teacher | (Level 3) Associate Educator

Posted on

To obtain a set of prime implicants, let's start by making a Karnaugh map. These maps, by default, all us to determine prime implicants easily, as we'll see

Let's let A be the most significant digit, then B, then C, then D as the least significant digit. This gives us a set of 16 binary numbers of the form ABCD. Now, let's set up the K-Map.

The top row will be AB (from left to right: 00, 01, 11, 10). The left side will be CD (from top to bottom: 00, 01, 11, 10). Green will represent "TRUE" and red will represent "FALSE."

Recall: `f = sum(0,1,6,7,8,9,13,14,15)`

Now, there are other ways to get this result. We could have set up a truth table or explicity expressed each true result as a sum of smaller expressions. However, I find the K-Map to be easiest. Here's why:

We have two squares. One in the bottom center (outlined in purple) and one that wraps around the upper left and right (outlined in blue).

Notice, too, that we have 1 condition that stands alone: 13 (1110). We'll just have to incorporate this into our result and see whether it is a standalone prime.

Now, let's get our function from the K-Map to see if we get prime implicants:

`F = BC + barBbarC + ABbarCD`

Well, based on our K-Map, the above function covers all true cases. However, notice that we can do the following to the above equation:

`F = BC + barC(barB + ABD)`

Well, this in the parentheses is one of those functions that's reducible. Recall that `barB + BX = barB+X` because the first expression is redundant (We already know that either B is true or isn't true, and X is the only condition limiting the case with a true B). I know that line of reasoning may be difficult to follow, so to prove it to yourself, you may want to make a truth table to see the two expressions are equivalent.

So using this redundancy we can reduce F: