Dark Mode

go_editor
asked
in Digital Logic
Sep 28, 2014

9,266 views
33 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}}$

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

$${\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)

1

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

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

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

5

3 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 vote

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.