The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
3.3k views

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}}$
asked in Digital Logic by Veteran (103k points) | 3.3k views
0
Please explain
0

.....

4 Answers

+38 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,

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

answered by Active (2.1k points)
edited by
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
0
That is we need to complement only first literal?
0

dint get your question "FIRST"  literal in the sense?

0
Can you please elaborate mutually exclusive .........How are 1 and 7 mutually exclusive....? 1 is 001 and its complement 110 i.e 6
0
ohh sorry i written by mistake 1,7 it should be 0,7
Thanx for correction i'll update it ...
+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
yes, that should be a typo.
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 2n 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 

0

@kaplish, why 22n-1. Why 2 raise to d power of 2n-1. 2n-1 is understandable. But why 2?

+3

See how much I understand here.

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

Now from n boolean variable 2n 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))

0
I didn't understood , explain me by giving example
+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.
answered by Loyal (8.5k points)
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.
answered by (105 points)
edited by
–2 votes

It's (D)

answered by Loyal (7.6k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,079 questions
47,675 answers
147,469 comments
62,393 users