From a truth table to a MUX and Shannon expansion

Derive the selection rule

To output a when sel is 0 and b when sel is 1, multiply each input by its selection condition, then OR the terms:

Substituting $s=0$ leaves only a; substituting $s=1$ leaves only b. If a and b are equal, changing sel does not change the output. Tests that expose selection errors must therefore include unequal data inputs.

The blue path marks the selected input. Make a and b different, then change sel. With equal data values, even an incorrectly wired selector is difficult to distinguish from the output alone.

A MUX provides a general decomposition of logic functions

For any Boolean function F, call the cofactors obtained by fixing s to 0 and 1 $F_0$ and $F_1$:

This is Shannon expansion. s ? F1 : F0 splits any function into two parts. For $F=a\oplus b$ with a as the selector, $F_0=b$ and $F_1=\overline b$, so a MUX^{iMultiplexer A combinational circuit that connects one of several inputs to the output according to a select signal. Specify how select bits map to input numbers.} and inversion^{iInversion The NOT operation, which changes 0 to 1 and 1 to 0. A bar over an expression applies NOT to the entire expression beneath it. Learn more} implement XOR.

Four-to-one selection and priority

Selecting one of four inputs with two select bits can use two levels of 2-to-1 MUXes. In contrast, if (req0) ... else if (req1) ... prioritizes the earlier request when multiple requests are 1. Address selection and priority selection are distinct problems.

assign y = sel[1] ? (sel[0] ? d3 : d2)
                 : (sel[0] ? d1 : d0);

In an ideal balanced tree, $2^m$ inputs yield m selection stages. Physical delay depends on input arrival times, load and wiring as well as stage count. Function decomposition creates implementation candidates; it does not prove optimal delay.