How many Boolean functions of degree n are self-dual?
2014
How many Boolean functions of degree n are self-dual?
- A.
2n
- B.
(2)2n
- C.
2 n^2
- D.
(2) ^ (2 n-1)
Attempted by 195 students.
Show answer & explanation
Correct answer: D
A Boolean function of degree n is self-dual if f(x) equals not f(not x). Input vectors form 2^(n-1) complementary pairs. For each pair, the function value determines the other, leaving 2 choices per pair. Thus, there are 2^(2^(n-1)) self-dual functions.
A video solution is available for this question — log in and enroll to watch it.