Boolean switching algebra
Chapter 2
Karnaugh maps
00 01 11 10
0
1
0
1
2
3
6
7
4
5
AB
C
MSB
LSB
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
000 001 011 010
ABC
DE
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=E
100 101 111 110
ABC
DE
00
01
11
10
16 20 28 24
17 21 29 25
19 23 31 27
18 22 30 26
MSB=A ; LSB=E
It is a matrix of squares,each
square represent a minterm or
maxterm from a Boolean
equation,
N-variable karnaugh map have 2n
squares.
The binary numeral on the sides
of k-map is the variable
coordinates,
By decoding the binary coordinates,We label
the decimal value for each square,
00 01 11 10
0
1
0
1
2
3
6
7
4
5
AB
C
MSB
LSB
The decimal number is
the subscript of the
relative minterm or
maxterm,
So a direct connection
can be made between
the minterm or maxterm
equation list and the
appropriate square in
karnaugh map.
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
The squares correspond to the adjacent
minterms are adjacent squares.
Across the top and down the side of k- map,only
one bit changes occur between adjacent squares
for each column and row
Logically adjacent
Adjacent
Symmetrical
(0,8,2,4)
(1,3,9,11)
stack
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
Describe a switching
function
by
K-map
F(A,B,C,D)=∑m(1,3,5,12,13,14,15)
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
Writing 1 in the
square correspond
to a minterm.
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
0
0
0
0 0
0
0
0
Writing 0 in the
square correspond
to a maxterm.
Simplify a equation
use
N-variable K-map
Boolean Identity AB+AB’=A
A sum of 2 logically adjacent m-
minterms can be simplified by
eliminating one variable,which is
the different literal in the two
minterms,
The resulting product term has
m-1 literals.
Boolean Identity AB+AB’=A
All minterm groups must occur in a
power of 2,2n,n is the number of
variables to be eliminated by the
group,
The resulting product term have
m-n literals,which are the common
variables to all minterms
m1=A’B’C’D,m3=A’B’CD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
Common literals
A’,B’,D
m1+m2=A’B’ D
m=4,n=1
m-1=3
m1=A’B’C’D,m9=AB’C’D
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1 1
Common literals:
B’,C’,D
m1+m9=B’C’D
m=4,n=1
m-1=3
m0=A’B’C’D’,m1=A’B’C’D
m2=A’B’CD’,m3=A’B’CD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
m0+m1=A’B’C’
m2+m3=A’B’C
Common literals
A’,B’
m0+m1+m2+m3=A’B’
m=4,n=2
m -n =2
m1=A’B’C’D,m3=A’B’CD
m9=AB’C’D,m11=AB’CD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
m1+m3=A’B’D
m9+m11=AB’D
m1+m3+m9+m11=B’D
m=4,n=2
m -n =2
m1=A’B’C’D,m3=A’B’CD
m9=AB’C’D,m11=AB’CD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
Common literals
B’,D
m1+m3+m9+m11=B’D
m=4,n=2
m -n =2
m0=A’B’C’D’,m2=A’B’CD’
m8=AB’C’D’,m10=AB’CD’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
Common literals
B’ & D’
m0+m2+m8+m9=B’D’
m=4,n=2
m -n =2
1
1
m0=A’B’C’D’,m1=A’B’C’D,m2=A’B’CD’,m3=A’B’CD
m4=A’BC’D’,m5=A’BC’D,m6=A’BCD’,m7=A’BCD
m0+m1+m2+m3=A’B’
m4+m5+m6+m7=A’B
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
A’B’+A’B=A’
m=4,n=3
m -n =1
m0=A’B’C’D’,m1=A’B’C’D,m2=A’B’CD’,m3=A’B’CD
m4=A’BC’D’,m5=A’BC’D,m6=A’BCD’,m7=A’BCD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
m=4,n=3
m -n =1
Common literals
A’
(0,1,2,3,4,5,6,7)= A’∑ m
m1=A’B’C’D,m3=A’B’CD,m9=AB’C’D,m11=AB’CD
m4=A’BC’D’,m12=ABC’D’,m6=A’BCD’,m14=ABCD’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
m1+m3+m9+m11=B’D
m4+m12+m6+m14=BD’
m0=A’B’C’D’,m1=A’B’C’D,m2=A’B’CD’,m3=A’B’CD
m4=A’BC’D’,m5=A’BC’D,m6=A’BCD’,m7=A’BCD
m8=AB’C’D’,m9=AB’C’D,m10=AB’CD’,m11=AB’CD
m12=A’BC’D’,m13=A’BC’D,m14=A’BCD’,m15=A’BCD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
Common literals
A’
(0,1,2,3,4,5,6,7)= A’∑ m
1
1
1
1
1
1
1
1Common literals
A
(8,9,10,11,12,13,14,15)= A∑ m
(0--15)= A+A’=1∑ m m=4,n=4
m -n =0
m0=A’B’C’D’,m1=A’B’C’D,m2=A’B’CD’,m3=A’B’CD
m4=A’BC’D’,m5=A’BC’D,m6=A’BCD’,m7=A’BCD
m8=AB’C’D’,m9=AB’C’D,m10=AB’CD’,m11=AB’CD
m12=A’BC’D’,m13=A’BC’D,m14=A’BCD’,m15=A’BCD
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
12
=∑
－
i=0 i
n
m
Boolean Identity AB+AB’=A
All minterm groups must occur in a
power of 2,2n,n is the number of
variables to be eliminated by the
group,
The resulting product term have
m-n literals,which are the common
variables to all minterms
Any single minterm or permitted group of
minterms is called an implicant of output
equation,The group size should be an integer
power of 2.
A prime implicant is a group of minterms that
cannot be covered by any other implicant.
Essential prime implicant(EPI) is a prime
implicant that contains one or more minterms
that are unique; that is,terms not contained in
any other prime implicant.
A set of 2n k-map squares are combined to form
a prime implicant,if n-variables of the equation
being simplified have 2n permutations within the
set and the remaining m-n variables have the
same value within the set,The result product
term has m-n literal.
In other words 2n k-map squares may be
combined to form a group of minterms contain
m-n literals,where m represents the number of
variables in the original equation.
Step of simplification
Load the minterms into the k-map by placing a
1 in the appropriate square
Look for all prime implicants
Look for all essential prime implicants
Select all EPI and a minimal set of remaining
implicants that cover all remaining 1s in the
karnaugh map
More than one equally simplified result is
possible when more than one set of remaining
prime implicants contain the same number of
minterms
Examples
F(A,B,C,D)=∑m(1,3,5,12,13,14,15)
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
PI:
PI1(1,3)
PI2(1,5)
PI3(5,13)
PI4(12,13,14,15)
F(A,B,C,D)=∑m(1,3,5,12,13,14,15)
EPI:
PI1,PI4
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
PI:
PI1(1,3)=A’B’D
PI2(1,5)=A’C’D
PI3(5,13)=BC’D
PI4(12,13,14,15)=AB
F(A,B,C,D)=∑m(1,3,5,12,13,14,15)
F=A’B’D+AB+BC’D
=A’B’D+AB+A’C’D
Minimal cover:
EPI+PI2={PI1,PI4,PI2}
EPI+PI3={PI1,PI4,PI3}
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
PI:
PI1(1,3),PI2(1,5)
PI3(5,13)
PI4(12,13,14,15)
EPI:
PI1,PI4
The number of square-groups
is the least.
The size of each square-group
is the biggest.
F(A,B,C,D)=∑m(0,1,2,3,5,7,8,10)
Simplest SOP
Simplest POS
F(A,B,C,D)=∑m(0,1,2,3,5,7,8,10)
Simplest SOP
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1?F=A’D+B’D’
F(A,B,C,D)=∑m(0,1,2,3,5,7,8,10)
Simplest POS
F ’=∑m(4,6,9,11,12,13,14,15)
2n -1∑
i=0
mi =1
F+F’=1
F(A,B,C,D)=∑m(0,1,2,3,5,7,8,10)
Simplest POS
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
F ’=∑m(4,6,9,11,12,13,14,15)
F’ =AD+BD’
F=(F’)’
=(AD+BD’)’=(A’+D’)(B’+D)
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
Simplest SOP
Simplest POS
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
Simplest SOP
Simplest POS
F(A,B,C,D)’=∏M(0,1,4,6,8,9,12,13)
∏
2n -1
i=0
Mi =0
FF’=0
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
Simplest SOP
Simplest POS
(F(A,B,C,D)’) ’=(∏M(0,1,4,6,8,9,12,13))’
=∑m(0,1,4,6,8,9,12,13)
=F
F(A,B,C,D)’=∏M(0,1,4,6,8,9,12,13)
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
Simplest SOP
F =∑m(0,1,4,6,8,9,12,13)
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1 F =A’BD’+B’C’+C’D’+AC’
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
Simplest POS
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1 1
1
1
1
B’C
CD
A’BD
AC
F =∑m(0,1,4,6,8,9,12,13)
F’=∑m(2,3,5,7,10,11,14,15)
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1 1
1
1
1
B’C
CD
A’BD
AC
F’=∑m(2,3,5,7,10,11,14,15)
= A’BD+ AC+ B’C +CD
F =(C’+D)(A’+C’)(A+B’+D’)(B+C’)
F(A,B,C,D)=∏M(2,3,5,7,10,11,14,15)
Simplest POS
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
0
0
0
0 0
0
0
0
B+C’
F =(C’+D)(A’+C’)(A+B’+D’)(B+C’)
C’+D’
A+B’+D’
A’+C’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
AC
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
BC
F=(AB+BC+CA)’+ABC’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
AB
1
1
1
1
1
1
1
1
F=(AB+BC+CA)’+ABC’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
AB
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
AC 1
1
1
1
1
1
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
BC
1
1
1
1
1
1
+AC+BC
F=(AB+BC+CA)’+ABC’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
AB
1
1
1
1
+AC+BC
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
(AB+BC+CA)’
F=(AB+BC+CA)’+ABC’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
(AB+BC+CA)’
00 01 11 10ABCD
00
01
11
10
0 4 12 8
1 5 13 9
3 7 15 11
2 6 14 10
MSB=A ; LSB=D
1
1
1
1
1
1
1
1
1
1
(AB+BC+CA)’+ABC’
F=C’+A’B’
HOMEWORK
Chapter2
21,24i,27b,29a
Chapter3
10c,14a