Demystifying SOP and POS

Background

One of the most elementary fact taught in a standard digital electronics course is the fact that any boolean truth table can be written as a formula in one of the SOP (sum of products) or POS (product of sums).
This might seem slightly magical in the first encounter, especially if one wants to write down the formula using step by step instructions in these books.

For instance, consider the following boolean truth table:

x	y	z	f
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1
Then we can write

$$f=\bar{x}\bar{y}\bar{z}+\bar{x}yz+xy\bar{z}+xyz,(SOP),$$

or

$$f=(x+y+\bar{z})(x+\bar{y}+z)(\bar{x}+y+z)(x+\bar{y}+z),(POS).$$

However, there is a very easy and intuitive way of understanding this.

Analogy

Consider creating a pixelated pattern using wood blocks. There are two obvious ways to do this:

• Put the wooden blocks besides each other to form the pattern.
• Carve the pattern out from a solid.
  First approach is the same as sum of products, and the second method is the product of sums.

But how does it work? The and formula and or formula as the following interesting properties, and the best way to put this is by an example. Let $x_1,x_2,x_3,x_4$ boolean variables, and consider the following formula

$$f=x_1{\bar{x}}_2{x}_3{\bar{x}}_4,g={\bar{x}}_1+x_2+{\bar{x}}_3+{\bar{x}}_4.$$

Then

• $f$ is true if and only if $(x_1,x_2,x_3,x_4)=(1,0,1,0)$.
• g is false if and only if $(x_1,x_2,x_3,x_4)=(1,0,1,1)$.

In other words, $f$ is always false except at one point, and $g$ is always true except at one point. In other words, $f$ is like the wooden blocks that we can place besides each other, and $g$ is like the carving masks.

So back to the example above, in order to produce the pattern $f$, we can treat each of the rows that are $1$, as the wooden pieces required to make the pattern, and each row with value $0$ as the parts that needs to be carved out.

So to produce the bit pattern in $f$ we can start with all zero rows, and add the rows with value $1$ one by one. Or start with all $1$ rows and carve out the rows with value $0$.

Starting with all 0 rows and putting 1’s

For each row that its value is $1$, we come up with a formula that is $1$ only at that row. We use the property of and formula that is zero everywhere except at one point. Then we add those building blocks:

$$f=\bar{x}\bar{y}\bar{z}+\bar{x}yz+xy\bar{z}+xyz,(SOP),$$

Starting with all 1’s and carving 0’s

We use the property of the or formula that is 1 everywhere except at one row. So for each row with value zero that we want to carve out, we write an or formula that is zero only and only at that row, and multiply these masks. So

$$f=(x+y+\bar{z})(x+\bar{y}+z)(\bar{x}+y+z)(x+\bar{y}+z).$$

Note that the indicator functions for the POS can be derived via the De Morgan’s law. For instance suppose we want to find an expression that is zero in the second row, and is one everywhere else. To make that we can easily bake a function that is 1 at the second row and is zero everywhere else, which is

$$\bar{x}\bar{y}z.$$

Now the original function of interest will be logical not of the function above:

$$\overline{\bar{x}\bar{y}z}=x+y+\bar{z},$$

which is the first expression in the $f$ written as SOP.

under development:

Similar Ideas in Probability Theory

In the probability theory it is often the case to write a simple random variable as sum of indicator functions. Let $X$ be a random variable

$$X:\Omega \to \{a_1,a_2,\dots ,a_n\}.$$

Then we can write this random variables as a sum of indicator random variables

$$X=\sum _{i=1}^n{a}_i{1}_{\{X=a_i\}}.$$

where for any $A\subseteq \Omega$ the indicator function

$$1_A:\Omega \to \{0,1\},$$

is defined as

$$1_A(\omega )=\{\begin{array}{l}1\omega \in A,\\ 0\omega \notin A.\end{array}$$

We can also write the random variable as a product of indicator functions, that is

$$X=\prod a_i^{1_{X=a_i}}$$