ELITE TUTORING
CHAPTER SIX
Standard Boolean Expression Formats
The development of standards is important to the computer industry
for a number of reasons. It allows independently developed systems
and subsystems to be connected, it provides reliability through well-
tested design methods, and it shortens the design time by providing off-
the-shelf tools and components for quick development.
In the design of digital systems, there are some standards that are
regularly applied to combinational logic. Over time, design tools and
programmable hardware have been developed to support these
standards allowing for quick implementation of digital logic.
This chapter outlines two standard representations of combinational
logic: Sum-of-Products and Product-of-Sums. Both of these formats
represent the fastest possible digital circuitry since, aside from a
possible inverter, all of the signals pass through exactly two layers of
logic gates. This also opens the door for the development of
programmable hardware where a single computer chip can be
programmed to handle any logic circuit.
6.1 Sum-of-Products
A sum-of-products (SOP) expression is a boolean expression in a
specific format. The term sum-of-products comes from the expression's
form: a sum (OR) of one or more products (AND). As a digital circuit,
an SOP expression takes the output of one or more AND gates and
OR's them together to create the final output.
The inputs to the AND gates are either inverted or non-inverted
input signals. This limits the number of gates that any input signal
passes through before reaching the output to an inverter, an AND gate,
and an OR gate. Since each gate causes a delay in the transition from
input to output, and since the SOP format forces all signals to go
through exactly two gates (not counting the inverters), an SOP
expression gives us predictable performance regardless of which input
in a combinational logic circuit changes.
Below is an example of an SOP expression:
_ _ _ _ _
ABCD + ABD + CD + AD
109
,ELITE TUTORING
110 Computer Organization and Design Fundamentals
There are no parentheses in an SOP expression since they would
necessitate additional levels of logic. This also means that an SOP
expression cannot have more than one variable combined in a term with
an inversion bar. The following is not an SOP expression:
__ _ _ _ _
(AB)CD + ABD + CD + AD
This is because the first term has A and B passing through a NAND
gate before being AND'ed with C and D thereby creating a third level
of logic. To fix this problem, we need to break up the NAND using
DeMorgan's Theorem.
__ _ _ _ _
(AB)CD + ABD + CD + AD
_ _ _ _ _ _
(A + B)CD + ABD + CD + AD
_ _ _ _ _ _ _
ACD + BCD + ABD + CD + AD
This expression is now considered to be in SOP format.
As far as the implementation of an SOP expression is concerned,
combinations of non-inverted and inverted signals are input to one or
more AND gates. The outputs from these gates are all input to a single
OR gate. Figure 6-1 shows a sample SOP binary circuit.
A
B
C
D
ABC + BD + CD
Figure 6-1 Sample Sum-of-Products Binary Circuit
6.2 Converting an SOP Expression to a Truth Table
Examining the truth table for an AND gate reveals that exactly one
row has a one for its output. All of the other rows have a zero output. If
we invert one of the inputs, this simply moves the row with the one
, ELITE TUTORING
Chapter 6: Standard Boolean Expression Formats 111
output to another position. There is still only one row outputting a one.
Figure 6-2 shows some examples of this behavior.
_ _ _
A B C A·B·C A B C A·B·C A B C A·B·C
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 1
0 1 1 0 0 1 1 0 0 1 1 0
1 0 0 0 1 0 0 0 1 0 0 0
1 0 1 0 1 0 1 1 1 0 1 0
1 1 0 0 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 0 1 1 1 0
Figure 6-2 Samples of Single Product (AND) Truth Tables
The output of an OR gate is a one if any of the inputs is a one.
Therefore, when the products are OR'ed together, a one appears in the
output column for each of the products. For example, if we OR'ed
together each of the products from Figure 6-2, a one would be output in
the rows corresponding to A=1, B=1, and C=1; A=1, B=0, and C=1;
and A=0, B=1, and C=0. This is shown in Figure 6-3.
_ _ _ _ _ _
A B C A·B·C A·B·C A·B·C ABC + ABC + ABC
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 1 1
0 1 1 0 0 0 0
1 0 0 0 0 0 0
1 0 1 0 1 0 1
1 1 0 0 0 0 0
1 1 1 1 0 0 1
Figure 6-3 Sample of a Sum-of-Products Truth Table
Therefore, to convert an SOP expression to a truth table, examine
each product to determine when it is equal to a one. Where that product
is a one, a one will also be outputted from the OR gate.
Each of the products in the above example contains all of the input
variables for the SOP expression. What if one of the products doesn't
do this? For example, what if an SOP expression has inputs A, B, and
C, but one of its products only depends on A and B?
CHAPTER SIX
Standard Boolean Expression Formats
The development of standards is important to the computer industry
for a number of reasons. It allows independently developed systems
and subsystems to be connected, it provides reliability through well-
tested design methods, and it shortens the design time by providing off-
the-shelf tools and components for quick development.
In the design of digital systems, there are some standards that are
regularly applied to combinational logic. Over time, design tools and
programmable hardware have been developed to support these
standards allowing for quick implementation of digital logic.
This chapter outlines two standard representations of combinational
logic: Sum-of-Products and Product-of-Sums. Both of these formats
represent the fastest possible digital circuitry since, aside from a
possible inverter, all of the signals pass through exactly two layers of
logic gates. This also opens the door for the development of
programmable hardware where a single computer chip can be
programmed to handle any logic circuit.
6.1 Sum-of-Products
A sum-of-products (SOP) expression is a boolean expression in a
specific format. The term sum-of-products comes from the expression's
form: a sum (OR) of one or more products (AND). As a digital circuit,
an SOP expression takes the output of one or more AND gates and
OR's them together to create the final output.
The inputs to the AND gates are either inverted or non-inverted
input signals. This limits the number of gates that any input signal
passes through before reaching the output to an inverter, an AND gate,
and an OR gate. Since each gate causes a delay in the transition from
input to output, and since the SOP format forces all signals to go
through exactly two gates (not counting the inverters), an SOP
expression gives us predictable performance regardless of which input
in a combinational logic circuit changes.
Below is an example of an SOP expression:
_ _ _ _ _
ABCD + ABD + CD + AD
109
,ELITE TUTORING
110 Computer Organization and Design Fundamentals
There are no parentheses in an SOP expression since they would
necessitate additional levels of logic. This also means that an SOP
expression cannot have more than one variable combined in a term with
an inversion bar. The following is not an SOP expression:
__ _ _ _ _
(AB)CD + ABD + CD + AD
This is because the first term has A and B passing through a NAND
gate before being AND'ed with C and D thereby creating a third level
of logic. To fix this problem, we need to break up the NAND using
DeMorgan's Theorem.
__ _ _ _ _
(AB)CD + ABD + CD + AD
_ _ _ _ _ _
(A + B)CD + ABD + CD + AD
_ _ _ _ _ _ _
ACD + BCD + ABD + CD + AD
This expression is now considered to be in SOP format.
As far as the implementation of an SOP expression is concerned,
combinations of non-inverted and inverted signals are input to one or
more AND gates. The outputs from these gates are all input to a single
OR gate. Figure 6-1 shows a sample SOP binary circuit.
A
B
C
D
ABC + BD + CD
Figure 6-1 Sample Sum-of-Products Binary Circuit
6.2 Converting an SOP Expression to a Truth Table
Examining the truth table for an AND gate reveals that exactly one
row has a one for its output. All of the other rows have a zero output. If
we invert one of the inputs, this simply moves the row with the one
, ELITE TUTORING
Chapter 6: Standard Boolean Expression Formats 111
output to another position. There is still only one row outputting a one.
Figure 6-2 shows some examples of this behavior.
_ _ _
A B C A·B·C A B C A·B·C A B C A·B·C
0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 1
0 1 1 0 0 1 1 0 0 1 1 0
1 0 0 0 1 0 0 0 1 0 0 0
1 0 1 0 1 0 1 1 1 0 1 0
1 1 0 0 1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 0 1 1 1 0
Figure 6-2 Samples of Single Product (AND) Truth Tables
The output of an OR gate is a one if any of the inputs is a one.
Therefore, when the products are OR'ed together, a one appears in the
output column for each of the products. For example, if we OR'ed
together each of the products from Figure 6-2, a one would be output in
the rows corresponding to A=1, B=1, and C=1; A=1, B=0, and C=1;
and A=0, B=1, and C=0. This is shown in Figure 6-3.
_ _ _ _ _ _
A B C A·B·C A·B·C A·B·C ABC + ABC + ABC
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 1 1
0 1 1 0 0 0 0
1 0 0 0 0 0 0
1 0 1 0 1 0 1
1 1 0 0 0 0 0
1 1 1 1 0 0 1
Figure 6-3 Sample of a Sum-of-Products Truth Table
Therefore, to convert an SOP expression to a truth table, examine
each product to determine when it is equal to a one. Where that product
is a one, a one will also be outputted from the OR gate.
Each of the products in the above example contains all of the input
variables for the SOP expression. What if one of the products doesn't
do this? For example, what if an SOP expression has inputs A, B, and
C, but one of its products only depends on A and B?
