GATE CS 2014 Set 2 Q6 — Boolean Algebra

A Boolean function $F(x_1, x_2, ', x_n)$ of $n$ variables has $2^n$ possible input combinations (rows in its truth table).

By definition, a function $F$ is self-dual if and only if: $$F(x_1, x_2, \dots, x_n) = \overline{F(\bar{x}_1, \bar{x}_2, \dots, \bar{x}_n)}$$

This condition imposes a constraint on the outputs of complementary input combinations:

• We can group the $2^n$ input combinations into $2^{n-1}$ complementary pairs of the form $(x, \bar{x})$.
• For any such pair, if we assign a value to $F(x)$, the value of $F(\bar{x})$ is uniquely determined as its complement. Specifically:
  • If $F(x) = 0$, then $F(\bar{x})$ must be $1$.
  • If $F(x) = 1$, then $F(\bar{x})$ must be $0$.
• Thus, for each of the $2^{n-1}$ pairs, we have exactly $2$ choices for the output assignment.

Since the choice for each pair is independent of the others, the total number of self-dual functions is: $$\underbrace{2 \times 2 \times \dots \times 2}_{2^{n-1} \text{ times}} = 2^{2^{n-1}}$$

Therefore, the correct option is D.