Canonical Form
Boolean functions expressed as a sum of minterms or product of maxterms are said to be in canonical form.
For a Boolean function of \(n\) variables, a product term in which each of the \(n\) variables appears once (either in its complemented or uncomplemented form) is called a minterm. Thus, a minterm is a logical expression of \(n\) variables that employs only the complement \((')\) operator and the AND \((\cdot)\) operator.
For a Boolean function of \(n\) variables, a sum term in which each of the \(n\) variables appears once (either in its complemented or uncomplemented form) is called a maxterm. Thus, a maxterm is a logical expression of \(n\) variables that employs only the complement \((')\) operator and the OR \((+)\) operator.
For a Boolean function of \(n\) variables, there are \(2^n\) distinct minterms/maxterms, since a variable in the minterm/maxterm expression can be in either its complemented or its uncomplemented form.
The maxterm with subscript \(i\) is a complement of the minterm with the same subscript \(i\) and vice versa.
\(\boxed{m_{i}^{\,\prime} = M_i}\)
\(\boxed{M_{i}^{\,\prime} = m_i}\)
For example, a truth table of functions \(f_1\) and \(f_2\) of \(3\) variables \((x,\,y,\,z)\).
| \(x\) | \(y\) | \(z\) | \(f_1\) | \(f_2\) | Minterms \(m_i\) | Maxterms \(M_i\) |
|---|---|---|---|---|---|---|
| \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(\displaystyle m_0 = x^{\,\prime} \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle M_0 = x + y + z\) |
| \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(\displaystyle m_1 = x^{\,\prime} \cdot y^{\,\prime} \cdot z\) | \(\displaystyle M_1 = x + y + z^{\,\prime}\) |
| \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(\displaystyle m_2 = x^{\,\prime} \cdot y \cdot z^{\,\prime}\) | \(\displaystyle M_2 = x + y^{\,\prime} + z\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(\displaystyle m_3 = x^{\,\prime} \cdot y \cdot z\) | \(\displaystyle M_3 = x + y^{\,\prime} + z^{\,\prime}\) |
| \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | \(\displaystyle m_4 = x \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle M_4 = x^{\,\prime} + y + z\) |
| \(1\) | \(0\) | \(1\) | \(0\) | \(1\) | \(\displaystyle m_5 = x \cdot y^{\,\prime} \cdot z\) | \(\displaystyle M_5 = x^{\,\prime} + y + z^{\,\prime}\) |
| \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(\displaystyle m_6 = x \cdot y \cdot z^{\,\prime}\) | \(\displaystyle M_6 = x^{\,\prime} + y^{\,\prime} + z\) |
| \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(\displaystyle m_7 = x \cdot y \cdot z\) | \(\displaystyle M_7 = x^{\,\prime} + y^{\,\prime} + z^{\,\prime}\) |
Sum of Minterms
A Boolean function can be expressed algebraically from a given truth table by forming a minterm for each combination of the variables that produces a \(1\) in the function and then taking the OR \((+)\) of all those minterms.
Expressing the truth table of function \(f_1\) as a sum of minterms,
\(\displaystyle f_1 = \Sigma(1,\,4,\,7) = m_1 + m_4 + m_7\)
\(\displaystyle f_1 = x^{\,\prime} \cdot y^{\,\prime} \cdot z + x \cdot y^{\,\prime} \cdot z^{\,\prime} + x \cdot y \cdot z\)
Expressing the truth table of function \(f_2\) as a sum of minterms,
\(\displaystyle f_2 = \Sigma(3,\,5,\,6,\,7) = m_3 + m_5 + m_6 + m_7\)
\(\displaystyle f_2 = x^{\,\prime} \cdot y \cdot z + x \cdot y^{\,\prime} \cdot z + x \cdot y \cdot z^{\,\prime} + x \cdot y \cdot z\)
The summation symbol \(\Sigma\) stands for the OR-ing \((+)\) of minterms; the numbers are the indices of the minterms of the function.
To express a Boolean function as a sum of minterms, it must first be brought into a form of AND terms. This may be done by using the distributive law. Then any missing variable \(x\) in each AND term is AND-ed \((+)\) with \(x + x^{\,\prime}\). Similar minterms can be combined by using the idempotence theorem.
Product of Maxterms
A Boolean function can be expressed algebraically from a given truth table by forming a maxterm for each combination of the variables that produces a \(0\) in the function and then taking the AND \((\cdot)\) of all those maxterms.
Expressing the truth table of function \(f_1\) as a sum of maxterms,
\(\displaystyle f_1 = \Pi(0,\,2,\,3,\,5,\,6) = M_0 \cdot M_2 \cdot M_3 \cdot M_5 \cdot M_6\)
\(\displaystyle f_1 = \left(x + y + z\right)\cdot\left(x + y^{\,\prime} + z\right)\cdot\left(x + y^{\,\prime} + z^{\,\prime}\right)\cdot\left(x^{\,\prime} + y + z^{\,\prime}\right)\cdot\left(x^{\,\prime} + y^{\,\prime} + z\right)\)
Expressing the truth table of function \(f_2\) as a sum of maxterms,
\(\displaystyle f_2 = \Pi(0,\,1,\,2,\,4) = M_0 \cdot M_1 \cdot M_2 \cdot M_4\)
\(\displaystyle f_2 = \left(x + y + z\right)\cdot\left(x + y + z^{\,\prime}\right)\cdot\left(x + y^{\,\prime} + z\right)\cdot\left(x^{\,\prime} + y + z\right)\)
The product symbol \(\Pi\) stands for the AND-ing \((\cdot)\) of maxterms; the numbers are the indices of the maxterms of the function.
To express a Boolean function as a product of maxterms, it must first be brought into a form of OR terms. This may be done by using the distributive law. Then any missing variable \(x\) in each OR term is OR-ed \((+)\) with \(x \cdot x^{\,\prime}\). Similar maxterms can be combined by using the idempotence theorem.
Conversion between Canonical Forms
The complement of a function expressed as the sum of minterms equals the sum of minterms missing from the original function. And, the complement of a function expressed as the product of maxterms equals the product of maxterms missing from the original function.
For example, consider the function \(\displaystyle F(A,\,B,\,C) = \Sigma(1,\,4,\,5,\,6,\,7)\)
Since there are \(3\) variables in a function \(F\), the function \(F\) has \(2^3 = 8\) distinct minterms/maxterms.
Therefore, the function has a complement that can be expressed as
\(\displaystyle F^{\prime}(A,\,B,\,C) = \Sigma(0,\,2,\,3) = m_0 + m_2 + m_3\)
Taking the complement of \(F^{\prime}\) by De Morgan’s theorem, the function \(F\) is obtained in a different form
\(\displaystyle F(A,\,B,\,C) = (m_0 + m_2 + m_3)^{\prime} = m_{0}^{\,\prime} \cdot m_{2}^{\,\prime} \cdot m_{3}^{\,\prime} = M_0 \cdot M_2 \cdot M_3 = \Pi(0,\,2,\,3)\)
In general, to convert from one canonical form to another, interchange the symbols \(\Sigma\) and \(\Pi\) and list those numbers missing from the original form.
In order to find the missing terms, one must realize that the total number of minterms/maxterms is \(2^n\), where \(n\) is the number of binary variables in the function.
Standard Form
Another way to express Boolean functions is in standard form. In this configuration, the terms that form the function may contain one, two, or any number of literals. There are two types of standard forms: the sum of products and product of sums.
The sum of products is a Boolean expression containing AND terms, called product terms, with one or more literals each. The sum denotes the OR-ing \((+)\) of these terms.
For example, \(\displaystyle F_1 = y^{\,\prime} + x \cdot y + x^{\,\prime} \cdot y \cdot z^{\,\prime}\)
The product of sums is a Boolean expression containing OR terms, called sum terms. Each term may have any number of literals. The product denotes the AND-ing \((\cdot)\) of these terms.
For example, \(\displaystyle F_2 = x \cdot \left(y^{\,\prime} + z\right) \cdot \left(x^{\,\prime} + y + z^{\,\prime}\right)\)
The gate structure of the sum-of-products expression consists of a group of AND gates for the product terms followed by a single OR gate. And, the gate structure of the product-of-sums expression consists of a group of OR gates for the sum terms followed by a single AND gate.
This standard type of expression results in a two-level structure of gates.
In general, a two-level implementation is preferred because it produces the least amount of delay through the gates when the signal propagates from the inputs to the output. However, the number of inputs to a given gate might not be practical.