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

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.6k points)
edited by | 4.5k views
+1
Plz explain
–25
Read any book for digital logic or search this question on google. Can't be explained here
0
For an intuition, think about the way we create a Variable Entrant K-Map.
+1

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
+2
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)$
+3

@mcjoshi

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)

+3
That was a doubt long ago. I know it now. thanks btw
+7
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.
0
what if inverter is also not given?
+3

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.

0
How to calculate F?
+12 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.9k points)
0
can you post a diagram to show implementing all min terms using inverter / NOT gate
+8

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

0
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?
0
@geet if inverter is not provided then option A is correct
+8 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 (26.7k points)
edited by
+1
thank you..the question was easy but its a bit tricky to collect..ur explanation has very well explained me the concept
0
@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 ".
0
maximum how many variable boolean function can be implemented by 8:1 multiplexer ?
+1

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' etc..in 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.

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

how 2n-1?

–2 votes
Simple logic is...you can not get A' and B' (or any 2 variables ) from single not gate...................to use 2^(n-2)line to 1 mux
answered by (13 points)
Answer:

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

40,871 questions
47,531 answers
146,031 comments
62,297 users