Lec 02-04-2025: Creating a MUX from a Boolean Function

Implementing a Boolean Function with a MUX

To see how this works, we’ll implement $f(x, y, z) = x'y + y'z'$ using a $4 \times 1$ MUX with $yz$ as the select lines.

How a $4 \times 1$ MUX Works

A $4 \times 1$ MUX has four inputs and two select lines — we’ll label our inputs $I_0, I_1, I_2, I_3$. The select lines determine which input gets routed to the output — when they read $yz = 00$, $I_0$ comes through; when $yz = 10$, $I_2$ comes through; and so on.

Since $y$ and $z$ are the select lines, the task essentially becomes: what should each of $I_0, I_1, I_2, I_3$ be so that whenever the MUX selects it, the output matches $f(x, y, z)$?

Identifying the Minterms

Start by drawing the truth table for $xyz$, then identify which entries make $f = 1$. These are the minterms: the cases the MUX needs to produce a $1$ for.

Entry	$x$	$y$	$z$
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Since $f$ is a sum (OR) of product terms, then $f = 1$ whenever at least one product term equals 1.

Since each term directly encodes the variable values that make it 1, we can just read off the variable values that make each term 1:

$$x'y = 1 \quad \implies \quad x'y = 1 \cdot 1 \quad \implies \quad x = 0,\; y = 1$$ $$y'z' = 1 \quad \implies \quad y'z' = 1 \cdot 1 \quad \implies \quad y = 0,\; z = 0$$

Note that variables that don’t appear in a term are unconstrained — $x'y$ says nothing about $z$, so $z$ can be either $0$ or $1$. Similarly, $y'z'$ says nothing about $x$.

So for $x'y$, then we can just look for entries where $x = 0$ and $y = 1$, likewise for $y'z'$ we can just look for the entries where $y = 0$ and $z = 0$, and those entries will be the minterms.

Entry	$x$	$y$	$z$
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

Assigning the MUX Inputs

Every entry in the truth table belongs to exactly one input of $I_0, \ldots, I_3$. Since $y$ and $z$ are the select lines, they determine which input gets routed through — so within any of $I_0, \ldots, I_3$, the only remaining variable is $x$.

We notice from the truth table that there exist four pairs of entries that share the same $yz$ value but differ in $x$ — this means each of $I_0, \dots, I_3$ can only be a constant ($0$ or $1$) or a function of $x$ alone. Entries $0$ and $4$ both have $yz = 00$, so they both belong to $I_0$; entries $2$ and $6$ both have $yz = 10$, so they both belong to $I_2$; and so on. We’ll line up these entries in a column in the table below:

A convenient way to organize this is a grid where the columns are $I_0 \ldots I_3$ and the entries split by whether $x = 0$ or $x = 1$. Each cell holds the corresponding truth table entry number, and the minterms from above are circled:

	$I_0$	$I_1$	$I_2$	$I_3$
$x'$	0	1	2	3
$x$	4	5	6	7

Reading off $I_0, \dots, I_3$ from each column:

• Both cells circled: $f = 1$ regardless of $x$, so $I_0 = 1$.
• No cells circled: $f = 0$ regardless of $x$, so $I_1 = 0$.
• Only the $x'$ cell circled: $f = 1$ when $x = 0$ and $0$ when $x = 1$, so $I_2 = x'$. The same logic applies to $I_3$, so $I_3 = x'$ as well.

To generalize this: each column tells you what $I_k$ must be.

• None of the rows circled: $f = 0$ for both values, so $I_k = 0$.
• Otherwise, we take the union of all the circled rows. In our example, where we have a case that has all rows circled, we get $x' + x = 1$ (by the complementarity law), so for this reason we can just say $I_k = 1$ when all rows are circled.

$$I_0 = 1 \qquad I_1 = 0 \qquad I_2 = x' \qquad I_3 = x'$$

Reading the Output Expression

Internally, a MUX AND-gates each input with the select-line combination that activates it, then OR-s all of those together. For $yz = 00$, the activating combination is $y'z'$, so $I_0$ contributes $I_0 \cdot y'z'$; for $yz = 01$ it’s $y'z$, contributing $I_1 \cdot y'z$; and so on. Summing all four gives the general output expression:

$$I_0 y'z' + I_1 y'z + I_2 yz' + I_3 yz$$

Substituting the values found above:

$$(1)y'z' + \cancel{(0)y'z} + x'yz' + x'yz = \boxed{y'z' + x'yz' + x'yz}$$

As a quick sanity check, this simplifies back to $f$: $\; y'z' + x'y(z' + z) = y'z' + x'y = f \;\color{green}{\checkmark}$

The Completed MUX

Example 1

Using a MUX of size $2^2 \times 1$, implement $f(x,y,z) = x'y + y'z'$ using as control lines: $xy$

Based on your solution, provide the completed MUX and give the expression of the MUX’s output.

Solution

	$x$	$y$	$z$
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

	$I_0$	$I_1$	$I_2$	$I_3$
$z'$	0	2	4	6
$z$	1	3	5	7

Inputs:

$$I_0 = z' \qquad I_1 = 1 \qquad I_2 = z' \qquad I_3 = 0$$

Output Expression:

$$\begin{align*} & I_0 x'y' + I_1 x'y + I_2 xy' + I_3 xy \\ =\; & z'x'y' + (1)x'y + z'xy' + \cancel{(0)xy} \\ =\; & x'y'z' + x'y + xy'z' \end{align*}$$

The MUX

Example 2: Using a $2 \times 1$ MUX

Implement $f(x, y, z) = x'y + y'z'$ using a $2 \times 1$ MUX with $y$ as the select line.

Draw the completed MUX and give the expression of the MUX’s output.

Solution

	$x$	$y$	$z$
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

	$I_0$	$I_1$
$x'z'$	0	2
$x'z$	1	3
$xz'$	4	6
$xz$	5	7

Inputs:

$$I_0 = x'z' + xz' = z'(x' + x) = z'(1) = z'$$ $$I_1 = x'z' + x'z = x'(z' + z) = x'(1) = x'$$

Output Expression:

$$\begin{align*} & I_0 y' + I_1 y \\ =\; & z'y' + x'y \end{align*}$$

The MUX