Fundamentals of Logic Design Chapter03.ppt

SLIDESFORCHAPTER3BOOLEANALGEBRA continued Clickthemousetomovetothenextpage UsetheESCkeytoexitthischapter Thischapterinthebookincludes ObjectivesStudyGuide3 1MultiplyingOutandFactoringExpressions3 2Exclusive ORandEquivalenceOperations3 3TheConsensusTheorem3 4AlgebraicSimplificationofSwitchingExpressions3 5ProvingtheValidityofanEquationProgrammedExercisesProblems DistributiveLaws Givenanexpressioninproduct of sumsform thecorrespondingsum of productsexpressioncanbeobtainedbymultiplyingout usingthetwodistributivelaws X Y Z XY XZ 3 1 X Y X Z X YZ 3 2 Inaddition thefollowingtheoremisveryusefulforfactoringandmultiplyingout X Y X Z XZ X Y 3 3 Example 3 4 p 63 Inthefollowingexample ifweweretomultiplyoutbybruteforce wewouldgenerate162terms and158ofthesetermswouldthenhavetobeeliminatedtosimplifytheexpression Instead wewillusethedistributivelawstosimplifytheprocess Thesametheoremsthatareusefulformultiplyingoutexpressionsareusefulforfactoring Byrepeatedlyapplying 3 1 3 2 and 3 3 anyexpressioncanbeconvertedtoaproduct of sumsform Exclusive ORandEquivalenceOperations Theexclusive ORoperation isdefinedasfollows Theequivalenceoperation isdefinedby Section3 2 p 64 Wewillusethefollowingsymbolforanexclusive ORgate ThefollowingtheoremsapplytoexclusiveOR Section3 2 p 65 Wewillusethefollowingsymbolforanequivalencegate Section3 2 p 66 Becauseequivalenceisthecomplementofexclusive OR analternatesymboloftheequivalencegateisanexclusive ORgatewithacomplementedoutput Theequivalencegateisalsocalledanexclusive NORgate Example1 Example2 Section3 2 p 66 By 3 6 and 3 17 F A B C A B C B AC B AC A BC A B C AB C B A C B A C A C C A B AB B A C C A B A B AB C A B AB C by 3 6 A B AB C A B AB C by 3 19 A B C ABC A BC AB C Section3 2 p 66 67 Theconsensustheoremcanbestatedasfollows XY X Z YZ XY X Z 3 20 DualForm X Y X Z Y Z X Y X Z 3 21 TheConsensusTheorem ConsensusTheoremProof XY X Z YZ XY X Z X X YZ XY XYZ X Z X YZ XY 1 Z X Z 1 Y XY X Z Section3 3 p 67 Basicmethodsforsimplifyingfunctions Section3 4 p 68 69 1 Combiningterms UsethetheoremXY XY Xtocombinetwoterms Forexample 2 Eliminatingterms UsethetheoremX XY Xtoeliminateredundanttermsifpossible thentrytoapplytheconsensustheorem XY X Z YZ XY X Z toeliminateanyconsensusterms Forexample abc d abcd abd X abd Y c 3 24 a b a bc a b X a b a bc bcd a bd a bc bcd X c Y bd Z a b 3 24 3 Eliminatingliterals UsethetheoremX X Y X Ytoeliminateredundantliterals Simplefactoringmaybenecessarybeforethetheoremisapplied A B A B C D ABCD A B B C D ABCD A B C D ABCD B A ACD A C D B A CD A C D A B BCD A C D 3 26 4 Addingredundantterms Redundanttermscanbeintroducedinseveralwayssuchasaddingxx multiplyingby x x addingyztoxy x z oraddingxytox Whenpossible theaddedtermsshouldbechosensothattheywillcombinewithoreliminateotherterms WX XY X Z WY Z addWZ byconsensustheorem WX XY X Z WY Z WZ eliminateWY Z WX XY X Z WZ eliminateWZ WX XY X Z 3 27 Example 3 28 p69 70 Thefollowingcomprehensiveexampleillustratesuseofallfourmethods ProvingValidityofanEquation Section3 5 p70 Constructatruthtableandevaluatebothsidesoftheequationforallcombinationsofvaluesofthevariables Thismethodisrathertediousifthenumberofvariablesislarge anditcertainlyisnotveryelegant Manipulateonesideoftheequationbyapplyingvarioustheoremsuntilitisidenticalwiththeotherside Reducebothsidesoftheequationindependentlytothesameexpression Oftenwewillneedtodetermineifanequationisvalidforallcombinationsofvaluesofthevariables Severalmethodscanbeusedtodetermineifanequationisvalid 4 Itispermissibletoperformthesameoperationonbothsidesoftheequationprovidedthattheoperationisreversible Forexample itisallrighttocomplementbothsidesoftheequation butitisnotpermissibletomultiplybothsidesoftheequationbythesameexpression MultiplicationisnotreversiblebecausedivisionisnotdefinedforBooleanalgebra Similarly itisnotpermissibletoaddthesametermtobothsidesoftheequationbecausesubtractionisnotdefinedforBooleanalgebra Firstreducebothsidestoasumofproducts oraproductofsums Comparethetwosidesoftheequationtoseehowtheydiffer Thentrytoaddtermstoonesideoftheequationthatarepresentontheotherside Finallytrytoeliminatetermsfromonesidethatarenotpresentontheother Toprovethatanequationisnotvalid itissufficienttoshowonecombinationofvaluesofthevariablesforwhichthetwosidesoftheequationhavedifferentvalues Whenusingmethod2or3abovetoprovethatanequationisvalid ausefulstrategyisto Whatevermethodisused frequentlycomparebothsidesoftheequationandletthedifferentbetweenthemserveasaguideforwhatstepstotakenext Example ShowthatA BD BCD ABC AB D BC D AD A BC Example1 p 71 Solution Startingwiththeleftside DifferencesbetweenBooleanalgebraandordinaryalgebra Section3 5 p72 Aswehavepreviouslyobserved someofthetheoremsofBooleanalgebraarenottrueforordinaryalgebra Similarly someofthetheoremsofordinaryalgebraarenottrueforBooleanalgebra Consider forexample thecancellationlawforordinaryalgebra Ifx y x z theny z 3 31 ThecancellationlawisnottrueforBooleanalgebra Wewilldemonstratethisbyconstructingacounterexampleinwhichx y x zbuty z Letx 1 y 0 z 1 Then 1 0 1 1but0 1 Inordinaryalgebra thecancellationlawformultiplicationisIfxy xz theny z 3 32 Thislawisvalidprovidedx 0 InBooleanalgebra thecancellationlawformultiplicationisalsonotvalidwhenx 0 Letx 0 y 0 z 1 then0 0 0 1 but0 1 Becausex 0abouthalfthetimeinswitching