The GATE Grind

GATE 2014 CS (CS2) – Question 16

Digital Logic · Boolean Algebra and Minimization · 1 mark · Multiple choice

The dual $F^D$ of Boolean function $F(x_1,\ldots,x_n,+,\cdot,{}^\prime)$ swaps + and ·. F is self-dual when $F=F^D$. How many self-dual functions of n Boolean variables exist?

  1. $2^n$
  2. $2^{n-1}$
  3. $2^{2^n}$
  4. $2^{2^{n-1}}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $2^{2^{n-1}}$

Explanation

Self-duality requires f(x)=¬f(¬x). The2ⁿinput rows form2^(n−1) complementary pairs; selecting the output on one member forces the other. Two independent choices per pair give **2^(2^(n−1)),D**. The choices are of truth-table entries rather than expressions.