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.
- Calculate the total number of such functions.
- 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
Best Answer
A "block of two" on a Karnaugh map corresponds to a Boolean function of the form $xy$ (complements of variables allowed). So we are looking for Boolean functions of weight $4$ ($4$ ONEs in the truth table or on the Karnaugh map) that can be covered by $3$ "blocks of two" but not by $2$ "blocks of two", that is, the minimum sum of products expression has three terms, and not two. The simplest form is thus $$xy \vee xz \vee yz$$ which is the T shape referred to (see also my comment on the main question), and complementing variables gives us $2^3 = 8$ different T shapes, some of which are "wrapped around" the edges (which is perfectly acceptable). Are there any others? Well, let's try counting. The principle of inclusion-exclusion tells us that
Well, two different "blocks of two" must intersect in one position because if they intersect in both positions, they are identical, and if they don't intersect at all, they cover all $4$ ONEs in the function. So, all three "blocks of two" must also intersect in the same position giving $$4 = (2+2+2) - (1 + 1 + 1) + 1$$ as the total weight, and also showing that the T shape is the only one possible.