Multiplexer implementation

A multiplexer looks up an answer: the select lines say which row, and the data inputs hold the answers. So a MUX can build any function, with no gates at all.

All variables on the selects. For an n-variable function, use a 2ⁿ:1 MUX. Put the variables on the selects (MSB variable on the MSB select), and tie each data input Iᵢ to F's value on row i. The data inputs, read from I0 up, are the truth table's output column.

One variable fewer. Use a 2ⁿ⁻¹:1 MUX. Put n − 1 variables on the selects. The remaining variable, the leftover, goes to the data inputs. Each data input now covers two truth-table rows that differ only in the leftover variable x. Read F on those two rows (x = 0 first):

• 0 0 → 0
• 1 1 → 1
• 0 1 → x
• 1 0 → x', the complement of x

That always works, because a function of one variable can only be one of those four. Each data input is a shannon expansion cofactor.

Recipe:

1. Write down which variable goes on S1 and which on S0.
2. For each Iᵢ, translate the code i into your variables and find its two rows.
3. Match the pair, as above.
4. Verify by expanding S₁S₀I₀+S₁S₀I₁+S₁S₀I₂+S₁S₀I₃.