INTRO TO COMP ENG CHAPTER III 1 CHAPTER III BOOLEAN ALGEBRA CHAPTER III BOOLEAN ALGEBRA R M Dansereau v 1 0 INTRO TO COMP ENG CHAPTER III 2 BOOLEAN ALGEBRA BOOLEAN VALUES BOOLEAN VALUES INTRODUCTION 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 0 R M Dansereau v 1 0 INTRO TO COMP ENG CHAPTER III 3 BOOLEAN ALGEBRA BOOL OPERATIONS BOOLEAN VALUES INTRODUCTION FUNDAMENTAL OPERATORS Three fundamental operators in Boolean algebra NOT unary operator that complements represented as A A or A AND binary operator which performs logical multiplication i e A ANDed with B would be represented as AB or A B OR binary operator which performs logical addition i e A ORed with B would be represented as A B NOT AND OR A B A B A A A B AB 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 R M Dansereau v 1 0 INTRO TO COMP ENG CHAPTER III 4 BOOLEAN ALGEBRA BOOL OPERATIONS BOOLEAN OPERATIONS FUNDAMENTAL OPER BINARY BOOLEAN OPERATORS Below is a table showing all possible Boolean functions F N given the twoinputs A and B A B F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 10 F 11 F 12 F 13 F 14 F 15 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 AB Null A A B A B Inhibition R M Dansereau v 1 0 B A B A B B A Implication AB 1 Identity INTRO TO COMP ENG CHAPTER III 5 BOOLEAN ALGEBRA BOOLEAN ALGEBRA PRECEDENCE OF OPERATORS BOOLEAN OPERATIONS FUNDAMENTAL OPER BINARY BOOLEAN OPER Boolean expressions must be evaluated with the following order of operator precedence parentheses Example AND F A C BD BC E OR F R M Dansereau v 1 0 A C BD BC E NOT INTRO TO COMP ENG CHAPTER III 6 BOOLEAN ALGEBRA BOOLEAN ALGEBRA FUNCTION EVALUATION BOOLEAN OPERATIONS BOOLEAN ALGEBRA PRECEDENCE OF OPER Example 1 Evaluate the following expression when A 1 B 0 C 1 F C CB BA Solution F 1 1 0 0 1 1 0 0 1 Example 2 Evaluate the following expression when A 0 B 0 C 1 D 1 F D BCA AB C C Solution F 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 R M Dansereau v 1 0 INTRO TO COMP ENG CHAPTER III 7 BOOLEAN ALGEBRA BOOLEAN ALGEBRA BASIC IDENTITIES BOOLEAN OPERATIONS BOOLEAN ALGEBRA PRECEDENCE OF OPER FUNCTION EVALUATION X 0 X X 1 X X 1 1 X 0 0 X X X X X X Idempotent Law X X 1 X X 0 Complement X X Identity Involution Law X Y Y X XY YX Commutativity X Y Z X Y Z X YZ XY Z Associativity X Y Z XY XZ X YZ X Y X Z Distributivity X XY X X X Y X Absorption Law X X Y X Y X X Y XY Simplification X Y X Y XY X Y DeMorgan s Law XY X Z YZ XY X Z X Y X Z Y Z X Y X Z R M Dansereau v 1 0 Consensus Theorem INTRO TO COMP ENG CHAPTER III 8 BOOLEAN ALGEBRA BOOLEAN ALGEBRA BOOLEAN ALGEBRA PRECEDENCE OF OPER FUNCTION EVALUATION BASIC IDENTITIES DUALITY PRINCIPLE 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 forms X Y X Y R M Dansereau v 1 0 as well as XY X Y INTRO TO COMP ENG CHAPTER III 9 BOOLEAN ALGEBRA BOOLEAN ALGEBRA FUNCTION MANIPULATION 1 Example Simplify the following expression F BC BC BA Simplification F B C C BA F B 1 BA F B 1 A F B R M Dansereau v 1 0 BOOLEAN ALGEBRA FUNCTION EVALUATION BASIC IDENTITIES DUALITY PRINCIPLE INTRO TO COMP ENG CHAPTER III 10 BOOLEAN ALGEBRA BOOLEAN ALGEBRA FUNCTION MANIPULATION 2 Example Simplify the following expression F A AB ABC ABCD ABCDE Simplification F A A B BC BCD BCDE F A B BC BCD BCDE F A B B C CD CDE F A B C CD CDE F A B C C D DE F A B C D DE F A B C D E R M Dansereau v 1 0 BOOLEAN ALGEBRA BASIC IDENTITIES DUALITY PRINCIPLE FUNC MANIPULATION INTRO TO COMP ENG CHAPTER III 11 BOOLEAN ALGEBRA BOOLEAN ALGEBRA FUNCTION MANIPULATION 3 Example Show that the following equality holds A BC BC A B C B C Simplification A BC BC A BC BC A BC BC A B C B C R M Dansereau v 1 0 BOOLEAN ALGEBRA BASIC IDENTITIES DUALITY PRINCIPLE FUNC MANIPULATION INTRO TO COMP ENG CHAPTER III 12 STANDARD FORMS SOP AND POS BOOLEAN 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 F A B C D AB BCD AD Products of sums POS Example F A B C D A B B C D A D R M Dansereau v 1 0 INTRO TO COMP ENG CHAPTER III 13 STANDARD FORMS MINTERMS BOOLEAN ALGEBRA BOOLEAN ALGEBRA STANDARD FORMS SOP AND POS The following table gives the minterms for a three input system m0 m1 m2 m3 m4 m5 m6 m7 A B C ABC ABC ABC ABC ABC ABC ABC ABC 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 R M Dansereau v 1 0 INTRO TO COMP ENG CHAPTER III 14 BOOLEAN ALGEBRA STANDARD FORMS SUM OF MINTERMS BOOLEAN ALGEBRA STANDARD FORMS SOP AND POS MINTERMS Sum of …
View Full Document
Unlocking...