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.

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₁,...,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₁,...,a_n)=1 then in the term corresponding to the entry (a₁,...,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 SOP 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³ⁿ. However, since the number of Boolean functions is only 2²ⁿ, 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.