CS231 Boolean Algebra 1Review: Standard forms of expressions• We can write expressions in many ways, but some ways are more useful than others• A sum of products (SOP) expression contains:– Only OR (sum) operations at the “outermost” level– Each term that is summed must be a product of literals• The advantage is that any sum of products expression can be implemented using a two-level circuit– literals and their complements at the “0th” level– AND gates at the first level– a single OR gate at the second level• This diagram uses some shorthands…– NOT gates are implicit– literals are reused– this is notokay in LogicWorks!f(x,y,z) = y’ + x’yz’ + xzCS231 Boolean Algebra 2The dual idea: products of sums• A product of sums (POS) expression contains:– Only AND (product) operations at the “outermost” level– Each term must be a sum of literals• Product of sums expressions can be implemented with two-level circuits– literals and their complements at the “0th” level–OR gatesat the first level– a single AND gateat the second level• Compare this with sums of productsf(x,y,z) = y’ (x’ + y + z’) (x + z)CS231 Boolean Algebra 3Complementing a function algebraically• You can use DeMorgan’s law to keep “pushing” the complements inwards• You can also take the dual of the function, and then complement each literal– If f(x,y,z) = x(y’z’ + yz)…– …the dual of f is x + (y’ + z’)(y + z)…– …then complementing each literal gives x’ + (y + z)(y’ + z’)…– …so f’(x,y,z) = x’ + (y + z)(y’ + z’)f(x,y,z) = x(y’z’ + yz)f’(x,y,z) = ( x(y’z’ + yz) )’ [ complement both sides ]= x’ + (y’z’ + yz)’ [ because (xy)’ = x’ + y’ ]= x’ + (y’z’)’ (yz)’ [ because (x + y)’ = x’ y’ ]= x’ + (y + z)(y’ + z’) [ because (xy)’ = x’ + y’, twice]CS231 Boolean Algebra 4K-map Review• K-maps are an alternative to algebra for simplifying expressions.– The result is a minimal sum of products, which leads to a minimal two-level circuit.– It’s easy to handle don’t-care conditions.– K-maps are really only good for manual simplification of small expressions... but that’s good enough for CS231!• Things to keep in mind:– Remember the correct order of minterms on the K-map.– When grouping, you can wrap around all sides of the K-map, and your groups can overlap.– Make as few rectangles as possible, but make each of them as large as possible. This leads to fewer, but simpler, product terms.– There may be more than one valid solution.CS231 Boolean Algebra 5Finding SOP Format from minterm• F(x,y,z) = Σm(0,1,2,4)• F = YXZCS231 Boolean Algebra 6Finding SOP Format from minterm• F(x,y,z) = Σm(0,1,2,4)• F = y’z’ + x’z’ + x’y’ Y 1 1 0 1 X 1 0 0 0 ZCS231 Boolean Algebra 7Finding POS Format from minterm• F(x,y,z) = Σm(0,1,2,4)• F’(x,y,z) = Σm(3,5,6,7)• F’ = • F = YXZCS231 Boolean Algebra 8Finding POS Format from minterm• F(x,y,z) = Σm(0,1,2,4)• F’(x,y,z) = Σm(3,5,6,7)• F’ = yz + xz + xy• F = (y’+z’)(x’+z’)(x’+y’) Y 0 0 1 0 X 0 1 1 1 ZCS231 Boolean Algebra 9Finding minimal SOP/POS from Boolean Expression• F(w,x,y,z) = w’x’ + yz’ + wxy + w’x’yz’ + wxy’z + w’y’z’• Minimal SOP: F = Y X W ZCS231 Boolean Algebra 10Finding minimal SOP/POS from Boolean Expression• F(w,x,y,z) = w’x’ + yz’ + wxy + w’x’yz’ + wxy’z + w’y’z’• Minimal SOP: F =w’x’ + yz’ + w’z’ + wxz Y 1 1 1 1 1 0 0 1 0 1 1 1 X W 0 0 0 1 ZCS231 Boolean Algebra 11Finding minimal SOP/POS from Boolean Expression• F(w,x,y,z) = w’x’ + yz’ + wxy + w’x’yz’ + wxy’z + w’y’z’• Min SOP of F’ = • Min POS of F = Y 1 1 1 1 1 0 0 1 0 1 1 1 X W 0 0 0 1 Z Y 0 0 0 0 0 1 1 0 1 0 0 0 X W 1 1 1 0 ZCS231 Boolean Algebra 12Finding minimal SOP/POS from Boolean Expression• F(w,x,y,z) = w’x’ + yz’ + wxy + w’x’yz’ + wxy’z + w’y’z’• Min SOP of F’ = w’xz + wx’z + wy’z’• Min POS of F = (w+x’+z’)(w’+x+z’)(w’+y+z) Y 1 1 1 1 1 0 0 1 0 1 1 1 X W 0 0 0 1 Z Y 0 0 0 0 0 1 1 0 1 0 0 0 X W 1 1 1 0 ZCS231 Boolean Algebra 13Don’t-Care Conditions• Occasionally, we don’t care what the value of a function is for certain minterms. – When a certain input(s) will never happen. E.g. when dealing with Binary-coded decimal (BCD), the inputs for 1010-1111 (10-15) will never occur.– When a certain input(s) will occur, but we don’t care what the output will be in response to them. E.g. imagine a circuit which counts votes and has two outputs: a Yes/No output and a output which indicates ‘Tie’. If the vote is a tie, we don’t care whether the Yes/No output is 1 or 0.• We can either include or exclude these minterms in our function, whichever allows us to create the simplest representation. • On our K-map, we represent these minterms with an ‘x’ to indicate that it may or may not be grouped.CS231 Boolean Algebra 14Practice: Don’t Care• f(w,x,y,z) = Σm(1,3,7,11,15)• d(w,x,y,z) = Σd(0,2,5) Y X W ZCS231 Boolean Algebra 15Practice: Don’t Care• f(w,x,y,z) = Σm(1,3,7,11,15)• d(w,x,y,z) = Σd(0,2,5)• F(w,x,y,z) = yz + w’x’• F(w,x,y,z) = yz + w’zNOT equivalent,but both valid. Y x 1 1 x 0 x 1 0 0 0 1 0 X W 0 0 1 0 ZCS231 Boolean Algebra 16Summary• We can use K-maps to find the minimal Sum of Products (MSP) given some representation of a function.• The minimal Product of Sums of a function can be found by complementing the MSP of that function’s complement. Thus K-maps can be used to find a minimal PoS.• Don’t-care conditions allow us to simplify the expression (and thus the circuit) for functions where we’re only concerned about some of the inputs. This can result in multiple functions which are algebraically unequal, but both of which correctly meet the specifications of our function.CS231 Boolean Algebra 17More Practice: Don’t Care• f(w,x,y,z) = Σm(• d(w,x,y,z) = Σd( Y X W