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

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.

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.

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.

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.