MIT OpenCourseWare http ocw mit edu 6 080 6 089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 6 080 6 089 GITCS Feb 12 2008 Lecture 3 Lecturer Scott Aaronson 1 1 1 Scribe Adam Rogal Administrivia Scribe notes The purpose of scribe notes is to transcribe our lectures Although I have formal notes of my own these notes are intended to incorporate other information we may mention during class a record for future reference 1 2 Problem sets A few comments on the problem sets Firstly you are welcome to collaborate but please mark on your problem sets the names of whom you worked with Our hope is to try all the problems Some are harder than others there are those marked challenge problems as well If you can t solve the given problem be sure to state what methods you tried and your process up to the point you could not continue This is partial credit and much better than writing a complete but incorrect solution After all according to Socrates the key to knowledge is to know what you don t know 1 3 O ce hours We will have o ce hours once a week 2 2 1 Recap Computer science as a set of rules We can view computer science as the study of simple set of rules and what you can and can t build with them Maybe the rst example of that could be considered Euclidian geometry And the key to discovering what processes we can build is that these rules are well de ned 2 2 Logic The eld of logic focuses on automating or systematizing not just any mechanical processes but rational thought itself If we could represent our thoughts by manipulations of sequences of symbols then in principle we could program a computer to do our reasoning for us We talked the simplest logical systems which were the only ones for thousands of years Syllo gisms and propositional logic the logic of Boolean variables that can be either true or false and related to each other through operators like and or and not We nally discussed rst order logic 3 1 2 2 1 First order logic The system of rst order logic is built up of sentences Each of these sentences contain variables such as x y and z Furthermore we can de ne functions which take these variables as input For example let s de ne a function P rime x Given an integer it will return true if the number is prime false if it is composite Just like functions in any programming languages we can build functions out of other functions by calling them as subroutines In fact many programming languages themselves were modeled after rst order logic Furthermore as in propositional logic symbols such as and or not and implies allow us to relate objects to each other Quanti ers are a crucial part of rst order logic Quanti ers allow us to state propositions such as Every positive integer x is either prime or composite x P rime x Composite x There s a counterexample of course namely 1 We can also say There exists an x such that something is true x Something x When people talk about rst order logic they also normally assume that the equals sign is available 2 2 2 Inference rules We want a set of rules that will allow us to form true statements from other true statements Propositional tautologies A A Modus ponens A A B B Equals Equals X X Equals X Y Equals Y X Transitivity property Equals X Y Equals Y Z Equals X Z Furthermore we have the rule of change of variables If you have a valid sentence that sentence will remain valid if we change variables 2 2 3 Quanti er rules If A x is a valid sentence for any choice of x then for all x A x is a valid sentence Conversely if A x is a valid sentence for all x then any A x for a xed x is a valid sentence A X x A x We also have rules for dealing with quanti ers For example it is false that for all x A x i there exists an x A x x A x A x 3 2 2 2 4 Completeness theorem Kurt Go del proved that the rules thus stated were all the rules we need He proved that if you could not derive a logical contradiction by using this set of rules there must be a way of assigning variables such that all the sentences are satis ed 3 Circuits Electrical engineers views circuits to be complete loops typically represented in gure 1 However in computer science circuits have no loops and are built with logic gates Figure 1 A simple EE circuit 3 1 Logic gates The three best known logic gates are the NOT AND and OR gates shown in gure 2 A D OT OR Figure 2 The logical gates NOT AND and OR Though primitive on their own these logic gates can be strung together to form complex logical operations For example we can design a circuit shown in gure 3 that takes the majority of 3 variables x y and z We can also use De Morgan s law to form a AND gate from an OR gate and vice versa as shown gure 4 OR A D A D A D x y z Figure 3 The majority circuit 3 3 OT A D OR OT OT Figure 4 An AND gate can be constructed from an OR and three NOT gates by using De Morgan s law These logic gates can also be combined to form other gates such as the XOR and NAND gates shown in gure 5 Conversely by starting with the NAND gate we can build any other gate we want A D XOR Figure 5 NAND and XOR gates On the other hand no matter how we construct a circuit with AND and OR gates if the input is all 1 s we can never get an output of 0 We call a Boolean function that can be built solely out of AND and OR gates a monotone Boolean function Are there any other interesting sets of gates that don t let us express all Boolean functions Yes the XOR and NOT gates Because of their linearity no matter how we compose these gates we can never get functions like AND and OR 4 Puzzle Here s an amusing puzzle can you compute the NOT s of 3 input variables using as many AND OR gates as you like but only 2 NOT gates 4 0 1 Limitations Although we have discovered that circuits can be a powerful tool as a model of computation they have some clear limitations Firstly circuits o er no form of storage or memory They also have no feedback the output of a gate never gets fed as the input But from a modern standpoint …