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

Best answer
52 votes
52 votes
$2^{n-1} $ to $1$

We will map $(n-1)$ variables  to select lines  and $1$ variable to input line
selected by
75 votes
75 votes

As we know that mux is a fully functionally complete circuit(It can implement any Boolean function).we know that if I have 4 *1 mux than I can implement any function with 2 variables.and if I have 8*1 mux then I can implement any function with 3 variables but how??? Actually, in 8 *1 mux, I have 3 select lines and 8 inputs and these 8 inputs are actually minterms(or combinations possible with 3 variables). So, I can assign a value to each of 8 Combinations based on the select lines.

So, in the same way, I can implement an "n" variable function with the help of 2n *1 MUX. But now the actual question comes that is: can I implement a 3 variable function with 4*1 MUX or Can I implement an "n+1" variable function with 2n * 1 MUX????

So, here the answer is yes, I can implement 3 variable functions with 4*1 MUX OR I can implement "n+1" or more than this with 2^n *1 MUX. But how, so I will show u with an example

I have explained in the above page in a very easy way. In the same way, I can implement more than "n" variable function with 2n * 1 MUX.So what I need to do is, for implementing 3 variable functions with 22 * 1 MUX, I need to give(3-1) select lines and one output line. In the same go, u know that they have given 1 multiplexor and one, not gate, for implementing a function of "n" variable and they are asking about what would be a minimum size of a multiplexor, so out of n variables, "n-1" will be select lines and one output line. So minimum size of multiplexor = 2n-1 * 1

edited by
19 votes
19 votes
Answer :-> C

What is wrong with D option ->

Assume that you need to implement A+B+C , 3 variable boolean function .
You have given 2^n-2 to 1 mux  i.e. 2 to 1 mux & 1 inverter.

Suppose you decide to connect A as select line of 2 to 1 mux.

Now when A = 1, you can happily connect 1 to input I1, but when A = 0, you got to connect B+C to I0 . Which is not possible as you don't have B+C. For B+C you need OR gate so D is false.

C is enough, that inverter takes care of cases in which we need to invert input to connect to input line.

For A you don't need to use inverter. B is overkill.
10 votes
10 votes

"With $2^n:1$  Mux, We can implement all n variable functions, and some n+1 variable function"

Lets take a small example, with n=3:

 

f(A,B,C) = Σm(0, 1, 3, 6, 7)

 

A B C     F 

0 0 0      1

0 0 1      1

0 1 0      0 

0 1 1      1 

1 0 0      0

1 0 1      0

1 1  0     1

1 1  1     1 

We can easily implement this with $2^3 * 1$ Mux 

The implementation is: 

 

Now Lets take another function, f (A,B,C) = Σm(2, 4, 5, 6)

Can we implement this 3 var function with $2^2 \times 1$  i.e  $4 \times 1$ Mux ? 

No, as 4 x1 Mux have only 4 inputs but we have total 8 inputs.

So, Not possible. 

 

But if we have an extra NOT gate, then we can implement this easily. 

A B C     F 

0 0 0      0

0 0 1      0

0 1 0      1

0 1 1      0

1 0 0      1

1 0 1      1

1 1  0     1

1 1  1     0

Now check the below implementation: 

 

Here, we have taken A, B as Select lines, so it will have 00, 01, 10, and 11 combinations and the output will depend on C inputs.

Now if we observe the truth table, we will find  F values in 1st and 3rd case are independent of C.

But in 2nd and 4th case it is complement of C.

That why here we need a Not gate to take complement of C as Input. 

So we can implement this 3 var function with 2³⁻¹ MUX using an extra NOT gate. 

 

In general, 

If Invertor is available, then we can implement n var function with 2ⁿ⁻¹ x 1 MUX

 

So Option C. is the correct ans.

 

 

Note:

 

We can use $2^n \times 1$ Mux to implement “some” $n+1$ var functions also “without Using NOT gate”

 

f(A,B,C) = Σm(0, 1, 3, 6, 7)

 

A B C     F 

0 0 0     1

0 0 1     1

0 1 0     0 

0 1 1     1 

1 0 0     0

1 0 1     0

1 1 0     1

1 1 1     1 

 

We can implement this using 4x1 Mux without using any NOT gate also (even though it is 3 var fun) 

edited by
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}& ...