It’s similar to truth table; instead of being organized

i/p and o/p) into columns and rows, the K-map is an
array of cells in which each cell represents a binary
value of the input variables.
• Thecells are arranged in a way so that simplification
of a given expression is simply a matter of properly

1. TheKarnaughMap
Er abhishek singh

2. KarnaughMaps
•Karnaughmaps(K-maps)aregraphicalrepresentations of
Booleanfunctions.
•One mapcell correspondstoa rowinthetruthtable.
•Also,onemapcell correspondstoamintermoramaxterm in
the Boolean expression
•Multiple-cellareas ofthemapcorrespond tostandardterms.
•A K-mapprovides asystematicmethodforsimplifyingBoolean
expressionsand,ifproperlyused,willproducethesimplestSOP
orPOSexpressionpossible,knownastheminimumexpression.
Erabhisheksingh

3. WhatisK-Map
•It’ssimilartotruthtable;insteadof beingorganized
(i/pando/p)intocolumnsandrows,theK-mapisan
arrayofcellsinwhicheach cellrepresentsa binary
value of theinputvariables.
•Thecellsare arrangedinaway sothatsimplification
ofagivenexpressionissimplyamatterof properly
groupingthecells.
•K-mapscanbeusedforexpressionswith2,3,4,and
5variables.
Er abhishek singh

4. Two-VariableMap
1
0
0 1
x
2
x
1
0
m
0
1
m
1
2
m
2
3
m
3
orderingofvariablesis IMPORTANTforf(x
1,x
2),x
1is
therow,x
2isthe column.
Cell0representsx
1’x
2’;Cell1representsx
1’x
2;etc.If
amintermispresentinthe function,thena1is
placedinthecorrespondingcell.
1
0
10
x
1
x
2
0
m
0
2
m
2
1
m
1
3
m
3
OR
Er abhishek singh

5. Two-VariableMap
•Anytwoadjacent cellsin themapdifferbyONLYonevariable,
whichappearscomplementedin onecell and
uncomplementedintheother.
•Example:
m
0(=x
1’x
2’)isadjacenttom
1(=x
1’x
2)andm
2(=x
1x
2’)butNOTm
3
(=x
1x
2)
Er abhishek singh

6. 2-VariableMap --Example
•f(x
1,x
2)=x
1’x
2’+x
1’x
2+x
1x
2’
=m
0+m
1+m
2
=x
1’+x
2’
•1splacedin K-map forspecifiedmintermsm
0,
m
1,m
2
•Groupingof1sallowssimplification
•What (simpler) function is represented by each
dashedrectangle?
–x
1’=m
0+m
1
–x
2’=m
0+m
2
•Herem
0coveredtwice
1
0
1
x
x
10
2
0 1
11
2
1
3
0
Er abhishek singh

7. The3VariableK-Map
•Thereare8cells asshown:
0 1
C
AB
00
01
11
10
ABCABC
ABCABC
ABCABC
ABCABC
Er abhishek singh

8. Example3var.k-map
M
_
in
_
im
_
iz
_
et
_
he f
_
ollowing equationusingk-map
y=ABC+ABC+ABC+ABC
_____
ABC=000=0
_
ABC=101=5
ABC=010=2
ABC=111=7
Usingthisfillthek-map
•Grouping–here2 groups of21’s
Ispossible
Er abhishek singh

9. For upper group A and C are
constants and B is varying.
NeglectB.AandCbothare0.
__
Henceoutputofthisgroup isAC
•For upper group A and C are
constants and B is varying.
Neglect B.A and C both are 0.
Hence outputofthis groupisAC
Thus outputYisgiven by,
__
Y=AC+AC
=A
⃝.
C
Er abhishek singh

10. 00 01 11 10
CD
AB
00
01
11
10
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
The4-VariableK-Map
Er abhishek singh

11. 00011110
CD
AB
00
01
11
10
CellAdjacency
Er abhishek singh

12. •Solvethegiven
k-map
•StepI-grouping
•StepII -outputof
eachgroup
•StepIII-finaloutput
Hereansweris,
___
Y=CD+BC+BD
Er abhishek singh

13. K-MapSOPMinimization
•TheK-MapisusedforsimplifyingBooleanexpressionstotheir
minimalform.
•A minimizedSOPexpressioncontainsthefewestpossible
terms withfewestpossiblevariablesper term.
•Generally,aminimumSOP expressioncanbe implemented
withfewerlogicgatesthanastandardexpression.
Er abhishek singh

14. Grouping
Rulesofgrouping-
1’s&0’scan
notbegrouped
diagonal 1’scan
notbegrouped
Er abhishek singh

15. Elementsinagroup shouldbe2
n
Er abhishek singh

16. Minimum
Groups
shouldbe
formed
For above
rule group
Overlapping
isapplicable
Er abhishek singh

17. Er abhishek singh

18. Mappinga Standard SOPExpression
•For anSOPexpressionin
standardform:
–A1isplacedontheK-mapforeach
producttermintheexpression.
–Each 1 is placed in a cell
corresponding to the value of a
productterm.
–Example:forthe productterm ,
a1goes inthe101cellona3-
C
0 1
AB
00
01
11
10
ABCABC
ABCABC
ABCABC
ABCABC
variable map.ABC
Er abhishek singh

19. C
AB
00
01
11
10
Mapping a Standard SOPExpression
Theexpression:
ABCABCABCABC
000 001 110 100
0 1
1 1
1
1
ABCDABCDABCDABCDABCDABCDABCD
ABCABCABC
Practice:
ABCABCABCABC
Er abhishek singh

20. Three-VariableK-Maps
f(0,4)BC f(4,5)AB f(0,1,4,5)B f(0,1,2,3)A
0
1
BC
A
00011110
1000
1000
0
1
BC
A
00011110
0000
1100
0
1
BC
A
00011110
1111
0000
0
1
BC
A
00011110
1100
1100
f(0,4)AC f(4,6)AC f(0,2)AC f(0,2,4,6)C
0
1
BC
A
00011110
0110
0000
0
1
BC
A
00011110
0000
1001
0
1
BC
A
00011110
1001
1001
0
1
BC
A
00011110
1001
0000
Er abhishek singh

21. Four-VariableK-Maps
f(0,8)BCD
f(5,13)BCD f(13,15)ABD f(4,6)ABD
f(2,3,6,7)AC f(4,6,12,14)BD f(2,3,10,11)BC f(0,2,8,10)BD
CD
000111 10
AB
00
01
11
10
1000
0000
0000
1000
CD
000111 10
AB
00
01
11
10
0000
0100
0100
0000
CD
000111 10
AB
00
01
11
10
0000
0000
0110
0000
CD
000111 10
AB
00
01
11
10
0000
1001
0000
0000
CD
000111 10
AB
00
01
11
10
0011
0011
0000
0000
CD
000111 10
AB
00
01
11
10
0000
1001
1001
0000
CD
000111 10
AB
00
01
11
10
0011
0000
0000
0011
CD
00011110
AB
00
01
11
10
1001
0000
0000
1001
Er abhishek singh

22. Four-VariableK-Maps
CD
000111 10
AB
00
01
11
10
0000
1111
0000
0000
CD
000111 10
AB
00
01
11
10
0010
0010
0010
0010
CD
000111 10
AB
00
01
11
10
1010
0101
1010
0101
CD
000111 10
AB
00
01
11
10
0101
1010
0101
1010
CD
000111 10
AB
00
01
11
10
0110
0110
0110
0110
CD
000111 10
AB
00
01
11
10
1001
1001
1001
1001
CD
000111 10
AB
00
01
11
10
0000
1111
1111
0000
CD
000111 10
AB
00
01
11
10
1111
0000
0000
1111
f (4,5,6,7)AB f(3,7,11,15)CD
f (0,3,5,6,9,10,12,15)
f ABCD
f(1,2,4,7,8,11,13,14)
f ABCD
f(1,3,5,7,9,11,13,15)
fD
f (0,2,4,6,8,10,12,14)
fD
f (4,5,6,7,12,13,14,15)
fB
f (0,1,2,3,8,9,10,11)
fB
Er abhishek singh

23. DeterminingtheMinimumSOPExpressionfromtheMap
CD
AB
00011110
00 11
011111
111111
10 1
AC
B
ACD
BACACD
Er abhishek singh

24. DeterminingtheMinimumSOPExpressionfromtheMap
ABBCABC
C
AB
0 1
1
1
1 1
00
01
11
10
0 1
C
AB
00
01
11
10
1 1
1
1
1 1
BACAC
Er abhishek singh

25. Mapping Directlyfroma TruthTable
I/P O/P
ABCX
0001
0010
0100
0110
1001
1010
1101
1111
C
AB
00
01
11
10
0 1
1
1
1
1
Er abhishek singh

26. Don’tCareConditions
•Adon’tcarecondition,markedby(X)inthetruth
table,indicatesaconditionwherethedesigndoesn’t
careiftheoutputisa(0)ora(1).
•Adon’tcareconditioncan betreatedasa (0)or a(1)
in aK-Map.
•Treatingadon’t careasa (0)meansthatyoudonot
needtogroupit.
•Treatingadon’t careasa (1)allowsyoutomakea
groupinglarger,resultinginasimplerterm intheSOP
equation.
Er abhishek singh

27. SomeYouGroup,SomeYouDon’t
0
X
1 0
0 0
X 0
CVC
AB
AB
AB
AB
AC
This don’t care condition was treated as a (1).
This allowed the grouping of a single one to
becomeagroupingoftwo,resultingina simpler
term.
Therewasnoadvantageintreatingthis
don’tcareconditionasa(1),thusitwas
treatedasa(0)andnotgrouped.
Er abhishek singh

28. Example
Solution:
FRTRS
4
R S T U F
4
0 0 0 0 X
0 0 0 1 0
0 0 1 0 1
0 0 1 1 X
0 1 0 0 0
0 1 0 1 X
0 1 1 0 X
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 X
1 1 0 0 X
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
X 0 X 1
0 X 1 X
X 0 0 0
1 1 X 1
RS
RS
RS
RS
V
TUTUTU
RT
TU
RS
Er abhishek singh

29. IMPLEMENTATIONOFK-MAPS
-Insomelogic circuits,theoutputresponses
for some input conditions are don’t care
whethertheyare1or0.
x
1dd1
d 1
InK-maps,don’t-careconditionsarerepresented
byd’sin thecorrespondingcells.
Don’t-careconditionsareusefulinminimizing
thelogicfunctionsusingK-map.
-Canbeconsideredeither1or0
-Thusincreasesthe chancesofmergingcellsintothelargercells
-->Reducethenumberofvariablesin theproductterms
yz x’
yz’
x
y
z
F
Er abhishek singh

30. K-MapPOSMinimization
•Theapproachesaremuchthe same(asSOP)exceptthatwith
POSexpression,0s representing thestandardsumtermsare
placedontheK-map insteadof 1s.
Er abhishek singh

31. C
0 1
AB
00
01
11
10
Mapping a StandardPOS Expression
Theexpression:
(ABC)(ABC)(ABC)(ABC)
000 010 110 101
0
0
0
0
Er abhishek singh

32. K-mapSimplificationofPOSExpression
(ABC)(ABC)(ABC)(ABC)(AB C)
0 1
C
AB
00
01
11
10 AB
0 0
0 0
0
AC
BC
A
1
11
A(BC)
ABAC
Er abhishek singh

33. -Sum-of-IMPLEMENTATIONOFK-MAPS
ProductsForm-
Logicfunctionrepresentedby aKarnaughmap
canbeimplementedintheform of not-AND-OR
Acelloracollectionoftheadjacent1-cellscan
be realizedbyanAND gate,withsome inversionoftheinputvariables.
x
y
x
y
’
’
’
z
x’
y
z’
x
y
z’
1 1
1
z
F(x,y,z)=(0,2,6)
1 1
1
x’
’z
y
z’

x’
y
x
y
z’
x’
y’
z’
F
x
z
y
z
F
notAND OR
z’

Er abhishek singh

34. -Product-of-IMPLEMENTATIONOFK-MAPS
SumsForm-
Logicfunctionrepresentedby aKarnaughmap
canbeimplementedintheform ofI-OR-AND
IfweimplementaKarnaughmapusing0-cells,
thecomplementofF,i.e., F’,canbeobtained.
Thus, by complementing F’ using DeMorgan’s
theoremF canbeobtained
F(x,y,z)=(0,2,6)
x
y
zx
y’
z
F’=xy’+z
F=(xy’)z’
=(x’+y)z’
x
y
z
F
IOR AND
001 1
0001
Er abhishek singh

35. Designofcombinationaldigitalcircuits
•Stepstodesigna combinationaldigitalcircuit:
–Fromtheproblemstatementderivethetruthtable
–Fromthetruthtablederivetheunsimplifiedlogic
expression
–Simplifythe logic expression
–Fromthesimplifiedexpressiondrawthelogiccircuit
Er abhishek singh

36. Example:Designa3-input(A,B,C)digitalcircuitthatwillgiveatitsoutput
(X)alogic1onlyifthebinarynumberformedattheinputhasmoreones
thanzeros.
XACABBC
A
Inputs
BC
Output
X
0000 0
1001 0
2010 0
3011 1
4100 0
5101 1
6110 1
7111 1
BC
0
1
00011110
A
0010
0111
A B C
X
X(3,5,6,7)
Er abhishek singh

37. XACABABC
A B C
X
X(2,3,4,5,6,7,8,9)A
Inputs
BCD
Output
X
00000 0
10001 0
20010 1
30011 1
40100 1
50101 1
60110 1
70111 1
81000 1
91001 1
101010 0
111011 0
121100 0
131101 0
141110 0
151111 0
D
CD
00 01 1110
00
01
11
10
AB
0011
1111
0000
1100
X
Same
Example:Designa4-input(A,B,C,D)digitalcircuitthatwillgiveat
itsoutput(X)alogic1onlyifthebinarynumberformedatthe
inputisbetween2and9(including).
Er abhishek singh