Logic: From Greeks to philosophers to circuits.COS 1163/14/2005Instructor: Sanjeev AroraIn addition to course handouts, many web-based resources; e.g., http://www.allaboutcircuits.com/vol_4/chpt_7/1.html3 equivalent ways of representationBoolean Expression E = S AND D = S· DTruth table – Gives value of E for every possible assignment to D, S.TRUE=1; FALSE= 0.(E is a “Boolean function” of D, S)001011110000ESDBoolean CircuitESDEd goes to the party if Dan doesn’t and Stella doesBoolean “algebra”A AND B written as A · BA OR B written as A + B0 + 0=01 + 0 =11 + 1=10 · 0 =00 · 1 =01·1 = 1Funny arithmeticBoolean gatesOutput voltage is high if both input voltages are high, otherwise output voltage lowHigh voltage = 1Low voltage = 0xxx xyyx · yx + yShannon (1939)Output voltage is high if either input voltage is high, otherwise output voltage lowOutput voltage is high if input voltage is low,otherwise output voltage lowClaude Shannon (1916-2001)founder of many fields (circuits, information theory, artificialintelligence…)With “Theseus” mouseCombinational circuit Boolean gates connected by wires Important: no cycles allowedWires: transmit voltage(and hence value)Examples(Sometimes we use thisfor shorthand)4-way ANDMore complicated exampleCombinational circuits and control “If data has not arrived and packet has been sent, send a signal”Packet sent?Data arrived?ESDCircuits compute functions Every combinational circuit computes a Boolean function of its inputsInputs OutputsBen RevisitedBen only rides to class if he overslept, but even then if it is raining he’ll walk and show up late to class (he really hates to bike in the rain). But if there’s an exam that day he’ll bike if he overslept, even in the rain.B: Ben BikesR: It is rainingE: There is an exam todayO: Ben oversleptGive boolean expression for B in terms of R, E and OBen’s truth table11110011110110010110001001000000BEROGoing from truth table to Boolean expression Take OR of all input combinations that lead to 1B = O·R·E + O·R·E + O·R·E11110011110110010110001001000000BEROAside: AND, OR, and NOT gates suffice to implement every boolean function!Sizes of representations For k variables:1…11……………………1…100…100…000…00X…BAk + 12k1073741824104857610242k302010kTools for reducing size: (a) circuit optimization (b) modular designExpression simplification Some simple rules:x · 1 = xx · 0 = 0x + 0 = xx + 1 = 1x + x = x · x = xx · (y + z) = x · y + x · zx + (y · z) = (x+y) · (x+z)x · y + x · y= x · (y + y)= x · 1= xDe Morgan’s Laws:x · y = x + yx + y = x · ySimplifying Ben’s circuit B = O·R·E + O·R·E + O·R·E= O·(R·E + R·E + R·E)= O·(R·(E + E) + R·E)= O·(R + R·E)= O·((R + R) · (R + E))= O·(R + E)Something to think about: How hard is Circuit Verification? Given a circuit, decide if it is trivial (either it always outputs 1 or always outputs 0 no matter the input) Alternative statement: Decide if there is any setting of the inputs that makes the circuit evaluate to 1. Time required?Boole’s reworking of Clarke’s “proof” of existence of God(see handout) General idea: Try to prove that Boolean expressions E1, E2, …, Ekcannot simultaneously be true Method: Show E1· E2 · … · Ek= 0 Discussion for next time: What exactly does Clarke’s “proof” prove? How convincing is such a proof to you?Also: Do Google search for “Proof of God’s Existence.”Going beyond combinational circuits Need 2-way communication between circuits (i.e., need to allow cycles!) Need memory (scratchpad)CPUEthernet cardCircuit for Binary Addition?25= 1100129= 11101--------------110110Read handout: Will discuss next time.Worked out example: Going from truth table to Boolean expression Take OR of all input combinations that lead to 1X = A·B·C + A·B·C + A·B·C +
View Full Document
Unlocking...