The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+30 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

asked in Digital Logic by Veteran (59.5k points)
edited by | 4.1k views
Plz explain
Read any book for digital logic or search this question on google. Can't be explained here
For an intuition, think about the way we create a Variable Entrant K-Map.

By using 2∗ 1 we can implement all 'n' variables functions can be implemented but only some of the functions of  'n+1' can be implemented. However, if we are having an Inverted gate in addition, we can implement all 'n+1' variable functions as well.  

5 Answers

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

We will map $(n-1)$ variables  to select lines  and $1$ variable to input line
answered by Loyal (8.1k points)
selected by
When input = $A$, we can get all minterms having $A$, And when input = $A'$ we can get all minterms having $A'$, but how can we get both at a time as only $1$ MUX and $1$ inverter is available.

Means How can we implement $f(a,b,c) = \sum(0,7)$


implement f(a,b,c)=∑(0,7) , n=3 varriable so 2n-1 to 1 line i.e 4*1 MUX  is ok

here B and C are select line 

I0 connect to A' , I1 to 0 , I2 to 0 , I3 to A

so output of this is A'B'C' + ABC =∑(0,7)

That was a doubt long ago. I know it now. thanks btw
With two variables A and B, what kind of output combination i can think of ?
Either it is zero, 1, C or $\overline{C}$
That means if we use A,B as select lines then i can produce any combination of output.

A  B  C | F
0  0  0 | 1
0  0  1 | 0
0  1  0 | 0
0  1  1 | 1
1  0  0 | 1
1  0  1 | 1
1  1  0 | 0
1  1  1 | 1
For this function the following is the correct schematic.

Note that by changing the connections on the data inputs we could implement any function of A, B and C.
what if inverter is also not given?

then you have to use 1 more $2\times1$ mux that will act as Not gate.

At A=0, this gives 1.

And at A=1, this gives 0.

How to calculate F?
+11 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.
answered by Boss (42.6k points)
can you post a diagram to show implementing all min terms using inverter / NOT gate

you can think this way ...hope this gonna be helpful to you

So This means we can use only one 2^n to 1 MUX to implement any n variables boolean function.
Is it correct?

I want to ask that in what case option (a) can be correct?
@geet if inverter is not provided then option A is correct
+7 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

answered by Veteran (92k points)
is this only true given, 0 and 1 are also available as inputs? along with inverter, to implement all possible min terms?!
what about the terms when x is false..we wont get all the min terms of x complement..??
yes I think it will be true for all cases
@ sretha, without even NOT gate we will need 2^n to 1 MUX right??

how 2n-1?

+7 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 2^n *1 MUX.

But now the actual question come that is: can I implement a 3 variable function with 4*1 MUX or Can I implement a "n+1" variable function with 2^n * 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 example

I have explained in above page in a very easy way. In the same way, I can implement more than "n" variable function with 2^n * 1 MUX.

So what I need to do is, for implementing 3 variable functions with 2^2 * 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 = 2^(n-1) * 1

answered by Boss (24.9k points)
edited by
thank you..the question was easy but its a bit tricky to collect..ur explanation has very well explained me the concept
@akash.dinkar12 , ya buddy I have doubt

As it is saying implement any Boolean functions of n variables.

1. As my knowledge there will total 2^2^n function for n variables .

2. How we calculate F value ?

3.And plz explain this "Any boolean functions of n variables ".
–2 votes
Simple logic can not get A' and B' (or any 2 variables ) from single not use 2^(n-2)line to 1 mux
answered by (13 points)

Related questions

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

38,112 questions
45,620 answers
49,297 users