GATE CS 2007 Q34 — Combinational Circuits

To implement any Boolean function of $n$ variables using a single multiplexer and one inverter, we can use the Shannon's expansion theorem or variable-entrance mapping.

Let the $n$ variables of the Boolean function be $x_1, x_2, \dots, x_n$.

1. We can connect $n-1$ of these variables (say, $x_1, x_2, \dots, x_{n-1}$) to the select lines of the multiplexer.
2. This requires a multiplexer with $n-1$ select lines, which corresponds to $2^{n-1}$ input lines.
3. The remaining single variable, $x_n$, along with its complement $\bar{x}_n$ (obtained using the single allowed inverter), and the constants $0$ and $1$, are connected to the data input lines of the multiplexer as needed.

Thus, any arbitrary $n$-variable Boolean function can be implemented using a $2^{n-1}$ to $1$ line multiplexer and one inverter.

Therefore, the minimum size of the multiplexer needed is $2^{n-1}$ line to $1$ line.