# What is the minimum size of multiplexer needed to implement any boolean function of n variables if we are given a multiplexer and an inverter to use?

The following is the solution given.

We can use n-1 selection lines , and using 0,1 and nth variable and its compliment to realize the function So ans is 2^(n-1):1

I'm unable to understand how it exactly works. If we have a function of say 3 variables. We can have 8 input lines for the multiplexer. If we take 2 select lines as per the solution, we can choose only 4 of the inputs.

I assume that using the inverter, we are somehow connecting the third select line which will double the possibilities to 8. But I'm unable to get a clear idea of how the connection is made.

Any help is highly appreciated.

• Suppose the function is Summation minterms(0,1,2,3,4,5,6,7). And I want to choose a1'a2a3. The a2a3 choose the last one labelled 11 but with it we have a1 connected and not a1'. So how do I implement the function I just described? – aste123 Jan 14 '16 at 19:03