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 !
On
For any self-dual function, the number of it's minterms must be equal to it's number of maxterms. Also, no two complementary minterms must be present in the function. By complementary minterms, I mean those whose sum is equal to $n$, the number of variables of the function. Hence there will be $2^{n-1}$ such complementary minterm pairs, one can select atmost one minterm from each of the pairs and should select one from all pairs to get a self dual function. That can be done in $2^{2^{n-1}}$ ways, which gives the total number of self dual functions.
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: