# how many boolean functions exist that satisfy the condition

How many boolean functions exist that satisfy the following condition? $$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$

• Are the $x_i$ fixed? – Kai Nov 8 '18 at 21:48
• I'm pretty sure they aren't fixed – Gabi G Nov 8 '18 at 21:55
• It's a counting exercise. Realise that whenever you choose $f(x_1,\ldots , x_n) = b$ for fixed $x_1,\ldots , x_n$, you fix $f(\neg x_1,\ldots , \neg x_n) = \neg b$. So how many choices do you have to make to fully determine $f$? – Kai Nov 8 '18 at 22:06
• @Kai This is an answer to the question. Post it as such? – Yuval Filmus Nov 8 '18 at 22:18
• aww, did I give away too much? – Kai Nov 9 '18 at 10:43

If we did not have this constraint, there would initially be $$2^{2^n}$$ possible boolean functions on $$n$$ boolean variables. We have $$2^n$$ unique inputs that we can either map to a 1 or 0 for any of them.

Now for this problem, we need to map a subset of those $$2^n$$ inputs because the rest will be implicitly mapped. For instance if we map $$f(x_1, \neg x_2, \neg x_3) = 0$$, this will implicitly map $$f(\neg x_1, x_2, x_3) = 1$$. This means only a subset of the $$2^n$$ inputs can be uniquely mapped, the rest will be implicitly mapped as described. For this, we need to determine how many pairs of inputs exist such that we have: $$(\{\ell_1, \ell_2, \ldots \ell_n\}, \{\neg \ell_1, \neg \ell_2, \ldots, \neg \ell_n\})$$ where $$\ell_i$$ is a literal (positive or negative) containing variable $$x_i$$. Intuitively, we should know that each pair contains 2 sets of $$n$$ variables so there should be $$2^n / 2 = 2^{n-1}$$ pairs possible. Another way to think about it would be to hold one variable constant positive, let's say $$x_1$$. We then define a new function: $$f_{x_1}(x_2, x_3, \ldots, x_n) = \ldots$$ In this function we "hold" $$x_1$$ to be positive so that we're only ever setting one of the sets in these pairs that we have described, thus we only have $$2^{2^{n-1}}$$ possible functions $$f_{x_1}$$. With this, we can now define $$f$$ pretty easily:

$$f(x_1, \ell_2, \ell_3, \ldots \ell_n) = f_{x_1}(\ell_1, \ell_2, \ldots, \ell_n)$$

$$f(\neg x_1, \neg \ell_2, \neg \ell_3, \ldots \neg \ell_n) = \neg f_{x_1}(\ell_1, \ell_2, \ldots, \ell_n)$$

We basically use $$x_1$$ to say "we're looking at the positive instance of this input" vs "we're looking at the negative instance of this input". Then this configuration of $$f_{x_1}$$ will ensure they are opposite. Consider the following example on 3 variables:

$$\begin{array}{|c|c|c|c|} \hline x_1 & x_2 & x_3 & f_{x_1}(x_2, x_3) & f_{x_1}(\neg x_2, \neg x_3) & f(x_1, x_2, x_3) \\ \hline 0 & 0 & 0 & 1 & 0 & 1\\ \hline 0 & 0 & 1 & 1 & 1 & 0\\ \hline 0 & 1 & 0 & 1 & 1 & 0\\ \hline 0 & 1 & 1 & 0 & 1 & 0\\ \hline 1 & 0 & 0 & 1 & 0 & 1\\ \hline 1 & 0 & 1 & 1 & 1 & 1\\ \hline 1 & 1 & 0 & 1 & 1 & 1\\ \hline 1 & 1 & 1 & 0 & 1 & 0\\ \hline \end{array}$$

With this we can see $$f_{x_1}$$ is clearly a function over $$n-1$$ variables and thus there are $$2^{2^{n-1}}$$ possible functions that satisfy this.