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?
On
As a related note to the question above, the dual of a Boolean function is the complement of the original function, but with all inputs complemented. Thus, a self-dual boolean function would be such that its complement is the same as the function when its inputs are complemented.
A relatively easy way to prove this is based on the fact that each Boolean function has a unique SOP and POS representation. Say we have a function $f$, of $N$ boolean variables, $A_1, A_2, ... A_N$. Then
$$f(A_1, A_2, ...A_N) = \sum_{i\in I} m_i = \prod_{j\in I^C} M_j $$
where $m_i$ is a minterm which is part of that function's 'on-set' ($I$), $M_j$ is a maxterm and part of the function's 'off-set' ($I^C$). Note that the set $I$ is a subset of integer values between 0 and $2^N - 1$.
From de Morgan's law, we can easily prove that $m_i = M_i'$, that is, the i-th minterm is the complement of the i-th maxterm.
Using the classical definition of a Boolean dual (exchange $\cdot$ and $+$, 0s and 1s), the dual of the function $f$ is:
$$f^D(A_1, A_2, ... A_N) = \prod_{i\in I} m_i^D $$
where $m_i^D$ is the dual of the i-th minterm. It can be shown that $m_i^D = M_{2^N - i - 1}$ (for e.g. for a function of 2 Boolean variables, $m_1 = A_1'A_2$ $\Longrightarrow m_1^D = A_1' + A_2 = (A_1 A_2')' = m_2' = M_2$). Thus,
$$f^D(A_1, A_2, ... A_N) = \prod_{i\in I} m_i^D = \prod_{i\in I} m'_{2^N-i-1} $$ which, from de Morgan's law, gives us $$f^D(A_1, A_2, ... A_N) = (\sum_{i\in I} m_{2^N-i-1})'$$
$\because$ the i-th minterm is the same as the $(2^N - i - 1)$-th minterm with complemented inputs,
$$f^D(A_1, A_2, ... A_N) = (f(A_1', A_2', ... A_N'))'$$
Thus, for a self-dual function, $$f(A_1, A_2, ... A_N) = (f(A_1', A_2', ... A_N'))'$$
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.