《Mathematics for Computer》Lecture 11 Logic

6.042/18.] Mathematics for Computer Science February 1, 2005 Srini devadas and Eric Lehman Lecture notes Logic It's really sort of amazing that people manage to communicate in the English language Here are some typical sentences: 1. You may have cake or you may have ice cream 2. If pigs can fly, then you can understand the Chernoff bound 3. If you can solve any problem we come up with then you get an a for the course. 4. Every American has a dream What precisely do these sentences mean? Can you have both cake and ice cream or must you choose just one desert? If the second sentence is true, then is the Chernoff bound incomprehensible? If you can solve some problems we come up with but not all, then do you get an a for the course? And can you still get an a even if you cant solve any of the problems? Does the last sentence imply that all Americans have the same dream or might they each have a different dream? Some uncertainty is tolerable in normal conversation. But when we need to formu late ideas precisely-as in mathematics-the ambiguities inherent in everyday language become a real problem. We cant hope to make an exact argument if were not sure ex actly what the individual words mean. (And, not to alarm you, but it is possible that we'll be making an awful lot of exacting mathematical arguments in the weeks ahead. ) So be- fore we start into mathematics, we need to investigate the problem of how to talk about mathematics To get around the ambiguity of English, mathematicians have devised a special mini- language for talking about logical relationships. This language mostly uses ordinary English words and phrases such as"or","implies",and"for all". But mathematicians endow these words with definitions more precise than those found in an ordinary dictio- nary. Without knowing these definitions, you could sort of read this language, but you would miss all the subtleties and sometimes have trouble following along Surprising ngly, in the midst of learning the language of logic, we'll come across the most important open problem in computer science- a problem whose solution could chang he world

6.042/18.062J Mathematics for Computer Science February 1, 2005 Srini Devadas and Eric Lehman Lecture Notes Logic It’s really sort of amazing that people manage to communicate in the English language. Here are some typical sentences: 1. “You may have cake or you may have ice cream.” 2. “If pigs can fly, then you can understand the Chernoff bound.” 3. “If you can solve any problem we come up with, then you get an A for the course.” 4. “Every American has a dream.” What precisely do these sentences mean? Can you have both cake and ice cream or must you choose just one desert? If the second sentence is true, then is the Chernoff bound incomprehensible? If you can solve some problems we come up with but not all, then do you get an A for the course? And can you still get an A even if you can’t solve any of the problems? Does the last sentence imply that all Americans have the same dream or might they each have a different dream? Some uncertainty is tolerable in normal conversation. But when we need to formu￾late ideas precisely— as in mathematics— the ambiguities inherent in everyday language become a real problem. We can’t hope to make an exact argument if we’re not sure ex￾actly what the individual words mean. (And, not to alarm you, but it is possible that we’ll be making an awful lot of exacting mathematical arguments in the weeks ahead.) So be￾fore we start into mathematics, we need to investigate the problem of how to talk about mathematics. To get around the ambiguity of English, mathematicians have devised a special mini￾language for talking about logical relationships. This language mostly uses ordinary English words and phrases such as “or”, “implies”, and “for all”. But mathematicians endow these words with definitions more precise than those found in an ordinary dictio￾nary. Without knowing these definitions, you could sort of read this language, but you would miss all the subtleties and sometimes have trouble following along. Surprisingly, in the midst of learning the language of logic, we’ll come across the most important open problem in computer science— a problem whose solution could change the world

1 Propositions A proposition is a statement that is either true or false. This definition is a little vague, but it does exclude sentences such as, What's a surjection, again? and"Learn logarithms Here are some examples of propositions All greeks are human All humans are mortal "All Greeks are mortal Archimedes spent a lot of time fussing with such propositions in the 4th century BC while developing an early form of logic. These are perfectly good examples, but we'll be more concerned with propositions of a more mathematical flavor 2+3=5′ This proposition happens to be true. Sometimes the truth of a proposition is more difficult to determine 6+a=d has no solution where a, b, c are positive integers Euler made this conjecture in 1769. For 218 years no one knew whether this proposition was true or false. Finally, Noam Elkies who works at the liberal arts school up Mass Ave found a solution to the equation: a= 2682440, b= 15365639, c= 18796760, d= 20615673 So the proposition is false! There are many famous propositions about primes. Recall that a prime is an integer greater than 1 not divisible by any positive integer other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, and 13. On the other hand 9 and 77 are not primes, because 9 is divisible by 3 and 77 is divisible by 7. The following proposition is called Goldbach's Conjecture, after Christian Goldbach who first stated it in 1742 Every even integer greater than 2 is the sum of two primes Even today, no one knows whether Goldbach's Conjecture is true or false. Every even integer ever checked is a sum of two primes, but just one exception would disprove the For the next while, we won't be much concerned with the internals of propositions whether they involve mathematics or greek mortality--but rather with how propositions are combined and related. So we'll frequently use variables such as P and Q in place of specific propositions such as"All humans are mortal"and2+3=5". The understanding that these variables, like propo take nly the values and“ false Such true/false variables are sometimes called Boolean variables after their inventor eorge something-or-other

2 Logic 1 Propositions A proposition is a statement that is either true or false. This definition is a little vague, but it does exclude sentences such as, “What’s a surjection, again?” and “Learn logarithms!” Here are some examples of propositions. “All Greeks are human.” “All humans are mortal.” “All Greeks are mortal.” Archimedes spent a lot of time fussing with such propositions in the 4th century BC while developing an early form of logic. These are perfectly good examples, but we’ll be more concerned with propositions of a more mathematical flavor: “2 + 3 = 5” This proposition happens to be true. Sometimes the truth of a proposition is more difficult to determine: 4 “a + b4 + c4 = d4 has no solution where a, b, c are positive integers.” Euler made this conjecture in 1769. For 218 years no one knew whether this proposition was true or false. Finally, Noam Elkies who works at the liberal arts school up Mass Ave. found a solution to the equation: a = 2682440, b = 15365639, c = 18796760, d = 20615673. So the proposition is false! There are many famous propositions about primes. Recall that a prime is an integer greater than 1 not divisible by any positive integer other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, and 13. On the other hand, 9 and 77 are not primes, because 9 is divisible by 3 and 77 is divisible by 7. The following proposition is called Goldbach’s Conjecture, after Christian Goldbach who first stated it in 1742. “Every even integer greater than 2 is the sum of two primes.” Even today, no one knows whether Goldbach’s Conjecture is true or false. Every even integer ever checked is a sum of two primes, but just one exception would disprove the claim. For the next while, we won’t be much concerned with the internals of propositions— whetherthey involve mathematics or Greek mortality— butrather with how propositions are combined and related. So we’ll frequently use variables such as P and Q in place of specific propositions such as “All humans are mortal” and “2+3 = 5”. The understanding is that these variables, like propositions, can take on only the values “true” and “false”. Such true/false variables are sometimes called Boolean variables after their inventor, George something­or­other

Logic 1.1 Combining Propositions In English, we can modify, combine, and relate propositions with words such as"not " and""or"implies", and" if-then". For example we can combine three propositions Into one like If all humans are mortal and all greeks are human then all greeks are mortal 111“Not,"And"and"Or We can precisely define these special words using truth tables. For example, if P denotes an arbitrary proposition, then the validity of the proposition"not P"is defined by the following truth table P not P The first row of the table indicates that when proposition P is true(), the proposition ot p"is false(F). The second line indicates that when P is false IS probably what you would expect al, a truth table indicates the true /false value of a proposition for( setting of the variables. For example, the truth table for the proposition "P and Q"has four lines, since the two variables can be set in four different ways PLaNd Q TTFF TFFF According to this table, the proposition"P and Q" is true only when P and Q are both true. This is probably reflects the way you think about the word"and There is a subtlety in the truth table for "P or Q PQ Por Q TFF TFTF TTTE This says that"P or Q"is true when P is true, Q is true, or both are true. This isn't always the intended meaning of"or"in everyday speech, but this is the standard definition in mathematical writing. So if a mathematician says, You may have cake or your may hav ice cream", then you can have both

Logic 3 1.1 Combining Propositions In English, we can modify, combine, and relate propositions with words such as “not”, “and”, “or”, “implies”, and “if­then”. For example, we can combine three propositions into one like this: If all humans are mortal and all Greeks are human, then all Greeks are mortal. 1.1.1 “Not”, “And” and “Or” We can precisely define these special words using truth tables. For example, if P denotes an arbitrary proposition, then the validity of the proposition “not P” is defined by the following truth table: P not P T F F T The first row of the table indicates that when proposition P is true (T), the proposition “not P” is false (F). The second line indicates that when P is false, “not P” is true. This is probably what you would expect. In general, a truth table indicates the true/false value of a proposition for each possible setting of the variables. For example, the truth table for the proposition “P and Q” has four lines, since the two variables can be set in four different ways: P Q T T T T F F F T F F F F P and Q According to this table, the proposition “P and Q” is true only when P and Q are both true. This is probably reflects the way you think about the word “and”. There is a subtlety in the truth table for “P or Q”: P Q T T T T F T F T T F F F P or Q This says that “P or Q” is true when P is true, Q is true, or both are true. This isn’t always the intended meaning of “or” in everyday speech, but this is the standard definition in mathematical writing. So if a mathematician says, “You may have cake or your may have ice cream”, then you can have both

112“ Implies The least intuitive connecting word is"implies". Mathematicians regard the propositi P implies Q"and"if P then Q"as synonymous, so both have the same truth table. (The lines are numbered so we can refer to the them later. P miLl P Q if P then Q 123 TTFF FTF TFTT Let's experiment with this definition. For example, is the following proposition true false? If Goldbach's Conjecture is true then >0 for every real number z. Now, we told you before that no one knows whether Goldbach's Conjecture is true or false. But that doesnt prevent you from answering the question This proposition has the form P=Q where P is"Goldbach's Conjecture is true"and Q is"->0 for every real number a". Since Q is definitely true, were on either line 1 or line 3 of the truth table Either way, the proposition as a whole is true One of our original examples demonstrates an even stranger side of implications pigs fly, then you can understand the Chernoff bound Don t take this as an insult; we just need to figure out whether this proposition is true or false. Curiously, the answer has nothing to do with whether or not you can understand the Chernoff bound. Pigs do not fly, so we re on either line 3 or line 4 of the truth table In both cases, the proposition is true n contrast, here's an example of a false implication "If the moon is white then the moon is made of white cheddar Yes, the moon is white. But, no, the moon is not made of white cheddar cheese. So we're on line 2 of the truth table, and the proposition is false The truth table for implications can be summarized in words as follows An implication is true when the if-part is false or the then-part is true This sentence is worth remembering; a large fraction of all mathematical statements are the if-then form!

4 Logic 1.1.2 “Implies” The least intuitive connecting word is “implies”. Mathematicians regard the propositions “P implies Q” and “if P then Q” as synonymous, so both have the same truth table. (The lines are numbered so we can refer to the them later.) P Q 1. T T T 2. T F F 3. F T T 4. F F T P implies Q, if P then Q Let’s experiment with this definition. For example, is the following proposition true or false? 2 “If Goldbach’s Conjecture is true, then x ≥ 0 for every real number x.” Now, we told you before that no one knows whether Goldbach’s Conjecture is true or false. But that doesn’t prevent you from answering the question! This proposition has the 2 form P ⇒ Q where P is “Goldbach’s Conjecture is true” and Q is “x ≥ 0 for every real number x”. Since Q is definitely true, we’re on either line 1 or line 3 of the truth table. Either way, the proposition as a whole is true! One of our original examples demonstrates an even stranger side of implications. “If pigs fly, then you can understand the Chernoff bound.” Don’t take this as an insult; we just need to figure out whether this proposition is true or false. Curiously, the answer has nothing to do with whether or not you can understand the Chernoff bound. Pigs do not fly, so we’re on either line 3 or line 4 of the truth table. In both cases, the proposition is true! In contrast, here’s an example of a false implication: “If the moon is white, then the moon is made of white cheddar.” Yes, the moon is white. But, no, the moon is not made of white cheddar cheese. So we’re on line 2 of the truth table, and the proposition is false. The truth table for implications can be summarized in words as follows: An implication is true when the if­part is false or the then­part is true. This sentence is worth remembering; a large fraction of all mathematical statements are of the if­then form!

Logic 113“ If and only If Mathematicians commonly join propositions in one additional way that doesn't arise in ordinary speech. The proposition"P if and only if Q"asserts that P and Q are logically equivalent; that is, either both are true or both are false P QPif and only迁Q T F F T FF FFT The following if-and-only-if statement is true for every real numberz: x2-4≥0 if and only if a≥2 For some values of both inequalities are true. For other values of a, neither inequality is true. In every case however, the proposition as a whole is true The phrase"if and only if"comes up so often that it is often abbreviated"iff 1.2 Propositional Logic in Computer Programs Propositions and logical connectives arise all the time in computer programs. For exam- ple, consider the following snippet, which could be either C, C++, or Java if(x>0|(x<=0y>100)) ffurther instructions) The symbol II denotes"or", and the symbol & denotes"and". The further instructions are carried out only if the proposition following the word if is true. On closer inspection, this big expression is built from two simpler propositions. Let A be the proposition that x >0, and let b be the proposition that y >100. Then we can rewrite the condition this A truth table reveals that this complicated expression is logically equivalent to"A or B A BAor((not A)and B)A or B F T T T FF F F This means that we can simplify the code snippet without changing the programs behav-

Logic 5 1.1.3 “If and Only If” Mathematicians commonly join propositions in one additional way that doesn’t arise in ordinary speech. The proposition “P if and only if Q” asserts that P and Q are logically equivalent; that is, either both are true or both are false. P Q T T T T F F F T F F F T P if and only if Q The following if­and­only­if statement is true for every real number x: 2 “x − 4 ≥ 0 if and only if | | x ≥ 2” For some values of x, both inequalities are true. For other values of x, neither inequality is true . In every case, however, the proposition as a whole is true. The phrase “if and only if” comes up so often that it is often abbreviated “iff”. 1.2 Propositional Logic in Computer Programs Propositions and logical connectives arise all the time in computer programs. For exam￾ple, consider the following snippet, which could be either C, C++, or Java: if ( x > 0 || (x <= 0 && y > 100) ) (further instructions) The symbol || denotes “or”, and the symbol && denotes “and”. The further instructions are carried out only if the proposition following the word if is true. On closer inspection, this big expression is built from two simpler propositions. Let A be the proposition that x > 0, and let B be the proposition that y > 100. Then we can rewrite the condition this way: A or ((not A) and B) A truth table reveals that this complicated expression is logically equivalent to “A or B”. A B T T T T T F T T F T T T F F F F A or ((not A) and B) A or B This means that we can simplify the code snippet without changing the program’s behav￾ior: