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?

Question

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.

Answer 1

The less efficient (and maybe more obvious) way is to connect fixed logic levels to each input of the multiplexer. You need a 2^N input multiplexer for N inputs. So, an 16-input mux for any function of 4 bits.

If, instead, you connect the respective inputs to either one of the inputs (that doesn't go to the multiplexer select input) or its complement, as required for the function, then you can halve the multiplexer size. So an 8-input mux (plus an inverter) for any function of 4 bits.

Answer 2

Here's a non-specific example: -

enter image description here

Oops it's basically what Spehro said so honours go to him!!

OUT(1) = 000 + 101 + 010 + 111

• aste123: 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?
• Andy aka: You just need to "re-wire" A1 and the inverter (to the inputs) to suit the function you want to achieve.