“mcs-ftl” — 2010/9/8 — 0:40 — page 5 — #111 PropositionsDefinition. A proposition is a statement that is either true or false.For example, both of the following statements are propositions. The first is trueand 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 excludestatements 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, oreven what the proposition means. In part, this is because the English language isriddled 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 thecourse.”4. “Every American has a dream.”What precisely do these sentences mean? Can you have both cake and ice creamor must you choose just one dessert? If the second sentence is true, then is theChebyshev bound incomprehensible? If you can solve some problems we come upwith but not all, then do you get an A for the course? And can you still get an Aeven if you can’t solve any of the problems? Does the last sentence imply that allAmericans have the same dream or might some of them have different dreams?Some uncertainty is tolerable in normal conversation. But when we need toformulate ideas precisely—as in mathematics and programming—the ambiguitiesinherent in everyday language can be a real problem. We can’t hope to make anexact argument if we’re not sure exactly what the statements mean. So before westart into mathematics, we need to investigate the problem of how to talk aboutmathematics.To get around the ambiguity of English, mathematicians have devised a specialmini-language for talking about logical relationships. This language mostly usesordinary English words and phrases such as “or”, “implies”, and “for all”. But1“mcs-ftl” — 2010/9/8 — 0:40 — page 6 — #12Chapter 1 Propositionsmathematicians endow these words with definitions more precise than those foundin an ordinary dictionary. Without knowing these definitions, you might sometimesget the gist of statements in this language, but you would regularly get misled aboutwhat they really meant.Surprisingly, in the midst of learning the language of mathematics, we’ll comeacross the most important open problem in computer science—a problem whosesolution could change the world.1.1 Compound PropositionsIn English, we can modify, combine, and relate propositions with words such as“not”, “and”, “or”, “implies”, and “if-then”. For example, we can combine threepropositions 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 propo-sitions are combined and related. So we’ll frequently use variables such as P andQ in place of specific propositions such as “All humans are mortal” and “2 C 3 D5”. The understanding is that these variables, like propositions, can take on onlythe values T (true) and F (false). Such true/false variables are sometimes calledBoolean variables after their inventor, George—you guessed it—Boole.1.1.1 NOT, AND, and ORWe can precisely define these special words using truth tables. For example, ifP denotes an arbitrary proposition, then the truth of the proposition “NOT.P /” isdefined by the following truth table:P NOT.P /T FF TThe 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 /” istrue. This is probably what you would expect.In general, a truth table indicates the true/false value of a proposition for eachpossible setting of the variables. For example, the truth table for the proposition2“mcs-ftl” — 2010/9/8 — 0:40 — page 7 — #131.1. Compound Propositions“P AND Q” has four lines, since the two variables can be set in four different ways:P Q P AND QT T TT F FF T FF F FAccording to this table, the proposition “P AND Q” is true only when P and Q areboth 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 QT T TT F TF T TF F FThe third row of this table says that “P OR Q” is true even if both P and Q aretrue. This isn’t always the intended meaning of “or” in everyday speech, but this isthe standard definition in mathematical writing. So if a mathematician says, “Youmay 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 QT T FT F TF T TF F F1.1.2 IMPLIESThe least intuitive connecting word is “implies.” Here is its truth table, with thelines labeled so we can refer to them later.P Q P IMPLIES QT T T (tt)T F F (tf)F T T (ft)F F T (ff)Let’s experiment with this definition. For example, is the following propositiontrue or false?3“mcs-ftl” — 2010/9/8 — 0:40 — page 8 — #14Chapter 1 Propositions“If the Riemann Hypothesis is true, then x2 0 for every real number x.”The Riemann Hypothesis is a famous unresolved conjecture in mathematics —noone knows if it is true or false. But that doesn’t prevent you from answering thequestion! This proposition has the form P IMPLIES Q where the hypothesis, P , is“the Riemann Hypothesis is true” and the conclusion, Q, is “x2 0 for every realnumber 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 istrue or false. Curiously, the answer has nothing to do with whether or not you canunderstand the Chebyshev bound. Pigs cannot fly, so we’re on either line (ft) orline (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