##### 1

Show that Equation (5.2.1) and Equation (5.2.2) represent the same functionality. This shows that the sum of minterms and product of Maxterms are complementary.

SolutionSome terminology and definitions at this point will help our discussion. Consider two dictionary definitions of *literal* from *Merriam-Websters's Online Dictionary*[A.1.18]:

adhering to fact or to the ordinary construction of primary meaning of a term or expression : ACTUAL

of, relating to, or expressed in letters

In programming we use the first definition of literal. For example, in the following code sequence

the number “123”, the character “b”, and the string “Hello” are all literals. They are interpreted by the compiler exactly as written. On the other hand, “xyz”, “a”, and “greeting” are all names of variables. By the way, `*greeting` is a pointer variable that contains the address of the first characters in the text string, “Hello”.

In mathematics we use the second definition of literal. That is, in the algebraic expression \begin{equation*} 3x + 12 y - z \end{equation*} the letters \(x\text{,}\) \(y\text{,}\) and \(z\) are called literals. It is common to omit the “\(\cdot\)” operator to designate multiplication. Similarly, it is often dropped in Boolean algebra expressions when the AND operation is implied.

The meaning of *literal* in Boolean algebra is slightly more specific. It means the presence of a variable or its complement in an expression. For example, the expression
\begin{equation*}
x \cdot y + x' \cdot z + x' \cdot y' \cdot z'
\end{equation*}
contains seven literals. From the context of the discussion you should be able to tell which meaning of “literal” is intended and when the “\(\cdot\)” operator is omitted.

A Boolean expression is created from the numbers \(\binary{0}\) and \(\binary{1}\text{,}\) and literals. Literals can be combined using either the “\(\cdot\)” or the “\(+\)” operators, which are multiplicative and additive operations, respectively.

A *product term* is one in which all the literals are connected with AND operators. AND is multiplicative, hence the use of “product.” A product term that contains all of the variables in the problem, either in its complemented or uncomplemented form, is called a *minterm* or *standard product*. For example, if a problem involves three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) then \((x\cdot y\cdot z)\text{,}\) \((x' \cdot y \cdot z')\text{,}\) and \((x' \cdot y' \cdot z')\) are all minterms, but \((x\cdot y)\) is not.

One or more product terms connected with OR operators is a *sum of products* (*SoP*). OR is additive, hence the use of “sum.” An SoP in which each product term is a minterm is called a *sum of minterms* (*SoM*) or *canonical sum*. Since all the variables are present in each minterm, the canonical sum is unique for a given problem.

A function that defines the solution to a problem can be expressed as a sum of minterms (SoM) in which each of the minterms evaluates to \(1\text{.}\) When first defining a problem, starting with the SoM ensures that the full effect of each variable has been taken into account. This often does not lead to the best implementation. In Section 5.3 we will see some tools to simplify the expression, and hence, the implementation.

It is common to index the minterms according to the values of the variables that would cause that minterm to evaluate to \(1\text{.}\) For example, \(x' \cdot y' \cdot z' = 1\) when \(x = 0\text{,}\) \(y = 0\text{,}\) and \(z = 0\text{,}\) so this would be \(m_{0}\text{.}\) The minterm \(x' \cdot y \cdot z'\) evaluates to \(1\) when \(x = 0\text{,}\) \(y = 1\text{,}\) and \(z = 0\text{,}\) so is \(m_{2}\text{.}\) Table 5.2.1 lists all the minterms for a three-variable expression.

minterm | \(x\) | \(y\) | \(z\) |

\(m_{0} = x' \cdot y' \cdot z'\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{0}\) |

\(m_{1} = x' \cdot y' \cdot z\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{1}\) |

\(m_{2} = x' \cdot y \cdot z'\) | \(\binary{0}\) | \(\binary{1}\) | \(\binary{0}\) |

\(m_{3} = x' \cdot y \cdot z\) | \(\binary{0}\) | \(\binary{1}\) | \(\binary{1}\) |

\(m_{4} = x \cdot y' \cdot z'\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{0}\) |

\(m_{5} = x \cdot y' \cdot z\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{1}\) |

\(m_{6} = x \cdot y \cdot z'\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{0}\) |

\(m_{7} = x \cdot y \cdot z\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{1}\) |

A convenient notation for expressing a sum of minterms is to use the \(\sum\) symbol with a numerical list of the minterm indices. For example,
\begin{align}
F(x,y,z)&= x' \cdot y' \cdot z' + x' \cdot y' \cdot z + x \cdot y' \cdot z + x \cdot y \cdot z'\notag\\
&= m_{0} + m_{1} + m_{5} + m_{6}\notag\\
&= \sum (0,1,5,6)\label{eq-sop}\tag{5.2.1}
\end{align}
As you might expect, each of the terms defined above has a dual definition. A *sum term* is one in which all the literals are connected with OR operators. OR is additive, hence the use of “sum.” A sum term that contains all of the variables in the problem, either in its complemented or uncomplemented form, is called a *Maxterm* or *standard sum*. For example, if a problem involves three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) then \((x + y + z)\text{,}\) \((x' + y + z')\text{,}\) and \((x' + y' + z')\) are all Maxterms, but \((x + y)\) is not.

One or more sum terms connected with AND operators is a *product of sums* (*PoS*). AND is multiplicative, hence the use of “product.” A PoS in which each product term is a Maxterm is called a *product of Maxterms* (*PoM*) or *canonical product*. Since all the variables are present in each Maxterm, the canonical product is unique for a given problem.

It also follows that any Boolean function can be uniquely expressed as a product of Maxterms (PoM) that evaluate to \(0\text{.}\) Starting with the product of Maxterms ensures that the full effect of each variable has been taken into account. Again, this often does not lead to the best implementation, and in Section 5.3 we will see some tools to simplify PoMs.

It is common to index the Maxterms according to the values of the variables that would cause that Maxterm to evaluate to \(0\text{.}\) For example, \(x + y + z = 0\) when \(x = 0\text{,}\) \(y = 0\text{,}\) and \(z = 0\text{,}\) so this would be \(M_{0}\text{.}\) The Maxterm \(x' + y + z'\) evaluates to 0 when \(x = 1\text{,}\) \(y = 0\text{,}\) and \(z = 1\text{,}\) so is \(M_{2}\text{.}\) Table 5.2.2 lists all the Maxterms for a three-variable expression.

Maxterm | \(x\) | \(y\) | \(z\) |

\(M_{0} = x + y + z\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{0}\) |

\(M_{1} = x + y + z'\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{1}\) |

\(M_{2} = x + y' + z\) | \(\binary{0}\) | \(\binary{1}\) | \(\binary{0}\) |

\(M_{3} = x + y' + z'\) | \(\binary{0}\) | \(\binary{1}\) | \(\binary{1}\) |

\(M_{4} = x' + y + z\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{0}\) |

\(M_{5} = x' + y + z'\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{1}\) |

\(M_{6} = x' + y' + z\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{0}\) |

\(M_{7} = x' + y' + z'\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{1}\) |

A convenient notation for expressing a sum of Maxterms is to use the \(\prod\) symbol with a numerical list of the Maxterm indices. For example,
\begin{align}
F(x,y,z)&= (x + y' + z) \cdot (x + y' + z') \cdot (x' + y + z) \cdot (x' + y' + z')\notag\\
&= M_{2} + M_{3} + M_{4} + M_{7}\notag\\
&= \prod (2,3,4,7)\label{eq-prodsum}\tag{5.2.2}
\end{align}
The names “minterm” and “Maxterm” may seem somewhat arbitrary, but consider the two functions:
\begin{gather}
F_{1}(x,y,z) = x \cdot y \cdot z\label{mrow-54}\tag{5.2.3}\\
F_{2}(x,y,z) = x + y + z\label{mrow-55}\tag{5.2.4}
\end{gather}
There are eight (\(2^{3}\)) permutations of the three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\) \(F_{1}\) has one minterm and evaluates to \(1\) for only one of the permutations, \(x = y = z = 1\text{.}\) \(F_{2}\) has one Maxterm and evaluates to 1 for all permutations *except* when \(x = y = z = 0\text{.}\) This is shown in the following truth table:

minterm | Maxterm | |||

\(x\) | \(y\) | \(z\) | \(F_{1} = x \cdot y \cdot z\) | \(F_{2} = x + y + z\) |

\(\binary{0}\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{0}\) |

\(\binary{0}\) | \(\binary{0}\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{1}\) |

\(\binary{0}\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{1}\) |

\(\binary{0}\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{1}\) |

\(\binary{1}\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{1}\) |

\(\binary{1}\) | \(\binary{0}\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{1}\) |

\(\binary{1}\) | \(\binary{1}\) | \(\binary{0}\) | \(\binary{0}\) | \(\binary{1}\) |

\(\binary{1}\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{1}\) | \(\binary{1}\) |

OR-ing more minterms to an SoP expression *expands* the number of cases where it evaluates to \(1\text{,}\) and AND-ing more Maxterms to a PoS expression *reduces* the number of cases where it evaluates to \(1\text{.}\)

Show that Equation (5.2.1) and Equation (5.2.2) represent the same functionality. This shows that the sum of minterms and product of Maxterms are complementary.

Solution