# Can we derive all boolean functions using a 2x1 Multiplexer?

It is possible to implement all boolean functions using a 4x1, 8x1 or a 16x1 Multiplexer.

But is it possible to implement all boolean functions with a 2x1 Multiplexer? I think it is not, because how would it be possible to implement AND, OR, XOR, etc. I think only NOR can be implemented using a 2x1 Multiplexer.

Am I missing any point here?

• With a single 2->1 mux, or using only 2->1 muxes? – Wouter van Ooijen Apr 17 '18 at 15:36
• I see no problem to implement invert, and, or with a single 2->1 mux. – Wouter van Ooijen Apr 17 '18 at 15:37
• All boolean functions with up to how many inputs? – The Photon Apr 17 '18 at 15:44

Starting from a standard 2x1 mux: simulate this circuit – Schematic created using CircuitLab

You can write its output $O$ as a function of $A, B, C$: $$O = A\cdot\overline{C} + B\cdot C$$

Starting from here, you have a lot of possibilities. $$A = 1, B = 0 \implies O = \overline{C}\\ B = 1 \implies O = A\cdot\overline{C} + 1\cdot C = A + C\\ A = 0 \implies O = B\cdot C$$

So you already have not, or, and. I think you can work the rest from here.

Not just with only a 2:1 multiplexer, you'll need to negate a few inputs to get some of the functions like xor.

The can do and and or without gates

Here is one for a xor function, but it requires a not gate.

Remember that a mux is a collection of gates, a useful one. It's important for you to know how to scale these down becasue you can simplify logic on FPGA's and ASICS and eliminate gates by coding correctly and understanding what the end design goal is. On an ASIC, generally a fewer number of gates is better. On an FPGA using fewer resources is better and usually an FPGA consists of a simple logic chain (like a mux combined with some other logic) and a memory element to form a cell or logic block.

Shown below is a truth table for a 2:1 mux, which can be changed to form many different functions: A mux has the following boolean expression:

$F = SA+\overline{S}B$

Where

• F is the output,
• S is the switch signal
• A is one of the inputs
• B is the other input

So your question boils down to this:

Can we make $F = SA+\overline{S}B_m$ into

• $F = AB_a$
• Yes, the first term in the mux expression, ground $B_m$ and replace $S$ with $B_a$.
• $F = \overline{AB}$
• No, in the mux expression, there is only one inverter for one of the input variables. With another inverted input we can use De Morgans laws, or we just do the same as $F = AB$ and stick the inverter on the output.

I can continue with more gates. But since I've already encountered a "no", it doesn't matter.

For clarity, no, you can't derive all boolean functions using a 2:1 multiplexer.