Boolean Canonical Forms: Sum-of-Products and Product-of-Sums

In this follow-up to my previous articles on Boolean algebra basics and Boolean algegra laws, after first discussing some terminology, we will explore two canonical forms used to describe logic systems via the Boolean expressions that define them:

1. The sum-of-products (SoP), which is also known as the disjunctive normal form
2. The product-of-sums (PoS), which is also known as the conjunctive normal form

 

I will start with the SoP form because most people find it relatively straightforward. The PoS form is less intuitive for many. We will develop both using the principles of Boolean algebra and an appeal to intuition. After establishing both forms, we will describe how arbitrary Boolean equations can be recast into either form and how each form can be remolded into the other.

 

What is a Boolean Canonical Form?

Let’s demystify some of the terminology we will be using. The title says that this article is about “canonical forms.” What does this mean? A “form” is just a way to represent something—in this case, representing logic systems using Boolean expressions. Something is in a “canonical form” if it follows generally accepted rules regarding how to express that representation.

In many math and science fields, these rules often require that the representation have a particular format such that the canonical representation of a particular system is unique. This uniqueness makes determining if two systems are equivalent very straightforward. If their canonical representations are identical, then the two systems are equivalent, otherwise, they aren’t.

 

Equivalent Sans Ordering

Other terminology that you will come across is “sans ordering” or something similar. This means that two expressions are considered identical even if the ordering of the terms and/or factors within the expressions, or the ordering of variables within terms and/or factors, is different. For instance, A + B and B + A, while not strictly identical, would be considered equivalent sans ordering because of the commutative property of addition. Similarly, BC and CB are equivalent san ordering due to the commutative property of multiplcation. 

Combining those two properties, A + BC and CB + A, while not strictly identical, would be considered equivalent sans ordering. On the other hand, (A+B)(A+C), while equivalent logically to those equations, would not be considered equivalent.

“Sans ordering” is very common because humans are generally good enough at pattern matching to quickly recognize whether two expressions that are identical up to the ordering of the elements within it are equivalent. This lets the rules that define the canonical form to be greatly simplified and to focus on the important aspects (i.e., the things that humans aren’t good at recognizing, such as whether or not the application of some Boolean identities could transform one expression into the other).

 

The Importance of Uniqueness for Canonical Forms

Uniqueness is a very valuable property when working with logic systems because there are usually many different ways to describe the same system. For instance, consider the following logic equations for two systems.

 

$$X = (\overline{A}+BC) \cdot (\overline{B}C) + (A\overline{C} + B) \cdot (AB) $$

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

 

In these expressions, we adhere to the common convention that the order of precedence for Boolean operations is:

1. NOT (represented with an overbar)
2. AND (represented like arithmetic multiplication)
3. OR (represented like arithmetic addition)

 

Are these two systems equivalent? It turns out that they are, but this is far from obvious. One way to establish equivalence is to generate the truth table for each expression and then compare the two truth tables row by row.

Take a moment to become satisfied that the following truth table for output Z agrees with the equations for both X and Y above.

 

Table 1. Truth table for the example logic system.

A	B	C	Z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

 

Since there are three variables, there are only eight rows (2³ = 8). Practical logic systems may have many more signals than this, making it cumbersome, if not outright impractical, to generate and compare the truth tables.

 

SoP and PoS to the Rescue

What is needed is a systematic way to put both systems into a canonical form. Ideally, the method of doing so should be one that is easy to automate so that the two equations can be entered into a computer program in any acceptable form, and the program can then place them in canonical form for comparison (as well as for other subsequent purposes).

There are two widely used such forms in Boolean algebra: “canonical disjunctive normal form” and “canonical conjunctive normal form”. Again, don’t let unfamiliar terms rattle you. The terms ‘disjunctive’ and ‘conjunctive’ are simply fancy words used in formal logic circles for logical-OR and logical-AND, respectively.

 

Normal, Standard, or Canonical Forms?

The other term that might be unfamiliar is “normal form”. In many instances, “canonical form”, “normal form”, and “standard form” are interchangeable; but in computer science, while “normal form” and “standard form” are usually equivalent, they often refer to a slightly-relaxed version of the more-strict “canonical form”. The canonical form stresses uniqueness (usually sans ordering), while the normal form is willing to sacrifice this in favor of allowing greater compactness. We will see examples of this as we proceed.

 

Sum-of-Products: The Canonical Disjunctive Normal Form

Instead of just stating what this form is, let’s see how it evolves quite naturally from the truth table representation of a logic function. Let’s use the truth table shown earlier in Table 1. We can easily translate this truth table into a logic equation by going down the table and, for each row in which the output is a 1, write a logic expression that is True for that row and that row only.

We will use the simplest such expression in which every input variable is present exactly once. The complemented form of variable is used if it must be False (0), or uncomplimented if it must be True (1). For simplicity, we have replicated the three rows which have a Z=1 output in Table 2.

 

Table 2. Truth table for which Z is True (1).

A	B	C	Z
0	0	1	1
1	1	0	1
1	1	1	1

 

From these three rows, we can generate three product statements (logical-AND):

 

$$Z_1 = \overline{A}\overline{B}C$$

$$Z_2 = AB \overline{C}$$

$$Z_3 = ABC$$

 

Minterms

Each of these three product statements is a minterm—a term that is True (1) for exactly one combination of inputs. The standard way to represent a minterm is as a product (i.e., logical-AND) of all of the signals, using the complement of any signal that needs to be False for that combination of inputs.

 

Sum of the Minterms = Sum-of-Products

An equation comprised of the sum of minterms is a unique representation (sans ordering) of the logic system it describes and is, therefore, canonical. The equation for our three minterm row equations ORed together is:

 

$$Z = \overline{A}\overline{B}C + AB\overline{C} + ABC$$

 

This is a sum-of-products equation, or when we want to sound sophisticated, the canonical disjunctive normal form. Using the notation borrowed from normal arithmetic in which logical-AND is depicted as the product of two signals and logical-OR is depicted as the sum (as is done above), this equation takes on the form of a sum of terms in which each term is the product of signals, thus giving it the widely used “sum-of-products” moniker, or SoP for short.

An examination of the last two terms in this equation shows that they can easily be combined and the variable ‘C’ eliminated from them, leaving:

 

$$Z = \overline{A}\overline{B}C + AB$$

 

This is certainly a more compact way of writing the logic equation for the same system, and this equation is also clearly written in SoP (or in conjunctive normal form). However, this equation is no longer in canonical form, which requires that each term be a “minterm.”

 

Product-of-Sums: The Canonical Disjunctive Normal Form

While the SoP form is pretty intuitive for most people, it can result in overly long expressions, particularly for systems where most input combinations produce a logic True output and only a few produce a logic False.

So, it is reasonable to wonder if there is an alternative normal form that favors this situation. There is, and it is commonly known as the product-of-sums form (PoS), more properly known as the “disjunctive normal form”.

For a concrete example, let’s consider the following truth table, which is merely the logical inverse of our earlier system with \(W = \overline{Z}\).

 

Table 3. Truth table for calculating product-of-sums example.

A	B	C	W
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

 

Our process for developing the product-of-sums form will be effectively the opposite of that used to generate the sum-of-products. This time, our goal is to construct an expression that is only False (0) for each row in our table, for which W is False (0). These three rows are listed in Table 4.

 

Table 4. Truth table for which W is False (0).

A	B	C	W
0	0	1	0
1	1	0	0
1	1	1	0

 

Let’s consider the case of A=0, B=0, and C=1, as shown in the first row of Table 4. Our truth table shows that the output for this case should be 0.

Consider the situation when A=1? Without knowing what B and C are, we know that the output should be True because we know that whatever row of the truth table it might be, it can’t be the one we are interested in. So, we want a function that will be True whenever A=1, regardless of the value of any other input. That is the description of an OR gate in which one input is A.

By similar reasoning, we want our other inputs to be B and C’, or:

 

$$ \overline{W_1} = A + B + \overline{C}$$

 

Before proceeding, let’s be sure that we are comfortable with the notion that this really does what we want, meaning that it is False if A=0, B=0, and C=1 but that it is True in every other case. First, for the case we are interested in, the output will be False because the expression was crafted specifically such that each of the terms in the expression is False in this case—for each input, we are using the opposite of the value in that target row.

 

Maxterms

Just as a minterm is an expression that is True for exactly one combination of inputs, a maxterm is an expression that is False for exactly one. As we have done above in our equation for \(\overline{W_1}\), the standard way to represent a maxterm is as the sum (i.e., logical-OR) of all the variables, using the complement of each signal that needs to be True for that combination of inputs.

To see that it must then be True for all other cases, we merely need to recognize that the only way to get to any other case is to change the value of at least one of the input signals and, in doing so, change the value of that term in the expression from False to True. Then, because the terms are all ORed together, all it takes is a single term being True to make the overall expression True.

Using the same approach, the expressions for the other two rows in Table 4 that should produce a False (0) output can be written as:

 

$$ \overline{W_2} = \overline{A} + B + C$$

$$ \overline{W_3} = \overline{A} + B + \overline{C}$$

 

Product of the Maxterms = Product-of-Sums

An equation comprised of the product of maxterms is a unique representation (sans ordering) of the logic system it describes and is, therefore, canonical. Therefore, our last step is to combine these individual expressions to get a correct equation for the complete truth table. In words, we can describe what we need in two different ways, both of which result in the same equation.

First, we could say that we need ALL of the individual expressions to be True in order for the overall equation to be True. Second, we could say that the output should be False if ANY of the individual expressions are False. Both of these describe a logical-AND of all the relevant expressions, which is precisely what we need:

 

$$W = (A + B + \overline{C}) \cdot (\overline{A} + B + C) \cdot (\overline{A} + B + \overline{C})$$

 

This equation is our desired product-of-sums or, more formally, the canonical disjunctive normal norm.

 

The Relationship Between Sum-of-Products and Product-of-Sums

Let’s now take a step back and come at this again, but from a different direction, to achieve the same result for the product–of-sums. Imagine first making a second function that is the logical inverse of the target function, W.

We already know how to write an SoP equation for this second function using the minterms associated with each row for which this function is True (which are exactly the rows where our target function is False). In this example, we’ve already done this since our “second function” happens to be our original system \(Z = \overline{W}\)..

We can therefore generate an equation for W by inverting the SoP equation for Z.

 

$$W = \overline{Z} = \overline{\overline{A}\overline{B}C + AB\overline{C} + ABC}$$

 

We can then apply DeMorgan’s Theorem to get rid of the overall inversion.

 

$$W = \overline{(\overline{A}\overline{B}C)} \cdot \overline{(AB\overline{C})} \cdot \overline{(ABC)}$$

 

Finally, we can apply DeMorgan’s to each of the factors to remove their inversions, yielding the same final equation obtained previously.

 

$$W = (A + B + \overline{C}) \cdot (\overline{A} + B + C) \cdot (\overline{A} + B + \overline{C})$$

 

As was the case with the equation for Z, we can simplify this expression to

 

$$W = (A + B + \overline{C}) \cdot (\overline{A} + B)$$

 

This equation is still in PoS (or conjunctive normal) form, but is not in canonical form, which requires that each factor be a maxterm that is True for all possible combination of inputs except exactly one.

 

When to Use SoP and PoS

A given logic system can be described by countless, seemingly different, Boolean equations. The use of canonical forms for these equations makes the process of determining if two such systems are equivalent more tractable since any system has only one equation of that form that describes it, at least up to the point of the specific ordering of the elements that make up the equation.

Two very common such forms are the sum-of-products (when each term is a minterm) and the product-of-sums (when each factor is a maxterm). The former is particularly useful when relatively few of the possible input combinations produce a logical True output, while the latter is best suited when most of them do.

Understanding how to develop and manipulate these Boolean canonical forms is important for digital system design and optimization.

 

Featured image used courtesy of Adobe