GATE CS 2014 Set 2 Q.16 (CS Q.6): Boolean Algebra and Logic Minimization

The dual of a Boolean function $F(x_1, x_2, \dots, x_n, +, \cdot, ')$ , written as $F^D$ , is the same expression as that of $F$ with $+$ and $\cdot$ swapped. $F$ is said to be self-dual if $F = F^D$ . The number of self-dual functions with $n$ Boolean variables is

$2^n$

$2^{n-1}$

$2^{2^n}$

$2^{2^{n-1}}$

Official answer and solution

Official answer: D
From: Official GATE 2014 answer key

Solution

Use the property that self-dual Boolean functions are constrained by complementary pairs of truth table entries.

Definition of Self-Dual Function:
A function $F(x_1, \dots, x_n)$ is self-dual if $F = F^D$ , which is algebraically equivalent to:
$F(x_1, x_2, \dots, x_n) = \overline{F(\overline{x_1}, \overline{x_2}, \dots, \overline{x_n})}.$
Truth Table Combinations:
- A Boolean function with $n$ variables has $2^n$ distinct input combinations (minterms).
- Each minterm $m$ has a unique complementary minterm $m' = 2^n - 1 - m$ where every bit is inverted.
- These form exactly $\frac{2^n}{2} = 2^{n-1}$ mutually exclusive pairs of complementary minterms.
Degrees of Freedom:
- For any pair of complementary minterms $(m, m')$ , if we assign $F(m) = b \in \{0, 1\}$ , the self-dual condition strictly fixes $F(m') = 1 - b$ .
- Therefore, we have an independent binary choice (0 or 1) for only $2^{n-1}$ input pairs.
Total Number of Self-Dual Functions:
$N = 2^{2^{n-1}}.$

This matches option D.

Final answer

Common trap

Confusing 2^(2^(n-1)) with 2^(2^n - 1) or 2^(n-1).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 2
Question: 16 of 65, printed as CS Q.6
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source