Karnaugh Maps

So what is a Karnaugh map? A Karnaugh map provides a pictorial method of grouping together expressions with common factors and therefore eliminating unwanted ... KarnaughMaps Introduction RulesofSimplification Examples Problems Introduction SofarwecanseethatapplyingBooleanalgebracanbeawkwardin ordertosimplifyexpressions.Apartfrombeinglaborious(andrequiring therememberingallthelaws)themethodcanleadtosolutionswhich,though theyappearminimal,arenot. TheKarnaughmapprovidesasimpleandstraight-forwardmethodof minimisingbooleanexpressions.WiththeKarnaughmapBoolean expressionshavinguptofourandevensixvariablescanbe simplified. SowhatisaKarnaughmap? AKarnaughmapprovidesapictorialmethodofgrouping togetherexpressionswithcommonfactorsandtherefore eliminatingunwantedvariables.TheKarnaughmapcanalsobe describedasaspecialarrangementofatruthtable. Thediagrambelowillustratesthecorrespondencebetweenthe Karnaughmapandthetruthtableforthegeneralcaseofatwo variableproblem. Thevaluesinsidethesquaresarecopiedfromtheoutput columnofthetruthtable,thereforethereisonesquareinthe mapforeveryrowinthetruthtable.Aroundtheedgeofthe Karnaughmaparethevaluesofthetwoinputvariable.Ais alongthetopandBisdownthelefthandside.Thediagrambelowexplainsthis: Thevaluesaroundtheedgeofthemapcanbethoughtofas coordinates.Soasanexample,thesquareonthetoprighthand cornerofthemapintheabovediagramhascoordinatesA=1and B=0.Thissquarecorrespondstotherowinthetruthtablewhere A=1andB=0andF=1.NotethatthevalueintheFcolumnrepresentsaparticularfunctiontowhichtheKarnaughmapcorresponds. Examples Example1: Considerthefollowingmap. Thefunctionplottedis:Z=f(A,B)=A+AB Notethatvaluesoftheinputvariablesformtherows andcolumns.ThatisthelogicvaluesofthevariablesAandB(withonedenotingtrueform andzerodenotingfalseform)formtheheadoftherowsandcolumnsrespectively. Bearinmindthattheabovemapisaonedimensional typewhichcanbeusedtosimplifyanexpressionintwo variables. Thereisatwo-dimensionalmapthatcanbeusedforup tofourvariables,andathree-dimensionalmapforuptosix variables. Usingalgebraicsimplification,Z=A+AB Z=A(+B) Z=A VariableBbecomesredundantdueto BooleanTheoremT9a. Referringtothemapabove,thetwoadjacent1'sare groupedtogether.ThroughinspectionitcanbeseenthatvariableBhasitstrueand falseformwithinthegroup.ThiseliminatesvariableBleavingonlyvariableAwhich onlyhasitstrueform.TheminimisedanswerthereforeisZ=A. Example2: ConsidertheexpressionZ=f(A,B)=+A +BplottedontheKarnaughmap: Pairsof1'saregroupedasshown above,andthesimplifiedanswerisobtainedbyusingthefollowingsteps: Notethattwogroupscanbeformedfortheexamplegivenabove,bearinginmindthatthelargest rectangularclustersthatcanbemadeconsistoftwo1s.Noticethata1canbelongtomorethan onegroup. ThefirstgrouplabelledI,consistsoftwo1swhichcorrespondtoA=0,B=0andA=1,B=0. Putinanotherway,allsquaresinthisexamplethatcorrespondtotheareaofthemapwhere B=0contains1s,independentofthevalueofA.SowhenB=0theoutputis1.Theexpression oftheoutputwillcontaintheterm ForgrouplabelledIIcorrespondstotheareaofthemapwhereA=0.Thegroupcantherefore bedefinedas.ThisimpliesthatwhenA=0theoutputis1. Theoutputistherefore1wheneverB=0andA=0 HencethesimplifiedanswerisZ=+ Verifythisalgebraicallyinyournotebooks. Problems MinimisethefollowingproblemsusingtheKarnaughmapsmethod. Z=f(A,B,C)= +B+AB +AC Z=f(A,B,C)=B+B+BC+ A Clickhereforanswers. Tosubmityourquestionsandqueriespleaseclickhere: ComposedbyDavidBelton-April98