Activity 1.5.1.
Use Logisim to build the circuit in Figure 1.5.3, and verify that it has the truth table in Table 1.5.2.
Section 1.5 Standard forms: minterms and maxterms
In this section we will introduce two standard forms for Boolean functions: the minterm and the maxterm. Every boolean function can be represented as a sum of minterms or as a product of maxterms. Each of these representations leads directly to a circuit.
Consider the expression
\begin{equation*}
\bar{x} y z + x \bar{y} z\text{.}
\end{equation*}
If we list out the barred and unbarred versions of all the variables that appear in the expression, we get the following:
\begin{equation*}
x, \bar{x}, y, \bar{y}, z, \bar{z}\text{.}
\end{equation*}
These occur in complementary pairs: for any choice of logical values of \(x\text{,}\) \(y\text{,}\) \(z\text{,}\) exactly one of the members of each pair is 1 and the other is 0. Table 1.5.1 summarizes the situation.
| minterm | \(x\) | \(y\) | \(z\) |
|---|---|---|---|
| \(m_0 = \bar{x} \cdot \bar{y} \cdot \bar{z}\) | 0 | 0 | 0 |
| \(m_1 = \bar{x} \cdot \bar{y} \cdot z\) | 0 | 0 | 1 |
| \(m_2 = \bar{x} \cdot y \cdot \bar{z}\) | 0 | 1 | 0 |
| \(m_3 = \bar{x} \cdot y \cdot z\) | 0 | 1 | 1 |
| \(m_4 = x \cdot \bar{y} \cdot \bar{z}\) | 1 | 0 | 0 |
| \(m_5 = x \cdot \bar{y} \cdot z\) | 1 | 0 | 1 |
| \(m_6 = x \cdot y \cdot \bar{z}\) | 1 | 1 | 0 |
| \(m_7 = x \cdot y \cdot z\) | 1 | 1 | 1 |
Each of the rows in the table is called a minterm. The name comes from the fact that each row is a product of literals (variables or their negations), and the product of literals is called a term. The term is called a minterm because it is 1 for the combination of inputs that is listed in the row, and 0 for all other combinations. The minterm is called canonical because it is the simplest possible expression for the function.
Subsection 1.5.1 Minterm canonical form
Look again at Table 1.5.1. Notice that each minterm is labeled by the integer representation of the combination of inputs that makes it 1. For example, \(m_5\) is 1 when \(x = 1\text{,}\) \(y = 0\text{,}\) and \(z = 1\text{,}\) and this combination of inputs, that is, the binary number \(101\text{,}\) is the integer 5. The minterm \(m_7\) is 1 when \(x = 1\text{,}\) \(y = 1\text{,}\) and \(z = 1\text{,}\) and this combination of inputs, that is, the binary number \(111\text{,}\) is the integer 7.
Given any truth table for a 3-variable function, we can write down the minterm canonical form for the function by adding the minterms that are 1 in the truth table. For example, Table 1.5.2 corresponds to the minterm canonical form \(m_1 + m_3 + m_5\text{,}\) because minterms \(m_1\text{,}\) \(m_3\text{,}\) and \(m_5\) are the only ones that are 1 in the truth table.
| \(x\) | \(y\) | \(z\) | \(f\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
To represent the minterm form as a circuit, we remember that multiplication is AND and addition is OR. So the circuit for \(m_1 + m_3 + m_5\) is as pictured in Figure 1.5.3.
Activity 1.5.2.
Write down the minterm canonical form for the function \(g\) whose truth table is given in Table 1.5.4.
| \(x\) | \(y\) | \(z\) | \(g\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Activity 1.5.3.
Use Logisim to build the circuit for the function \(g\) whose minterm canonical form you wrote down in the previous activity, and verify that it has the truth table in Table 1.5.4.
When there are more variables, just put them in an order and write down all the minterms. There will be \(2^n\) minterms for a function of \(n\) variables. For example, for a function of 4 variables, there will be 16 minterms.
Activity 1.5.4.
Write down the table of all 16 minterms for variables \(w\text{,}\) \(x\text{,}\) \(y\text{,}\) and \(z\) (in that order).
Activity 1.5.5.
Write down the minterm canonical form for the function \(h\) whose truth table is given in Table 1.5.5.
| \(w\) | \(x\) | \(y\) | \(z\) | \(h\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Activity 1.5.6.
Use Logisim to build the circuit for the function \(h\) whose minterm canonical form you wrote down in the previous activity, and verify that it has the truth table in Table 1.5.5.
Expressions that are sums of minterms are called sums of products, or SOP expressions. The circuit corresponding to an SOP expression is called a sum of products circuit.
In the next subsection, we will introduce the dual of the minterm canonical form, called the maxterm canonical form. It is useful to know both forms, because sometimes one is easier to work with than the other. One may be easier to build as a circuit than the other, involving fewer gates.
Subsection 1.5.2 The maxterm canonical form
The maxterm canonical form is the dual of the minterm canonical form. The dual of a function is obtained by interchanging AND and OR, and 0 and 1. So the dual of the minterm \(m_1\) is the maxterm \(M_1\text{,}\) which is \(x + y + \bar{z}\text{.}\) The dual of the minterm canonical form \(m_1 + m_3 + m_5\) is the maxterm canonical form \(M_1 \cdot M_3 \cdot M_5\text{.}\)
The maxterm \(M_1\) is 0 when \(x = 0\text{,}\) \(y = 0\text{,}\) and \(z = 1\text{,}\) and this combination of inputs, that is, the binary number \(001\text{,}\) is the integer 1. The maxterm \(M_3\) is 0 when \(x = 0\text{,}\) \(y = 1\text{,}\) and \(z = 1\text{,}\) and this combination of inputs, that is, the binary number \(011\text{,}\) is the integer 3. The maxterm \(M_5\) is 1 when \(x = 1\text{,}\) \(y = 0\text{,}\) and \(z = 1\text{,}\) and this combination of inputs, that is, the binary number \(101\text{,}\) is the integer 5. Table 1.5.7 summarizes the situation.
Warning 1.5.6.
Notice that the maxterms are labeled by the integers that make them 0, not 1. This is the opposite of the situation with minterms.
| maxterm | \(x\) | \(y\) | \(z\) |
|---|---|---|---|
| \(M_0 = x + y + z\) | 0 | 0 | 0 |
| \(M_1 = x + y + \bar{z}\) | 0 | 0 | 1 |
| \(M_2 = x + \bar{y} + z\) | 0 | 1 | 0 |
| \(M_3 = x + \bar{y} + \bar{z}\) | 0 | 1 | 1 |
| \(M_4 = \bar{x} + y + z\) | 1 | 0 | 0 |
| \(M_5 = \bar{x} + y + \bar{z}\) | 1 | 0 | 1 |
| \(M_6 = \bar{x} + \bar{y} + z\) | 1 | 1 | 0 |
| \(M_7 = \bar{x} + \bar{y} + \bar{z}\) | 1 | 1 | 1 |
Let us reconsider the function in Table 1.5.2. The maxterm canonical form for this function is \(M_0 \cdot M_2
\cdot M_4 \cdot M_6 \cdot M_7\text{,}\) because maxterms \(M_0\text{,}\) \(M_2\text{,}\) \(M_4\text{,}\) \(M_6\text{,}\) and \(M_7\) are the only ones that are 0 in the truth table.
Activity 1.5.7.
Write down the maxterm canonical form for the function \(g\) whose truth table is given in Table 1.5.4.
Activity 1.5.8.
Use Logisim to build the circuit for the function \(g\) whose maxterm canonical form you wrote down in the previous activity, and verify that it has the truth table in Table 1.5.4.
When there are more variables, just put them in an order and write down all the maxterms. There will be \(2^n\) maxterms for a function of \(n\) variables. For example, for a function of 4 variables, there will be 16 maxterms.
Activity 1.5.9.
Write down the table of all 16 maxterms for variables \(w\text{,}\) \(x\text{,}\) \(y\text{,}\) and \(z\) (in that order).
Activity 1.5.10.
Write down the maxterm canonical form for the function \(h\) whose truth table is given in Table 1.5.5.
Activity 1.5.11.
Use Logisim to build the circuit for the function \(h\) whose maxterm canonical form you wrote down in the previous activity, and verify that it has the truth table in Table 1.5.5.
Expressions that are products of maxterms are called products of sums, or POS expressions. The circuit corresponding to a POS expression is called a product of sums circuit.
The minterm canonical form and the maxterm canonical form are called canonical because they are the simplest possible expressions for the function. The minterm canonical form is the simplest sum of products expression, and the maxterm canonical form is the simplest product of sums expression.
Activity 1.5.12.
When is the minterm canonical form simpler than the maxterm canonical form, and vice versa?
