BOOLEAN ALGEBRA

BOOLEAN VALUES
INTRODUCTION

• Boolean algebra is a form of algebra that deals with single digit binary
values and variables.
• Values and variables can indicate some of the following binary pairs of
values:
• ON / OFF
• TRUE / FALSE
• HIGH / LOW
• CLOSED / OPEN
• 1/0
 BOOL. OPERATIONS
FUNDAMENTAL OPERATORS

• Three fundamental operators in Boolean algebra

• NOT: unary operator that complements represented as A , A , or  A

• AND: binary operator which performs logical multiplication
• i.e. A ANDed with B would be represented as AB or A  B
• OR: binary operator which performs logical addition
• i.e. A ORed with B would be represented as A + B
NOT AND OR
A A A B AB A B A +B

0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
 BOOL. OPERATIONS
BINARY BOOLEAN OPERATORS

• Below is a table showing all possible Boolean functions FN given the two-

inputs A and B.

A B F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

0 AB A B A +B B A AB 1
Null A B A B Identity
Inhibition A +B Implication
 BOOLEAN ALGEBRA
PRECEDENCE OF OPERATORS

• Boolean expressions must be evaluated with the following order of operator

precedence

• parentheses
• NOT Example:
• AND
F = AC + BD +BCE
• OR
 BOOLEAN ALGEBRA
FUNCTION EVALUATION

• Example 1:
Evaluate the following expression when A = 1 , B = 0 , C = 1
F = C + CB + BA

• Solution
F = 1 + 1  0 + 0 1 = 1 + 0+ 0 = 1
• Example 2:
Evaluate the following expression when A = 0 , B = 0 , C = 1 , D = 1
F = DBCA + AB + C + C
• Solution
F = 1  0  1  0 + 0  0 + 1 + 1 = 1  0 + 1 + 1 = 1  1 = 1
 BOOLEAN ALGEBRA
BASIC IDENTITIES

X +0 = X X 1 = X Identity
X +1 = 1 X 0 = 0
X +X = X X X = X Idempotent Law
X + X= 1 X  X= 0 Complement
X= X Involution Law
X+Y = Y +X XY = YX Commutativity
X + Y + Z = X + Y + Z XYZ = XYZ Associativity
XY + Z = XY + XZ X + YZ = X + YX +Z Distributivity
X + XY = X XX + Y = X Absorption Law
X + XY = X+Y XX+ Y = XY Simplification
X + Y= XY XY= X+Y DeMorgan’s Law
XY + XZ+ YZ X + YX+ ZY + Z Consensus Theorem
= XY + XZ =  X+ YX+ Z
 BOOLEAN ALGEBRA
DUALITY PRINCIPLE

• Duality principle:
• States that a Boolean equation remains valid if we take the dual of the
expressions on both sides of the equals sign.
• The dual can be found by interchanging the AND and OR operators
along with also interchanging the 0’s and 1’s.
• This is evident with the duals in the basic identities.
• For instance: DeMorgan’s Law can be expressed in two forms

X + Y= XY as well as XY= X+Y

 BOOLEAN ALGEBRA
FUNCTION MANIPULATION (1)

• Example: Simplify the following expression

F = BC + BC + BA

• Simplification

F = BC + C + BA

F = B  1 + BA

F = B1 + A

F = B
 BOOLEAN ALGEBRA
FUNCTION MANIPULATION (2)

• Example: Simplify the following expression

F = A + AB + ABC + ABCD + ABCDE

• Simplification
F = A + AB + BC + BCD + BCDE
F = A + B + BC + BCD + BCDE
F = A + B + BC + CD + CDE
F = A + B + C + CD + CDE
F = A + B + C + CD + DE
F = A + B + C + D + DE
F=A+B+C+D+ E
 BOOLEAN ALGEBRA
FUNCTION MANIPULATION (3)

• Example: Show that the following equality holds

ABC + BC = A + B + CB + C

• Simplification

ABC + BC = A + BC + BC

= A + BCBC

= A + B + CB + C
 STANDARD FORMS
SOP AND POS

• Boolean expressions can be manipulated into many forms.

• Some standardized forms are required for Boolean expressions to simplify
communication of the expressions.
• Sum-of-products (SOP)
• Example:

FA B C D = AB + BCD + AD

• Products-of-sums (POS)
• Example:

FA B C D = A + BB + C + DA + D

 Minterm

A product term containing all the k variables in either complemented or

uncomplemented form is called minterm
 STANDARD FORMS
MINTERMS

• The following table gives the minterms for a three-input system

m0 m1 m2 m3 m4 m5 m6 m7
A B C ABC ABC ABC ABC ABC ABC ABC ABC
0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 1 0 0 0
1 0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 1 0
1 1 1 0 0 0 0 0 0 0 1
 STANDARD FORMS
SUM OF MINTERMS

• Sum-of-minterms standard form expresses the Boolean or switching

expression in the form of a sum of products using minterms.

• For instance, the following Boolean expression using minterms

FA B C = ABC + ABC + ABC + ABC

could instead be expressed as

FA B C = m0 + m1 + m4 + m5

or more compactly

FA B C = m 0 1 4 5 = one-set0 1 4 5

 STANDARD FORMS
MAXTERMS

• The following table gives the maxterms for a three-input system

M0 M1 M2 M3 M4 M5 M6 M7

A + B +C A + B +C A + B +C A + B +C
A B C A +B+ C A+ B+ C A +B+ C A+B+C
0 0 0 0 1 1 1 1 1 1 1
0 0 1 1 0 1 1 1 1 1 1
0 1 0 1 1 0 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 1
1 0 0 1 1 1 1 0 1 1 1
1 0 1 1 1 1 1 1 0 1 1
1 1 0 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 0
 STANDARD FORMS
PRODUCT OF MAXTERMS

• Product-of-maxterms standard form expresses the Boolean or switching

expression in the form of product of sums using maxterms.

• For instance, the following Boolean expression using maxterms

FA B C = A + B + CA + B + CA + B + C

could instead be expressed as

FA B C = M1  M4  M7

or more compactly as

FA B C =  M 1 4 7 = zero-set1 4 7

 STANDARD FORMS
MINTERM AND MAXTERM EXP.

• Given an arbitrary Boolean function, such as

FA B C = AB + BA + C

how do we form the canonical form for:

• sum-of-minterms
• Expand the Boolean function into a sum of products. Then take
each term with a missing variable X and AND it with X + X .
• product-of-maxterms
• Expand the Boolean function into a product of sums. Then take
each factor with a missing variable X and OR it with XX.
 STANDARD FORMS
FORMING SUM OF MINTERMS

• Example
FA B C = AB + BA + C = AB + AB + BC
= ABC + C + ABC + C + A + ABC
= ABC + ABC + ABC + ABC + ABC
= m 0 1 4 6 7

A B C F
0 0 0 1 0
0 0 1 1 1
0 1 0 0
Minterms listed as
0 1 1 0 1s in Truth Table
1 0 0 1 4
1 0 1 0
1 1 0 1 6
1 1 1 1 7
 STANDARD FORMS
FORMING PROD OF MAXTERMS

• Example
FA B C = AB + BA + C = AB + AB + BC
= A + BA + B + CA + B + C (using distributivity)

= A + B + CCA + B + CA + B + C
= A + B + CA + B + CA + B + C
=  M 2 3 5
A B C F
0 0 0 1
0 0 1 1 Maxterms listed as
0 1 0 0 2 0s in Truth Table
0 1 1 0 3
1 0 0 1
1 0 1 0 5
1 1 0 1
1 1 1 1
 STANDARD FORMS
CONVERTING MIN AND MAX

• Converting between sum-of-minterms and product-of-maxterms

• The two are complementary, as seen by the truth tables.

• To convert interchange the  and  , then use missing terms.

• Example: The example from the previous slides

FA B C = m 0 1 4 6 7

is re-expressed as

FA B C =  M 2 3 5

where the numbers 2, 3, and 5 were missing from the minterm

representation.
 KARNAUGH MAPS

• Often it is desired to simplify a Boolean function. A quick graphical

approach is to use Karnaugh maps.

Properties
The maps are considered to be “rolled” or continuous, so that top and bottom
edges or left and right side edges are touching. For the three-variable map,
considers the left side edge and the right side edges are touching.
 SIMPLIFICATION
KARNAUGH MAPS

• Often it is desired to simplify a Boolean function. A quick graphical

approach is to use Karnaugh maps.

2-variable 3-variable 4-variable

Karnaugh map Karnaugh map Karnaugh map
CD
AB 00 01 11 10
BC 00 0 1 0 0
B
A 0 1 A 00 01 11 10 01 0 1 0 0
0 0 0 0 0 1 1 0 11 1 1 1 1
1 0 1 1 0 1 1 1 10 0 1 0 0

F = AB F = AB + C F = AB + CD
 SIMPLIFICATION
KARNAUGH MAP ORDERING

• Notice that the ordering of cells in the map are such that moving from one
cell to an adjacent cell only changes one variable.

2-variable 3-variable 4-variable

Karnaugh map Karnaugh map Karnaugh map
CD D D D
AB 00 01 11 10
BC C C C 00 0 1 3 2 B
B A
A 0 1 A 00 01 11 10 01 4 5 7 6
B
0 0 1 A 0 0 1 3 2 A 11 12 13 15 14
A
1 2 3 A 1 4 5 7 6 A 10 8 9 11 10 B
B B B B C C

• This ordering allows for grouping of minterms/maxterms for simplification.

 SIMPLIFICATION
IMPLICANTS

• Implicant
• Bubble covering only 1s (size of bubble
must be a power of 2). CD
• Prime implicant AB 00 01 11 10
• Bubble that is expanded as big as possible
00 1 1 0 0
(but increases in size by powers of 2).
• Essential prime implicant 01 0 0 1 0
• Bubble that contains a 1 covered only by 11 0 1 1 1
itself and no other prime implicant bubble.
10 1 1 0 0
• Non-essential prime implicant
• A 1 that can be bubbled by more then one
prime implicant bubble.
 SIMPLIFICATION
PROCEDURE FOR SOP

• Procedure for finding the SOP from a Karnaugh map

• Step 1: Form the 2-, 3-, or 4-variable Karnaugh map as appropriate for
the Boolean function.
• Step 2: Identify all essential prime implicants for 1s in the Karnaugh map
• Step 3: Identify non-essential prime implicants for 1s in the Karnaugh
map.
• Step 4: For each essential and one selected non-essential prime
implicant from each set, determine the corresponding product term.
• Step 5: Form a sum-of-products with all product terms from previous
step.
 SIMPLIFICATION
EXAMPLE FOR SOP (1)

• Simplify the following Boolean function

FA B C =  m 0 1 4 5 = ABC + ABC + ABC + ABC

• Solution:
BC
A 00 01 11 10
zero-set2 3 6 7
0 1 1 0 0 one-set0 1 4 5
1 1 1 0 0

• The essential prime implicants are B .

• There are no non-essential prime implicants.
• The sum-of-products solution is F = B .
 SIMPLIFICATION
EXAMPLE FOR SOP (2)

• Simplify the following Boolean function

FA B C = m 0 1 4 6 7 = ABC + ABC + ABC + ABC + ABC

• Solution:
BC
A 00 01 11 10
zero-set2, 3, 5
0 1 1 0 0
one-set0 1 4 6 7
1 1 0 1 1

• The essential prime implicants are AB and AB .

• The non-essential prime implicants are BC or AC .
• The sum-of-products solution is
F = AB + AB + BC or F = AB + AB + AC .
 SIMPLIFICATION
PROCEDURE FOR POS

• Procedure for finding the SOP from a Karnaugh map

• Step 1: Form the 2-, 3-, or 4-variable Karnaugh map as appropriate for
the Boolean function.
• Step 2: Identify all essential prime implicants for 0s in the Karnaugh map
• Step 3: Identify non-essential prime implicants for 0s in the Karnaugh
map.
• Step 4: For each essential and one selected non-essential prime
implicant from each set, determine the corresponding sum term.
• Step 5: Form a product-of-sums with all sum terms from previous step.
 SIMPLIFICATION
EXAMPLE FOR POS (1)

• Simplify the following Boolean function

FA B C =  M 2 3 5 = A + B + CA + B + CA + B + C

• Solution:
BC
A 00 01 11 10
zero-set2, 3, 5
0 1 1 0 0
one-set0 1 4 6 7
1 1 0 1 1

• The essential prime implicants are A + B + C and A + B .

• There are no non-essential prime implicants.
• The product-of-sums solution is F = A + BA + B+ C.
 SIMPLIFICATION
EXAMPLE FOR POS (2)

• Simplify the following Boolean function

FA B C =  M 0 1 5 7 8 9 15
• Solution:
• The essential prime implicants zero-set0 1 5 7 8 9 15
one-set2 3 4 6 10 11 12 13 14
are B + C and B + C + D .
• The non-essential prime implicants CD
AB 00 01 11 10
can be A + B + D or A + C + D .
00 0 0 1 1
• The product-of-sums solution can be either
01 1 0 0 1
F = B + CB + C + DA + B + D
11 1 1 0 1
or
10 0 0 1 1
F = B + CB + C + DA + C + D
 SIMPLIFICATION
DON’T-CARE CONDITION

• Switching expressions are sometimes given as incomplete, or with don’t-

care conditions.
• Having don’t-care conditions can simplify Boolean expressions and
hence simplify the circuit implementation.
• Along with the zero-set  and one-set  , we will also have dc .
• Don’t-cares conditions in Karnaugh maps
• Don’t-cares will be expressed as an “X” or “-” in Karnaugh maps.
• Don’t-cares can be bubbled along with the 1s or 0s depending on
what is more convenient and help simplify the resulting expressions.
 SIMPLIFICATION
DON’T-CARE EXAMPLE (1)

• Find the SOP simplification for the following Karnaugh map

CD
AB 00 01 11 10 zero-set0 1 5 7 8 9 15
00 0 0 1 1 one-set2 3 4 6 11 12
01 1 0 0 1 dc10 13 14

11 1 X 0 X
Taken
to be 0 10 0 0 1 X Taken
to be 1

• Solution:

• The essential prime implicants are BD and BC .

• There are no non-essential prime implicants.
• The sum-of-products solution is F = BC + BD .
 SIMPLIFICATION
DON’T-CARE EXAMPLE (2)

• Find the POS simplification for the following Karnaugh map

CD
AB zero-set0 1 5 7 8 9 15
00 01 11 10
one-set2 3 4 6 11 12
00 0 0 1 1
dc10 13 14
01 1 0 0 1

Taken 11 1 X 0 X
10 0 0 1 X Taken
to be 0
to be 1

• Solution:

• The essential prime implicants are B + C and B + D .

• There are no non-essential prime implicants.
• The product-of-sums solution is F = B + CB +D.