GATE CSE 2014 | Set 2 | Question: 6

Question

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

• A. $2^n$
• B. $2^{n-1}$
• C. $2^{2^{n}}$
• D. $2^{2^{n-1}}$

Comments

Please explain

---

https://www.geeksforgeeks.org/gate-gate-cs-2014-set-2-question-16/

---

2 conditions for self dual 

1. $f$ must be neutral i.e #(minterms) = #(maxterms) 

2. minterms must be disjoint 

if we have $n$ variables, then $2^n$ minterms 

to satisfy disjoint property, we have to take pairs like $(1,7),(2,6),(3,4)...$ and ther are $\frac{2^n}{2}=2^{n-1}$  such pairs 

from each pair , we can take any 1 minterm. so each pair has $2$ choices and there are $2^{n-1}$ such pairs 

total = $2^{2^{n-1}}$ self dual functions possible. 

---

total function for n varibles is 2^2^n
than half of the function are self dual
Option D is Correct

Answer 1

A function is self dual if it is equal to its dual (A dual function is obtained by interchanging $.$ and $+$).

For self-dual functions,

1. Number of min terms equals number of max terms 
2. Function should not contain two complementary minterms  - whose sum equals $2^{n}-1$, where $n$ is the number of variables.

$${\begin{array}{|c|c|c|c|}\hline
\textbf{}&    \textbf{A}&  \textbf{B}&\bf{C} \\\hline
0&0&0&0 \\1& 0&0&1 \\   2& 0&1&0 \\  3& 0&1&1 \\  4&  1&0&0 \\    5&1&0&1 \\   6& 1&1&0 \\   7&1&1&1\\ \hline   
 \end{array}}$$

So, here $(0,7) (1,6) (2,5) (3,4)$ are complementary terms so in self-dual we can select any one of them but not both.

Totally $2\times 2\times 2\times 2 =2^4$ possibility because say from $(0,7)$ we can pick anyone in minterm but not both.

For example, let $f = \sum (0,6,2,3)$

NOTE: here I have taken only one of the complementary term for min term from the sets.

So, remaining numbers will go to MAXTERMS

For above example, $2^4 =16$ self dual functions are possible 

So, if we have $N$ variables, total Minterms possible is $2^n$

Then half of them we selected so $2^{n-1}$.

Now we have 2 choices for every pair for being selected.

So total such choices $=\underbrace{2\times 2\times 2\times 2\dots 2}_{2^{n-1}\text{ times} }$

$\therefore 2^{2^{n−1}}$ (option D)

Comments

$-−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−$

$Let\ n =2. \\ \rightarrow 2^{2^{n}} boolean funtions\ are\ possible.\\ \rightarrow 2^{2^{n-1}} self-dual funtions\ are\ possible.\\ i.e. 4\ self-dual functions\ are\ possible. \\ \\ --------------------------------\\ A \ \ B \\ 0 \ \ \ 0 \leftarrow 0\ i.e. {a}'{b}' \\ 0 \ \ \ 1 \leftarrow 1\ i.e. {a}'{b} \\ 1 \ \ \ 0 \leftarrow 2\ i.e. {a}{b}' \\ 1 \ \ \ 1 \leftarrow 3\ i.e. {a}{b} \\ \\ --------------------------------\\ (As\ explained\ above\ in\ the\ answer.)\\ Here, (0,3)\ are\ self\ complementary\ terms.\\ Likewise\ (1,2)\ are\ self\ complementary\ terms.\\ \\ --------------------------------\\ Here,\ 4\ possible\ self\ dual\ functions\ are:\\ f_{1} = \sum (0,1)\\ f_{2} = \sum (0,2)\\ f_{3} = \sum (3,1)\\ f_{4} = \sum (3,2)\\ //Observe\ in\ each\ of\ the\ above\ functions,\ one\ term\ is\ chosen\\ //from\ complementary\ pair\ (0,3)\ and\ the\ second\ term\ is\ chosen\ from\\ //the\ complementary\ pair (1,2).\\ --------------------------------\\ \\ Now,\ lets\ verify\ that\ the\ above\ mentioned\ functions\ are\ indeed\ self-dual. \\ \\ Consider f_{3} = \sum (3,1) = ab + {a}'b \\ Dual\ of\ f_{3} = (a+b)({a}' + b)$

$Likewise\ we\ can\ verify\ that\ f_{1},\ f_{2},\ f_{4}\ also\ are\ self-dual\ functions.$

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

---

Thanks a lot @Higgs

---

A self-dual function must satisfy F(x', y') = ¬F(x, y). So for each pair (x,y), F(¬x, ¬y) must be the negation of F(x,y). Let's consider the truth table for F. For n=2, there are 4 inputs: (0,0), (0,1), (1,0), (1,1). For the function to be self-dual, F(0,0) must be ¬F(1,1), and F(0,1) must be ¬F(1,0).

So the truth table is determined by half of the entries. For n=2, how many free variables do we have? F(0,0) can be chosen freely, but then F(1,1) is determined. Similarly, F(0,1) can be chosen freely, and F(1,0) is determined. However, there's a catch when the input is self-dual. In this case, for n=2, the inputs (0,0) and (1,1) are duals, (0,1) and (1,0) are duals. So each pair must have opposite values.

Therefore, the number of self-dual functions for n=2 is 2^(2^{n-1}) = 2^{2^{1}} = 4. For n=2, the number of independent choices is 2^{2^{n-1}} = 4, we can choose F(0,0) and F(0,1) freely, each being 0 or 1, and the other entries are determined. So 2^2 = 4, which matches.

So for n=2, the answer would be D: 2^{2^{n-1}}.

Answer 2

Truth Table of $F(x, y)$

List all input combinations in standard binary order and denote the output values as $a_1, a_2, a_3, a_4$:

$$
\begin{array}{|c|c||c|}
\hline
x & y & F(x, y) \\
\hline
0 & 0 & a_1 \\
0 & 1 & a_2 \\
1 & 0 & a_3 \\
1 & 1 & a_4 \\
\hline
\end{array}
$$

Complement the Inputs and Evaluate $F$

Now construct a new column: for each row, complement both inputs and write the value of $F$ at that new input point.

$$
\begin{array}{|c|c||c|c|}
\hline
x & y & F(x, y) & F(\overline{x}, \overline{y}) \\
\hline
0 & 0 & a_1 & F(1, 1) = a_4 \\
0 & 1 & a_2 & F(1, 0) = a_3 \\
1 & 0 & a_3 & F(0, 1) = a_2 \\
1 & 1 & a_4 & F(0, 0) = a_1 \\
\hline
\end{array}
$$

Observe that the values in the fourth column are the values of $F$ in reverse order: $(a_4, a_3, a_2, a_1)$.

Step 3: Definition of the Dual Function

The dual of a Boolean function, $F^D(x, y)$, is defined by the following rule on any Boolean expression for $F$:

• Replace every OR ($+$) by AND ($\cdot$),
• Replace every AND ($\cdot$) by OR ($+$),
• Do not change any literals (i.e., $x$ remains $x$, not $\overline{x}$).

This is a purely syntactic transformation. However, to find the truth values of $F^D$, we do not need the expression we can use the following key observation.Consider what happens when we complement all literals in $F$ (i.e., replace $x$ with $\overline{x}$, $y$ with $\overline{y}$) and then complement the entire function output. This operation, $\overline{F(\overline{x}, \overline{y})}$, reverses the roles of AND and OR due to De Morgan’s laws:

• A product term $x \cdot y$ becomes $\overline{x} \cdot \overline{y}$; its complement is $\overline{\overline{x} \cdot \overline{y}} = x + y$.
• A sum term $x + y$ becomes $\overline{x} + \overline{y}$; its complement is $\overline{\overline{x} + \overline{y}} = x \cdot y$.

Thus, complementing all inputs and then complementing the output has the same effect as swapping AND and OR in the original expression, while leaving the original variables unchanged—which is exactly the definition of the dual.

Therefore, the truth table of $F^D$ is identical to that of $\overline{F(\overline{x}, \overline{y})}$.

Complete Truth Table with Dual Column

Now compute $\overline{F(\overline{x}, \overline{y})}$ by complementing the fourth column from Step 2:

$$
\begin{array}{|c|c||c|c|c|}
\hline
x & y & F(x, y) & F(\overline{x}, \overline{y}) & \overline{F(\overline{x}, \overline{y})} = F^D(x, y) \\
\hline
0 & 0 & a_1 & a_4 & \overline{a_4} \\
0 & 1 & a_2 & a_3 & \overline{a_3} \\
1 & 0 & a_3 & a_2 & \overline{a_2} \\
1 & 1 & a_4 & a_1 & \overline{a_1} \\
\hline
\end{array}
$$

Hence, we see explicitly that:

• $F^D(0,0) = \overline{a_4} = \overline{F(1,1)}$,
• $F^D(0,1) = \overline{a_3} = \overline{F(1,0)}$,
• $F^D(1,0) = \overline{a_2} = \overline{F(0,1)}$,
• $F^D(1,1) = \overline{a_1} = \overline{F(0,0)}$.

This confirms the identity:
$$
F^D(x, y) = \overline{F(\overline{x}, \overline{y})}.
$$

Self-Duality Condition

A function is self-dual if $F(x, y) = F^D(x, y)$ for all inputs. From the table, this requires:

$$
\begin{aligned}
a_1 &= \overline{a_4}, \\
a_2 &= \overline{a_3}.
\end{aligned}
$$

Thus, only $a_1$ and $a_2$ can be chosen freely; $a_3$ and $a_4$ are then determined. This gives $2^2 = 4$ self-dual functions for $n = 2$.For $n$ variables, the $2^n$ input combinations form $2^{n-1}$ pairs $(\mathbf{x}, \overline{\mathbf{x}})$. Self-duality imposes one constraint per pair, leaving $2^{n-1}$ independent binary choices. Hence, the total number of self-dual Boolean functions of $n$ variables is:

$$
\color{lime} \boxed{2^{2^{\,n-1}}}
$$

Comments

Awesome explanation thank you for writing such detailed answer @parity

---

Thank you for this explanation! it was really great.

Answer 3

The question asks for no: of self-dual functions for n variables. Principle of Duality: Any theorem or identity in Boolean algebra remains true if 0 and 1 are swapped and . and + are swapped throughout. There are two properties for self-dual functions: 1. It is neutral (no of minterms = no of maxterms) 2. A single function does not contains two mutually exclusive terms. Considering the above properties. If we have n-variable then we have 2^n minterms/maxterms From 2^n minterms/maxterms there are (2^n)/2 mutually exclusive pairs. ie 2^(n-1) So we have 2^(n-1) pairs to use to make self-dual functions. So, by Fundamental principle of counting, because each pair in 2^(n-1) has two choices. No of self-dual functions from n-variables are = 2*2*2...2^(n-1) times = 2^(2^(n-1)) or example if n=3 We have minterms as(000,001,010,...,111) Mutually exclusive pairs are (0,7),(1,6),(2,5),(3,4) The pairs are mutually exclusive since they cannot come in a self-dual function together. So here we have.2*2*2*2 functions ie 16.

Answer 4

A boolean function is self-dual, if it is negated by negating all inputs.

>f(x1,x2,...xn)=¬f(¬x1,¬x2,...¬xn)

This implies that for each of the $2^{n}$ input combinations, there is another combination with the opposite function value. Therefore, the function table must have $2^{n−1}$ rows with function value true and the same number of rows with function value false...

As the self-dual functions are fully defined by $2^{n−1}$of the $2^{n}$ truth table entries, the output column can be interpreted as binary number with $2^{n−1}$ bits. This leads to $2^{2^{n−1}}$different self-dual functions.

Answer 5

Here is answer : 

Answer 6

Here is the answer without using the concept minterm and maxterm: I found this intuitive.