R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-1BOOLEAN ALGEBRA•CHAPTER IIICHAPTER IIIBOOLEAN ALGEBRAR.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-2BOOLEAN 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 / 0R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-3BOOL. 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• i.e. ANDed with would be represented as or •OR: binary operator which performs logical addition• i.e. ORed with would be represented as AA′ A∼AB ABAB⋅AB AB+AB001101010001AB001101010111A0110AAB A B+NOT AND ORR.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-4BOOL. OPERATIONSBINARY BOOLEAN OPERATORSBOOLEAN ALGEBRA•BOOLEAN OPERATIONS-FUNDAMENTAL OPER.•Below is a table showing all possible Boolean functions given the two-inputs and .000000000011111111010000111100001111100011001100110011110101010101010101FNABABF0F1F2F3F4F5F6F7F8F9F10F11F12F13F14F1501AB A B+AB⊕ABAB+AB BAAB⊕Null IdentityInhibitionImplicationR.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-5BOOLEAN ALGEBRAPRECEDENCE OF OPERATORSBOOLEAN ALGEBRA•BOOLEAN OPERATIONS-FUNDAMENTAL OPER.-BINARY BOOLEAN OPER.•Boolean expressions must be evaluated with the following order of operator precedence• parentheses• NOT• AND• ORExample:FACBD+()BC+()E=FACBD+BC+E={{{R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-6BOOLEAN 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====R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-7BOOLEAN ALGEBRABASIC IDENTITIESBOOLEAN ALGEBRA•BOOLEAN OPERATIONS•BOOLEAN ALGEBRA-PRECEDENCE OF OPER.-FUNCTION EVALUATIONX0+X=X1+1=XX′+1=X′()′X=XY+YX+=X1⋅X=X0⋅0=XX′⋅0=XY YX=XYZ()XY()Z=XYZ+()+XY+()Z+=XY Z+()XY XZ+=XYZ+XY+()XZ+()=CommutativityIdentityInvolution LawAssociativityDistributivityComplementIdempotent 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+()=R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-8BOOLEAN ALGEBRADUALITY PRINCIPLEBOOLEAN ALGEBRA•BOOLEAN ALGEBRA-PRECEDENCE OF OPER.-FUNCTION 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 asR.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-9BOOLEAN 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=R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-10BOOLEAN ALGEBRAFUNCTION MANIPULATION (2)BOOLEAN ALGEBRA•BOOLEAN ALGEBRA-BASIC IDENTITIES-DUALITY PRINCIPLE-FUNC. MANIPULATION•Example: Simplify the following expression• SimplificationF A AB ABC ABCD ABCDE++ + +=F A A B BC BCD BCDE++ +()+=F ABBCBCDBCDE++ ++=F ABBCCDCDE++()++=F ABCCDCDE++++=F ABCCDDE+()+++=F ABCDDE++++=F ABCDE++++=R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-11BOOLEAN 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+()+=R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-12STANDARD 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+()=R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-13STANDARD FORMSMINTERMSBOOLEAN ALGEBRA•BOOLEAN ALGEBRA•STANDARD FORMS-SOP AND POS•The following table gives the minterms for a three-input systemABCABCABC ABC ABCABC ABC ABC ABC1000000001000000001000000001000000001000000001000000001000000001000011110011001101010101m2m3m4m1m0m5m6m7R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-14STANDARD 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.• For instance, the following Boolean expression using mintermscould instead be expressed asor more compactlyFABC,,()ABC ABC ABC ABC+++=FABC,,()m0m1m4m5+++=FABC,,()m0145,,,()∑one-set0145,,,()==R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-15STANDARD FORMSMAXTERMSBOOLEAN ALGEBRA•STANDARD FORMS-SOP AND POS-MINTERMS-SUM OF MINTERMS•The following table gives the maxterms for a three-input systemABC0111111110111111110111111110111111110111111110111111110111111110000011110011001101010101M2M3M4M1M0M5M6M7ABC++ABC++ABC++ABC++ABC++ABC++ABC++ABC++R.M. Dansereau; v.1.0INTRO. TO COMP. ENG.CHAPTER III-16STANDARD 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
View Full Document
Unlocking...