Question

How many Boolean functions of degree \(n\) are self-dual\(?\)

We define the relation \( \le \) on the set of Boolean functions of degree \(n\) so that \(F \le G\), where \(F\) and \(G\) are Boolean functions if and only if \({\bf{G}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\) whenever \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = 1}}\).

Short answer

There are \({{\bf{2}}^{{{\bf{2}}^{{\bf{n - 1}}}}}}\) self-dual Boolean functions of degree \(n\).

Step-by-step solution

Definition

The complement of an element: \(\bar 0{\bf{ = 1}}\) and \({\bf{\bar 1 = 0}}\).

The Boolean sum \({\bf{ + }}\) or \(OR\) is \({\bf{1}}\) if either term is \({\bf{1}}\).

The Boolean product \( \cdot \) or \(AND\) is \({\bf{1}}\) if both terms are \({\bf{1}}\).

A Boolean function is self-dual iff \(F\left( {{x_1},{x_2}, \ldots ,{x_n}} \right){\bf{ = }}\overline {F\left( {{{\bar x}_1},{{\bar x}_2}, \ldots ,{{\bar x}_n}} \right)} \).

Using the Boolean function

Let \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\) be a Boolean function.

Let us first consider \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\). It has \(n{\bf{ - 1}}\) variables. Since each \({x_i}\) can take on two values (\({\bf{0}}\) or \({\bf{1}}\)), there are \(\underbrace {2 \cdot 2 \cdot \ldots \cdot 2}_{{\bf{n - }}1{\rm{ }}{\bf{repetitions}}{\rm{ }}}{\bf{ = }}{{\bf{2}}^{{\bf{n - 1}}}}\) possible ways to assign values to each of the \(n{\bf{ - 1}}\) variables.

Next, there are \(2\) possible images for each of the \({2^{n - 1}}\) combinations of values of the \(n{\bf{ - 1}}\) variables (that is, the image is either \({\bf{0}}\) or \({\bf{1}}\)) and thus there are \(\underbrace {2 \cdot 2 \cdot \ldots \cdot 2}_{{2^{n - 1}} repetitions{\rm{ }}} = {2^{{2^{n - 1}}}}\) possible ways, so there are \({{\bf{2}}^{{{\bf{2}}^{{\bf{n - 1}}}}}}\). Boolean functions \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\).

Next, it can determine \({\bf{F}}\left( {{{\bf{x}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\) using the self-dual property;

\(\begin{array}{c}{\bf{F}}\left( {{\bf{0,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right){\bf{ = }}\overline {{\bf{F}}\left( {{\bf{\bar 0,}}{{{\bf{\bar x}}}_{\bf{2}}}{\bf{, \ldots ,}}{{{\bf{\bar x}}}_{\bf{n}}}} \right)} \\{\bf{ = }}\overline {{\bf{F}}\left( {{\bf{1,}}{{{\bf{\bar x}}}_{\bf{2}}}{\bf{, \ldots ,}}{{{\bf{\bar x}}}_{\bf{n}}}} \right)} \end{array}\)

Therefore, there are \({{\bf{2}}^{{{\bf{2}}^{{\bf{n - 1}}}}}}\)self-dual Boolean functions \({\bf{F}}\left( {{\bf{1,}}{{\bf{x}}_{\bf{2}}}{\bf{, \ldots ,}}{{\bf{x}}_{\bf{n}}}} \right)\).