boolean-expression - I am right Boolean expression using Karnaugh map

Question

I got an question from school - Obtain the minimal form for the following Boolean expression using Karnaugh map. F(U, V, W, Z) = ∑(0, 1, 2, 3, 6, 7, 8, 9, 10, 13, 15)

And I solved it like this

There are four pairs and one quad that reduce as given below:
Pair-1(m7 + m6) reduces to U’VW
Pair-2(m8 + m9) reduces to UV’W’<br> Pair-3(m13 + m15) reduces to UVZ
Pair-4(m8 + m10) reduces to UV’Z’<br> Quad (m0 + m1 + m2 + m3) reduces to U’V’<br> Simplified Boolean expression for given K-map is F(U,V,W,Z) = U’VW + A’C’O + UVZ + UV’Z’ + U’V’</p>

But my teacher said

answer is not matching with the rules of boolean..as it wants first quads and then pair but answer is showing diff.

I am confused

Answer 1

进行如下操作：

UVZ

U'W

V'W'

V'Z'

我在http://www.logicminimizer.com/上使用了该工具

Answer 2

For the given output defined as the function f of the four variables u, v, w and z:

f(u,v,w,z) = ∑(0,1,2,3,6,7,8,9,10,13,15)

that could be alternatively represented by following truth table (where s is the index of the current state and matching cell in Karnaugh map and o is the output value):

  s | u v w z | o
----|---------|---
  0 | 0 0 0 0 | 1
  1 | 0 0 0 1 | 1
  2 | 0 0 1 0 | 1
  3 | 0 0 1 1 | 1
  4 | 0 1 0 0 | 0
  5 | 0 1 0 1 | 0
  6 | 0 1 1 0 | 1
  7 | 0 1 1 1 | 1
  8 | 1 0 0 0 | 1
  9 | 1 0 0 1 | 1
 10 | 1 0 1 0 | 1
 11 | 1 0 1 1 | 0
 12 | 1 1 0 0 | 0
 13 | 1 1 0 1 | 1
 14 | 1 1 1 0 | 0
 15 | 1 1 1 1 | 1

was your answer:

f(u,v,w,z) = ¬u⋅v⋅w + u⋅¬v⋅¬w + u⋅v⋅z + u⋅¬v⋅¬z + ¬u⋅¬v

a perfectly valid boolean expression equivalent to the original function alright, BUT!

If it had to be implemented in a logic circuit design, you would might take into consideration how many variables are actually used as logic gates' inputs, how many inputs are there for each of them or how costly are the selected types and numbers of logic gates from the point of time (and possible delays and hazards), money or surface take. Some of the given variables might not even be vital as inputs for some of the logical gates used in a design.

For this reason, you would normally try to minimalize the expression to the smallest possible clusters of variables without compromising the desired output value.

Minimalization – either to get an expression in it's minimal CNF or in minimal DNF – is done by finding the largest possible groups in your K-map.

You do not care about slight (not fully) overlapping of the found groups, because larger the group, the less variables you actually might need to include into the design. You just have to be careful to include only the needed minimum and cover the desired output value, so that if you would have to remove one of the groups, it would change the output's value for one/some/all of the states.

In plain language I think the recipe would be: to circle all ones, but not a single zero (zeros, but not a single one respectively) with the largest bubbles there can be found and each bubble must clasp in something, that any of the other ones could not have and did not already better.

So I think, what your teacher meant by "first quads and then pair", is exactly that.

In the following picture (generated using latex) there is your solution next to it's equivalent minimal DNF (~ circling the ones).

You can also check, that the next equation is valid by inserting your solution into an online tool Wolfram Alpha and checking it's DNF and CNF.

¬u⋅v⋅w + u⋅¬v⋅¬w + u⋅v⋅z + u⋅¬v⋅¬z + ¬u⋅¬v = ¬u⋅w + ¬v⋅¬w + ¬v⋅¬z + u⋅v⋅z