I came across this slides which states following two theorems:
Theorem There are $2^{2^{n-1}}$ different self-dual functions of $n$ variables.
Theorem Let $f$ be a self-dual function of $n$ variables, and let $|f|$ be the number of inputs a for which $f(a) = 1$, then $|f| = 2^{n-1}$
However, it does not give any proof. Also, I tried to deduce it on my own but not moving with anything. How can these theorems be proved?
Best Answer
A boolean function is self-dual, if it is negated by negating all inputs.
$$f(x_1, x_2, ... x_n) = \lnot f(\lnot x_1, \lnot x_2, ... \lnot x_n)$$
This implies that for each of the $2^n$ input combinations, there is another combination with the opposite function value. Therefore, the function table must have $2^{n-1}$ rows with function value $true$ and the same number of rows with function value $false$.
As the self-dual functions are fully defined by $2^{n-1}$ of the $2^n$ truth table entries, the output column can be interpreted as binary number with $2^{n-1}$ bits. This leads to $2^{2^{n-1}}$ different self-dual functions.
Example for clarification
taken from chapter 5 of
Tsutomu Sasao: Switching Theory for Logic Synthesis
The dual function of $(x \land y) \lor (z \land w)$ is $$\overline{(\bar x \land \bar y) \lor (\bar z \land \bar w)} = (x \lor y) \land (z \lor w)$$ The identity expressed in De Morgan's Theorem 1:
The negation of a disjunction is the conjunction of the negations.