Digital Electronics and Logic Design Lecture Note

Chapter Four
Standard Boolean Expressions and Simplification
Canonical form (Minterns and Maxterms)
A binary variable may appear either in its normal form or in its complement form. Consider two
binary variables x and y combined with AND operation. Since each variable may appears in either
form there are four possible combinations: x′y′, x′y, xy′, xy. Each of the term represent one
distinct minterm or a standard product. With n variable, 2n minterms can be formed. In a
similar fashion, n variables forming an OR term provide 2n possible combinations called
maxterms or standard sum. Each maxterm is obtained from an OR term of the n variables, with
each variable being primed if the corresponding bit is 1 and un-primed if the corresponding bit is
0. Note that each maxterm is the complement of its corresponding minterm and vice versa.

A Boolean function may be expressed algebraically from a given truth table by forming a
minterm for each combination of variable that produce a 1 and taken the OR of those terms.
Similarly, the same function can be obtained by forming the maxterm for each combination of
variable that produces 0 and then taken the AND of those term.

dec x y z Minterms Maxterms

0 0 0 0 X’Y’Z’=m0 X+Y+Z
1 0 0 1 X’Y’Z=m1 X+Y+Z’
2 0 1 0 X’YZ’=m2 X+Y’+Z
3 0 1 1 X’YZ=m3 X+Y’+Z’
4 1 0 0 XY’Z’=m4 X’+Y+Z
5 1 0 1 XY’Z=m5 X’+Y+Z’
6 1 1 0 XYZ’=m6 X’+Y’+Z
7 1 1 1 XYZ=m7 X’+Y’+Z’

It is sometime convenient to express the Boolean function when it is in sum of minterms, in the
following notation:
F(X,Y,Z)=Σ(1,4,5,6,7)
The summation symbol Σ stands for the ORing of the terms; the numbers following it are the
minterms of the function. The letters in the parenthesis following F form list of the variables in
the order taken when the minterm is converted to an AND term.
So, F(x,y,z)= Σ (1,4,5,6,7) = x’y’z+ xy’z’+ xy’z+ xyz’+ xyz

1
 Digital Electronics and Logic Design Lecture Note

Sometime it is convenient to express a Boolean function in its sum of minterm. If it is not in that
case, the expression is expanded into the sum of AND term and if there is any missing variable, it
is ANDed with an expression such as x+x′ where x is one of the missing variables.
✓ Example1: express the Boolean function F = A + B'C as a sum of mintem.
Ans:-F = A'B'C + AB'C + AB'C + ABC' + ABC
= ml + m4 + m5 + rn6 + m7
To express a Boolean function as a product of maxterms, it must first be brought into a form of
OR terms. This can be done by using distributive law x+yz=(x+y)(x+z) then if there is any
missing variable, say x in each OR term is ORded with xx′.
✓ Example2: Express the Boolean function F = xy + x'z as a product of maxterms. First,
convert the function into OR terms by using the distributive law:
• F = xy + x'z = (xy + x’)(xy + z)
• = (x + x')(y+ x')(x + z)(y + z)
• = (x' + y)(x + z)(y + z)
The function has three variables: x, y, and z each OR term is missing one variable; therefore

Combining all the terms and removing those which appear more than once, we finally obtain

xyz|f
---------
000|0
001|0
010|1
011|0
100|1
101|0
110|0
111|1

Since you can describe any combinatorial circuit with a truth table, and you can describe any truth
table with an expression, you can describe any combinatorial circuit with an expression.

2
 Digital Electronics and Logic Design Lecture Note

Simplicity of logic expressions

There are many logic expressions (and therefore many circuits) that correspond to a certain truth
table, and therefore to a certain function computed. For instance, the following two expressions
compute the same function: x(y+z) =xy+xz. The left one requires two gates, one AND-GATE and
one OR-GATE. The second expression requires two AND-GATES and one OR-GATE. It seems
obvious that the first one is preferable to the second one. However, this is not always the case. It
is not always true that the number of gates is the only way, nor even the best way, to determine
simplicity. We have, for instance, assumed that gates are ideal. In reality, the signal takes some
time to propagate through a gate. We call this time the gate delay. We might be interested in circuits
that minimize the total gate delay, in other words, circuits that make the signal traverse the fewest
possible gates from input to output. Such circuits are not necessarily the same ones that require the
smallest number of gates.

Gate Circuit minimization

The complexity of the digital logic gates that implement a Boolean function is directly related to
the complexity of the algebraic expression from which the function is implemented. Although the
truth table representation of a function is unique, it can appear in many different forms when
expressed algebraically.

Simplification through algebraic manipulation

A Boolean equation can be reduced to a minimal number of literal by algebraic manipulation as
stated above. Unfortunately, there are no specific rules to follow that will guarantee the final
answer. The only methods is to use the theorem and postulate of Boolean algebra and any other
manipulation that becomes familiar

e.g.

• Simplify x+x′y
▪ x+x′y=(x+x′)(x+y)
▪ =x+y

• Simplify x′y′z+x′yz+xy′
▪ x′y′z+x′yz+xy′=x′z(y+y′)+xy′
o =x′z+xy′
• Simplify xy +x′z+yz
▪ xy +x′z+yz= xy +x′z+yz(x+x′)

3
 Digital Electronics and Logic Design Lecture Note

o =xy +x′z+yzx+yzx′ xy(1+z) +x′z(1+y)

o =xy+x′z

Karnaugh map
The Karnaugh map also known as Veitch diagram or simply as K map is a two dimensional form
of the truth table, drawn in such a way that the simplification of Boolean expression can be
immediately be seen from the location of 1’s in the map. The map is a diagram made up of squares,
each square represent one minterm. Since any Boolean function can be expressed as a sum of
minterms, it follows that a Boolean function is recognized graphically in the map from the area
enclosed by those squares whose minterms are included in the function.

Determining the Minimum SOP Expression from the Map

When all the 1s representing the standard product terms in an expression are properly mapped and
grouped, the process of determining the resulting minimum SOP expression begins. The following
rules are applied to find the minimum product terms and the minimum SOP expression:
1. Group the cells that have 1s. Each group of cells containing 1s creates one product term
composed of all variables that occur in only one form (either uncomplemented or
complemented) within the group. Variables that occur both uncomplemented and
complemented within the group are eliminated. These are called contradictory variables.
2. Determine the minimum product term for each group.
(a) For a 3-variable map:
(1) A 1-cell group yields a 3-variable product term
(2) A 2-cell group yields a 2-variable product term
(3) A 4-cell group yields a 1-variable term
(4) An 8-cell group yields a value of 1 for the expression
(b) For a 4-variable map:
(1) A 1-cell group yields a 4-variable product term
(2) A 2-cell group yields a 3-variable product term
(3) A 4-cell group yields a 2-variable product term
(4) An 8-cell group yields a 1-variable term
(5) A 16-cell group yields a value of 1 for the expression
3. When all the minimum product terms are derived from the Karnaugh map, they are
summed to form the minimum SOP expression.

The 2-Variable Karnaugh Map

A two variable Boolean function can be represented as follow

4
 Digital Electronics and Logic Design Lecture Note

Example 1. F(x,y)= Σ(1,2,3)=m1+m2+m3=x’y+xy’+xy , when simplified using K map.

F(x,y)=x+y
The 3-Variable Karnaugh Map
The 3-variable Karnaugh map is an array of eight cells, as shown in figure below (a). In this case,
A, B, and C are used for the variables although other letters could be used. Binary values of A and
B are along the left side (notice the sequence) and the values of C-are across the top.
A three variable function can be represented as follow

5
 Digital Electronics and Logic Design Lecture Note

Example 1. F(x,y,z)=Σ(3,4,6,7)= X’YZ+ XY’Z’+ XYZ’+ XYZ

Example 2. F(x,y,z)=Σ(0,2,4,5,6)= X’Y’Z’+ X’YZ’+ XY’Z’+ XY’Z+ XYZ’

6
 Digital Electronics and Logic Design Lecture Note

Exercise 1.
Use a Karnaugh map to find the minimum SOP form for each expression and draw a logic circuit diagram
for the simplified version.
A. A’ B’ C’ + A’ B’C + AB’C
B. AC(B’ + C)
C. A’(BC + BC’) + A(BC + BC’)
D. A’B’C’ + AB’C’ + A’BC’ + ABC’
The 4-Variable Karnaugh Map
A four variable Boolean function can be represented in the map bellow

EXAMPLE 4–

7
 Digital Electronics and Logic Design Lecture Note

Determine the product terms for the Karnaugh map in Figure below and write the resulting
minimum SOP expression.

8
 Digital Electronics and Logic Design Lecture Note

9
 Digital Electronics and Logic Design Lecture Note

Don’t Care” Conditions

10
 Digital Electronics and Logic Design Lecture Note

Exercise 2.

1. Determine the truth table and draw the logic circuit diagram after simplifying.

11
 Digital Electronics and Logic Design Lecture Note

2. Determine the function expression for the following truth table.

a. Simplify the function
b. Draw the logic circuit diagram for the simplified.

12