edited by
31,278 views
68 votes
68 votes

Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of $n$ variables. What is the minimum size of the multiplexer needed?

  1. $2^n$ line to $1$ line

  2. $2^{n+1}$ line to $1$line

  3. $2^{n-1}$ line to $1$line

  4. $2^{n-2}$ line to $1$line

edited by

9 Answers

8 votes
8 votes

In MUX single input line is enough to generate different kind of output signal. Because different kind of output depend on select line, not on input line

See for 3 variable, we can just 1 as input line, 2 as select line

if Say X is input line, and A,B are select line

then outputs are A'B'X+A'BX+AB'X+ABX

So, output variation depend on only select line , not input line .confirmed!!

But here NOT gate actually not doing any  huge difference.

It only giving some input as NOT signal.

So, without NOT gate, without NOT gate, with buffer  any case we get $2^{n-1}$ line to 1 line

I think same case going to happen with AND, OR............with any gate also

1 votes
1 votes
We know that there are 2^n distinct functions but exactly half of them are inverse of each other like x and ~x , x EXOR y and x EXNOR y (in case of even no. Input) such complements can be easily implemented by using negation operator hence only 2^n-1 lines are enough
1 votes
1 votes
Both true and complement forms of all variables are necessary to implement any function of n variables.
A $2^n$ X 1 multiplexer can implement any function of n variables. As n variables are given to select lines, so that true and complement forms of all variables get generated inside the MUX.
As one inverter is available, we can generate complement of one variable outside of the Multiplexer. And remaining (n-1) variables are given to select lines. With this we have true and complement form of all n variables.
So, the answer is $2^n$-1 X 1 MUX.
0 votes
0 votes
we can implement n+1 variable  functions with $2^n *1$ MUX by providing n variables to n  select lines and 1 variable can be given to input lines , either in pure form or complimented form.(according to function)

In Complimented form we may need a NOT gate

so with a NOT gate we need $2^n$$^-$$^1$ *1 MUX

check yourself by implementing 3 variable function with $2^2$ * 1 MUX
Answer:

Related questions

66 votes
66 votes
6 answers
2
Kathleen asked Sep 21, 2014
19,176 views
The control signal functions of a $4$-$bit$ binary counter are given below (where $X$ is “don’t care”):$$\small {\begin{array}{|c|c|c|c|l|}\hline\textbf{Clear}& ...