CS231 Boolean Algebra 1From now on: • Combinatorial Circuits:– Study analyses and design of circuits made up of gates without memory– Design components needed for a simple “Computer”• Sequential Circuits:– Study basic memory elements– Study Circuits that can be designed using memory elements and gates• Design a computer (and understand design of computers in general)CS231 Boolean Algebra 2Combinatorial Circuits• Analysis of Circuits:– Given a circuit with gates (but no feedback : i.e. no memory), figure out what it does– Express it as “boolean expressions”• Methods for simplifying circuits– Boolean algebra– Karnaugh Maps (K-maps)CS231 Boolean Algebra 3Functions• Computers take inputs and produce outputs, just like functions in math!• Mathematical functions can be expressed in two ways:• We can represent logical functions in two analogous ways too:– A finite, but non-unique Boolean expression. – A truth table, which will turn out to be unique and finite.x y f(x,y)0 0 0… … …2 2 6… … …23 41 87… … …f(x,y) = 2x + y= x + x + y= 2(x + y/2)= ...An expression isfinite but not uniqueA function table isunique but infiniteCS231 Boolean Algebra 4Basic Boolean operations • There are three basic operations for logical values.x y xy0 0 00 1 01 0 01 1 1x y x+y0 0 00 1 11 0 11 1 1x x’0 11 0AND (product)of two inputsOR (sum) of two inputsNOT(complement)on one inputxy, or x•y x + y x’Operation:Expression:Truth table:CS231 Boolean Algebra 5Boolean expressions• We can use these basic operations to form more complex expressions:f(x,y,z) = (x + y’)z + x’• Some terminology and notation:– f is the name of the function.– (x,y,z) are the input variables, each representing 1 or 0. Listing the inputs is optional, but sometimes helpful.– A literal is any occurrence of an input variable or its complement. The function above has four literals: x, y’, z, and x’.• Precedences are important, but not too difficult.– NOT has the highest precedence, followed by AND, and then OR.– Fully parenthesized, the function above would be kind of messy:f(x,y,z) = (((x +(y’))z) + x’)CS231 Boolean Algebra 6Truth tables• A truth table shows all possible inputs and outputs of a function.• Remember that each input variable represents either 1 or 0.– Because there are only a finite number of values (1 and 0), truth tables themselves are finite.– A function with n variables has 2n possible combinations of inputs.• Inputs are listed in binary order—in this example, from 000 to 111.x y z f(x,y,z)0 0 0 10 0 1 10 1 0 10 1 1 11 0 0 01 0 1 11 1 0 01 1 1 1f(0,0,0) = (0 + 1)0 + 1 = 1f(0,0,1) = (0 + 1)1 + 1 = 1f(0,1,0) = (0 + 0)0 + 1 = 1f(0,1,1) = (0 + 0)1 + 1 = 1f(1,0,0) = (1 + 1)0 + 0 = 0f(1,0,1) = (1 + 1)1 + 0 = 1f(1,1,0) = (1 + 0)0 + 0 = 0f(1,1,1) = (1 + 0)1 + 0 = 1f(x,y,z) = (x + y’)z + x’CS231 Boolean Algebra 7Primitive logic gates• Each of our basic operations can be implemented in hardware using a primitive logic gate.– Symbols for each of the logic gates are shown below.– These gates output the product, sum or complement of their inputs.Logic gate:AND (product)of two inputsOR (sum) of two inputsNOT(complement)on one inputxy, or x•y x + y x’Operation:Expression:CS231 Boolean Algebra 8Expressions and circuits•AnyBoolean expression can be converted into a circuit by combining basic gates in a relatively straightforward way.• The diagram below shows the inputs and outputs of each gate.• The precedences are explicit in a circuit. Clearly, we have to make sure that the hardware does operations in the right order!(x + y’)z + x’CS231 Boolean Algebra 9Circuit analysis• Circuit analysis involves figuring out what some circuit does.– Every circuit computes some function, which can be described with Boolean expressions or truth tables.– So, the goal is to find an expression or truth table for the circuit.• The first thing to do is figure out what the inputs and outputs of the overall circuit are.– This step is often overlooked!– The example circuit here has threeinputs x, y, z and oneoutput f.CS231 Boolean Algebra 10Write algebraic expressions...• Next, write expressions for the outputs of each individual gate, based on that gate’s inputs.– Start from the inputs and work towards the outputs.– It might help to do some algebraic simplification along the way.• Here is the example again.– We did a little simplification for the top AND gate.– You can see the circuit computes f(x,y,z) = xz + y’z + x’yz’CS231 Boolean Algebra 11...or make a truth table• It’s also possible to find a truth table directly from the circuit.• Once you know the number of inputs and outputs, list all the possible input combinations in your truth table.– A circuit with n inputs should have a truth table with 2nrows.– Our example has three inputs, so the truth table will have 23= 8 rows. All the possible input combinations are shown.x y z f0 0 00 0 10 100 1 11 001 0 11 101 1 1CS231 Boolean Algebra 12Simulating the circuit• Then you can simulate the circuit, either by hand or with a program like LogicWorks, to find the output for each possible combination of inputs.• For example, when xyz = 101, the gate outputs would be as shown below.– Use truth tables for AND, OR and NOT to find the gate outputs.– For the final output, we find that f(1,0,1) = 1. x y z f0 0 00 0 10 100 1 11 001 0 1 11 1 01 1 11011001101CS231 Boolean Algebra 13Finishing the truth table• Doing the same thing for all the other input combinations yields the complete truth table.• This is simple, but tedious.x y z f0 0 0 00 0 1 10 1010 1 101 0001 0 1 11 1001 1 1 1CS231 Boolean Algebra 14Expressions and truth tables• Remember that if you already have a Boolean expression, you can use that to easily make a truth table.• For example, since we already found that the circuit computes the function f(x,y,z) = xz + y’z + x’yz’, we can use that to fill in a table:– We show intermediate columns for the terms xz, y’z and x’yz’.– Then, f is obtained by just OR’ing the intermediate columns.x y z xz y’z x’yz’ f 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1CS231 Boolean Algebra 15Expressions and truth tables• Remember that if you already have a Boolean expression, you can use that to easily make a truth table.• For example, since we already
View Full Document
Unlocking...