# calculating number of boolean functions

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

• 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. – Brian M. Scott Oct 17 '12 at 12:04
• 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$. – Dilip Sarwate Oct 17 '12 at 12:05
• sorry for the confusion, i meant the answer was 70 and i obtained it by (8C4) thank you for your responses – Z Oj Oct 17 '12 at 12:07
• @Brian M.Scott In addition to the L and T shapes aren't there also some S-like shapes? – Alan Gee Oct 17 '12 at 12:26
• @Alan: You’re right. It’s clearly my bedtime. They add another $4$, if I’m not mistaken, bringing my total to $16$. – Brian M. Scott Oct 17 '12 at 12:33

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

the total weight of $4$ equals the sum of the weights of the three "blocks of two" minus the sum of the weights of the pairwise intersections of "blocks of two" plus the weight of the intersection of all three "blocks of two".

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.

We can classify all $\binom 8 4$ functions of three variables with $4$ minterms according to the "number of blocks" one obtains on a Karnaugh map. First note that the K-map method produces a prime and irredundant expression: every term (or block) is a prime implicant, and every term covers one minterm not covered by any other term in the expression.

We classify prime and irredundant covers according to the number of prime implicants. Then we'll argue that the correspondence between covers and functions is one-to-one.

• Prime and irredundant covers with four implicants. There are two of them, even and odd parity. No two minterms may be adjacent on the map, and there's only two ways to achieve that.
• Prime and irredundant covers with three prime implicants. There are eight of them of the type shown by @DilipSarwate, namely $(x \wedge y) \vee (x \wedge z) \vee (y \wedge z)$. There are 24 more of the form $(x \wedge y \wedge z) \vee (\neg x \wedge \neg y) \vee (\neg x \wedge \neg z)$.
• Prime and irredundant covers with two prime implicants. We divide them according to the number of variables appearing in the cover.
• Two variables: these are the even and odd parity functions of two variables, of which there are six in total.
• Three variables: These covers must be of the form $(v \wedge b) \vee (\neg v \wedge c)$, where $v$ is a variable and $b$, $c$ are literals (not of $v$). The variable $v$ can be chosen in three ways; for each choice of $v$, there are four choices of $b$ and then two choices for $c$, for a total of 24 covers.
• Prime and irredundant covers with one prime implicant. The implicant is a literal; hence there are six choices in this case.

In summary: $2 + (8+24) + (6+24) + 6 = 70 = \binom 8 4$ as expected. The number of covers that consist of three "blocks of two" is 8, as identified by @DilipSarwate.

We now argue that the each of the 70 functions has exactly one prime and irredundant cover. This is not necessary if we are convinced we counted all the covers above, but it doesn't hurt either. Recall that the consensus of $a \wedge b$ and $\neg a \wedge c$ is $b \wedge c$. Further recall that a term of a prime cover is essential (i.e., must be part of any prime cover) if it is not covered by the disjunction of its conjunctions and consensus terms with the other prime implicants of the cover.

Finally, if a prime cover consists of all essential primes, it is the unique prime and irredundant cover. All these are classic results. Since all covers listed above are made of essential primes, they are all unique.

L shapes: --. or --' or '-- or .-- count: 8

T shapes: -'- or -.- count: 4

Z shapes: -.. or ..- count: 4

Each of these shapes is 3-across on the map, so you can shift each across by one to get another boolean function.

total: 16

If you treat the side edges as wrap-arounds you get 32

• The wording of that question was quite confusing, but I think this is what it means... – Sean O'Brien Oct 17 '12 at 12:48
• Yeah the wording of the question is very unclear. Keep in mind that the L-blocks can be covered by only two as well. Also I think the wrap-around of the edges should be included because that wrap-around takes into account renaming the variables (ie: making the x column the y column can produce a shape which appears disconnected on the map) – Sean O'Brien Oct 17 '12 at 13:00
• yeah thats whats confusing me a little now; from my understanding of the maps you try to obtain the minimum # of blocks that covers all the 1's (which in this case is 3) but a couple of my 's', and t maps can be undertaken with 2 blocks of 2 which brings my original total down to 8 if they don't need to overlap – Z Oj Oct 17 '12 at 13:16