12,203 views
38 votes
38 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

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

4 Answers

Best answer
73 votes
73 votes

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)

edited by
5 votes
5 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.
1 votes
1 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.
edited by
Answer:

Related questions

33 votes
33 votes
3 answers
2
go_editor asked Sep 28, 2014
9,364 views
Consider the equation $(123)_5=(x8)_y$ with $x$ and $y$ as unknown. The number of possible solutions is _____ .
52 votes
52 votes
6 answers
3