Implementing 3 variable boolean function using mux 4 to 1 and inverter

Question

I'm trying to understand if it's possible to Implement boolean function with 3 inputs using only mux 4 to 1 and inverter. As far as I understand I can put in the selectors the first 2 variables to select between the 4 options. then I have another variable which I can connect to the 4 options (00,01,10,11) but I can't solve it to make sure it will suffice any 3 variables function.

I would like to know how to approach this kind of questions, how to "prove" such things?

Thanks.

Answer 1

It is possible to make any boolean function f(a,b,c) using a 4:1 mux and an inverter

With the inverter make ~c

Connect a and b to the mux address lines.

Connect each mux data input to the one of 0,1,c,or ~c as appropriate.

The mux output has your function result.

Answer 2

It is a nice exercise to understand different ways to represent a logical function.

In short: you can always implement a logical function of \$N\$ variables with a \2ドル^{N-1}\$:1 multiplexer and some amount of inverters by using one of the variables at data inputs of the multiplexer and others - at control inputs.

Here's an explanation. Let's consider a logical function of 3 variables \$y(x_0, x_1, x_2)\$. When you look at its truth table, you can easily divide it into two parts: one where \$x_0\$ equals "0" and one where \$x_0\$ equals "1". Then we need to look at pairs of \$y\$ values with equal \$(x_1, x_2)\$ argument values. For a pair of \$y\$ values there are only four possible combinations:

"0" and "0" - which means that for a certain \$(x_1, x_2)\$ value, \$y\$ always equals "0", i.e. \$y\$ doesn't depend on \$x_0\$;

"1" and "1" - this is similar to the first case, \$y\$ doesn't depend on \$x_0\$, but always equals "1";

"0" and "1" - which means that for a certain \$(x_1, x_2)\$ value \$y\$ = "0" when \$x_0\$ = "0", and \$y\$ = "1" when \$x_0\$ = "1", i.e. \$y = x_0\$;

"1" and "0" - this is an inversion of the previous case, for a certain \$(x_1, x_2)\$ value \$y\$ = "1" when \$x_0\$ = "0", and \$y\$ = "0" when \$x_0\$ = "1", i.e. \$y = \bar x_0\$.

You can connect \$(x_1, x_2)\$ value to the 2-bit control input of the 4:1 mux. It will select a corresponding \$y\$ pair. To have a constant "0" or "1" (1-st and 4-th cases), you put a constant "GND" or "VCC" respectively at the corresponding data input. If \$y\$ in pair depends on \$x_0\$ (2-nd and 3-rd cases), you put \$x_0\$ or \$\bar x_0\$ at the corresponding data input.

Here is an example of a logical function (in the form of a truth table) and its implementation using a 4:1 mux.

Truth table Mux implementation

In this example:

for \$(x_1, x_2)=0\$: \$y(0,(0,0)) = y(1,(0,0)) = 0\$, hence GND at the 0-th data input,

for \$(x_1, x_2)=1\$: \$y(0,(0,1)) = 1, y(1,(0,1)) = 0\$, hence \$\bar x_0\$ at the 1-st data input,

for \$(x_1, x_2)=2\$: \$y(0,(0,1)) = 0, y(1,(0,1)) = 1\$, hence \$x_0\$ at the 2-nd data input,

for \$(x_1, x_2)=3\$: \$y(0,(0,1)) = y(1,(0,1)) = 1\$, hence VCC at the 3-rd data input.