Karnaugh Maps, Truth Tables, and Boolean Expressions

Now that we have developed the Karnaugh map with the aid of Venn diagrams, let's put it to use. Karnaugh maps reduce logic functions more quickly and easily ... NetworkSites: Latest News TechnicalArticles Latest Projects Education Latest News TechnicalArticles MarketInsights Education LogIn Join Login JoinAAC Orsigninwith Facebook Google LinkedIn GitHub     0:00 / 0:00 Podcast Latest Subscribe Google Spotify Apple iHeartRadio Stitcher Pandora TuneIn Menu Articles Latest News Projects TechnicalArticles IndustryArticles IndustryWhitePapers Forums Latest HardwareDesign Embedded&Programming Education Math&Science Community Education Textbooks VideoLectures&Tutorials Worksheets IndustryWebinars VirtualWorkshops Tools Calculators PartSearch TestEquipmentDatabase BomTool ICDesignCenter Videos Latest NewProducts VideoTutorials On-DemandWebinars TechChats VirtualWorkshops Datasheets Giveaways Industry Tech Days Podcast Connectwithus NetworkSites: Textbook KarnaughMaps,TruthTables,andBooleanExpressions JoinourEngineeringCommunity!Sign-inwith: Home Textbook Vol.IV-Digital KarnaughMapping KarnaughMaps,TruthTables,andBooleanExpressions PagesinChapter8 IntroductiontoKarnaughMapping VennDiagramsandSets BooleanRelationshipsonVennDiagrams MakingaVennDiagramLookLikeaKarnaughMap KarnaughMaps,TruthTables,andBooleanExpressions LogicSimplificationWithKarnaughMaps Larger4-variableKarnaughMaps MintermvsMaxtermSolution SumandProductNotation Don’tCareCellsintheKarnaughMap Larger5&6-variableKarnaughMaps KarnaughMaps,TruthTables,andBooleanExpressions Chapter8-KarnaughMapping PDFVersion WhoDevelopedtheKarnaughMap? MauriceKarnaugh,atelecommunicationsengineer,developedtheKarnaughmapatBellLabsin1953whiledesigningdigitallogicbasedtelephoneswitchingcircuits. TheUseofKarnaughMap NowthatwehavedevelopedtheKarnaughmapwiththeaidofVenndiagrams,let’sputittouse.KarnaughmapsreducelogicfunctionsmorequicklyandeasilycomparedtoBooleanalgebra.Byreducewemeansimplify,reducingthenumberofgatesandinputs. Weliketosimplifylogictoalowestcostformtosavecostsbyeliminationofcomponents.Wedefinelowestcostasbeingthelowestnumberofgateswiththelowestnumberofinputspergate. Givenachoice,moststudentsdologicsimplificationwithKarnaughmapsratherthanBooleanalgebraoncetheylearnthistool.       Weshowfiveindividualitemsabove,whicharejustdifferentwaysofrepresentingthesamething:anarbitrary2-inputdigitallogicfunction.Firstisrelayladderlogic,thenlogicgates,atruthtable,aKarnaughmap,andaBooleanequation. Thepointisthatanyoftheseareequivalent.TwoinputsAandBcantakeonvaluesofeither0or1,highorlow,openorclosed,TrueorFalse,asthecasemaybe.Thereare22=4combinationsofinputsproducinganoutput.Thisisapplicabletoallfiveexamples. Thesefouroutputsmaybeobservedonalampintherelayladderlogic,onalogicprobeonthegatediagram.Theseoutputsmayberecordedinthetruthtable,orintheKarnaughmap.LookattheKarnaughmapasbeingarearrangedtruthtable. TheOutputoftheBooleanequationmaybecomputedbythelawsofBooleanalgebraandtransferedtothetruthtableorKarnaughmap. Whichofthefiveequivalentlogicdescriptionsshouldweuse?Theonewhichismostusefulforthetasktobeaccomplished.     Theoutputsofatruthtablecorrespondonaone-to-onebasistoKarnaughmapentries.Startingatthetopofthetruthtable,theA=0,B=0inputsproduceanoutputα. NotethatthissameoutputαisfoundintheKarnaughmapattheA=0,B=0celladdress,upperleftcornerofK-mapwheretheA=0rowandB=0columnintersect.Theothertruthtableoutputsβ,χ,δfrominputsAB=01,10,11arefoundatcorrespondingK-maplocations. Below,weshowtheadjacent2-cellregionsinthe2-variableK-mapwiththeaidofpreviousrectangularVenndiagramlikeBooleanregions.     CellsαandχareadjacentintheK-mapasellipsesintheleftmostK-mapbelow.Referringtotheprevioustruthtable,thisisnotthecase.Thereisanothertruthtableentry(β)betweenthem.WhichbringsustothewholepointoftheorganizingtheK-mapintoasquarearray,cellswithanyBooleanvariablesincommonneedtobeclosetooneanothersoastopresentapatternthatjumpsoutatus. ForcellsαandχtheyhavetheBooleanvariableB’incommon.WeknowthisbecauseB=0(sameasB’)forthecolumnabovecellsαandχ.ComparethistothesquareVenndiagramabovetheK-map. AsimilarlineofreasoningshowsthatβandδhaveBooleanB(B=1)incommon.Then,αandβhaveBooleanA’(A=0)incommon.Finally,χandδhaveBooleanA(A=1)incommon.ComparethelasttwomapstothemiddlesquareVenndiagram. Tosummarize,wearelookingforcommonalityofBooleanvariablesamongcells.TheKarnaughmapisorganizedsothatwemayseethatcommonality.Let’strysomeexamples.   Examples   Example: TransferthecontentsofthetruthtabletotheKarnaughmapabove.   Solution: Thetruthtablecontainstwo1s.theK-mapmusthavebothofthem.locatethefirst1inthe2ndrowofthetruthtableabove. notethetruthtableABaddress locatethecellintheK-maphavingthesameaddress placea1inthatcell Repeattheprocessforthe1inthelastlineofthetruthtable.   Example: FortheKarnaughmapintheaboveproblem,writetheBooleanexpression.Solutionisbelow.     Solution: Lookforadjacentcells,thatis,aboveortothesideofacell.Diagonalcellsarenotadjacent.AdjacentcellswillhaveoneormoreBooleanvariablesincommon. Group(circle)thetwo1sinthecolumn Findthevariable(s)topand/orsidewhicharethesameforthegroup,WritethisastheBooleanresult.ItisBinourcase. Ignorevariable(s)whicharenotthesameforacellgroup.InourcaseAvaries,isboth1and0,ignoreBooleanA. Ignoreanyvariablenotassociatedwithcellscontaining1s.B’hasnoonesunderit.IgnoreB’ ResultOut=B ThismightbeeasiertoseebycomparingtotheVenndiagramstotheright,specificallytheBcolumn.   Example: WritetheBooleanexpressionfortheKarnaughmapbelow.     Solution:(above) Group(circle)thetwo1’sintherow Findthevariable(s)whicharethesameforthegroup,Out=A’   Example: FortheTruthtablebelow,transfertheoutputstotheKarnaugh,thenwritetheBooleanexpressionfortheresult.     Solution: Transferthe1sfromthelocationsintheTruthtabletothecorrespondinglocationsintheK-map. Group(circle)thetwo1’sinthecolumnunderB=1 Group(circle)thetwo1’sintherowrightofA=1 Writeproducttermforfirstgroup=B Writeproducttermforsecondgroup=A WriteSum-Of-ProductsofabovetwotermsOutput=A+B ThesolutionoftheK-mapinthemiddleisthesimplestorlowestcostsolution.Alessdesirablesolutionisatfarright.Aftergroupingthetwo1s,wemakethemistakeofformingagroupof1-cell.Thereasonthatthisisnotdesirableisthat: ThesinglecellhasaproducttermofAB’ ThecorrespondingsolutionisOutput=AB’+B Thisisnotthesimplestsolution   Thewaytopickupthissingle1istoformagroupoftwowiththe1totherightofitasshowninthelowerlineofthemiddleK-map,eventhoughthis1hasalreadybeenincludedinthecolumngroup(B).Weareallowedtore-usecellsinordertoformlargergroups.Infact,itisdesirablebecauseitleadstoasimplerresult. Weneedtopointoutthateitheroftheabovesolutions,OutputorWrongOutput,arelogicallycorrect.Bothcircuitsyieldthesameoutput.Itisamatteroftheformercircuitbeingthelowestcostsolution.   Example: FillintheKarnaughmapfortheBooleanexpressionbelow,thenwritetheBooleanexpressionfortheresult.     Solution:(above) TheBooleanexpressionhasthreeproductterms.Therewillbea1enteredforeachproductterm.Though,ingeneral,thenumberof1sperproducttermvarieswiththenumberofvariablesintheproducttermcomparedtothesizeoftheK-map. Theproducttermistheaddressofthecellwherethe1isentered.Thefirstproductterm,A’B,correspondstothe01cellinthemap.A1isenteredinthiscell.TheothertwoP-termsareenteredforatotalofthree1s Next,proceedwithgroupingandextractingthesimplifiedresultasintheprevioustruthtableproblem.   Example: Simplifythelogicdiagrambelow.     Solution: (Figurebelow) WritetheBooleanexpressionfortheoriginallogicdiagramasshownbelow TransfertheproducttermstotheKarnaughmap Formgroupsofcellsasinpreviousexamples WriteBooleanexpressionforgroupsasinpreviousexamples Drawsimplifiedlogicdiagram     Example:Simplifythelogicdiagrambelow.     Solution: WritetheBooleanexpressionfortheoriginallogicdiagramshownabove TransfertheproducttermstotheKarnaughmap. Itisnotpossibletoformgroups. Nosimplificationispossible;leaveitasitis. Nologicsimplificationispossiblefortheabovediagram.Thissometimeshappens.NeitherthemethodsofKarnaughmapsnorBooleanalgebracansimplifythislogicfurther. WeshowanExclusive-ORschematicsymbolabove;however,thisisnotalogicalsimplification.Itjustmakesaschematicdiagramlooknicer. SinceitisnotpossibletosimplifytheExclusive-ORlogicanditiswidelyused,itisprovidedbymanufacturersasabasicintegratedcircuit(7486).   RELATEDWORKSHEETS: KarnaughMappingWorksheet BooleanAlgebraWorksheet BasicLogicGatesWorksheet MakingaVennDiagramLookLikeaKarnaughMap TextbookIndex LogicSimplificationWithKarnaughMaps RelatedContent TheKarnaughMapBooleanAlgebraicSimplificationTechnique GrayCodeBasics EverythingAbouttheQuine-McCluskeyMethod DescribingCombinationalCircuitsinVerilog BooleanBasics PublishedunderthetermsandconditionsoftheDesignScienceLicense Comments 0Comments Logintocomment Loadmorecomments YouMayAlsoLike RFSwitchUpsPowerDensityandIntegrationfor5GNetworks byJeffChild Proposedstandardizationofchipletmodelsforheterogenousintegration bySiemensDigitalIndustriesSoftware TheGuidetoPCBADevelopmentforSemiconductorApplications byTempoAutomation EmergingTrendsinWirelessInfrastructure byRohde&Schwarz IoTCommunicationProtocols—IoTDataProtocols byIgnaciodeMendizábal WelcomeBack Don'thaveanAACaccount?Createonenow. Forgotyourpassword?Clickhere. SignIn Stayloggedin Orsigninwith Facebook Google Linkedin GitHub Continuetosite QUOTEOF THEDAY “ ” -