SOP & POS

Deriving the Boolean Expressions from Truth Table

There are 2 types of Boolean Equations used in this section for the analysis of truth table. One type is called the

SUM OF PRODUCTS (SOP) and the other is the PRODUCT OF SUM (POS).

SUM OF PRODUCTS (SOP)

A Boolean expression that consists of the ORing of terms that are ANDed.

EXAMPLES:

f = AB + A'C' + BCD

f = AA' + AB' + A'B + BB'

f = ABCD + A'BCD + (BC)'

PRODUCT OF SUM (POS)

A Boolean expression that consists of the ANDing of terms that are ORed.

EXAMPLES:

f = (A + B) (C + D)

f = (A + B +C) (A + B' + C') (A' + B + C) (A' + B' + C')

f = (A' + B + C') (A' + B' + C) (A + B' + C)

The Logic Circuit Diagrams for SOP and POS.

The standard representations of a Boolean function typically contain either logical

product (AND) terms called “minterms” or logical sum (OR) terms called “maxterms.” These standard representations make the minimization procedures easier. The standard representations are also called “Canonical forms.”

A minterm is a product term of all input variables in which each variable can be either complemented or uncomplemented. For example, there are four minterms for two variables, A and B. These minterms are A'B', A'B, AB', and AB. On the other hand, there are eight minterms for three variables, A, B, and C. These minterms are A' B' C', A' B' C, A'BC', A'BC, AB'C', AB'C, ABC', and ABC. These product terms represent numeric values from 0 through 7. In general, there are 2nminterms for n variables.

A minterm is represented by the symbol mj, where the subscript j is the decimal equivalent of the binary number of the minterm. For example, the decimal equivalents (j) of the binary numbers represented by the four minterms of two variables, A and B, are 0 (A'B'), 1(A'B), 2(AB'), and 3 (AB). Therefore, the symbolic representations of the four minterms of two variables are m0,m1, m2, and mj, as follows:

In general, the n minterms of p variables is n = 2p variables are:m0,m1, m2, ... ,mn-1.

From Table Above, we can write the minterm expansion for a general function of 3 variables as follows:

Note that if ai=1, minterm mi is present in the expansion; if ai=0, the corresponding minterm is not present. This equation is the Sum-of-Minterms which forms the CANNONICAL SOP.

It has been shown that a Boolean hnction can be defined by a truth table. A Boolean function can be expressed in terms of minterms. For example, consider the following truth table:

One can determine the function f by logically summing (ORing) the product terms for which f is 1. Therefore,

f = A'B' + AB' + AB

This is called the Sum-of-Products (SOP) expression.

Sum of Product format (SOP)

A logic diagram of a sum-of-products expression contains several AND gates followed by a single OR gate. In terms of minterms, f can be can be derived from the equation:

Where f having a0=a2=a3=1 making f = m1+m2+m3 can be represented as:

A maxterm, on the other hand, can be defined as a logical sum (OR) term that contains all input variables in complemented or uncomplemented form. The four maxterms of two variables (A,B) are A + B, A + B', A' + B , and A' + B'. A maxterm is obtained from the logical sum of all the input variables by complementing each variable. Each maxterm is represented by the symbol Mj, where the subscript j is the decimal equivalent of the binary number of the maxterm. Therefore, the four maxterms of the two variables, A and B, can be represented as follows:

In general, there are n maxterms (M0,M1,M2, . .. , Mn-1) for p variables, where n = 2p .

From Table Above, we can write the MAXTERM expansion for a general function of 3 variables as follows:

Note that if ai=1, ai +Mi=1, and Mi drops out of the expansion; however,Mi is present if ai=0. This equation is the Product-of-Maxterms which forms the CANNONICAL POS.

For example, let us consider again the following truth table: where the Function f as expressed in minterms is

f = A'B' + AB' + AB

We are now going to consider using the Maxterms to get the Boolean function f. One can determine the function f by taking the logical product (ANDing) of the sum terms (Maxterms) for which f is 0. Therefore, f = A + B'

SInce there is only one Maxterm or Sum Term, we cannot form any Logical Product of Sum Terms or POS. Comparing the Boolean functions derived from using the Minterms and Maxterms we have the following expressions.

Derived using the Minterms or the SOP, we have f = A'B' + AB' + AB

Derived using the Maxterms or the POS, we have f = A + B'

Take NOTE, that these 2 expressions are equivalent and both described the same LOGIC Circuit.

We can prove that they are equivalent by simplifying f = A'B' + AB' + AB

f = A'B' + AB' + AB <--- Minterms (SOP)

A'B' + AB' + AB' + AB

B' (A' + A) + A (B' + B)

A + B' <--- Maxterms (POS)

Below shows how to get or form the Minterms and Maxterms for 2 variables from a Truth Table.

Below shows how to get or form the Minterms and Maxterms for 3 variables from a Truth Table.

If you examine carefully the Minterm and its Corresponding Maxterm, you will find out that they are complements with one another. Let us consider 2 variables A and B and the Table above and let us verify and check these.

m0 = M0' or A'B' = ( A + B )' m0' = M0 or (A'B')' = A + B

m1 = M1' or A'B = ( A + B' )' m1' = M1 or (A'B)' = A + B

m2 = M2' or AB' = ( A' + B )' m2' = M2 or (AB')' = A' + B

m3 = M3' or AB = ( A' + B' )' m3' = M3 or (AB)' = A' + B'

They are all indeed complement with one another as can be proven using the De Morgan's Theorem. That is, a Minterm is the complement of its corresponding Maxterm and vice versa.

Let us have another example of proving Minterm complement is equal to its corresponding Maxterm.

Consider the Truth Table below.

f = m0 = A'B'

f' = m1 + m2 + m3 = A'B + AB' + AB

Let us compute for the complement of f' which is (f')' or f.

f = (f ')' = ( m1 + m2 + m3 )' = (A'B + AB' + AB )'

= m1' . m2' . m3' = (A'B)' (AB')' (AB)'

= (A + B') (A' + B) (A' + B')

= M1 M2 M3

From the above, we can see that m1' . m2' . m3' = M1 M2 M3. Since m1' = M1, m2' = M2 and m3' = M3.

From this example we can see that we can get the Boolean expression of a function from the Truth Table by forming the SOP using the Minterms or the POS using the Maxterms. And also that the complement of a Minterm is its corresponding Maxterm and vice versa.

Using the Product-of-Maxterms equation,

We can get the minterm expansion for the complement of the function or F'

Note that all minterms which are not present in F are present in F'.

While using the Sum-of-Minterms equation, we can get the maxterm expansion for F'

Note that all maxterms which are not present in F are present in F'.

.

Product of Sum format (POS)

If a Boolean expression consists in the ANDing of terms that are ORed as shown in the function below;

f = (A + B' + C') (A + B' + C) (A + B+ C').

ILLUSTRATIONS in FORMING SOP & POS

Let us consider the following Truth Table and get the Boolean Expression in the form of SOP (Sum of Product or Sum of Minterms) and POS (Product of Sum or Product of Maxterms).

Take note that the corresponding Minterms and Maxterms complement each other.

We can now form the SOP by summing all the Minterms where the function f is 1 and the POS by taking the Product of all the Maxterms where the function f is 0.

The function f above is f = A + BC', This can be verified by applying the Truth Table.

Conversion between Canonical Forms

From the above example, it may be noted that the complement of a function expressed as the sum of products (SOP) equals to the sum of products or sum of the minterms which are missing from the original function. This is because the original function is expressed by those minterms that make the function equal to 1, while its complement is for those minterms whose values are 0.

F (A,B,C) = Σm( 2,4,5,6,7)

= m2 + m4 + m5 + m6 + m7

= A'BC' + AB'C' + AB'C + ABC' + ABC

This has the complement that can be expressed as

F′ (A,B,C) = Σm(0,1,3)

= m0 + m1 + m3

= A'B'C' + A'B'C + AB'C'

Now, if we take complement of F′ by DeMorgan’s theorem, we obtain F as

F (A,B,C) = (m0 + m1 + m3 )′

= m0′m1′m3′

= M0M1M3

= πm(0,1,3)

= (A + B + C)(A + B + C′) (A + B′ + C′)

This example demonstrates the conversion between a function expressed in sum of products (SOP) and its equivalent in product of sums (POS). A similar example can show the conversion between the product of sums (POS) and its equivalent sum of products. In general,

to convert from one canonical form to other canonical form, it is required to interchange the symbols Σ and π, and list the numbers which are missing from the original form.

Note: From the minterm/maxterm expansion we get the SOP ( consisting of minterms for all F = 1) and POS ( consisting of maxterms for all F = 0) from the same TRUTH TABLE. And that their Boolean Expressions Are derived from the same Logic Circuit.

This is different from taking the SOP of the Complement of the Function, where we take the SOP of the Function F', where the minterms in the complement of the Function F' are those minterms that are not present in the Original Function F.

REVIEW:

BASIC PROCEDURES in FORMING SOP & POS

SUM OF PRODUCTS (SOP)

This form of a Boolean expression can be developed from a given Truth Table by using the following procedure.

1) Inspect the Truth Table for each output of a 1.

2) For each output of a 1, make a Product Term of each input variable, complementing those with a 0 value.

Do this for every input combinations of the entire Truth Table.

3) Lastly, write the Boolean expression that is the SUM of all the Product Terms.

PRODUCT OF SUM (POS)

This form of a Boolean expression can be developed from a given Truth Table by using the following procedure.

1) Inspect the Truth Table for each output of a 0.

2) For each output of a 0, make a SUM Term of each input variable, complementing those with a 1 value.

Do this for every input combinations of the entire Truth Table.

3) Lastly, write the Boolean expression that is the PRODUCT of all the SUM TERMS.

Canonical and Standard and NonStandard Form.

When a Boolean Expression is reduced, the equation that is left over will be one of the following standard forms;

A) sum-of-prodructs (SOP) or B) product-of-sum (POS).

Product Term. In Boolean algebra, the logical product of several variables on which a function depends is considered to be a product term. In other words, the AND function is referred to as a product term or standard product. The variables in a product term can be either in true form or in complemented form. For example, ABC′ is a product term.

Sum Term. An OR function is referred to as a sum term. The logical sum of several variables on which a function depends is considered to be a sum term. Variables in a sum term can also be either in true form or in complemented form. For example, A + B + C′ is a sum term.

Sum of Products (SOP). The logical sum of two or more logical product terms is referred to as a sum of products expression. It is basically an OR operation on AND operated variables. For example, Y = AB + BC + AC or Y = A′B + BC + AC′ are sum of products expressions.

Product of Sums (POS). Similarly, the logical product of two or more logical sum terms is called a product of sums expression. It is an AND operation on OR operated variables. For example, Y = (A + B + C)(A + B′ + C)(A + B + C′) or Y = (A + B + C)(A′ + B′ + C′) are product of sums expressions.

Standard form. The standard form of the Boolean function is when it is expressed in sum of the products or product of the sums fashion. The examples stated above, like Y = AB + BC + AC or Y = (A + B + C)(A + B′ + C)(A + B + C′) are the standard forms.

A boolean function may also be expressed in a non standard form. In that case, distributive law can be used to remove the parenthesis.

F=(xy+zw)(x′y′+z′w′) = xyx'y' + xyz'w' + zwx'y' + zwz'w' = xyz'w' + zwx'y'

Cannonical Form - Here Boolean expression are expressed as Sum of Minterms or Product of Maxterms.

That is, in every term all variables exists either in TRUE or COMPLEMENTED form as shown below.

SOP Cannonical Form - Boolean expression expressed as Sum of Minterms.

F(x, y, z) = m3 + m5 + m6 + m7 = x' y z + x y' z + x y z' + x y z

POS Cannonical Form - Boolean expression expressed as Product of Maxterms.

F(x, y, z) = M0 • M1 • M2 • M4 = (x+y+z) • (x+y+z' ) • (x+y'+z) • (x'+y+z)

Formal descriptions (“standard forms”)

o a literal is a variable or the complement of a variable

o a product term is a single literal or a logical product of two or more literals

o a sum-of-products expression is a logical sum of product terms

o a sum term is a single literal or a logical sum of two or more literals

o a product-of-sums expression is a logical product of sum terms

o a normal term is a product or sum term in which no variable appears more than once

o an n-variable minterm is a normal product term with n literals

o an n-variable maxterm is a normal sum term with n literals

o the canonical sum of a logic function is a sum of minterms corresponding to input combinations for which the function produces a “1”

output

o the canonical product of a logic function is a product of maxterms corresponding to input combinations for which the function produces a

“0” output

NOTES on Concept of Active Logic Levels:

When an input or output line on a logic circuit symbol has no bubble on it, that line is said to be active-HIGH. When an input or output line does have a bubble on it, that line is said to be active-LOW. The presence or absence of a bubble, then, determines the active-HIGH/active-LOW status of a circuit's inputs and output, and is used to interpret the circuit operation.