Suppose only one multiplexer and one inverter are allowed to be used to…

Answer: a 2n-1-to-1 multiplexer (i.e., 2^{n-1} data inputs)

Construction (sufficiency):

• Choose n-1 of the variables as the multiplexer select inputs.

• There are 2^{n-1} possible assignments to these select inputs; for each assignment, the corresponding data input must implement the function of the remaining variable.

• As a function of a single variable, that value can only be one of: constant 0, constant 1, the variable itself, or the variable negated.

• With one inverter available we can produce the negation; constants and the variable itself are directly available. Therefore each data input can be set to the required value, so a 2^{n-1}-to-1 multiplexer plus one inverter can realize any n-variable Boolean function.

Minimality (necessity):

• If the multiplexer had fewer than 2^{n-1} data inputs, then by the pigeonhole principle at least two different assignments to the n-1 selector variables would share the same data input.

• Those two selector assignments could require different single-variable functions of the remaining variable (for example one requires the remaining variable, the other its negation), so a shared data input would make it impossible to represent all possible n-variable functions.

• Hence at least 2^{n-1} distinct data inputs are necessary.

Therefore the minimum multiplexer size required is 2^{n-1}-to-1.