Boolean Logic -- SOP and POS forms

Introduction

Let's set the stage for this discussion by defining a function with the following truth table.


#||A|B|C||F
0||0|0|0||0
1||0|0|1||1
2||0|1|0||0
3||0|1|1||1
4||1|0|0||1
5||1|0|1||0
6||1|1|0||1
7||1|1|1||1
Table 1 - Arbitrary function defined via Truth Table

The first column is merely a convenient label for each row obtained by interpreting the combination of inputs as a straight binary value.

As we will see shortly, we can express this function in two equivalent ways:

\((1) \ \ F \, = \, \overline{A}\overline{B}C \, + \, \overline{A}BC \, + \, A\overline{B}\overline{C} \, + \, AB\overline{C} \, + \, ABC
\
(2) \ \ F \, = \, (A+B+C)(A+\overline{B}+C)(\overline{A}+B+\overline{C})\)

The first of these, Eqn (1), is the Standard Sum of Products, or Standard SOP, form while the second, Eqn (2), is the Standard Product of Sums, or Standard POS, form.

The term "standard" here means that the expression consists exclusively of minterms (in the case of Standard SOP) or maxterms (in the case of Standard POS). What a minterm and maxterm are will be discussed shortly.

As we can see, the names are quite descriptive -- the SOP form takes on the appearance of being a sum of several terms, each of which is the product of several factors while the POS form takes on the appearance of being a product of several factors, each of which is the sum of several terms.

We should keep in mind that "products" and "sums" are concepts from normal algebra; while we borrow the terms and use them in Boolean algebra, we do not mean "multiplication" or "addition" -- a "product" in Boolean algebra is a logical AND operation while a "sum" is a logical OR operation.

In this discussion, we are interested in how to go from a Truth Table to the SOP or POS forms and how to work with them, including translating between them, using Boolean algebraic manipulations only. So we will not be discussing topics such as Karnaugh maps except in passing.

Before we can talk about constructing the SOP and POS forms from the Truth Table, we need to define a couple of more fundamental concepts, namely minterms and maxterms.

Minterm

A "minterm" is a Boolean expression that is True for the minimum number of combinations of inputs; this minimum number is exactly one (the case of a term being True for no combination of inputs is, of course, simply a hard False and is trivial and uninteresting).

Because we want to minimize the coverage, we want to use the Boolean operation that is the most restrictive, which is the AND operation. Since the AND is true only if ALL of the inputs are True, we can craft an expression that is True for only a single combination of inputs by including each input in the product. If the input is uncomplemented, then we require that it be True, while if it is complemented, then we require it to be False. The minterm expression for each combination of inputs is therefore


#||A|B|C||minterm
0||0|0|0|| \(\overline{A}\overline{B}\overline{C}\)
1||0|0|1|| \(\overline{A}\overline{B}C\)
2||0|1|0|| \(\overline{A}B\overline{C}\)
3||0|1|1|| \(\overline{A}BC\)
4||1|0|0|| \(A\overline{B}\overline{C}\)
5||1|0|1|| \(A\overline{B}C\)
6||1|1|0|| \(AB\overline{C}\)
7||1|1|1|| \(ABC\)
Table 2 - Table of Minterms

Keep in mind that each minterm is True only for the specific combination of inputs with which it is associated and is False for all others.

In order to be a minterm, the product must cover exactly one of the possible combination of inputs. To do this, each input must be present in either uncomplemented or complemented form. Consider the system of three inputs in the table above. We can combine the last two minterms, namely ABC'+ABC, into a single product, namely AB. Using this "simplifies" the expression and it is still in SOP form, but it is not a minterm and the resulting expression is no longer in standard -- i.e., canonical -- SOP form. This may or may not be important.

If we have an expression that is in SOP form but is not in standard form and we need it to be, then we can simply expand each product by ANDing it with products that are constructed by ORing one of the missing inputs and its complement. Thus, we can expand AB back to minterm form as follows:

\(AB \ = \ AB(C+\overline{C}) \ = \ ABC \, + \, AB\overline{C}\)

Maxterm

A "maxterm" is a Boolean expression that is True for the maximun number of combinations of inputs; this maximum number is exactly one fewer than the total number of possibilities (the case of a term being True for all combinations is, of course, simply a hard True and is trivial and uninteresting).

Because we want to maximize the coverage, we want to use the Boolean operation that is the most permissive, which is the OR operation. While the OR is True if ANY of its inputs is True, for our purposes it is more convenient to recognize that the OR is False only if ALL of its inputs are False; thus, we can craft an expression that is False for only a single combination of inputs by including each input in the sum. If the input is uncomplemented, then we require that it be False, while if it is complemented, then we require it to be True. The maxterm expression for each combination of inputs is therefore


#||A|B|C||maxterm
\(\overline{0}\) ||0|0|0|| \(A+B+C\) \(\overline{1}\) ||0|0|1|| \(A+B+\overline{C}\) \(\overline{2}\) ||0|1|0|| \(A+\overline{B}+C\) \(\overline{3}\) ||0|1|1|| \(A+\overline{B}+\overline{C}\) \(\overline{4}\) ||1|0|0|| \(\overline{A}+B+C\) \(\overline{5}\) ||1|0|1|| \(\overline{A}+B+\overline{C}\) \(\overline{6}\) ||1|1|0|| \(\overline{A}+\overline{B}+C\) \(\overline{7}\) ||1|1|1|| \(\overline{A}+\overline{B}+\overline{C}\)
Table 3 - Table of Maxterms

Keep in mind that each maxterm is False only for the specific combination of inputs with which it is associated and is True for all others.

In order to be a maxterm, the sum must cover all but exactly one of the possible combination of inputs. To do this, each input must be present in either uncomplemented or complemented form. Consider the system of three inputs in the table above. We can combine the last two maxterms, namely (A'+B'+C)(A'+B'+C'), into a single sum, namely (A'+B'). Using this "simplifies" the expression and it is still in POS form, but it is not a maxterm and the resulting expression is no longer in standard -- i.e., canonical -- POS form. This may or may not be important.

If we have an expression that is in POS form but is not in standard form and we need it to be, then we can simply expand each sum by ORing it with terms that are constructed by ANDing one of the missing inputs and its complement. Thus, we can expand (A'+B') back to maxterm form as follows:

\(\overline{A} + \overline{B} \ = \ \overline{A} + \overline{B}+C \overline{C} \ = ( \overline{A} + \overline{B}+C)( \overline{A}+ \overline{B} + \overline{C})\)

The above equation may look odd but that is because while we are used to multiplication being distributable over addition (and thus AND being distributable over OR looks natural), we are used to addition not being distributable over multiplication. However, OR is distributable over AND, hence

\(X+YZ \ = \ (X+Y)(X+Z)\)

In the above relation,
\(X \ = \ \overline{A} + \overline{B}\)

Relationship between Labels, Minterms, and Maxterms

Consider the minterm and maxterm for a particular row. Since the minterm is True ONLY when that input combination is asserted while the maxterm is False ONLY when that combination is asserted, it is clear that each minterm is the logical inverse of the corresponding maxterm (and vice versa, of course).

This relationship is quite obvious if we look at a particular example, say Row 3, and apply DeMorgan's Theorem to it.

\((3) \ \ \text{Minterm3} \, = \, \overline{A}BC
\,
(4) \ \ \text{Maxterm3} \, = \, \overline{\text{Minterm3}}
\ \ \ \ \ = \, \overline{\overline{A}BC}
\ \ \ \ \ = \, (A+\overline{B}+\overline{C})\)

The labels in Tables 2 are often used as a synonym for a minterm expression. This makes intuitive sense if we think of row N being "True" when the minterm associated with the row labeled N is True.

In contrast, since a maxterm is the logical inverse of a minterm, we can use an inverted label to refer to a maxterm, as shown in Table 3. Therefore

\((5) \ 3 \, = \, \overline{A}BC \ (\text{Minterm3})
\
(6) \ \overline{3} \, = \, (A+\overline{B}+\overline{C}) \ (\text{Maxterm3})\)

It should be clear how this labeling convention is consistent with, for instance, applying DeMorgan's theorems and other Boolean operations.

Standard SOP (Sum of Products)

As mentioned in the introduction, the SOP form takes on the appearance of being a sum of several terms, each of which is the product of several factors.

To craft the SOP form of a Boolean logic function, we merely need to OR together the minterms associated with each combination of inputs for which the overall output should be True.

By looking at Table 1 we see that we need to sum the minterms associated with rows {1,3,4,6,7}. This is often represented simply as

\((7) \ \ F \, = \, \sum(1,3,4,6,7)\)

By expanding the summation and replacing each label with the corresponding minterm, we immediately obtain Eqn 1, which is the canonical disjunctive form. Don't let the fancy words confuse you; the term "canonical" just means "standardized" while the term "disjunctive" merely means a logical union, which is the same thing as a logical ORing of sets. This form is more commonly known, particularly among the more application-oriented, simply as the Standard SOP form.

Standard POS (Product of Sums)

As mentioned in the introduction, the POS form takes on the appearance of being a product of several factors, each of which is the sum of several terms.

To craft the POS form of a Boolean logic function, we merely need to AND together the maxterms associated with each combination of inputs for which the overall output should be False.

This is not as obvious as the need to OR together the minterms to get the SOP, so let's consider it for a moment. If we AND together several factors, the output will be False as long as any one of the factors is False. A maxterm is False for exactly one combination of inputs, so using a maxterm for a combination for which we want the overall output to be False will achieve this goal and, since that maxterm is True for all other combinations, it will have no effect on the output for them. As long as we do not include the maxterms for any combinations that we do want the output to be True for, we are guaranteed that all of the other maxterms in the expression will be True and, hence, the overall product of them will be True.

By looking at Table 1 we see that we need to take the product of the maxterms associated with rows {0',2',5'}. This is often represented simply as

\((8) \ \ F \, = \, \prod (\overline{0}, \overline{2}, \overline{5})\)

By expanding the product and replacing each label with the corresponding maxterm, we immediately obtain Eqn 2, which is the canonical conjunctive form. Don't let the fancy words confuse you; the term "canonical" just means "standardized" while the term "conjunctive" merely means a logical intersection, which is the same thing as a logical ANDing of sets. This form is more commonly known, particularly among the more application-oriented, simply as the Standard POS form.

Converting Boolean Expressions into SOP/POS Form

The process of converting any Boolean expression into either POS or SOP form (canonical or otherwise) is very straightforward.

To get the expression in SOP form, you simply distribute all AND operations over any OR operations and continue doing this as long as possible. When finished, you will have an expression in SOP form. If you want it in canonical form, then you simply expand each term as necessary.

To get the expression in POS form, you simply distribute all OR operations over any AND operations and continue doing this as long as possible. When finished, you will have an expression in POS form. If you want it in canonical form, then you simply exapnd each term as necessary.

Most people have little problem getting an arbitrary expression into SOP form because the notation used for AND and OR are the same used for multiplication and addition in normal arithmetic and the notion of distributing multiplication over addition has long become internalized. But the fact that addition is not distributable over multiplication has also been internalized and hence doing something that looks the same does not come naturally. But just as AND can be distributed over OR, so too can OR be distributed over AND.
  • Like
Reactions: Parth786

Blog entry information

Author
WBahn
Views
148,161
Last update

More entries in General

More entries from WBahn

Share this entry

Top