Which formula corresponds to this K-Map?

Question

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map.

$f(w,x,y,z) = \sum(3,7,9,11,13,15) + \Phi(4,5,6)$

We know that both options (a) and (b) are equivalent, and both represent the K-Map's function.

Option (c) however, turns to $(x)(x+w)$ if we make a subcube of size 8 using the first and last row, and a subcube of 00-01 on both axes (size = 4).

If however we take the first row and last row as different subcubes, and the subcube of 00-01, we get the function = $(x'+y)(x+y)(x+w)$.

Which of the above two methods gives the right answer (i.e., is the correct method)?

To complicate matters further, the answer key lists the answer to the question as (d)None, but I find the answer to be (c). Is the book's answer wrong? Or am I wrong?

Answer 1

First, you need to describe all three of your options using a minimum amount of literals. To achieve this you will need to do the following (use basic boolean algebra laws):


Using the Distributive Law ($ A(B+C) = AB + AC$):

(a) $(w + x)y = wy + xy$


Option $b$ is already shown in its minimal form, so we can leave it like that:

(b) $xy + yw$


To minimize the form of option $c$, we will use a few laws:

Using the Distributive Law ($A+(BC)=(A+B)(A+C)$):

(c) $(w+x)$**(w'+y)(x'+y)** $=(w+x)$**(y+w'x')**

Next, we can see that $w+x$ is $(w'x')'$, by De Morgan's Theorem.

This allows us to use the law $A(A'+B)=AB$ (in our case, $w+x$ will be $A$ and $y$ will be $B$):

$(w+x)(y+w'x')=(w+x)y$


We see that (c) is the same expression as (a), and they both are the same as (b).
All 3 options are the same.
Now let us check if they are OK (they are OK if they implement the K-map).

For this we can minimize the given k-map. If it results in the same minimal expression - all 3 options are OK. If not, then all 3 are not OK.

xy \wz|00|01|11|10
00____| 0 | X | 0 | 0
01____| 0 | X | 1 | 1
11____| 1 | 1 | 1 | 1
10____| 0 | X | 0 | 0

The 4 BOLD cells are one group $=wy$
The 4 ITALIC cells (line 3) are another group $=xy$

Together: $wy+xy$

After minimizing the map we see that the expression that we got is the same expression as (a), (b) and (c) (since they are all the same).

This means that options a-c all implement the k-map.

So the correct answer must be d.

EDIT

When trying to group the cells, the groups need to be of the size 2 in the power of n (can be 1, 2, 4, 8...). You must always look for the biggest possible groups. (so the second option that you suggested would be wrong anyway - it is better to group 8 cells and not 4 and 4).

Next, you tried to group '0's. You can only group '0's if you want the Maxterms. Only when you are looking for the POS (product of sums), aka CNF form. You are looking for the minterms (SOP). You need to choose cells that have the value '1' in them.

About the 'x (called 'don't care'): If you have an 'x' placed in a cell next to cells that are '1', and that 'x' will help you make a bigger group - you use it.
If the 'x' doesn't help you - you pretend that it is a '0'.

So, if you have the row: 0 x 1 1 and all of the other cells are '0' - you only group the '1' and '1' (because the size of the group with 'x' is 3 - and it is not a power of 2 !).

Hope this helps :)

Answer 2

Let $$S = (w + x) (w' + y) (x' + y).$$

• if $y = 1$, then $S = (w + x)$;
• if $y = 0$, then $S = (w + x) w' x' = 0$.

Therefore, $S$ is equivalent to $(w+x) y$.