How many boolean functions of $n$ variables exists that can be written as one product

Question

I want to calculate the number of boolean functions of $n$ variables that can be written as one product of some literals.

For example, such functions of 4 variables could be

$ f(x_1,x_2,x_3,x_4)=x_1x_2$

$f(x_1,x_2,x_3,x_4)=x_1'$

(Where $x_1'$ means the complement of $x_1$ in boolean algebra).

I know that the final answer should be $3^n+1$ but have no idea how to prove it.

My first thought is that there are $n$ options to choose the first variable (between $x_1$,...,$x_n$) and so $n \cdot 2$ options to choose the first literal, $n-1$ options to choose the second variable and so $(n-1) \cdot 2$ options to choose the second literal, so there are $n!/(n-k)! \cdot 2^k.$ Now since we also dont care about the order we should divide by $k!$ which brings us to $\binom{n}{k} \cdot 2^k$ and if we will sum over k from 0 to n, it is equal to $(2+1)^n $ which is $3^n$ and Im not sure where the extra 1 comes from.

Any help would be appreciated.

Answer 1

Any product that contains both $x_i$ and $x_i'$ yields $0$. Otherwise, for each $i$, you have three choices: $x_i$, $x_i'$, or neither, yielding $3^n$ additional functions.