First, you have to define "multiplexer". For generality, let's assume a basic 2-way multiplexer that has 2 data inputs, a select input and a data output. But when working with SSI/MSI TTL or CMOS, you can get anything up to a 16:1 multiplexer as a building block.

There's definitely a maximum number of muxes required for any N-input function: You simply construct a 2^N-way mux that has N select inputs, and you tie each of the 2^N data inputs high or low as required. This requires 2^N-1 + 2^N-2 + ... + 2⁰ = 2^N 1 muxes.

\begin{array}{cc} N & muxes \\ 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ ... & ... \\ N & 2^N - 1 \end{array}

However, the minimum number of muxes for any arbitrary function of N variables very much depends on the function. There are some functions that are surprisingly efficiently implemented with 2-input muxes, especially if you allow one mux to feed the select input of another. All of the early Actel (now Microsemi) FPGA families used muxes as their basic logic element, rather than the now-ubiquitous LUT (look-up table).

First, you have to define "multiplexer". For generality, let's assume a basic 2-way multiplexer that has 2 data inputs, a select input and a data output. But when working with SSI/MSI TTL or CMOS, you can get anything up to a 16:1 multiplexer as a building block.

There's definitely a maximum number of muxes required for any N-input function: You simply construct a 2^N-way mux that has N select inputs, and you tie each of the 2^N data inputs high or low as required. This requires 2^N-1 + 2^N-2 + ... + 2⁰ = 2^N 1 muxes.

\begin{array}{cc} N & muxes \\ 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ ... & ... \\ N & 2^N - 1 \end{array}

However, the minimum number of muxes for any arbitrary function of N variables very much depends on the function. There are some functions that are surprisingly efficiently implemented with 2-input muxes, especially if you allow one mux to feed the select input of another. All of the early Actel (now Microsemi) FPGA families used muxes as their basic logic element, rather than the now-ubiquitous LUT (look-up table).

For example, a 2-input AND or 2-input OR just requires one mux, so an N-way AND or N-way OR can be constructed from just N 1 muxes. A 2-input XOR or XNOR requires just two muxes, so an N-way XOR tree (parity generator) requires just 2(N 1) muxes.

First, you have to define "multiplexer". For generality, let's assume a basic 2-way multiplexer that has 2 data inputs, a select input and a data output. But when working with SSI/MSI TTL or CMOS, you can get anything up to a 16:1 multiplixer as a building block.

There's definitely a maximum number of muxes required for any N-input function: You simply construct a 2^N-way mux that has N select inputs, and you tie each of the 2^N data inputs high or low as required. This requires 2^N-1 + 2^N-2 + ... + 2⁰ = 2^N 1 muxes.

\begin{array}{cc} N & muxes \\ 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ ... & ... \\ N & 2^N - 1 \end{array}

However, the minimum number of muxes for any arbitrary function of N variables very much depends on the function. There are some functions that are surprisingly efficiently implemented with 2-input muxes, especially if you allow one mux to feed the select input of another. All of the early Actel (now Microsemi) FPGA families used muxes as their basic logic element, rather than the now-ubiquitous LUT (look-up table).

First, you have to define "multiplexer". For generality, let's assume a basic 2-way multiplexer that has 2 data inputs, a select input and a data output. But when working with SSI/MSI TTL or CMOS, you can get anything up to a 16:1 multiplexer as a building block.

There's definitely a maximum number of muxes required for any N-input function: You simply construct a 2^N-way mux that has N select inputs, and you tie each of the 2^N data inputs high or low as required. This requires 2^N-1 + 2^N-2 + ... + 2⁰ = 2^N 1 muxes.

\begin{array}{cc} N & muxes \\ 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ ... & ... \\ N & 2^N - 1 \end{array}

However, the minimum number of muxes for any arbitrary function of N variables very much depends on the function. There are some functions that are surprisingly efficiently implemented with 2-input muxes, especially if you allow one mux to feed the select input of another. All of the early Actel (now Microsemi) FPGA families used muxes as their basic logic element, rather than the now-ubiquitous LUT (look-up table).