6
$\begingroup$

I would just like to clarify if I am on the right track or not. I have these questions:

Consider the Boolean functions $f(x,y,z)$ in three variables such that the table of values of $f$ contains exactly four $1$’s.

  1. Calculate the total number of such functions.
  2. We apply the Karnaugh map method to such a function $f$. Suppose that the map does not contain any blocks of four $1$’s, and all four $1$’s are covered by three blocks of two $1$’s. Moreover, we find that it is not possible to cover all $1$’s by fewer than three blocks. Calculate the number of the functions with this property.

1a: I have answered $70 = \binom{8}{4}$.

1b: I have manually drawn up Karnaugh maps and have obtained the answer $12$, but my friend has $24$. Is there another way to do this?

Thank you

  • 0
    Like you, I count $12$, $8$ in which the $1$’s occupy an L-shaped region and $4$ in which they occupy a sort of T-shaped region.2012-10-17
  • 0
    Why $70\cdot \binom{8}{4}$ instead of just $\binom{8}{4}$ for part (i)? For part (ii), consider functions of the form $xy \vee xz \vee yz$.2012-10-17
  • 0
    sorry for the confusion, i meant the answer was 70 and i obtained it by (8C4) thank you for your responses2012-10-17
  • 0
    @Brian M.Scott In addition to the L and T shapes aren't there also some S-like shapes?2012-10-17
  • 0
    @Alan: You’re right. It’s clearly my bedtime. They add another $4$, if I’m not mistaken, bringing my total to $16$.2012-10-17
  • 0
    Sean appears to agree. Goodnight Brian.2012-10-17

3 Answers 3