mcs ftl 2010 9 8 0 40 page 5 11 1 Propositions Definition A proposition is a statement that is either true or false For example both of the following statements are propositions The first is true and the second is false Proposition 1 0 1 2 3 5 Proposition 1 0 2 1 1 3 Being true or false doesn t sound like much of a limitation but it does exclude statements such as Wherefore art thou Romeo and Give me an A Unfortunately it is not always easy to decide if a proposition is true or false or even what the proposition means In part this is because the English language is riddled with ambiguities For example consider the following statements 1 You may have cake or you may have ice cream 2 If pigs can fly then you can understand the Chebyshev 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 dessert If the second sentence is true then is the Chebyshev 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 some of them have different dreams Some uncertainty is tolerable in normal conversation But when we need to formulate ideas precisely as in mathematics and programming the ambiguities inherent in everyday language can be a real problem We can t hope to make an exact argument if we re not sure exactly what the statements mean So before 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 1 mcs ftl 2010 9 8 0 40 page 6 12 Chapter 1 Propositions mathematicians endow these words with definitions more precise than those found in an ordinary dictionary Without knowing these definitions you might sometimes get the gist of statements in this language but you would regularly get misled about what they really meant Surprisingly in the midst of learning the language of mathematics we ll come across the most important open problem in computer science a problem whose solution could change the world 1 1 Compound 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 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 and 2 C 3 D 5 The understanding is that these variables like propositions can take on only the values T true and F false Such true false variables are sometimes called Boolean variables after their inventor George you guessed it Boole 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 truth of the proposition NOT P is defined by the following truth table P T F NOT P F T The first row of the table indicates that when proposition P is true the proposition NOT P is false 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 2 mcs ftl 2010 9 8 0 40 page 7 13 1 1 Compound Propositions P AND Q has four lines since the two variables can be set in four different ways P Q P T T T F F T F F AND Q T F F F According to this table the proposition P AND Q is true only when P and Q are both true This is probably the way you think about the word and There is a subtlety in the truth table for P OR Q P Q P OR Q T T T T F T F T T F F F The third row of this table says that P OR Q is true even if both P and Q 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 you may have ice cream he means that you could have both If you want to exclude the possibility of both having and eating you should use exclusive or XOR P Q P XOR Q T T F T F T F T T F F F 1 1 2 IMPLIES The least intuitive connecting word is implies Here is its truth table with the lines labeled so we can refer to them later P Q P T T T F F T F F IMPLIES T F T T Q tt tf ft ff Let s experiment with this definition For example is the following proposition true or false 3 mcs ftl 2010 9 8 0 40 page 8 14 Chapter 1 Propositions If the Riemann Hypothesis is true then x 2 0 for every real number x The Riemann Hypothesis is a famous unresolved conjecture in mathematics no one knows if it is true or false But that doesn t prevent you from answering the question This proposition has the form P IMPLIES Q where the hypothesis P is the Riemann Hypothesis is true and the conclusion Q is x 2 0 for every real number x Since the conclusion is definitely true we re on either line tt or line ft of the truth table Either way the proposition as a while is true One of our original examples demonstrates an even stranger side of implications If pigs can fly then you can understand the Chebyshev 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 Chebyshev bound Pigs cannot fly so we re on either line ft or line ff of the truth table In both cases the proposition is true In contrast here s an example of a false implication If the moon shines white then the moon …