2
$\begingroup$

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)$$

$\endgroup$
  • $\begingroup$ Are the $x_i$ fixed? $\endgroup$ – Kai Nov 8 '18 at 21:48
  • $\begingroup$ I'm pretty sure they aren't fixed $\endgroup$ – Gabi G Nov 8 '18 at 21:55
  • 2
    $\begingroup$ 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$? $\endgroup$ – Kai Nov 8 '18 at 22:06
  • $\begingroup$ @Kai This is an answer to the question. Post it as such? $\endgroup$ – Yuval Filmus Nov 8 '18 at 22:18
  • 1
    $\begingroup$ aww, did I give away too much? $\endgroup$ – Kai Nov 9 '18 at 10:43
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.