计算机中的布尔逻辑课件

计算机中的布尔逻辑BooleanLogicABooleanvariable,A,iseithertrueorfalseABooleanexpression,(AANDB),evaluatestoeithertrueorfalseBooleanoperatorsinclude:AND(&

•)OR(+)NOT(abar'¬~)

BooleanOperatorsaANDbtrueonlywhenAandBarebothtrueaORbtruewhenAistrue,Bistrue,orbotharetrueNOTatruewhenAisfalseTruthTablesTruthtablescanbeusedtocapturewhenanexpressionistrue,givenitsinputsabaANDb001011101111YoumaketruthtablesforANDandNOTExampleBooleanExpressions(aANDb)OR(NOTaANDc)a·b+~a·cab+ācTruthtablescanbemadeforcomplexexpressionsaswellabValue001010100111Example:

(aANDb)OR((NOTb)and(NOTa))BooleanLogic(continued)GatesGatesHardwaredevicesbuiltfromtransistorstomimicBooleanlogicAnelectronicdevicethatoperatesonacollectionofbinaryinputstoproduceasinglebinaryoutputANDgate(page161intext)Twoinputlines,oneoutputlineOutputsa1whenbothinputsare1Gates(continued)ORgate(page163intext)Twoinputlines,oneoutputlineOutputsa1wheneitherinputis1NOTgate(page161intextOneinputline,oneoutputlineOutputsa1wheninputis0andviceversaFigure4.15TheThreeBasicGatesandTheirSymbolsCircuitsAcollectionoflogicgatesthattransformsasetofbinaryinputsintoasetofbinaryoutputsWiregatestogetherkeepingconstraintsforthenumberofinputstoanygateExampleCircuitIfa,b,c,anddarealltruetheoutputcanbedeterminedbytracingthroughthecircuit

ab

cdoutput11111100DesigningCircuitsAcircuitconstructionalgorithmTruthTableConstructionDetermineoutputsforeverypossibleinputSub-expressionConstruction(usingANDandNOTgates)Foreachoutputfindtherowsthatare1andbuildasub-expressionthatistruefortheexactinputSub-expressioncombination(usingORgates)Takeeachsubexpressionandcombinethem,2atatime,usingORgatesCircuitDiagramProductionConstructfinalcircuitbyconvertingBooleanoperatorsintogatesExampleCircuitDesignDesigna3-inputcircuitthatistrueifexactlytwoinputsaretrue,andfalseotherwiseYouTryit:Designa2-inputcircuitthatistrueiftheinputsarethesame,andfalseotherwiseExamplesofCircuitDesignandConstructionCompare-for-equalitycircuitAdditioncircuitBothcircuitscanbebuiltusingthecircuitdesignalgorithmCEcomparestwounsignedbinaryintegersforequalityBuiltbycombiningtogether1-bitcomparisoncircuits(1-CE)Integersareequalifcorrespondingbitsareequal(ANDtogether1-CDcircuitsforeachpairofbits)ACompare-for-EqualityCircuit1-CEcircuittruthtableabOutput001010100111ACompare-for-EqualityCircuit(continued)1-CEBooleanexpressionFirstcase:(NOTa)AND(NOTb)Secondcase:aANDbCombined:((NOTa)AND(NOTb))OR(aANDb)ACompare-for-EqualityCircuit(continued)Figure4.22One-BitCompare-for-EqualityCircuitN-BitCompareforEqualityCircuitANDtogetherthe1-CEcircuits,twoatatimeAnAdditionCircuitAddstwounsignedbinaryintegers,settingoutputbitsandanoverflowBuiltfrom1-bitadders(1-ADD)Startingwithrightmostbits,eachpairproducesAvalueforthatorderAcarrybitfornextplacetotheleft1-ADDtruthtableInputOnebitfromeachinputintegerOnecarrybit(alwayszeroforrightmostbit)OutputOnebitforoutputplacevalueOnecarrybitAnAdditionCircuit(continued)Figure4.24The1-ADDCircuitandTruthTableBuildingthefulladderPutrightmostbitsinto1-ADD,withzeroforth