The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

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

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

+40 votes

Best answer

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

For self-dual functions,

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

A | B | C | |

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 |

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

and 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} }$

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

0

Can you please explain "mutually exclusive terms" ...How can we decide mutually exclusive terms here..?

+3

A mutually exclusive term is one....... if we write canonical form of term (ie containing all Variable in each term either in term of its complemented or original form eg AB'C=5 (101 binary ) )

now if AB'C is a term then A'CB' (i.e 2 (010 binary)) is its mutually exclusive term

now if AB'C is a term then A'CB' (i.e 2 (010 binary)) is its mutually exclusive term

0

Can you please elaborate mutually exclusive .........How are 1 and 7 mutually exclusive....? 1 is 001 and its complement 110 i.e 6

+3

you have taken both mutually exclusive terms together ∑(1,6,2,3) Here 1 and 6 is in same pair ...Don't you think its wrong.

0

The only thing given is that dual of a fn is obtained by make $+ --> .$ and vice versa. So we can figure out that if $ f = f D$ then number of minterms will be same in both.. but from where you came to this mutual exclusive thing..

0

What do u mean by no of minterms equal to no of max terms bro my doubt is that for a n variable we will have 2^{n} maxterms and mi terms what do u mean by equal no of min terms equal to max how do u want me to compare a minterms and max term

+3

See how much I understand here.

It is a boolean function. i.e. 0,1

Now from n boolean variable 2^{n} boolean function possible.

As it is self dual function ,so, Say elements are 00,01,10,11

here 00 can map in 11.

So, we can say total number of boolean variable exists $\frac{2^{n}}{2}$

Now from this much of variable self dual function possible $2^{2^{n-1}}$

0

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))

+2

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

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

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

0 votes

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.

0 votes

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.

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users