-1
$\begingroup$

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)$ Here is the K-Map

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). Procedure 1

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)$. Procedure 2## Heading ##

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?

$\endgroup$
  • 1
    $\begingroup$ Please do not use pictures for critical portions of your post. Pictures cannot be searched and are inaccessible to those using screen readers. $\endgroup$ – hengxin Jan 18 '16 at 12:42
  • $\begingroup$ Agreed. Please transcribe at least the core question. (Also, please shrink the images to, say, half the width. They are unnecessarily large and pixelated.) $\endgroup$ – Raphael Jan 18 '16 at 14:00
  • $\begingroup$ @hengxin I understand, but how can I represent a K-Map without a picture? Are there any tools that can help me do this? $\endgroup$ – Somenath Sinha Jan 18 '16 at 15:44
  • $\begingroup$ Maybe it can be represented by a simple $5 \times 5$ table which consists of manually aligned numbers and symbols ($x, y, w, z, X$). You can enclose the table in a code environment. If it is too tedious, please shrink the images as @Raphael suggested. Then putting all three images into one picture is an alternative option. $\endgroup$ – hengxin Jan 19 '16 at 2:21
  • 2
    $\begingroup$ I'm fine with using image for the k-maps themselves (cc @hengxin); they can not be searched or copy-pasted properly, anyway, and your markings are probably impossible to do with MathJax. (That said, matrices are not that hard to do; see here.) My former comment applies, though: make the problem statement text, and shrink the images. $\endgroup$ – Raphael Jan 19 '16 at 8:15
1
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ Could you elaborate where exactly I went wrong when I tried to minimize the K-Map? (which led me to the wrong minimal expression x(x+w)) ? $\endgroup$ – Somenath Sinha Jan 20 '16 at 5:32
  • 1
    $\begingroup$ Just added an explanation in the answer. $\endgroup$ – eevee25 Jan 20 '16 at 19:40
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.