The dual of a Boolean function $F(x_1,x_2 \dots x_n,+,\bullet)$, written as $F^D$, is the same expression as that of $F$ with $+$ and $\bullet$ swapped. $F$ is said to be self-dual if $F=F^D$. What is the number of self-dual functions with $n$ Boolean variables?
I have no clue where to begin with. Any subtle hint would be great.
Thanks !
Best Answer
the notion of dual function you introduce is not well-defined. A self-dual expression is well-defined but a given function can have two expressions, one being self-dual and the other not self-dual, for example: $x$ and $x∙x$ both define the identity function but one expression is self-dual, the other not. (here, I suppose that you're working with the $Z/2Z$ ring, i.e. $+$ is XOR and $∙$ is AND, but the same problem arises in the Boolean lattice, i.e. OR/AND setting).
the classical definition of self-dual boolean function is a function that commutes with the permutation 0/1 (i.e. negation $\neg$), precisely: $f(x_1,...,x_n) = \neg f(\neg x_1, ..., \neg x_n)$.
the origin of your confusion maybe comes from the fact that the dual of a monotonic function (i.e. in the OR/AND setting) is obtained by inverting OR and AND in the minimal disjunctive form.
So what do you want to count: self-dual expressions (in which setting)? self-dual function in the classical sense? self-dual monotonic functions?
Update after comment:
For monotone self-dual function, two possible approaches: