Combinational Blocks — worked example

Digital Logic 101 · Combinational Blocks · Example

Implement F(A,B,C) = Σm(0, 2, 5, 7) with a 4:1 MUX

A 2^k:1 MUX implements any k-input Boolean function when k − 1 of the function's variables drive the select lines and the data inputs are tied to the remaining variable, its complement, 0, or 1. With a 4:1 MUX (two select lines) and three variables A, B, C, we use A and B as selects and let C — or something built from C — drive each of D₀..D₃.

Step 1 — Truth table

Write F across all 8 rows of (A,B,C):

A	B	C	F
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Figure 1. Truth table for F(A,B,C) = Σm(0,2,5,7).

Step 2 — Residue table

Group rows by (A,B). Each (A,B) pair gives two rows of F — one for C=0 and one for C=1. The two values together pin down which of {0, 1, C, C'} that data input must be.

AB    F at C=0    F at C=1    Tie D_AB to
00       1            0            C'
01       1            0            C'
10       0            1            C
11       0            1            C

Read the residue rule from the two F-values per (A,B):

F=0 in both rows → tie D to 0.
F=1 in both rows → tie D to 1.
F follows C (00 / 11 → 0 / 1) → tie D to C.
F is the inverse of C (00 / 11 → 1 / 0) → tie D to C′.

Step 3 — Map AB to D-inputs

With A as the MSB of the select (S₁) and B as the LSB (S₀), AB=00 picks D₀, AB=01 picks D₁, AB=10 picks D₂, AB=11 picks D₃.

D₀ = C′ — because at AB=00 F is $C\,'$ .
D₁ = C′ — because at AB=01 F is $C\,'$ .
D₂ = C — because at AB=10 F follows C.
D₃ = C — because at AB=11 F follows C.

Step 4 — Verify algebraically

Expanding the MUX equation:

Y = D_0 \overline{A}\overline{B} + D_1 \overline{A}B + D_2 A\overline{B} + D_3 AB

Substitute D₀=D₁=C′ and D₂=D₃=C:

Y = \overline{C}(\overline{A}\overline{B} + \overline{A}B) + C(A\overline{B} + AB)

\quad = \overline{C}\,\overline{A} + C\,A

Multiply out and collect minterms:

Y = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}B\overline{C} + A\overline{B}C + ABC

That is exactly Σm(0, 2, 5, 7). ✓

Resulting circuit

Figure 2. 4:1 MUX wired to implement F(A,B,C) = Σm(0,2,5,7). Selects S₁=A, S₀=B; data D₀=D₁=C′ and D₂=D₃=C. The 8-row truth table collapses into one chip plus an inverter.

A 4:1 MUX with k+1 = 3 inputs handles any 3-variable Boolean function: drive 2 selects with two variables, and tie each of 4 data inputs to {0, 1, C, C'} according to the residue table. More generally, a 2^k:1 MUX implements every k+1-input function this way.