A Boolean function F of n variables is self-dual if and only if F(x1, x2, …,…

Concept

A self-dual Boolean function assigns opposite output values to complementary input vectors: the value at x determines the value at ¬x.

For n ≥ 1, the 2n input vectors form disjoint complementary pairs, and each pair contributes one independent binary choice.

Application

1. There are 2n possible n-bit input vectors.

2. No n-bit vector equals its own complement, so these vectors form 2n−1 complementary pairs.

3. Within each pair {x, ¬x}, choosing F(x) fixes F(¬x) = ¬F(x); therefore each pair allows exactly two assignments.

4. Independent choices across all pairs give 2 raised to the number of pairs: 22⁽ⁿ⁻¹⁾.

Cross-check with n = 2

The four inputs split into the following two complementary pairs:

Each pair permits two opposite-output assignments, so the total is 2 × 2 = 4. The formula also gives 22⁽²⁻¹⁾ = 22 = 4.

Result: the number of self-dual Boolean functions is 22⁽ⁿ⁻¹⁾.