A Boolean function F is called selfdual if and only if \(F(x_1 , x_2 , … x_n )…
2014
A Boolean function F is called selfdual if and only if
\(F(x_1 , x_2 , … x_n ) = F(\bar {x_1} ,\bar {x_2} , … \bar {x_n} )\)
How many Boolean functions of degree n are self-dual ?
- A.
\(2^n\) - B.
\((2)^{2^{n}}\) - C.
\((2) ^{n^2}\) - D.
\((2) ^{2^{n–1}}\)
Attempted by 338 students.
Show answer & explanation
Correct answer: D
Answer: 2^{2^{n-1}}
Explanation:
There are 2^n possible input vectors for n Boolean variables. These vectors pair up with their bitwise complements, so there are 2^{n-1} complementary pairs.
For each complementary pair, the function values on the two inputs are tied together by the self-duality condition. Under the usual definition F(x) = NOT F(¬x) the values are opposite; under the alternative symmetry F(x) = F(¬x) the values are equal. In either case one independent binary choice per pair determines both values.
Since there are 2 choices for each of the 2^{n-1} pairs, the total number of self-dual functions is 2^{2^{n-1}}.
Note: This counting argument applies for n ≥ 1.