How many functions of n input variables that can be written as a single multiple of literals of any length (between 1 and n) are there?

I've seen the answer is (3^n)+1 but didn't really understand why.
I'll be happy to see the explanation

 

Is this homework?

How would you go about enumerating them?

If you have, say, 4 variables how many single multiples are there of length 1? How do you find that out given n?

How many of length 2? How do you find that out given n?

How many of length 3? How do you find that out given n?

How many of length 4? How do you find that out given n?

In general, how many single multiples of k distinct variables are there given n variables to choose from?

Now sum them up for k=1 through k=n?

 

It's a test review, I suppose it fits to homework as well, wasn't sure where to put it, since it's more of combinatorics question than
electrical engineering.

I'm still not sure how to go with it, 2^(n-literals)=number of boxes in karnaugh maps.
from here I can manually figure out the number on a 4 variable function,
but I'm not sure how to treat it for n inputs function karnaugh map.

I can't use binomial coefficient because the boxes have to be adjacent in order to get a single multiple.

 

Let's first be sure that we both understand the question, as right now I don't think I do (not with that answer, anyway).

Let's say that I only have one variable, {A}. Then there is only a single function that I can write that has at least one of the variable:

f(A) = A

But the equation says there should be 4.

Let's say that I have two variables, {A,B}. How many ways are there to write functions that consist of a "single multiple of literals" of any length from 1 to 2?

f(A,B) = A
f(A,B) = B
f(A,B) = AB

But the equation says that there should be 10.

Notice that if we change the equation slightly, we can match these two data points:

3^(n-1) yields 1 for n=1 and 3 for n=2.

But does it hold up for n=3?

f(A,B,C) = A
f(A,B,C) = B
f(A,B,C) = C
f(A,B,C) = AB
f(A,B,C) = BC
f(A,B,C) = AC
f(A,B,C) = ABC

There are 7 when the modified equation claims 9 (while the original equation claims 28).

So there is a disconnect somewhere.

Does the question make clear what is meant by a "single multiple of literals"? The very notion of "multiple of literals" is poorly defined since, in Boolean logic, you don't really multiply literals together -- that is an illusion owing to the common notation that is used for the logical AND operation. But I can't think of any other way to interpret it.

Perhaps they mean including complements? That would tie in better with the notion of K-map groupings.

1 variable

f(A) = A
f(A) = A'

I see no way to come up with 4 different functions with only 1 variable unless you include f(A) = 0 and f(A) = 1, but these are functions using 0 variables and your problem statement explicitly requires at least one variable be used.

f(A,B) = A
f(A,B) = A'
f(A,B) = B
f(A,B) = B'
f(A,B) = AB
f(A,B) = AB'
f(A,B) = A'B
f(A,B) = A'B'

If we change the equation to (3^n) - 1, then this works for both. I think the (3^n) + 1 might include functions consisting of 0 to n variables.

See what you get for 3 variables.

 

I think you're right about the 0 thing.
anyway looks like it workd for 3, but according to this logic
the number of functions should be

(noting (a,b) as binom)
l=n
sum[(2^l)*(n,l)] + 2
l=1
No?

 

I'd have to think about it some, but you are on the right track for coming up with a valid expression. However, I don't see any easy trick to evaluating that finite sum and putting it in the closed form that we are shooting for.

But there's a much cleaner way to go about it.

Consider that, for four functions, each of your functions can be written in the form:

f(A,B,C,D) = a(A)·b(B)·c(C)·d(D)

And each of the individual functions, such as a(A), is a single term function of one variable, of which there are four, but only three that are meaningful, namely A, B, and TRUE. The case where it is FALSE will result in a LOT of degenerate functions since if ANY of the individual functions is FALSE then the overall function is FALSE. But if we exclude that, then every combination of the three remaining choices yields a distinct overall function. We just need to count how many of those there are. This reduces to asking how many n-digit values can be represented in base-3? But this excludes one case, namely the case in which the output is always FALSE. Note that it DOES include the case where the output is always TRUE. So we just need to add one more to the list of functions.

 

Seems right, Thank you. This was very helpful