SRI RAMAKRISHNA INSTITUTE OF TECHNOLOGY, COIMBATORE-10

(An Autonomous Institution)

(Approved by AICTE, New Delhi and permanently Affiliated to Anna University, Chennai)

SIMPLIFICATION OF BOOLEAN EXPRESSION

Ms.R.Gayathri,
Assistant Professor (Sr.Gr.)/ECE
 Boolean Algebra Summary

• Interpret high or low voltage as representing true or false.

• A variable whose value can be either 1 or 0 is called a Boolean
variable.

• AND, OR, and NOT are the basic Boolean operations.

• Express Boolean functions with either an expression or a truth table.
• Every Boolean expression can be converted to a circuit.
• Boolean algebra can help simplify expressions, which in turn
will lead to simpler circuits.

2
 Boolean Algebra Summary
• Recall that the two binary values have different names:
– True/False
– On/Off
– Yes/No
– 1/0
• Use 1 and 0 to denote the two values.
• The three basic logical operations are:
– AND
– OR
– NOT
• AND is denoted by a dot (·).
• OR is denoted by a plus (+).
• NOT is denoted by an overbar ( ¯ ), a single quote mark (') after, or (~)
before the variable
 Boolean Algebra Summary
• Examples:
– is read “Y is equal to A AND B.”
– is read “z is equal to x OR y.”
– is read “X is equal to NOT A.”

Tabular listing of the values of a function for all possible

combinations of values on its arguments
Example: Truth tables for the basic logic operations:

AND OR NOT
X Y Z = X·Y X Y Z = X+Y X Z 
0 0 0 0 0 0 X
0 1 0 0 1 1 0 1
1 0 0 1 0 1 1 0
1 1 1 1 1 1
 Boolean Operator Precedence
• The order of evaluation is:

• Parentheses
• NOT
• AND
• OR

• Consequence: Parentheses appear around OR expressions

• Example: F = A(B + C)(C + D)

 Boolean Algebra Postulates
• Commutative Law
x•y=y•x x+y=y+x

• Identity Element
x•1=x x+0=x
x’1 = x ’ x’+ 0 = x ’

• Complement
x • x’ = 0 x + x’ = 1
 Boolean Algebra Theorems
Theorem 1
– x•x=x x+x=x

• Theorem 2
– x•0 x+1=1
=0
• Theorem 3: Involution
– ( x’ )’ = x (x)=x
 Boolean Algebra Theorems
• Theorem 4:
– Associative: (x•y)•z=x•(y•z)
(x+y)+z=x+(y+z)
– Distributive :
x•(y+z)=(x•y)+(x•z)
x+(y•z)=(x+y)•(x+z)

• Theorem 5: DeMorgan
– ( x • y )’ = x’ + ( x + y )’ = x’ • y’
–x•y) =x +y
y’ (x+y) = x•y
• Theorem 6: Absorption
– x•(x+y)=x
x+(x•y)=x
 Truth Table to Verify DeMorgan’s

X + Y =X·Y X · Y = X + Y
X Y X·Y X+Y X Y X+Y X · Y X·Y X+Y
0 0 0 0 1 1 1 1 1 1
0 1 0 1 1 0 0 0 1 1
1 0 0 1 0 1 0 0 1 1
1 1 1 1 0 0 0 0 0 0
• Generalized DeMorgan’s Theorem:
X1 + X2 + … + X n = X1 · X2 · … · Xn
X1 · X 2 · … · X n = X1 + X 2 + … + X n
 Logic Gates

• In the earliest computers, switches were opened and closed by magnetic

fields produced by energizing coils in relays. The switches in turn
opened and closed the current paths.

• Later, vacuum tubes that open and close current paths electronically
replaced relays.

• Today, transistors are used as electronic switches that open and close
current paths.
 Logic Gate Symbols

• Logic gates have special symbols:

X X
Z= X·Y Z=X+Y X Z= X

Y AND gate Y OR gate NOT gate or

inverter
 Boolean Functions
• A Boolean function is a function whose arguments, as well as the function itself,
assume values from a two-element set ({0, 1)}).
• Example: F(x, y) = x ’ y ’ + xyz + x’y

• After finding the circuit inputs and outputs, you can come up with either an
expression or a truth table to describe what the circuit does.
• You can easily convert between expressions and truth tables.
Find the circuit’s
inputs and outputs

Find a Boolean Find a truth table

expression for for the circuit
the circuit
 Boolean Functions
x y z F
• Boolean Expression/Function
0 0 0 0
Example: F (x, y) = x + y’ z
0 0 1 1
• Truth Table
0 1 0 0
All possible combinations of input variables
0 1 1 0
1 0 0 1
Logic Circuit
1 0 1 1
x F 1 1 0 1
y
1 1 1 1
z
 Logic Diagrams and Expressions
Truth Table Logic Equation/Boolean Function
X Y Z
F  X  Y ×Z
0 0 0 0
F X Y Z
0 0 1 1
0 1 0 0
X Logic Circuit
0 1 1 0
1 0 0 1
Y F
1 0 1 1
1 1 0 1 Z
1 1 1 1

• Boolean equations, truth tables and logic diagrams

• describe the same function!
Truth tables are unique, but expressions and logic diagrams are not. This
gives flexibility in implementing functions.
 Boolean Functions Exercise

• The truth table for the function:

F (X, Y, Z ) = X Y + Y Z
Draw the logic circuit for the boolean function above.
X Y Z XY Y YZ F=XY+YZ
is:
0 0 0 0 1 0 0
0 0 1 0 1 1 1
0 1 0 0 0 0 0
0 1 1 0 0 0 0
1 0 0 0 1 0 0
1 0 1 0 1 1 1
1 1 0 1 0 0 1
1 1 1 1 0 0 1
 Converting from Truth Table to Boolean
Function
• In designing digital circuits, the designer often begins with a truth table
describing what the circuit should do.

• The design task is largely to determine what type of circuit will perform the
function described in the truth table.

• While some people seem to have a natural ability to look at a truth table and
immediately envision the necessary logic gate or relay logic circuitry for the task,
there are procedural techniques available for the rest of us.

• Here, Boolean algebra proves its utility in a most dramatic way!

 Converting from Truth Table to Boolean
Function

• This problem will be solved by showing that any Boolean function can be
represented by a Boolean sum of Boolean products of the variables and their
complements or the product of sums.
• There are two ways to convert from truth tables to Boolean functions:
1. Using Sum of Products /Minterms
2. Using Product of Sums /Maxterms
 Converting from Truth Table to
Boolean Function
• Minterm A B Minterm
– Product (AND function) C
– Contains all variables 0 0 0 m0 ABC
0
– Evaluates to ‘1’ for a specific
1 0 0 m1 ABC
combination 1
Example 2 0 1 m2 ABC
A B C 0
A=0 (0) • (0) • (0) 3 0 1 m3 ABC
1
B=0 4 1 0 m4 ABC
C=0 1 • 1 • 1= 0
1
5 1 0 m5 ABC
1
 Converting from Truth Table to
Boolean Function
• Maxterm A B Maxterm
– Sum (OR function) C
– Contains all variables 0 0 0 M0 A B 
0 C
– Evaluates to ‘0’ for a specific
1 0 0 M1 A  B 
combination
1 C
Example
2 0 1 M2 A  B 
A B C 0 C
A=1 (1) • (1) • (1) 3 0 1 M3 A  B 
B=1 1 C
C=1 0 • 0 • 0= 4 1 0 M4 A  B 
0 0 C
 Converting from Truth Table to Boolean Function

• Truth Table to Boolean Function

A B C F
F  ABC  ABC
0 0 0 0
0 0 1 1  ABC  ABC
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
Using Minterms
 Converting from Truth Table to Boolean Function

• Truth Table to Boolean Function

F  ( A  B  C) ( A  B  C ) ( A  B  C ) ( A  B 
A B CC) F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0 Using Maxterms
 Converting from Truth Table to Boolean Function

• Sum of Minterms A B
C
F F

F  ABC  ABC  ABC  ABC 0 0 0 0 1

F  m1  m4  m5  m7 0
1 0 0 1 0
F   1
•Product
( 1 , 4 , 5 , 7of
) Maxterms 2 0 1 0 1
0
F  ABC  ABC  ABC  ABC
3 0 1 0 1
F  ABC  ABC  ABC  ABC 1
F  A B C  ABC  ABC  ABC 4 1 0 1 0
0
F  ( A  B  C)( A  B  C)( A  B  C)( AB
 C) 5 1 0 1 0
1
F  M 0 M 2 M 3 M 6
6 1 1 0 1
NAND & NOR IMPLEMENTATION
Two-level Logic using NAND Gates
• Replace minterm AND gates with NAND gates
• Place compensating inversion at inputs of OR
gate
Two-level Logic using NAND Gates (cont’d)
• OR gate with inverted inputs is a NAND gate
– de Morgan's: A' + B' = (A • B)'
• Two-level NAND-NAND network
– Inverted inputs are not counted
– In a typical circuit, inversion is done once and
signal distributed
 Two-level Logic using NOR Gates
• Replace maxterm OR gates with NOR gates
• Place compensating inversion at inputs of AND
gate
 Two-level Logic using NOR Gates (cont’d)

• AND gate with inverted inputs is a NOR gate

– de Morgan's: A' • B' = (A + B)'
• Two-level NOR-NOR network
– Inverted inputs are not counted
– In a typical circuit, inversion is done once and
signal distributed
Two-level Logic using NAND and NOR Gates
• NAND-NAND and NOR-NOR networks
– de Morgan's law: (A + B)' = A' • B'
(A • B)' = A' + B'
– written differently: A + B = (A' • B')’
(A • B) = (A' + B')'
• In other words ––
– OR is the same as NAND with complemented inputs
– AND is the same as NOR with complemented inputs
– NAND is the same as OR with complemented inputs
– NOR is the same as AND with complemented inputs
OR OR AND AND

NAND NAND NOR NOR

 Conversion Between Forms
• Convert from networks of ANDs and ORs to networks of
NANDs and NORs
– Introduce appropriate inversions ("bubbles")
• Each introduced "bubble" must be matched by a
corresponding "bubble"
– Conservation of inversions
– Do not alter logic function
• Example: AND/OR to NAND/NAND
A A
NAND
B B
Z NAND Z
C C
NAND
D D
 Conversion Between Forms (cont’d)

• Example: verify equivalence of two forms

A A
NAND
B B
Z NAND Z
C C
NAND
D D

Z = [ (A • B)' • (C • D)' ]'

= [ (A' + B') • (C' + D') ]'
= [ (A' + B')' + (C' + D')' ]
= (A • B) + (C • D) ü
 Conversion Between Forms (cont’d)

• Example: map AND/OR network to NOR/NOR

network A

B
Z
C
D

A \A
NOR NOR
\B
B
Z NOR Z
C
\C
D NOR NOR
\D

Step 1 Step 2
conserve conserve
"bubbles" "bubbles"
 Conversion Between Forms (cont’d)

• Example: verify equivalence of two forms

\A
A NOR
\B
B
Z
C NOR Z

D \C
NOR
\D

Z = { [ (A' + B')' + (C' + D')' ]' }'

={ (A' + B') • (C' + D') }'
= (A' + B')' + (C' + D')'
= (A • B) + (C • D) ü
Karnaugh Maps (K maps)
 What are Karnaugh maps?

• Karnaugh maps provide an alternative way of simplifying logic circuits.

• Instead of using Boolean algebra simplification techniques, you can

transfer logic values from a Boolean statement or a truth table into a
Karnaugh map.
• The arrangement of 0's and 1's within the map helps you to visualize the
logic relationships between the variables and leads directly to a simplified
Boolean statement.
 Karnaugh maps

• Karnaugh maps, or K-maps, are often used to simplify logic problems with 2,
3 or 4 variables.

Cell = 2n ,where n is a number of variables

For the case of 2 variables, we form a map consisting of 22=4 cells as shown
in Figure
A A A
0 1 0 1 0 1
B B B
0 A B A  B 0 00 10 0 AB AB
0 2
01 11
1 A B A  B 1
1 3
1
A B AB
Maxterm Minterm
 Karnaugh maps

• 3 variables Karnaugh map

Cell = 23=8

AB
C 00 01 11 10
0 2 6 4
0 A B C A BC ABC AB C
1 3 7 5
1 A B C A BC ABC AB C
 Karnaugh maps

• 4 variables Karnaugh map

AB
CD 00 01 11 10
0 4 12 8
00
1 5 13 9
01
3 7 15 11
11

2 6 14 10
10
 Karnaugh maps

• The Karnaugh map is completed by entering a '1‘(or ‘0’) in

each of the appropriate cells.
• Within the map, adjacent cells containing 1's (or 0’s) are
grouped together in twos, fours, or eights.
 Example

2-variable Karnaugh maps are trivial but can be used to introduce the
methods you need to learn. The map for a 2-input OR gate looks like this:
A
0 1
B
A
Y 0 1
B
A
1 1 1
A B Y
0 0 0
B
0 1 1
1 0 1
A+B
1 1 1
 Example

AC
A B C Y
0 0 0 1 AB
0 0 1 1 C 00 01 11 10
0 1 0 0 0 1 1 1
0 1 1 0
1 0 0 1 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0 B
B  AC
Plotting Functions on the
K-map

SOP Form
 Canonical SOP Form

Three Variable Example

F  ABC  ABC  ABC  ABC

using shorthand notation
F  m6  m3  m1  m5

F  A, B, C    m 1,3,5, 6 
Three-Variable K-Map Example
Plot 1’s (minterms) of switching function

ab
c 00 01 11 10

0 1

1 1 1 1

F  a, b, c    m 1,3,5, 6 
Three-Variable K-Map Example
Plot 1’s (minterms) of switching function

ab
c 00 01 11 10
ab
bc
0 1

1 1 1 1

F  a, b, c   ab  bc
 Guidelines for Simplifying Functions

• Each square on a K-map of n variables has n logically adjacent squares.

(i.e. differing in exactly one variable)
• When combing squares, always group in powers of 2m , where m=0,1,2,….
• In general, grouping 2m variables eliminates m variables.
• Group as many squares as possible. This eliminates the most variables.
• Make as few groups as possible. Each group represents a separate product
term.
• cover each minterm at least once. However, it may be covered more than
once.
 Four Variable K –Map Example
• Use a K-Map to simplify the following Boolean expression

F  a, b, c, d    m  0, 2,3, 6,8,12,13,15 
 Four-variable K-Map
F  a, b, c, d    m  0, 2,3, 6,8,12,13,15 
ab
cd 00 01 11 10

00
1 1 1
01
1
11
1 1
10
1 1
 Four-variable K-Map
ab
cd 00 01 11 10

00
1 1 1
01
1
11
1 1
10
1 1
F   m  0, 2,3, 6,8,12,13,15 
 Four-variable K-Map
ab
cd 00 01 11 10

00
1 1 1
01
1
11
1 1
10
1 1
F  abd  abc  acd  abd  acd
 Example
• Use a K-Map to simplify the following Boolean expression

F  a, b, c, d    m  0, 2, 6,8,12,13,15 
 d 3,9,10 
D=Don’t care (i.e. either 1 or 0)
 Four-variable K-Map
ab
cd 00 01 11 10

00
1 d 1 1
01
1 d
11
d 1
10
1 1
F  a, b, c, d    m 0, 2, 6,8,12,13,15   d 3, 4,9 
 Four-variable K-Map
ab
cd 00 01 11 10

00
1 d 1 1
01
1 d
11
d 1
10
1 1

F  ac  ad  abd
Five variable K-map- F  a, b, c, d , e 

Use two four variable K-maps

A=1

A=0
Use Two Four-variable K-Maps

A=0 map A=1 map

bc bc
de 00 01 11 10 de 00 01 11 10

00 00

01 01

11 11

10 10
 Five variable example
F  a, b, c, d , e    m 5, 7,13,15, 21, 23, 29,31
Use Two Four-variable K-Maps
A=0 map A=1 map
bc bc
de 00 01 11 10 de 00 01 11 10

00 00

01
1 1 01 1 1
11
1 1
11
11
10 10

F2  a  ce 
F1  a  ce 

F  F1  F2  a  ce   a ce   ce
Plotting Functions on the
K-map

POS Form
PoS Optimization
• Maxterms are grouped to find minimal PoS
expression 00 01 yz11 10
0 x +y+z x+y+z’ x+y’+z’ x+y’+z
x
1 x’ +y+z x’+y+z’ x’+y’+z’ x’+y’+z
PoS Optimization
• F(W,X,Y,Z)= ∏ M(0,1,2,4,5)
yz
00 01 11 10

0 x +y+z x+y+z’ x+y’+z’ x+y’+z

x
1 x’ +y+z x’+y+z’ x’+y’+z’ x’+y’+z

F(W,X,Y,Z)= Y . (X + Z)
yz
00 01 11 10

0 0 0 1 0
x
1 0 0 1 1
PoS Optimization from SoP
F(W,X,Y,Z)= Σm(0,1,2,5,8,9,10)
= ∏ M(3,4,6,7,11,12,13,14,15)

F(W,X,Y,Z)= (W’ + X’)(Y’ + Z’)(X’ + Z)

0

0 0 0 Or,

0 0 0 0 F(W,X,Y,Z)= X’Y’ + X’Z’ + W’Y’Z

0 Which one is the minimal one?

SoP Optimization from PoS
F(W,X,Y,Z)= ∏ M(0,2,3,4,5,6)
= Σm(1,7,8,9,10,11,12,13,14,15)

1 F(W,X,Y,Z)= W + XYZ + X’Y’Z

1 1 1 1

1 1 1 1
Thank you