Slide 1MidtermPart 1: Self-ReproductionSlide 4Slide 5Slide 6High-level view of self-reproducing programSelf-reproducing machinesSlide 9Moving on to part 2… Upcoming lectures: Computational HardwareSlide 11Propositional Logic: HistoryExampleEd goes to the party if Dan goes or Stella goesBoolean expressionsTruth tableLet’s work an example…Ben RevisitedBoolean “algebra”Boolean circuitThree Equivalent RepresentationsEd goes to the party if Dan doesn’t AND Stella doesn’tSlide 23Self-reproducing programs. And Introduction to logic.COS 116, Spring 2012Adam FinkelsteinMidtermOne week from today – in class Mar 15Covers lectures, labs, homework, readings to dateOld midterms will be posted on course webMar 12 and 14 lab times will be review feel free to attend either or both come with questionsPart 1: Self-ReproductionFallacious argument for impossibility:BlueprintBlueprintBlueprint“Droste Effect”Fallacy Resolved: “Blueprint” can involve computation; need not be an exact copy! Print the following sentence twice, the second time in quotes. “Print the following sentence twice, the second time in quotes.”High-level view of self-reproducing programPrint 0Print 1...Print 0. . . . . . . . . . . .. . . . . .. . . . . .}Prints binary code of B}Takes binary string on tape, and in its place prints (in English) the sequence of statements that produce it, followed by the translation of the binary string into English.ABSelf-reproducing machines[John von Neumann, 1940s]2-D and 3-D cellular automata(with a “moving arm” controlledby the automaton itself) that makes a precise copy of itself.“Accidental changes” duringcopying --> mutations, evolutionThis and related ideas of Pauli motivated discoveryof the molecular basis of life on earth (DNA, RNA etc.)Moving on to part 2… Upcoming lectures: Computational HardwareBoolean logic and Boolean circuitsSequential circuits (circuits with memory)Clocked circuits and Finite State MachinesCPUsOperating SystemNetworks, InternetBen only rides to class if he overslept, but even then if it is raining he’ll walk and show up late (he hates to bike in the rain). But if there’s an exam that day,he’ll bike if he overslept, even in the rain. Q: It is raining today, Ben overslept, and there’s an exam. Will Ben bike today?“Logical reasoning”, “Propositional logic.”Discussion TimePropositional Logic: HistoryAristotle – Law of excluded middle, Law of contradiction.Stoic Philosophers (3rd century BC) – Basic inference rules (modus ponens etc.)Some work by medieval philosophersDe Morgan and Boole (19th century): Symbolic logic – “automated”, “mechanical”C. Shannon (1930s) – Proposal to use digital hardwareExampleEd goes to the party if Dan does not and Stella does.Choose “Boolean variables” for 3 events:E: Ed goes to partyD: Dan goes to partyS: Stella goes to party}{Each is either TRUE or FALSEE = S AND (NOT D)Alternately: E = S AND DEd goes to the party if Dan goes or Stella goesE = D OR S E is TRUE if one or both of D and S are TRUENote: In everyday language OR has another meaning too!Example: You can eat an orange or an appleLogical “OR”Boolean expressionsComposed of boolean variables, AND, OR, and NOTExamples:D AND ( P OR (NOT Q))C OR D OR ETruth tableLists the truth value of the Boolean expression for all combinations of values for the variables.Boolean Expression E = S AND D001011110000ESDTruth table 0 = FALSE 1 = TRUE Write E for all possible values of D, S.Let’s work an example…Boolean Expression E = D OR SWhat are x and y ?!?y01111x10100ESDPossibilities:x=0, y=0x=0, y=1x=1, y=0X=1, y=1Ben RevisitedB: Ben BikesR: It is rainingE: There is an exam todayO: Ben oversleptBreak up in groups of three and come up with Boolean expression for B in terms of R, E and O. Ben only rides to class if he overslept. But even then if it is raining he’ll walk and show up late (he hates to bike in the rain). But if there’s an exam that day he’ll bike if he overslept, even in the rain.Boolean “algebra”A AND B written as A B A OR B written as A + B0 + 0 = 01 + 0 = 11 + 1 = 10 0 = 00 1 = 01 1 = 1Funny arithmeticBoolean circuitPictorial representation of Boolean expression using Special symbols for AND, OR and NOTA AND BA OR BAThree Equivalent RepresentationsBoolean Expression E = S AND DTruth table:Value of E for every possible D, S. TRUE=1; FALSE= 0.001011110000ESDBoolean CircuitESDEd goes to the party if Dan doesn’t AND Stella doesn’tE = D AND SIs this equivalent to:Ed goes to the party ifNOT (Dan goes OR Stella goes)….?(De Morgan’s Laws)Next time: Boolean circuits, the basic components of the digital worldMidterm will have a question on boolean
View Full Document
Unlocking...