The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 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 (52.1k points)
edited by | 6.2k 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.  



i think these three questions are very much related to this question (especially the last one).

6 Answers

+30 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?
if no of inverter =2 then 2^(n-2) to 1 mux sufficient

if no of inverter =3 then 2^(n-3) to 1 mux sufficient.

and so on......correct me if i am wrong

@talha hashim

You will need additional AND OR gates if no.of inverters > 1


 why is that so, can you explain?


 can u show that with an example?


  If only multiplexer is given and not inverter, then answer would be 2^n to 1.... right?

+15 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 (41k 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
0 easy to understand
+15 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

answered by Boss (41k 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 ".
maximum how many variable boolean function can be implemented by 8:1 multiplexer ?

Dharmendra Lodhi 

I think, u wanted to know this, like if we have 8*1 MUX then we can implement any 3 variable boolean function But if we have to implement any 4 variable function with 8*1 MUX, as we have seen we can implement it as well provided that we should have given 1 inverter as well otherwise we can not implement it.

Similarly, u want to know that if we have given 8*1 MUX then can we implement any 5 variable function or not?? 

If i m getting ur question then answer will be in this way, with the help of 8*1 MUX, we can not implement 5 variable but we can implement any four variable function with one 1 inverter but why?? because in order to implement any 4 variable function, we will give 3 selection lines(might be A, B, C) and D is only input remaining it might be D or D' we can do it with one inverter(ie; they have given us 1 inverter in question as well) but if we want to attain the same functionality of 5 variable boolean function implemented with 8*1 MUX then we can not do it with one inverter then we can not implement it because(3 selection lines will be there might be A, B, C )and there are other remaining two variables D, E which will be given as input which will be various combinations to input only like CD or CD' order to implement CD , we require 1 AND gate and output of that AND gate will be input to 8*1 MUX.

So the summary is if we have only 1 inverter and we have to implement any 4 variable boolean function then we can do it with the help of 2*1 MUX but we can not implement 5 variables boolean function with only 1 inverter and yes we can implement it if we have lot of AND gates too.



If we were given 2 multiplexers,1 not and an and gate then we could have implemented n variable function with 2^(n-2)line to 1 mux .right??

+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 (112k 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?

0 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
answered by (13 points)
–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
49,811 questions
54,540 answers
75,603 users