Chapter 10.1 and 10.2: Boolean AlgebraLearning ObjectivesTwo-Element Boolean AlgebraSlide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Boolean AlgebraSlide 15Slide 16Slide 17Slide 18Slide 19Sum of products expressionF(x,y,z) = (x + y) z’Slide 22Slide 23Slide 24Functional CompletenessChapter 10.1 and 10.2: Boolean AlgebraBased on Slides fromDiscrete Mathematical Structures: Theory and ApplicationsDiscrete Mathematical Structures: Theory and Applications2Learning ObjectivesLearn about Boolean expressionsBecome aware of the basic properties of Boolean algebraDiscrete Mathematical Structures: Theory and Applications3Two-Element Boolean AlgebraLet B = {0, 1}.Discrete Mathematical Structures: Theory and Applications4Two-Element Boolean AlgebraDiscrete Mathematical Structures: Theory and Applications5Discrete Mathematical Structures: Theory and Applications6Discrete Mathematical Structures: Theory and Applications7Discrete Mathematical Structures: Theory and Applications8Two-Element Boolean AlgebraDiscrete Mathematical Structures: Theory and Applications9Two-Element Boolean AlgebraDiscrete Mathematical Structures: Theory and Applications10Discrete Mathematical Structures: Theory and Applications11Discrete Mathematical Structures: Theory and Applications12Discrete Mathematical Structures: Theory and Applications13Discrete Mathematical Structures: Theory and Applications14Boolean AlgebraDiscrete Mathematical Structures: Theory and Applications15Boolean AlgebraDiscrete Mathematical Structures: Theory and Applications16Discrete Mathematical Structures: Theory and Applications17Find a minterm that equals 1 ifx1 = x3 = 0 and x2 = x4 = x5 =1,and equals 0 otherwise.x’1x2x’3x4x5Discrete Mathematical Structures: Theory and Applications18Discrete Mathematical Structures: Theory and Applications19Therefore, the set of operators {. , +, ‘} is functionally complete.Discrete Mathematical Structures: Theory and Applications20Sum of products expressionExample 3, p. 710Find the sum of products expansion of F(x,y,z) = (x + y) z’Two approaches:1) Use Boolean identifies2) Use table of F values for all possible 1/0 assignments of variables x,y,zDiscrete Mathematical Structures: Theory and Applications21F(x,y,z) = (x + y) z’Discrete Mathematical Structures: Theory and Applications22F(x,y,z) = (x + y) z’F(x,y,z) = (x + y) z’= xyz’ + xy’z’ + x’yz’Discrete Mathematical Structures: Theory and Applications23Discrete Mathematical Structures: Theory and Applications24Discrete Mathematical Structures: Theory and Applications25Functional Completeness0100111 The set of operators {. , +, ‘} is functionally complete.Can we find a smaller set?Yes, {. , ‘}, since x + y = (x’ . y’)’Can we find a set with just one operator?Yes, {NAND}, {NOR} are functionally complete:NAND: 1|1 = 0 and 1|0 = 0|1 = 0|0 = 1NOR:100 {NAND} is functionally complete, since {. , ‘} is so andx’ = x|xxy =
View Full Document