## The SOP and POS forms of Boolean Functions

We illustrate the principles of representing the functions in the
SOP (= Sup-of-Products) and POS (= Product-of-Sums) forms on the example
of the three-input **majority function F**. This function takes on
the value 1 if and only if the number of ones in the input vector
exceeds the number of zeros.

*A B C* | *F* |

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 |
0 0 0 1 0 1 1 1 |

In general the SOP form of a Boolean function consists of
collections of ANDed variables (called *terms*) that are ORed
together. For example, the SOP form of the function **F** is

Any Boolean function **f(x**_{1},...,x_{n}) can be
represented in the SOP form. We describe below a way for constructing one of
such representations, which is called *canonical*.
For this consider the entries in the truth table
where the function **f** takes on the value 1. For each such a string the
SOP form will contain a term involving all the **n** variables, some of
which are negated. More exactly,
if **f(a**_{1},...,a_{n})=1 then in the term corresponding
to the entry **(a**_{1},...,a_{n}) the variable
**x**_{i} is negated **a**_{i}=0 and is not negated
otherwise. Therefore, the number of
terms in the canonical SOP form equals the number of "ones" of the
function **f**, i.e. the number of entries of the truth table where
**f** takes on the value 1.

The SOP form of a function is not unique in general. For example, the
majority function can also be represented in the following (non-canonical)
SOP form

| |
| (1) |

A dual to the SOP form is the POS form. The POS form consists of
collections of ORed variables (called *maxterms*) that are ANDed together.
One method of obtaining the POS form is to start with the complement of the
SOP form, and then apply DeMorgan's theorem.

For example, consider the majority function above, and represent its
complement in the POS form:

| |
| (2) |

Complementing both sides of (2), and applying the involution property
yields

| |
| (3) |

Applying to (3) DeMorgan's theorem in the form
provides

| |
| (4) |

Finally, applying to (4) DeMorgan's theorem in the form
results in a
POS form for **F**

This method being applied to the canonical SOP form results in the POS
form called canonical. The number of the maxterms in the canonical POS form
equals the the number of zeros of the function. Moreover, in each
maxterm every variable appears exactly once in either true or negated
form. Any maxterm has a value 0 for only one entry in the truth table.

One motivation for using the POS form is that it may result in a simpler
Boolean formula. Thus, if the number of ones of a Boolean function
exceeds the number of zeros, then the number of terms in the canonical
POS from exceeds one in the canonical POS form.

The SOP form of a function is not unique in general. For example, applying
the methods above to the SOP form of majority function (1) results
in the following (non-canonical) POS form

It can be shown that the number of distinct SOP (and also POS) forms
of **n** variables equals **2**^{3n}. However, since
the number of Boolean functions is only **2**^{2n},
then not all these forms correspond to different functions. In other words,
a function can have many SOP (resp. POS) different forms. Therefore, it
makes sense to ask for a simplest one, in a sense.