Chapter 4 Boolean Algebra and Logic Simplification
Standard Forms of Boolean Expressions:
All Boolean expressions can be converted into one of two forms:
- Sum-of-products form (SOP)
- Product-of-sums form (POS)
The purpose of such standardization into SOP or POS forms is to make evaluation,
simplification and implementation processes much more easier
Sum-of-Products Form (SOP):
Recall that a product term is a product (Boolean multiplication) of literals
When two or more product terms are summed by Boolean addition the resulting
expression is a sum-of-products (SOP)
Some examples are:
Note: in SOP expression a single over bar cannot extend over more than one variable
The Domain of a Boolean expression:
- is the set of variables contained in the expression in either complemented or
uncomplemented form
- For example: the domain of the expression is the set of
variables: A B C D E
AND/OR implementation of SOP expressions:
- The implementation of SOP expressions is performed through AND-OR logic
- Each product term is implemented as AND gate
- The number of AND gates is equal to the number of product terms
- Then all the outputs of AND gates are ORed into a single OR gate
- For example: the SOP expressions is implemented as
NAND/Negative-OR implementation of SOP expressions:
1
Chapter 4 Boolean Algebra and Logic Simplification
- It is possible to implement SOP expressions using NAND gates and Negative-OR
gate.
- Recall that double negation cancel each other so is the double bubbles
Conversion of general expressions into SOP form:
- By applying Boolean algebra techniques any Boolean expression can be converted
into SOP form
___________________________________________________________________________
Example 4.7:
___________________________________________________________________________
The Standard SOP Forms:
- Standard SOP form Is a SOP form where all the variables from the domain appear
in each term of the expression
- Any SOP expression can be converted into standard SOP expression through
Boolean algebra techniques
Converting product terms into Standard SOP:
- Each product term that doesn’t contain all the variables in the domain is
expanded to contain the messing variables using the rule ( )
o Step 1: multiply each nonstandard product term by a term made of the sum
of missing variable and its complement (recall that you can multiply
anything by 1 without changing its value)
o Step 2: repeat step 1 until all resulting terms contain all variables in the
domain in either complemented or uncomplemented form
2
Chapter 4 Boolean Algebra and Logic Simplification
___________________________________________________________________________
Example 4.8:
___________________________________________________________________________
Binary Representation of a Standard SOP Term:
- A standard product term is equal to 1 for only one combination of variable values.
And it is equal to 0 for all other combinations of variable values
- For example the term is only equal to one for the values :
A=1 B=0 C=1 D=0
Thus = =1.1.1.1 =1
- In this case the product term has the binary value of 1010
- An SOP expression is equal to 1 if one or more of its term equal to 1
___________________________________________________________________________
Example 4.9:
3
Chapter 4 Boolean Algebra and Logic Simplification
___________________________________________________________________________
The Product-of-Sums Form (POS):
Recall that a sum term is a term consisting of a sum (Boolean addition) of literals
When two or more sum terms are multiplied the resulting expression is a product-of-
sums (POS)
Some examples are:
Note: in POS expressions a single over bar cannot extend over more than one
variable
OR/AND implementation of POS expressions:
- The implementation of POS expressions is performed through OR-AND logic
- Each sum term is implemented as OR gate
- The number of OR gates is equal to the number of sum terms
- Then all the outputs of OR gates are ANDed into a single AND gate
- For example: the POS expressions is implemented as
4
Chapter 4 Boolean Algebra and Logic Simplification
The Standard SOP Forms:
- Standard POS form Is a POS form where all the variables from the domain appear
in each term of the expression
- Any POS expression can be converted into standard POS expression through
Boolean algebra techniques
Converting sum terms into Standard POS term:
- Each sum term that doesn’t contain all the variables in the domain is expanded to
contain the messing variables using the rule ( )
o Step 1: add to each nonstandard sum term a term made of the product of
missing variable and its complement (recall that you can add 0 to anything
without changing its value)
o Step 2: apply the rule
o Step 3: repeat step 1 until all resulting sum terms contain all variables in the
domain in either complemented or uncomplemented form
___________________________________________________________________________
Example 4.10:
___________________________________________________________________________
5
Chapter 4 Boolean Algebra and Logic Simplification
Binary Representation of a Standard POS Term:
- A standard sum term is equal to 0 for only one combination of variable values.
And it is equal to 1 for all other combinations of values
- For example the term is only equal to 0 for the values :
A=0 B=1 C=0 D=1
Thus = =0.1.0.1 =0
- In this case the sum term has the binary value of 0101
An POS expression is equal to 0 if one or more of its sum terms equal to 0
___________________________________________________________________________
Example 4.11:
___________________________________________________________________________
Converting Standard SOP to Standard POS:
- The binary values of the product terms in a given standard SOP expression are not
present in the equivalent standard POS expression
- Also, the binary values that are not represented in in the SOP expression are
present in the equivalent POS expression
- So to convert from standard SOP to standard POS:
o Step 1: evaluate each product term in SOP expression (that is determine the
binary number that represent the product term)
o Step 2: determine all the binary numbers not included in the evaluation is
step 1
o Step 3: write the equivalent sum term for each binary number from step 2
and express in POS form
- Using similar procedure we can go from POS to SOP
6
Chapter 4 Boolean Algebra and Logic Simplification
___________________________________________________________________________
Example 4.12:
___________________________________________________________________________
Boolean Expressions and Truth Tables:
Converting SOP Expression to Truth Table Format:
- First of all list all the possible input variable combination
- Convert SOP to standard SOP
- Recall that SOP expression is equal to 1 if at least one of its product terms is equal
to 1
- Place 1 in the output column for each input value that makes the standard SOP
expression equal to 1
- Place 0 in the output column for the remaining input combination values
___________________________________________________________________________
Example 4.13:
Develop truth table for the expression:
7
Chapter 4 Boolean Algebra and Logic Simplification
___________________________________________________________________________
Converting POS Expressions to Truth Table:
First of all list all the possible input variable combination
Convert POS to standard POS
Recall that POS expression is equal to 0 if at least one of its sum terms is equal to 0
Place 0 in the output column for each input value that makes the standard SOP
expression equal to 0
Place 1 in the output column for the remaining input combination values
___________________________________________________________________________
Example 4.14:
8
Chapter 4 Boolean Algebra and Logic Simplification
___________________________________________________________________________
Determining a Standard SOP Expression From a Truth Table:
- List the binary values of input combinations for which the output is 1
- For each such input combination a product term would generated
- In each input combination:
o replace each 1 with its corresponding variable
o replace each 0 with the complement of its corresponding variable
- finally, separate between the generated product terms by Boolean addition
Determining a Standard POS Expression From a Truth Table:
- List the binary values of input combinations for which the output is 0
- For each such input combination a sum term would be generated
- In each input combination:
o Replace each 0 with its corresponding variable
o replace each 1 with the complement of its corresponding variable
- finally, separate between the generated sum terms by Boolean multiplication
___________________________________________________________________________
Example 4.15:
9
Chapter 4 Boolean Algebra and Logic Simplification
___________________________________________________________________________
10
