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?



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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.