PowerPoint PresentationTopicsCombinatorial logicTruth TableSlide 5Translating mathematics to machinesLogical expressionsTruth tables with 2 inputsSlide 9And, Or, and Not are sufficientSlide 11NOR is sufficient by itselfLogical ExpressionsLogic Function ExampleLogic Function Example 2Example “Truth Table”Evaluation of Logical Expressions with “Truth Tables”Some Important Logical FunctionsLogic GatesLogic Circuits10/22/2004 EE 42 fall 2004 lecture 22 1Lecture #22 Truth tables and gatesThis week: Circuits for digital devices10/22/2004 EE 42 fall 2004 lecture 22 2TopicsToday:•Combinatorial logic•Truth tables•And, Or, and Not gates10/22/2004 EE 42 fall 2004 lecture 22 3Combinatorial logicCombinatorial logic describes a digital circuit where there are a set of digital inputs, say N wires each one (1) or zero (0)( example:1=true, 2 volts or 0=false, zero volts)And M digital outputs, M wires each carrying 1 or 0, which are an instantaneous function of the inputsSo in combinatorial logic, there is no sequence of events, internal memory or flags, just a straight inputoutput10/22/2004 EE 42 fall 2004 lecture 22 4Truth Table•A truth table is a general way of describing combinatorial logic, by just listing all of the possible states of the input, and the value of each output which is the result. Lets look at a truth table for “exclusive or” (XOR)A B output0 0 00 1 11 0 11 1 0Every possible combination of inputs10/22/2004 EE 42 fall 2004 lecture 22 5In principle, every problem which could be described with discrete inputs (integers, fractions, flags programs!) could be solved with a single combinatorial logic machine.This is very fast once built.But it practice, the combinatorial logic would get too complex, for example the truth table would have 2n rows, where N is the number of Boolean variables needed to take into account all possible inputs.So for complex problems, we use combinatorial logic circuits as steps from state to state of a machine (a “finite state machine”, for example a computer)10/22/2004 EE 42 fall 2004 lecture 22 6Translating mathematics to machines•So once again, we are in the position of translating mathematics into a machine which can execute the formulas, but this time as digital, Boolean expressions rather than as continuous functions of time and voltage.10/22/2004 EE 42 fall 2004 lecture 22 7Logical expressions•Fortunately, as Boole pointed out, the language of facts which are true or false are natural to us as a species, and so we can deal with much of Boolean logic intuitively. •However, more complex logic expressions are easier if we have a notation, symbols and rules for manipulation.10/22/2004 EE 42 fall 2004 lecture 22 8Truth tables with 2 inputs•With just two Boolean inputs, there are four possible combinations, so a truth table for two inputs would have four rows.•00, 01, 10, 11•Each of the rows of a possible truth table can have a different Boolean output, so there are 16 different possible truth tables for an expression with two inputs, and they are shown on the next slide9A B out0 0 00 1 01 0 01 1 0A B out0 0 10 1 01 0 01 1 0A B out0 0 00 1 11 0 01 1 0A B out0 0 10 1 11 0 01 1 0A B out0 0 00 1 01 0 11 1 0A B out0 0 10 1 01 0 11 1 0A B out0 0 00 1 11 0 11 1 0A B out0 0 10 1 11 0 11 1 0A B out0 0 00 1 01 0 01 1 1A B out0 0 10 1 01 0 01 1 1A B out0 0 00 1 11 0 01 1 1A B out0 0 10 1 11 0 01 1 1A B out0 0 00 1 01 0 11 1 1A B out0 0 10 1 01 0 11 1 1A B out0 0 00 1 11 0 11 1 1A B out0 0 10 1 11 0 11 1 1NORANDXORORNAND10/22/2004 EE 42 fall 2004 lecture 22 10And, Or, and Not are sufficient•As you see from the next slide, with only the functions AND OR and NOT, all of the possible expressions for two inputs can be formed.•Any expression of any number of inputs can be formed using just AND OR, and NOT.•NOR by itself is also complete, but is not as intuitive to use11A B out0 0 00 1 01 0 01 1 0A B out0 0 10 1 01 0 01 1 0A B out0 0 00 1 11 0 01 1 0A B out0 0 10 1 11 0 01 1 0A B out0 0 00 1 01 0 11 1 0A B out0 0 10 1 01 0 11 1 0A B out0 0 00 1 11 0 11 1 0A B out0 0 10 1 11 0 11 1 0A B out0 0 00 1 01 0 01 1 1A B out0 0 10 1 01 0 01 1 1A B out0 0 00 1 11 0 01 1 1A B out0 0 10 1 11 0 01 1 1A B out0 0 00 1 01 0 11 1 1A B out0 0 10 1 01 0 11 1 1A B out0 0 00 1 11 0 11 1 1A B out0 0 10 1 11 0 11 1 1Not (A or B)AND (A or B) and (not (A and B))ORNot (A and B)False B and (not A) Not AA and (not B) Not BNot (A OR B) B (not A) or (A and B)A A OR (Not B) True10/22/2004 EE 42 fall 2004 lecture 22 12NOR is sufficient by itself•NOT A = A NOR A•A AND B = (Not A) NOR (Not B)•A OR B= Not (A NOR B)•So if you can build a NOR circuit, these can be combined to form any Boolean logic expression10/22/2004 EE 42 fall 2004 lecture 22 13Logical ExpressionsExample: Z = AExamples: X = A · B ; Y = A · B · CExamples: W = A+B ; Z = A+B+CStandard logic notation :AND: “dot”OR : “+ sign”NOT: “bar over symbol for complement”With these basic operations we can construct any logical expression. Order of operation: NOT, AND, OR (note that negation of an expression is performed after the expression is evaluated, so there is an implied parenthesis, e.g. means .BA -B)(A -10/22/2004 EE 42 fall 2004 lecture 22 14Logic Function Example• Boolean Expression: H = (A · B · C) + TThis can be read H=1 if (A and B and C are 1) or T is 1, orH is true if all of A,B,and C are true, or T is true, orThe voltage at node H will be high if the input voltages at nodes A, B and C are high or the input voltage at node T is high10/22/2004 EE 42 fall 2004 lecture 22 15Logic Function Example 2 Boolean Expression: B = A + S(D + T )This can be read B=1 if A = 1 or S=1 AND (D OR T =1), i.e.B=1 if {A = 1} or {S=1 AND (D OR T =1)}orB is true IF {A is true} OR {S is true AND D OR T is true}orThe voltage at node H will be high if {the input voltage at node A is high} OR {the input voltage at S is high and the voltages at D and T are high}You …
View Full Document
Unlocking...