Transcription of CHAPTER III BOOLEAN ALGEBRA - gatech.edu
1 Dansereau; TO COMP. III-1 BOOLEAN ALGEBRA CHAPTER IIICHAPTER IIIBOOLEAN Dansereau; TO COMP. III-2 BOOLEAN VALUESINTRODUCTIONBOOLEAN ALGEBRA BOOLEAN VALUES BOOLEAN ALGEBRA is a form of ALGEBRA that deals with single digit binary values and variables. Values and variables can indicate some of the following binary pairs of values: ON / OFF TRUE / FALSE HIGH / LOW CLOSED / OPEN 1 / Dansereau; TO COMP. III-3 BOOL. OPERATIONSFUNDAMENTAL OPERATORSBOOLEAN ALGEBRA BOOLEAN VALUES-INTRODUCTION Three fundamental operators in BOOLEAN ALGEBRA NOT: unary operator that complements represented as , , or AND: binary operator which performs logical multiplication ANDed with would be represented as or OR: binary operator which performs logical addition ORed with would be represented as AA A ABABAB ABAB+AB001101010001AB001101010111A0110 AABA B+ Dansereau; TO COMP. III-4 BOOL. OPERATIONSBINARY BOOLEAN OPERATORSBOOLEAN ALGEBRA BOOLEAN OPERATIONS-FUNDAMENTAL OPER.
2 Below is a table showing all possible BOOLEAN functions given the two-inputs and .000000000011111111010000111100001111100 011001100110011110101010101010101 FNABABF0F1F2F3F4F5F6F7F8F9F10F11F12F13F1 4F1501 ABA B+AB ABAB+ABBAAB Dansereau; TO COMP. III-5 BOOLEAN ALGEBRAPRECEDENCE OF OPERATORSBOOLEAN ALGEBRA BOOLEAN OPERATIONS-FUNDAMENTAL BOOLEAN OPER. BOOLEAN expressions must be evaluated with the following order of operator precedence parentheses NOT AND ORExample:FACBD+()BC+()E=FACBD+ BC+ E={ { { Dansereau; TO COMP. III-6 BOOLEAN ALGEBRAFUNCTION EVALUATIONBOOLEAN ALGEBRA BOOLEAN OPERATIONS BOOLEAN ALGEBRA -PRECEDENCE OF OPER. Example 1:Evaluate the following expression when , , Solution Example 2:Evaluate the following expression when , , , SolutionA1=B0=C1=FCCBBA++=F 1 10 01 + +100++1===A0=B0=C1=D1=FDBCAABC+()C++()=F 1 010 00 1+()1++() 1011++() 11 1==== Dansereau; TO COMP. III-7 BOOLEAN ALGEBRABASIC IDENTITIESBOOLEAN ALGEBRA BOOLEAN OPERATIONS BOOLEAN ALGEBRA -PRECEDENCE OF EVALUATIONX0+X=X1+1=XX +1=X () X=XY+YX+=X1 X=X0 0=XX 0=XYYX=XYZ()XY()Z=XYZ+()+XY+()Z+=XY Z+()XY XZ+=XYZ+XY+()XZ+()=CommutativityIdentity Involution LawAssociativityDistributivityComplement Idempotent LawXX X=XX+X=Absorption LawXX Y+()X=XXY+X=SimplificationXX Y+()XY=XX Y+XY+=DeMorgan s LawXY() X Y +=XY+() X Y =Consensus TheoremXY+()X Z+()YZ+()XY X ZYZ++ XY X Z+= XY+()X Z+()= Dansereau; TO COMP.}}}
3 III-8 BOOLEAN ALGEBRADUALITY PRINCIPLEBOOLEAN ALGEBRA BOOLEAN ALGEBRA -PRECEDENCE OF EVALUATION-BASIC IDENTITIES Duality principle: States that a BOOLEAN equation remains valid if we take the dual of the expressions on both sides of the equals sign. The dual can be found by interchanging the AND and OR operators along with also interchanging the 0 s and 1 s. This is evident with the duals in the basic identities. For instance: DeMorgan s Law can be expressed in two formsXY+() X Y =XY() X Y +=as well Dansereau; TO COMP. III-9 BOOLEAN ALGEBRAFUNCTION MANIPULATION (1) BOOLEAN ALGEBRA BOOLEAN ALGEBRA -FUNCTION EVALUATION-BASIC IDENTITIES-DUALITY PRINCIPLE Example: Simplify the following expression SimplificationF BCBCBA++=FBCC+()BA+=FB1BA+ =FB1A+()=FB= Dansereau; TO COMP. III-10 BOOLEAN ALGEBRAFUNCTION MANIPULATION (2) BOOLEAN ALGEBRA BOOLEAN ALGEBRA -BASIC IDENTITIES-DUALITY PRINCIPLE-FUNC. MANIPULATION Example: Simplify the following expression SimplificationFA AB ABC ABCD ABCDE++ ++=FA A B BC BCD BCDE++ +()+=F ABBCBCDBCDE++ ++=F ABBCCDCDE++()++=F ABCCDCDE++++=F ABCCDDE+()+++=F ABCDDE++++=F ABCDE++++= Dansereau; TO COMP.
4 III-11 BOOLEAN ALGEBRAFUNCTION MANIPULATION (3) BOOLEAN ALGEBRA BOOLEAN ALGEBRA -BASIC IDENTITIES-DUALITY PRINCIPLE-FUNC. MANIPULATION Example: Show that the following equality holds SimplificationABC BC+()ABC+()BC+()+=ABC BC+()ABCBC+()+= ABC()BC()+= ABC+()BC+()+= Dansereau; TO COMP. III-12 STANDARD FORMSSOP AND POSBOOLEAN ALGEBRA BOOLEAN ALGEBRA -BASIC IDENTITIES-DUALITY PRINCIPLE-FUNC. MANIPULATION BOOLEAN expressions can be manipulated into many forms. Some standardized forms are required for BOOLEAN expressions to simplify communication of the expressions. Sum-of-products (SOP) Example: Products-of-sums (POS) Example:FABCD,,,()AB BCD AD++=FABCD,,,()AB+()BCD++()AD+()= Dansereau; TO COMP. III-13 STANDARD FORMSMINTERMSBOOLEAN ALGEBRA BOOLEAN ALGEBRA STANDARD FORMS-SOP AND POS The following table gives the minterms for a three-input Dansereau; TO COMP. III-14 STANDARD FORMSSUM OF MINTERMSBOOLEAN ALGEBRA BOOLEAN ALGEBRA STANDARD FORMS-SOP AND POS-MINTERMS Sum-of-minterms standard form expresses the BOOLEAN or switching expression in the form of a sum of products using minterms.
5 For instance, the following BOOLEAN expression using mintermscould instead be expressed asor more compactlyFABC,,()ABC ABC ABC ABC+++=FABC,,()m0m1m4m5+++=FABC,,()m0145 ,,,() one-set0145,,,()== Dansereau; TO COMP. III-15 STANDARD FORMSMAXTERMSBOOLEAN ALGEBRA STANDARD FORMS-SOP AND POS-MINTERMS-SUM OF MINTERMS The following table gives the maxterms for a three-input systemABC0111111110111111110111111110111 1111101111111101111111101111111100000111 10011001101010101M2M3M4M1M0M5M6M7 ABC++ABC++ABC++ABC++ABC++ABC++ABC++ABC++ Dansereau; TO COMP. III-16 STANDARD FORMSPRODUCT OF MAXTERMSBOOLEAN ALGEBRA STANDARD FORMS-MINTERMS-SUM OF MINTERMS-MAXTERMS Product-of-maxterms standard form expresses the BOOLEAN or switching expression in the form of product of sums using maxterms. For instance, the following BOOLEAN expression using maxtermscould instead be expressed asor more compactly asFABC,,()ABC++()ABC++()ABC++()=FABC,,() M1M4M7 =FABC,,()M147,,() zero-set147,,()== Dansereau; TO COMP.
6 III-17 STANDARD FORMSMINTERM AND MAXTERM ALGEBRA STANDARD FORMS-SUM OF MINTERMS-MAXTERMS-PRODUCT OF MAXTERMS Given an arbitrary BOOLEAN function, such ashow do we form the canonical form for: sum-of-minterms Expand the BOOLEAN function into a sum of products. Then take each term with a missing variable and AND it with . product-of-maxterms Expand the BOOLEAN function into a product of sums. Then take each factor with a missing variable and OR it with .FABC,,()AB B A C+()+=XXX+ Dansereau; TO COMP. III-18 STANDARD FORMSFORMING SUM OF MINTERMSBOOLEAN ALGEBRA STANDARD FORMS-MAXTERMS-PRODUCT OF MAXTERMS-MINTERM & MAXTERM ExampleFABC,,()AB B A C+()+AB AB BC++== AB C C+()AB C C+()AA+()BC++= ABC ABC ABC ABC ABC++++= m01467,,,,() =ABC F1100101100001111001100110101010101467 Minterms listed as1s in Truth Dansereau; TO COMP. III-19 STANDARD FORMSFORMING PROD OF MAXTERMSBOOLEAN ALGEBRA STANDARD FORMS-PRODUCT OF MAXTERMS-MINTERM & MAXTERM-FORM SUM OF MINTERMS ExampleFABC,,()AB B A C+()+AB AB BC++== AB+()ABC++()ABC++()= M235,,() = ABCC++()ABC++()ABC++()= ABC++()ABC++()ABC++()=(using distributivity)ABC F11001011000011110011001101010101235 Maxterms listed as0s in Truth Dansereau; TO COMP.
7 III-20 STANDARD FORMSCONVERTING MIN AND MAXBOOLEAN ALGEBRA STANDARD FORMS-MINTERM & MAXTERM-SUM OF MINTERMS-PRODUCT OF MAXTERMS Converting between sum-of-minterms and product-of-maxterms The two are complementary, as seen by the truth tables. To convert interchange the and , then use missing terms. Example: The example from the previous slidesis re-expressed aswhere the numbers 2, 3, and 5 were missing from the minterm representation. FABC,,()m01467,,,,() =FABC,,()M235,,() = Dansereau; TO COMP. III-21 SIMPLIFICATIONKARNAUGH MAPSBOOLEAN ALGEBRA STANDARD FORMS-SUM OF MINTERMS-PRODUCT OF MAXTERMS-CONVERTING MIN & MAX Often it is desired to simplify a BOOLEAN function. A quick graphical approach is to use Karnaugh 01 11 10 ABC00010101AB01000100111101000001111000 01 11 10 ABCD2-variableKarnaugh map3-variableKarnaugh map4-variableKarnaugh mapFAB=FABC+=FABCD+= Dansereau; TO COMP. III-22 SIMPLIFICATIONKARNAUGH MAP ORDERINGBOOLEAN ALGEBRA STANDARD FORMS SIMPLIFICATION-KARNAUGH MAPS Notice that the ordering of cells in the map are such that moving from one cell to an adjacent cell only changes one variable.
8 This ordering allows for grouping of minterms/maxterms for 01 11 10 ABC01230101AB013245761213151489111000011 11000 01 11 10 ABCD2-variableKarnaugh map3-variableKarnaugh map4-variableKarnaugh Dansereau; TO COMP. III-23 SIMPLIFICATIONIMPLICANTSBOOLEAN ALGEBRA STANDARD FORMS SIMPLIFICATION-KARNAUGH MAPS-KARNAUGH MAP ORDER Implicant Bubble covering only 1s (size of bubblemust be a power of 2). Prime implicant Bubble that is expanded as big as possible(but increases in size by powers of 2). Essential prime implicant Bubble that contains a 1 covered only byitself and no other prime implicant bubble. Non-essential prime implicant A 1 that can be bubbled by more then oneprime implicant 11 Dansereau; TO COMP. III-24 SIMPLIFICATIONPROCEDURE FOR SOPBOOLEAN ALGEBRA SIMPLIFICATION-KARNAUGH MAPS-KARNAUGH MAP ORDER-IMPLICANTS Procedure for finding the SOP from a Karnaugh map Step 1: Form the 2-, 3-, or 4-variable Karnaugh map as appropriate for the BOOLEAN function.
9 Step 2: Identify all essential prime implicants for 1s in the Karnaugh map Step 3: Identify non-essential prime implicants for 1s in the Karnaugh map. Step 4: For each essential and one selected non-essential prime implicant from each set, determine the corresponding product term. Step 5: Form a sum-of-products with all product terms from previous Dansereau; TO COMP. III-25 SIMPLIFICATIONEXAMPLE FOR SOP (1) BOOLEAN ALGEBRA SIMPLIFICATION-KARNAUGH MAP ORDER-IMPLICANTS-PROCEDURE FOR SOP Simplify the following BOOLEAN function Solution: The essential prime implicants are . There are no non-essential prime implicants. The sum-of-products solution is .FABC,,()m0145,,,() ABC ABC ABC ABC+++==110011000100 01 11 10 ABCzero-set2367,,,()one-set 0 1 4 5,,,()BFB= Dansereau; TO COMP. III-26 SIMPLIFICATIONEXAMPLE FOR SOP (2) BOOLEAN ALGEBRA SIMPLIFICATION-IMPLICANTS-PROCEDURE FOR SOP-EXAMPLE FOR SOP Simplify the following BOOLEAN function Solution: The essential prime implicants are and.
10 The non-essential prime implicants are or . The sum-of-products solution is or .FABC,,()m01467,,,,() ABC ABC ABC ABC ABC++++==110010110100 01 11 10 ABCzero-set235,,()one-set 0 1 4 6 7,,,,()ABABBCACF ABABBC++=F ABABAC++= Dansereau; TO COMP. III-27 SIMPLIFICATIONPROCEDURE FOR POSBOOLEAN ALGEBRA SIMPLIFICATION-IMPLICANTS-PROCEDURE FOR SOP-EXAMPLE FOR SOP Procedure for finding the SOP from a Karnaugh map Step 1: Form the 2-, 3-, or 4-variable Karnaugh map as appropriate for the BOOLEAN function. Step 2: Identify all essential prime implicants for 0s in the Karnaugh map Step 3: Identify non-essential prime implicants for 0s in the Karnaugh map. Step 4: For each essential and one selected non-essential prime implicant from each set, determine the corresponding sum term. Step 5: Form a product-of-sums with all sum terms from previous Dansereau; TO COMP. III-28 SIMPLIFICATIONEXAMPLE FOR POS (1) BOOLEAN ALGEBRA SIMPLIFICATION-PROCEDURE FOR SOP-EXAMPLE FOR SOP-PROCEDURE FOR POS Simplify the following BOOLEAN function Solution: The essential prime implicants are and.
