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/

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

What i conclude  

no of minterm n, so we have 2 option either to select or not

but again one constrain we are having in pairs, it reduces to half

(2^n)/2

these are possible combination

again we have two option for each combination

whether to select it or not

therefore  2^(2^(n−1))

---

I didn't understood , explain me by giving example

---

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

$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.$

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

Answer 2

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 3

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 4

It's (D)